Elitist ant system for route allocation problem

Abstract

As Multi-Agent Systems (MAS) have gained their place in the artificial intelligence field by proving their effectiveness in solving optimisation problems, this paper presents a new approach for a hard and well-known problem: vehicle route allocation. After a brief introduction about the MAS and stigmergy in section one, the paper presents the rationale (section two) where Ant Colony Optimisation (ACO) and its common extensions such as Elitist Ant System (EAS), Max-Min Ant System (MMAS), Rank-Based Ant System (ASrank) and others are described, and the approach (section three) where the reasons for choosing EAS as starting algorithm and the steps that must be followed in order to adapt EAS for solving the Route Allocation Problem (RAP) are presented. The resulted algorithm is depicted in section four. The paper concludes that the approach proved to be workable on usual configurations and effective in dealing with combinatorial explosion usually encountered in optimisation problems.