MIO API question

Question

Hi,

We are using the following MIO API to generate the schedule.

https://learn.microsoft.com/en-us/bingmaps/rest-services/routes/optimized-itinerary

It's working fine, but some of the records are not generating the proper schedule.

When we schedule 4 records , it generates the following schedule.

We found that the difference is that it should go to E first, then D, and finally to the End location. However, it goes to D first, then E, and finally to the End location, which is the reason for the increased time. To generate the schedule, we pass records to MIO, which then generates the schedule. We are currently checking if there is any parameter or way to obtain the best possible route.

Thanks!

Answer 1

Shortest path calculations (Travelling Salesmen) use a lot of compute fast and with each point added, the time to compute grows exponentially. As such a heuristic algorithm is used to estimate the shortest path through a network. Since this is an estimate, it may not find the perfect shortest solution, but one that is one of the shorter possible options. This is just how heuristic algorithms work, and any other method would take too long when you add more points. The MIO API was designed with the idea that there would be a lot of points being submitted. If you are only submitting 5 points, the brute force calculation for shortest path doesn't take that long and could be done in code and give the perfectly optimal solution. A couple of options to try if you have a small number of points (less than 10):

• Try using the Bing Maps Route API and turn on waypoint optimization. I'm not a certain if this uses heuristics always for using brute force if there is a small number of points. Worth a try. https://learn.microsoft.com/en-us/bingmaps/rest-services/examples/optimized-waypoints-example The Bing Maps RESTToolkit actually has an extension for the Route API that allows you to specify the method to use to optimize the waypoints https://github.com/Microsoft/BingMapsRESTToolkit/blob/master/Docs/Getting%20Started.md#-travelling-salesmen-problem
• Use the Azure Maps Routing API, I know for certain that it uses brute force when there is less than 10 points as I worked with the routing team to make this the case a few years ago. Note that Azure Maps is Microsoft's newest mapping platform.
• Do the calculation in code; first you need a distance matrix. You could use the Bing Maps Route Matrix API, however straight-line matrices are often good enough for most scenarios. The Haversine algorithm is commonly used for the straight-line calculations: https://rosettacode.org/wiki/Haversine_formula From there the brute force shortest path can be calculated. The code used by the Bing Maps RESTToolkit for this can be found here: https://github.com/microsoft/BingMapsRESTToolkit/blob/master/Source/Extensions/TSP%20Resources/GreedyTspAlgorithm.cs

Answer 2

Hi @Balasaheb Molawade

As we have just announced the EOL for Bing Maps MIO I recommend you review the samples provided as a replacement.

https://aka.ms/BingMapsDiyOptimizer

https://aka.ms/AzureMapsDiyOptimizer

As you have experienced, customers want to customize the optimizer and that has led to the decision to suggest each customer take ownership of the optimizer so that they can tweak it.

Sincerely,

IoTGirl