DE10311516A1 - Method for calculating the route in a navigation system - Google Patents

Abstract

A method is proposed for calculating a route from a starting point to a destination in a navigation system, the route being determined as a series of traffic route sections and / or traffic route points to which resistance values are assigned, in such a way that the total resistance of the route becomes minimal, with the Taking traffic reports indicating traffic disruptions into account when calculating the route, the resistance values of the traffic route sections and / or traffic route points affected by the traffic disruptions are increased, which is characterized in that at least lower-value classified traffic route sections and / or traffic route points in the vicinity of a traffic route section and / or traffic route point affected by a traffic disruption the same resistance is assigned as the traffic route section and / or traffic route point affected by the traffic disruption. DOLLAR A This means that route calculation through particularly sensitive areas, in particular residential streets or traffic-calmed zones, can be prevented, particularly in the case of inner-city or inner-city traffic disruptions.

Description

State of technology

The invention is based on a method for route calculation in a navigation system of the type of the independent Claim from.

They are the navigation systems for motor vehicles known that are able to enter a destination via a User interface a route from a current location, which is determined by means of a locating device for the input Calculate destination. The route calculation is in a database stored traffic route data in the form of traffic route points and / or Traffic route sections connecting traffic route points, which individually assigned resistance values, i.e. node or edge resistances are. edges resistors result from a permissible vehicle speed, for example on one and the length of a traffic route section. For example, node resistances can be average Transit times for map a traffic waypoint. The route is arranged in a row calculated from traffic route sections and / or traffic route points, wherein a route calculation algorithm on which the route calculation is based strives to reduce the total resistance of the route, which turns out to be Sum of the resistance values of the stringing together of traffic route sections and / or traffic waypoints.

It is also known to indicate traffic disruptions Traffic reports in digital form via radio, for example in the form of TMC (Traffic Message Channel) information according to the ALERT-C protocol, transferred to.

Today's navigation systems that have a radio receiver that to receive the over Broadcast broadcast Traffic announcements are capable of being generated by the Represented traffic reports Traffic disruption the route calculation. To do this, the resistance values of those affected by the traffic disruption Traffic route sections and / or traffic route points depending the type and extent a traffic disruption elevated. In as a result, the route calculation algorithm becomes a route to the exclusion of the traffic route section affected by a traffic disruption and / or calculate waypoints, if their total resistance is less than the total resistance of a route that the from a traffic disruption affected traffic route section and / or traffic waypoint. For example, a route that includes a section of a motorway calculated, however, TMC traffic reports are at least part of this section of the motorway, the Resistance of the affected section of the motorway depending by the TMC traffic reports represented traffic incidents elevated and subsequently bypassing the affected section of the motorway including low-value classified road sections, such as federal or rural roads and / or local passages calculated if the total resistance of the route is included the bypass is less than the total resistance of the route including the section of the motorway affected by the traffic disruption.

Advantages of invention

Modern digital radio transmission systems, such as DAB or DVB-T offer compared to the previous conventional FM radio and the RDS (radio data system) provided therein the advantage of a significantly increased transmission bandwidth for additional information, including for example, digitally coded traffic reports. While for the im RDS system provided TMC traffic news a limited transmission bandwidth and thus also a limited address space for addressing those affected by traffic disruptions Places is available enable the new digital broadcast transmission systems mentioned above, furthermore but also the existing RDS-TMC system to a limited extent, an extended address space and thus a much higher resolution Location encoding that is no longer just on highways and essential highways limited. It is therefore to be expected that even traffic disruptions within the future of towns or cities location-coded and thus within broadcasts Traffic announcements for this designed radio receiver and associated vehicle navigation system can be transmitted.

The method according to the invention for calculating the route in a vehicle navigation system with the features of the independent claim allows advantageously, low-value classified traffic route sections and / or Traffic waypoints in the vicinity of a traffic disorder Traffic route section and / or traffic waypoint as potential Bypass for one from the traffic disruption affected traffic route section and / or traffic route point of to exclude the route calculation.

