Modified Ant Colony Optimization Algorithm for Multiple-vehicle Traveling Salesman Problems

DOI

10.2991/ijndc.2018.7.1.4How to use a DOI?

Keywords

Multiple-vehicle traveling salesmen problem; ant system; local search; simulated annealing; 2-opt; 3-opt

Abstract

In this work, we extended the original Traveling Salesman Problem (TSP) to cover not only the case of multiple vehicles but also to constrain the minimum and maximum numbers of cities each vehicle can visit. Our algorithm is a modified Ant Colony Optimization (ACO) algorithm which has the ability to avoid local optima; our algorithm can be applied to transportation problem that covers either a single vehicle or multiple vehicles. To the original ACO, we added a new reproduction method, a new pheromone updating strategy, and four improved local search strategies. We tested our algorithm on several standard datasets in the TSP library. Its single-vehicle performance was compared to that of ant system (AS) and elitist ant system (EAS) algorithms. Its multiple-vehicle performance was evaluated against that of ant colony system variants reported in the literature. The experiments show that our proposed ACO’s single-vehicle performance was superior to that of AS and EAS on every tested dataset and its multiple-vehicle performance was excellent.

Copyright

© 2018 The Authors. Published by Atlantis Press SARL.

Open Access

This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

Download article (PDF)
View full text (HTML)

TY  - JOUR
AU  - Yindee Oonsrikaw
AU  - Arit Thammano
PY  - 2018
DA  - 2018/12/31
TI  - Modified Ant Colony Optimization Algorithm for Multiple-vehicle Traveling Salesman Problems
JO  - International Journal of Networked and Distributed Computing
SP  - 29
EP  - 36
VL  - 7
IS  - 1
SN  - 2211-7946
UR  - https://doi.org/10.2991/ijndc.2018.7.1.4
DO  - 10.2991/ijndc.2018.7.1.4
ID  - Oonsrikaw2018
ER  -