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

Solutions obtained

Instance type: Dumas, time window factor: 60

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

Solutions and bounds obtained, 'Dumas' instances (w=60)
Instance	Size	mtz-tw	mtz-strong	mtz-2idx
n20w60.001	20	335^*	335^*	335^*
n20w60.002	20	244^*	244^*	244^*
n20w60.003	20	352^*	352^*	352^*
n20w60.004	20	280^*	280^*	280^*
n20w60.005	20	338^*	338^*	338^*
n40w60.001	40	494^*	494^*	494^*
n40w60.002	40	470^*	470^*	470^*
n40w60.003	40	393^*	408^*	393^*
n40w60.004	40	382^*	382^*	382^*
n40w60.005	40	328^*	328^*	328^*
n60w60.001	60	609^*	609^*	609^*
n60w60.002	60	566^*	566^*	566, 543
n60w60.003	60	485^*	485^*	485, 475
n60w60.004	60	571^*	571^*	no sol, 529
n60w60.005	60	569^*	569^*	569^*
n80w60.001	80	554^*	554^*	554, 505
n80w60.002	80	628^*	633^*	no sol, 592
n80w60.003	80	649, 642	651^*	no sol, 588
n80w60.004	80	612, 588	619, 597	no sol, 509
n80w60.005	80	no sol, 528	596, 535	no sol, 470
n100w60.001	100	658, 642	670, 646	no sol, 577
n100w60.002	100	no sol, 610	no sol, 597	no sol, 529
n100w60.003	100	no sol, 697	no sol, 698	no sol, 635
n100w60.004	100	772, 733	no sol, 739	no sol, 690
n100w60.005	100	661^*	661^*	no sol, 600
n150w60.001	150	no sol, 799	no sol, 801	no sol, 713
n150w60.002	150	no sol, 768	no sol, 771	no sol, 666
n150w60.003	150	no sol, 729	no sol, 741	no sol, 662
n150w60.004	150	no sol, 751	no sol, 753	no sol, 675
n150w60.005	150	no sol, 802	no sol, 802	no sol, 723