Method and apparatus for trip routing with configurable constraints

• US 7,774,133 B2
• Filed: 07/05/2006
• Issued: 08/10/2010
• Est. Priority Date: 07/05/2006
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Schwarzmann, Winfried
• Primary Examiner(s): Tran; Dalena
• Application Number:
  US11/481,880
• Publication Number:
  US 20080010006A1
• Time in Patent Office: 1,497 Days
• Field of Search: 701/201, 701/208, 701/209, 342/451, 342/452, 340/995
• US Class Current: 701/202
• 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

Abstract

A method of analyzing a path by defining a plurality of contiguous geographical regions, each to have a uniform value of a characteristic affecting travel through the region and evaluating the path from a point in an origin region through an intermediate region to a point in a destination region. Related methods and means of representing paths, and systems to implement the methods are also described and claimed.

Claims

1. A method comprising:

defining a plurality of contiguous geographical regions, each region to have a uniform value of a characteristic throughout the region;

evaluating a path from a point in an origin region to a point in a destination region and passing through an intermediate region based on a first value of the characteristic in the origin region, a second value of the characteristic in the intermediate region, and a third value of the characteristic in the destination region;

identifying a plurality of paths from the point in the origin region to the point in the destination region, at least one path to pass through the intermediate region;

repeating the evaluating operation on each of the plurality of paths; and

selecting one of the plurality of paths based on the evaluations.

2. The method of claim 1, further comprising:

identifying an alternative path; and

selecting at least one of the path or the alternative path based on an evaluation.

3. The method of claim 1 wherein evaluating the path comprises:

identifying a plurality of alternative crossing points at which the path may cross from one region to another region; and

selecting one of the alternative crossing points.

4. The method of claim 1 wherein the characteristic comprises at least one of a legal restriction, a physical restriction, or a temporal restriction.

5. The method of claim 4 wherein the legal restriction comprises an Environment, Health and Safety (“

EH&

S”

) regulation.

6. The method of claim 1 wherein the point in the origin region and the point in the destination region mark a first segment of a multi-segment trip, the method further comprising:

repeating the evaluating operation on a path from the point in the destination region of the first segment to an endpoint of a second segment of the multi-segment trip.

7. A method comprising:

obtaining two consecutive waypoints of a trip;

identifying an origin region containing a first of the two waypoints and a destination region containing a second of the two waypoints, wherein a region is a contiguous set of points that share a common value for a characteristic;

planning a path from the first waypoint to the second waypoint through at least one intermediate region based on an evaluation of the characteristic;

returning the path;

planning the path based on at least one crossing point at a border between two consecutive regions in a sequence of regions; and

wherein

returning the path comprises returning a sequence of points starting with the first waypoint, continuing with at least one crossing point and ending with the second waypoint.

8. The method of claim 7 wherein returning the path comprises returning a sequence of regions starting with the origin region, continuing through at least one intermediate region, and ending with the destination region.

9. The method of claim 7 wherein returning the path comprises returning a sequence of crossing points, each crossing point to identify a point near an intersection of the path and a common border between two consecutive regions.

10. The method of claim 7 wherein at least one of the first waypoint and the second waypoint is identified as a zone within a region.

11. A method comprising:

obtaining two consecutive waypoints of a trip;

identifying an origin region containing a first of the two waypoints and a destination region containing a second of the two waypoints, wherein a region is a contiguous set of points that share a common value for a characteristic;

planning a path from the first waypoint to the second waypoint through at least one intermediate region based on an evaluation of the characteristic;

returning the path;

receiving a plurality of candidate paths from the first waypoint to the second waypoint;

for each candidate path, identifying a sequence of intermediate regions through which the candidate path passes; and

identifying a best path among the plurality of candidate paths based on an evaluation of each of the candidate paths.

12. The method of claim 11 wherein each candidate path of the plurality of candidate paths is specified by a sequence of crossing points between intermediate regions through which the candidate path passes.

13. A method comprising:

obtaining two consecutive waypoints of a trip;

identifying an origin region containing a first of the two waypoints and a destination region containing a second of the two waypoints, wherein a region is a contiguous set of points that share a common value for a characteristic;

