System and method for dynamic path optimization

• US 9,207,090 B2
• Filed: 10/17/2013
• Issued: 12/08/2015
• Est. Priority Date: 09/26/2013
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Cheng, Yu, Wang, Mengjiao, Li, Wen-Syan
• Primary Examiner(s): Cheung, Mary
• Application Number:
  US14/056,701
• Publication Number:
  US 20150088417A1
• Time in Patent Office: 782 Days
• US Class Current: 1/1
• 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

Abstract

Techniques of dynamic path optimization are disclosed. In some embodiments, a method comprises receiving an instruction to determine an optimal path from a source geographical location to a destination geographical location, and determining an optimal path from the source geographical location to the destination geographical location using corresponding historical traffic information for each one of a plurality of sub-paths. The historical traffic information for each sub-path may correspond to an estimated arrival time at a start location for the corresponding sub-path and be used to select sub-paths from the plurality of sub-paths. The selected sub-paths may define the optimal path. In some embodiments, the historical traffic information comprises an indication of traffic flow for the corresponding sub-path. In some embodiments, the indication of traffic flow comprises an average speed of traffic flow.

Claims

1. A computer-implemented method comprising:

receiving an instruction to determine an optimal path from a source geographical location to a destination geographical location;

determining, by a machine having a memory and at least one processor, an optimal path from the source geographical location to the destination geographical location using corresponding historical traffic information for each one of a plurality of sub-paths, the historical traffic information for each sub-path corresponding to an estimated arrival time at a start location for the corresponding sub-path and being used to select sub-paths from the plurality of sub-paths, the selected sub-paths defining the optimal path, the determining the optimal path comprising;

associating each one of a plurality of nodes with a corresponding one of a plurality of geographical locations, the plurality of geographical locations comprising the source geographical location, the destination geographical location, a start location for each sub-path, and an end location for each sub-path;

determining neighbor nodes from the plurality of nodes for a current node of the plurality of nodes, each neighbor node being connected to the current node via a corresponding sub-path;

estimating a corresponding time cost for traveling to each of the neighbor nodes via the corresponding sub-path based on the corresponding historical traffic information at the estimated arrival time for the current node;

selecting one of the neighbor nodes and the corresponding sub-path to be included in the optimal path;

updating the current node to be equal to the selected neighbor node; and

repeating the determining neighbor nodes, estimating, selecting, and updating steps until the current node equals the corresponding node of the destination geographical location; and

causing information about the optimal path to be displayed to a user on a device.

2. The method of claim 1, wherein the historical traffic information comprises an indication of traffic flow for the corresponding sub-path.

3. The method of claim 2, wherein the indication of traffic flow comprises an average speed of traffic flow.

4. The method of claim 2, wherein the historical traffic information further comprises an indication of availability for the corresponding sub-path.

5. The method of claim 1, wherein each selected sub-path is selected based on a preference to minimize travel time.

6. The method of claim 1, wherein the information about the optimal path comprises at least one of a time cost for the optimal path, an estimated arrival time at the destination geographical location using the optimal path, and the selected sub-paths for the optimal path.

7. A system comprising:

a machine having a memory and at least one processor; and

a dynamic path optimization module on the machine, the dynamic path optimization module being configured to;

receive an instruction to determine an optimal path from a source geographical location to a destination geographical location;

determine an optimal path from the source geographical location to the destination geographical location using corresponding historical traffic information for each one of a plurality of sub-paths, the historical traffic information for each sub-path corresponding to an estimated arrival time at a start location for the corresponding sub-path and being used to select sub-paths from the plurality of sub-paths, the selected sub-paths defining the optimal path, the determining the optimal path comprising;

associating each one of a plurality of nodes with a corresponding one of a plurality of geographical locations, the plurality of geographical locations comprising the source geographical location, the destination geographical location, a start location for each sub-path, and an end location for each sub-path;

determining neighbor nodes from the plurality of nodes for a current node of the plurality of nodes, each neighbor node being connected to the current node via a corresponding sub-path;

estimating a corresponding time cost for traveling to each of the neighbor nodes via the corresponding sub-path based on the corresponding historical traffic information at the estimated arrival time for the current node;

selecting one of the neighbor nodes and the corresponding sub-path to be included in the optimal path;

updating the current node to be equal to the selected neighbor node; and

repeating the determining neighbor nodes, estimating, selecting, and updating steps until the current node equals the corresponding node of the destination geographical location; and

cause information about the optimal path to be displayed to a user on a device.

8. The system of claim 7, wherein the historical traffic information comprises an indication of traffic flow for the corresponding sub-path.

9. The system of claim 8, wherein the indication of traffic flow comprises an average speed of traffic flow.

10. The system of claim 8, wherein the historical traffic information further comprises an indication of availability for the corresponding sub-path.

11. The system of claim 7, wherein the dynamic path optimization module is configured to select sub-paths based on a preference to minimize travel time.

12. The system of claim 7, wherein the information about the optimal path comprises at least one of a time cost for the optimal path, an estimated arrival time at the destination geographical location using the optimal path, and the selected sub-paths for the optimal path.

13. A non-transitory machine-readable storage device, tangibly embodying a set of instructions that, when executed by at least one processor, causes the at least one processor to perform a set of operations comprising:

receiving an instruction to determine an optimal path from a source geographical location to a destination geographical location;

determining an optimal path from the source geographical location to the destination geographical location using corresponding historical traffic information for each one of a plurality of sub-paths, the historical traffic information for each sub-path corresponding to an estimated arrival time at a start location for the corresponding sub-path and being used to select sub-paths from the plurality of sub-paths, the selected sub-paths defining the optimal path, the determining the optimal path comprising;

associating each one of a plurality of nodes with a corresponding one of a plurality of geographical locations, the plurality of geographical locations comprising the source geographical location, the destination geographical location, a start location for each sub-path, and an end location for each sub-path;

determining neighbor nodes from the plurality of nodes for a current node of the plurality of nodes, each neighbor node being connected to the current node via a corresponding sub-path;

estimating a corresponding time cost for traveling to each of the neighbor nodes via the corresponding sub-path based on the corresponding historical traffic information at the estimated arrival time for the current node;

selecting one of the neighbor nodes and the corresponding sub-path to be included in the optimal path;

updating the current node to be equal to the selected neighbor node; and

repeating the determining, estimating, selecting, and updating steps until the current node equals the corresponding node of the destination geographical location; and

causing information about the optimal path to be displayed to a user on a device.

14. The non-transitory machine-readable storage device of claim 13, wherein the historical traffic information comprises an indication of traffic flow for the corresponding sub-path.

15. The non-transitory machine-readable storage device of claim 13, wherein each selected sub-path is selected based on a preference to minimize travel time.