System and method for efficient travel time and route computation

Patent metadata

Field	Value
Publication number	US-10133991-B2
Application number	US-201715843980-A
Country	US
Kind code	B2
Filing date	Dec 15, 2017
Priority date	Sep 18, 2014
Publication date	Nov 20, 2018
Grant date	Nov 20, 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 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 trave

Assignees

• Servicenow Inc

Inventors

• Henderson Lisa
• Boyle Bryan

Classifications

• G01C21/343

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

• 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

• G06Q10/08

  Logistics, e.g. warehousing, loading or distribution; Inventory or stock management · 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