An Exact Method for the Double TSP with Multiple Stacks

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

    Research output: Book/ReportReportResearchpeer-review

    235 Downloads (Pure)


    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
    Place of PublicationKgs. Lyngby
    PublisherDTU Management
    Number of pages13
    ISBN (Print)978-87-90855-37-6
    Publication statusPublished - 2009
    SeriesDTU Management 2009


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

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

    Cite this