Solving the TSP

Imagine that you manage a small fulfillment center and need to deliver packages to a list of customers using a single vehicle. What’s the best route for the vehicle to take so that you can visit all your customers and then return to the starting point? This is an example of the classic TSP.

The TSP dates back to 1930, and since then has been one of the most thoroughly studied problems in optimization. It is often used to benchmark optimization algorithms. The problem has many variants, but it was originally formulated after a traveling salesman who needs to take a trip that covers several cities:

“Given a list of cities and the distances between each pair of the cities, find the shortest possible path that goes through all the cities and then returns to the starting city.”

Using combinatorics, you could find that when given n cities, the number of possible paths that go through all cities is (n − 1) !/ 2.

The following figure...