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

arXiv: https://arxiv.org/abs/2508.08477 · HTML: https://mlsanity.com/paper/2508.08477/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 18 references that are in the map.
- First posted on arXiv 11 Aug 2025.

## Builds on (most cited first, 1 of 1)

- [The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics](https://mlsanity.com/paper/2002.01070/) (2020)

## Abstract (arXiv)

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.