An Integration of Multiple Heuristics for Multi-Depot Multiple Traveling Salesman Problems

Abstract

This paper addresses the multi-depot multiple traveling salesman problem (MDMTSP), a complex combinatorial optimization problem with significant real-world applications in logistics and transportation. A permutation-based representation is proposed to encode candidate solutions, where salesman routes are generated by partitioning the permutation according to dynamic city assignments. To enhance local search capability, an Exchange Operation (EO) and a K-opt Operation (KOO) are incorporated as fundamental neighborhood operators. Building on these operators, three well-known metaheuristics-Artificial Bee Colony (ABC), Genetic Algorithm (GA), and Differential Evolution (DE)-are systematically adapted for the MDMTSP. Specifically, ABC is redesigned using EO and KOO, GA is modified with cyclic crossover and KOO-based mutation, and DE is reconstructed by integrating EO, KOO, and cyclic crossover mechanisms. To exploit the complementary strengths of these algorithms, a two-phase hyperheuristic framework, termed ABC-DE-GA, is proposed. In the first phase, ABC, DE, and GA are executed independently to explore diverse regions of the search space and identify promising solution zones. In the second phase, the best solution obtained is iteratively refined by cyclically applying all three heuristics until convergence stagnates. Extensive experiments conducted on benchmark instances from TSPLIB, along with rigorous statistical analysis, demonstrate that the proposed ABC-DE-GA framework consistently outperforms state-of-the-art methods in terms of solution quality, robustness, and convergence efficiency.