Solving Large Scale TSP using OR

The Traveling Salesman Problem (TSP) might seem tedious initially, but tackling it on a large scale is like embarking on an epic adventure! With hundreds or thousands of cities, you explore exciting challenges in optimization, discover the magic of genetic algorithms, and dive into the fun of simulated annealing and ant colony optimization. Large-scale TSP transforms a mundane task into a thrilling quest for computational brilliance.

I want to try an approximate solution but practical one in this post! The google OR-Tools has been used for this purpose.

Traditional TSP formulation:

There are two famous TSP formulations which tackles the problem using MILP

MTZ formulation

DFJ formulation

Constraint Programming using Circuit

    def AddCircuit(self, arcs):
        """Adds Circuit(arcs).

    Adds a circuit constraint from a sparse list of arcs that encode the graph.

    A circuit is a unique Hamiltonian path in a subgraph of the total
    graph. In case a node 'i' is not in the path, then there must be a
    loop arc 'i -> i' associated with a true literal. Otherwise
    this constraint will fail.        

The challenge is that these methods perform well for smaller node counts (<= 150-200). However, the problem's complexity escalates significantly, making it impractical to solve for larger numbers of nodes within a reasonable timeframe.

So what if we need to solve a problem with 1000 nodes ?

Let's discuss the approach.

The idea is creating an invisible grid like this

The number of these grid is important (if n = 1 we solve the oroginal problem) if we increase it then each subproblem becomes easier.

Subproblem:

In each cell, find a path that visits every node exactly once, ensuring the path enters and exits the cell only once. The question is what is the entering and exiting nodes of each cell ?

first we solve the TSP for the centers of these rectangles

Now we know that from cell 0, we enter cell 1 and then proceed to cell 7. To transition between cells, we should select a node from each cell that connects them together.

node_centers = [r for r in rects]
pos = {}
for r, (x1,y1,x2,y2) in rects.items():
  xm,ym = 0.5*(x1+x2), 0.5*(y1+y2)
  pos[r]=(xm,ym)

model = cp_model.CpModel()
solver = cp_model.CpSolver()

U = {(i,j):model.NewBoolVar(f"connection_{i}_{j}")  for i in node_centers for j in node_centers if i!=j}
arcs = [(i,j,v) for (i,j),v in U.items() ]
model.AddCircuit(arcs)
# Maximize x
expressions = [v*dist(pos[i],pos[j]) for (i,j),v in U.items() ]
model.Minimize(sum(expressions))
solver.Solve(model)        

the nodes are found

0: [6, 1],
 1: [0, 7],
 2: [8, 3],
 3: [2, 9],
 4: [10, 5],
 5: [4, 11],
 6: [12, 0],
 7: [1, 13],
 8: [14, 2],
 9: [3, 10],
 10: [9, 4],
 11: [5, 17],
 12: [18, 6],
 13: [7, 14],
 14: [13, 8],
 15: [16, 21],
 16: [17, 15],
 17: [11, 16],
 18: [24, 12],
 19: [20, 25],
 20: [26, 19],
 21: [15, 22],
 22: [21, 23],
 23: [22, 29],
 24: [30, 18],
 25: [19, 31],
 26: [32, 20],
 27: [28, 33],
 28: [34, 27],
 29: [23, 35],
 30: [31, 24],
 31: [25, 30],
 32: [33, 26],
 33: [27, 32],
 34: [35, 28],
 35: [29, 34]        

now for each rectangle the shortest path between the two nodes are found

for r in rects:
  (st,fn) = s_nodes[r]
  nodes_r = [n for n in data if data[n][2] == r]
  print(r, len(nodes_r))
  pos = {n:data[n][0:2] for n in nodes_r}
  model = cp_model.CpModel()
  solver = cp_model.CpSolver()
  U = {(i,j):model.NewBoolVar(f"connection_{i}_{j}")  for i in nodes_r for j in nodes_r if i!=j}
  arcs = [(i,j,v) for (i,j),v in U.items() ]
  arcs +=[(fn,st,True)]
  model.AddCircuit(arcs)
  # Maximize x
  expressions = [v*dist(pos[i],pos[j]) for (i,j),v in U.items() ]
  model.Minimize(sum(expressions))
  solver.Solve(model)        

Now plot the TSP in each cell

and final touch, connect them using the points obtained previously (red links):

Now it's time to remove all traces of the magic !

Some observations:

• The objective value and computational complexity depend on the number of considered cells
• This is an approximation and can be used as a good initial guess for the solver (if optimal solution is needed)
• Further simplification can make the problem faster (let's discuss it in comment section)
• Join the optimization newsletter

The code is available on my Git repo

#orms #ortools #python #optimization