System and method for efficient travel time and route computation

• US 9,911,087 B1
• Filed: 09/18/2014
• Issued: 03/06/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): Ingram, Thomas
• Application Number:
  US14/489,563
• Time in Patent Office: 1,265 Days
• 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 computer-implemented system configured to compute an optimized routing sequence for a set of task sites, the system comprising:

digital data storage; and

at least one processor coupled to the digital data storage configured to execute instructions to;

for each task site of the set of task sites;

search for previously cached travel times between a starting location and the task site, 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 a travel time between the starting location and the task site; and

transform the previously cached travel times to a route output by;

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

testing multiple possible routes from the starting location and proceeding in series to the set of tasks using straight line distances and the regional average speed to obtain distances and travel times for every segment of the multiple possible routes without sending, via network communications using the application programming interface, a second request for using the third party service; and

identifying the route output as a shortest route of one of the multiple possible routes satisfying predetermined conditions for the set of task sites; and

output the route output.

2. The system of claim 1, wherein the instructions to search for the previously cached travel times includes instructions to truncate a latitude and a longitude of each of the starting location and locations associated with each task site before searching for the previously cached travel times.

3. The system of claim 1, wherein the predetermined conditions include at least one time window applicable to a task site in the set of task sites and at least one specified order for conducting tasks at two or more task sites of the set of task sites.

4. The system of claim 1, wherein the at least one processor interfaced with the third party service using the application programming interface provided by a third party, wherein access to the third party service is controlled by a unique key, and wherein each request to the third party service results in a charge assessed against an owner of the unique key.

5. The system of claim 1, wherein the instructions to test the multiple possible routes includes instructions to search for previously cached travel times between a starting location and an ending location of each segment before using the straight line distances and the regional average speed.

6. The system of claim 5, wherein the instructions to search the record for previously cached travel times between the starting location and the ending location of each segment includes instructions to truncate a latitude and a longitude of each of the starting location and the ending location of each segment before searching the record for previously cached travel times.

7. The system of claim 1, wherein the route output includes an optimized routing sequence, the sequence comprising each of the set of task sites in order of selection within the identified one of the multiple possible routes.

8. The system of claim 1, wherein the at least one processor is further configured to execute instructions, responsive to unavailability of the third party service in response to a third request for the third party service to calculate the travel time between the starting location and the task site, to:

calculate a distance between the starting location and the task site;

retrieve a predefined estimated average speed;

adjust the predefined estimated average speed according to the distance; and

calculate a travel time for the distance using the adjusted predefined estimated average speed.

9. A method to compute an optimized routing sequence for a set of task sites, the method comprising:

for each task site of a set of task sites;

searching for previously cached travel times between the starting location and the task site, 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 a travel time between the starting location and the task site; and

transforming the previously cached travel times to a route output, wherein transforming the previously cached travel times to the route output comprises;

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

testing multiple possible routes from the starting location and proceeding in series to the set of tasks using straight line distances and the regional average speed to obtain distances and travel times for every segment of the multiple possible routes without sending, via network communications using the application programming interface, a second request for using the third party service; and

identifying the route output as a shortest route of one of the multiple possible routes satisfying predetermined conditions for the set of task sites; and

outputting the route output.

10. The method of claim 9, further comprising:

truncating a latitude and a longitude of each of the starting location and locations associated with each task site before searching for the previously cached travel times.

11. The method of claim 9, further comprising:

determining a possible route of the multiple possible routes for testing by;

sorting a first number of task sites of the set of task sites having time window conditions according to window end time; and

grouping any task sites of the set of task sites without conditions relating to time or sequence after the end of the first number of task sites.

12. The method of claim 9, further comprising:

determining at least a first possible route and a second possible route of the multiple possible routes for testing by;

sorting a first number of task sites of the set of task sites having time window conditions according to window end time;

grouping any task sites of the set of task sites without conditions relating to time or sequence after the end of the first number of task sites in a first specified order to determine the first possible route; and

grouping any task sites of the set of task sites without conditions relating to time or sequence after the end of the first number of task sites in a second specified order to determine the second possible route.

13. The method of claim 12, wherein:

the identified route comprises one of the first possible route or the second possible route having a least overall travel time.

14. The method of claim 9, further comprising:

before testing the multiple possible routes using the straight line distances and the regional average speed, searching for previously cached travel times between starting and ending locations of every segment of the multiple possible routes.

15. The method of claim 14, further comprising:

truncating a latitude and a longitude of each of the starting and ending locations before searching the record for previously cached travel times between starting and ending locations of every segment of the multiple possible routes.

16. The method of claim 9, further comprising:

sending a third request to the third party service to obtain at least one of step by step driving instructions, distances, or travel times along the identified route.

17. A computer-implemented system, comprising:

digital data storage; and

at least one processor coupled to the digital data storage configured to execute instructions for;

searching the digital data storage for previously cached travel times between a starting location and each task site of a set of task sites; and

transforming the previously cached travel times to a route output by;

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

testing multiple possible routes from the starting location and proceeding in series to the set of task sites using straight line distances and the regional average speed to obtain distances and travel times for every segment of the multiple possible routes without sending, via network communications using an application programming interface, a request for using the third party service; and

identifying the route output as a shortest route of the multiple possible routes satisfying predetermined conditions for the set of task sites; and

outputting the route output.