A polynomial-time dynamic programming algorithm for an optimal picking problem in automated warehouses

被引：0
作者：
Barbato, Michele [1 ]
Ceselli, Alberto [1 ]
Righini, Giovanni [1 ]
机构：
[1] Univ Milan, Dipartimento Informat Giovanni Antoni, Via Celoria 18, I-20133 Milan, Italy
来源：
JOURNAL OF SCHEDULING | 2024年 / 27卷 / 04期
关键词：
Combinatorial optimization; Crane scheduling; Polynomial-time algorithm; Dynamic programming; STORAGE;
D O I：
10.1007/s10951-024-00811-2
中图分类号：
T [工业技术];
学科分类号：
08 ;
摘要：
We consider an optimization problem arising when a set of items must be selected and picked up from given locations in an automated storage and retrieval system by a crane of given capacity, minimizing the overall distance traveled. The problem has been classified as open in a recent taxonomy of optimal picking problems in automated warehouses. In this paper, we analyze some non-trivial properties of the problem and we describe a polynomial-time dynamic programming algorithm to solve it to proven optimality.
引用
收藏
页码：393 / 407
页数：15
相关论文
共 17 条
[1]   Robotized and Automated Warehouse Systems: Review and Recent Developments [J].
Azadeh, Kaveh ;
De Koster, Rene ;
Roy, Debjit .
TRANSPORTATION SCIENCE, 2019, 53 (04) :917-945
[2]  
Barbato M., 2019, AIRO SPRINGER SERIES, V3, P151
[3]   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
[4]   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
[5]  
Brucker P., 1998, Journal of Scheduling, V1, P31, DOI 10.1002/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO
[6]  
2-R
[7]   Design and control of warehouse order picking: A literature review [J].
de Koster, Rene ;
Le-Duc, Tho ;
Roodbergen, Kees Jan .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 182 (02) :481-501
[8]   A shift-based sequencing method for twin-shuttle automated storage and retrieval systems [J].
Dooly, Daniel R. ;
Lee, Heungsoon Felix .
IIE TRANSACTIONS, 2008, 40 (06) :586-594
[9]   A Joint Comparative Analysis of Routing Heuristics and Paperless Picking Technologies Using Simulation and Data Envelopment Analysis [J].
Fontin, Jean-Raymond ;
Lin, Shi-Woei .
APPLIED SCIENCES-BASEL, 2020, 10 (24)
[10]   Polynomial Time Algorithms to Minimize Total Travel Time in a Two-Depot Automated Storage/Retrieval System [J].
Gharehgozli, Amir Hossein ;
Yu, Yugang ;
Zhang, Xiandong ;
de Koster, Rene .
TRANSPORTATION SCIENCE, 2017, 51 (01) :19-33
12