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: Dumas, time window factor: 40

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 "Dumas et al. 1995. An Optimal Algorithm for the Traveling Salesman Problem with Time Windows. Operations Research, 43, 367 - 371."

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, 'Dumas' instances (w=40)
InstanceSizemtz-twmtz-strongmtz-2idx
n20w40.001 20 0.11 0.24 0.81
n20w40.002 20 0.00 0.00 0.12
n20w40.003 20 0.02 0.03 0.58
n20w40.004 20 0.06 0.07 0.46
n20w40.005 20 0.03 0.06 1.82
n40w40.001 40 0.14 0.32 8.67
n40w40.002 40 0.26 0.65 31.09
n40w40.003 40 0.30 0.75 18.33
n40w40.004 40 3.39 1.23 467.75
n40w40.005 40 4.79 7.93 254.85
n60w40.001 60 4.73 8.37 1266.09
n60w40.002 60 13.18 10.76 707.81
n60w40.003 60 66.10 100.61 >3600
n60w40.004 60 8.15 18.67 352.34
n60w40.005 60 6.68 7.42 1077.44
n80w40.001 80 8.14 2.46 1427.77
n80w40.002 80 >3600 >3600 >3600
n80w40.003 80 32.70 83.82 >3600
n80w40.004 80 427.73 428.42 >3600
n80w40.005 80 66.06 134.23 >3600
n100w40.001 100 1583.73 694.96 >3600
n100w40.002 100 >3600 >3600 >3600
n100w40.003 100 >3600 346.76 >3600
n100w40.004 100 955.93 1142.49 >3600
n100w40.005 100 76.36 101.40 >3600
n150w40.001 150 >3600 >3600 >3600
n150w40.002 150 >3600 >3600 >3600
n150w40.003 150 >3600 >3600 >3600
n150w40.004 150 215.46 571.71 >3600
n150w40.005 150 >3600 >3600 >3600
n200w40.001 200 >3600 >3600 >3600
n200w40.002 200 >3600 >3600 >3600
n200w40.003 200 >3600 >3600 >3600
n200w40.004 200 >3600 >3600 >3600
n200w40.005 200 >3600 >3600 >3600