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
-
Official comment
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
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
Post is closed for comments.
Comments
7 comments