System and method for efficient travel time and route computation

Patent metadata

Field	Value
Publication number	US-9911087-B1
Application number	US-201414489563-A
Country	US
Kind code	B1
Filing date	Sep 18, 2014
Priority date	Sep 18, 2014
Publication date	Mar 6, 2018
Grant date	Mar 6, 2018

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.

First claim

What is claimed is:

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

Assignees

• Servicenow Inc

Inventors

• Henderson Lisa
• Boyle Bryan

Classifications

• G06Q10/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 title

• G01C21/343

  Calculating itineraries (travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047) · CPC title

• G01C21/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 title

• G06Q10/047 Primary

  Optimisation of routes or paths, e.g. travelling salesman problem · CPC title

• G06Q10/08

  Logistics, e.g. warehousing, loading or distribution; Inventory or stock management · CPC title