An Algorithm for the Euclidean Bounded Multiple Traveling Salesman Problem
Mathematics · 08.07.2026 · 14 (14) · 2464
DOI: 10.3390/math14142464 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics, online erschienen am 08.07.2026. Verfasst von Víctor Pacheco-Valencia und 3 weiteren Autor:innen. Die Arbeit nennt 80 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: SECIHTI-Mexico.
Abstract (Originalsprache)
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.
Förderung
- SECIHTI-Mexico
Zitieren
APA
Pacheco-Valencia, V., Vakhania, N., Alonso-Pecina, F., & Hernández-Aguilar, J. A. (2026). An Algorithm for the Euclidean Bounded Multiple Traveling Salesman Problem. Mathematics, 14(14), 2464. https://doi.org/10.3390/math14142464
Vancouver
Pacheco-Valencia V, Vakhania N, Alonso-Pecina F, Hernández-Aguilar JA. An Algorithm for the Euclidean Bounded Multiple Traveling Salesman Problem. Mathematics. 2026;14(14):2464. doi:10.3390/math14142464
BibTeX
@article{PachecoValencia2026,
author = {Pacheco-Valencia, Víctor and Vakhania, Nodari and Alonso-Pecina, Federico and Hernández-Aguilar, José Alberto},
title = {An Algorithm for the Euclidean Bounded Multiple Traveling Salesman Problem},
journal = {Mathematics},
year = {2026},
volume = {14},
number = {14},
pages = {2464},
doi = {10.3390/math14142464}
}
EUVIMED