A Fast GRASP Metaheuristic for the Trigger Arc TSP with MIP-Based Construction and Multi-Neighborhood Local Search

Joan Salvà Soler, Grégoire de Lambertye
8/11/2025
cs.AIcs.DM

No confident code implementation found for this paper.

Abstract

The Trigger Arc Traveling Salesman Problem (TA-TSP) extends the classical TSP by introducing dynamic arc costs that change when specific "trigger" arcs are traversed, modeling scenarios such as warehouse operations with compactable storage systems. This paper introduces a GRASP-based metaheuristic that combines multiple construction heuristics with a multi-neighborhood local search. The construction phase uses mixed-integer programming (MIP) techniques to transform the TA-TSP into a sequence of tailored TSP instances, while the improvement phase applies 2-Opt, Swap, and Relocate operators. Computational experiments on MESS 2024 competition instances achieved average optimality gaps of 0.77% and 0.40% relative to the best-known solutions within a 60-second limit. On smaller, synthetically generated datasets, the method produced solutions 11.3% better than the Gurobi solver under the same time constraints. The algorithm finished in the top three at MESS 2024, demonstrating its suitability for real-time routing applications with state-dependent travel costs.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

FMT$^{x}$: An Efficient and Asymptotically Optimal Extension of the Fast Marching Tree for Dynamic Replanning

78% match2025

A Random-Key Optimizer for Combinatorial Optimization

78% match2024

Large Neighborhood Prioritized Search for Combinatorial Optimization with Answer Set Programming

77% match2024

A Multi-population Integrated Approach for Capacitated Location Routing

77% match2024

cuGenOpt: A GPU-Accelerated General-Purpose Metaheuristic Framework for Combinatorial Optimization

76% match1 repo492026

An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem

76% match2024

Cite this paper

@article{soler2025fast,
  title  = {A Fast GRASP Metaheuristic for the Trigger Arc TSP with MIP-Based Construction and Multi-Neighborhood Local Search},
  author = {Joan Salvà Soler and Grégoire de Lambertye},
  year   = {2025},
  eprint = {2508.08477},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2508.08477v3}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2508.08477.svg)](https://codeofpaper.com/paper/2508.08477)

Discussion