一种鱼骨仓储布局下的拣选路径优化方法

摘要/Abstract

摘要： 根据一种非传统鱼骨(fishbone)布局的特点，基于仓储运作约束条件建立了拣选路径优化模型，构造了非传统货位距离矩阵；在标准遗传算法基础上，通过进化逆转算子克服标准遗传算法存在早熟收敛和局部搜索能力较差等问题，给出了一种多种群遗传算法；为验证算法的有效性，在不同订单规模下，将多种群遗传算法与标准遗传算法和S-Shape算法进行比较，应用MATLAB软件仿真分析，一系列实验结果表明多种群遗传算法计算结果最优，并且寻优速度更快于标准遗传算法，能够很好地解决鱼骨仓储布局下的拣选路径优化问题，提高仓储智能化水平。

关键词: 鱼骨布局, 拣选路径优化, 多种群遗传算法, 进化逆转算子

Abstract: A picking route optimization model was established and the distance matrix for the storage location in non-traditional warehouse was constructed according to the characteristics of a non-traditional fishbone layout and considering the actual warehouse operation constraints. Meanwhile, a MPGA with an evolutional reversed operator was proposed based on the standard genetic algorithm (SGA) to overcome the premature convergence and poor local search ability of SGA. To verify the effectiveness of the algorithm, MPGA was compared with SGA and S-Shape under different order sizes, and the MATLAB software was used to simulate and analyze. Experimental results show that the MPGA has the best calculation results, and the speed of searching optimal solution is quicker than that of SGA. The proposed algorithm may be better to solve the problems of picking route optimization for the warehouse with fishbone layout and improve the intelligent level of warehousing.

Key words: fishbone layout, picking route optimization, multiple population genetic algorithm(MPGA), evolutional reversed operator

中图分类号:

TH181
TB491

刘建胜;雷兆发;聂伟豪;涂海宁. 一种鱼骨仓储布局下的拣选路径优化方法[J]. 中国机械工程.

LIU Jiansheng;LEI Zhaofa;NIE Weihao;TU Haining. An Optimization Method of Picking Routes for Warehouses with Fishbone Layout[J]. China Mechanical Engineering.

参考文献

