Asymmetric Traveling Salesman Problem: Results obtained for TSPLIB instances


Results obtained using Gurobi for solving the asymmetric traveling salesman problem, using models described in Mathematical Optimization: Solving Problems using Python and Gurobi. CPU time limited to 3600 seconds. (Click on values for selecting data to display.)

Performance data
CPU time required
Number of solution failures
Solutions and bounds

CPU used

(click on values for detailed output)
Legend for columns in the next tables
LabelDescription
inst Instance name
mtz Time used by Miller-Tucker-Zemlin's potential formulation
mtz_strong Time used by a stronger version of Miller-Tucker-Zemlin's formulation
scf Time used by a single-commodity flow formulation
mcf Time used by a multi-commodity flow formulation

chart
CPU used as a function of instance size
InstanceSizemtzmtz_strongscfmcf
atex1 16 2.17 0.31 0.24 0.17
br17 17 18.01 0.60 0.32 0.27
atex3 32 2.34 0.18 0.91 16.44
ftv33 34 0.76 3.34 0.70 2.44
ftv35 36 3.60 1.20 1.28 9.16
ftv38 39 1.79 1.97 0.72 15.61
p43 43 >3600 >3600 723.42 >3600
ftv44 45 4.04 1.34 3.51 32.80
atex4 48 >3600 >3600 1002.54 >3600
ftv47 48 8.86 2.08 3.82 72.89
ry48p 48 51.82 39.15 62.56 71.62
ft53 53 52.17 32.47 183.36 66.89
ftv55 56 10.06 10.35 2.78 111.67
ftv64 65 37.05 8.30 8.28 444.62
ft70 70 >3600 8.04 11.06 269.80
ftv70 71 65.67 15.28 54.68 558.84
atex5 72 >3600 >3600 >3600 >3600
ftv90 91 42.05 4.56 11.87 995.47
kro124p 100 223.85 33.66 117.91 >3600
ftv100 101 13.16 6.30 39.40 >3600
td100.1 101 1.30 0.82 5.32 >3600
ftv110 111 88.28 25.08 43.72 >3600
dc112 112 >3600 >3600 >3600 >3600
ftv120 121 228.15 34.81 100.57 >3600
dc126 126 >3600 >3600 >3600 >3600
ftv130 131 90.75 11.82 43.33 >3600
dc134 134 >3600 >3600 588.88 >3600
ftv140 141 18.67 8.14 66.04 >3600
ftv150 151 35.81 4.90 67.49 >3600
ftv160 161 219.02 20.94 137.68 >3600
ftv170 171 697.44 46.18 395.88 >3600
dc176 176 >3600 >3600 3008.62 >3600
dc188 188 >3600 >3600 >3600 >3600
code198 198 9.78 8.79 120.12 >3600
code253 253 94.45 15.84 >3600 >3600
td316.10 317 12.33 16.85 417.06 >3600
rbg323 323 24.87 24.83 333.58 >3600
rbg358 358 42.36 36.60 1476.73 >3600
rbg403 403 43.59 59.79 820.20 >3600
rbg443 443 91.93 82.95 376.37 >3600
dc563 563 >3600 >3600 >3600 >3600
atex8 600 >3600 >3600 >3600 >3600
big702 702 >3600 639.82 >3600 >3600
dc849 849 >3600 >3600 >3600 >3600
dc895 895 >3600 >3600 >3600 >3600
dc932 932 >3600 >3600 >3600 >3600
td1000.20 1001 598.61 442.23 >3600 -