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

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=180)
InstanceSizemtz-twmtz-strongmtz-2idx
n20w180.001 20 1.36 0.50 9.60
n20w180.002 20 1.31 1.51 12.65
n20w180.003 20 6.66 3.22 30.76
n20w180.004 20 4.17 1.56 6.76
n20w180.005 20 9.95 17.09 40.10
n40w180.001 40 >3600 >3600 >3600
n40w180.002 40 558.35 398.06 2440.24
n40w180.003 40 17.41 2.51 125.79
n40w180.004 40 411.57 407.40 1589.92
n40w180.005 40 >3600 >3600 >3600
n60w180.001 60 >3600 >3600 >3600
n60w180.002 60 >3600 >3600 >3600
n60w180.003 60 >3600 >3600 >3600
n60w180.004 60 >3600 >3600 >3600
n60w180.005 60 >3600 >3600 >3600
n80w180.001 80 >3600 >3600 >3600
n80w180.002 80 >3600 >3600 >3600
n80w180.003 80 >3600 >3600 >3600
n80w180.004 80 >3600 >3600 >3600
n80w180.005 80 >3600 >3600 >3600
n100w180.001 100 >3600 >3600 >3600
n100w180.002 100 >3600 >3600 >3600
n100w180.003 100 >3600 >3600 >3600
n100w180.004 100 >3600 >3600 >3600
n100w180.005 100 >3600 >3600 >3600