Exact Solutions to the Double Travelling Salesman Problem with Multiple Stacks

In this paper we present mathematical programming formulations and solution approaches for the optimal solution of the Double Travelling Salesman Problem with Multiple Stacks (DTSPMS). A set of orders is given, each one requiring transportation of one item from a customer in a pickup region to a customer in a delivery region.

The vehicle available for the transportation in each region carries a container. The container is organized in rows of given length. Each row is handled independently from the others according to a LIFO (Last In First Out) stack policy. The DTSPMS problem consists of determining the pickup tour, the loading plan of the container and the delivery tour in such a way that the total length of the two tours is minimized.

The formulations are based on different modelling ideas and each formulation gives rise to a specific solution approach. We present computational results on a set of benchmark instances that compare the different approaches and show that the most successful one is a decomposition approach applied to a new model.