Method and system for dynamically navigating a vehicle to its destination

0001Process and system for dynamic route guidance of a

0002Vehicle

0003The invention relates to a method for dynamic guidance of a vehicle according to the preamble of claim 1 and a system for dynamic guidance of a vehicle according to the preamble of claim 19.

0004When driving a vehicle dynamically, the current and the future traffic situation likely to occur in the course of the journey to the destination are taken into account when selecting a route to the destination. On the one hand, so-called 'on-board methods' are used, in which the route to the destination is determined in a vehicle-side facility. On the other hand, 'off-board methods' are used, in which the route is calculated in a traffic control center. In the case of on-board methods, the traffic situation used for determining the route is made available wirelessly to the vehicle-side device, in the case of off-board methods it is kept available in the traffic control center and the calculated route is sent wirelessly to the vehicle-side device . In the following, data made wirelessly available to the vehicle-side device relating to the traffic situation - for example traffic disruptions - or the calculated route are collectively referred to as route-related data. In DE 19547574 AI it is proposed to send route-related data wirelessly from a traffic control center to a vehicle-side device, a simulation of the driving of the vehicle being carried out in real time in the traffic control center and / or m of the vehicle-side device.

0005EP 0838797 AI sets out a vehicle-side device which is set up to receive route-related data. With a given destination and start location of the vehicle, a first route is determined without taking route-related data into account. Furthermore, a second route is determined taking into account received route-related data, insofar as the received route-related data relate to the first route. If the expected travel time on the second route is shorter than the expected travel time on the first route, the driver is given selection information. The selection information offers the second route as an alternative route to the first route.

0006DE 19956108 AI forms the subject of EP 0838797 AI. For this purpose, DE 19956108 AI proposes that the vehicle-side device carries out a plurality of route determinations for alternative routes in the event that received route-related data relate to the determined first route. Alternative routes are determined for several turning points at which it is possible to leave the calculated first route, and the driver is provided with appropriate selection information.

0007The generic EP 0974137 B1 describes a method in which a vehicle-side device receives route-related data wirelessly from a traffic control center. If a traffic disturbance is detected in the traffic center on the calculated route, the traffic center determines a new route and sends this wirelessly to the vehicle-side device. The object of the present invention is to propose a universal method for dynamic destination guidance of a vehicle which takes into account traffic disturbances relevant to the vehicle and always ensures an optimal route at low cost. Another object of the invention is to propose a corresponding system.

0008The invention achieves this object with regard to the method with the features of patent claim 1 and with regard to the system with the features of patent claim 19. The subclaims relate to advantageous training and further education.

0009According to the invention, at least one traffic disruption not located on the calculated route is monitored in the traffic control center and if this traffic disruption is reduced, the calculated route is at least partially recalculated. In other words, the invention relates, for example, to the case that an alternative route to the calculated route exists, the alternative route being the “better” route if a traffic disruption were not located on it. "Better" means shorter or cheaper, for example. Therefore, if this traffic disruption diminishes, for example resolves, the route is at least partially recalculated. Thus, according to the invention, a "best" route is always calculated for the vehicle.

0010While it is already known to monitor a calculated route for whether there is a traffic disruption, the case of traffic disruptions not located on the calculated route is considered here. According to the invention, a new route is only calculated for the vehicle if such a traffic disruption is reduced. Because, for example, if such a traffic disruption "worsens", a recalculation of the route will in no case lead to a route other than the calculated route. In addition, an appropriate selection of the traffic disruptions to be monitored ensures that not all but "relevant" traffic disruptions are monitored. A traffic disruption is, for example, "relevant" and is therefore monitored if it is located on a possible alternative route to the calculated route. The invention thus ensures a cost-optimal procedure when realizing dynamic destination guidance of a vehicle using a traffic control center. Because a mostly costly transmission of route-related data is not caused every time the traffic situation changes, but only when a monitored traffic disruption is reduced. The method according to the invention can be used universally both for on-board destination guidance and for off-board destination guidance and for mixed forms (hybrid destination guidance). In addition, both in on-board destination guidance and in off-board destination guidance, the computing effort in the on-board facility or the traffic control center is minimized in that it is not necessary to redetermine or recalculate the route each time the traffic situation changes. Such a redetermination or recalculation is only necessary if a monitored traffic disruption is reduced. The method according to the invention thus universally ensures a cost-optimal procedure.

0011The traffic disruptions to be monitored, which are not located on the calculated route, can be selected in a computationally simple manner if all traffic disruptions located in a predeterminable area around the calculated route are monitored. The predeterminable area around the calculated route can, for example, be designed in the form of a corridor around the route.

0012In a particularly preferred embodiment, in the event of a change in the newly calculated route compared to the calculated route, the traffic control center wirelessly sends information to the vehicle-side device. The vehicle-side device is thus immediately informed of a possible change and the driver of the vehicle can subsequently request route-related data wirelessly from the traffic control center, for example. It is possible to provide individual support for the vehicle, since the calculated route is stored in the traffic control center and the traffic control center therefore always knows which route the vehicle is taking. Since the vehicle-side device and / or the driver of the vehicle itself the exact position of the vehicle^¬ As a result, a targeted decision can be made as to whether new route-related data should be requested from the traffic control center. The sending of route-related data, which is usually costly, is only initiated on the vehicle side if it is advantageous for the vehicle and not if the newly calculated route is changed. The information sent wirelessly by the traffic control center can also contain data as to whether the newly calculated route provides an advantage over the calculated route, for example time saving, and how great this advantage is.

