Autonomous Units for Solving the Capacitated Vehicle Routing Problem Based on Ant Colony Optimization

Abstract

Communities of autonomous units and ant colony systems have fundamental features in common. Both consists of a set of autonomously acting units that transform and move around a common environment that is usually a graph. In contrast to ant colony systems, the actions of autonomous units are specified by graph transformation rules which have a precisely defined operational semantics and can be visualized in a straightforward way. In this paper, we model an ant colony system solving the capacitated vehicle routing problem as a community of autonomous units. The presented case study shows that the main characteristics of ant colony systems such as tour construction and pheromone updates can be captured in a natural way by autonomous units.