The double travelling salesman problem with multiple stacks - Formulation and heuristic solution approaches

Hanne Løhmann Petersen, Oli B.G. Madsen

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    This paper introduces the double travelling salesman problem with multiple stacks and presents four different metaheuristic approaches to its solution. The double TSP with multiple stacks is concerned with determining the shortest route performing pickups and deliveries in two separated networks (one for pickups and one for deliveries) using only one container. Repacking is not allowed, instead each item can be positioned in one of several rows in the container, such that each row can be considered a LIFO (last in, first out) stack, but no mutual constraints exist between the rows. Two different neighbourhood structures are developed for the problem and used with each of three local search metaheuristics. Additionally some simpler removal and reinsertion operators are used in a Large neighbourhood search framework. Finally some computational results are given along with lower bounds on the objective value.
    Original languageEnglish
    JournalEuropean Journal of Operational Research
    Volume198
    Issue number1
    Pages (from-to)139-147
    ISSN0377-2217
    DOIs
    Publication statusPublished - 2009

    Keywords

    • Metaheuristics
    • Packing
    • Routing
    • TSP variants

    Fingerprint Dive into the research topics of 'The double travelling salesman problem with multiple stacks - Formulation and heuristic solution approaches'. Together they form a unique fingerprint.

    Cite this