Traveling Salesman with multiple start points and one end point

Question

I am trying to make a Google maps application which involves routing of vehicles from different locations. For example lets say there are three vehicles, each at a different location, and they have to cover 10 locations and reach one common destination. I need to find the most optimum way to cover all the 10 points with the 3 vehicles. I know that the Google Directions API provides a "way point" feature to solve the traveling salesman problem but that's only with one vehicle. I looked at the Vehicle Routing Problem but wasn't able to find an algorithm to solve my problem. I will appreciate if anyone can point me in the right direction to solve this problem.

Answer 1

I believe this can be framed as a network flow problem and solved with linear programming. Most books on linear programming address such problems. For example here's a chapter from a book on optimization

In your case I would model your starting locations as sources, the cars as the product being shipped, the cities are the nodes, and the single sink is the final destination. The weights on the routes are distances.

A special case of the network flow problem is the "shortest route tree problem" (page 8 of the paper referenced above), which sounds like your exact problem, only in reverse: you start at a common point and move to the other nodes. The solution to your problem should be the same.

Answer 2

You could model this as a Travelling Salesman Problem (one salesman who visits all cities and returns to his starting point). The modifications you have to make to the problem are:

The cost to go from the end point to the start points is zero. The end point should be duplicated as many times as there are cars.

The solution of the TSP will then give one tour that connects all cities with minimal cost. Each path (part of this tour) from one of the start points to one of the copies of the end point is then the route one of the cars should take.

Since this solution can use state-of-the-art TSP solvers, you might get better results than using an algorithm you construct yourself.