Method for the automatic calculation of optimum routes

• US 7,711,474 B2
• Filed: 08/16/2002
• Issued: 05/04/2010
• Est. Priority Date: 09/14/2001
• Status: Active Grant

• Current Assignee: Robert Bosch GmbH
• Original Assignee: Robert Bosch GmbH
• Inventors: Hoeling, Holger, Mueller, Guido
• Primary Examiner(s): Tran; Khoi
• Assistant Examiner(s): Broadhead; Brian J
• Application Number:
  US10/489,486
• Publication Number:
  US 20050065717A1
• Time in Patent Office: 2,818 Days
• Field of Search: 701/201, 701/202, 701/206, 701/208, 701/209, 701/210
• US Class Current: 701/201
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries

Abstract

A method for automatically calculating optimum routes in a traffic-route network is provided, taking into consideration at least one set, fixed route section, where the traffic-route network is described by segments for traffic-route sections, weighted with a resistance, and nodes for the intersection points of traffic-route sections, and the route to be calculated runs from a starting segment to a destination segment, and where, for purposes of optimization, the segments from the destination segment to the starting segment are evaluated with respect to the best resistance. The route is optimized, in each instance, from a starting segment up to the fixed route sections, at the fixed route sections, and from the fixed route section up to a destination segment.

Claims

1. A method for automatically calculating an optimum route in a traffic-route network, taking into consideration a predefined route section that includes a plurality of segments linked to one another, the method comprising:

describing the traffic-route network by segments representing traffic-route sections, each segment being weighted with a respective resistance;

calculating a route from a starting segment to a destination segment, taking into consideration the predefined route section,

initially optimizing a second portion of the route extending from the predefined traffic route section with respect to a favorable resistance to the destination segment so that the second portion of the route is yielded by a transition segment of the predefined route section to the destination segment;

optimizing a first portion of the route extending from a starting segment to the predefined route section for the least resistance to both the destination segment and the predefined route section, wherein an overall route is yielded from the first portion of the route and the second portion of the route from the starting segment via a part of the predefined route section, at least via the transition segment, to the destination segment;

dividing the route into at least two route portions including the first portion extending from the starting segment up to approximately the end of the predefined route section, and the second portion extending from approximately the end of the predefined route section up to the destination segment;

separately optimizing the first portion and the second portion; and

determining the optimum route from the results of the optimization for the first portion and the second portion.

2. The method of claim 1, wherein a route for a starting route segment and for a destination route segment is defined as optimal for an incoming segment that is interconnected with a specific segment to be tested when one of:

i) a resistance of the route, defined as being currently optimal for the incoming segment, is less optimal than the resistance of a new route starting from the incoming segment, using an actual segment that was previously optimized; and

ii) a resistance of the route, defined as currently optimal for the incoming segment, corresponds to the resistance of a new route starting from the incoming segment, using the actual segment, and the resistance of the route defined as being currently optimal for the incoming segment with reference to the entire route, is less optimal than a total resistance of the entire, new route starting from the incoming segment, using the actual segment.

3. The method of claim 2, wherein:

a) the second route portion is optimized first;

b) the first route portion is optimized subsequently; and

c) the optimum route is determined from the results of the optimization of the first and second route portions.

4. The method of claim 2, further comprising:

initializing a route table for the first route portion and the second route portion, the route table having all possible segments of the traffic-route network for the route in the specific route segment, the initialization being such that each segment has one resistance per direction of a segment and each resistance includes a subsequent segment number;

wherein, for the initialization, the resistances are set to an extreme value and subsequent segments are set to undefined.

5. The method of claim 4, further comprising:

initializing original segments, from which the optimization is started, to optimize the route in the second route portion; and

setting the resistance of the original segments in the route table to zero and setting corresponding successor segments to unavailable.

6. The method of claim 5, further comprising:

initializing original segments to optimize the first route portion, wherein starting segments of the destination segment having the lowest resistance up to the second route portion are provided as the original segments;

setting a total resistance of the original segments to the value determined during the optimization of the second route portion for the original segment; and

setting the resistances for the segments of the predefined route section to zero, with respect to the first route portion.

7. The method of claim 6, wherein the initialization is carried out at the start of the optimization of the first route portion and the second route portion.

8. The method of claim 4, wherein the route table includes a status identifier for each segment of the predefined route section.

9. The method of claim 4, further comprising:

saving optimized segments in a segment list.

10. The method of claim 1, wherein first partial routes are determined from all segments of the predefined route section to the destination segment in the initial optimizing of the second portion, and a partial route that is a first partial route whose resistance to the destination segment is the least is selected to be updated in a route table.