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

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=160)
Instance	Size	mtz-tw	mtz-strong	mtz-2idx
n20w160.001	20	241^*	241^*	241^*
n20w160.002	20	201^*	201^*	201^*
n20w160.003	20	201^*	201^*	201^*
n20w160.004	20	203^*	203^*	203^*
n20w160.005	20	245^*	245^*	245^*
n40w160.001	40	348^*	348^*	348^*
n40w160.002	40	337^*	337^*	337^*
n40w160.003	40	344, 326	346^*	344^*
n40w160.004	40	288^*	288^*	288^*
n40w160.005	40	315^*	315^*	315^*
n60w160.001	60	no sol, 504	560, 548	563, 493
n60w160.002	60	423^*	423^*	423^*
n60w160.003	60	438, 421	434, 422	435, 410
n60w160.004	60	401^*	401^*	415, 364
n60w160.005	60	502^*	502^*	502, 442
n80w160.001	80	551, 454	no sol, 458	no sol, 383
n80w160.002	80	no sol, 505	no sol, 510	no sol, 455
n80w160.003	80	552, 476	540, 478	525, 438
n80w160.004	80	no sol, 428	no sol, 442	no sol, 385
n80w160.005	80	no sol, 395	482, 397	no sol, 364
n100w160.001	100	no sol, 516	656, 524	no sol, 431
n100w160.002	100	585, 485	584, 485	no sol, 422
n100w160.003	100	541, 434	529, 465	no sol, 373
n100w160.004	100	no sol, 477	no sol, 486	no sol, 435
n100w160.005	100	709, 521	no sol, 529	no sol, 428