Destination-Oriented Route Construction for Ant Colony Optimization to Solve MinMax Multiple Travelling Salesmen Problems

This paper proposes a destination-oriented route construction method (DORC) for ant colony optimization (ACO) to effectively solve minmax multiple traveling salesmen problems (MTSP) with multiple depots. Unlike existing studies, DORC first determines the destination for each salesman before building his route. Then, it constructs the routes for all salesmen by integrating the information of the current visiting city and the destination. In this way, the selection of cities for all salesmen is directional toward the destination. Therefore, DORC expectedly helps ACO build promising routes for all salesmen. Thereafter, this paper embeds DORC into the five classical ACO algorithms, namely ant system (AS), elite AS (EAS), max-min AS (MMAS), rank-based AS (RAS), and ant colony system (ACS) to solve MTSP. Experiments conducted on MTSP instances with different numbers of cities and different numbers of salesmen demonstrate that DORC helps the five ACO algorithms achieve much better performance. Particularly, the experimental results reveal that the helpfulness of DORC is more significant for the five ACOs in solving large-scale MTSP with a large number of cities and a large number of salesmen.