Exact Solutions to the Double Travelling Salesman Problem with Multiple Stacks

Hanne L. Petersen, Claudia Archetti, M. Grazia Speranza

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    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.
    Original languageEnglish
    JournalNetworks
    Volume56
    Issue number4
    Pages (from-to)229-243
    ISSN0028-3045
    DOIs
    Publication statusPublished - 2010

    Keywords

    • pickup and delivery
    • travelling salesman problem
    • loading
    • LIFO
    • branch and cut

    Fingerprint Dive into the research topics of 'Exact Solutions to the Double Travelling Salesman Problem with Multiple Stacks'. Together they form a unique fingerprint.

    Cite this