Vehicle Routing Problem with Time Windows with Gurobi and Python
Answered
Hi Team Gurobi!
I'm trying to model and solve Toth and Vigo's VRPTW formulation in Python with Gurobi. The model is really slow, even though I'm only running with 25 customers with fairly relaxed time windows. Any suggestions as to why the model is weak? I'm new to Gurobi, and any help would be much appreciated.
Kind regards,
Mads Hoffmann
# Init
from gurobipy import *
import numpy as np
import matplotlib as plt
from pandas import *
import pandas as pd
from gurobipy import GRB
from gurobipy import quicksum
# nodes and vehicles
data = pd.read_csv('DTUDistanceMatrix Car 100.CSV', sep=';')
n = 26
numVehicles = 1
# vehicles and capacity
vehicles = []
for i in range(numVehicles):
vehicles.append(i+1)
# customers
customers = [ i for i in range(n) if i != 0]
nodes = [0]+customers
# arcs
arcs = [(i,j) for i in nodes for j in nodes if i!= j]
Q = 144
q = data.values[0:n,106].astype(int)
q = q.tolist()
e = data.values[0:n,104].astype(int)
l = data.values[0:n,105].astype(int)
s = data.values[0:n,107].astype(int)
s = s.tolist()
# distance matrix
dist1=data.values[0:n,1:n+1]
time_matrix = distance_to_time(dist1) # convert to time matrix
dist=np.array(time_matrix)
time = np.array(time_matrix)
bigM=max(s)+max(l)+np.max(dist)-max(e)
# Gurobi model
# arcs in model
arc_var = [(i,j,k) for i in nodes for j in nodes for k in vehicles]
arc_time = [(i,k) for i in nodes for k in vehicles]
# model
model = Model('VRPTW')
# variables
x = model.addVars(arc_var, vtype=GRB.BINARY, name ='x')
t = model.addVars(arc_time, vtype=GRB.CONTINUOUS, name = 't')
# 5.1 objective function
model.setObjective(quicksum(dist[i,j]*x[i,j,k] for i,j,k in arc_var),GRB.MINIMIZE)
# 5.2
model.addConstrs(quicksum(x[i,j,k] for j in nodes for k in vehicles)==1 for i in customers)
# 5.3
model.addConstrs(quicksum(x[0,j,k] for j in customers)==1 for k in vehicles)
# 5.4
model.addConstrs(quicksum(x[i,j,k] for i in nodes)-quicksum(x[j,i,k] for i in nodes)==0 for j in customers for k in vehicles)
# 5.5
model.addConstrs(quicksum(x[i,0,k] for i in customers)==1 for k in vehicles)
# 5.6
model.addConstrs(t[i,k]+s[i]+time[i][j]-t[j,k] <= (1-x[i,j,k])*BigM for i in customers for j in customers for k in vehicles)
# 5.7
model.addConstrs(t[i,k] >=e[i] for i,k in arc_time)
model.addConstrs(t[i,k] <=l[i] for i,k in arc_time)
# 5.8
model.addConstrs(quicksum(q[i] * quicksum(x[i, j, k] for j in nodes) for i in customers) <= Q for k in vehicles)
model.setParam('MIPGap', 0.005)
model.optimize()
-
Hi Mads,
The Big-M model is known to provide only weak dual bounds. There are a few things that can be improved in this formulation, e.g., to avoid the vehicle index k if the fleet is homogeneous. You could take a look at my notebooks on the CVRP and the VRPTW here: https://github.com/ruthmair/vrp
In this notebooks I also show different formulations that might provide better dual bounds.
Still, VRPs are very tough to solve, even for small sizes with less than 100 customers. All the formulations in my notebooks above are NOT state-of-the-art, they are mainly easy to use. State-of-the-art solution approaches are based on branch-prize-and-cut algorithms that are very sophisticated to implement.
Best regards,
Mario1 -
Thank you Mario! Some very helpful information.
Why is it important to linearize the MIP with big-M?
Is it necessary to linearize VRPs?
Im trying to work out why the big M is necessary.
Have a lovely weekend.
Kind regards,
Mads0 -
In the formulation from your initial screenshot, constraints (5.6) ensure that the time windows are satisfied. But in this type of formulation, those constraints are quadratic. You could also add quadratic constraints to Gurobi but in most cases performance will be worse than linearizing those constraints via Big-Ms. But you could still try!
There are other types of VRP formulations, e.g., the single-commodity flow model in the notebook I linked above. In this case you do not need to linearize since it is a different modeling concept.
There are even better formulations based on route variables where one variable corresponds to a whole route. To solve such formulations you need to implement column (and cut) generation methods that are not easy to do. If you manage to implement them correctly, the solution performance will be much better though.
0 -
Mario Ruthmair correct me if I am wrong but Gurobi does not allow to do Branch-Price-Cut right? we can only apply the pricing at the root node.
Best regards,
0 -
Indeed, Gurobi (and most other commercial solvers) do not provide a branch-price-and-cut framework. What people are usually doing is:
- Use Gurobi (or another solver) only as LP solver and implement their own custom branch-and-bound framework. The benefit is that you have full control of branching, cutting, node selection, etc., and are able to customize it to your application.
- As you mentioned already, it is possible with Gurobi to do column generation in the root node of the branch-and-bound tree and then keep the variable set fixed in the branch-and-bound phase. Note that this approach might not give you an optimal solution, this is just a heuristic.
- Use an alternative solver like SCIP that implements branch-price-and-cut. You might not have the same performance as with commercial solvers, but there is no need for your own implementation.
- There are other very successful approaches, e.g., by Baldacci et al., that do not require a branch-and-price framework to solve route-based formulations.
0 -
Can you I see how your cvs data looks like?
0
Please sign in to leave a comment.
Comments
7 comments