Exact and heuristic solutions to the Double TSP with Multiple Stacks

Hanne Løhmann Petersen (Invited author), Claudia Archetti (Invited author), Oli B.G. Madsen (Invited author), M. Grazia Speranza (Invited author)

    Research output: Contribution to conferenceConference abstract for conferenceResearchpeer-review

    Abstract

    The double travelling salesman problem with multiple stacks (DTSPMS) is a pickup and delivery problem where pickups and deliveries are separated, such that all pickup operations are performed before the first delivery takes place. All operations are carried out by one vehicle and no reloading is allowed. The vehicle provides several separated (horizontal) stacks/rows for the transportation of the orders, such that each stack is accessed using a LIFO principle, independently of the other stacks. In a real-life setting the dimensions of the problem is 33 orders each consisting of one euro-pallet, which can be loaded in 3 stacks in a standard 40 foot container. Different exact and heuristic solution approaches to the DTSPMS have been implemented and tested. The exact approaches are based on different mathematical formulations of the problem which are solved using branch-and-cut. One formulation leads to a decomposition approach, consisting of a routing master problem and a loading feasibility subproblem, which generates infeasible paths for the master problem. The latter is the most promising of the tested approaches, and solves all tested problems with up to 15 orders, as well as some larger instances. The implemented heuristics include tabu search, simulated annealing and large neighbourhood search. Particularly the LNS approach shows promising results. It finds the known optimal solution of smaller instances (15 orders) within 10 seconds in most cases, and in 3 minutes it finds solutions to 33 order instances that are on average within 1% of the best known solutions.
    Original languageEnglish
    Publication date2009
    Publication statusPublished - 2009
    EventROUTE 2009: International Workshop on Vehicle Routing, Intermodal Transport and Related Areas - Skodsborg, Denmark
    Duration: 21 Jun 200924 Jun 2009
    Conference number: 6

    Conference

    ConferenceROUTE 2009: International Workshop on Vehicle Routing, Intermodal Transport and Related Areas
    Number6
    CountryDenmark
    CitySkodsborg
    Period21/06/200924/06/2009

    Fingerprint Dive into the research topics of 'Exact and heuristic solutions to the Double TSP with Multiple Stacks'. Together they form a unique fingerprint.

    Cite this