基于遗传算法的双区型仓库拣货路径优化研究

《基于遗传算法的双区型仓库拣货路径优化研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据2242009，45(6)ComputerEngineeringandApplications计算机工程与应用基于遗传算法的双区型仓库拣货路径优化研究王宏，符卓，左武WANGHong，FUZhuo，ZUOWu中南大学交通运输工程学院，长沙410075SchoolofTrafficandTransportationEngineering，CentralSouthUniversity，Changsha410075，ChinaE—mail：whcsu@163．comWANGHong·FUZhuo·ZUO

2、WuGeneficalgorithmforpickmgroutingproblemin2-blockwarehonse．Computer歪趣；iII∞ri雌andApplications．2009。45(6)：224--228．Abstract：Pickingoperatingcosts黜theimportantpartofthelogisticscosts．Accordingtothecharacteristicofthepickinglout--ingprobleminthe2-blockwareho

3、use。themathematicalmodelisestablishedforthisproblemandacorrespondinggeneticalso-rithmisdesignedforit．ThepickingroutingproblemissolvedbyS-shapealgorithm，dynamicprogramming，andproposalgeneticalgorithmrespectively．TheresultsshowthatitCallsignificantlyreducet

4、hedistanceandtimesofpickingroutingtOsolvetheproblembyproposedgeneticalgorithm．Keywords：logistics；picking；pickingrouting；vehicleroutingproblem；geneticalgorithm摘要：拣货作业成本是物流成本的重要组成部分。根据物流配送中·心传统双区型仓库拣货路径问题的特点，建立了数学模型，并设计了相应的遗传算法来求解该问题。在算例中，通过与传统穿越策略、S形启发式算法和

5、动态规划方法的比较，结果表明以遗传算法优化拣货路径问题，可以明显减少拣货路径的距离及拣货作业时间，具有良好的实用性。关键词：物流；拣货；拣货路径；车辆路径问题；遗传算法DOI：10．37780．issn．1002—8331．2009．06．065文章编号：1002—8331(2009)06-0224---05一文献标识码：A中图分类号：Tlr391在物流配送中心的各项内部作业中，拣货作业是一项重要且繁琐的工作。通常拣货作业是指按订单分拣，将顾客所订的货物从仓库中挑选出来发货的业务。按订单拣货作业要投入仓库

6、作业的一半以上的人力，至少要占配送中心全部作业时间的30％一40％1t1，是左右配送中心生产率能否提高的重要作用环节。订单拣取路径问题是一种典型的组合优化问题，合理安排对订单中货物的拣取顺序，可以减少拣货人员拣货过程中的行走距离，加快订单拣取速度、缩短客户等待时间，对提高配送中心的竞争力具有重要的意义。在规模较小时，该问题可用分支定界法等求解，但是随着问题规模的增大，求解的复杂度将呈指数增长，传统的优化方法显得无能为力。Goetschalekx&Radiff等阳提出使用经验启发式算法(如S-shapeAl

7、gorithm)和动态规划方法优化拣货路径，但这些方法都是在一定的拣货规则下的寻优，优化效果不是太好，而且只能处理单次车的拣货路径的优化。陈伊菲、刘军p晤用运输路径TSP以及VRP模型设计分析了仓库中心拣货路径，用扫描算法将待拣货物分车，每次车的货物用Dijkstra方法求最短路径。但是用该方法分车影响了最终的优化效果，且Dijkstra方法只能处理小规模问题。林雨秦等-o设计蚁群算法处理了该问题，但他们仅考虑了单次车路径的优化。本文针对拣货路径问题的不同特点，先将该问题分类成一单一车和一单多车两种情况，

8、并设计相应的遗传算法分别求解。1物流西已送中心拣货作业1．1问题描述双区型仓库一般是由一定数量的等长巷道组成，巷道两侧的货架上存放着需要拣取的各种物品。横向有三条过道，不同于单区型仓库(single—blockwa陀hou跎)的是：除巷道上下两端分别有过道外，中间还有一条过道(如图1中的过道6)，而单区型仓库缺少中问这条过道。据相关文献分析，该条中间过道在提高大型仓库拣选效率方面有很大帮助s．11～。整个仓库平面图如图1所示，