Ant colony based dynamic voronoi method for the multi-depot multiple TSP

Abstract

This paper introduces a novel approach to solving the Multi-Depot Multiple Traveling Salesman Problem (MDMTSP), an extension of the classic Traveling Salesman Problem (TSP) characterized by multiple salesmen operating from various depots. The MDMTSP is particularly relevant in practical scenarios such as logistics and distribution, where efficient routing is crucial. Our approach integrates the Ant Colony System (ACS) with dynamically updated Voronoi regions, offering an innovative method to efficiently organize the assign-ment and routing of salesmen. This method not only optimizes the salesmen's routes but also ensures an efficient distribution of workload among them, leading to overall reduced travel distances. Experimental results demonstrate the effectiveness of our approach, highlighting significant improvements in route optimization compared to other existing methods.