Capacitated Vehicle Routing Problem - Formulation & Code
Awaiting user input
Hello,
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/en-us/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 Big-M constraints, single/multi-commodity 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