Method for the automatic calculation optimum routes

• US 20050065717A1
• Filed: 08/16/2002
• Published: 03/24/2005
• Est. Priority Date: 09/14/2001
• Status: Active Grant

• Current Assignee: Robert Bosch GmbH
• Original Assignee: Robert Bosch GmbH
• Inventors: Hoeling, Holger, Mueller, Guido
• Granted Patent: US 7,711,474 B2
• Time in Patent Office: Days
• 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-10. -10. (canceled).

11. A method for calculating an optimum route in a traffic-route network, taking into consideration a predefined route section, 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 part of the route extending from the predefined route section to the destination segment so that resistance to the destination is minimized; and

evaluating a part 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.

12. The method of claim 11, further comprising:

dividing the route into at least two route portions including a first portion extending from the starting segment up to approximately the end of the predefined route section, and a 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.

13. The method of claim 12, wherein a route is defined as optimal for an incoming segment that is interconnected with a specific segment to be tested when one of:

i) the 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 the actual segment; and

ii) the 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.

14. The method of claim 13, 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.

15. The method of claim 13, 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.

16. The method of claim 15, 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.

17. The method of claim 16, 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.

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

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

20. The method of claim 15, further comprising:

saving optimized segments in a segment list.

21. A computer program having program codes for implementing calculation of optimum routes in a traffic-route network, taking into consideration a predefined route section, the program codes performing, when executed on a processing unit, the following:

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 part of the route extending from the predefined route section to the destination segment so that resistance to the destination is minimized; and

evaluating a part 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.