The route planner of Siemens VDO plans routes from the current car position to destinations specified by the driver. For this planning the actual road network is used with for each road segment the standard driving speed. However, using only one speed for a road segment is not realistic. For example, during rush hours the speed at a certain road, segment will be lower than during the rest of the day. A special form of varying speeds for road segments are caused by traffic congestions. Traffic congestions cause the speed at a road segment to \Iary with time and most of the time the future development of a congestion is not known. The main objective of this research is to "find planning and monitoring algorithms which can deal effectively with long range, time dependent traffic information within the framework available in the VDO navigation systems". One of the requirements is that the algorithm should be fast enough, since a driver does not want to wait long before a route is presented. Finding an algorithm is important since otherwise a seemingly good route planned using the standard speeds can in reality be bad because a traffic congestion is present. Taking the congestion into account could have led to a route only slightly worse than the route in case of no congestions but much better than that same route with the congestion. First, the different types of minimum cost path problems are investigated. Mathematical models are given and (the lack of) algorithms to solve the minimum cost path problems are discussed. No effective algorithms for minimum cost paths in road networks with congestions are known. Only if the future development of congestions would be known a good route could be planned. Since no effective algorithms are known, an algorithm is examined by means of simulation. The current way of taking congestions into account is neglecting all congestions more than 150 km. away from the car. This strategy is compared with an alternative strategy, which lets the influence of a congestion decrease in a non linear way as the distance between the car and the congestion increases. Since most of the times detours are planned locally, it should be investigated what happens if all roads near the congestion are also assumed to be infected by the congestion. The consequences of the increase in certainty of the course of the congestion as new (updated) information is provided should also be investigated. In this research, a general model of the expected course of the congestion is used. It is probably beneficial to investigate the courses of certain groups of similar congestions (single car accident, open bridge, tumbled truck etcetera), and to define an expected course for each of these groups. Based on the fact that most of the detours planned are local, and are only found after a number of replannings, it is interesting to check the quality of the routes planned in case the search level at the area around the congestion is manually set to a greater detail. (Author/publisher)
Abstract