Large neighborhood search for the pickup and delivery traveling salesman problem with multiple stacks

This article studies a single vehicle pickup and delivery problem with loading constraints. In this problem, the vehicle contains a number of (horizontal) stacks of finite capacity for loading items from the rear of the vehicle. Each stack must satisfy a last-in-first-out constraint where any new item must be loaded on top of a stack and any unloaded item must be on top of its stack. A large neighborhood search is proposed for solving this problem. Computational results are reported on different types of randomly generated instances. Results are also reported on benchmark instances for two special cases of our problem and a comparison is provided with state-of-the-art methods. (c) 2012 Wiley Periodicals, Inc. NETWORKS, 2012