Often referred to as ‘the traveling salesman problem’, planning how to most efficiently travel to a number of stops is an age-old problem. It’s difficult enough to optimize the stops for a single driver or delivery person’s day, and the challenge compounds quickly when trying to optimize routes for a fleet of drivers, your mobile salesforce, or a large team of repair personnel in the field.

A powerful addition to the Bing Maps routing API is now available to help! With waypoint optimization you can pass in up to 25 waypoints (stops) and they will be re-ordered and optimized to minimize travel time or distance.

Let’s look at a real-world use case to better understand the benefits of route optimization. Let’s say you run a delivery business in Kansas City. Your day begins downtown and ends in North Kansas City. Along the way you have 6 stops to make. The Route shown here in the first map was calculated based on the order the stops were passed in. That’s 131 miles and 2 hours 54 minutes of driving. In the second map, we see the result of specifying the ‘optimizeWaypoints=true’ flag on the API call. Much better! We just saved 27 miles and 30 minutes of driving.

Before optimization

After optimization

The route optimization performed is based on actual road-distance, which will yield much more accurate results compared to algorithms that cut corners and use simple straight-line ‘crow flies’ distance between stops. Geographic constraints like rivers, lakes and divided highways can really throw these calculations off. Consider the simple route below. The straight-line distance from A to B is less than half a mile. But that body of water sitting between them makes the actual driving distance 2 miles. For enterprise-grade results, you definitely want to avoid any route optimization that use straight-line distance calculations behind the scenes!

Now you’re probably thinking, this is great, but how much is this added functionality going to cost me? Here’s the best news – there is no additional charge for an optimized route! Each API call to the routing service is 1 billable transaction, whether the optimize flag is specified or not. And that includes passing in up to 25 waypoints for optimization. For requirements of more than 25 waypoints, please contact Bing Maps team at maplic@microsoft.com.

If you already know which stops a given driver in your fleet is going to make, this new optimization capability can bring big cost and time savings to your organization. But what if you have dozens of drivers needing to make 100 stops? Which stops should be assigned to which drivers to provide each driver with the most efficient itinerary?

The Bing Maps Distance Matrix API is ideal for solving this complex logistics problem. You can use it to compute optimal travel time and distances from all origins to destinations at scale, and then combing with optimization algorithms find the best stops for each driver to make. You can then use the waypoint optimization function to find the best driving directions with turn by turn instructions for each driver’s itinerary.

Learn more about the Distance Matrix API on our website and check out the developer docs. Also, for code samples, go to GitHub.

Note: If you are using the Bing Maps JavaScript control for route calculation, these new optimization parameters are not yet exposed there. We are working on that and will have news here on the blog when it is ready, but for now these route optimization capabilities are only in our REST API.

A great place to get started is with the documentation for the Route API. And this quick tutorial will show you how to create the REST URL optimizing 5 stops along a route.

– Bing Maps Team

Source: Bing Maps Routing API knows the shortest route that visits all waypoints! | Maps Blog