Crane scheduling for end-of-aisle picking: Complexity and efficient solutions based on the vehicle routing problem

被引:6
作者
Boysen, Nils [1 ]
Emde, Simon [2 ]
Stephan, Konrad [1 ]
机构
[1] Friedrich Schiller Univ Jena, Lehrstuhl Operat Management, Carl Zeiss Str 3, D-07743 Jena, Germany
[2] Aarhus Univ, Dept Econ & Business Econ, CORAL, Analyt, Fuglesangs Alle 4, DK-8210 Aarhus V, Denmark
关键词
Facility logistics; Warehousing; Crane scheduling; Vehicle routing; ORDER-PICKING; AUTOMATED STORAGE; PERFORMANCE ANALYSIS; RETRIEVAL-SYSTEMS; DWELL POINT; DESIGN; MODELS; BOUNDS;
D O I
10.1016/j.ejtl.2022.100085
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
To relieve human order pickers from unproductive walking through a warehouse, parts-to-picker systems deliver demanded stock keeping units (SKUs) toward picking workstations. In a wide-spread parts-to-picker setup, a crane-operated automated storage and retrieval system (ASRS) delivers bins with demanded SKUs toward an end-of-aisle picking workstation and returns them back into the rack once the picks are completed. We consider the scheduling of the crane that operates subsequent dual commands. Each dual command combines a retrieval request for another SKU bin demanded at the picking workstation with a storage request, where a bin that has already been processed and passed through the bin buffer is returned to its dedicated storage position in the ASRS. This system setup in general and the resulting crane scheduling problem in particular have been an active field of research for more than 30 years. We add the following contributions to this stream of research: We finally prove that the crane scheduling problem is strongly NP-hard. Furthermore, we show that, although only a single vehicle (namely, the crane) is applied, the problem is equivalent to the traditional vehicle routing problem (VRP). This opens the rich arsenal of very efficient VRP solvers, which substantially outperform existing tailor-made algorithms from the literature.
引用
收藏
页数:11
相关论文
共 46 条
[1]  
Allied Market Research, 2020, AUT STOR RETR SYST M
[2]   Design and analysis of an automated order-picking workstation [J].
Andriansyah, R. ;
Etman, L. F. P. ;
Adan, I. J. B. F. ;
Rooda, J. E. .
JOURNAL OF SIMULATION, 2014, 8 (02) :151-163
[3]  
[Anonymous], 2010, INT J ADV SYST MEAS
[4]   Robotized and Automated Warehouse Systems: Review and Recent Developments [J].
Azadeh, Kaveh ;
De Koster, Rene ;
Roy, Debjit .
TRANSPORTATION SCIENCE, 2019, 53 (04) :917-945
[5]  
Baardman L., 2016, 14 IMHRC P
[6]   A Special Case of the Multiple Traveling Salesmen Problem in End-of-Aisle Picking Systems [J].
Baardman, Lennart ;
Roodbergen, Kees Jan ;
Carlo, Hector J. ;
Schrotenboer, Albert H. .
TRANSPORTATION SCIENCE, 2021, 55 (05) :1151-1169
[7]   Performance analysis of batching decisions in waveless order release environments for e-commerce stock-to-picker order fulfillment [J].
Bansal, Vishal ;
Roy, Debjit ;
Pazour, Jennifer A. .
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2021, 28 (04) :1787-1820
[8]   Warehousing in the e-commerce era: A survey [J].
Boysen, Nils ;
de Koster, Rene ;
Weidinger, Felix .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2019, 277 (02) :396-411
[9]   Parts-to-picker based order processing in a rack-moving mobile robots environment [J].
Boysen, Nils ;
Briskorn, Dirk ;
Emde, Simon .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2017, 262 (02) :550-562
[10]   A survey on single crane scheduling in automated storage/retrieval systems [J].
Boysen, Nils ;
Stephan, Konrad .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2016, 254 (03) :691-704