Solving VRP with time window doesn't converge but it makes plausible solution
OngoingHello,
I'm using MILP to solve VRPTW.
The problem is when the dataset gets larger the calculation won't converge, which is the BestBd value won't change after several minutes.
But when I halt the program, it gives me a solution that is plausible and actually better than other solver software.
So the question is, is there anything I can try? Or is this an expected behavior?
I tried changing several parameters below with some cobinations.
model.Params.NoRelHeurTime=100
model.Params.Heuristics=0.5
model.Params.MIPFocus=1
model.Params.Method=0
Here is the log.
Optimize a model with 5103 rows, 2601 columns and 19411 nonzeros
Model fingerprint: 0xb949d379
Model has 49 quadratic objective terms
Variable types: 100 continuous, 2501 integer (2450 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+02]
Objective range [7e-02, 8e-01]
QObjective range [2e+00, 2e+00]
Bounds range [1e+00, 1e+01]
RHS range [1e+00, 1e+02]
Presolve removed 816 rows and 249 columns
Presolve time: 0.04s
Presolved: 4336 rows, 2401 columns, 17207 nonzeros
Variable types: 98 continuous, 2303 integer (2253 binary)
Root relaxation: objective 2.257021e-01, 520 iterations, 0.02 seconds (0.02 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 0.22570 0 54 - 0.22570 - - 0s
H 0 0 80.0074131 0.22570 100% - 0s
H 0 0 69.9376504 0.22570 100% - 0s
H 0 0 69.2246282 0.22570 100% - 0s
H 0 0 67.9371765 0.22575 100% - 0s
0 0 0.22575 0 151 67.93718 0.22575 100% - 0s
H 0 0 61.1428414 0.22575 100% - 0s
H 0 0 61.0969246 0.22575 100% - 0s
0 0 0.22575 0 148 61.09692 0.22575 100% - 0s
H 0 0 60.7673378 0.22702 100% - 1s
H 0 0 60.7537920 0.22702 100% - 1s
0 0 0.22702 0 157 60.75379 0.22702 100% - 1s
H 0 0 57.8257696 0.22702 100% - 1s
0 0 0.23449 0 137 57.82577 0.23449 100% - 1s
0 0 0.24587 0 138 57.82577 0.24587 100% - 1s
0 0 0.24657 0 127 57.82577 0.24657 100% - 1s
H 0 0 55.3017919 0.24839 100% - 1s
0 0 0.24839 0 134 55.30179 0.24839 100% - 1s
0 0 0.24869 0 143 55.30179 0.24869 100% - 1s
0 0 0.24869 0 117 55.30179 0.24869 100% - 1s
0 0 0.26893 0 139 55.30179 0.26893 100% - 2s
H 0 0 55.2040245 0.26893 100% - 2s
0 0 0.27119 0 142 55.20402 0.27119 100% - 2s
0 0 0.27153 0 147 55.20402 0.27153 100% - 2s
0 0 0.27153 0 137 55.20402 0.27153 100% - 2s
H 0 0 55.1360537 0.27153 100% - 2s
0 0 0.27401 0 87 55.13605 0.27401 100% - 2s
H 0 0 50.0772778 0.27401 99.5% - 3s
H 0 0 49.9259832 0.27401 99.5% - 3s
H 0 2 49.5256481 0.27401 99.4% - 3s
0 2 0.27401 0 77 49.52565 0.27401 99.4% - 3s
H 2 4 49.4873881 0.27401 99.4% 850 3s
H 5 8 49.3455698 0.27401 99.4% 514 3s
H 7 16 49.0369253 0.27500 99.4% 452 4s
H 31 64 48.3667711 0.27500 99.4% 477 5s
H 52 64 48.0060443 0.27500 99.4% 419 5s
H 103 128 47.6830216 0.27500 99.4% 393 9s
H 159 192 47.3940071 0.27500 99.4% 323 16s
H 160 192 47.3815446 0.27500 99.4% 324 16s
H 161 192 47.2929219 0.27500 99.4% 323 16s
H 164 192 46.5474849 0.27500 99.4% 320 16s
H 165 192 46.1934013 0.27500 99.4% 319 16s
H 194 224 45.8156662 0.27500 99.4% 307 17s
H 200 224 45.8022425 0.27500 99.4% 305 17s
H 223 256 44.8097473 0.27500 99.4% 297 21s
H 225 256 44.5331845 0.27500 99.4% 296 21s
H 247 256 44.3225474 0.27500 99.4% 289 21s
H 250 256 44.1694361 0.27500 99.4% 288 21s
319 352 0.28167 12 121 44.16944 0.27500 99.4% 267 25s
H 335 352 43.9636861 0.27500 99.4% 263 25s
H 380 384 43.4633165 0.27500 99.4% 260 28s
H 799 1009 43.4317811 0.27500 99.4% 245 29s
H 807 1009 43.0767943 0.27500 99.4% 245 29s
1011 1476 0.28240 26 122 43.07679 0.27500 99.4% 233 30s
H 1487 1508 43.0385343 0.27500 99.4% 221 32s
H 1498 1508 42.8453288 0.27500 99.4% 222 32s
H 1514 1508 42.7659166 0.27500 99.4% 222 32s
2135 2058 0.28381 41 107 42.76592 0.27500 99.4% 214 42s
H 2145 2058 42.6476949 0.27500 99.4% 214 42s
H 2171 2110 42.2512815 0.27500 99.3% 214 44s
H 2699 2595 41.9945108 0.27500 99.3% 216 47s
H 2720 2595 41.9723397 0.27500 99.3% 216 47s
H 2763 2658 41.9690793 0.27500 99.3% 216 53s
H 2786 2658 41.9500769 0.27500 99.3% 217 53s
2795 3215 0.28381 50 110 41.95008 0.27500 99.3% 217 56s
H 3394 3245 41.4277012 0.27500 99.3% 215 58s
4351 4543 30.54506 79 55 41.42770 0.27500 99.3% 209 60s
H 4677 4541 41.1641638 0.27500 99.3% 207 60s
H 4934 4665 41.0514940 0.27500 99.3% 205 63s
H 4978 4665 40.9976634 0.27500 99.3% 205 63s
H 5208 5451 40.9526349 0.27500 99.3% 203 64s
H 5328 5448 40.9001220 0.27500 99.3% 203 64s
6006 5449 19.02340 61 87 40.90012 0.27500 99.3% 202 67s
H 6007 5177 40.6404278 0.45140 98.9% 201 73s
6011 5179 0.45140 29 155 40.64043 0.45140 98.9% 201 75s
6014 5181 0.45140 25 129 40.64043 0.45140 98.9% 201 81s
6016 5183 12.29962 47 122 40.64043 0.45140 98.9% 201 88s
6019 5186 0.45140 97 87 40.64043 0.45140 98.9% 203 90s
H 6020 4927 40.5972533 0.45140 98.9% 203 95s
H 6024 4683 40.1457191 0.45140 98.9% 202 102s
H 6027 4450 40.0649074 0.45140 98.9% 202 104s
6028 4451 0.45140 6 102 40.06491 0.45140 98.9% 202 105s
H 6028 4228 39.8469952 0.45140 98.9% 202 109s
6030 4229 0.45140 40 84 39.84700 0.45140 98.9% 202 110s
H 6030 4018 39.8087352 0.45140 98.9% 202 112s
H 6031 3820 39.7516666 0.45140 98.9% 204 114s
6032 3822 0.45140 25 80 39.75167 0.45140 98.9% 204 115s
6034 3825 0.45140 26 77 39.75167 0.45140 98.9% 204 120s
H 6080 3674 39.6859287 0.45140 98.9% 204 121s
H 6126 3541 38.9224159 0.45140 98.8% 203 170s
H 6128 3368 38.9136240 0.45140 98.8% 203 170s
H 6136 3202 38.5450453 0.45140 98.8% 203 170s
H 6138 3045 38.3299186 0.45140 98.8% 203 170s
H 6190 2944 38.1135848 0.45140 98.8% 202 202s
H 6191 2804 37.9170134 0.45140 98.8% 202 202s
H 6200 2667 37.8559152 0.45140 98.8% 201 202s
6254 2713 0.45140 32 84 37.85592 0.45140 98.8% 201 212s
H 6256 2585 37.7984997 0.45140 98.8% 201 212s
H 6260 2464 37.7984997 0.45140 98.8% 201 212s
6286 2487 0.45140 33 89 37.79850 0.45140 98.8% 200 248s
H 6291 2370 37.7596395 0.45140 98.8% 200 248s
H 6317 2254 37.6841623 0.45140 98.8% 200 248s
6318 2441 0.45140 33 92 37.68416 0.45140 98.8% 200 250s
6506 3150 0.45140 37 98 37.68416 0.45140 98.8% 196 267s
H 6784 2954 37.5180281 0.45140 98.8% 194 267s
H 6826 2841 37.4237363 0.45140 98.8% 193 267s
7277 2842 0.45140 47 73 37.42374 0.45140 98.8% 190 297s
H 7281 2747 37.3703276 0.45140 98.8% 190 297s
H 7306 2651 37.3247279 0.45140 98.8% 190 297s
H 7362 2548 37.2360880 0.45140 98.8% 189 297s
7438 7513 0.45140 50 77 37.23609 0.45140 98.8% 188 315s
13310 7410 0.46677 88 96 37.23609 0.45140 98.8% 169 327s
H13331 7410 37.2360880 0.45140 98.8% 170 327s
H14207 7410 37.0969656 0.45140 98.8% 168 327s
14772 7436 13.97696 96 95 37.09697 0.45140 98.8% 167 351s
H14778 7436 37.0969656 0.45140 98.8% 167 351s
H14786 7436 37.0969652 0.45140 98.8% 167 351s
14807 8127 10.97333 97 84 37.09697 0.45140 98.8% 167 372s
H15331 8127 37.0969650 0.45140 98.8% 166 372s
15669 13301 28.09131 106 55 37.09696 0.45140 98.8% 166 383s
H16163 13301 37.0782067 0.45140 98.8% 166 383s
22785 13332 0.45140 80 80 37.07821 0.45140 98.8% 163 456s
H22794 13322 36.6619339 0.45140 98.8% 163 456s
22818 15653 0.45140 81 87 36.66193 0.45140 98.8% 163 465s
H23014 15652 36.4790769 0.45140 98.8% 163 465s
H23167 15652 36.4713408 0.45140 98.8% 163 465s
25672 16181 11.98933 108 85 36.47134 0.45140 98.8% 162 490s
H25725 16168 35.9274566 0.45140 98.7% 162 490s
H25761 16168 35.8933138 0.45140 98.7% 162 490s
H26250 16196 35.8008391 0.45140 98.7% 162 543s
H26253 16196 35.7069765 0.45140 98.7% 162 543s
26282 16865 11.98935 127 104 35.70698 0.45140 98.7% 162 560s
H26787 16865 35.6609803 0.45140 98.7% 162 560s
27124 16897 11.98943 133 92 35.66098 0.45140 98.7% 162 579s
H27141 16896 35.5661234 0.45140 98.7% 162 579s
27156 18432 11.98944 134 92 35.56612 0.45140 98.7% 162 593s
H28496 18432 35.5423058 0.45140 98.7% 161 593s
29059 26817 0.45140 94 83 35.54231 0.45140 98.7% 160 624s
H35125 26817 35.5311467 0.45140 98.7% 159 624s
40804 27126 25.62163 219 74 35.53115 0.45140 98.7% 157 649s
41246 27477 25.62163 220 58 35.53115 0.45140 98.7% 158 672s
H41664 27477 35.5311463 0.45140 98.7% 158 673s
41802 28586 0.45140 80 89 35.53115 0.45140 98.7% 158 695s
43162 28618 0.47609 91 94 35.53115 0.45140 98.7% 159 719s
H43182 28618 35.5311461 0.45140 98.7% 159 719s
43194 35106 1.06188 92 97 35.53115 0.45140 98.7% 159 733s
51423 35136 10.07222 116 76 35.53115 0.45140 98.7% 165 788s
H51436 35136 35.5311461 0.45140 98.7% 165 788s
51457 39073 14.41447 117 93 35.53115 0.45140 98.7% 165 798s
56920 39102 0.45140 75 85 35.53115 0.45140 98.7% 170 875s
H56922 39094 35.3893297 0.45140 98.7% 170 875s
56955 43064 0.45140 76 93 35.38933 0.45140 98.7% 170 883s
H59743 43064 35.3893254 0.45140 98.7% 170 883s
H62814 45510 35.3893254 0.45140 98.7% 171 927s
H62993 45510 35.3893237 0.45140 98.7% 171 927s
65875 62029 0.45140 118 96 35.38932 0.45140 98.7% 172 971s
86703 63370 0.45140 265 100 35.38932 0.45140 98.7% 177 997s
H88130 63370 35.3893237 0.45140 98.7% 177 997s
88488 63461 0.45140 268 98 35.38932 0.45140 98.7% 177 1020s
88631 71263 0.45140 269 99 35.38932 0.45140 98.7% 177 1039s
99013 73320 0.45140 206 94 35.38932 0.45140 98.7% 179 1077s
102084 95561 0.45140 207 92 35.38932 0.45140 98.7% 179 1137s
131452 95737 0.45140 89 87 35.38932 0.45140 98.7% 188 1186s
131683 119640 0.45140 90 86 35.38932 0.45140 98.7% 188 1259s
163715 120728 12.84465 119 89 35.38932 0.45140 98.7% 192 1289s
165360 145511 21.17940 125 72 35.38932 0.45140 98.7% 192 1355s
197392 146639 infeasible 103 35.38932 0.45140 98.7% 195 1386s
[client] error : Web license token expired
198813 171418 0.45140 127 96 35.38932 0.45140 98.7% 195 1469s
203818 171418 0.45145 238 111 35.38932 0.45140 98.7% 196 1470s
230845 171443 0.67714 505 110 35.38932 0.45140 98.7% 199 1519s
230884 195272 0.67860 506 110 35.38932 0.45140 98.7% 199 1585s
H240919 195272 35.3893231 0.45140 98.7% 200 1585s
262916 195376 23.06783 89 79 35.38932 0.45140 98.7% 200 1627s
263104 220644 cutoff 92 35.38932 0.45140 98.7% 200 1700s
H295136 221045 35.3893228 0.45140 98.7% 204 1728s
295768 244328 6.67767 136 89 35.38932 0.45140 98.7% 204 1809s
327800 244350 cutoff 88 35.38932 0.45140 98.7% 206 1877s
327842 269473 infeasible 88 35.38932 0.45140 98.7% 206 1942s
Thank you very much for your help?
0
-
-
Gurobi Staff
As you noted, the performance challenge here appears to involve progress in the dual bound (aka best bound in the node log). You have set the MIP Focus parameter to 1, which will cause Gurobi to work more on finding good feasible solution (as will your setting of Heuristics=0.5). Those all appear to be good settings to use, but you might want to add some settings that are well suited to moving the dual bound more. Specifically
- Depending on how they are formulated and the input data, VRPs can have a fair bit of symmetry, so try setting the Symmetry parameter to 2
- Aggressive cuts can sometimes move the dual bound parameter, so try setting Gurobi's Cuts parameter to 2
Beyond that, perhaps you can use your knowledge of the model to derive a better dual bound and show that the MIPgap for the solutions Gurobi finds is actually significantly better than what is reported in the node log. What exactly is the objective in the model measuring, and can you derive your own lower bound for any integer feasible solution that is larger than the dual bound that is based on LP relaxations? This subject will be discussed in our tech talk next week on strong vs weak MIP formulations; you can register here:
https://www.gurobi.com/event/tech-talk-converting-weak-to-strong-mip-formulations/0 -
-
Dear Ed,
Thank you for your reply.
I tried the symmetry and the cut parameter, but it didn't work well...
Here is the entire code. The objective is the total working hours of all drivers.
(An explanation: Even if a driver arrives at a node early he/she has to wait until the time window start time. Also, he/she has to arrive at a node within the time window end time. The total working hours is a sum of each driver's arrival time to the depot.)
import pandas as pd
import numpy as np
from matplotlib import pyplot as plt
from gurobipy import *
import sys
# prerequisit setting here
capacity = 100
num_vehicles = 13
least_vehicles = 2
df = pd.read_csv('ex.csv')
df = df[0:15]
coordinates = np.column_stack((list(df["X"]), list(df["Y"])))
start_time, end_time, service_time = list(df["start_time"]), list(df["end_time"]), list(df["service_time"])
demand = list(df["Demand"])
n = len(coordinates)
depot, customers = coordinates[0, :], coordinates[1:, :]
inf = 100
all_nodes = [i for i in range(n)]
edges_index = [(i, j) for i in all_nodes for j in all_nodes if i != j]
model = Model("MVRP")
model.Params.NoRelHeurTime=20
model.Params.Heuristics=1.0
model.Params.MIPFocus=1
model.Params.Method=0
model.Params.Symmetry=2
model.Params.Cuts=2
quantity, arrTime, depTime = {}, {}, {} #intialize the decision variables
X, Y = list(df["X"]), list(df["Y"])
dist_matrix = np.empty([n, n])
for i in range(len(X)):
for j in range(len(Y)):
dist_matrix[i, j] = np.sqrt((X[i] - X[j]) ** 2 + (Y[i] - Y[j]) ** 2)
if i == j:
dist_matrix[i, j] = inf
continue
num_drivers = model.addVar(vtype=GRB.INTEGER, ub=num_vehicles, lb=least_vehicles)
edges = model.addVars(edges_index, vtype=GRB.BINARY)
quantity = model.addVars(n, vtype=GRB.INTEGER, lb=0, ub=capacity) # cumulative demand
arrTime = model.addVars(n, vtype=GRB.CONTINUOUS, lb=0, ub=100) # arrival time
depTime = model.addVars(n, vtype=GRB.CONTINUOUS, lb=0, ub=100) # depature time
# visit node exact once == sum(x) == 1
for i in range(1, n):
model.addConstr(quicksum(edges[i, j] for j in range(n) if i != j) == 1 )
# visit node exact once == sum(x) == 1
for j in range(1, n):
model.addConstr(quicksum(edges[i, j] for i in range(n) if i != j) == 1)
# leave depo once
model.addConstr(quicksum(edges[0, j] for j in range(1, n)) == num_drivers)
# arriv depot once
model.addConstr(quicksum(edges[i, 0] for i in range(1, n)) == num_drivers)
# capacity of vehicle and eliminate sub-tours
model.addConstrs(quantity[j] <= capacity for j in range(n))
model.addConstrs(quantity[j] >= demand[j] for j in range(n))
model.addConstrs(
quantity[j] >= quantity[i] + demand[j] * (edges[i, j]) - capacity * (1 - (edges[i, j]))
for i in range(1, n)
for j in range(1, n) if i != j
)
# time window(supposed to start at 9:00 am)
for i in range(0,n):
# arrival time at depot should be 0 which means a tour starts at 0
if i == 0:
depTime[i] = 0
model.addConstr(depTime[i] >= arrTime[i])
# arrival time should be after previous node arrival time + travel time
model.addConstrs(arrTime[j] - dist_matrix[j, i] - depTime[i] >= inf * (edges[i, j] - 1) for j in range(1, n) if i != j)
# arrival time should be after start time of timewindows
model.addConstr(arrTime[i] >= start_time[i])
# arrival time should be before end time of timewindows
model.addConstr(arrTime[i] <= end_time[i])
# objective
# sum arrTime at a node right before depot and distance between the node and depot so that it indicate the arrival time of the depot.
model.setObjective(
quicksum((arrTime[i] + dist_matrix[i,0]) * edges[i, 0] for i in range(1, n)),
GRB.MINIMIZE
)
model.optimize()
# get solution
sol_quantity, sol_edges, sol_arrtime = model.getAttr('x', quantity), model.getAttr('x', edges), model.getAttr('x', arrTime)
solEdges, solQuantity, solArrTime = np.empty([n, n]), np.empty([n]), np.empty([n])
for i in range(n):
solQuantity[i] = sol_quantity[i]
solArrTime[i] = sol_arrtime[i]
for j in range(n):
if i != j:
solEdges[i, j] = int(sol_edges[i, j])
else:
solEdges[i, j] = 0
print("route: ", [[i, j] for i in range(solEdges.shape[0]) for j in range(solEdges.shape[1]) if solEdges[i, j] ==1])
print("arrival time of each nodes: ", solArrTime)The data is something like this.
>> can you derive your own lower bound for any integer feasible solution that is larger than the dual bound that is based on LP relaxations?
Does it mean if I can set a lower bound or an upper bound to integer variables in the source code so that the dual bound increases? I tried setting some bound for integer variables but it didn't work well.
Even after I fixed the num_drivers value and eliminated quantity capacity, it wasn't improved...
>>This subject will be discussed in our tech talk next week on strong vs weak MIP formulations; you can register here:
Thank you very much for the information.
0 -
Please sign in to leave a comment.
Comments
2 comments