An Exact Framework for the Trigger Arc Traveling Salesman Problem

• Miguel Miní Unicamp
• Lucas de Oliveira Silva Unicamp
• Flávio K. Miyazawa Unicamp

DOI: https://doi.org/10.5753/etc.2026.23818

Resumo

The Trigger Arc Traveling Salesman Problem generalizes the classical TSP by introducing dynamically evolving arc costs that are modified upon traversal of designated “trigger” arcs. Thus, each arc’s cost is determined by the most recently traversed trigger arc that affects it, leading to an order-dependent cost. Such a structure makes an explicit modeling of trigger arcs computationally expensive, even for moderately sized instances. We propose an exact framework based on a standard MIP formulation of TSP, using classic rounding heuristics, together with a callback to separate trigger violations in candidate tours. Also, to control model size, we incorporate triggers progressively only as needed. The proposed approach solves several benchmark instances from the literature to optimality and achieves single-digit optimality gaps on a subset of larger instances.

Referências

Cerrone, C., Truvolo, M., Dragone, R., and Battaglia, R. (2025). The Trigger Arc TSP: Optimise the Picking Process in Warehouses with Compactable Storage Systems. In Decision Sciences. Springer.

Cook, W. J., Cunningham, W. H., Pulleyblank, W. R., and Schrijver, A. (2011). Combinatorial Optimization. Wiley.

Karp, R. M. (1979). A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem. SIAM Journal on Computing, 8(4):561–573.

Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.