
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.