\[ \begin{split} \begin{align} &d_{ij}: \text{distance between points i and j} \\ &x_{ij}: \text{equal to 1, if a link (i,j) is on the path; 0, o.w. } \\ &u_{i}\ : \text{the order node i is visted}\\ \end{align} \end{split} \]
\[ \begin{split} \begin{align} &\text{minimize} \sum_{i = 1}^{N} \sum_{j = 1, \\ j \neq i}^{N} x_{ij}d_{ij} \\ &\text{st} \\ \\ &\bullet \quad \sum_{j = 1}^{N} x_{ij} = 1 \qquad \qquad \forall i = 1...N \\ &\bullet \quad \sum_{i = 1}^{N} x_{ji} = 1 \qquad \qquad \forall j = 1...N \\ &\bullet \quad u_{i} - u_{j} + (N-1)x_{ij} + (N-3)x_{ji} \ \le \ N-2 \qquad {\forall i,j = 1...N,\ j \neq 0,\ i \neq j} \end{align} \end{split} \]
import pandas as pd
import matplotlib.pyplot as plt
import math
import numpy as np
import gurobipy as grb
nodes = pd.read_excel('NodeLocations.xlsx',sheet_name='u159')
N=len(nodes)
nLocs = nodes.to_numpy()
for i in range(N):
plt.scatter(nLocs[i,0], nLocs[i,1], color = 'black')
d = np.zeros((N,N))
for i in range(N):
for j in range(i+1,N):
d[i][j]=math.sqrt((nLocs[i][0]-nLocs[j][0])**2+(nLocs[i][1]-nLocs[j][1])**2)
d[j][i] = d[i][j]
#model
model = grb.Model('TSP')
#dvar
x = model.addVars(N,N,vtype=grb.GRB.BINARY, name ='x')
u = model.addVars(N, vtype=grb.GRB.INTEGER, lb=1, ub=N-1,name='u')
#obj
objective = grb.quicksum(x[i,j]*d[i,j] for i in range(N) for j in range(N))
model.setObjective(objective,grb.GRB.MINIMIZE)
#constr
for i in range(N): #out
model.addConstr(grb.quicksum(x[i,j] for j in range(N) if j!=i)==1)
for j in range(N): #in
model.addConstr(grb.quicksum(x[i,j] for i in range(N) if j!=i)==1)
for i in range(1,N): #0 starting node
for j in range(1,N):
if i!=j:
model.addConstr(u[i]-u[j]+(N-1)*x[i,j] + (N-3)*x[j,i] <= N-2) #subtour
model.setParam('TimeLimit',240)
#model.write('TSP.lp')
model.optimize()Set parameter Username
Academic license - for non-commercial use only - expires 2024-11-09
Set parameter TimeLimit to value 240
Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (win64)
CPU model: 11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 25124 rows, 25440 columns and 149468 nonzeros
Model fingerprint: 0x7ab5979f
Variable types: 0 continuous, 25440 integer (25281 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+02]
Objective range [1e+02, 7e+03]
Bounds range [1e+00, 2e+02]
RHS range [1e+00, 2e+02]
Presolve removed 0 rows and 160 columns
Presolve time: 0.36s
Presolved: 25124 rows, 25280 columns, 149468 nonzeros
Variable types: 0 continuous, 25280 integer (25122 binary)
Deterministic concurrent LP optimizer: primal and dual simplex
Showing first log only...
Concurrent spin time: 0.00s
Solved with dual simplex
Use crossover to convert LP symmetric solution to basic solution...
Root relaxation: objective 4.008077e+04, 682 iterations, 0.23 seconds (0.12 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 40080.7695 0 276 - 40080.7695 - - 1s
0 0 40278.5766 0 306 - 40278.5766 - - 3s
0 0 40279.2513 0 379 - 40279.2513 - - 3s
0 0 40524.5625 0 483 - 40524.5625 - - 4s
0 0 40524.5625 0 481 - 40524.5625 - - 4s
0 0 40772.4308 0 462 - 40772.4308 - - 5s
0 0 40772.7649 0 467 - 40772.7649 - - 5s
0 0 40784.1427 0 453 - 40784.1427 - - 5s
0 0 40784.1427 0 454 - 40784.1427 - - 6s
H 0 0 54353.663135 40784.1427 25.0% - 6s
0 0 40804.0563 0 391 54353.6631 40804.0563 24.9% - 6s
0 0 40804.0563 0 391 54353.6631 40804.0563 24.9% - 7s
0 0 40804.3498 0 475 54353.6631 40804.3498 24.9% - 7s
H 0 0 52083.825715 40804.3498 21.7% - 9s
0 0 40804.3498 0 476 52083.8257 40804.3498 21.7% - 9s
0 0 40804.8331 0 480 52083.8257 40804.8331 21.7% - 10s
0 0 40804.8331 0 479 52083.8257 40804.8331 21.7% - 10s
0 0 40806.7031 0 478 52083.8257 40806.7031 21.7% - 11s
0 0 40806.8385 0 483 52083.8257 40806.8385 21.7% - 11s
0 0 40806.9901 0 483 52083.8257 40806.9901 21.7% - 12s
0 0 40806.9901 0 483 52083.8257 40806.9901 21.7% - 12s
0 0 40806.9903 0 493 52083.8257 40806.9903 21.7% - 13s
0 0 40806.9903 0 473 52083.8257 40806.9903 21.7% - 13s
0 2 40806.9903 0 457 52083.8257 40806.9903 21.7% - 15s
H 27 32 47513.231598 40824.0168 14.1% 33.9 18s
H 61 63 47499.641128 40824.0168 14.1% 25.4 19s
88 97 40873.0302 18 396 47499.6411 40824.0168 14.1% 23.1 20s
288 310 40911.7997 63 288 47499.6411 40824.0168 14.1% 17.2 25s
H 440 440 47413.892410 40824.0168 13.9% 15.5 28s
H 441 440 47086.142385 40824.0168 13.3% 15.5 28s
542 575 40938.7074 119 250 47086.1424 40824.0168 13.3% 14.4 30s
699 699 41092.5817 152 286 47086.1424 40824.0168 13.3% 14.1 35s
H 700 699 47058.719832 40824.0168 13.2% 14.1 35s
H 702 699 46960.012587 40824.0168 13.1% 14.1 35s
1114 1162 41132.3808 245 266 46960.0126 40824.0168 13.1% 13.2 40s
H 1123 1162 46877.169874 40824.0168 12.9% 13.1 40s
H 1338 1338 46599.820771 40824.0168 12.4% 13.2 45s
H 1339 1338 46206.630253 40824.0168 11.6% 13.2 45s
H 1341 1338 46201.940801 40824.0168 11.6% 13.2 45s
H 1355 1353 45992.415022 40824.0168 11.2% 13.3 46s
1548 1609 43092.7543 342 242 45992.4150 40824.0168 11.2% 13.2 51s
1766 1842 43114.8380 405 216 45992.4150 40824.0168 11.2% 13.1 56s
1926 1959 43125.4452 444 204 45992.4150 40824.0168 11.2% 13.2 65s
H 1937 1955 45931.182755 40824.0168 11.1% 13.2 65s
1969 1983 43132.6492 455 199 45931.1828 40824.0168 11.1% 13.2 79s
H 1975 1831 43500.061113 40824.0168 6.15% 13.2 79s
H 1997 1648 43055.399419 40824.0168 5.18% 13.3 84s
2003 1757 cutoff 463 43055.3994 40829.2047 5.17% 13.3 87s
2276 2081 41173.6304 35 242 43055.3994 40829.9735 5.17% 13.9 92s
2459 2270 41210.5162 95 279 43055.3994 40829.9735 5.17% 13.7 96s
2845 2617 41249.4864 244 218 43055.3994 40829.9735 5.17% 13.1 103s
3017 2805 41312.7356 296 167 43055.3994 40831.3778 5.17% 13.1 106s
3250 2806 41621.3605 155 473 43055.3994 40836.3627 5.15% 13.5 114s
3252 2807 42422.8352 255 276 43055.3994 40836.3627 5.15% 13.5 115s
3253 2808 41464.9418 167 458 43055.3994 40836.3627 5.15% 13.5 124s
3257 2811 41534.8822 377 481 43055.3994 40836.3627 5.15% 13.5 126s
H 3257 2670 42887.854951 40965.3044 4.48% 13.5 131s
3260 2672 41816.2280 383 420 42887.8550 41067.0213 4.25% 13.5 137s
3263 2674 42796.3788 164 372 42887.8550 41097.4750 4.17% 13.5 141s
3267 2676 42024.0277 573 245 42887.8550 41143.7120 4.07% 13.5 145s
3271 2679 41784.1361 583 358 42887.8550 41182.4480 3.98% 13.5 150s
3277 2684 41445.7534 106 338 42887.8550 41188.0548 3.96% 14.7 161s
3282 2687 41599.1607 82 172 42887.8550 41188.1402 3.96% 14.7 167s
3284 2689 41856.7953 437 361 42887.8550 41188.1956 3.96% 14.7 170s
H 3287 2556 42804.281483 41189.0691 3.77% 14.7 175s
3293 2560 41464.2437 63 281 42804.2815 41209.8673 3.72% 14.6 180s
3297 2562 41381.7167 187 298 42804.2815 41233.3531 3.67% 14.6 185s
3301 2565 41841.1664 700 304 42804.2815 41236.4169 3.66% 14.6 190s
3305 2568 42647.4865 162 308 42804.2815 41236.4169 3.66% 14.6 195s
3308 2570 41739.5129 123 259 42804.2815 41267.9117 3.59% 14.6 205s
3377 2621 41283.0104 35 184 42804.2815 41267.9117 3.59% 16.6 212s
3452 2674 41293.7651 45 181 42804.2815 41267.9117 3.59% 17.0 215s
3640 2755 41302.0448 51 315 42804.2815 41267.9117 3.59% 18.2 220s
3947 2864 42016.0562 104 88 42804.2815 41267.9117 3.59% 19.2 225s
4148 2979 41718.6368 68 187 42804.2815 41267.9117 3.59% 20.2 230s
4524 3172 41294.9894 48 426 42804.2815 41267.9117 3.59% 20.6 235s
5000 3338 41441.2071 43 122 42804.2815 41267.9117 3.59% 21.5 240s
Cutting planes:
Gomory: 99
Cover: 1
Implied bound: 5
Projected implied bound: 6
MIR: 12
Flow cover: 54
Zero half: 7
RLT: 1
Relax-and-lift: 3
Explored 5044 nodes (110759 simplex iterations) in 240.08 seconds (122.80 work units)
Thread count was 8 (of 8 available processors)
Solution count 10: 42804.3 42887.9 43055.4 ... 46877.2
Time limit reached
Best objective 4.280428148328e+04, best bound 4.126791173090e+04, gap 3.5893%for i in range(N):
plt.scatter(nLocs[i,0], nLocs[i,1], color = 'black')
for i in range(N):
for j in range(N):
if i!=j:
if x[i,j].x > 0.9:
plt.plot([nLocs[i,0],nLocs[j,0]], [nLocs[i,1],nLocs[j,1]], color='red')