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: 80

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=80)
InstanceSizemtz-twmtz-strongmtz-2idx
n20w80.001 20 0.18 0.15 6.42
n20w80.002 20 0.19 0.04 1.32
n20w80.003 20 0.12 0.17 3.16
n20w80.004 20 0.08 0.08 3.72
n20w80.005 20 8.28 2.15 70.67
n40w80.001 40 32.58 13.15 538.31
n40w80.002 40 2352.42 1033.46 >3600
n40w80.003 40 139.60 85.31 >3600
n40w80.004 40 6.28 9.28 772.37
n40w80.005 40 80.85 485.46 1419.70
n60w80.001 60 419.48 1841.16 >3600
n60w80.002 60 >3600 3445.67 >3600
n60w80.003 60 >3600 >3600 >3600
n60w80.004 60 623.10 855.30 >3600
n60w80.005 60 1633.76 >3600 >3600
n80w80.001 80 >3600 2598.46 >3600
n80w80.002 80 >3600 >3600 >3600
n80w80.003 80 >3600 >3600 >3600
n80w80.004 80 >3600 >3600 >3600
n80w80.005 80 >3600 >3600 >3600