This article studies the pickup and delivery traveling salesman problem with multiple stacks. The vehicle contains a number of (horizontal) stacks of finite capacity for loading items from the rear of the vehicle. Each stack must satisfy the last-in-first-out constraint that states that any new item must be loaded on top of a stack and any unloaded item must be on top of its stack. A branch-and-cut algorithm is proposed for solving this problem. Computational results are reported on different types of randomly generated instances as well as on classical instances for some well-known special cases of the problem. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012 © 2012 Wiley Periodicals, Inc.
['Jean-François Côté', 'Claudia Archetti', 'Maria Grazia Speranza', 'Michel Gendreau', 'Jean-Yves Potvin']
A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks