Recently, we have run into the problem of trying to determine the optimal path to take when planning for a multiple destinations trip. It is the kind of problem that we face quite frequently in our everyday life, such as planning a holiday trip to various cities overseas; setting up business meetings with various people in different parts of the city; or delivering goods to different locations in a given area. The goal is to find the order of destinations to visit, which requires the least amount of effort (cost/distance/time) needed to spend on such trip. This is a classic example of a TSP, the Traveling Salesman Problem.

There is no “quick and easy” way to solve a TSP for large number of nodes, as it is a NP-Complete problem. Luckily for us, from a practical point of view, we are not trying to solve for large number of nodes. So here’s a few simple algorithms to get us what we need.

Brute Force

Algorithm: Calculate the distances between all nodes, then try all permutations to find the least effort path.

Pros: Accurate, it’ll give the best path possible

Cons: Slow and very taxing, almost impossible to perform on large number nodes. O(n!)

Nearest Neighbor / Greedy

Algorithm: Pick a starting node, then find the effort require to get to all other nodes, pick the least effort node and continue. Repeat until the last node is reached.

Pros: Fast. For n nodes, only need to calculate (n+1)*(n/2) distances, doesn’t require a pre-calculated matrix of distances.

Cons: Not always accurate, as near by nodes will “lure” the path away, often leaving a few nodes here and there that need to be “picked up” again at the end.

Node Adding

Algorithm: Pick a starting node and an ending node (or 3 nodes for a round trip route), pick a new node and insert it into the existing path at a position that will give the least amount of increase of effort.

Pros: Should gives better result as each new node should be in its correct position. Only need to calculate (n-1)*(n/2) distances.

Cons: Existing nodes may not be in their best position after new nodes are added.

There are more advance algorithms out there, such as Genetic, Ant Colony, etc, that would produce much better result. Also, adding backtracking or reordering existing paths could also give improvements. However, depending on the scenario/reason you want to perform this task for, as well as the available processing power and timeframe you have to do the calculations, it may or may not be practical or worthwhile to do so.

But of course, as an inquisitive programmer/problem solver, one would ignore practicality to find the optimal solution, just for kicks.