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

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=200)
Instance	Size	mtz-tw	mtz-strong	mtz-2idx
n20w200.001	20	233^*	233^*	233^*
n20w200.002	20	203^*	203^*	203^*
n20w200.003	20	249^*	249^*	249^*
n20w200.004	20	293^*	293^*	293^*
n20w200.005	20	227^*	227^*	227^*
n40w200.001	40	330, 311	330^*	330, 322
n40w200.002	40	303^*	303^*	303^*
n40w200.003	40	347, 274	350, 292	341, 266
n40w200.004	40	301, 286	301, 285	301, 271
n40w200.005	40	296^*	296^*	296^*
n60w200.001	60	410, 373	431, 384	431, 334
n60w200.002	60	414, 389	414, 389	no sol, 329
n60w200.003	60	no sol, 375	460, 416	no sol, 340
n60w200.004	60	432, 411	432, 410	433, 414
n60w200.005	60	441, 409	452, 405	431, 360
n80w200.001	80	no sol, 426	546, 429	no sol, 390
n80w200.002	80	524, 440	499, 459	no sol, 393
n80w200.003	80	no sol, 387	no sol, 401	no sol, 355
n80w200.004	80	no sol, 476	654, 481	no sol, 410
n80w200.005	80	470, 393	459, 395	no sol, 356
n100w200.001	100	no sol, 495	593, 505	no sol, 446
n100w200.002	100	no sol, 457	no sol, 465	no sol, 415
n100w200.003	100	638, 538	no sol, 537	no sol, 445
n100w200.004	100	no sol, 485	611, 491	no sol, 430
n100w200.005	100	no sol, 451	no sol, 460	no sol, 393