Travel route mapping

• US 7,162,363 B2
• Filed: 12/22/2004
• Issued: 01/09/2007
• Est. Priority Date: 12/22/2004
• Status: Active Grant

• Current Assignee: Leigh M. Chinitz
• Original Assignee: Leigh M. Chinitz
• Inventors: Chinitz, Leigh M.
• Primary Examiner(s): Black; Thomas
• Assistant Examiner(s): WEISKOPF, MARIE
• Application Number:
  US11/020,829
• Publication Number:
  US 20060136123A1
• Time in Patent Office: 748 Days
• Field of Search: 701/209, 701/210, 701/208, 701/211, 701/201, 701/207, 701/202, 701/200, 701/213, 340/990, 340/988, 340/995.21, 340/995.19, 340/995.2, 340/995.15, 342/357.13, 342/357.06, 180/167, 318/587, 345/440, 702/150, 731/78.R
• 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
• CPC Class Codes: G01C 21/3476 using point of interest [POI] information, e.g. a route passing visible POIs

Abstract

A method and system for providing a closed route for travel features a database having geographic information and input information including a starting point and a desired route length. The geographic information from the database and the input information are processed to define an outbound path from the starting point to a turning point, the turning point determined based on the desired route length, and to define an inbound path from the turning point to the starting point, the outbound path and the inbound path together defining the closed route. A representation of the closed route may be output as a static map, interactive map or a turn-by-turn listing.

Claims

1. A method of providing a closed route for travel, the method comprising:

providing a database having geographic information;

receiving input information including a starting point and a desired route length; and

processing the geographic information from the database and the input information to define an outbound path from the starting point to a turning point, the turning point determined based on the desired route length, and to define an inbound path from the turning point to the starting point, the outbound path and the inbound path together defining the closed route.

2. The method of claim 1 further comprising:

outputting a representation of the closed route.

3. The method of claim 2 wherein the representation includes a static map.

4. The method of claim 2 wherein the representation includes an interactive map.

5. The method of claim 2 wherein the representation includes a turn-by-turn listing.

6. The method of claim 1 wherein the geographic information includes a plurality of road segments each having a road segment length and wherein processing to define the outbound path includes:

(a) selecting a road segment corresponding to the starting point as the current road segment;

(b) cumulating the road segment length corresponding to the current road segment;

(c) evaluating one or more selection criteria to select a road segment from among one or more road segments connected to the current road segment;

(d) setting the selected road segment as the current road segment;

(e) repeating (b), (c) and (d) until the cumulated road segment length plus the distance from the current road segment to the starting point is greater than or equal to the desired route length, the turning point corresponding to the most recently selected road segment; and

(f) defining the outbound path from the series of selected road segments.

7. The method of claim 6 wherein the selection criteria includes selecting at random from among one or more road segments connected to the current road segment.

8. The method of claim 6 wherein the road segments each have a road type, the input information further includes a road type preference, and the selection criteria includes selecting from among one or more road segments connected to the current road segment based on the road type preference.

9. The method of claim 6 wherein the input information further includes a road continuity preference, and the selection criteria includes selecting from among one or more road segments connected to the current road segment based on the road continuity preference.

10. The method of claim 6 wherein the road segments each have a direction, the input information further includes a direction preference, and the selection criteria includes selecting from among one or more road segments connected to the current road segment based on the direction preference.

11. The method of claim 6 wherein the input information further includes one or more intermediate target points, and the selection criteria includes selecting from among one or more road segments connected to the current road segment based on proximity or direction to one or more of the intermediate target points.

12. The method of claim 6 wherein the road segments each have a road type, the input information further includes any combination of road type preference, road continuity preference, direction preference and one or more intermediate target points, and the selection criteria includes selecting from among one or more road segments connected to the current road segment based on any combination of road type preference, road continuity preference, direction preference, the intermediate target points and random selection.

13. The method of claim 1 wherein the geographic information includes a plurality of road segments and wherein processing to define the inbound path includes:

(a) selecting the road segment corresponding to the turning point as the current road segment;

(b) evaluating one or more selection criteria to select a road segment from among one or more road segments connected to the current road segment;

(c) setting the selected road segment as the current road segment;

(d) repeating (b) and (c) until the road segment corresponding to the starting point is selected; and

(e) defining the inbound path from the series of selected road segments.

14. The method of claim 13 wherein the selection criteria includes selecting at random from among one or more road segments connected to the current road segment.

15. The method of claim 13 wherein the road segments each have a road type, the input information further includes a road type preference, and the selection criteria includes selecting from among one or more road segments connected to the current road segment based on the road type preference.

