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

作者：Cote Jean Francois; Archetti Claudia; Speranza Maria Grazia; Gendreau Michel; Potvin Jean Yves^*

来源：Networks, 2012, 60(4): 212-226.

DOI：10.1002/net.21459

• traveling salesman
• pickup
• delivery
• loading
• multiple stacks

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-12