An Algorithm for the Euclidean Bounded Multiple Traveling Salesman Problem

In the Bounded Multiple Traveling Salesman Problem (BMTSP), a tour for each salesman that starts and ends at the depot and respects the bounds on the number of cities that a feasible salesman tour should satisfy is constructed. The objective is to minimize the total length of all tours. Already the Euclidean Traveling Salesman Problem is strongly NP-hard. Here, we propose a three-phase heuristic for the Euclidean BMTSP, which separates the partitioning, construction (routing), and improvement phases. At the partitioning phase, we construct k disjoint subsets through a minimum-distance vertex attachment process. The routing phase employs a convex-polygon-based construction procedure for the derived TSP instances. The improvement phase uses an iterative local search. We compare the performance of PCI-2 on the 22 existing benchmark instances and on the 168 newly generated instances with that of the ILP solver CPLEX and an Ant Colony Optimization algorithm. Computational results show that PCI-2 improves more than half of the previously best-known costs, including those of the largest benchmark instances. For the newly generated instances, PCI-2 produces lower-cost solutions than CPLEX in most cases and outperforms Ant Colony Optimization algorithm in 166 of the 168 instances.