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]

Solutions obtained

Instance type: Dumas, time window factor: 20

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."

Solutions obtained
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

Solutions and bounds obtained, 'Dumas' instances (w=20)
InstanceSizemtz-twmtz-strongmtz-2idx
n20w20.001 20 378* 378* 378*
n20w20.002 20 286* 286* 286*
n20w20.003 20 394* 394* 394*
n20w20.004 20 396* 396* 396*
n20w20.005 20 352* 352* 352*
n40w20.001 40 497* 500* 497*
n40w20.002 40 552* 552* 552*
n40w20.003 40 478* 478* 478*
n40w20.004 40 404* 404* 404*
n40w20.005 40 499* 499* 499*
n60w20.001 60 551* 551* 551*
n60w20.002 60 605* 605* 605*
n60w20.003 60 532* 533* 532*
n60w20.004 60 616* 616* 616*
n60w20.005 60 603* 603* 603*
n80w20.001 80 616* 616* 616*
n80w20.002 80 736* 737* 736*
n80w20.003 80 667* 667* 667*
n80w20.004 80 615* 615* 615*
n80w20.005 80 748* 748* 748*
n100w20.001 100 378* 378* 378*
n100w20.002 100 714* 715* no sol, 671
n100w20.003 100 762* 762* 763, 741
n100w20.004 100 799* 799* no sol, 772
n100w20.005 100 768* 774* no sol, 747
n150w20.001 150 925* 925* no sol, 856
n150w20.002 150 864* 864* no sol, 805
n150w20.003 150 832* 834* no sol, 756
n150w20.004 150 873* 873* no sol, 826
n150w20.005 150 836* 846, 844 no sol, 770
n200w20.001 200 1020, 1012 1019, 1013 no sol, 901
n200w20.002 200 972, 959 975, 958 no sol, 841
n200w20.003 200 1042* 1050* no sol, 839
n200w20.004 200 984, 977 992, 968 no sol, 889
n200w20.005 200 1020* 1020* no sol, 898