Optimize route by distance

Question

I am building a Here Maps based web application. Its main features include the ability to upload a spreadsheet file (.xls, .xlsx) to the server and plan a route with the addresses in the file, up to 500 waypoints.

Of course, these waypoints aren't any way in an optimized order, so I'd like to let the user click on a "OPTIMIZE ROUTE" button and that would optimize it by distance.

For example if the file has these three addresses:

1. New York
2. San Francisco
3. Long Island

The route by default would be to go from NY to SF, then back to LI.

The application would check the distances and reorder the waypoints array in a way like this:

NY -> LI -> SF

My question: Is there a built in route optimization function in Here Maps, or should I write my own?

Answer 1

You should take a look at the Matrix Routing API. This will calculate the "real" distance between each of N x M locations. With this information, you have reduced the issue to the Travelling Salesman Problem. Of course, the TSP is NP-complete, so you can't be certain you've got the optimal answer unless you use a brute force algorithm.

Personally I'd look at a nearest neighbour solution - quick, very simple to code and usually returns a "reasonable", if not optimal solution. You can update to more complex algorithms as necessary:

Pseudo-code below:

1. Start at point A
2. Matrix routing request to all remaining points.
3. Find nearest, this becomes the next Waypoint
4. Repeat from step 2.

Answer 2

This is called the travelling salesmen problem.

You need to have a table of the distance from any place to any other place you support.

Once you have that you can use any generic travelling salesmen algorithm.

Be warned that they are very famously slow.