Heuristic Algorithms for the Traveling Salesman Problem

Source: Artificial Intelligence on Medium

Photo Credit: IMDb

Heuristic Algorithms for the Traveling Salesman Problem

The traveling salesman problem (TSP) involves finding the shortest path that visits n specified locations, starting and ending at the same place and visiting the other n-1 destinations exactly once. To the layman, this problem might seem a relatively simple matter of connecting dots, but that couldn’t be further from the truth.

The TSP is actually one of the most significant problems in the history of applied mathematics. In 1952, three operations researchers (Danzig, Fulkerson, and Johnson, the first group to really crack the problem) successfully solved a TSP instance with 49 US cities to optimality. This breakthrough paved the way for future algorithmic approaches to the TSP, as well as other important developments in the field (like branch-and-bound algorithms). Consequently, it’s fair to say that the TSP has birthed a lot of significant combinatorial optimization research, as well as help us recognize the difficulty of solving discrete problems accurately and precisely.

The TSP’s wide applicability (school bus routes, home service calls) is one contributor to its significance, but the other part is its difficulty. It’s an NP-complete combinatorial problem, and therefore there is no known polynomial-time algorithm that is able to solve all instances of the problem. Some instances of the TSP can be merely understood, as the time required to solve the model optimally might take forever.

Consequently, researchers developed heuristic algorithms to provide solutions that are strong, but not necessarily optimal. In this blog post, I’ll show you the why and the how of two main heuristics for the TSP.

Photo by Lorenzo from Pexels

Understanding the VRP

To help motivate these heuristics, I want to briefly discuss a related problem in operations research, the vehicle routing problem (VRP).

The typical usage of VRP is as follows: given a set of vehicles and a set of locations, and assuming a fixed cost of traversing any location-location pair, find the path that reaches all locations at minimum cost. Although it sounds abstract, it has many applications in the real world (see our blog post on the vehicle routing problem [VRP] for more details).

For instance, in the domain of supply chain, a VRP solution might dictate the delivery strategy for a company that needs to fulfill orders for clients at diverse locations. You could think about it like this: find the cheapest or fastest routes under certain constraints (capacity, time, etc.) for a set of trucks, with each truck starting from a depot, visiting all its clients, and returning to its depot.

This is relevant for the TSP because, in the year 1959, Dantzig and Ramser showed that the VRP is actually a generalization of the TSP — when there are no constraints and only one truck traveling around at a time, the VRP reduces to the TSP. Consequently, a last resort for solving TSPs (when usual TSP heuristic methods aren’t working effectively) is to transform the problem into a VRP.

With that out of the way, let’s proceed to the TSP itself.

Modeling TSP

Firstly, let’s introduce the TSP model: a directed graph G=(V, A), where V is the set of vertices (locations) to be visited, and cᵢⱼ, (i,j) ∈ A is the cost (usually distance, or a literal dollar cost) of each edge (the path between two locations).

The objective of the TSP is to find the lowest-cost route that satisfies the problem’s four main constraints, specified below.

Constraints (1) and (2) tell us that each vertex j/i should connect to/be connected to exactly another one vertex i/j. However, these two constraints aren’t enough to guarantee that the model’s result has only one circuit.

Thus we have constraint (3), which says that the final solution cannot be a collection of smaller routes (or subtours) — the model must output a single route that connects all the vertices. Finally, constraint (4) defines a variable xᵢⱼ, setting it equal to 1 if two vertices (i, j) in the graph are connected as part of the final tour, and 0 if not.

So that’s the TSP in a nutshell. But how do people solve it in practice?

Heuristics and Problem Types

A good first step to an efficient solution is to get more specific about exactly what kind of TSP you’re solving — different heuristics may be better suited for some problems than others. Based on whether or not cᵢⱼ=cⱼᵢ (i.e., if the cost of going from A to B is the same as going from B to A), the TSP can be divided into two general types: the symmetric TSP (STSP) and the asymmetric TSP (ATSP).

The ATSP is usually related to intra-city problems. As city roads are often diverse (one-way roads are a simple example), you can’t assume that the best route from A to B has the same properties (vehicle capacity, route mileage, traffic time, cost, etc.) as the best route from B to A.

By contrast, the STSP is mostly for inter-city problems, usually with roughly symmetrical roads. The best routes connecting two cities usually use the same road(s) with only slightly different mileage (a difference that can typically be ignored in the big picture).

Due to the different properties of the symmetric and asymmetric variants of the TSP, we will discuss them separately below.

Heuristic for ATSP

One way to create an effective heuristic is to remove one or more of the underlying problem’s constraints, and then modify the solution to make it conform to the constraint after the fact, or otherwise use it to inform your heuristic. There are two good reasons why you might do so in the case of the TSP.

First, in general, constraints make an optimization problem more difficult to solve. A problem’s final solution value can only be the same or worse compared to the result of solving the same problem with fewer constraints. Naturally, if we ignore TSP’s third constraint (the most complicated one) to get an initial result, the resultant objective value should be better than the traditional solution.

Secondly, when we ignore constraint (3) in particular, it turns out that the TSP actually becomes the mathematical model for the assignment problem (AP). The assignment problem has the property of integrality, meaning that we can substitute the following for constraint (3):

