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: Gendreau, time window factor: 140

Benchmark instances used are described in "Gendreau et al. 1998. A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows. Operations Research, 43, 330 - 335."

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, 'Gendreau' instances (w=140)
Instance	Size	mtz-tw	mtz-strong	mtz-2idx
n20w140.001	20	176^*	176^*	176^*
n20w140.002	20	272^*	272^*	272^*
n20w140.003	20	236^*	236^*	236^*
n20w140.004	20	255^*	255^*	255^*
n20w140.005	20	225^*	225^*	225^*
n40w140.001	40	328^*	328^*	328^*
n40w140.002	40	383, 378	383^*	383^*
n40w140.003	40	397, 390	398, 393	397^*
n40w140.004	40	342^*	342^*	342^*
n40w140.005	40	371^*	371^*	371^*
n60w140.001	60	423^*	423^*	423, 373
n60w140.002	60	462^*	462^*	462, 455
n60w140.003	60	432, 398	427, 398	430, 389
n60w140.004	60	no sol, 428	no sol, 431	no sol, 416
n60w140.005	60	no sol, 387	no sol, 394	no sol, 368
n80w140.001	80	510^*	512^*	510, 473
n80w140.002	80	no sol, 401	no sol, 425	no sol, 350
n80w140.003	80	592, 552	582, 558	no sol, 487
n80w140.004	80	no sol, 390	447, 404	no sol, 335
n80w140.005	80	546, 541	549, 535	546, 463
n100w140.001	100	674, 561	607, 582	no sol, 507
n100w140.002	100	631, 589	649, 592	no sol, 510
n100w140.003	100	no sol, 449	527, 458	no sol, 388
n100w140.004	100	no sol, 471	701, 493	no sol, 402
n100w140.005	100	512, 470	518, 470	no sol, 416