Utilizing determined optimized time windows for precomputing optimal path matrices to reduce computer resource usage

• US 10,325,493 B1
• Filed: 12/30/2018
• Issued: 06/18/2019
• Est. Priority Date: 08/02/2018
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: MapAnything, Inc. (Salesforce.com, Inc.)
• Inventors: Stewart, John Brian, Weerapurage, Dinesh Premalal, Carnes, Timothy Alan, Groer, Christopher Sebastian, Gallege, Lahiru Sandakith Pileththuwasan, Lou, Chenlu
• Primary Examiner(s): Kiswanto, Nicholas
• Application Number:
  US16/236,577
• Time in Patent Office: 170 Days
• 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: G06F 17/11 for solving equations , e.g. nonlinear equations, general mathematical optimization problems optimization specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G08G 1/096811 where the route is computed offboard
• CPC Class Codes: G08G 1/0969 having a display in the form of a map

Abstract

A method involves accelerating the electronic determination of high quality solutions to routing problems by utilizing determined optimized time windows for precomputing optimal path matrices to reduce computer resource usage. The use of traffic windows defined based on changes in rates of change of speeds for traffic on road segments allows for more rapid determination of a set of one or more high quality solutions as compared to requiring on-demand, in-process determination of a shortest path for a particular time during comparison of paths or routes performed as part of a process for determining high quality solutions to the routing problem.

Claims

1. A method involving accelerating the electronic determination of optimized solutions to routing problems by utilizing determined optimized time windows for precomputing optimal path matrices to reduce computer resource usage, the method comprising:

(a) receiving, at a server, problem data for a routing problem comprising information for one or more locations involved in the routing problem;

(b) electronically accessing traffic data for a first set of road segments in one or more areas of a road network encompassing the one or more locations, the traffic data comprising speed information for travel along the road segments at various times;

(c) electronically defining, based on the accessed traffic data for the first set of road segments, a plurality of traffic windows each having a start time and an end time during a time period, electronically defining the plurality of traffic windows comprising

(i) electronically applying statistical methods to the accessed traffic data to determine a plurality of inflection points which represent times at which a change in a rate of change of speeds exceeds a minimum threshold, and

(ii) electronically defining a start time and an end time for each traffic window of the plurality of traffic windows based on the determined plurality of inflection points, each inflection point representing an end time for one traffic window and a start time for another traffic window;

(d) electronically populating one or more optimal path matrices with travel time estimates for each defined traffic window by, for each respective defined traffic window, calculating, for each of one or more respective ordered pairs of locations involved in the routing problem, a respective travel time estimate for an optimal path for travel from a respective first location of the respective ordered pair of locations to a respective second location of the respective ordered pair of locations, such calculated respective travel time estimate being calculated based on road network data and traffic data for that respective defined traffic window;

(e) electronically determining a set of one or more optimized solutions to the routing problem using a plurality of the calculated travel time estimates accessed from the one or more optimal path matrices; and

(f) returning, from the server, data corresponding to the determined set of one or more optimized solutions to the routing problem;

(g) wherein the use of traffic windows defined based on changes in rates of change of speeds for traffic on road segments allows for more rapid determination of the set of one or more optimized solutions as compared to requiring on-demand, in-process determination of an optimal path for a particular time during comparison of paths or routes performed as part of a process for determining optimized solutions to the routing problem.

2. The method of claim 1, wherein the time period comprises a week.

3. The method of claim 1, wherein the time period comprises a day.

4. The method of claim 1, wherein the time period comprises a plurality of weeks.

5. The method of claim 1, wherein the time period comprises one or more months.

6. The method of claim 1, wherein the time period comprises a plurality of days.

7. The method of claim 1, wherein electronically defining a start time and an end time for each traffic window of the plurality of traffic windows based on the determined plurality of inflection points comprises automatically defining a start time for a first traffic window proximate a certain time of day.

8. The method of claim 1, wherein electronically defining a start time and an end time for each traffic window of the plurality of traffic windows based on the determined plurality of inflection points comprises automatically defining a start time for a traffic window proximate midnight.

9. The method of claim 1, wherein electronically defining a start time and an end time for each traffic window of the plurality of traffic windows based on the determined plurality of inflection points comprises defining a traffic window which overlaps from one day to a next day.

10. The method of claim 1, wherein electronically populating one or more optimal path matrices with travel time estimates for each defined traffic window comprises electronically populating a different optimal path matrix for each defined traffic window.

11. The method of claim 1, wherein electronically populating one or more optimal path matrices with travel time estimates for each defined traffic window comprises electronically populating a single optimal path matrix with travel time estimates for each defined traffic window.

12. A method involving accelerating the electronic determination of optimized solutions to routing problems by utilizing determined optimized time windows for precomputing optimal path matrices to reduce computer resource usage, the method comprising:

(a) receiving, at a server, problem data for a routing problem comprising information for one or more locations involved in the routing problem;

(b) electronically accessing traffic data for a first set of road segments in one or more areas of a road network encompassing the one or more locations, the traffic data comprising travel time information for travel along the road segments at various times;

(c) electronically defining, based on the accessed traffic data for the first set of road segments, a plurality of traffic windows each having a start time and an end time during a time period, electronically defining the plurality of traffic windows comprising

(i) electronically applying statistical methods to the accessed traffic data to determine a plurality of inflection points which represent times at which a change in a rate of change of travel times exceeds a minimum threshold, and

(ii) electronically defining a start time and an end time for each traffic window of the plurality of traffic windows based on the determined plurality of inflection points, each inflection point representing an end time for one traffic window and a start time for another traffic window;

(d) electronically populating one or more optimal path matrices with travel time estimates for each defined traffic window by, for each respective defined traffic window, calculating, for each of one or more respective ordered pairs of locations involved in the routing problem, a respective travel time estimate for an optimal path for travel from a respective first location of the respective ordered pair of locations to a respective second location of the respective ordered pair of locations, such calculated respective travel time estimate being calculated based on road network data and traffic data for that respective defined traffic window;

(e) electronically determining a set of one or more optimized solutions to the routing problem using a plurality of the calculated travel time estimates accessed from the one or more optimal path matrices; and

(f) returning, from the server, data corresponding to the determined set of one or more optimized solutions to the routing problem;

(g) wherein the use of traffic windows defined based on changes in rates of change of travel times for traffic on road segments allows for more rapid determination of the set of one or more optimized solutions as compared to requiring on-demand, in-process determination of an optimal path for a particular time during comparison of paths or routes performed as part of a process for determining optimized solutions to the routing problem.

13. The method of claim 12, wherein the time period comprises a week.

14. The method of claim 12, wherein the time period comprises a plurality of weeks.

15. The method of claim 12, wherein the time period comprises one or more months.

16. The method of claim 12, wherein the time period comprises one or more days.

17. The method of claim 12, wherein electronically defining a start time and an end time for each traffic window of the plurality of traffic windows based on the determined plurality of inflection points comprises automatically defining a start time for a traffic window proximate midnight.

18. The method of claim 12, wherein electronically defining a start time and an end time for each traffic window of the plurality of traffic windows based on the determined plurality of inflection points comprises defining a traffic window which overlaps from one day to a next day.

19. The method of claim 12, wherein electronically populating one or more optimal path matrices with travel time estimates for each defined traffic window comprises electronically populating a different optimal path matrix for each defined traffic window.

20. The method of claim 12, wherein electronically populating one or more optimal path matrices with travel time estimates for each defined traffic window comprises electronically populating a single optimal path matrix with travel time estimates for each defined traffic window.