|title:||Hierarchical routing system using ant based control|
|published in:||July 2003|
Master of Science thesis
Dresden University of Technology, Germany Faculty of Computer Science
|PDF (2.465 KB)|
Nowadays traffic jams and slow-moving traffic are a big problem in many countries. Every day during the rush hours many streets are congested what results in big economic and environmental damages. Different approaches are followed to solve the problem. One way is the development of dynamic routing systems which use dynamic information about the traffic conditions on the streets to route vehicle on alternative ways around congestions. By that the road capacity is exploited in a more optimal way and congestions can be reduced.
In this thesis the design of a dynamic routing system, called Hierarchical routing system, has been developed which follows a new approach. It splits traffic networks into several smaller and less complex networks by introducing a hierarchy. The Hierarchical routing system therefore is designed to be a distributed routing system which consists of several parts where each of it is responsible for one network of the hierarchical network.
The route optimization is done with the ABC-algorithm, a decentralized routing algorithm, which uses intelligent agents which explore the network and find the shortest routes in time. This algorithm was derived from the behaviour of ants in nature. For the application in a hierarchical network the ABC-algorithm has been adapted. The concept of virtual nodes and time columns has been added and time agents have been introduced. Routes, which start in one network of the hierarchical network and end in another network, are computed as composed route out of several routes. An algorithm has been developed that computes the composed routes with the cooperation of the distributed parts of the Hierarchical routing system.
For collecting real time traffic information the vehicles themselves are used. They record the route they follow together with the needed time and send it at regular intervals to the Hierarchical routing system. That information is used to compute travel time estimates from intersection to intersection for every street of the network.
The concept of hierarchical routing combined with the ABC-algorithm ensures an excellent scalability of the routing system. By that the system should be capable of routing vehicles in real time even in very complex networks. Besides, the design of the Hierarchical routing system ensures a high robustness against failures of parts of the distributed system.