A Fast GRASP Metaheuristic for the Trigger Arc TSP with MIP-Based Construction and Multi-Neighborhood Local Search
This work addresses real-time routing applications with state-dependent travel costs, such as warehouse operations, but is incremental as it builds on existing TSP and metaheuristic methods.
The paper tackled the Trigger Arc Traveling Salesman Problem (TA-TSP), which models dynamic arc costs in scenarios like warehouse operations, by developing a GRASP-based metaheuristic that achieved average optimality gaps of 0.77% and 0.40% on competition instances and solutions 11.3% better than Gurobi on synthetic datasets within time limits.
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.