0013It is advantageous if, in addition to route-related data, the traffic center sends at least one route change location position and at least one change time to the vehicle-side device together with the calculated route. For example, when calculating a route, a future traffic situation is estimated using an assumed travel course of the vehicle. If the vehicle now has a different route than estimated, for example because it makes a stopover, the traffic situation to be estimated may have changed. This in turn was used to calculate another route. If the location position and the time of the expected change in the calculated route is now available in the vehicle-side device, a simple (also automatic) decision is possible on the vehicle side as to whether new, mostly fee-based route-related data should be requested from the traffic control center. A "start time" from which a calculated route "applies" and / or an "end time" from which a calculated route no longer "applies" is provided as the change time. Additionally or alternatively, it can be provided that the traffic control center sends information about the vehicle's travel path assumed in the traffic control center to the vehicle-side device on the calculated route. The assumed trip ver^¬ Run is mapped, for example, as an assumed average vehicle speed. It can also additionally be provided that the traffic control center sends route-related data relating to a recalculated route to the vehicle-side device from the change in the position of the route.

0014It is advantageously proposed that the route be recalculated only if a traffic disruption not located on the calculated route is reduced by more than a predeterminable amount. By using such a threshold value, the frequency of the recalculation of the route is reduced without having to accept major losses in accuracy.

0015In a preferred embodiment of the invention, the route-related data are designed as traffic data. This corresponds to the embodiment of the invention as on-board destination guidance. The traffic control center wirelessly sends traffic data to the vehicle-side device and the vehicle-side device uses the received traffic data for dynamic destination guidance of the vehicle by determining a route using the traffic data. For example, the traffic disturbances "relevant" for the vehicle, ie those monitored in the traffic control center, are sent as traffic data. It can be provided that the traffic data are compiled individually for the vehicle in the traffic control center. Such "individualized" traffic data are brought about, for example, by transmitting the vehicle position when the route-related data is requested by the vehicle. In particular if, when the route recalculated in the traffic control center changes in relation to the calculated route wirelessly, information is sent from the traffic control center to the vehicle-side device, the vehicle-side device can always promptly request current, individualized traffic data.

0016In a further preferred embodiment of the invention, the route-related data are designed as route data. This corresponds to the embodiment of the invention as off-board destination guidance. In this case, a route for the vehicle is calculated in the traffic center using, for example, the monitored traffic disturbances, and this calculated route is then made available to the vehicle-side device wirelessly.

0017It is advantageously proposed that, in the case of on-board destination guidance, ie when the route-related data is in the form of traffic data, additional information about the course of a calculated or determined route between the vehicle-side device and the traffic control center is transmitted wirelessly. For example, using so-called waypoints, ie from the calculated or "Support points" located on a particular route, ensures that the traffic control center and the on-board equipment calculate or determine the same route. For this purpose, the vehicle-side device or the traffic control center selects suitable points on the route and transmits them, for example, in each case together with the request or transmission of route-related data. In addition, it can be provided that if there is a mismatch between the route determined in the vehicle device and the route calculated in the traffic control center, corresponding information is sent wirelessly. The correspondence is checked by, for example, reconstructing this route in the vehicle-side device using the information about the course of the route calculated in the traffic control center and comparing it with the route determined in the vehicle-side device itself. This ensures that the route determined in the vehicle-side device and the route calculated in the traffic control center correspond even if different matching and / or routing methods and / or databases (digital road maps) are used in each case. As an alternative or in addition, provision is made to reconstruct this route in the traffic center using the information about the course of the route calculated in the vehicle-side device and to compare it with the route determined in the traffic center itself. It is also possible (for example for the selection of traffic disruptions to be monitored) to use such a reconstructed route in the traffic control center if the reconstructed route does not match the route determined in the traffic control center itself.

0018It is also advantageous for on-board destination guidance to additionally transmit information about the predeterminable area between the vehicle-side device and the traffic control center. For example, the vehicle-side device can query a specific, predeterminable area from the traffic center and thus be informed about the traffic disruptions located in this area, or the traffic center informs the vehicle-side device about the size of the specified area. This ensures that the vehicle is looked after as well as possible at the lowest possible cost. For example, when leaving the route, when choosing a new destination or when the vehicle approaches an intermediate destination, new traffic data is only requested from the traffic control center if part of the new route lies outside the predeterminable area, i.e. in an area without route-related data . This request can be made manually by the driver or automatically. In other words, the information about the predefinable area in the vehicle-side device in the event of a route change by the vehicle that takes place within the predefinable area ensures that route-related data are also present in the vehicle-side device for the new route. A recalculation of the route in the traffic control center is simplified if only that part of the calculated route is recalculated that the vehicle has not yet traveled through assuming a minimum speed. Such a minimum speed can be read out, for example, from corresponding databases. It is particularly advantageous if three recalculations of the route are carried out using three different average speeds of the vehicle on its route. These three average speeds correspond to a statistically slowest, fastest and average driving style. Such statistical data are obtained, for example, from historical source-destination relationships that have been stored with travel time information. This takes into account that the exact position of the vehicle in the traffic control center is not known. These three recalculations allow an optimal consideration of^'Decision points' where the vehicle can leave the pre-calculated route to switch to the newly calculated route. By using three different average speeds, all practical applications regarding the position of the vehicle are covered. For example, in the event of a change in the newly calculated route compared to the calculated route, the traffic control center wirelessly sends information to the vehicle-side device, including decision points. By comparing the current vehicle position with the decision points, it is possible to select the best decision point for the vehicle, ie the one closest to its route.

