Job Integrated Optimization of Automated Storage/retrieval Systems Based on Two-stage Wolf Pack Algorithm

doi:10.3969/j.issn.1004-132X.2022.21.003

Abstract

Abstract: In order to improve the loading/unloading operation efficiency of single-shuttle AS/RS under dynamic working conditions， a simulation optimization model was established for the job integrated optimization problem of AS/RS. The model considered the weight of goods and the frequency of entering and leaving the warehouse to divide the rack area. To minimize the running time of single-shuttle stacker in the instruction， a two-stage wolf pack algorithm was designed. The algorithm used the wolf pack algorithm to optimize the storage location assignment and job scheduling， and the solution processes reflected the mutual connection and feedback between the two optimization problems. The experimental results show that under different order sizes， the two-stage wolf pack algorithm may obtain satisfactory solutions and effectively shorten the operation time of AS/RS， compared with other optimization methods.

Key words: automated storage/retrieval systems（AS/RS）, storage location assignment, job scheduling, integrated optimization, two-stage wolf pack algorithm

摘要： 为提高单载具自动化立体仓库动态工况下的进出库效率，针对自动化立体仓库作业集成优化问题建立了仿真优化模型。模型根据货物重质、出入库频率划分货架区域，以指令内最小化单载具堆垛机运行时间为研究目标，设计了一种两阶段狼群算法对其进行优化。该算法使用狼群算法对货位分配和作业调度进行集成优化，求解过程体现出两优化问题之间的关联和反馈。实验结果表明，在不同的订单规模下，相比其他优化方式，两阶段狼群算法能得到满意解，并有效缩短自动化立体仓库的作业时间。

关键词: 自动化立体仓库, 货位分配, 作业调度, 集成优化, 两阶段狼群算法

CLC Number:

TP391.9

HE Li, TAO Yifei, LUO Junbin, XUN Hongkai. Job Integrated Optimization of Automated Storage/retrieval Systems Based on Two-stage Wolf Pack Algorithm[J]. China Mechanical Engineering, 2022, 33(21): 2538-2546.

何李, 陶翼飞, 罗俊斌, 荀洪凯. 基于两阶段狼群算法的自动化立体仓库作业集成优化[J]. 中国机械工程, 2022, 33(21): 2538-2546.

References