Especially in the case of intra-local traffic disruptions The traffic according to the invention has the advantage that particularly sensitive zones, such as traffic-calmed zones or pure residential streets, can be excluded from the calculation of bypass routes for nearby traffic route sections affected by traffic disruptions, and therefore do not become part of a route calculation to avoid a traffic disruption ,

Drawings embodiments of the invention are shown in the figures and are explained in more detail below. Same Reference numerals in the figures identify the same elements.

Show it

1 2 shows a block diagram of a vehicle navigation system for carrying out the method according to the invention,

2 an excerpt from a road map with a first route computed therein by a vehicle navigation system,

3 the same section of the road map with a traffic disruption drawn therein and a second route to bypass the traffic disruption calculated by a route calculation algorithm according to the prior art,

4 the same section of the road map with the traffic disruption drawn therein and a third travel route calculated by the route calculation algorithm according to the invention to circumvent the traffic disruption,

5 the same section of the road map with the traffic disruption drawn therein and a fourth route to circumvent the traffic disruption calculated by an alternative embodiment of the route calculation algorithm according to the invention.

description of the embodiments

1 shows a block diagram of a vehicle navigation system 500 to carry out the method according to the invention.

Central component of the navigation system 500 is a calculator 550 , which is used to implement the functions of the navigation system 500 executes an operating program for the device. To the calculator 550 a GPS (Global Positioning System) receiver is connected, which determines a current location from the satellite signals received. It is also connected to the computer 550 a vehicle sensor system 510 connected, which are, for example, wheel sensors of an anti-lock braking system (ABS) and / or acceleration sensors for detecting longitudinal and / or transverse accelerations of the vehicle or a gyrocompass, the signals of the sensors mentioned being suitable for deriving signals indicating vehicle movement are. The information from the vehicle sensors 510 are, like the information from the GPS receiver, a positioning module 515 supplied, preferably in the form of a software module within the computer 550 device program to be processed is implemented. The location module 515 determines a current vehicle location from the information supplied to it and reports this to the actual navigation module 520 , which in turn is a software module within the device program.

This in 1 shown vehicle navigation system 500 also has an input unit 530 with, for example, push buttons for operating the vehicle navigation system, in particular for entering a destination by the user. The vehicle navigation system also has 500 via an output device 535 on the one hand to guide the operator during the destination input process, and on the other hand to output directions of travel as part of route guidance after the route has been calculated.

To the calculator 550 of the vehicle navigation system 500 is also a database 525 connected, in which information about traffic routes via which the route can be calculated is stored. In the present case, the database is implemented in the form of a CD-ROM drive or DVD drive in which a corresponding data carrier, namely a CD or a DVD, which contains road map data, is inserted. Alternatively, the vehicle navigation system can also query road map data from a service provider, for example via a mobile radio interface.

The in the database 525 information includes place and street names and associated geographic coordinates.

Furthermore, the database contains according to the present embodiment the invention traffic route information in the form of information about traffic route sections, especially road sections, that connect geographic points. The traffic route sections are thereby parameters such as a length of the section and a permissible maximum speed assigned. In the case of a motorway section, it can be next to or instead the permissible top speed an average speed, as in usual traffic conditions was measured or a guide speed can also be assigned. From length or length and speed value is then for each traffic route section an individual resistance value can be determined, which is either the length of the Traffic route section or the transit time through the traffic route section equivalent.

As an alternative or in addition, the database can also contain information about traffic waypoints that lie between traffic route sections gene, included. This is, in particular, information about the exact geographical location of the traffic waypoints and resistance values preferably representing transit times.

After entering the destination and a street name via the input device 530 is the navigation module 520 able using the information in the database 525 Assign geographical coordinates to the entered destination and determine a traffic route section or traffic route point at or in the vicinity of which the destination is located. Furthermore, the navigation module is able to use the location information from the location module 515 to determine a current vehicle position and with the help of information from the database 525 to determine a traffic route section or traffic route point for the location to which or in the vicinity of which the current location is located.

