Traveling Salesman Problem with Time Windows


Results obtained using Gurobi for solving the Traveling Salesman Problem with Time Windows, using the models described in Mathematical Optimization: Solving Problems using Python and Gurobi. Benchmark instances are available in this site. CPU time limited to 3600 seconds. (Click on values for selecting instance type and time window factor.)

Performance dataDumasDumasDumasDumasGendreauGendreauGendreauGendreauGendreauGendreauGendreau
CPU time required [20] [40] [60] [80] [80] [100] [120] [140] [160] [180] [200]
Number of solution failures [20] [40] [60] [80] [80] [100] [120] [140] [160] [180] [200]
Solutions [20] [40] [60] [80] [80] [100] [120] [140] [160] [180] [200]

CPU used

Instance type: Gendreau, time window factor: 200

Results obtained using Gurobi for solving the Traveling Salesman Problem with Time Windows, using the models described in Mathematical Optimization: Solving Problems using Python and Gurobi. Benchmark instances are available in this site. CPU time limited to 3600 seconds. (Click on values for selecting instance type and time window factor.)

Benchmark instances used are described in "Gendreau et al. 1998. A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows. Operations Research, 43, 330 - 335."

CPU used
LabelDescription
mtz-tw model based on Miller-Tucker-Zemlin's one-index potential formulation
mtz-strong based on Miller-Tucker-Zemlin's one-index potential formulation, with stronger constraints
mtz-2idx based on Miller-Tucker-Zemlin's formulation, two-index potential formulation

chart
CPU used as a function of instance size, 'Gendreau' instances (w=200)
InstanceSizemtz-twmtz-strongmtz-2idx
n20w200.001 20 6.75 6.11 33.81
n20w200.002 20 2.44 2.40 7.50
n20w200.003 20 3.23 5.24 38.27
n20w200.004 20 10.29 7.09 96.17
n20w200.005 20 5.48 2.01 7.62
n40w200.001 40 >3600 1490.10 >3600
n40w200.002 40 669.63 307.26 2644.73
n40w200.003 40 >3600 >3600 >3600
n40w200.004 40 >3600 >3600 >3600
n40w200.005 40 822.18 725.31 1447.19
n60w200.001 60 >3600 >3600 >3600
n60w200.002 60 >3600 >3600 >3600
n60w200.003 60 >3600 >3600 >3600
n60w200.004 60 >3600 >3600 >3600
n60w200.005 60 >3600 >3600 >3600
n80w200.001 80 >3600 >3600 >3600
n80w200.002 80 >3600 >3600 >3600
n80w200.003 80 >3600 >3600 >3600
n80w200.004 80 >3600 >3600 >3600
n80w200.005 80 >3600 >3600 >3600
n100w200.001 100 >3600 >3600 >3600
n100w200.002 100 >3600 >3600 >3600
n100w200.003 100 >3600 >3600 >3600
n100w200.004 100 >3600 >3600 >3600
n100w200.005 100 >3600 >3600 >3600