Capacitated Vehicle Routing Problem  Formulation & Code
Awaiting user inputHello,
Hope this finds you well and safe.
I am trying to implement a BIP on Python using Gurobi module. The code ran without any errors however the result was a bit misleading. At this stage I am not sure if it's a formulation misinterpretation or I did not write the code correctly. I simplified the inputs to check first if the code is running. Below you will see the parameters and sets values.
Appreciate your support!
MIP Model:
Code:
import gurobipy as gp
from gurobipy import*
mdl = Model("VRP")
'''
Sets and parameters
'''
N = [1, 2, 3, 4]
V = [0,1,2,3,4]
K = [1, 2]
A = [(i,j) for i in V for j in V if i!=j]
q = {1:6, 2:2, 3:4, 4:3}
C = {1:8, 2:4}
M = {1:1, 2:2}
'''
cost matrix
'''
c = {(0,1): 3,
(0, 2): 4,
(0, 3): 5,
(0, 4):2,
(1, 0):3,
(1, 2):5,
(1, 3):7,
(1, 4):5,
(2, 0):4,
(2, 1):5,
(2, 3):9,
(2, 4):6,
(3, 0):5,
(3, 1):7,
(3, 2):9,
(3, 4):4,
(4, 0):2,
(4, 1):5,
(4, 2):6,
(4, 3):4
}
'''
Decision Variable
'''
pairs= [(i,j,k) for i in V for j in V for k in K]
x = mdl.addVars(pairs, vtype=GRB.BINARY, name ="x")
mdl.modelSense = GRB.MINIMIZE
'''
Constraints
'''
mdl.addConstrs(quicksum(x[i,j,k] for k in K for i in V if i != j) == 1 for j in N)
mdl.addConstrs(quicksum(x[0,j,k] for j in N ) <= M[k] for k in K)
mdl.addConstrs((quicksum(x[i,j,k] for i in V)  quicksum(x[j,i,k] for i in V)) == 0 for j in V for k in K)
mdl.addConstrs(quicksum(x[i,j,k] for i in V for j in N if j != i) <= C[k] for k in K)
mdl.addConstrs(x[i,i,k] == 0 for i in V for k in K)
'''
Objective Function
'''
mdl.setObjective(quicksum(x[i]*c[arcs] for i in pairs for arcs in A))
'''
Solve
'''
mdl.Params.MIPGap = 0.1
mdl.Params.TimeLimit = 30 # seconds
mdl.optimize()
x[1,2,1] = 1
x[2,4,1] = 1
x[3,1,1] = 1
x[4,3,1] = 1

This is a continuation of https://support.gurobi.com/hc/enus/community/posts/4403683886993
0 
Hi Wissam,
Could you elaborate or what exactly is strange with the formulation/implementation?
To my understanding your objective function should read
mdl.setObjective(quicksum(x[i,j,k]*c[(i,j)] for (i,j) in A for k in K))
Is this the source of the problem?
I would also recommend to work with the write() function and check whether the model you constructed is the one you also expect it to be.
mdl.write("myLP.lp")
Best regards,
Jaromił0 
In the results, there should be active arcs leaving the depot and it shows none. In addition, there is one vehicle type 1 and it cannot satisfy all the customers' demand at the same time.
I rewrote the objective function like you recommended and I got the same solution.
Will review and get back with new findings.
Thank you for your support!
Regards,
0 
Hi Wissam,
Usually, you should define a set of edges and then define your \(\texttt{x}\) variables over it. I guess in your case, the set of edges is defined as \(\texttt{A}\).
Best regards,
Jaromił0 
Since I just stumbled over this old thread:
Note that there are constraints missing that eliminate vehicle subtours that are separated from the depot.
There are many ways to do that, using BigM constraints, single/multicommodity flows, connectivity cuts, etc.0 
Additionally, since variable index k defines a vehicle type and not a single vehicle, the capacity constraint for one particular k is too restrictive since it sums up the demands served by all vehicles of some type.
0
Please sign in to leave a comment.
Comments
6 comments