0019It is advantageously proposed that the or each traffic disruption is monitored at least for a travel destination reaching time of the vehicle estimated on the traffic center side. This ensures in a particularly simple manner that the vehicle is optimally looked after during the entire journey. The time to reach the destination can be estimated, for example, using a minimum speed.

0020The additional wireless transmission of a destination destination time determined, for example estimated, on the vehicle side by the vehicle side device to the traffic control center is advantageous. This enables a reliable determination of the period for which the or each traffic disruption is monitored in the traffic center. For example, the vehicle-side device transmits corresponding information to the traffic control center together with the request for route-related data. When the destination arrival time is reached, the monitoring of the or any traffic disruption in the traffic control center is ended. In addition, the destination arrival time can also be saved in the vehicle. If the destination arrival time is then updated in the vehicle at certain time intervals, the updated destination arrival time can be transmitted to the traffic control center if a predeterminable deviation between the updated and stored destination arrival time is exceeded. The period of monitoring the or each traffic disruption in the traffic control center is thus precisely adapted to the course of the vehicle. It is therefore taken into account if, for example, the vehicle needs more (e.g. if the vehicle is traveling slower than estimated or if it makes a stopover) or less (e.g. if the vehicle is traveling faster than estimated) than the specifiable deviation in order to reach its destination. Alternatively or additionally, it is provided that the vehicle-side device sends the current vehicle position to the traffic control center when such a deviation is determined. As a further alternative or in addition, it is provided that the vehicle-side device can automatically send a feedback to the traffic center after receiving route-related data from the traffic center. This reliably ensures that the monitoring in the traffic control center is ended when the vehicle reaches its destination and / or when the destination guidance is interrupted, since the vehicle-side device will then not send any such feedback. In order to take into account the possibility that the wireless connection between the vehicle-side device and the traffic center is temporarily unavailable, it can be provided that the traffic center waits for this feedback for a certain period of time after the route-related data has been sent to the vehicle before the or any traffic disruption is ended.

0021It is particularly advantageous if, in order to determine traffic disturbances to be monitored, a route Ri is calculated in a first step without taking traffic disturbances into account, and a route R is calculated in a second step_A is calculated taking into account all traffic disruptions to the destination, in a third step all traffic disruptions are monitored for Ri and taking into account only the traffic disruptions already monitored, a route R₂ is calculated to the destination, in a fourth step all traffic disturbances on the previously calculated route R_, i ≥ 2, are monitored and a route R_{1 + i} taking into account the monitored traffic disturbances to the destination and the fourth step is repeated until the route R of the route R_A corresponds and already in a previous step all existing traffic disturbances on R_A be monitored. With this procedure, on the one hand, only those traffic disturbances are determined which are localized on routes which, when recalculated, can be a new route for the vehicle. On the other hand, only those traffic disruptions are monitored whose reduction or resolution could result in a changed route when the route was recalculated. Only "relevant" traffic disruptions on "relevant" routes (ie alternative routes) are monitored. Alternative routes are routes that could be calculated as a new route for the vehicle if one or more traffic incidents were resolved.

0022The first advantage results from the fact that in each step routes are calculated which are "optimal" taking into account part of the traffic disturbances actually present. In other words, these routes were optimal when unsupervised traffic disruptions resolved. Since only traffic disruptions are monitored on the routes calculated in this way, the first advantage arises. The second advantage is demonstrated by proof of contradiction. Assume that there is a route R_x, on which there are one or more faults Sl, ..., Sn that are not monitored by the described method. And further assumed, this route R_x if the disturbances Sl, ..., Sn were resolved, would be better than the route R calculated taking all traffic disturbances into account_A. Since it is a question of whether the traffic disruptions Sl, ..., Sn must be monitored for the detection of a change in the optimal route, the assumption that all traffic disruptions have been completely resolved also covers all other cases. A resolution is the most far-reaching change that would remain undetected if the traffic disruption was not monitored. According to the assumption, Sl, ..., Sn are not monitored and are therefore not taken into account when determining the route. For the route calculation, this corresponds to the case that all traffic disruptions have been resolved. Since Route R_x better than R_Ä then Route R_x as an optimal route R_x determined before an abort criterion is reached. Then, according to the method, all faults S1, ..., Sn are marked as to be monitored, which is a contradiction to the assumption.

0023Usually, only a few traffic disruptions need to be monitored, so that the effort in the traffic center for calculating the route to the destination requires only a small amount of computation. However, in order to reliably prevent the computing effort from becoming too great, it is advantageously proposed that the number of routes R_x on one in front^¬ specifiable maximum value n is limited. The most important traffic disruptions are thus monitored with minimal computing effort. An advantageous further development results from the fact that further routes R-_. be calculated, for example at a later time. For example, the other routes R-_. calculated when the traffic load of the traffic control center is low. This prevents the traffic center from being overloaded at peak times, but all traffic disruptions are nevertheless monitored.

