SYSTEM AND METHOD FOR TRIP ROUTING WITH CONFIGURABLE CONSTRAINTS

• US 20100152998A1
• Filed: 02/22/2010
• Published: 06/17/2010
• Est. Priority Date: 07/05/2006
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Schwarzmann, Winfried
• Granted Patent: US 8,467,958 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• 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; and

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.

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 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.

5. 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 characteristic;

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

returning the path.

6. The method of claim 5 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.

7. The method of claim 5 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.

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