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

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=120)
InstanceSizemtz-twmtz-strongmtz-2idx
n20w120.001 20 0.05 0.04 0.97
n20w120.002 20 7.93 8.21 38.87
n20w120.003 20 1.22 2.65 10.32
n20w120.004 20 2.08 0.49 16.10
n20w120.005 20 0.07 0.05 3.00
n40w120.001 40 784.65 738.67 238.63
n40w120.002 40 56.23 11.81 599.32
n40w120.003 40 67.86 49.13 730.72
n40w120.004 40 >3600 >3600 1997.18
n40w120.005 40 16.23 10.05 142.24
n60w120.001 60 391.63 924.74 2009.19
n60w120.002 60 414.85 485.87 >3600
n60w120.003 60 >3600 >3600 >3600
n60w120.004 60 2167.68 2767.88 >3600
n60w120.005 60 3202.55 >3600 >3600
n80w120.001 80 >3600 >3600 >3600
n80w120.002 80 >3600 >3600 >3600
n80w120.003 80 >3600 >3600 >3600
n80w120.004 80 >3600 >3600 >3600
n80w120.005 80 >3600 >3600 >3600
n100w120.001 100 >3600 >3600 >3600
n100w120.002 100 >3600 >3600 >3600
n100w120.003 100 >3600 >3600 >3600
n100w120.004 100 >3600 >3600 >3600
n100w120.005 100 >3600 >3600 >3600