Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 50 min ago
Peer-reviewedCC BY 4.0Mathematics

On the Segment-Based Remove-and-Reinsert Heuristic for the Generalized Traveling Salesman Problem

  • Aljaž Krpan1,2
  • Janez Žerovnik1,3
  1. 1Rudolfovo-Science and Technology Centre Novo mesto, Podbreznik 15, 8000 Novo mesto, Slovenia
  2. 2Faculty of Mathematics and Physics, University of Ljubljana, 1000 Ljubljana, Slovenia
  3. 3Faculty of Mechanical Engineering, University of Ljubljana, Aškerčeva 6, 1000 Ljubljana, Slovenia
Open at sourceDOICite

Abstract

Randomized arbitrary insertion (RAI), a well-known heuristic for the traveling salesman problem, is applied to the generalized traveling salesman problem (GTSP). The adaptation of the basic idea to the GTSP leads to eight variants of the basic heuristic. These basic constructive heuristics are followed by the iterative improvement phase, in which segments of the current tour are randomly selected, removed, and reinserted back into the solution using RAI. Experiments show that one of the variants of our heuristic, on average, provides solutions that are less than 1.2% above the best-known solution based on standard libraries of benchmark instances including GTSP, MOM and BAF libraries. Although this does not match the performance of the best state-of-the-art solvers, the 1.2% threshold is a surprisingly good achievement taking into account the conceptual simplicity of the heuristic.

Related

  1. Exact cost of the Euclidean Maximum Traveling Salesman Problem in one dimension
    Sergio Caracciolo, Carlo Vanoni
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsMathematical physicsarXiv
  2. Traveling Salesman Problem on Graphs with Proportional Independent Set
    Ethan X. Fang, Shengtao Guo, Junwei Lu +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Collaborative Attention Ant Colony Optimization for Large-Scale Traveling Salesman Problems
    Kexin Zhang, Shubin Liu, Xinyuan Zhang +1
    MathematicsPeer-reviewedCC BY 4.0General mathematicsCrossref
  4. Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment
    Sophia Heimann, Hung P. Hoang, Stefan Hougardy
    arXivPreprintCC BY-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Optimal Service Commitments in Traveling Salesman Problems with Stochastic Demand
    Lina Schmidt, Julian Golak, Arne Schulz +1
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@article{krpan2026segmentbased,
  title = {{On the Segment-Based Remove-and-Reinsert Heuristic for the Generalized Traveling Salesman Problem}},
  author = {Aljaž Krpan and Janez Žerovnik},
  journal = {Mathematics},
  year = {2026},
  month = oct,
  doi = {10.3390/math14203667},
  url = {https://www.mdpi.com/2227-7390/14/20/3667},
  note = {CC BY 4.0},
}
RIS
TY  - JOUR
TI  - On the Segment-Based Remove-and-Reinsert Heuristic for the Generalized Traveling Salesman Problem
AU  - Aljaž Krpan
AU  - Janez Žerovnik
PY  - 2026
DA  - 2026/10/10
JO  - Mathematics
DO  - 10.3390/math14203667
UR  - https://www.mdpi.com/2227-7390/14/20/3667
AB  - Randomized arbitrary insertion (RAI), a well-known heuristic for the traveling salesman problem, is applied to the generalized traveling salesman problem (GTSP). The adaptation of the basic idea to the GTSP leads to eight variants of the basic heuristic. These basic constructive heuristics are followed by the iterative improvement phase, in which segments of the current tour are randomly selected, removed, and reinserted back into the solution using RAI. Experiments show that one of the variants of our heuristic, on average, provides solutions that are less than 1.2% above the best-known solution based on standard libraries of benchmark instances including GTSP, MOM and BAF libraries. Although this does not match the performance of the best state-of-the-art solvers, the 1.2% threshold is a surprisingly good achievement taking into account the conceptual simplicity of the heuristic.
SN  - 2227-7390
ER  -