EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

An Algorithm for the Euclidean Bounded Multiple Traveling Salesman Problem

Víctor Pacheco-Valencia, Nodari Vakhania, Federico Alonso-Pecina, José Alberto Hernández-Aguilar

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →