Dynamic vehicle routing using Ant Based Control


Static route planners are widely available. But real-time navigation systems that provide optimal routes based on dynamic traffic information on highways and in cities do not yet exist. However, a great profit could be taken from such a system, looking at the amount of daily congestions. On highways, road sensors are capable of gathering a great deal of information about the traffic flow. But in cities such data is not available.
In this project we have explored the use of Ant Based Control for dynamic vehicle routing in a city .This approach is based on the behaviour of ants in nature. Ants lay a chemical track (pheromones) to find the shortest route from their nest to a food source. To find their way ants choose the track with highest concentration. Intelligent software agents imitate this behaviours of the natural ants. To collect real-time traffic information we assume that individual cardrivers send their position and followed route to a central system at regular times. GPS and GMS/GPRS are used for positioning and communication to a central system. These two components are combined in a routing system that provides car drivers with the shortest route from A to B.
Before this routing system can be implemented in the real world, it has to be thoroughly tested. For this purpose a simulation environment has been created (see demo), in which traffic in a city can be simulated. The vehicles in the simulation are placed in a realistic situation where they have to deal with matters like traffic lights and precedence rules and roundabouts, and driving on one lane, multi-lane or one-way roads. They provide dynamic data to the routing system by sending their position at regular times. This information is translated by the routing system in travel time estimates. With the aid of these travel times new shortest routes are computed. These routes are sent to the vehicles for navigation. The routing system has proven to be effective in finding good paths, avoiding congestions and roadblocks. The routing system allows for future extensions with even wider applications.
The application that simulates the above mentioned algorithms can be downloaded here. The zipped archive contains two Win32 executables and some example data with several road networks.
Powerpoint presentation of the project can be downloaded here.
blue line