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

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=160)
InstanceSizemtz-twmtz-strongmtz-2idx
n20w160.001 20 2.80 5.93 10.58
n20w160.002 20 0.38 0.45 3.97
n20w160.003 20 0.24 0.24 1.01
n20w160.004 20 1.83 0.40 21.54
n20w160.005 20 4.13 3.74 66.78
n40w160.001 40 173.19 112.99 472.01
n40w160.002 40 31.07 42.27 98.10
n40w160.003 40 >3600 477.01 2812.74
n40w160.004 40 6.74 13.39 428.98
n40w160.005 40 2881.99 3082.20 3251.09
n60w160.001 60 >3600 >3600 >3600
n60w160.002 60 65.28 74.87 1856.59
n60w160.003 60 >3600 >3600 >3600
n60w160.004 60 1709.49 2306.80 >3600
n60w160.005 60 1085.94 1359.37 >3600
n80w160.001 80 >3600 >3600 >3600
n80w160.002 80 >3600 >3600 >3600
n80w160.003 80 >3600 >3600 >3600
n80w160.004 80 >3600 >3600 >3600
n80w160.005 80 >3600 >3600 >3600
n100w160.001 100 >3600 >3600 >3600
n100w160.002 100 >3600 >3600 >3600
n100w160.003 100 >3600 >3600 >3600
n100w160.004 100 >3600 >3600 >3600
n100w160.005 100 >3600 >3600 >3600