US Patent 9222791 Query scenarios for customizable route planning

A point-to-point shortest path technique supports real-time queries and fast metric update or replacement (metric customization). Determining a shortest path between two locations uses three stages: a preprocessing stage, a metric customization stage, and a query stage. Extensions to the customizable route planning (CRP) technique for routing are provided. These extensions include, for example, the computation of alternative routes, faster techniques for unpacking shortcuts, efficient query techniques for batched shortest path (one-to-many, many-to-many, and points of interest) determinations, and determining routes and alternative routes using traffic information.