The navigation module calculates on the basis of the location and destination or the location and destination edge 520 using a calculation algorithm known per se, for example according to Ford-Moore, a route optimized with regard to an optimization criterion as a sequence of traffic route sections and / or traffic route points, whereby a route calculation algorithm on which the route calculation is based is aimed at the total resistance of the route, which is the sum of the resistance values to minimize the concatenation of traffic route sections and / or traffic route points.

Depending on the chosen optimization criterion different resistance values are used. In the event of the shortest route of the criterion preferably the lengths of the traffic route sections. In the case of the criterion shortest Travel time, however, are preferably the transit times the traffic route sections and, if known, the transit times through the traffic way points or intersections etc. of the optimization based on.

The car navigation system 500 still has an interface 540 to receive traffic reports indicating traffic incidents. In the present case, this is the interface 540 a radio receiver that is designed to receive traffic reports transmitted by radio stations in accordance with the TMC (Traffic Message Channel) standard. Alternatively or in addition, the interface can 540 be designed to receive further traffic reports or traffic reports transmitted according to different standards. In particular, traffic information that can be queried is expressly available here via alternative broadcasting standards, such as DAB (digital audio broadcasting), DVB / T (digital video broadcasting / terrestrial), but also, for example, via mobile radio, for example according to the GPRS or UMTS standard locked in.

the interface 540 for receiving traffic announcements is with a traffic announcement decoder 545 connected to the received traffic reports in a for the navigation module 520 understandable format. Furthermore, those are through the traffic announcement decoder 545 decoded traffic reports also via the output device 535 output for the information of the user.

To assign the received Traffic reports on geographical locations, in particular on road sections, Intersections or other prominent points in the traffic network to allow include these locations. In the simplest case it is absolute geographic coordinates, for example in the Form x ° eastern Length, y ° northern Width. Alternatively, as in the case of location referencing of the TMC systems can also transmit location codes the distinctive points, such as motorway exits, intersections etc. in the road network are clearly assigned. For the clear assignment of the coded in this way Traffic reports on traffic route sections stored in the database or traffic way points are corresponding referencing tables in the database available.

Will be through the interface 540 receive a traffic report containing a traffic disruption, the resistance value, that is to say the transit time through the affected traffic route section or traffic route point, is changed, in particular increased, in accordance with the type and / or extent of the reported traffic disruption. In the case of TMC traffic reports, events and dimensions for traffic reports are standardized. Standardized factors for increasing the resistance values are advantageously assigned to the standardized messages. For example, in the case of a traffic route section with a normal transit time ti, an extended transit time of, for example (20 × ti), can be assigned to this in the event of a reported traffic jam. It is readily apparent that influencing the resistance values of individual traffic route sections and / or traffic route points as a function of traffic reports can influence the result of the optimization algorithm on which the route calculation is based and thus the course of the route.

In the method according to the invention, in the case of received traffic reports which indicate traffic disturbances, not only the resistance values of the traffic route sections and / or traffic route points affected by the traffic disorders are increased, but also that compared to traffic route sections or traffic route points affected by the traffic disruption and classified traffic route sections and / or or traffic route points in the vicinity of a traffic route section affected by a traffic disruption and / or Ver at least the same resistance is assigned to the traffic route point as the traffic route section and / or traffic route point affected by the traffic disruption.

Classifications of traffic route sections can be provided in descending order, for example, as follows.

• - Highway
• - Federal road
• - Country road / district road
• - Local thoroughfare

• – Mehrspurige Ortsdurchgangsstraße
• – Ortsdurchgangsstraße
• – Durchgangsstraße durch Wohngebiet
• – Wohnstraße
• – Verkehrsberuhigte Zone

In the case of inner-city streets, a classification in descending order can be provided, for example, as follows.