[1]KOSTER D R, LE-DUC T, ROODBERGEN K J. Design and Control of Warehouse Order Picking: a Literature Review[J]. European Journal of Operational Research, 2007, 182(2): 481-501.
[2]PETERSEN C G. An Evaluation of Order Picking Routeing Policies[J]. International Journal of Operations & Production Management, 1997, 17(11): 1098-1111.
[3]PARIKHAB P J. A Travel-time Model for a Person-onboard Order Picking System[J]. European Journal of Operational Research, 2010, 200(2): 385-394.
[4]ROODBERGEN K J, VIS I F A. A Model for Warehouse Layout[J]. IIE Transactions, 2006, 38(10): 799-811.
[5]HONG S, JOHNSON A L, PETERS B A. Batch Picking in Narrow-aisle Order Picking Systems with Consideration for Picker Blocking[J]. European Journal of Operational Research, 2012, 221(3): 557-570.
[6]LE-DUC T, KOSTER D R. Travel Time Estimation and Order Batching in a 2-block Warehouse[J]. European Journal of Operational Research, 2007, 176(1): 374-388.
[7]VIGNALI G. Optimisation of Storage Allocation in Order Picking Operations through a Genetic Algorithm[J]. International Journal of Logistics Research & Applications, 2012, 15(2): 127-146.
[8]KOSTER D R, LE-DUC T, ZAERPOUR N. Determining the Number of Zones in a Pick-and-Sort Order Picking System[J]. International Journal of Production Research, 2012, 50(3): 757-771.
[9]KULAK O, TANER M E. Joint Order Batching and Picker Routing in Single and Multiple-cross-aisle Warehouses Using Cluster-based Tabu Search Algorithms[J]. Flexible Services & Manufacturing Journal, 2012, 24(1): 52-80.
[10]BOTTANI E, MONTANARI R, RINALDI M, et al. Intelligent Algorithms for Warehouse Management[J]. Intelligent Systems Reference Library, 2015, 87: 645-667.
[11]CHEN F Y, WANG H W, QI C, et al. An Ant Colony Optimization Routing Algorithm for Two Order Pickers with Congestion Consideration[J]. Computers & Industrial Engineering, 2013, 66(1): 77-85.
[12]PETERSEN C G. The Impact of Routing and Storage Policies on Warehouse Efficiency[J]. International Journal of Operations & Production Management, 1999, 19(10): 1053-1064.
[13]陈呈频，韩胜军，鲁建厦，等. 多车场与多车型车辆路径问题的多染色体遗传算法[J]. 中国机械工程, 2018, 29(2): 218-223.
CHEN Chengpin, HAN Shengjun, Lu Jiansha, et al. A Multi-chromosome Genetic Algorithm for Multi-depot and Multi-type Vehicle Routing Problems[J]. China Mechanical Engineering, 2018, 29(2): 218-223.
[14]高海昌，冯博琴，朱利. 智能优化算法求解TSP问题[J]. 控制与决策, 2006, 21(3): 241-247.
GAO Haichang, FENG Boqin, ZHU Li. Reviews of the Meta-heuristic Algorithms for TSP[J]. Control and Decision, 2006, 21(3): 241-247.
[15]王宏，符卓，左武. 基于遗传算法的双区型仓库拣货路径优化研究[J]. 计算机工程与应用, 2009, 45(6): 224-228.
WANG Hong, FU Zhuo, ZUO Wu. Genetic Algorithm for Picking Routing Problem in 2-block Warehouse[J]. Computer Engineering and Applications, 2009, 45(6): 224-228.
[16]陈方宇，王红卫，祁超，等. 考虑多拣货员堵塞的仓库拣选路径算法[J]. 系统工程学报, 2013(5): 581-591.
CHEN Fangyu, WANG Hongwei, QI Chao, et al.Routing Method for Multiple Order Pickers with Congestion Consideration[J]. Journal of Systems Engineering, 2013(5): 581-591.
[17]GUE K R, MELLER R D. Aisle Configurations for Unit-load Warehouses[J]. IIE Transaction, 2009(3): 171-182.
[18]ROODBERGEN K J, KOSTER D R. Routing Methods for Warehouses with Multiple Cross Aisles[J]. International Journal of Production Research, 2001, 39(9): 1865-1883.
[19]HALL R. Distance Approximations for Routing Manual Pickers in a Warehouse[J]. IIE Transactions, 1993, 25(4): 76-87.
[20]SHARP G P. Designing the Layout Structure of Manual Order Picking Areas in Warehouses[J]. IIE Transactions, 2008, 40(11): 1032-1045.
[21]PETERSEN C G, AASE G. A Comparison of Picking, Storage, and Routing Policies in Manual Order Picking[J]. International Journal of Production Economics, 2005, 92(1): 11-19.
[22]XIAO J, ZHENG L. A Correlated Storage Location Assignment Problem in a Single-block-multi-aisles Warehouse Considering BOM Information[J]. International Journal of Production Research, 2010, 48(5): 1321-1338.
[23]POHL L M, MELLER R D, GUE K R. Optimizing Fishbone Aisles for Dual-command Operations in a Warehouse[J]. Naval Research Logistics, 2009, 56(5): 389-403.
[24]雷英杰，张善文. MATLAB遗传算法工具箱及应用[M]. 西安：西安电子科技大学出版社, 2014: 1-10.
LEI Yingjie, ZHANG Shanwen. MATLAB Genetic Algorithm Toolbox and Application[M]. Xi’an: Xidian University Press, 2014: 1-10.
[25]LIU Y，SONG J，WEN J Y. An Optimizing Algorithm of Static Task Scheduling Problem Based on Bybrid Genetic Algorithm[J]. High Technology Letters, 2016, 22(2): 170-176.[26]林阳，赵欢，丁汉. 基于多种群遗传算法的一般机器人逆运动学求解[J]. 机械工程学报, 2017,53(3): 1-8.
LIN Yang, ZHAO Huan, DING Han. Solution of Inverse Kinematics for General Robot Manipulators Based on Multiple Population Genetic Algorithm[J]. Journal of Mechanical Engineering, 2017,53(3): 1-8.