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

DC FieldValueLanguage
dc.contributor.authorGraf, Benjamin
dc.date.accessioned2021-12-23T15:59:56Z-
dc.date.available2021-12-23T15:59:56Z-
dc.date.issued2021
dc.identifier.issn03772217
dc.identifier.urihttps://osnascholar.ub.uni-osnabrueck.de/handle/unios/4235-
dc.description.abstractThe 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.
dc.language.isoen
dc.publisherELSEVIER
dc.relation.ispartofEUROPEAN JOURNAL OF OPERATIONAL RESEARCH
dc.subjectBusiness & Economics
dc.subjectConstruction heuristics
dc.subjectManagement
dc.subjectOperations Research & Management Science
dc.subjectPreemption
dc.subjectRouting
dc.subjectStacker crane problem
dc.titlePreemptive stacker crane problem: Extending tree-based properties and construction heuristics
dc.typejournal article
dc.identifier.doi10.1016/j.ejor.2020.10.051
dc.identifier.isiISI:000626296800009
dc.description.volume292
dc.description.issue2
dc.description.startpage532
dc.description.endpage547
dc.contributor.orcid0000-0002-8382-4819
dc.identifier.eissn18726860
dc.publisher.placeRADARWEG 29, 1043 NX AMSTERDAM, NETHERLANDS
dcterms.isPartOf.abbreviationEur. J. Oper. Res.
Show simple item record

Page view(s)

1
Last Week
0
Last month
0
checked on Apr 14, 2024

Google ScholarTM

Check

Altmetric