0024The invention is preferably implemented as a computer program with program code means, a particular version of the method according to the invention being carried out when the respective program is executed on a computer.

0025A further preferred form of implementation of the invention is represented by a computer program product with program code means, the program code means being stored on a computer-readable data carrier in order to carry out a particular version of the method according to the invention when the respective program product is executed on a computer.

0026The invention is explained in more detail below with reference to drawings. Show:

00271 shows schematically different traffic disruptions during dynamic route guidance, FIG. 2 a, b, c, d, e, f steps of a preferred embodiment of the method according to the invention in the selection of traffic disruptions to be monitored, 4 decision points on a calculated route, FIG. 5 decision points on a route recalculated due to a reduction in a traffic disruption, FIG. 6 Determination of decision points by calculating a "shortest path tree", Fig. 7 a, b, c Determination of the decision points by ei^¬ ne sequence of several route calculations,

00288 a, b differences between the calculation of the "shortest path tree" and separate partial route calculations,

00299 use of decision points in connection with vehicle positions,

003010 shows a use of information about the predeterminable area,

003111 use of a destination arrival time determined on the vehicle side,

003212a, b, c schematically the use of a route change location position with change time of a calculated route,

003313a, b, c the use of route change location positions with change times of a calculated route,

003414 which data regarding route change location positions are transmitted from the traffic control center to the vehicle-side device.

00351 schematically shows various traffic disruptions during dynamic destination guidance from a starting point S to a destination Z. Conventionally, traffic disturbances A, B located on a route R calculated for a vehicle are monitored. The route is recalculated if the traffic situation on this route deteriorates, ie either if A and / or B worsens and / or if a new traffic disruption arises; however, if the traffic situation on the calculated route improves, no recalculation is carried out.

0036In a novel way, "relevant" traffic disturbances that are not located on the calculated route R are additionally monitored. "Relevant" means that a reduction or resolution of the traffic disruption could lead to another route. Traffic disturbances 1, 2, 3, 4 are not localized on the calculated route R in FIG. 1. Traffic disturbances 1, 2, 3, 4 are localized on alternative routes from starting point S to destination Z. If one of the traffic incidents 1, 2, 3 was reduced or resolved - and the traffic incidents remained unchanged on the calculated route R - the corresponding alternative route would be "better". Therefore, traffic disruptions 1, 2, 3 are "relevant" and are monitored. Traffic disruption 4, on the other hand, lies on such a route, which only leads to destination Z via a very long detour. Even if traffic disruption 4 would resolve, no better alternative to the calculated route R would result. Traffic disruption 4 is therefore not relevant and is not monitored. It should be noted that it is not possible to change the calculated route due to a deterioration in the traffic situation outside of the calculated route R (ie by increasing one or more traffic disruptions 1, 2, 3, 4 and / or the emergence of a new traffic disruption).

0037It should also be noted that in FIG. 1, with appropriate selection of the predeterminable area within which traffic disturbances are monitored, in addition to the "relevant" traffic disturbances 1, 2, 3, traffic disturbance 4 could also be regarded as relevant. In this case, although a reduction or resolution of this traffic disruption 4 will not lead to a change in the route, the route was recalculated. However, the traffic control center would not send any information to the vehicle-side device since the newly calculated route corresponds to the (previously calculated) route R. In the case of a "generous" choice of the predeterminable area, the low computational effort for the original route request from the vehicle-side device, in determining "relevant" traffic disruptions, a higher computational effort when improving the traffic situation, with a greater number of traffic disruptions to be considered when recalculating the route . By selecting a smaller area, the computation effort when recalculating the route can be reduced, but "relevant" traffic disruptions may be considered "not relevant". In any case, the route is recalculated when the traffic situation improves by a predetermined amount.

00382 shows steps of a preferred embodiment of the method according to the invention in the selection of traffic disruptions to be monitored. 2a shows the calculation of the optimal route Ri without taking traffic disturbances into account (first step), FIG. 2b shows the calculation of route R._A taking into account all traffic disruptions (second step), FIG. 2c the selection of traffic disruption 2 on Ri as "relevant" and calculation of route R.₂ taking into account this traffic disruption (third step), FIG. 2d the selection of traffic disruption 1 and calculation of route R.₃, the route R₃ the route R_A (fourth step; since not all traffic disruptions on R_A have been marked, further route calculations must be made), Fig. 2e the selection of traffic incidents A and B and calculation of route R.₄ (first repetition of fourth step) and FIG. 2f the selection of traffic disruption 3 and calculation of route R.₅, the route R₅ the route R_A corresponds (second repetition fourth step, since traffic disturbances A and B have already been marked in an earlier step, is canceled here).

0039A determination of marginal costs G (VS) of a traffic disruption VS can be read from FIG. 3. A partial route RA is shown, new (i) from the starting point S to the beginning of the traffic disruption VS (the position P), a partial route R_{A / new} <_) from the beginning of the traffic disruption VS (the location position P) to the destination Z, a calculated route R_A and the traffic disruption VS.

0040Each traffic disturbance VS identified as "relevant" is assigned costs K (VS), which include, for example, the loss of time caused. In addition, marginal costs G (VS) are determined, below which a change in the calculated route is possible. The marginal costs G (VS) are chosen so that in the event of a change in the calculated route in the event of a traffic disturbance VS the marginal costs are not reached. Conversely, it can happen that the marginal costs in the event of a traffic disruption are fallen short of, even though the newly calculated route remains unchanged, ie the same as the already calculated route.

