Formulations and algorithms for the Pickup and Delivery Traveling Salesman Problem with Multiple Stacks

In the Pickup and Delivery Traveling Salesman Problem with Multiple Stacks, one vehicle must fulfill a set of pickup and delivery requests. While being transported, items are stored in stacks with limited capacity. Each stack must follow the Last-In-First-Out policy. The objective of the problem is to find a vehicle route that fulfills all requests and minimizes traveled distance. In this paper, we propose new integer programming formulations to the problem along with ad hoc branch-and-cut algorithms and valid inequalities. The formulations and algorithms are applied to benchmark instances and the computational results are compared with the literature. Instances for which an optimal solution was previously known in the literature are solved more efficiently in this work. Also, new optimality certificates are provided for seven instances.