16. The method of claim 13 wherein the input information further includes a road continuity preference, and the selection criteria includes selecting from among one or more road segments connected to the current road segment based on the road continuity preference.

17. The method of claim 13 wherein the input information further includes one or more intermediate target points, and the selection criteria includes selecting from among one or more road segments connected to the current road segment based on proximity or direction to one or more of the intermediate target points.

18. The method of claim 13 wherein the road segments each have a road type, the input information further includes any combination of road type preference, road continuity preference and one or more intermediate target points, and the selection criteria includes selecting from among one or more road segments connected to the current road segment based on any combination of road type preference, road continuity preference, the intermediate target points, random selection and a preference to return the starting point.

19. The method of claim 1 further comprising:

defining another closed route if the absolute value of the difference between the length of the currently defined closed route and the desired route length is greater than a route length threshold.

20. The method of claim 1 wherein the geographic information includes a plurality of road segments and wherein processing to define the outbound and inbound paths includes:

selecting a first series of connected road segments from the starting point to the turning point; and

selecting a second series of connected road segments from the turning point to the starting point.

21. The method of claim 20 wherein selecting includes evaluating one or more selection criteria to select a road segment from among one or more road segments connected to a current road segment.

22. The method of claim 21 wherein the road segments each have a road type, the input information further includes any combination of road type preference, road continuity preference, direction preference and one or more intermediate target points, and the selection criteria includes selecting from among one or more road segments connected to the current road segment based on any combination of road type preference, road continuity preference, direction preference, the intermediate target points and random selection.

23. The method of claim 20 further comprising:

evaluating the defined closed route for the presence of loops;

removing from the defined closed route any loops having loop length less than a loop length threshold.

24. The method of claim 20 further comprising:

evaluating the defined closed route for the presence of detours;

removing from the defined closed route any detours having detour length less than a detour length threshold.

25. The method of claim 1 wherein the geographic information includes a plurality of road segments and wherein processing to define the outbound path includes selecting a first series of connected road segments from the starting point to the turning point at random.

26. The method of claim 25 wherein processing to define the inbound path includes selecting a second series of connected road segments from the turning point to the starting point at random with a weighted preference to return to the starting point.

27. The method of claim 25 wherein processing to define the inbound path includes selecting the first series of connected road segments in reverse order.

28. A system for providing a closed route for travel, the system comprising:

a database having geographic information;

an input unit for receiving input information including a starting point and a desired route length;

a road selection unit for extracting geographic information from the database;

a route calculation unit for processing the extracted geographic information and the input information to define an outbound path from the starting point to a turning point, the turning point determined based on the desired route length, and to define an inbound path from the turning point to the starting point, the outbound path and the inbound path together defining the closed route.

29. The system of claim 28 further comprising:

an output unit for outputting a representation of the closed route.

30. The system of claim 29 wherein the representation includes a static map.

31. The system of claim 29 wherein the representation includes an interactive map.

32. The system of claim 29 wherein the representation includes a turn-by-turn listing.

33. The system of claim 29 wherein the geographic information includes plural road segments and wherein the route calculation unit processes the road segments to define the outbound and inbound paths by:

selecting a first series of connected road segments from the starting point to the turning point; and

selecting a second series of connected road segments from the turning point to the starting point.

34. The system of claim 33 wherein selecting includes evaluating one or more selection criteria to select a road segment from among one or more road segments connected to a current road segment.

35. The system of claim 34 wherein the road segments each have a road type, the input information further includes any combination of road type preference, road continuity preference, direction preference and one or more intermediate target points, and the selection criteria includes selecting from among one or more road segments connected to the current road segment based on any combination of road type preference, road continuity preference, direction preference, the intermediate target points and random selection.

36. The system of claim 33 wherein the input information includes one or more intermediate target points and further comprising:

a target identification unit for identifying a listing of road segments corresponding to the intermediate target points;

wherein the route calculation unit processes the listing of road segments to select from among one or more road segments connected to a current road segment based on proximity or direction to the intermediate target points.

37. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for:

receiving input information including a starting point and a desired route length; and

processing geographic information from a database and the input information to define an outbound path from the starting point to a turning point, the turning point determined based on the desired route length, and to define an inbound path from the turning point to the starting point, the outbound path and the inbound path together defining the closed route.

38. A system for providing a closed route for travel, the system comprising:

means for providing geographic information;

means for receiving input information including a starting point and a desired route length; and

means for processing the geographic information and the input information to define an outbound path from the starting point to a turning point, the turning point determined based on the desired route length, and to define an inbound path from the turning point to the starting point, the outbound path and the inbound path together defining the closed route.