I'm trying to use Pulp to solve VRP problem. Here is the model:
for K in range(1,K+1):
# set problem type
problem = pulp.LpProblem('Etrash_Model', pulp.LpMinimize)
# set decision valiables
#x = pulp.LpVariable.dicts('x', ((i, j, k) for k in range(1,K+1) for i in V for j in V if i!=j ), lowBound=0, upBound=1, cat='Binary')
#y = pulp.LpVariable.dicts('y',(i for i in range(1,K+1)), lowBound=0, upBound=1, cat='Binary')
#x=pulp.LpVariable.dicts('x', ((i, j,k) for i in V for j in V for k in range(K) if i!=j ), lowBound=0, upBound=1, cat='Binary')
#u = pulp.LpVariable.dicts('u',N, lowBound=0, cat='Continuous')
#print("Customer set ", V)
x = [[[pulp.LpVariable("x%s_%s,%s"%(i,j,k), cat="Binary") if i != j else None for k in range(K)] for j in range(n)] for i in range(n)]
#print("decision variables ", x)
#set objective function
problem += pulp.lpSum([distances[i][j] * x[i][j][k] if j!=i else None for i in range(n) for j in range(n) for k in range(K)])
#set constraints
#cst 2
for j in range(1,n) :
problem+= pulp.lpSum(x[i][j][k] if j!=i else 0
for i in range(n)
for k in range(K)) ==1
#cst 3
for k in range(K):
problem += pulp.lpSum(x[0][j][k] for j in range(1,n)) == 1
problem += pulp.lpSum(x[i][0][k] for i in range(1,n)) == 1
#cst 4
for k in range(K):
for j in range(n):
problem += pulp.lpSum(x[i][j][k] if i != j else 0 for i in range(n)) - pulp.lpSum(x[j][i][k] for i in range(n)) == 0
#cst 5
for k in range(K):
problem += pulp.lpSum(df.demand[j] * x[i][j][k] if i != j else 0 for i in range(n) for j in range(1,n)) <= vehicle_capacity
# eliminate subtour (cst 6)
subtours = []
for i in range(2,n):
subtours += itertools.combinations(range(1,n), i)
for s in subtours:
problem += pulp.lpSum(x[i][j][k] if i !=j else 0 for i, j in itertools.permutations(s,2) for k in range(K)) <= len(s) - 1
# print vehicle_count which needed for solving problem
# print calculated minimum distance value
status = problem.solve()
if status == 1:
print("ok---------------------")
print('Vehicle Requirements:', K)
print('Moving Distance:', pulp.value(problem.objective))
status, pulp.LpStatus[status], pulp.value(problem.objective)
break
The problem that I get these solutions:
ok---------------------
Vehicle Requirements: 2
Moving Distance: 667.1482646478239
ok---------------------
Vehicle Requirements: 3
Moving Distance: 788.1102137014474
And when asking the optimal:
status, pulp.LpStatus[status], pulp.value(problem.objective)
(1, 'Optimal', 788.1102137014474)
I don't understand why it is 788.11. It would be 667.14 since it is a minimization problem.
What am I missing?
for K in range(1,K+1)
), and the last line (status, pulp.LpStatus[status], pulp.value(problem.objective)
) is just calling the objective value for the last of these linear programs. You setup is a bit odd. What exactly are you trying to achieve? $\endgroup$