planning a path from the first waypoint to the second waypoint through at least one intermediate region based on an evaluation of the characteristic;

returning the path;

evaluating the path by computing a sum of a plurality of scores, wherein a score corresponds to one of a cost to travel through a region or a cost to cross from one region to another region.

14. A machine-readable medium containing data and instructions to cause a programmable processor to perform operations comprising:

receiving an origin location, a destination location, and a cargo class;

planning a route from the origin location to the destination location through at least one intermediate region, the intermediate region defined by a difference in a factor affecting travel along the route; and

evaluating the route based on factors including the cargo class and at least one of an entry into the intermediate region, an exit from the intermediate region, or a travel through the intermediate region.

15. The machine-readable medium of claim 14 wherein the route is a first route, containing additional instructions to cause a programmable processor to perform operations comprising:

planning a second route from the origin location to the destination location;

evaluating the second route based on factors including the cargo class and a score of the second route; and

comparing the first route to the second route based on the evaluations.

16. The machine-readable medium of claim 15, containing additional instructions to cause a programmable processor to perform operations comprising:

emitting a plurality of routes ranked by a result of evaluating each of the plurality of routes.

17. The machine-readable medium of claim 14, containing additional instructions to cause a programmable processor to perform operations comprising:

emitting at least one route comprising a sequence of regions traversed by the route.

18. The machine-readable medium of claim 14, containing additional instructions to cause a programmable processor to perform operations comprising:

emitting at least one route comprising a sequence of crossing points at which the route crosses from one region to a neighboring region.

19. The machine-readable medium of claim 14, containing additional instructions to cause a programmable processor to perform operations comprising:

emitting an estimated time schedule of travel along the route.

20. The machine-readable medium of claim 14 wherein the data comprises:

a plurality of geographic region definitions, each region definition to be associated with a factor affecting travel along a route that enters, crosses or exits the region.

21. The machine-readable medium of claim 14 wherein the data comprises:

a location of at least one crossing point between a first region and a second, neighboring region.

22. The machine-readable medium of claim 14 wherein the difference in a factor affecting travel is at least one of:

a physical restriction affecting a maximum size or weight of a cargo;

a temporal restriction affecting travel along the route at a particular time;

or

a legal restriction implicated by the cargo class.

23. The machine-readable medium of claim 14 wherein evaluating the route comprises:

determining whether a shipment of the cargo class is permitted to pass from the origin location through the intermediate region to the destination location.

24. The machine-readable medium of claim 14 wherein evaluating the route comprises:

estimating a cost of moving a shipment of the cargo class from the origin location to the destination location through the intermediate region.

25. The machine-readable medium of claim 14 wherein the cargo class indicates at least one of:

a size of a shipment;

a weight of the shipment;

or

whether the shipment contains dangerous goods.

26. A method comprising:

defining a plurality of contiguous geographical regions, each region to have a uniform value of a characteristic throughout the region;

evaluating a path from a point in an origin region to a point in a destination region and passing through an intermediate region based on a first value of the characteristic in the origin region, a second value of the characteristic in the intermediate region, and a third value of the characteristic in the destination region; and

selecting one of a plurality of alternative intermediate regions wherein the path may pass through any one of the plurality of alternative intermediate regions.

27. A method comprising:

defining a plurality of contiguous geographical regions, each region to have a uniform value of a characteristic throughout the region;

evaluating a path from a point in an origin region to a point in a destination region and passing through an intermediate region based on a first value of the characteristic in the origin region, a second value of the characteristic in the intermediate region, and a third value of the characteristic in the destination region by determining whether a shipment following the path is in conformity with a first legal restriction in the intermediate region and a second legal restriction in the destination region.

28. A method comprising:

defining a plurality of contiguous geographical regions, each region to have a uniform value of a characteristic throughout the region;

evaluating a path from a point in an origin region to a point in a destination region and passing through an intermediate region based on a first value of the characteristic in the origin region, a second value of the characteristic in the intermediate region, and a third value of the characteristic in the destination region by determining a score of traversing the path or a schedule of traversing the path.