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

Benjamin Graf

European Journal of Operational Research, 2021, vol. 292, issue 2, 532-547

Abstract: 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.

Keywords: Routing; Stacker crane problem; Preemption; Construction heuristics (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720309425
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:292:y:2021:i:2:p:532-547

DOI: 10.1016/j.ejor.2020.10.051

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().