Valid inequalities and branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks

The focus of this work is the study of valid inequalities and exact algorithms for the pickup and delivery traveling salesman problem with multiple stacks. In the problem, a single vehicle must fulfill a set of client requests. Each request states that the vehicle must pick up an item at a given location, and later deliver it to another particular location. Inside the vehicle, items are stored in horizontal stacks of limited capacity. The loading and unloading operations of items follow the last-in-first-out policy. Every item is picked up on top of a stack and can only be delivered if it is also on top of its stack. The goal of this problem is to find a vehicle route of minimum cost. We propose a new formulation along with new valid inequalities for the problem. Several of these valid inequalities are lifted versions of inequalities previously proposed in the literature. The branch-and-cut algorithm based on the formulation and the valid inequalities is compared with the state-of-the-art solution methods for the problem. Computational experiments performed on benchmark instances show that the implemented algorithm outperforms all other competing exact algorithms for this problem.