System and method for efficient travel time and route computation

• US 10,133,991 B2
• Filed: 12/15/2017
• Issued: 11/20/2018
• Est. Priority Date: 09/18/2014
• Status: Active Grant

• Current Assignee: ServiceNow Incorporated
• Original Assignee: ServiceNow Incorporated
• Inventors: Henderson, Lisa, Boyle, Bryan
• Primary Examiner(s): Weber, Tamara L
• Application Number:
  US15/843,980
• Publication Number:
  US 20180107954A1
• Time in Patent Office: 340 Days
• Field of Search: None
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management

Abstract

A system and method efficiently computes travel times between an origin and destination, minimizing expensive calls to a third party service by first geographically expanding both origin and destination and then searching a cache of previously computed or obtained travel times for any route satisfying the expanded origin and destination. A further embodiment concerns a system and method to prepare an optimized routing sequence to travel to a set of geographical task sites, in satisfaction of applicable conditions for one or more of the task sites. Advantageously, optimized routing may employ the disclosed method of computing travel times between origin and destination.

Claims

1. A system, comprising:

a non-transitory memory; and

one or more hardware processors configured to read instructions from the non-transitory memory to perform operations comprising;

determining a starting location, wherein the starting location comprises a location of a completed task;

receiving a request to compute a travel route between the starting location and a set of task sites, the set of task sites comprising a first task site and a second task site;

searching for previously cached travel times between the starting location and the set of task sites, wherein the previously cached travel times were previously obtained from a request, sent via network communications using an application programming interface, to a third party service to calculate the respective travel times between the starting location, the first task site, and the second task site;

expanding a search for previously cached travel times by truncating a longitude and a latitude for geographical locations associated with the starting location and the set of task sites before searching for the previously cached travel times between the starting location and the set of task sites;

generating the travel route based on a minimization of a total travel time of respective travel times between the starting location and the first task site, between the starting location and the second task site, and between the first task site and the second task site; and

transmitting the travel route to a requestor.

2. The system of claim 1, wherein the completed task comprises a delivery of a component, an acquirement of the component, an installation of a network, a reconfiguration of the network, or any combination thereof.

3. The system of claim 1, wherein the travel route comprises driving instructions between the starting location and the set of task sites, distances between the starting location and the set of task sites, travel times between the starting location and the set of task sites, or any combination thereof.

4. The system of claim 1, wherein generating the travel route comprises:

and

calculating respective regional average speeds between the starting location, the first task site, and the second task site based on the previously cached travel times; and

generating the travel route based on the calculated regional average speeds.

5. The system of claim 1, wherein generating the travel route comprises:

calculating a regional average speed based on the previously cached travel times and corresponding travel distances;

calculating straight line distances between each of the starting location and the set of task sites;

testing multiple possible routes from the starting location and proceeding in series to the first task site and the second task site of the set of task sites using the regional average speed and the straight line distances for every segment of the multiple possible routes; and

identifying the travel route as a shortest route of the multiple possible routes.

6. The system of claim 1, wherein generating the travel route comprises:

sending a request to a third party processing system to determine the travel route.

7. The system of claim 1, wherein the travel route satisfies conditions associated with the set of task sites, wherein the conditions comprise a range of time in which the first task of the set of task sites is to be completed and an order of completing the first task relative to the second task of the set of task sites.

8. A method to determine a travel route between a set of task sites, comprising:

determining a starting location, wherein the starting location comprises a location of a completed task;

receiving a request to compute a travel route between the starting location and a set of task sites, the set of task sites comprising a first task site and a second task site;

searching for previously cached travel times between the starting location and the set of task sites, wherein the previously cached travel times were previously obtained from a request, sent via network communications using an application programming interface, to a third party service to calculate the respective travel times between the starting location, the first task site, and the second task site;

expanding a search for previously cached travel times by truncating a longitude and a latitude for geographical locations associated with the starting location and the set of task sites before searching for the previously cached travel times between the starting location and the set of task sites;

generating the travel route based on a minimization of a total travel time of respective travel times between the starting location and the first task site, between the starting location and the second task site, and between the first task site and the second task site; and

transmitting the travel route to a requestor.

9. The method of claim 8, wherein the completed task comprises a delivery of a component, an acquirement of the component, an installation of a network, a reconfiguration of the network, or any combination thereof.

10. The method of claim 8, wherein the travel route comprises driving instructions between the starting location and the set of task sites, distances between the starting location and the set of task sites, travel times between the starting location and the set of task sites, or any combination thereof.

11. The method of claim 8, wherein generating the travel route comprises:

calculating respective regional average speeds between the starting location, the first task site, and the second task site based on the previously cached travel times; and

generating the travel route based on the calculated regional average speeds.

12. The method of claim 8, wherein generating the travel route comprises:

calculating a regional average speed based on the previously cached travel times and corresponding travel distances;

calculating straight line distances between each of the starting location and the set of task sites;

testing multiple possible routes from the starting location and proceeding in series to the first task site and the second task site of the set of task sites using the regional average speed and the straight line distances for every segment of the multiple possible routes; and

identifying the travel route as a shortest route of the multiple possible routes.

13. The method of claim 8, wherein generating the travel route comprises:

sending a request to a third party processing system to determine the travel route.

14. The method of claim 8, wherein the travel route satisfies conditions associated with the set of task sites, wherein the conditions comprise a range of time in which the first task of the set of task sites is to be completed and an order of completing the first task relative to the second task of the set of task sites.

15. A tangible, non-transitory, machine-readable medium, comprising machine-readable instructions, configured to:

compute an optimized routing sequence from a starting location to a set of corresponding task sites, wherein the starting location comprises a location of a completed task, wherein computing the optimized routing sequence comprises;

searching a cache for travel times between the starting location and the set of corresponding task sites;

determining an optimized route based on minimizing a total time of the travel times between the starting location and the set of corresponding task sites;

computing expanded geographical locations of the starting location and the set of corresponding task sites prior to searching the cache for the travel times; and

transmitting the optimized route to a requestor.

16. The tangible, non-transitory, machine-readable medium of claim 15, wherein computing the optimized routing sequence comprises:

responsive to not finding the travel times within the cache, requesting a third party service to calculate the travel times between the starting location and the set of corresponding task sites.

17. The tangible, non-transitory, machine-readable medium of claim 16, wherein computing the optimized routing sequence comprises:

responsive to unavailability of the third party service, computing distances between the starting location and the set of corresponding task sites, retrieving a predefined estimated average speed, using a prescribed formula to adjust the predefined estimated average speed according to the computed distances, and computing the travel times for the computed distances using the adjusted predefined estimated average speed.