METHOD AND SYSTEM FOR MINIMAL DETOUR ROUTING WITH MULTIPLE STOPS

• US 20080275646A1
• Filed: 05/03/2007
• Published: 11/06/2008
• Est. Priority Date: 05/03/2007
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yin, Jian, Wang, Haixun, Perng, Chang-Shing, Zhang, Xiaolan
• Application Number:
  US11/743,784
• Publication Number:
  US 20080275646A1
• Time in Patent Office: Days
• US Class Current: 701/210
• 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
• CPC Class Codes: G01C 21/3476 using point of interest [POI] information, e.g. a route passing visible POIs
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

The present invention provides a system and method for optimizing routes that include multiple stops. This is accomplished by allowing users to identify a starting point, a destination, and types of businesses or other locations to be visited along the way. A route processor then provides users with a list of stores or other requested detour choices yielding a trip of optimal itinerary. The detour choices may be either an ordered sequence or an unordered set of points to be visited and may include constraints that make it possible to optimize utility functions according to user preferences.

Claims

1. A method for optimizing a route with a plurality of detours, comprising the steps of:

using at least one computer or other data processor to receive as input;

a start point,

an end point, and

at least one constraint requiring a route between said start point and said end point to pass through at least one selected intermediate point; and

using at least one computer or other data processor to provide as output a route that starts at said start point, ends at said end point, satisfies said constraint, and optimizes a given object function.

2. The method of claim 1, wherein said start point and said end point are points on a map.

3. The method of claim 1, wherein said object function is the length of a route on a map, which is to be minimized.

4. The method of claim 1, wherein the selected intermediate point is a member of a set of points of the same type, each of said points satisfying the constraint.

5. The method of claim 1, wherein a failure to satisfy the constraint results in an unfavorable change in the route'"'"'s value as reflected in the object function, thus reducing the preferability of a route that includes a choice that fails to satisfy the constraint.

6. The method of claim 1, wherein said constraint is a requirement for the route to pass through a plurality of intermediate points, each of said intermediate points being of a different type from the other intermediate points and each of said intermediate points being selected from among a plurality of candidate points of the same type.

7. The method of claim 1, wherein the constraint is a requirement for the route to include, or pass through, a plurality of intermediate points of different types, each such point being of one of a plurality of types, which plurality of types is a subset of all available types, and no such point being of the same type as another point to be included on the route.

8. A system for optimizing a route with a plurality of detours, comprising:

at least one route processor receiving as input;

a start point,

an end point, and

at least one constraint requiring a route between said start point and said end point to pass through at least one selected intermediate point; and

said at least one route processor providing as output a route that starts at said start point, ends at said end point, satisfies said constraint, and optimizes a given object function.

9. The system according to claim 8, wherein said start point and said end point are points on a map;

10. The system according to claim 9, wherein said map points are determined according to a global positioning satellite system.

11. The system according to claim 8, wherein data describing said points is received from one or a plurality of databases connected to said route processor by a network.

12. The system of claim 8, wherein said object function is the length of a route on a map, which is to be minimized.

13. The system of claim 8, wherein the selected intermediate point is a member of a set of points of the same type, each of said points satisfying the constraint.

14. The system of claim 8, wherein a failure to satisfy the constraint results in an unfavorable change in the route'"'"'s value as reflected in the object function, thus reducing the preferability of a route that includes a choice that fails to satisfy the constraint.

15. The system of claim 8, wherein said constraint is a requirement for the route to pass through a plurality of intermediate points, each of said intermediate points being of a different type from the other intermediate points and each of said intermediate points being selected from among a plurality of candidate points of the same type.

16. The system of claim 8, wherein said constraint is a requirement for the route to pass through a plurality of intermediate points of different types, each such point being of one of a plurality of types, which plurality of types is a subset of all available types, and no such point being of the same type as another point to be included on the route.

17. The system according to claim 8, wherein said output is provided as a visual display.

18. The system according to claim 8, wherein said output is provided as an audio message.

19. The system according to claim 8, wherein said output is provided as machine-readable data.

20. A machine-readable medium for optimizing a route with a plurality of detours, on which are provided:

machine-readable instructions for at least one computer or other data processor to receive as input;

a start point,

an end point, and

at least one constraint requiring a route between said start point and said end point to pass through at least one selected intermediate point; and

machine-readable instructions for at least one computer or other data processor to provide as output a route that starts at said start point, ends at said end point, satisfies said constraint, and optimizes a given object function.