An Exact Method for the Double TSP with Multiple Stacks

Richard Martin Lusby, Jesper Larsen, Matthias Ehrgott, David Ryan

    Research output: Contribution to journalJournal articleResearchpeer-review


    The double travelling salesman problem 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 3 columns of 11 rows) is used to transport up to 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 stacking plan for the pallets that minimizes the total transportation cost (ignoring the cost of transporting the container between the depots of the two trips) given that the container cannot be repacked at any stage. In this paper we present an exact solution method based on matching k-best TSP solutions for each of the separate pickup and delivery TSP problems and show that previously unsolved instances can be solved within seconds using this approach.
    Original languageEnglish
    JournalInternational Transactions in Operational Research
    Issue number5
    Pages (from-to)637-652
    Publication statusPublished - 2010


    • TSP
    • Exact method
    • K-best solution
    • Routing
    • Packing


    Dive into the research topics of 'An Exact Method for the Double TSP with Multiple Stacks'. Together they form a unique fingerprint.

    Cite this