计算机科学 ›› 2020, Vol. 47 ›› Issue (5): 204-211.doi: 10.11896/jsjkx.190400042
汤洪涛, 闫伟杰, 陈青丰, 鲁建厦, 詹燕
TANG Hong-tao, YAN Wei-jie, CHEN Qing-feng, LU Jian-sha, ZHAN Yan
摘要: 针对动态提高单载具堆垛机式自动化立体仓库拣选效率的问题,文中提出了一种基于共享货位存储与动态订单拣选策略下的货位分配与作业调度集成优化方法。将动态移库优化扩展到仓库的整个拣选生命周期,建立以双指令循环下堆垛机拣选任务所需的总作业时间最短为评价目标的数学模型,提出了一种基于K-Medoids聚类的粒子群优化(Particle Swarm Optimization,PSO)算法,用K-Medoids算法通过产品与订单的相关性进行初始货位的聚类分析,筛除劣质解的货位范围,并在K-Medoids聚类算法生成的解类簇基础上获得精确解。实验结果表明,考虑动态移库可以使仓库拣选效率提高20%,且该算法与传统PSO算法相比求解时间下降66%左右。
中图分类号:
[1]YANG P,MIAO L X.Review of Control Optimization for Automated Storage and Retrieval Systems[J].Industrial Engineering Journal,2011,14(1):123-127. [2]GAGLIARDI J P,RENAUD J,RUIZ A.Models for automated storage and retrieval systems:a literature review[J].International Journal of Production Research,2012,50(24):7110-7125. [3]NILS B,KONRAD S.A survey on single crane scheduling in automated storage/retrieval systems[J].European Journal of Ope-rational Research,European Journal of Operational Research,2016,254(3):691-704. [4]BIENKOWSKI M,BYRKA J,CHROBAK M,et al.Approximation algorithms for the joint replenishment problem with deadlines[J].Journal of Scheduling,2015,18(6):545-560. [5]CAI A J,CAI Y,GUO S H,et al.Storage location assignment strategy of double-crane in automated warehouse[J].Computer Integrated Manufacturing Systems,2018,24(12):3165-3177. [6]LERHER T,POTRC I,SRAML M,et al.Travel time modelsfor automated warehouses with aisle transferring storage and retrieval machine[J].European Journal of Operational Research,2010,205(3):571-583. [7]NILS B,DIRK B,FRANK M.A generalized classificationscheme for crane scheduling with interference[J].European Journal of Operational Research,2017,258(1):343-357. [8]CHEN L,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(4):991-1011. [9]ZHOU J,ZHAO C Y,LIU Z Q,et al.Operation optimization of storage and retrieval for stackers in AS/RS of raw tabacco material[J].Computer Integrated Manufacturing Systems,2009,15(4):772-776. [10]CAI A J,YING J Q,WANG J,et al.Scheduling model of crane in distributed automated warehouse[J].Computer Integrated Manufacturing Systems,2016,22(03):793-799. [11]HACHEMI K,SARI Z,GHOUALI N.A step-by-step dualcycle sequencing method for unit-load automated storage and retrieval systems[J].Computers & Industrial Engineering,2012,63(4):980-984. [12]YANG W,LIU J,YUE T,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. [13]LU C,ANDRE L,DIANE R.A tabu search algorithm for the relocation problem in a warehousing system[J].International Journal of Production Economics,2011,129(1):147-156. [14]KOH S G,KIM B S,KIM B N.Travel time model for the warehousing system with a tower crane S/R machine[J].Computers &Industrial Engineering,2002,43(3):495-507. [15]YANG P,MIAO L X,XUE Z J,et al.Variable neighborhoodsearch heuristic for storage location assignment and storage/retrieval scheduling under shared storage in multi-shuttle automated storage/retrieval systems[J].Transportation Research Part E - Logistics and Transportation Review,2015,79:164-177. [16]TANAKA S,ARAKI M.Routing problem under the sharedstorage policy for unit-load automated storage and retrieval systems with separate input and output points[J].International Journal of Production Research,2009,47(9):2391-2408. [17]GONG Y M,RENE D K.A polling-based dynamic order picking system for online retailer[J].IIE Transactions,2008,40(11):1070-1082. [18]LU W R,FARLANE M D,GIANNIKAS V,et al.An algorithm for dynamic order-picking in warehouse operations[J].European Journal of Operational Research,2016,248(1):107-122. [19]HUANG Y,LI H Y,XU K B,et al.S-shaped Function BasedAdaptive S-shaped Function Based Adaptive[J].ComputerScie-nce,2019,46(01):245-250. [20]PRANAV N,ARCHANA S,MADHAV C,et al.Empirical Analysis of Data Clustering Algorithms[J].Procedia Computer Science,2018,125(1):770-779. [21]AMIT B,ISSAM A M.Evolutionary Clustering Algorithms for Relational Data[J].Procedia Computer Science,2018,140(1):276-283. [22]CHEN J J,CHE J.IK-medoids Based Aircraft Fuel Consump-tion Clustering Algorithm[J].Computer Science,2018,45(8):306-309,314. [23]DING Y,ZHANG Q,LIN G L.Quay Crane Scheduling withYard Operation Balance at Automated Container Terminal[J].Journal of Chongqing Jiaotong university(Natural Science),2018,37(7):106-112. [24]WOLLIAM H,XIN M.The state-of-the-art integrations and applications of the analytic hierarchy process[J].European Journal of Operational Research,2018,267(2):399-414. [25]LIU X J,WEI Y C,YUAN B X,et al.Study on Adaptive Hie-rarchical Clustering De-noising Algorithm of Laser Ranging in Storage of Dangerous Chemicals[J].Computer Science,2018,45(S2):208-211,217. [26]ZOU P,LI B Z,YANG J G,et al.Hierarchical ant-Genetic algorithm-based multi-objective intelligent approach for flexible job shop scheduling[J].China Mechanical Engineering,2015,26(21):2873-2879,2884. |
[1] | 徐汝利, 黄樟灿, 谢秦秦, 李华峰, 湛航. 基于金字塔演化策略的彩色图像多阈值分割 Multi-threshold Segmentation for Color Image Based on Pyramid Evolution Strategy 计算机科学, 2022, 49(6): 231-237. https://doi.org/10.11896/jsjkx.210300096 |
[2] | 周天清, 岳亚莉. 超密集物联网络中多任务多步计算卸载算法研究 Multi-Task and Multi-Step Computation Offloading in Ultra-dense IoT Networks 计算机科学, 2022, 49(6): 12-18. https://doi.org/10.11896/jsjkx.211200147 |
[3] | 邱旭, 卞浩卜, 吴铭骁, 朱晓荣. 基于5G毫米波通信的高速公路车联网任务卸载算法研究 Study on Task Offloading Algorithm for Internet of Vehicles on Highway Based on 5G MillimeterWave Communication 计算机科学, 2022, 49(6): 25-31. https://doi.org/10.11896/jsjkx.211100198 |
[4] | 李晓东, 於志勇, 黄昉菀, 朱伟平, 涂淳钰, 郑伟楠. 面向河道环境监测的群智感知参与者选择策略 Participant Selection Strategies Based on Crowd Sensing for River Environmental Monitoring 计算机科学, 2022, 49(5): 371-379. https://doi.org/10.11896/jsjkx.210200005 |
[5] | 孙振强, 罗永龙, 郑孝遥, 章海燕. 一种融合用户情感与相似度的智能旅游路径推荐方法 Intelligent Travel Route Recommendation Method Integrating User Emotion and Similarity 计算机科学, 2021, 48(6A): 226-230. https://doi.org/10.11896/jsjkx.200900119 |
[6] | 刘炜, 李东坤, 徐畅, 田钊, 佘维. 应急通信网络中基于粒子群优化的信道分配算法 Channel Assignment Algorithm Based on Particle Swarm Optimization in Emergency Communication Networks 计算机科学, 2021, 48(5): 277-282. https://doi.org/10.11896/jsjkx.200400042 |
[7] | 栾凌, 潘连武, 闫雷, 武小琳. 基于边缘计算的输变电工程全环节单元确认的精准造价智能管控技术研究 Research on Intelligent Control Technology of Accurate Cost for Unit Confirmation in All Links of Power Transmission and Transformation Project Based on Edge Computing 计算机科学, 2021, 48(11A): 688-692. https://doi.org/10.11896/jsjkx.201100200 |
[8] | 张天瑞, 魏铭琦, 高秀秀. 基于IPSO-WRF的选择性激光烧结件气泡溶解时间预测模型 Prediction Model of Bubble Dissolution Time in Selective Laser Sintering Based on IPSO-WRF 计算机科学, 2021, 48(11A): 638-643. https://doi.org/10.11896/jsjkx.210300080 |
[9] | 田梦丹, 梁晓磊, 符修文, 孙媛, 李章洪. 具有博弈概率选择的多子群粒子群算法 Multi-subgroup Particle Swarm Optimization Algorithm with Game Probability Selection 计算机科学, 2021, 48(10): 67-76. https://doi.org/10.11896/jsjkx.200800128 |
[10] | 孟利民, 王锟, 郑增乾, 蒋维. 基于粒子群算法的D2D内容边缘缓存架构策略 Architecture Strategy of D2D Content Edge Cache Based on Particle Swarm Optimization 计算机科学, 2020, 47(11A): 345-348. https://doi.org/10.11896/jsjkx.200500079 |
[11] | 李宝胜, 秦传东. 基于粒子群优化的SVM多分类的电动车价格预测研究 Study on Electric Vehicle Price Prediction Based on PSO-SVM Multi-classification Method 计算机科学, 2020, 47(11A): 421-424. https://doi.org/10.11896/jsjkx.191200132 |
[12] | 王改云, 王磊杨, 路皓翔. 基于混合群智能算法优化的RSSI质心定位算法 RSSI-based Centroid Localization Algorithm Optimized by Hybrid Swarm Intelligence Algorithm 计算机科学, 2019, 46(9): 125-129. https://doi.org/10.11896/j.issn.1002-137X.2019.09.017 |
[13] | 张娜,滕赛娜,吴彪,包晓安. 基于粒子群优化算法的测试用例生成方法 Test Case Generation Method Based on Particle Swarm Optimization Algorithm 计算机科学, 2019, 46(7): 146-150. https://doi.org/10.11896/j.issn.1002-137X.2019.07.023 |
[14] | 胡鑫楠. 基于改进型混沌粒子群优化算法的FIR高通数字滤波器设计 FIR High Pass Digital Filter Design Based on Improved Chaos Particle Swarm Optimization Algorithm 计算机科学, 2019, 46(6A): 601-604. |
[15] | 邵炜晖, 许维胜, 徐志宇, 王宁, 农静. 基于改进粒子群算法的电动汽车停车场V2G策略研究 Research of V2G Strategies for EV Parking Lot Based on Improved PSO 计算机科学, 2018, 45(11A): 92-96. |
|