Geek Answers Handbook

The algorithm for minimizing the time of movement

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

I was thinking about something along the lines of creating a matrix in which the value located in (x, y) would be the distance of moving from the initial location x to the destination y, and then would perform some kind of matrix operation / algorithm for select such values so that each row / column has only one value selected from it, and so that the sum of these values ​​is minimized. Does anyone have any prerequisites for algorithms of this kind?

Comment Based Clarification:

  • Each destination must be visited by one traveler. All travelers do not need to visit all destinations.
  • If there are more destinations than travelers, travelers should simply hit one arbitrary destination (still minimizing the trip time) and then repeat the problem, but with two smaller directions.
  • The maximum number of recipients and travelers should be about 30 destinations and 10 travelers, so not a huge amount. I would like to avoid sheer brute force, if possible, nonetheless.
+4
source share
3 answers

Take a look at the Floyd-Warsall algorithm and Combine Sort Algorithm .

Given that the number of places to visit (peaks) is V, and the number of travelers is T, if you use the Floyd-Warsall algorithm, it should give you the shortest paths between pairs of peaks in your graph, with O (V ^ 3).

Then you can sort the lengths of the shortest paths in ascending order, which will work with complexity O (V log V).

Since you apply these algorithms sequentially, you still find the overall complexity of O (V ^ 3).

You will need to perform this second stage K times, where K is the ceiling (V / T), because at the first iteration you would visit T vertices, but V is greater than T, so you have a few more vertices to visit, At the next iteration delete the visited peaks from the calculation and sort the remaining distances (which you already found in the previous step), and then go to them from the new places of travelers T.

You can probably achieve a better result by choosing the smallest distance for each vertex, so the next selected vertex is the closest.

So your overall complexity will start to look like O (V ^ 3) + K x O (V log V), which I think tends to get closer to O (V ^ 3).

These are just a few ideas to get you started.

+3
source

If I understand your problem, I doubt that the number of travelers is important to quickly find a solution. Thus, we solve the problem with Traveling Salesman by some heuristics, and then move travelers around this cycle.

There are various design methods and various iterative improvement methods are documented. Below are a few examples (from academic to great animated examples):

+2
source

Since the Traveling Salesman problem works with factorial complexity, it can quickly grow beyond what is reasonable to run on CPY. Fortunately, the new computers are equipped with an excellent graphics card that can run problems such as hundreds or thousands of times faster than the processor.

I published an analysis and comparison of a fairly simplified solution for TSP here , which includes C # code that runs on an NVIDIA graphics card. You will also need to download the CUDAfy CUDAfy library to run the code directly.

With my Quad i7, 16 GB laptop and an NVIDIA GEFORCE GT graphics card, I report nearly 70 times better performance for 11 cities (14.7 seconds to 0.2 seconds), transferring the problem from one processor core to the GPU.

The code in the CUDA Tuning project is under the MIT license, so it can be used with attribution.

+1
source

More articles:


All Articles