The Trigger Arc Travelling Salesman Problem (TATSP) is an innovative variant of the classical Travelling Salesman Problem (TSP) that models scenarios in which edge costs dynamically change depending on the path taken. This new formulation has been developed with a real-world application in mind: optimizing picking operations in warehouses equipped with compactable storage systems.

The Trigger Arc TSP opens new perspectives in advanced logistics and industrial robotics, providing an optimized framework for managing intelligent movements in automated warehouses.

The Trigger Arc TSP Problem

In the TATSP, the cost of each edge may vary depending on the edges already traversed during the tour. In other words, some edges act as triggers, modifying the cost of other edges, making the problem particularly suitable for modeling logistics and transportation contexts with dynamic constraints.

We mathematically formulated the problem using an Integer Linear Programming (ILP) model and developed a computational implementation to solve it.

Application in Warehouses with Mobile Shelving Systems

The case study used to test our model concerns warehouses with mobile shelving systems, where the movement of a group of shelves can modify the accessibility configuration of other aisles. This scenario has strong implications in terms of:

• Operational efficiency, by reducing overall picking time
• Energy optimization, by minimizing the number of movements of compactable shelves
• Reduction of handling costs, thanks to an optimized routing strategy

Computational Results

We tested our model on a set of artificially generated instances and demonstrated that the proposed algorithm significantly reduces the overall tour cost compared to the traditional TSP, thanks to the strategic use of trigger edges.

However, the problem proves to be computationally challenging for large-scale instances, making the application of heuristic and metaheuristic techniques particularly relevant for solving it at scale.

For further details, consult the full publication:
https://link.springer.com/chapter/10.1007/978-3-031-78238-1_26