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

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=80)
InstanceSizemtz-twmtz-strongmtz-2idx
n20w80.001 20 329* 329* 329*
n20w80.002 20 338* 338* 338*
n20w80.003 20 320* 320* 320*
n20w80.004 20 304* 304* 304*
n20w80.005 20 264* 264* 264*
n40w80.001 40 395* 395* 395*
n40w80.002 40 429* 431* 429, 417
n40w80.003 40 410* 412* 410, 403
n40w80.004 40 417* 417* 417*
n40w80.005 40 344* 344* 344*
n60w80.001 60 457* 458* no sol, 386
n60w80.002 60 498, 482 498* 498, 433
n60w80.003 60 550, 534 550, 541 no sol, 478
n60w80.004 60 566* 566* 568, 530
n60w80.005 60 468* 468, 457 no sol, 399
n80w80.001 80 628, 602 624* no sol, 548
n80w80.002 80 591, 579 594, 582 no sol, 450
n80w80.003 80 no sol, 539 604, 546 no sol, 498
n80w80.004 80 604, 566 599, 570 no sol, 534
n80w80.005 80 no sol, 533 571, 552 no sol, 492