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:
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?
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: