ROAR: Restricted 2-Opt And Ruin-and-recreate Heuristic for Large and Extreme Scale Traveling Repairman Problem
Abstract
The Traveling Repairman Problem minimizes cumulative arrival times rather than the total route length, as in the classical Traveling Salesman Problem. The literature contains several legacy metaheuristics for the TRP; however, most are evaluated on small- and medium-scale instances and show limited scalability for large and extreme datasets. GILS-RVND, the current gold standard in metaheuristic algorithms, performs well on small and medium instances but struggles to scale due to the exhaustive neighborhood search in the RVND phase. To address this limitation, we introduce Restricted 2-Opt And Ruin-and-recreate (ROAR), a Large Neighborhood Search-based method that integrates ruin-and-recreate with greedy insertion and a restricted, insertion-anchored 2-opt operator. Computational experiments demonstrate that ROAR produces high-quality solutions for large-scale instances and outperforms existing methods under strict time limits. We further introduce an O(1)-time, O(1)-space algorithm for evaluating 2-opt moves during a contiguous systematic sweep, which, to the best of our knowledge, is unprecedented. Finally, we evaluate ROAR on instances with up to 200,000 nodes, substantially exceeding the largest instances previously reported in the literature (11,849 nodes).
Related
- On the Segment-Based Remove-and-Reinsert Heuristic for the Generalized Traveling Salesman Problem
- A Parallel Heuristic for the Fixed Cardinality Binary Quadratic Program
- A Ceiling Continued Fraction Approach to the Erdős-Straus Conjecture: Heuristic finiteness of counterexamples
- New binary optimal LCD codes using heuristic embedding
- A Frank-Wolfe-based primal heuristic for quadratic mixed-integer optimization
BibTeX
@misc{nguyen2026roar,
title = {{ROAR: Restricted 2-Opt And Ruin-and-recreate Heuristic for Large and Extreme Scale Traveling Repairman Problem}},
author = {Khoa Hoang Dang Nguyen and Nam Khoa Pham and Khanh Dinh Nam Nguyen and Bac Ba Thanh Nguyen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.37128},
eprint = {2610.37128},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.37128},
}
RIS
TY - UNPB
TI - ROAR: Restricted 2-Opt And Ruin-and-recreate Heuristic for Large and Extreme Scale Traveling Repairman Problem
AU - Khoa Hoang Dang Nguyen
AU - Nam Khoa Pham
AU - Khanh Dinh Nam Nguyen
AU - Bac Ba Thanh Nguyen
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.37128
UR - https://arxiv.org/abs/2610.37128
AB - The Traveling Repairman Problem minimizes cumulative arrival times rather than the total route length, as in the classical Traveling Salesman Problem. The literature contains several legacy metaheuristics for the TRP; however, most are evaluated on small- and medium-scale instances and show limited scalability for large and extreme datasets. GILS-RVND, the current gold standard in metaheuristic algorithms, performs well on small and medium instances but struggles to scale due to the exhaustive neighborhood search in the RVND phase. To address this limitation, we introduce Restricted 2-Opt And Ruin-and-recreate (ROAR), a Large Neighborhood Search-based method that integrates ruin-and-recreate with greedy insertion and a restricted, insertion-anchored 2-opt operator. Computational experiments demonstrate that ROAR produces high-quality solutions for large-scale instances and outperforms existing methods under strict time limits. We further introduce an O(1)-time, O(1)-space algorithm for evaluating 2-opt moves during a contiguous systematic sweep, which, to the best of our knowledge, is unprecedented. Finally, we evaluate ROAR on instances with up to 200,000 nodes, substantially exceeding the largest instances previously reported in the literature (11,849 nodes).
ER -