Travel Time Minimization Algorithm

Question

I am looking for guidance in creating an algorithm to minimize the total travel time for a group of travelers to get to a group of fixed destinations. The travelers do not all start in the same place, but each destination must be visited by a traveler before the scenario can be considered complete (similar to TSP).

I was thinking of something along the lines of generating a matrix in which the value located at (x, y) would be the travel distance from starting location x to destination y, and then performing some kind of matrix operation/algorithm to select values such that each row/column only had one value selected from it, and that the sum of these values was minimized. Does anyone have any background with algorithms for this sort of thing?

Clarification based on comments:

• Each destination must be visited by one traveler. All the travelers do not have to visit all the destinations.
• If there are more destinations than travelers, the travelers should just aim to hit one arbitrary destination each (still minimizing travel time), and then repeat the problem, but with two fewer destinations.
• The maximum number of destinations and travelers should be around 30 destinations and 10 travelers, so not a huge number. I would like to avoid pure brute force if possible nonetheless.

Answer 1

Take a look at the Floyd-Warshall algorithm and the Merge Sort algorithm.

Given that the number of locations to visit (vertices) is V and the number of travellers is T, if you apply the Floyd-Warshall algorithm, it should give you shortest paths between pairs of vertices in your graph, with O(V^3) complexity.

You can then sort the lengths of the shortest paths in ascending order, which is going to be an operation with O(V lg V) complexity.

Since you are applying these algorithms in sequence, you're still at an overall complexity of O(V^3).

You will have to perform this second stage K times where K is ceiling(V / T), because in the first iteration, you would have visited T vertices, but V is greater than T so you have some more vertices to visit. In your next iteration, you will remove the visited vertices from the calculation and sort the remaining distances (which you have already found in the previous step) and then proceed to visit them from the new locations of the T travellers.

You could probably achieve a better result by picking the smallest distance for each vertex, so the next vertex you select is the closest one on offer.

Therefore your overall complexity will start to look like O(V^3) + K x O(V lg V), which I think tends to approach O(V^3).

These are just some ideas to get you started.

Answer 2

If I understand your problem, I doubt that the number of travelers is relevant to finding a solution quickly. So we're solving the basic Traveling Salesman problem by some heuristic and then moving the travelers around that cycle.

There are various constructive methods and various iterative improvement methods documented. A few examples are below (ranging from the academic to nifty animated examples):

• http://en.wikipedia.org/wiki/Christofides_algorithm
• http://bjornson.inhb.de/?p=26
• http://www.cs.ubc.ca/labs/beta/Courses/CPSC532D-05/Slides/tsp-camilo.pdf

Answer 3

As the Travelling Salesman problem runs in factorial complexity, it can rapidly grow beyond what is sensible to run on the CPY. Fortunately, newer computers all come with a perfectly capable graphics card that can run problems such as this hundreds or thousand of times faster than a CPU.

I have posted an analysis and comparison of a fairly simplistic solution to the TSP here which includes C# code that runs on an NVIDIA graphics card. It will be necessary to also download the CUDAfy CUDAfy library to run the code directly.

With my Quad i7, 16GB laptop and an NVIDIA GEFORCE GT graphics card, I report a performance improvement for 11 cities of almost about 70 times (14.7 sec. to 0.2 sec.) porting the problem from a single CPU core to the GPU.

The code in the CUDA Tuning project is under the MIT Licence, so free to use with attribution.