1
$\begingroup$

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?

$\endgroup$
3
  • 4
    $\begingroup$ 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? $\endgroup$
    – Kuifje
    Dec 20, 2022 at 12:29
  • $\begingroup$ I'm trying to solve the VRP where K is the number of vehicules like in this blog:medium.com/jdsc-tech-blog/… $\endgroup$
    – MAYA
    Dec 20, 2022 at 14:00
  • 1
    $\begingroup$ 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. $\endgroup$
    – PeterD
    Dec 20, 2022 at 20:37

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.