The classic TSP is one of those things that’s incredibly easy to say, but yet somehow, quite hard (NP-Hard) to solve optimally in the general case.

Overview

Given a set of points, visit them all in the cheapest way.

There are many ways one can construct a tour (or a route through all the points), so many in fact that for even small problems with say, 59 points, there are as many unique ways of constructing a tour as there are atoms in the universe (1.3x10^80 and 10^80 respectively).

That doesn’t mean we can’t solve a TSP, it just means that at some point - solving larger problems are going to take exponentially longer. So if we’re in a hurry, we might have to take the best solution we’ve found so far instead of waiting for a marginally better solution to be found.

One can think of the solution to a classic TSP geometrically like this:

The dots represent the locations which need to be visited and the lines between the points represent the order in which we’re going to visit the locations. We often refer to a point, or location, as a node in a sequencing context. The reason for this is that the underlying graph uses this terminology. When talking about the pieces between nodes, i.e. from node A to node B, we refer to these lines as edges as they represent the connectivity between the nodes.

It’s rare in the real-world that we’re able to travel in a straight lines between nodes - even drones may have to fly around objects or perform additional maneuvers to get between two locations. For this reason, our TSP API has the ability to plug into real-world road networks to describe how we move around. Luckily, the representation of the problem doesn’t change, we’re still trying to find the least-cost path through all the nodes, but our input data has been modified to represent the real-world cost of using an edge in the network.

So the distance and time used by the TSP service between Node A and Node B is not the straight line edge distance (unless you’ve overridden the default value with the straight line distance), but rather the distance of the dotted line from Node A to Node B. This dotted line is obviously longer than the straight line distance. This is always true as it turns out - the road network distance will always be further than the straight line distance between any two nodes on the network.

So looping back to the original example here. We could display the actual routes between points being used by the solver in the background. We get something like this:

The objective in the academic version of the TSP is to find the tour which visits all nodes (exactly once) and minimises the distance travelled. In real-world applications, this cost function may be more complicated, consisting of a tradeoff between distance and time as sometimes the shortest route in distance is not the cheapest route (with respect to time). More complex models which support the tailoring of the cost function are discussed in the IVR Model classes. To see how to make a call to the API to solve a simple TSP model, see the next section on the classic TSP - a great way to get a handle on the fundamentals of making a call to the API.

Next up: Running a classic tsp