• - Multi-lane thoroughfare
• - Local thoroughfare
• - thoroughfare through residential area
• - residential street
• - Reduced traffic zone

The method according to the invention is described below using 2 to 5 explained in more detail.

In the 2 to 5 the same section from a street map is shown. The map section refers to an area within a town or city. A federal road 10 runs through this, in the selected map section consisting of the traffic route sections 11 . 12 . 13 . 14 and 15 and / or the traffic waypoints 111 . 121 . 131 and 141 , There are also two local thoroughfares 20 , consisting of sections of traffic routes 21 . 22 . 23 . 24 . 25 and 26 or traffic waypoints 211 . 221 . 231 . 241 and 251 such as 30 , consisting of sections of traffic routes 31 . 32 and 33 in front. The above-mentioned traffic route points mark junctions or crossings from or between the aforementioned federal road 10 and the aforementioned thoroughfares 20 and 30 , From the nodes 121 . 131 . 211 . 221 . 231 . 241 and the traffic route points of the second local thoroughfare, which are marked by circles but are not described in any more detail 30 branch off residential thoroughfares, which are meshed with further residential thoroughfares, which are shown in the figure as solid thin lines, and pure residential streets or traffic-calmed zones, which are shown in the figure as thin dashed lines, via further intersections.

As shown in 2 the route calculation algorithm has calculated a route that includes the traffic route sections 11 the federal road 10 such as 21 . 22 . 23 . 24 , 25 and 26 of the first local thoroughfare 20 includes. Thus, the section consisting of the traffic route sections 21 . 22 . 23 . 24 and 25 between the crossing points 111 and 251 or the traffic route sections 11 and 26 the shortest (or fastest depending on the optimization criterion) connection.

The representation in 3 is based on the receipt of a traffic announcement, which is the traffic waypoint 221 , that is, an intersection with the second local thoroughfare 20 concerns. The content of the traffic report is, for example, a traffic jam in the area of the confluence 221 as a result of a traffic accident. This traffic event is marked with an "X" in the figure. As a result of these traffic reports, the navigation module orders 520 the adjacent traffic route sections 22 and 23 and / or the traffic waypoint 221 a significantly increased resistance value, for example in the form of a passage time through the traffic waypoint increased by a predetermined factor 221 and / or the traffic route sections 22 and 23 or a longer one of the traffic route sections enlarged by a predetermined factor 22 and 23 to.

In a navigation system according to the prior art, the route calculation algorithm would now determine the fastest or shortest route taking into account the reported traffic disruption or the correspondingly influenced resistance values. In the present example, this would be based on the edge 11 over the edges 21 . 41 . 42 . 51 . 24 and 25 to the edge 26 to lead. Accordingly, the traffic route sections would be in this route section 41 and 51 , which are residential area thoroughfares, and the traffic route section 42 , which is a pure residential street or a restricted traffic area.

The aim of the present invention is however, the calculation of alternative routes by particularly sensitive Zones or sections of traffic routes, such as this pure residential streets or traffic-calmed zones are to be prevented.

This is achieved by using at least the pure residential street 42 , which is opposite the traffic route sections 22 and 23 the local thoroughfare 20 is a lower-value classified road, the same resistance value is assigned as that of the traffic route sections 22 and 23 due to the traffic disruption at the confluence 221 has been assigned. Because in the present case two traffic route sections 22 and 23 would be affected here, preferably the traffic route section 42 the sum of the increased resistance values of the traffic route sections 22 and 23 assigned. As a result, the bypass route would be for the traffic route sections 22 and 23 , namely the section consisting of the traffic route sections 41 . 42 and 51 result in a higher total resistance than for the sum of the traffic route sections affected by the traffic disruption 22 and 23 , namely a total resistance consisting of the increased resistance of the traffic route sections 22 and 23 plus the resistances for the traffic route sections 41 and 51. Consequently, route calculation is considered inspection of the traffic route sections 41 . 42 and 51 to bypass the traffic route sections affected by the traffic disruption 22 and 23 effectively avoided. In case of doubt, the route calculation would be a traffic jam through the traffic disruption at the traffic waypoint 221 rather consider a bypass over the traffic route sections 41 . 42 and 51 ,

