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

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=140)
InstanceSizemtz-twmtz-strongmtz-2idx
n20w140.001 20 1.84 0.83 16.84
n20w140.002 20 2.68 2.59 11.80
n20w140.003 20 2.50 5.27 46.09
n20w140.004 20 18.90 12.74 14.59
n20w140.005 20 1.14 0.39 23.11
n40w140.001 40 47.10 25.90 701.12
n40w140.002 40 >3600 2085.23 2325.14
n40w140.003 40 >3600 >3600 2863.72
n40w140.004 40 40.93 70.07 2450.20
n40w140.005 40 652.57 173.56 1284.56
n60w140.001 60 1228.06 1652.90 >3600
n60w140.002 60 1493.34 444.52 >3600
n60w140.003 60 >3600 >3600 >3600
n60w140.004 60 >3600 >3600 >3600
n60w140.005 60 >3600 >3600 >3600
n80w140.001 80 1876.91 458.01 >3600
n80w140.002 80 >3600 >3600 >3600
n80w140.003 80 >3600 >3600 >3600
n80w140.004 80 >3600 >3600 >3600
n80w140.005 80 >3600 >3600 >3600
n100w140.001 100 >3600 >3600 >3600
n100w140.002 100 >3600 >3600 >3600
n100w140.003 100 >3600 >3600 >3600
n100w140.004 100 >3600 >3600 >3600
n100w140.005 100 >3600 >3600 >3600