Method of determining a route from a starting point to a destination in a route network

• US 6,230,099 B1
• Filed: 07/15/1999
• Issued: 05/08/2001
• Est. Priority Date: 08/12/1998
• Status: Expired due to Term

• Current Assignee: Robert Bosch GmbH
• Original Assignee: Robert Bosch GmbH
• Inventors: Fabian, Thomas
• Primary Examiner(s): Issing, Gregory C.
• Application Number:
  US09/354,559
• Time in Patent Office: 663 Days
• Field of Search: 701/209, 701/208
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968

Abstract

In the method of determining a route from a starting point to a destination in a route network represented by a group of straight edges and nodes in a memory, especially a road network, each straight edge is correlated with a respective path resistance and the route is defined as a successive sequence of edges. The successive sequence of edges is determined by minimizing the sum of all path resistances. Each edge is also associated with at least one traffic-way-type path resistance value. The at least one traffic-way-type resistance value is first minimized during determination of a portion of the route from one edge to a following edge and only in the case that the traffic-way-type resistance value does not increase or decrease from one edge to the next is a minimization of the resistance performed for that portion of the route.

Claims

1. A method of determining a route from a starting point to a destination in a route network, said route network being represented by a group of straight edges and nodes in a memory, wherein each of said straight edges is correlated with a respective path resistance and the route is defined as a successive sequence of said edges and said successive sequence of said edges is determined by minimizing a resistance equal to the sum of all of said path resistances;

wherein each of said edges is associated with at least one traffic-way-type path resistance value, wherein at least one traffic-way-type resistance value is first minimized during determination of a portion of the route from one of said edges to a following one of said edges and only in the case that said traffic-way-type resistance value does not increase or decrease from the one edge to the following edge is a minimization of the resistance performed for said portion of said route.

2. The method as defined in claim 1, wherein said traffic-way-type path resistance value for a respective one of said edges gives a sum of all paths on which said respective one of said edges has a predetermined traffic-way-type.

3. The method as defined in claim 2, wherein said route network is a road network and said traffic-way-type designates an express highway, country road, ferry route, through street or tunnel.

4. The method as defined in claim 1, wherein said traffic-way-type path resistance value for a respective one of said edges specifies a frequency of accidents, a number of radar traps or a number of lights.

5. The method as defined in claim 1, wherein said traffic-way-type path resistance value for a respective one of said edges specifies a physical property of said respective one of said edges.

6. The method as defined in claim 5, wherein said physical property is an amount of pollution associated with said respective one of said edges.

7. The method as defined in claim 5, further comprising providing a navigation device containing said memory and supplying said physical property to said navigation device for determination of said traffic-way-type path resistance value by means of vehicle telematics.

8. The method as defined in claim 7, wherein said physical property is supplied on-line by a service provider.

9. The method as defined in claim 7, wherein said physical property is supplied via GSM.

10. The method as defined in claim 7, wherein a polygon area on a digital map is defined in which all of said edges have a predetermined one of said physical properties and said polygon area on said digital map and said predetermined one of said physical properties are supplied to said navigation device.

11. The method as defined in claim 1, further comprising selectively activating or deactivating consideration of at least one of said at least one traffic-way-type path resistance value during route determination.

12. The method as defined in claim 1, further comprising determining said route iteratively from a destination edge of said straight edges.

13. A method of determining a route from a starting point to a destination in a route network, said route network being represented by a group of straight edges and nodes in a memory, wherein each of said straight edges is correlated with a respective path resistance and the route is defined as a successive sequence of said edges and said successive sequence of said edges is determined by minimizing the sum of all of said path resistances;

said method comprising

a) setting up a route table in which a respective resistance value, following edge value and traffic-way-type value are entered for each of said straight edges in a forward direction and in a back direction;

b) setting all of said resistance values and said traffic-way-type values of the route table to infinity and clearing all of said following edge values;

c) setting said resistance value and said traffic-way-type value of a selected destination edge of said edges to zero;

d) storing the destination edge in a first list for already optimized edges;

e) setting up of an empty second list for edges to be optimized in a next step;

f) testing whether or not the first list is empty and halting said method when a positive result is obtained;

g) defining one of the edges from the first list as the actual edge;

h) defining all the edges interconnected with the actual edge as incoming edges;

i) testing for all incoming edges whether or not a traffic-way-type optimization condition, traffic-way-type value(incoming edge)>

traffic-way-type path value (incoming edge)+traffic-way-type value (actual edge), is fulfilled and if said traffic-way-type optimization condition is fulfilled proceeding to step j), but not fulfilled jumping to step k);

j) entering a respective one of the incoming edges in the second list, setting the resistance value of the respective incoming edge in the route table to the sum (path resistance (incoming edge)+resistance (actual edge)), setting the traffic-way-type value of the respective incoming edge in the route table to the sum (traffic-way-type path value (incoming edge)+traffic-way-type value (actual edge)) and entering the actual edge as the following edge of the respective incoming edge and then jumping to step I);

k) rejecting the respective incoming edge if

traffic-way-type value(incoming edge)<

traffic-way-type path value (incoming edge)+traffic-way-type value (actual edge), or when

traffic-way-type value(incoming edge)=traffic-way-type path value (incoming edge)+traffic-way-type value (actual edge), determining for the respective incoming edge whether or not a resistance optimization condition

resistance (incoming edge)>

path resistance (incoming edge)+resistance (actual edge),

 

is fulfilled, and when the resistance optimization condition is fulfilled, entering the respective incoming edge in the second list, setting the resistance value of the respective incoming edge in the route table to the sum (path resistance (incoming edge)+resistance (actual edge)), setting the traffic-way-type value of the respective incoming edge in the route table to the sum (traffic-way-type path value (incoming edge)+traffic-way-type value (actual edge)) and entering the actual edge as the following edge of the respective incoming edge, but when the resistance optimization condition is not fulfilled rejecting the incoming edge;

l) setting another of the edges in the first list as the actual edge and jumping to step h), or jumping to step m) when all of said edges contained in the first list were already previously set as the actual edge; and

m) exchanging the first list with the second list, clearing the second list and jumping to step f).

14. In a method of determining a route from a starting point to a destination in a route network, said route network being represented by a group of straight edges and nodes in a memory, wherein each of said straight edges is correlated with a respective edge travel cost and the route is defined as a successive sequence of said edges and said successive sequence of said edges is determined by minimizing the sum of all of said edge travel costs, the improvement comprising associating each of said edges with a first travel cost in the form of at least one traffic-way-type path resistance value and also with a second travel cost in the form of a path resistance value, wherein at least one traffic-way-type resistance value is first minimized during determination of a portion of the route from one of said edges to a following one of said edges and only in the case that said traffic-way-type resistance value does not increase or decrease from the one edge to the following edge is a minimization of a resistance for said portion of said route performed.