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

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=40)
Instance	Size	mtz-tw	mtz-strong	mtz-2idx
n20w40.001	20	254^*	254^*	254^*
n20w40.002	20	333^*	333^*	333^*
n20w40.003	20	317^*	317^*	317^*
n20w40.004	20	388^*	388^*	388^*
n20w40.005	20	288^*	288^*	288^*
n40w40.001	40	465^*	465^*	465^*
n40w40.002	40	461^*	461^*	461^*
n40w40.003	40	470^*	474^*	470^*
n40w40.004	40	452^*	452^*	452^*
n40w40.005	40	453^*	453^*	453^*
n60w40.001	60	591^*	591^*	591^*
n60w40.002	60	621^*	621^*	621^*
n60w40.003	60	603^*	603^*	603, 588
n60w40.004	60	597^*	597^*	597^*
n60w40.005	60	539^*	539^*	539^*
n80w40.001	80	604^*	606^*	604^*
n80w40.002	80	no sol, 588	618, 611	no sol, 521
n80w40.003	80	668^*	674^*	no sol, 637
n80w40.004	80	557^*	557^*	no sol, 503
n80w40.005	80	695^*	695^*	no sol, 633
n100w40.001	100	770^*	770^*	no sol, 716
n100w40.002	100	633, 626	656, 642	no sol, 570
n100w40.003	100	734, 724	736^*	no sol, 659
n100w40.004	100	651^*	651^*	no sol, 563
n100w40.005	100	699^*	699^*	no sol, 644
n150w40.001	150	no sol, 897	no sol, 906	no sol, 824
n150w40.002	150	942, 934	943, 930	no sol, 844
n150w40.003	150	no sol, 702	754, 710	no sol, 608
n150w40.004	150	761^*	764^*	no sol, 684
n150w40.005	150	no sol, 784	no sol, 783	no sol, 725
n200w40.001	200	no sol, 980	no sol, 984	no sol, 868
n200w40.002	200	no sol, 902	no sol, 907	no sol, 761
n200w40.003	200	954, 908	no sol, 900	no sol, 748
n200w40.004	200	no sol, 958	1008, 957	no sol, 787
n200w40.005	200	no sol, 989	no sol, 997	no sol, 824