A simulation system for hierarchical routing using Ant Based Control

title: A simulation system for hierarchical routing using Ant Based Control
author: Rui Li
published in: July 2004
appeared as: Master of Science thesis
Knowledge Based Systems group
Delft University of Technology
PDF (5.032 KB)

Abstract

In modern society, traffic congestion is a tough problem for many countries all over the world. Governments employ many kinds of approaches to mitigate the traffic jam. They build broader roads, establish more reasonable traffic rules and engage more managers.
Dynamic routing is an efficient way to reduce traffic congestions. Based on different routing problems, variant routing algorithms are developed. The Ant Based Control algorithm (ABC-algorithm) is a promising approach among them. This algorithm is developed from the principles that ants use to find food in the nature, and it is especially suited to find solutions to difficult discrete optimization problems where the dynamic data changes very fast. It introduces intelligent agents (artificial ants) to explore the traffic network and find the optimal route in time.
But when traffic networks become more and more complex, the Ant Based Control routing shows poor performance. To improve the efficiency of a routing system based on ABC-algorithm, we propose hierarchical routing. The hierarchical routing is mainly devised to reduce memory requirements of simulations over very large topologies. In this approach, a complex traffic network is broken down into several layers of networks: one abstract level network and several detailed level networks. The hierarchical routing system therefore consists of some distributed routing systems where each of them is responsible for one network of the hierarchical network. And each distributed routing system needs less information to perform routing.
We develop a software prototype – a hierarchical routing simulation system. The system is based on the Ant Based Control algorithm. We deliver some experiments on the system, and get excellent results presenting high stability, efficiency and robustness. Thus we conclude that the system is capable of routing vehicles in real time, even in very complex traffic network.

 
blue line
University logo