Bing Maps Routing API knows shortest route that visits all waypoints

  1. Brink's Avatar
    Posts : 38,910
    64-bit Windows 10 Pro build 18898
       #1

    Bing Maps Routing API knows shortest route that visits all waypoints


    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
      My ComputersSystem Spec

  2.    #1

    Does that mean that MS has solved the infamous "traveling salesman" problem? I wonder...
    --Ed--
      My ComputersSystem Spec

  3.    #2

    EdTittel said: View Post
    Does that mean that MS has solved the infamous "traveling salesman" problem? I wonder...
    --Ed--
    Good question. Are MS claiming their algorithm finds the mathematically optimum route given the constraints or just a good but maybe sub-optimal solution?
      My ComputersSystem Spec


 

Related Threads
Source: Bing Maps Location Recognition API Now Generally Available | Maps Blog
Source: Announcing Improvements to Maps Related Searches for the UK | Maps Blog See also: Bing Maps United Kingdom Quality Update 2018 | Maps Blog
Source: Geocoding and Routing improvements added to Bing Maps | Maps Blog
Source: Bing Maps V8 Web Control SDK November 2017 Update | Maps Blog
Bing Maps V8 Summer Update in Windows 10 News
Source: Bing Maps V8 Summer Update | Maps Blog
Our Sites
Site Links
About Us
Windows 10 Forums is an independent web site and has not been authorized, sponsored, or otherwise approved by Microsoft Corporation. "Windows 10" and related materials are trademarks of Microsoft Corp.

© Designer Media Ltd
All times are GMT -5. The time now is 12:07.
Find Us