Article ID: | iaor20105929 |
Volume: | 17 |
Issue: | 5 |
Start Page Number: | 637 |
End Page Number: | 652 |
Publication Date: | Sep 2010 |
Journal: | International Transactions in Operational Research |
Authors: | Ryan David, Ehrgott Matthias, Larsen Jesper, Lusby Richard M |
Keywords: | distribution, vehicle routing & scheduling |
The double travelling salesman problem (TSP) with multiple stacks (DTSPMS) is a pickup and delivery problem in which all pickups must be completed before any deliveries can be made. The problem originates from a real-life application where a 40-foot container (configured as 11 rows of three columns) is used to transport 33 pallets from a set of pickup customers to a set of delivery customers. The pickups and deliveries are performed in two separate trips, where each trip starts and ends at a depot and visits a number of customers. The aim of the problem is to produce a packing plan for the pallets that minimizes the total transportation cost given that the container cannot be repacked at any stage. In this paper we present an exact solution method based on matching