New formulation and branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks: new formulation and branch-and-cut algorithm

In this paper, we consider the pickup and delivery traveling salesman problem with multiple stacks in which a single vehicle must serve a set of customer requests defined by a pair of pickup and delivery destinations of an item. The vehicle contains a fixed number of stacks, where each item is loaded at a pickup location and unloaded at the corresponding delivery location. Each stack has finite capacity, and its loading and unloading sequence must follow the last-in-first-out (LIFO) policy, that is, for each stack, just the last item loaded can be unloaded at its corresponding delivery location. We propose a new integer programming formulation for this problem with a polyhedral representation described by exponentially many inequalities and a branch-and-cut algorithm for solving the proposed formulation. Computational results show that our approach is competitive with the best algorithm in the literature. Also, three new certificates of optimality are provided and several optimality gaps are reduced.