Aspects of OR - Traveling Salesperson Problem (TSP)

The Traveling Salesperson Problem (TSP) is a classic optimization problem in computer science and mathematics. Imagine a salesperson who needs to visit a set of cities exactly once and return to the starting city. The goal is to find the shortest possible route that achieves this.

The origin of the problem dates back to the 1800s, when the mathematician William Rowan Hamilton and his associates pondered with the so-called "Icosian Game", which is equivalent to finding the Hamiltonian cycle in a graph.

The TSP can be visualized on a map where cities are points and roads connecting them have distances or costs. For instance, if the salesperson has 10 cities to visit, there are over 3.6 million possible routes to consider! As the number of cities increases, the number of possible routes grows exponentially, making it challenging to solve directly.

The TSP is important because it has practical applications in logistics, planning, and routing problems. It also serves as a foundation for understanding other optimization challenges in fields like genetics, computer networks, and manufacturing.

Despite its simplicity to describe, TSP is a NP-hard problem. This means there’s no efficient algorithm that guarantees a perfect solution in every case. However, finding good solutions is possible through approximations and heuristics. Common solution techniques include brute force, dynamic programming, and algorithms like nearest neighbor, genetic algorithms, or simulated annealing. We will explore some of these techniques in this blog post.

Formal problem definition

The Traveling Salesperson Problem (TSP) can be defined mathematically as follows:

Input:

A set of $n$ cities, $C = \{c_1, c_2, \ldots, c_n\}$ .
A distance matrix $D$ $D$ , where $d_{ij}$ $d_{ij}$ represents the cost (distance, time, or another metric) of traveling from city $c_i$ $c_{i}$ to city $c_j$ $c_{j}$ . The cost satisfies:
- $d_{ij} > 0$ (positive costs).
- $d_{ii} = 0$ (no cost for staying at the same city).

Objective:

Find a permutation $\pi = (\pi_1, \pi_2, \ldots, \pi_n)$ of the cities such that the total travel cost is minimized. The total travel cost is given by:
$\text{Total cost} = d_{\pi_n \pi_1} + \sum_{i=1}^{n-1} d_{\pi_i \pi_{i+1}},$ where $\pi_n$ represents the last city in the tour, returning to the starting city $\pi_1$ .

Constraints:

Each city must be visited exactly once.
The tour must start and end at the same city.

Output:

The optimal route $\pi^*$ that minimizes the total cost.

With this formal description of the problem, one can construct a graph where each city is a node and each edge has a weight equal to the distance between the two cities. The problem then becomes finding the Hamiltonian cycle with the minimum cost in this graph. Given the description in terms of graph, we can also formulate the problem as an integer linear program.

Formulation as integer linear program

Let's consider the same input as before, a set of cities $C = \{c_1, c_2, \ldots, c_n\}$ and a distance matrix $D$ . We introduce a binary variable $x_{ij}$ for each pair of cities $(i, j)$ , i.e. for each edge in the graph. The variable $x_{ij}$ is 1 if the edge $(i, j)$ is used in the Hamiltonian cycle, and 0 otherwise. We also introduce an auxiliary variable $u_i$ which is used to enforce a connected tour. This is also known as subtour elimination.

Integer Linear Programming (ILP) Formulation for the Traveling Salesperson Problem (TSP)

The Traveling Salesperson Problem (TSP) can be formulated as an Integer Linear Program (ILP). Below is the standard ILP formulation for the symmetric TSP, where the goal is to minimize the total travel cost.

Objective Function

Minimize the total travel cost: $\min \sum_{i \in C} \sum_{j \in C, j \neq i} d_{ij} x_{ij}.$

Constraints

Visit Each City Exactly Once: Each city must have exactly one incoming and one outgoing edge. $\sum_{j \in C, j \neq i} x_{ij} = 1 \quad \forall i \in C,$ $\sum_{i \in C, i \neq j} x_{ij} = 1 \quad \forall j \in C.$
Subtour Elimination: To avoid disconnected subtours, enforce the following constraints using the auxiliary variables $u_i$ from above(only valid for $i \geq 2$ ):
$u_i - u_j + n x_{ij} \leq n - 1 \quad \forall i, j \in C, i \neq j.$
The variable $u_i$ can be interpreted as the position of city $i$ in the tour.
Binary Decision Variables: Ensure that the variables represent valid routes.
$x_{ij} \in \{0, 1\} \quad \forall i, j \in C, i \neq j.$

Explanation of Constraints

The degree constraints ensure that every city is entered and exited exactly once.
The subtour elimination constraint prevents the formation of disjoint tours by introducing auxiliary variables $u_i$ , which effectively order the cities visited.

This ILP formulation is efficient for small problem sizes but becomes computationally expensive for large $n$ due to the exponential growth of the decision space. Advanced techniques like cutting planes, branch-and-bound, and heuristic algorithms are often used to solve large instances of TSP.

Implementation in Python

An implementation of the ILP formulation in Python using Gurobi can be found here. We assume that the input is given as a networkx graph.

First, create the model:

model = gp.Model('TSP')

nodes = list(G.nodes())
n = len(nodes)

Add all needed variables:

# Create binary variables for edges
x = model.addVars([(i, j) for i in nodes for j in nodes if i != j], vtype=GRB.BINARY, name='x')

# u[i] represents the position of node i in the tour
u = model.addVars(nodes, lb=0, ub=n-1, vtype=GRB.CONTINUOUS, name='u')

Add the objective function:

# Objective: Minimize total distance
model.setObjective(gp.quicksum(G[i][j]['weight'] * x[i,j] for i, j in x.keys()), GRB.MINIMIZE)

And finally the constraints as described above.

# Constraints for entering nodes
for j in nodes: model.addConstr(gp.quicksum(x[i,j] for i in nodes if i != j) == 1, f'enter_{j}')
    
# Constraints for exiting nodes
for i in nodes: model.addConstr(gp.quicksum(x[i,j] for j in nodes if i != j) == 1, f'exit_{i}')     
    
# Fix the position of the first node
model.addConstr(u[nodes[0]] == 0, "root")
    
# Add subtour elimination constraints
for i in nodes:
  for j in nodes[1:]:  # Skip first node as destination
    if i != j:
      model.addConstr(u[i] - u[j] + n * x[i,j] <= n - 1, f'mtz_{i}_{j}')

That's it! Happy solving!