This increase in resistance affects all those affected by the traffic route sections affected by the traffic disruption 22 and 23 lower-value classified traffic route sections within a certain radius 100 are located around the traffic disruption or the affected traffic route sections ( 3 ).

According to a particularly advantageous embodiment of the invention, it can be provided that the degree of inferiority of the traffic route section, from which a traffic disturbance on a traffic route section lying in the vicinity or in the vicinity leads to an increase in the resistance value, can be specified. As already stated, in the case of 3 respectively. 4 it should be provided that only the resistance value of the pure residential street 42 due to the traffic disruption "X" at the point 221 is increased. This means that in the present case between the category of the road affected by the traffic disruption 20 , namely local thoroughfare and the category of the devalued street 42 , namely the pure residential street is a street category, namely the residential area thoroughfare, which is not subject to devaluation. In contrast, however, it can also be provided that not only the pure residential street 42 , but also the residential thoroughfares 41 and 54 the resistance values of the traffic route sections affected by the traffic disruption 22 and 23 be assigned, since the residential thoroughfare is also a lower category than the local thoroughfare 20 with the traffic route sections 22 and 23 ,

At the in 4 The situation described has the route calculation algorithm as a result of the increased resistance values of the traffic route sections 22 and 23 an optimized, ie shortest or fastest route from the traffic route section 11 over the traffic route sections 12 and 13 the federal road 10 , the residential area thoroughfares 71 . 72 . 73 and 74 as well as the traffic route section 33 the second thoroughfare 30 to the target edge 26 certainly.

The inclusion of residential thoroughfares 71 . 72 . 73 and 74 in the calculated route is due to the fact that it is no longer in the in 4 drawn radius 100 to drop the traffic disruption.

At the in 5 The situation shown has been defined in accordance with an alternative embodiment of the invention in such a way that all of the lower-value classified traffic route sections have been assigned a resistance value which is increased as a result of the traffic disruption and which lies within the town affected by the traffic report. Thus, in the case of 5 also the traffic route sections 71 . 72 . 73 and 74 that according to 4 Part of the route were the increased resistance values of the traffic route sections affected by the traffic disruption 22 and 23 been assigned. From the perspective of the route calculation algorithm, this results from the end of the traffic route section 13 over the edges 71 . 72 . 73 and 74 overall a higher resistance than across the edges 14 . 31 and 32 to the edge 33 , As a result, the route starting from the edge is given as a favorable route taking into account the currently selected optimization criterion 11 the route through the traffic route sections 12 . 13 and 14 the federal road 10 and further the traffic route sections 31 . 32 and 33 the second thoroughfare 30 to the target edge 26 ,

Other definitions of the radius or the area around the traffic route section affected by the traffic disruption and / or traffic waypoint are possible and are in the range of the present Invention.

Claims (2)

Method for calculating a route from a starting point to a destination in a navigation system, the route being determined as a series of traffic route sections and / or traffic route points to which resistance values are assigned, in such a way that the total resistance of the route is minimized, taking into account traffic disruptions indicating traffic messages in the route calculation, the resistance values of the traffic route sections and / or traffic route points affected by the traffic disruptions are increased, characterized in that at least the same resistance is assigned to lower-ranked classified traffic route sections and / or traffic route points in the vicinity of a traffic route section and / or traffic route point affected by a traffic disruption , such as the traffic section and / or traffic point affected by the traffic disruption. Method according to Claim 1, characterized in that the assignment of at least the same resistance as the traffic route section / traffic route point affected by the traffic disruption is limited to those lower-rated classified traffic route sections / traffic route points which lie within traffic-calmed zones and / or residential areas within town ten lie.