CARAVAN: Congestion avoidance and route allocation using virtual agent negotiation

Traffic congestion becomes a cascading phenomenon when vehicles from a road segment chaotically spill on to successive road segments. Such uncontrolled dispersion of vehicles can be avoided by evenly distributing vehicles along alternative routes. This paper proposes a practical multiagent-based approach, which is designed to achieve acceptable route allocation within a short time frame and with low communication overheads. In the proposed approach, which is called Congestion Avoidance and Route Allocation using Virtual Agent Negotiation (CARAVAN), vehicle agents (VAs) in the local vicinity communicate with each other before designated decision points (junctions) along their route. Cooperative route-allocation decisions are performed at these junctions. VAs use intervehicular communication to propagate key traffic information and undertake its distributed processing. Every VA exchanges its autonomously calculated route preference information to arrive at an initial allocation of routes. The allocation is improved using a number of successive virtual negotiation 'deals.' The virtual nature of these deals requires no physical communication and, thereby, reduces communication requirements. In addition to the theory and concept, this paper presents the design and implementation methodology of CARAVAN, including experimental results for synthetic and real-world road networks. Results show that when compared against the shortest path algorithm for travel time improvements, CARAVAN offers 21%-43% gain (when traffic demand is below network capacity) and 13%-17% gain (when traffic demand exceeds network capacity), demonstrating its ability to regulate overall system traffic using local coordination strategies.