# Problem of optimal solution generated with Pulp

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[j][k] for j in range(1,n)) == 1
problem += pulp.lpSum(x[i][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


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?

• You are solving a series of $K$ linear programs (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? Dec 20, 2022 at 12:29
• I'm trying to solve the VRP where K is the number of vehicules like in this blog:medium.com/jdsc-tech-blog/…
– MAYA
Dec 20, 2022 at 14:00
• is the problem with 2 vehicles solved to optimality? I believe that, if no feasible solution has been found within the time limit, pulp might return an infeasible solution that e.g., violates integrality constraints. Dec 20, 2022 at 20:37