Premium
Exact solutions to the double travelling salesman problem with multiple stacks
Author(s) -
Petersen Hanne L.,
Archetti Claudia,
Speranza M. Grazia
Publication year - 2010
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20375
Subject(s) - travelling salesman problem , pickup , container (type theory) , benchmark (surveying) , computer science , mathematical optimization , set (abstract data type) , traveling purchaser problem , 2 opt , decomposition , stack (abstract data type) , row , vehicle routing problem , bottleneck traveling salesman problem , mathematics , routing (electronic design automation) , engineering , artificial intelligence , mechanical engineering , ecology , computer network , geodesy , database , image (mathematics) , biology , programming language , geography
In this article 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 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 modeling 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. © 2010 Wiley Periodicals, Inc. NETWORKS, 2010