Dynamic vehicle routing using ant based control

title: Dynamic vehicle routing using ant based control
author: Ronald Kroon
published in: May 2002
appeared as: Master of Science thesis
Delft University of Technology
pages 131
PDF (4.657 KB)


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 thesis 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. Intelligent software agents imitate some of the behaviours of the natural ants. Two improvements have been made to earlier versions of the Ant Based Control algorithm. Furthermore we have looked at the possibilities for collecting real-time traffic information from individual vehicles. We have chosen for an approach, which uses GPS and GMS/GPRS 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, 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.

blue line
University logo