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 data | Dumas | Dumas | Dumas | Dumas | Gendreau | Gendreau | Gendreau | Gendreau | Gendreau | Gendreau | Gendreau |

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] |

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

Label | Description |

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 |

Instance | Size | mtz-tw | mtz-strong | mtz-2idx |

n20w40.001, n20w40.002, n20w40.003, n20w40.004, n20w40.005 | 20 | 0 | 0 | 0 |

n40w40.001, n40w40.002, n40w40.003, n40w40.004, n40w40.005 | 40 | 0 | 0 | 0 |

n60w40.001, n60w40.002, n60w40.003, n60w40.004, n60w40.005 | 60 | 0 | 0 | 1 |

n80w40.001, n80w40.002, n80w40.003, n80w40.004, n80w40.005 | 80 | 1 | 1 | 5 |

n100w40.001, n100w40.002, n100w40.003, n100w40.004, n100w40.005 | 100 | 3 | 2 | 10 |

n150w40.001, n150w40.002, n150w40.003, n150w40.004, n150w40.005 | 150 | 7 | 6 | 15 |

n200w40.001, n200w40.002, n200w40.003, n200w40.004, n200w40.005 | 200 | 12 | 11 | 20 |