logo资料库

论文研究-物流配送中心拣货路径优化算法的研究 .pdf

发布时间：2022-05-30 发布人：admin 分类：说明书 资料大小：0.44M 资料格式：pdf 举报 版权申诉
第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
资料共8页，全文预览结束
    中国科技论文在线 http://www.paper.edu.cn 物流配送中心拣货路径优化算法的研究# 陈丽，敖日格乐，黄利刚* （沈阳工业大学信息科学与工程学院，沈阳 110870） 5 摘要：在物流配送中心的各项内部作业中，拣货作业是一项重要且耗时的工作，把 RFID 技 术应用于仓储管理中，货物精确定位且信息实时反馈，快速无纸化订单传送。对此结合遗 传算法和模拟退火算法的优点，给出了混合遗传退火算法在基于 RFID 的仓储配送中心的拣 货路径优化中的应用，仿真结果表明，该算法有效缩短拣货路径长度节约拣货时间，适用 于基于 RFID 仓储配送中心的路径优化中。 关键词：拣货作业；RFID 技术；混合遗传退火算法；路径优化 中图分类号：TP391.9 10 15 20 25 Logistics Distribution Center Study Solves the Order Picking Optimization Algorithm CHEN Li, AO Ri-ge-le, HUANG Ligang (School of Information Science and Engineering Shenyang University of Technology, Shenyang 110870) Abstract: Among all kinds of internal operations in the logistics distribution center, Picking operation is an important and time-consuming work.,By applying RFID technology in warehouse management, It helps Accurate location, Real-time feedback information of goods and rapid paperless order delivery. Combined with the advantages of genetic algorithm and simulated annealing algorithm, This paper proposes hybrid genetic annealing algorithm and applies it in order picking optimization in a distribution center of the storage based on the RFID,The simulation results show that the algorithm effectively shortens the picking path length to save time and perfectly applies to the path optimization of storage based on RFID distribution center. Key words: picking the homework; RFID technology; mixed genetic annealing algorithm; path optimization; 30 0 引言 35 40 随着近几年在中国电子商务的快速发展，各物流公司也雨后春笋搬崛起，仓储和配送中 心越来越成为企业关注的焦点。一些商业企业、制造企业和物流企业纷纷构建自己的配送中 心和配送体系，以期降低物流成本，提高物流服务水平[1-2]。如何提高配送中心的管理和运 作水平，己经成为这些企业急需解决的问题。而在配送中心内，拣货作业是配送中心的核心 作业环节，拣货作业成本占到整个配送中心物流成本的 40%[3]左右，其效率的高低直接影响 到整个配送中心的运作效率，订单拣取路径问题是一种典型的组合优化问题，合理安排对 订单中货物的拣取顺序，可以减少拣货车辆拣货过程中的行走距离，加快订单拣取速度、 缩短客户等待时间，对提高配送中心的竞争力具有重要的意义。 目前我国大多数企业中，人工拣选仍占有相当大的比重，所以引进相关硬件和软件技术； 研究拣货路径优化问题，对降低拣货路径，缩短拣货时间，从而提高客户服务水平具有十分 重要的意义[4]。李振、胡庆东等运用运输路径 TSP 以及 VRP 模型设计分析了仓库中心拣货 路径，用基于小生境遗传算法求最短路径[5]，但他们仅考虑了单次车路径的优化。孙慧，张 柯等探建立了拣货车容量受限的 TSP 模型，并基于遗传算法，设计一种启发式算法对拣货 基金项目：国家自然科学基金（51105257） 作者简介：陈丽(1969- ),女副教授,主要研究领域为智能机器与系统. E-mail: argol666@163.com - 1 -
    中国科技论文在线 http://www.paper.edu.cn 路径进行优化处理[6],但是优化效果有待改进而且没能考虑订单的动态实时性对拣货路径的 影响。故本文引进 RFID 技术并针对拣货路径问题建立了数学模型,设计了混合遗传退火算法 45 求解。 因为遗传算法全局优化能力较强, 但局部搜索能力较差；模拟退火算法具有较强的局部 搜索能力；因此可以将遗传算法和模拟退火算法相互结合,取长补短[7-11]。为了克服遗传算法 和模拟退火算法各自的缺点, 发挥它们的优势，本文设计了混合遗传退火算法；并将该算法 50 应用到基于 RFID 的仓储拣货路径优化中，仿真结果表明，此算法收敛速度快，寻优能力强， 能取得较好优化效果。 1 研究对象的选择 双区型仓库一般是由一定数量的等长巷道组成，巷道两侧的货架上存放着需要拣取的各 种物品。横向有三条过道，除巷道左右两端分别有过道外，中间还有一条过道(如图 1)[12]。 据相关文献分析，在现实中该条中间走道在提高大型仓库拣选效率方面有很大帮助。所以本 55 文选择该类仓库为问题的分析对象，并设计相应的算法。 为了进行计算，需要对仓库模型的数据进行具体的说明。在仓库中共有三个过道，过道 距离 a=2m 存储位置的长和宽均为 1m 即 b=c=1m 巷道宽度 d=1.5m 对于垂直方向上的位移忽 略不计。 60 1.1 双区型仓库平面布局模型图 图 1 双区型仓库布局图 1.2 货位的编码及距离计算 为了方便的解决储位点之间距离计算的问题，需要先对仓库的任意一个储位点进行编 65 码，具体的编码方式为: [分区编号 巷道号 巷道左右两侧编号 货架号]。 例如：在图 1 中标有 1 的货架编码为[1 1 1 1]，标有 8 的货架码为[1 1 2 4]。 拣选起始点的位置设为[0 0 0 0]，这种储位编码方式非常放便进行扩展，例如在具体的 订单中，可以在编码的后面加上容量和重量信息： 70 例如：编码[2 5 2 9] [4] [2]，意思是需要拣取的货品位于第 2 个分区，第 5 巷道的右侧 第 9 个货位上，容积为 4 个单位(立方分米 dm3) 其质量为 2 个单位(千克 kg)。 对货位进行编码的目的是为了进行计算任意两个货位之间的距离，对于任意两个货位之 - 2 -
    中国科技论文在线 http://www.paper.edu.cn 间的距离计算，例如[x1 x2 x3 x4]和[x1 ' x2 (1) 计算穿越的过道距离，其值为 ' x3 ' x4 ']，采用如下的步骤进行求解: ； 75 (2) 计算穿越的巷道距离，其值为 ； (3) 计算穿越的货位距离，在计算该距离的时候需要按照以下两种情况进行处理: (a) x1 和 x1 '相同，说明处于同一个分区中，然后再看 x4 和 x4 ' ，会出现两种不同的行走 策略，如图 2 所示。则取值 ,即选取两种策略中的较小 行走距离方案，两个值相同则随机选取一个。 80 (b) x1 和 x1 '是不相同，说明两个拣选货位不在同一个分区中，如果 ，则穿越的 货位距离 ；如果 则距离为 。 策略 1 策略 2 85 N 穿越货位距离 图 2 路径选择策略 开始 穿过 过道距离 穿过 巷道距离 是否同区 Y 是否同巷道 N Y 穿越货位距离 1 穿越货位距离 2 合计储位距离 结束 图 3 货位距离计算流程图 - 3 - '1lx x*a'22x x*d + 2c''4444min(x x 2 ,40 x x)'1lx x'44x- 120 - x'1lx x'44x120 x
    中国科技论文在线 2 拣货作业数学模型建立 http://www.paper.edu.cn 分析可知，拣货路径优化问题可以视为 TSP 问题。因此建立数学模型如下： 约束条件： 90 95 1 拣完货品 i 后立即拣货品 j yij= m：表示配送中心拣选设备的数目 m=1,2,…,M； 100 n：代表待拣选货品的品相数目 n=1,2,…,N； 0 否则 ...... i：代表拣选路径的条数 i=1, 2, 3,……； mx：货品 x 的质量需求； vx：货品 x 的容量需求； V：代表拣选设备 m 的载货容积能力； 105 M：代表拣选设备 m 的载货质量能力； x, y：代表待拣选货品中的任意一种； dixy：代表拣选路径 i 上货品 x 和 Y 之间的距离； Si 1：代表拣选路径 i 上第一个拣选货品到出入口距离； n：代表拣选路径 i 上最后一个拣选货品到出入口距离； Si yixy：决定拣选路径 i 上货品 x 和货品 y 是否相邻； 模型目标函数(1)式表示进行拣选路径优化后使得总的拣选行走距离最短。约束条件(2) 110 和(3)代表任一货品只存在于一条拣选路径上，只被拣选一次即可。约束条件(4)和(5)代表所 有货品的容量和载重量需求不能超过所有拣选设备的拣选能力。约束条件(6)为决策变量， 如果在拣选路径上拣选完货品 x 后立即拣选货品 y 则为 1，否则为 0。 115 3 拣货作业路径优化算法的实现 本文混合遗传退火算法的基木思想是:将遗传算法与模拟退火算法相结合，构成一种混 合遗传退火算法。遗传算法是从一组随机产生的初始解(初始群体)开始全局最优解的搜索过 程，它先通过选择、交叉、变异等遗传操作来产生最优解，然后再对遗传算法所得得最优解 进行模拟退火。这个运行过程反复迭代地进行，直到满足 T=0 条件为止。混合遗传退火算 120 法将遗传算法和模拟退火算法的优点充分结合了起来，大大提高了算法的优化效果。 - 4 - 1nixyixyiim1x1y1f(x)min(dy+ s+ s)1MNN ixyx1y 1 y1,2,3N2N ixy y1y 1 x1,2,3N3Nxx1v4NVxx1m5NM6
    中国科技论文在线 3.1 遗传算法部分 1、 确定订单编码方式 http://www.paper.edu.cn 本文采取自然数的编码，在计算的过程中，首先对拣选设备按照顺序进行排列，例如 第一个拣选设备对应第一个路径中的货品拣选，这样编码中的货品与拣选设备就可以对应 125 起来。 具体操作如下: 例如一个订单或一批订单中有 N 个货品需要从配送中心的仓库中进行拣选，这 N 个货 品均用自然数编码来表示自己。货品的所在的存储位置通过 RFID 准确知道，即根据自然 数能够推出货品的种类以及货品存储的位置。引入自然数 0 来代表仓库的出入口，也就是 130 拣选作业的起始地点。假如需要拣选的货品的拣选路径为: 路径:起始点 0 货品 1 储位点 货品 2 储位点 货品 3 储位点 ……货品 N 储位 点 起始点 0 上述的拣选路径用自然数编码可以表示为: (0,1,2,3……N,0) 上面的编码解释为:配送中心中有一辆拣货车辆，在本次拣选的货品为 1, 2, 3……N， 135 货品数目为 N，当货品的重量或体积达到拣货车辆的最大承载重量或体积时返回到起始点 （本文设车辆最大载货重量为 60kg，最大载货容量为 120dm3）。对于配送中心拣选设备 的数目没有限制，即可以是单个拣选设备也可以是多个拣选设备。 2、确定适应度函数和设计选择策略 适应度函数的确定也是遗传算法设计过程中的核心问题，适应度函数直接关系到染色 140 体的选择和交叉操作。对于染色体应用适应度函数所求的适应值只能为正值，所以拣选路 径优化问题的适应度函数也不能使用原始适应度函数。拣选路径优化问题的适应度函数采 取如下所示: 145 f(x)n:适应度函数值 f(x):该路长 f(x)min:当前最短路长 在选择策略的设计上，拣选路径优化问题，其设计的目标函数为求最小值，同时目标函 数的值能够直接代表遗传算法中染色体的优劣程度，因此拣选路径优化问题的选择策略使每 个染色体被选择的概率按照如下公式进行计算: 150 2、 交叉算子的设计 在进行交叉运算以前，首先用适应度函数评价父代的适应度值，然后按照适应度值的优 劣通过选择算子选出用于进行交叉操作的染色体。由于订单的编码中含有拣选货物序列号， 对选择的个体直接进行交叉往往会产生不可行解，即部分货品可能重复出现在拣选序列中， 而另外部分货品可能被遗漏，没有被拣选，这样的拣选序列是符合要求的。因此，本文对序 155 列编码运用部分匹配交叉算(Partially Matched Crossover Operator,PMX)，对实数编码采用算 术交叉算子。 - 5 - nmin1fxfxfx+1......(7) iii1fxpx = .......(8)f(x)Ni
    中国科技论文在线 http://www.paper.edu.cn 为了更简单地描述上述部分映射交叉操作的工作过程, 下面以两个简单的 A、B 染色体 为例进行说明： 160 首先, 随机选取染色体中的两个位置, 并根据这两个位置定义子串, 再通过交换两个染 色体中的子串来产生原型子代个体。假设选取的位置分别为 3 和 6, 则产生的原型子代个体 为： 接着, 建立两个子串之间的映射关系如下: 165 A 2 6 3 B 9 1 4 5 最后, 根据上述映射修复原型子代个体, 产生如下可行子代： 170 4、变异算子的设计 变异操作是为了在运算过程中能改变某些成员的值，以避免失去一些有用的基因，防止 某些成员的值处于不变的状态，是一种防止算法早熟的措施。与选择算子相反，变异算子的 作用是增加算法的种群多样性，而在一定程度破坏了算法的收敛性。有效的变异算子要求达 到两个方面的作用: 175 ①改善遗传算法的局部搜索能力。遗传算法使用交叉算子已经从全局的角度出发找到了 一些较好的个体编码结构，他们已接近或有助于接近问题的最优解。但仅使用交叉算子无法 对搜索空间的细节进行局部搜索。这时若使用变异算子来调整个体编码串中的部分基因值， 就可以从局部的角度出发使个体更加逼近最优解，从而提高了遗传算法的局部搜索能了。 ②维持群体的多样性，防止出现早熟现象。变异算子用新的基因替换原有基因值，从而 180 可以改变个体编码串的结构，维持群体的多样性，这样就有利于防止出现早熟现象。 本文采用连续多次对换的变异技术，使可行解有较大的顺序排列上的变化，以抑制“进 化逆转”的同化作用。本文设计变异发生概率 Pm=0.3，连续多代目标值没有下降时强制保留 最优个体，停止“进化逆转”。 3.2 模拟退火算法部分 185 本文为了加快搜索的速度，通过较小的代价获得一个具有较高适应值的路径作为初始路 径。考虑到遗传算法的全局搜索优势，在初始解的选择上采用遗传算法迭代一定次数后的解 作为模拟退火算法的初始解。所以步骤如下： (1) 初始化：初始温度 T=4(经过多次仿真实验最合适)，初始解为遗传算法所得的最优 解，T 值的迭代次数 40。 190 (2) 对 j=1，…，2000 循环执行第(3)第(4)步； (3) 随机扰动产生新解 Xtemp； (4) 若 df<0 则，更优解以概率 1 接受，若较差的解以概率 exp(-df/T)接受 Xtemp 作为新 的当前解； - 6 - A 1 2 3 4 5 6 7 8 9B 4 5 6 9 1 2 7 3 8A 1 2 6 9 1 2 7 8 9B 4 5 3 4 5 6 7 3 8A 5 3 6 9 1 2 7 8 4B 9 1 3 4 5 6 7 2 8
    中国科技论文在线 http://www.paper.edu.cn (5) 降温：T=T-0.1，如果满足终止条件 T=0 则输出当前解作为最优解，终止算法输出 195 结果。 4 仿真结果及分析 图 4 修正遗传算法仿真结果图 200 图 5 混合遗传退火算法仿真结果图 本文设拣货车辆从仓库的货架上随机拣 100 个不同货品（目前无法通过 RFID 获得货品 - 7 - 050100150200250300350400450500200022002400260028003000320034003600迭代次数f(x)最优解050100150200250300350150020002500300035004000迭代次数f(x)最优解
    中国科技论文在线 http://www.paper.edu.cn 准确位置），通过两种算法仿真结果显示（图 4，5），本文算法仿真结果优于修正遗传算 法。在开始迭代后，本文算法 f(x)最优解在 1800 附近，明显优于修正遗传算法的最优解； 205 并且迭代次数在 350 附近就开始收敛于最优解，收敛速度快于修正遗传算法的 500 次左右； 总路径长度比修正遗传算法缩短 400 米左右。仿真结果表明，本文提出的混合遗传退火算法 对解决基于 RFID 仓储配送中心拣货路径问题有较好的优化作用。 5 结论 把 RFID 技术应用于仓储管理中可以实时检测到货物的准确位置和相关信息，再合理地 210 选择拣货路径对于降低物流配送中心运营成本、提高配送中心工作效率和客户满意度等方面 具有重要作用。针对订单拣选特点，建立了相应的拣货路径数学模型，并设计混合遗传退火 算法对其进行了求解，求解结果表明本文所设计算法相比修正遗传算法能很好的优化配送中 心的拣货路径问题，从而减少配送中心的拣货时间，提高运作效率。 参考文献 215 [1] 王永波，温佩芝，李丽芳，张建军.大型仓储拣货路径优化算法研究[J].计算机仿真学报，2013，30（5）： 337-340 [2] Roodbergen K J，de Koster R.Routing order pickers in a warehouse with a middle aisle[J].European Journal of Operation Research，2001，133（1）：32-43. [3] 李振 胡庆东 张国英 马湘 基于小生境遗传算法的人工拣货路径优化研究[J].物流科技学报 2011 （6）： 85-88 [4] 王占磊 配送中心订单分批及拣选路径优化问题研究[D].长春：吉林大学 ，2013. [5] 李哲，田征 物流中心拣货单处理及拣货路径优化研究[D].大连：大连海事大学，2011. [6] 孙慧，张柯，张富金，张纪会 基于遗传算法的双区型仓库人工拣货路径优化[J].青岛大学学报，2014， 29（1）：79-82. [7] Andresen M, Brasel H, Moring, et al. Simulated Annealing and Genetic Alogrithms for Minimizing Mean Flow Time in an Open Sho[J].Mathemetical and Computer Modelling,2008,48(7/8):1279-1293. [8] 刘爱军 [9] 郭丹丹 [10] 任昊南 [11] WANG Pengtao,LIU Yanliang,WU Jing,Solving lo-gistics transportation based on genetic simulated annealing algorithm[J].Journal of Computational Information System,2008,4(2):559-564. [12] 王宏 224-228 含精英策略的小生境遗传退火算法研究及其应用[J].中国机械工程学报，2012，23（5）：556-563. 基于模拟退火混合遗传算法的多式联运优化问题的研究[D].大连：大连海事大学，2012. 用遗传算法求解 TSP 问题[D].济南：山东大学，2008. 2009，45（6）： 基于遗传算法的双区型仓库拣货路径优化研究[J] 计算机工程与应用 左武 符卓 220 225 230 235 - 8 -
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料