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

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=120)
Instance	Size	mtz-tw	mtz-strong	mtz-2idx
n20w120.001	20	267^*	267^*	267^*
n20w120.002	20	218^*	218^*	218^*
n20w120.003	20	303^*	303^*	303^*
n20w120.004	20	300^*	300^*	300^*
n20w120.005	20	240^*	240^*	240^*
n40w120.001	40	433^*	434^*	433^*
n40w120.002	40	445^*	445^*	445^*
n40w120.003	40	357^*	357^*	357^*
n40w120.004	40	303, 294	303, 294	303^*
n40w120.005	40	350^*	350^*	350^*
n60w120.001	60	384^*	384^*	384^*
n60w120.002	60	427^*	427^*	427, 400
n60w120.003	60	411, 392	407, 393	406, 370
n60w120.004	60	490^*	490^*	490, 454
n60w120.005	60	547^*	no sol, 527	no sol, 473
n80w120.001	80	510, 480	506, 479	no sol, 386
n80w120.002	80	no sol, 534	577, 542	613, 495
n80w120.003	80	563, 521	567, 520	538, 489
n80w120.004	80	502, 474	506, 473	500, 429
n80w120.005	80	620, 562	612, 566	no sol, 516
n100w120.001	100	756, 573	730, 572	no sol, 512
n100w120.002	100	no sol, 486	no sol, 485	no sol, 423
n100w120.003	100	645, 595	656, 591	no sol, 524
n100w120.004	100	748, 589	703, 605	no sol, 548
n100w120.005	100	587, 503	602, 508	no sol, 439