0041To derive the specified marginal costs G (VS), the traffic disruption VS is considered, the costs of which are at a lower value K_New(VS) decrease and thereby change the calculated route. All other "relevant" traffic disruptions remain unchanged. Now the travel time along the newly calculated route R_A, _New searched. Since the recalculated route was caused by the reduction in the traffic disruption VS, Rs_A, _New run through VS. The route R_A, _no_ consists of a part R_A, new (i) / which runs from the starting point S to the start of the traffic disruption VS at the position P and a part R_A, _New {₂), which runs from the location P through the disturbance S to the destination Z. For this purpose, it is assumed that it is not possible to turn off the route along the route section which is occupied by the traffic disruption VS. If this were the case, R_{A / new} not necessarily run through the entire traffic disruption VS and the marginal costs considered here did not ensure detection of a change in the calculated route.

0042In the original route request, the traffic disruption VS was selected as "relevant" as a route R_x was calculated from the starting point S to the destination Z on which the traffic disruption VS is located. R_x consists of a part R_{1 (D} from the starting point S to the local position P and a part R_ι(₂> from P to destination Z. R_x is "optimal" on the condition that only those at the time of the calculation of R_x traffic disruptions selected as "relevant" are taken into account. Since R_x then "optimal", R are also R under this condition_{1 (D} and R_ (₂) "optimal". The travel time on R-_., which also only takes into account the traffic disturbances that have already been selected^¬ are viewed with t^*(R,) denotes, the same applies to the travel times of the sub-routes R__d) and R_ (₂). To be^¬ It is important to ensure that the traffic disruption VS itself at the time of the calculation of R-_. is not yet marked as "relevant". Taking into account all traffic disruptions, the "optimal" sub-route R_A,_neu (i) can have a longer or the same travel time as t^*(R_{l (1)}j where only a part of all

0043Traffic disruption was taken into account. Since both R_A,_neu (₂) as well as R_ (₂) run through the traffic disruption VS and the cost of VS in t^*(R_{l (2)}) are not included, R_A,_New(₂) only have a longer or the same travel time as the travel time of R_ (increased by the cost of the traffic disruption VS (₂> :

0044So the following applies:

0045* (^R, (l))^≤tl^RA_;new (l) j and R_{l (2}} κ_New (vs) ≤ t (R_{A ncιιi2)}) _f with this also applies: <img file="WO03091663A1_D0001.tif" />

0046Since R_A,_New is cheaper than the originally calculated route R if required_A the following also applies: <img file="WO03091663A1_D0002.tif" /> and with that t^t{R,) + K_nc,_ll(VS) &lt;t {R_A) or K_New(VS) &lt;t (R_A) - t '(R,).

0047Therefore the marginal costs G (VS) = t (R_A ) - t^* (R_l ) selected. This value can be calculated during the determination of "relevant" traffic disruptions in the original route request and its shortfall can easily be checked whenever the traffic situation changes.

0048In order to ensure that a change in the "optimal" route is recognized even in the case of traffic disruptions which extend over a number of successive route sections, such traffic disruptions can be divided into a proportion for each affected route section. In other words, traffic disturbances VS that occur over several sections of the route ki, ... k_n run into several traffic disruptions Si, ... S_n be divided, which are each considered as an independent traffic disruption, each traffic disruption S_x contains the portion of the traffic disruption S that is located on route section ki.

0049The concept of the decision points is explained in more detail with reference to FIGS. 4 and 5. FIG. 4 shows decision points on the calculated route, and FIG. 5 decision points on the route recalculated due to a reduction in a traffic disruption. Decision points are used by the traffic control center in the event of a change in the calculated route, in order to inform the vehicle at which points, ie, without precise knowledge of the vehicle position Switching to an alternative route brings a cost advantage (eg time advantage) to the location positions of the originally calculated route. When leaving the originally calculated route closest to the decision point in the direction of travel of the vehicle, the greatest cost advantage can be achieved. Therefore, this point is selected and displayed by the vehicle system. Then it can be decided, for example by the vehicle driver or automatically, whether he should, for the expected cost benefit, request a fee for new route-related data (traffic data for on-board destination guidance or route data after recalculating the route for off-board destination guidance) ) starts.

00504, decision points Pi, P₂ as well as routes R_lr R₂, R_s and a traffic incident VS is shown. The "optimal" route has a route on the originally calculated route R_s new traffic disruption VS changed. Depending on the vehicle position, one of the two alternative routes or the original route is the cheapest. If the vehicle is in front of the decision point Pi, Ri is the "best" route. The vehicle is between the decision points Pi and P.₂, so is R₂ the "best" route. If the vehicle is after decision point P₂, so is R_s the "best" route.

0051The principle of the decision points can also be used if the calculated route changes due to a reduction or resolution of a relevant disturbance. This is shown in FIG. 5. Decision points Pi, P are again shown₂ and routes R ', R (Pχ), R (P₂) and a traffic disruption VS '. The "optimal" route R 'has changed due to a reduction in the monitored traffic disruption VS'. After the recalculation, the "optimal" route includes the route with the monitored traffic disruption VS '. If the vehicle is in front of the decision point Pi, R (P_) is the "best" route. The vehicle is between the decision points Pi and P.₂, then R (P₂) the "best" route. If the vehicle is after decision point P₂, the originally calculated route R 'is the "best" route.

0052FIG. 6 shows how decision points are determined by the calculation of a "shortest path tree". The shortest route tree ("tree") is calculated using a method known per se, for example the Dij kstra algorithm, with the shortest routes to the destination Z. This results in a route calculation using route nodes ("nodes") Traffic network, for example a digital road map. The originally calculated route R is also shown. The successor of node Pi on the tree is node P₂that is not on the original route R. This is why node Pi is the first decision point on the route. The successor of Pi on the original route, node P₃, however, is not connected to node Pi by a tree edge. The situation is different with node P₄, which is the successor of node P. on the tree as well as on the original route₃ is therefore node P₃ no decision point. The successor to node P₄ on the tree, node P₅, is not the successor of P₄ on the originating route, so that node P₄ the second decision point is.

0053By tracking the tree successors of a decision point, the shortest route to the goal can be read from this decision point. 6 is the shortest path from decision point P₄ about P₅ and P₇ to the destination Z. In the event that there is sufficient transmission capacity when the vehicle is notified of the newly calculated "optimal" route, the course of the newly calculated "optimal" route of one or more decision points can also be transmitted.

0054This procedure for determining the decision points can be implemented by means of a single, backward-looking route search, with a shortest route tree being calculated from destination Z and containing the optimal routes from each point in the traffic network to destination Z. In this case, in particular for each node on the traffic network, a unique successor node is determined, which lies on the optimal route to destination Z, and the travel time on the fastest route to destination Z is determined for each node. Those nodes on the calculated route R are selected whose successor nodes on the shortest path tree are not on the route R and are chosen as decision points. For each decision point, the difference between the travel time on the calculated route R from the decision point to the destination Z and the corresponding travel time on the newly calculated shortest route tree is formed to calculate the time saving.

0055Alternatively, in order to determine the decision points, the "optimal" route is first recalculated from the point on the calculated route R that the vehicle has already exceeded assuming a minimum speed, taking into account traffic forecasts that the vehicle assumes the current time at this point. This route will run to a first decision point E_ on the calculated route R and then branch off from it. In a second step, an "optimal" route R 'from point E_x 'calculated from that directly behind the decision point E calculated in the last step_x lies on the calculated route R, it being assumed that the vehicle is currently at point E_ ^λ located. If this route R 'does not match the original route R, this creates a further decision point E₁₊χ. This second step is repeated until a maximum predetermined number of iterations is reached, the decision point E last calculated_x lies behind the point on the route that the vehicle can already have reached at a maximum assuming a maximum speed, or the last calculated route matches the originally calculated route. For each decision point, the difference between the travel time on the originally calculated route from the decision point to destination Z and the corresponding travel time on the newly calculated route is formed to calculate the time saving.

00567 a, b, c visualize the determination of the decision points by a sequence of several route calculations. Reference is made to the starting position already shown in FIG. 6. In the first route calculation, see FIG. 7a, the starting point Po is selected, since it is assumed that the vehicle at least the node P at the time ti of this new route calculation₀ has reached. In this route calculation, current and forecast traffic data are taken into account on the assumption that the vehicle is moving at time ti m P₀ located. This first route calculation shows that the "optimal" route at the node Pi branches off from the calculated route R, so Pi is selected as the first decision point Ei. The second route calculation, see FIG. 7b, begins in the successor node Eι^,=P₃ from node Ei on the calculated route R. It is now assumed that the vehicle is at time ti m P₃ located. In this second route calculation, the node P₄ = E₂ determined as the second decision point. The route obtained in the third calculation, see FIG. 7c, corresponds to the originally calculated route R, so that no further decision point is recognized. The sequence of route calculations is ended.

0057In the second alternative, more computing time has to be invested than in the first alternative, since the usual methods of route calculation are about as complex as the calculation of the shortest path tree. The advantage of the second alternative is that traffic forecasts are used more correctly. It is taken into account that the vehicle can be at various points on the original route at the time ti of the new route calculation. The future traffic situation for each route section m is thus also taken into account, for example for the point in time at which the vehicle can arrive there. In contrast, when calculating the shortest path tree according to the first alternative, the time of arrival of the vehicle t_e.g. set at destination Z. The arrival times of all other sections of the route are the points in time at which the vehicle had to leave there in order to reach the destination Z at time t_.

0058Fig. 8 illustrates this difference: When calculating the shortest path tree, the uniform arrival time t_e.g.= 10: 40 a.m. accepted at the destination, see Fig. 8a. This results in a departure time of 10:20 a.m. at P₆, 10:00 a.m. to P₃ and 9:40 a.m. to P₀. In reality, the vehicle is somewhere between P at 10:00 a.m.₀ and V_ on the original route. In the three route calculations of Po, P shown in FIG. 8b₃ and Pε out, a departure time of 10:00 a.m. is assumed. This results in the three possible arrival times 11:00 a.m., 10:40 a.m. and 10:20 a.m. The traffic situation near the destination Z is then also taken into account for these three different times, which is not the case with the shortest path tree in FIG. 8a. In the event of strong, forecast changes in the traffic situation, this can result in the calculation of different routes and, under certain circumstances, different decision points through the two methods. In other words, in the second alternative shown in FIG. 8b, it is assumed at the start of each route calculation i (i = 1, 2, 3) that the vehicle is around t^(1> = 10:00 a.m. at the respective starting point P₀, P₃ and P₆ located.

0059In a third alternative to the calculation of the decision points, the position of the vehicle unknown in the traffic control center is estimated. For example, a last destination arrival time determined and sent by the vehicle is used for this purpose. When the traffic situation changes, three (possible) vehicle positions are estimated in the traffic control center, namely for slowest, fastest and average driver behavior, and changes in the calculated route R and possibly decision points are then determined for these estimated vehicle positions and sent to the vehicle.

0060With the decision points Ei and E₂ On the originally calculated route R, those nodes have now been determined in which, according to the traffic data and forecasts currently available, a turn from the calculated, ie original route R leads to a more favorable route than remaining on the route R. For every decision point Ei, E₂ calculates the cost advantage (eg time advantage) that results from changing to the "cheaper" route. At least the last decision point in the direction of travel and its cost advantage are wirelessly transmitted to the vehicle as part of the route-related data. Alternatively or in addition, provision can be made for wirelessly transmitting a predefinable maximum number of decision points with their cost advantages to the vehicle. Of course, the transfer of a respective cost advantage can also be dispensed with. After receiving such a transmission, the vehicle-side device selects the decision point that is closest to the vehicle in the direction of travel. The position of this decision point, possibly together with the possible cost savings, is displayed to the vehicle driver. The vehicle driver can then wirelessly request route-related data from the traffic control center in the form of the newly calculated route (off-board destination guidance) or the changed traffic situation (on-board destination guidance). In this case, the transmission received is ignored by the on-board device if there is no longer a decision point in the direction of travel or if the route guidance has already been completed.

0061In Fig. 9 the use of decision points E (Pι) and E (P₂) in connection with vehicle positions Pi, P₂, P₃ shown again during the dynamic route guidance from starting point S to destination Z. The vehicle-side device checks which decision point is suitable on the basis of the vehicle position and requests automated, or on request wireless, corresponding route-related data from the traffic control center. If the vehicle is at the position Pi, branching from the calculated route R at the decision point E (Pι) enables the newly calculated route R._x avoiding traffic congestion 1 and thus - despite the greater length of the newly calculated route Ri compared to the calculated route R - a faster journey to the destination Z than if the calculated route R remains R. The vehicle is at position P.₂, a branching off from the calculated route R at the decision point E (P₂) on the newly calculated route R₂ still avoiding traffic jam 1 and thus - despite the route R₂ localized small traffic congestion 2 - a faster trip to the destination Z than if the calculated route R remains on the other hand. However, the vehicle is at position P₃, there is no longer a decision point that would allow branching off from the calculated route R and thus avoiding the traffic jam 1.

0062The use of information about the predeterminable area is illustrated in FIG. 10. Since the vehicle no longer has any route-related data for the destination Z after leaving the predeterminable region V and the traffic center has no information as to whether the calculated route R is still being followed by the vehicle, the route-related data include information about the predeterminable region V. This means that route-related data can be used in the vehicle even when a new route R is being followed₂ to an intermediate destination ZZ selected by the driver₂ possible. Because the route R₂ is completely covered by area V. In contrast, route-related data cannot be used in the vehicle if the vehicle is following a new route Ri to an intermediate destination ZZi selected by the driver. Because a large part of Route Ri is not covered by area V. It is therefore always possible to check on the vehicle whether a desired stopover is still within the predeterminable area V and / or whether the arrival time at the stopover differs greatly from the original arrival time. In this case, new route-related data is requested from the traffic control center automatically or at the driver's request.

0063FIG. 11 shows the use of a destination arrival time determined on the vehicle side for the duration of the monitoring of the or each traffic disruption in the traffic center. So that the monitoring is not terminated too early - for example if the vehicle is traveling slower than estimated in the traffic control center - or too late - for example if the vehicle is traveling faster than estimated in the traffic control center - a destination arrival time T determined by the vehicle is used₀ sent wirelessly from the on-board device to the traffic control center. The vehicle-side then finds a continuous comparison of the stored destination arrival time T₀ with a currently determined arrival time T_A instead of. Differs the currently be^¬ agreed arrival time T_A from the stored destination arrival time To by more than a predeterminable threshold value X (for example X = 30 minutes), corresponding information is sent automatically or on request from the on-board device to the traffic control center and the stored destination arrival time T₀ with the currently determined arrival time T_A overwritten. Then a current arrival time T_A certainly. The currently determined arrival time T differs_A of the stored destination arrival time To not by more than the predeterminable threshold value X, a current arrival time T_A certainly .

006412 schematically illustrates the use of a route change location position with the change time of a calculated route. 12a schematically shows a dynamic route guidance from start position A to destination position D. There are two possible connections, namely from start position A via location position B to destination position D or alternatively from start position A via location positions B and C to destination position D. While the connection from location position B to destination position D has a shorter length than via location positions B and C to destination position D, a traffic disruption VS is occasionally located on the first alternative.

0065This traffic disruption VS leads to the travel time curve shown in FIG. 12b, which is designated RI for the first alternative and R2 for the second alternative and the time required in each case for the journey from location position B to destination position D at different arrival times on the route. change location position B. The temporary increase in travel time RI caused by the traffic disruption VS can be clearly seen. With an expected arrival time of the vehicle m B of t_E the connection is calculated in the traffic center via location positions B and C to destination position D as a route, since this is the time t_E is the fastest connection.

0066But if the vehicle now before the time t_mιn or after time t_maχ reaches position B, this calculated route is no longer the fastest. Therefore, the location position B is the route change location position with the change times t_mιn and t_Max transmitted from the traffic control center to the vehicle-side device. In addition, route-related data relating to the connection from location position B to destination position D can also be transmitted to the vehicle-side device. In this case, when the vehicle arrives at the route change location position B before t_mιn or after t_Max automated or on request to switch to the new route from location position B to destination position D. If corresponding route-related data for the alternative route at the route change location B is not available in the vehicle-side device , this route-related data is requested automatically or on request from the traffic control center.

0067Alternatively, as shown in FIG. 12 c, provision can be made for the vehicle to change the route only if the travel time is thereby reduced by at least a certain amount Δt. In this case, when the vehicle arrived at the route change location position B before t '_mιn or after t '_Max automated or changed to the new route from location position B to destination position D on request. This procedure is particularly suitable when the vehicle-side device has to request new, mostly fee-based route-related data from the traffic control center.

0068The use of route change location positions with change times of a calculated route is shown in FIG. 13. The example from FIG. 2 is used in FIG. 13, further calculations being carried out after FIG. 2f. In Fig. 2 routes R-_., i = l ... m calculated on which "relevant" traffic disturbances to be monitored^¬ stanchions. Now, according to parameters of a vehicle or driver, for example minimum and maximum average speeds to be assumed, each earliest point of a traffic disruption is an earliest arrival time t_raιnDriver and a latest arrival time t_{ma driver} assigned. These arrival times result, for example, from the minimum and maximum assumed average speed on the respective calculated route. A further calculation of a route is then carried out, in which the costs (for example travel time) for an edge k with a traffic disturbance to be monitored instead of the costs C_k(t_E) (where t_E the expected arrival time of the vehicle at edge k) the cost max (C_k(t)), te [t,_{mn driver}, t_{maX) driver}J can be used. In other words, the travel times are used in the "worst case". As the cost of the rest

0069Edges are used for free traffic costs. As long as a newly calculated route R_j differs from the previously calculated route R, all traffic disruptions on R_j marked as to be monitored and a further route is calculated. In FIG. 13 a, the traffic disruptions 1, 2, A and B have become larger than in FIG. 2, route R berechnet is calculated and traffic disorder 4 is additionally monitored. The traffic disorder 4 additionally marked as to be monitored is not transmitted from the traffic control center to the vehicle-side device sent.

0070Then all routes R, ≠ R_A (i = l ... m ... n) the

0071Location point P is determined as the route change location position, on the R, from the route "assuming an average speed" which is "optimal"_A branches off, and the location point Q is determined at which the two routes meet again. The range of possible arrival times [t_{mmι driver}, t_maxFalιrer J in the local point P is determined and the expected travel times from P to Q for departure in P between t_raι__rahrer and t_{ma driver} on the routes R_A and

0072R, are compared. If available, the latest time t_mm before the expected arrival time t_E determined in the location point P, at which the travel time between P and Q on route R, the corresponding travel time on R_A falls below by a predetermined amount. If available, the earliest time t_mx after t_E for whom this also applies. In Fig. 13b, the location points P and Q are on the route R_A marked and the route R₆. The travel times between P and Q on the routes R are shown by way of example in FIG. 13c₆ and R_A . A time t_mιn does not exist here because between t_mιn, ahrer and t_E the travel time on Re is always longer than on R_A.

007314 shows which data relating to route change location positions are transmitted from the traffic control center to the vehicle-side device. For each predetermined route change location positions P-_. (i = 1 ... n; Pj_. is further away from the starting point S than P-, for i> j) it is checked whether the associated arrival time falls below _-, _ (P,) or the arrival time t_ιnax(P,) can be exceeded if the vehicle does not have any of the arrival times t_mιn(PJtj <i falls below and none of the arrival times t_MaxPJ, j <i and neither an assumed minimum speed v_mιn falls below an assumed maximum speed v_Max exceeded. The arrival time t is only when this condition is met_mιn (P,) or t_ma(P,) transmitted to the vehicle, the coordinates of P, also not being transmitted if neither t_ιmn(P₁) still t_Max (P,) are to be transferred.

0074Referring to Fig. 14, the following t_m_n (Pι) and t_Max(P_) transferred: t_mιn(Pι) and t_Max(Pι) are in the range that with speeds between v_mιn and V_Max can be achieved and are thus transmitted. t_mιn(P₂), however, can no longer be undershot if the vehicle with v_Max drive and not before t_mιn(Pι) i-point Pi arrives. t_Max(P₂) can be maintained if t_maχ (Pι) and v_mιn not be exceeded. Therefore point P₂ not transferred to the vehicle. Point P₃ is transmitted because t_Max(P₃) could be exceeded, _mιn (P3) is not transmitted. Furthermore, it can be provided that traffic disruptions are only monitored in the traffic control center for as long as the vehicle while maintaining a minimally assumed speed and while maintaining the speed determined by the t_Max(P₁) set

0075Maximum time limits to the destination Z is on the way, whereby when recalculating the route the least traveled

0076Route on the originally calculated route assuming a minimum speed and compliance with the t_Max(P₁) is determined.