Bing blogs

This is a place devoted to giving you deeper insight
into the news, trends, people and technology behind Bing.

Maps Blog

January
05

Bing Maps New Routing Engine

Did you happen to notice the new routing engine we implemented on Bing Maps? No? I suppose that’s a good thing since your service was never interrupted. However, I can tell you that we’re enjoying the reduced latency, high performance, low overhead benefits of a new route calculation algorithm that changes the game in how driving directions queries are computed. It started when I took over as PM of backend services for Bing Maps. The Microsoft Research team presented this crazy new idea to replace our modified Dijkstra's algorithm with the blandly named “Customizable Route Planning” algo. We’ve been using our own modified Dijkstra for years, it’s done a great job and it’s flexible – so, why would we change that? Once we saw the calculation numbers it was a no brainer to begin implementation immediately. For any of our route calculations we’re now processing requests twice as fast as we ever have. Oh, snaps! Now, if only CRP could double the speed limit. Future enhancement!

CRP_02

The CRP routing engine comes with some special sauce too. We exposed a feature in the API for alternate routes, so when you’d like to see additional options for the route you can request up to 3 routes in one request using the maxSolutions method. You can then display them on the map for visual reference.

So, how does it work? Well, it’s 3 major steps: Preprocessing. More preprocessing. Then, real time query calculation. Easy, right?! Here’s an excerpt from the CRP

Basic Algorithm. Our metric-independent preprocessing stage partitions the graph into connected cells with at most U (an input parameter) vertices each, with as few boundary arcs (arcs with endpoints in di erent cells) as possible. The metric customization stage builds a graph H containing all boundary vertices (those with at least one neighbor in another cell) and boundary arcs of G. It also contains a clique for each cell C: for every pair (v;w) of boundary vertices in C, we create an arc (v;w) whose cost is the same as the shortest path (restricted to C) between v and w (or in nite if w is not reachable from v). We do so by running Dijkstra from each boundary vertex. Note that H is an overlay [24]: the distance between any two vertices in H is the same as in G. Finally, to perform a query between s and t, we run a bidirectional version of Dijkstra's algorithm on the graph consisting of the union of H, Cs, and Ct. (Here Cv denotes the subgraph of G induced by the vertices in the cell containing v.) As already mentioned, this is the basic strategy of separator-based methods. In particular, HiTi [19] uses edge-based separators and cliques to represent each cell. Unfortunately, HiTi has not been tested on large road networks; experiments were limited to small grids, and the original proof of concept does not appear to have been optimized using modern algorithm engineering techniques. Our rst improvement over HiTi and similar algorithms is to use PUNCH [5] to partition the graph. Recently developed to deal with road networks, it routinely nds solutions with half as many boundary edges (or fewer), compared to the general-purpose partitioners (such as METIS [20]) commonly used by previous algorithms. Better partitions reduce customization time and space, leading to faster queries. For our experiments, we used relatively long runs of PUNCH, taking about an hour. Our results would not change much if we used the basic version of PUNCH, which is only about 5% worse but runs in mere minutes. We use parallelism: queries run forward and reverse searches on two CPU cores, and customization uses all four (each cell is processed independently).

If you’re really hardcore, you can read the full paper on the Microsoft Research web site. Special thanks to the Microsoft Research Team - Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck.

CP

Comments

  • Would I see these new routes on my Windows Phone?

    Also, is there a way to avoid tolls on the phone?

  • Why doesn't Bing Maps have auto-complete on destinations as Google Maps? It's annoying to type the whole destination.

  • Yes! The new routing engine is already in place and working behind the scenes for all US-based routes.

  • Auto-complete is on the backlog.

  • The WP team hasn't implemented "avoid toll roads" into the native mapping application. It's in the API, though. :)

  • Hi Chris,

    Its al very well to have these technical updates but what about updating the maps themselves?  This past weekend my family drove to Boise from Portland.  Not having done so before, we decided to stay in Pendleton at the ***.  When I cam into town, I used my WP7 phone to provide directions to the *** hotel but it led me through Pendleton down some dusty country road to nowhere.  We ended up using Google Maps on the phone to estimate where the *** was.  It was up at the next interstate exit.

    I love Windows phone and use bing constantly but failures with Bing Maps and directions on the phone are too common.  Is the Bing team aware of these things or how can the community pass feedback on inaccurate maps and routes?

  • Looks like the text extraction from the algorithm paper doesn't understand typesetting ligatures (ff, fi etc. typeset as one glyph).  Can you put them in?

  • Why is maxSolutions available only in USA?

  • I'm curious as to why the "maxSolutions" has a note in the docs saying "This parameter does not support routes with more than two waypoints."  So if I have a route with a waypoint in the middle, will I have to call the API from point 1 to 2, then from 2 to 3, in order to get all available solutions for the three points?  Docs link: msdn.microsoft.com/.../ff701717.aspx