EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Using Randomized Heuristics and Regression to Estimate the Close Enough TSP Optimal Tour Length

Hugo Mainguy, Bruce Golden, Luca Bertazzi, Debdatta Sinha Roy

Algorithms · 23.10.2026 · 19 (11) · 911

DOI: 10.3390/a19110911 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Algorithms, online erschienen am 23.10.2026. Verfasst von Hugo Mainguy und 3 weiteren Autor:innen. Die Arbeit nennt 22 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In the Close Enough Traveling Salesman Problem (CETSP), one must find the shortest tour that travels through every given customer-centered neighborhood, which is usually a disk centered on each customer or target. This problem has applications in various fields, such as radio frequency identification (RFID), mission planning for Unmanned Aerial Vehicles (UAVs), multi-visit drone routing, and aerial route reconnaissance planning. In this study, we combine prior work on CETSP estimation models and on using results from a randomized heuristic on combinatorial optimization problems such as the TSP, VRP, Split Delivery VRP (SDVRP), and the Knapsack Problem in order to obtain high-quality optimal solution value estimates efficiently. Here, we use discretization heuristics based on the Generalized TSP (GTSP) and merging nodes in Steiner zones. With our regression-based approach, we are able to obtain estimates on instances that would otherwise take hours to solve to optimality. We obtain an MAPE of 0.56% on a set of 780 CETSP instances, handily improving on similar predictor-based approaches that did not use heuristics, and we compute accurate estimates for instances that take much longer to solve or even approximate. We are motivated to contribute to this research stream in order to show that we can obtain excellent optimal solution value estimates to a wide variety of hard combinatorial optimization problems.

Zitieren

APA

Mainguy, H., Golden, B., Bertazzi, L., & Roy, D. S. (2026). Using Randomized Heuristics and Regression to Estimate the Close Enough TSP Optimal Tour Length. Algorithms, 19(11), 911. https://doi.org/10.3390/a19110911

Vancouver

Mainguy H, Golden B, Bertazzi L, Roy DS. Using Randomized Heuristics and Regression to Estimate the Close Enough TSP Optimal Tour Length. Algorithms. 2026;19(11):911. doi:10.3390/a19110911

BibTeX
@article{Mainguy2026,
  author = {Mainguy, Hugo and Golden, Bruce and Bertazzi, Luca and Roy, Debdatta Sinha},
  title = {Using Randomized Heuristics and Regression to Estimate the Close Enough TSP Optimal Tour Length},
  journal = {Algorithms},
  year = {2026},
  volume = {19},
  number = {11},
  pages = {911},
  doi = {10.3390/a19110911}
}
Kostenlos starten →