Dynamic Routing using Ant-Based Control

Currently most car drivers use static routing algorithms based on the shortest distance between start and end position. But the shortest route is different from the fastest route in time. Because existing routing algorithms lack the ability to react to dynamic changes in the road network, drivers are not optimally routed. In this thesis we present a multi-agent approach for routing vehicle drivers using historically-based traffic information. The general workings of our solution bears strong similarities with Ant Based Control (ABC) and AntNet, but an important modification has been made, namely the adaptation of ant-like agents for spatio-temporal routing. The dynamic routing algorithm proposed, routes self-interested drivers on an intersection to intersection basis via the fastest path between a proposed source and a destination. For this to happen, a time-expanded graph encodes variable road network costs. Ant-like agents are launched in this graph. They use a technique of collective learning based on locally dependent pheromone tables. Finally, we report results obtained for part of The Netherlands' GIS-based road network. In the established experiment setting, the new ABC makes a positive difference for drivers. An important reduction of the travelling time was observed in 53% of the cases. The experimental results also showed that ABC clearly outperforms Static Dijkstra's algorithm and Dynamic Dijkstra with updates.

Subject

Ant Based Control
ABC
Dynamic
Routing

To reference this document use:

http://resolver.tudelft.nl/uuid:cfe2d030-8232-4306-b267-38959f504908

Embargo date

2010-08-25

Part of collection

Student theses

Document type

master thesis

Rights

Files

PDF

MSc.pdf

10.86 MB

Close viewer