How to improve solver solution time in VRP TW Optimization
Answered
Hi guys, I've been struggling to solve this problem for my research. So my research is about VRP with Time Windows and Heterogenous Fleet consisting of 26 nodes with 4 vehicle available. I have been trying several of parameters but still can't get the solution. Can someone help me with the tuning so the solving time can be improved. Thanks here is the gurobi solver log from gurobipy.
model.Params.timeLimit = 3600
model.Params.MIPGap = 0.05
model.Params.MIPFocus=2
model.Params.Presolve=2
model.optimize()
Set parameter TimeLimit to value 3600
Set parameter MIPGap to value 0.05
Set parameter MIPFocus to value 2
Set parameter Presolve to value 2
Gurobi Optimizer version 9.5.2 build v9.5.2rc0 (win64)
Thread count: 2 physical cores, 4 logical processors, using up to 4 threads
Optimize a model with 1548 rows, 1452 columns and 10905 nonzeros
Model fingerprint: 0xaf99e83e
Variable types: 66 continuous, 1386 integer (1386 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+05]
Objective range [1e-03, 2e+05]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+05]
Presolve added 0 rows and 60 columns
Presolve removed 8 rows and 0 columns
Presolve time: 0.70s
Presolved: 1540 rows, 1512 columns, 31809 nonzeros
Variable types: 63 continuous, 1449 integer (1437 binary)
Root relaxation presolved: 1540 rows, 1512 columns, 31809 nonzeros
Root relaxation: objective 3.844821e+01, 200 iterations, 0.04 seconds (0.03 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 38.44821 0 54 - 38.44821 - - 0s
H 0 0 374778.43667 38.44821 100% - 1s
0 0 52.51442 0 111 374778.437 52.51442 100% - 1s
0 0 79.96605 0 141 374778.437 79.96605 100% - 1s
H 0 0 372494.07016 79.96605 100% - 1s
0 0 83.39883 0 108 372494.070 83.39883 100% - 1s
0 0 106.87158 0 147 372494.070 106.87158 100% - 1s
0 0 107.08841 0 148 372494.070 107.08841 100% - 1s
0 0 120.39348 0 178 372494.070 120.39348 100% - 2s
0 0 124.14781 0 148 372494.070 124.14781 100% - 2s
0 0 124.22477 0 139 372494.070 124.22477 100% - 2s
0 0 124.22875 0 141 372494.070 124.22875 100% - 2s
0 0 142.57139 0 168 372494.070 142.57139 100% - 3s
....
80193 65878 4916.94374 89 207 206943.017 4852.83975 97.7% 76.3 1338s
80309 66059 204674.137 137 114 206943.017 4852.85362 97.7% 76.3 1342s
80534 66203 infeasible 115 206943.017 4852.85741 97.7% 76.3 1346s
80704 66439 4936.81558 75 135 206943.017 4852.89106 97.7% 76.2 1351s
80984 66632 5235.32817 94 150 206943.017 4852.94463 97.7% 76.2 1355s
81555 67188 5590.06491 98 130 206943.017 4853.04542 97.7% 76.3 1362s
81899 67350 6854.89430 79 78 206943.017 4853.06672 97.7% 76.2 1366s
82516 67912 206638.868 117 64 206943.017 4853.15187 97.7% 76.0 1373s
82749 68111 5232.82553 68 171 206943.017 4853.21617 97.7% 76.0 1377s
83001 68366 5248.13724 92 93 206943.017 4853.25026 97.7% 76.0 1380s
83528 68678 4861.10447 72 226 206943.017 4853.26741 97.7% 75.9 1385s
-
Hi,
Modeling and solving VRPs (with TW) is far from being trivial. State-of-the-art models require to implement a branch-and-price or a branch-and-cut algorithm. Compact models (with a polynomial number of variables and constraints) as you are using here can solve small to medium-sized instances but usually not much more than 50-100 customers.
Your solver log tells me that the model you are using provides a very weak linear programming relaxation, I guess it is based on Big-M constraints for modeling the capacity and time constraints. Solver parameters can hardly compensate for these weak bounds.
I would strongly recommend to improve your formulation instead of tuning parameters. One promising concept in compact VRP models is to use single-commodity flows for modeling capacity and time windows. The main idea is to use variables \(f_{ij}\) that denote the vehicle load at node \(i\) (including the demand at \(i\)) when immediately going to node \(j\) afterwards. With flow conservation constraints and linking constraints to your binary arc variables, this should provide a better dual bound than your current model. Similarly, time windows can be modeled with another set of flow variables \(g_{ij}\) that denote the starting time of service at node \(i\) when immediately going to node \(j\) afterwards.
Best regards,
Mario1 -
my model was this, how can i accomodate to change the time windows constraint? Because they do have large number constraint
1 -
First of all, you can safely remove the k index, since you visit each customer exactly once. You just limit the number of arcs going out of the depot by m.
The capacity constraints 5.72 can be replaced by a single-commodity flows, as it is described in this paper by Letchford and Salazar in Section 3.1. Exactly the same modeling approach can be used for the time window constraints.
This paper by the way gives a nice overview of VRP models.
0 -
Thanks, and i'm sorry to keep bothering you. I did change to single flow commodity flow but not sure if it is the correct one. The model became like this:
0 -
Please take a closer look at the paper I mentioned before. The flow conservation constraints (6) are defined per customer and sum up all incoming flow minus all outgoing flow.
The same thing applies to the flow conservation constraints (8) for handling the time windows. Additionally, they have to be transformed to inequalities since you might have some waiting time if you arrive earlier, before the start of the time window.
0 -
Thanks for your insight sir. Gurobi support was top notch
0
Please sign in to leave a comment.
Comments
6 comments