| dc.description.abstract | The vehicle routing problem (VRP) is an important NP-complete combinatorial optimization problem, with many applications. This thesis presents a novel method for solving two-dimensional Euclidean VRPs based on a multi-agent model inspired by the slime mold Physarum polycephalum. The model consists of a large population of particles initialized around the depot, from where they spread across the environment. Each vehicle is represented by a different kind of particle. Each particle is attracted to cities and to other particles of its kind. A solution is generated by letting each population of particles cover a number of cities, in such a way that all cities are covered. The outline of each population then determines both which cities should be visited by which vehicle, as well as the tour that should be taken by that vehicle. By using the properties of the multi-agent Physarum material and a feedback system based on the cities covered by each population, valid VRP solutions can be generated. The model was tested with 8 different problem sets with different problem parameters, each problem set consisting of 20 different problems, and each problem being run 20 times. The problem sets varied in parameters from 2 vehicles on 10 cities with 6 capacity each, to 3 vehicles on 20 cities with 9 capacity each.
Performance was variable between problems and between problem sets, from solutions on average 23.6% longer than optimal on the former to at least 52.2% longer than optimal on the latter. Performance was generally superior on problem sets with fewer cities and larger capacities, compared to those with more cities, narrower capacity requirements, or both. The mechanics of solution formation are observed and discussed. While the model is not competitive in solution quality, it is nonetheless notable for its novel method of operation, consisting of complex behaviour from simple principles. Several techniques used may be of interest for improving or creating other multi-agent Physarum solvers. | |
