Preemptive stacker crane problem: Extending tree-based properties and construction heuristics

Autor(en): Graf, Benjamin
Stichwörter: Business & Economics; Construction heuristics; Management; Operations Research & Management Science; Preemption; Routing; Stacker crane problem
Erscheinungsdatum: 2021
Herausgeber: ELSEVIER
Volumen: 292
Ausgabe: 2
Startseite: 532
Seitenende: 547
The stacker crane problem (SCP) considers the cost-minimal routing of a single unit-capacity vehicle that needs to satisfy a given set of one-to-one pickup and delivery requests. In the preemptive stacker crane problem (PSCP), the vehicle is additionally allowed to temporarily drop its payload at arbitrary intermediate locations. While a payload is stored at an intermediate location, other requests may be performed. Prior work in the literature has shown that a specific tree structure is sufficient to represent optimal solutions for the PSCP. Building on this tree structure, this work establishes bounds on the benefits of preemption and additional drop locations that are neither associated with a pickup nor a delivery location, proposes reduced solution representations and describes algorithms for subproblems solvable in polynomial time. Furthermore, heuristic construction methods adapted for the PSCP from well-known heuristics for the asymmetric traveling salesman problem (ATSP) and capacitated vehicle routing problem (CVRP) are presented. The previously described and newly proposed adapted heuristics are evaluated and compared in a large scale computational study with respect to computation time, solution quality and other solution characteristics. (C) 2020 Elsevier B.V. All rights reserved.
ISSN: 03772217
DOI: 10.1016/j.ejor.2020.10.051

Show full item record

Page view(s)

Last Week
Last month
checked on May 21, 2024

Google ScholarTM