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

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=180)
Instance	Size	mtz-tw	mtz-strong	mtz-2idx
n20w180.001	20	253^*	253^*	253^*
n20w180.002	20	265^*	265^*	265^*
n20w180.003	20	271^*	271^*	271^*
n20w180.004	20	201^*	201^*	201^*
n20w180.005	20	193^*	193^*	193^*
n40w180.001	40	337, 329	337, 330	340, 307
n40w180.002	40	346^*	347^*	346^*
n40w180.003	40	277^*	279^*	277^*
n40w180.004	40	354^*	354^*	354^*
n40w180.005	40	345, 285	335, 281	345, 301
n60w180.001	60	413, 367	415, 369	420, 351
n60w180.002	60	417, 372	399, 383	399, 371
n60w180.003	60	465, 408	445, 423	no sol, 353
n60w180.004	60	no sol, 424	456, 442	456, 406
n60w180.005	60	395, 369	397, 368	no sol, 321
n80w180.001	80	no sol, 499	no sol, 501	no sol, 439
n80w180.002	80	no sol, 424	507, 436	513, 391
n80w180.003	80	no sol, 457	592, 464	no sol, 426
n80w180.004	80	478, 448	503, 447	478, 432
n80w180.005	80	no sol, 425	513, 436	no sol, 401
n100w180.001	100	no sol, 523	657, 537	no sol, 457
n100w180.002	100	no sol, 483	no sol, 489	no sol, 430
n100w180.003	100	no sol, 542	682, 547	no sol, 457
n100w180.004	100	no sol, 496	no sol, 504	648, 453
n100w180.005	100	no sol, 456	585, 464	no sol, 406