［1］HESKETT J L. Cube Per Order Index：a Key to Warehouse Stock Location［J］. Transportation and Distribution Management， 1963， 3（1）：27-31.
［2］YANG Dong， WU Yaohua， MA Wenkai. Optimization of Storage Location Assignment in Automated Warehouse［J］. Microprocessors and Microsystems， 2021， 80：103356.
［3］朱杰，张文怡，薛菲. 基于遗传模拟退火算法的立体仓库储位优化［J］. 计算机应用， 2020， 40（1）：284-291.
ZHU Jie， ZHANG Wenyi， XUE Fei. Storage Location Assignment Optimization of Stereoscopic Warehouse Based on Genetic Simulated Annealing Algorith-m［J］. Journal of Computer Applications， 2020， 40（1）：284-291.
［4］YAN Bo， YAN Chang， LONG Feng， et al. Multi-objective Optimization of Electronic Product Goods Location Assignment in Stereoscopic Warehouse Based on Adaptive Genetic Algorithm［J］. Journal of Intelligent Manufacturing， 2018， 29：1273-1285.
［5］张贵军，姚俊，周晓根，等. 基于精英多策略的货位分配优化方法［J］. 计算机科学， 2018， 45（1）：273-279.
ZHANG Guijun， YAO Jun， ZHOU Xiaogen， et al. Storage Location Assignment Optimization Method Based on Elite Multi-strategy［J］. Computer Science， 2018， 45（1）：273-279.
［6］JIAO Yuling， XING Xiaocui， ZHANG Peng， et al. Multi-objective Storage Location Allocation Optimi-zation and Simulation Analysis of Automated Warehouse Based on Multi-population Genetic Algorithm［J］. Concurrent Engineering， 2018， 26（4）：367-377.
［7］蔡安江，蔡曜，郭师虹，等. 两端式同轨双车运行模式的货位分配策略［J］. 计算机集成制造系统， 2018， 24（12）：3165-3177.
CAI Anjiang， CAI Yao， GUO Shihong， et al. Storage Location Assignment Strategy of Double-crane in Automated Warehouse［J］. Computer Integrated Manufacturing Systems， 2018， 24（12）：3165-3177.
［8］TUANI A F， KEEDWELL E， COLLETT M. Heterogenous Adaptive Ant Colony Optimization with 3-opt Local Search for the Travelling Salesman Problem［J］. Applied Soft Computing， 2020， 97（4）：106720.
［9］AMIRHOSSEIN M， HAMIDREZA E. Multi-shuttle Automated Storage and Retrieval System［J］. Review of Industrial Engineering Letters， 2018， 4（1）：12-20.
［10］蔡安江，薛晓飞，郭师虹，等. 两端式自动化立体仓库布局堆垛机调度［J］. 中国机械工程， 2019， 30（6）：735-741.
CAI Anjiang， XUE Xiaofei， GUO Shihong， et al. Stacker Scheduling of Layouts for Automatic Warehouses with Double Ended［J］. China Mechanical Engineering， 2019， 30（6）：735-741.
［11］CHEN Lu， LANGEVIN A， RIOPEL D. The Storage Location Assignment and Interleaving Problem in an Automated Storage/Retrieval System with Shared Storage［J］. International Journal of Production Research， 2010， 48（3/4）：991-1011.
［12］杨朋，缪立新，戚铭尧. 多载具自动化存取系统货位分配和拣选路径集成优化［J］. 清华大学学报（自然科学版）， 2011， 51（2）：261-266.
YANG Peng， MIAO Lixin， QI Mingyao. Integrated Optimization of Storage Location Assignment and Route Planning in a Multi-shuttle Automated Storage and Retrieval System［J］. Journal of Tsinghua University（Science and Technology）， 2011， 51（2）：261-266.
［13］杨玮，刘江，岳婷，等. 多载具自动化立体仓库货位分配与作业调度集成优化［J］. 计算机集成制造系统， 2019， 25（1）：247-255.
YANG Wei， LIU Jiang， YUE Ting， et al. Integrated Optimization of Location Assignment and Job Scheduling in Multi-carrier Automated Storage and Retrieval System［J］. Computer Integrated Manufacturing Systems， 2019， 25（1）：247-255.
［14］汤洪涛，闫伟杰，陈青丰，等. 自动化立体仓库货位分配与作业调度集成优化［J］. 计算机科学， 2020， 47（5）：204-211.
TANG Hongtao， YAN Weijie， CHEN Qingfeng， et al. Integrated Optimization of Location Assignment and Job Scheduling in Automated Storage and Retrieval System［J］. Computer Science， 2020， 47（5）：204-211.
［15］杨玮，傅卫平，王雯，等. 基于多色集合和粒子群算法的立体仓库货位分配优化［J］. 机械科学与技术， 2012， 31（4）：648-651.
YANG Wei， FU Weiping， WANG Wen， et al. Optimizing Space Allocation for Article Based on Theory of Polychromatic Sets and Particle Swarm Algorithm［J］. Mechanical Science and Technology for Aerospace Engineering， 2012， 31（4）：648-651.
［16］YANG Zhonghua， WANG Ling， CAI Yeqing， et al. A Polychromatic Sets Theory Based Algorithm for the Input/Output Scheduling Problem in AS/RSs［J］. Evolutionary Intelligence， 2019， 12（3）：333-340.
［17］吴虎胜，张凤鸣，吴庐山. 一种新的群体智能算法——狼群算法［J］. 系统工程与电子技术， 2013， 35（11）：2430-2438.
WU Husheng， ZHANG Fengming， WU Lushan. New Swarm Intelligence Algorithm—Wolf Pack Algorithm［J］. System Engineering and Electronics， 2013， 35（11）：2430-2438.
［18］吴虎胜，张凤鸣，李浩，等. 求解TSP问题的离散狼群算法［J］. 控制与决策， 2015， 30（10）：1861-1867.
WU Husheng， ZHANG Fengming， LI Hao， et al. Discrete Wolf Pack Algorithm for Traveling Salesman Problem［J］. Control and Decision， 2015， 30（10）：1861-1867.
［19］谢锐强，张惠珍. 求解柔性作业车间调度问题的两段式狼群算法［J］. 计算机工程与应用， 2021， 57（7）：251-256.
XIE Ruiqiang， ZHANG Huizhen. Two-vector Wolf Pack Algorithm for Flexible Job Shop Scheduling Problem［J］. Computer Engineering and Application， 2021， 57（7）：251-256.

[1]	GUO Jutao, LYU Youlong, DAI Zheng, ZHANG Jie, GUO Yu. Compound Rules and Reinforcement Learning Based Scheduling Method for Mixed Model Assembly Lines [J]. China Mechanical Engineering, 2023, 34(21): 2600-2606,2614.
[2]	ZHANG Kai, BI Li, JIAO Xiaogang. Research on Flexible Job-shop Scheduling Problems with Integrated Reinforcement Learning Algorithm [J]. China Mechanical Engineering, 2023, 34(02): 201-207.
[3]	ZHANG Heng;LI Aiping;FU Xiang;SHAO Huan;LIU Xuemei. An Integrated Optimization Method for Setups Planning and Line Balancing of Mixed Model Transfer Lines [J]. China Mechanical Engineering, 2019, 30(20): 2497-2504.
[4]	NIE Li1;ZHANG Guohui2;WANG Xiaogang1;BAI Yuewei1. A Game-theory Based Optimization Approach for Job Scheduling in Virtual Manufacturing Networks [J]. China Mechanical Engineering, 2019, 30(12): 1492-1497.
[5]	Zhou Guanghui, Cheng Yuansen, Xiao Zhongdong, Miao Faxiang, Wang Rui. Stackelberg Game for Critical Job Scheduling in Service-oriented Manufacturing Plants [J]. China Mechanical Engineering, 2014, 25(3): 341-345,416.