A Lexi-Search Algorithm for Double Traveling Salesman Problem with Multiple Stacks with LIFO

The double traveling salesman problem with multiple stacks is a variant of the pickup and delivery traveling salesman problem in which all pickups must be completed before any of the deliveries. In addition, items can be loaded on multiple stacks in the vehicle and each stack must obey the last-in-first-out policy. The problem consists in finding the shortest Hamiltonian cycles covering all pickup and delivery locations while ensuring the feasibility of the loading plan. We formulate the problem as two traveling salesman problems linked by infeasible path constraints. We also introduce several strengthening of these constraints which are used within a Lexi-Search algorithm.