Doing so makes the problem a linear program, which means it can be solved far more quickly than its integer program counterpart. In addition, it’s a P problem (rather than an NP problem), which makes the solve process even faster. The solution output by the assignment problem heuristic can serve as the lower bound for our TSP solution. (This heuristic can be used for both STSP and ATSP, but is usually better for the ATSP given the symmetry-induced two-vertex subtours created by the STSP.)

Photo by Zan on Unsplash

So now that we’ve explained this heuristic, let’s walk through an example. Since we’ve eliminated constraint (3) (the subtour elimination constraint), the assignment problem approach can thus output multiple smaller routes instead of one big route. The assignment problem’s solution (a collection of p directed subtours C₁, C₂, …, Cₚ, covering all vertices of the directed graph G) often must be combined to create the TSP’s heuristic solution.

The algorithm for combining the AP’s initial result is as follows:

  1. Set C=C₁, C₂, …, Cₚ.
    – If p = 1, then stop — the current solution is the optimal solution.
    – Otherwise, proceed to step 2.
    (Here, p is the number of subtours. If p = 1 (which means the result has exactly one tour), that’s the optimal result for TSP.)
  2. Identify the two subtours Cₕ, Cₖ ∈ C with the most vertices.
  3. Merge Cₕ, Cₖ in a way that results in the smallest cost increase. Then C has one fewer subtour, and p becomes p-1.
    – If p=1, then stop — the current solution is the feasible solution for ATSP.
    – Otherwise, go back to step 2.

We can use a simple example here for further understanding [2]. Assume there are six locations, and that the matrix below shows the cost between each location pair.

Let’s say that the following is the optimal solution from the AP model:

There are multiple subtours, so they must be combined via our combination heuristic described above. First, we have to find the top two subtours, then merge them with the smallest cost increase (according to our above chart). The result looks like this:

After this first round, there are no more subtours — just the single tour that covers all vertices. Therefore we’re done!

(In this simple example, the initial AP result only had two subtours, so we only needed to do a single merge. If there are M subtours in the AP’s initial solution, we need to merge M-1 times.)

Photo by Jon Tyson on Unsplash

Heuristic for STSP — Nearest Neighbor

Assuming that the TSP is symmetric means that the costs of traveling from point A to point B and vice versa are the same. With this property in effect, we can use a heuristic that’s uniquely suited for symmetrical instances of the problem. It’s known as the nearest neighbor approach, as it attempts to select the next vertex on the route by finding the current position’s literal nearest neighbor.

It works as follows:

  1. Randomly select one vertex as the root.
  2. Find the vertex that is closest (more precisely, has the lowest cost) to the current position but is not yet part of the route, and add it into the route.
  3. Repeat until the route includes each vertex.

See the following graph and the description below for a detailed solution. (Ignore the coloration of the lines for now.)

In the graph above, let’s say that we choose the leftmost node as our root, and use the algorithm to guide us to a solution.

There are three nodes connected to our root node: the first node from the right, the second node from the left, and the third node from the left. They can each connect to the root with costs 1+, 1+, and 1, respectively (where is an infinitesimally small positive value). Following the nearest neighbor algorithm, we should add the vertex with minimal cost, meaning the third node from the left should be our choice.

Step by step, this algorithm leads us to the result marked by the red line in the graph, a solution with an objective value of 10. However, we can see that going straight down the line from left to right and connecting back around gives us a better route, one with an objective value of 9+5.

Generalizing this observation, as the number of nodes involved increases, the difference between the Nearest Neighbor result and the optimal one will be infinite. However, when using Nearest Neighbor for the examples in TSPLIB (a library of diverse sample problems for the TSP), the ratio between the heuristic and optimal results averages out to about 1.26, which isn’t bad at all. Given its ease of implementation and the fact that its results are solid, the Nearest Neighbor is a great heuristic for the STSP.

Photo by Roman Koval from Pexels

Summary

In this blog, we introduced heuristics for the TSP, including algorithms based on the Assignment Problem for the ATSP and the Nearest Neighbor algorithm for the STSP. Both of these algorithms are frequently used in practice for well-defined problems.

But the reality of a given problem instance doesn’t always lend itself to these heuristics. Sometimes, a problem has to be converted to a VRP to be solvable. While there’s plenty of research on the VRP, it’s complicated enough to solve on its own, and the VRP conversion approach isn’t ideal.

In addition, there are still many uncertainties involved in heuristic solutions, including how to accurately predict the time needed for a path, or how to measure the cost of operating a given route, figures that are usually assumed to be fixed and known for optimization purposes, but typically aren’t in reality. Optimization techniques really need to be combined with other approaches (like machine learning) for the best possible results [3].

If you enjoyed this post, enjoy a higher-level look at heuristics in our blog post on heuristics in optimization. And don’t forget to check back later for a blog on another heuristic algorithm for STSP (Christofides)!

Reference

[1] ] D.S. Johnson, L.A. McGeoch, F. Glover, C. Rego, 8th DIMACS Implementation Challenge: The Traveling Salesman Problem, 2000.

[2] G. Ghiani, G. Laporte, R. Musmanno, Introduction to Logistics System Management

[3] Lecture notes form Dr. Salvesbergh, Transportation, 2018

*Note: all our discussion about TSP in this post pertains to the Metric TSP, which means it satisfies the triangle inequality: