仓库拣货路径问题研究文献综述

    王赛男

    摘 要：仓库分为传统仓库和非传统仓库，拣货路径问题是仓库研究重大课题，本文通过整理国内外文献对此问题进行综述。

    关键词：拣货路径;仓库

    0 引言

    1959年，国外学者 Dantzig等首次提出拣货路径问题，这个问题是由仓库中的订单拣货所产生的。1976年，S. Sahni等证明了仓储分配问题是NP-Hard问题。从此，拣货路径问题引起了广大国内外学者的关注，对该问题的研究也被赋予重大的理论意义和实际意义。

    1 国内外文献综述

    1.1 国内拣货路径问题研究现状

    国内关于仓库拣货路径问题的研究，大致可以按照仓库类型分为平面仓库和立体仓库两大类。由于在平面仓库中拣货员在水平方向的多变性和堆垛机在垂直方向的恒定性，大多数学者对拣货路径的研究还是基于平面仓库。

    1.1.1 平面仓库拣货路径研究

    （1）关于不同规模大小的仓库拣货路径问题研究

    国内学者对平面仓库的拣货路径问题研究中，最具有代表性的是传统仓库中的双区型仓库。2011年，李振等将拣货路径优化问题先转化成TSP（Traveling Salesman Problem）问题，在不考虑拣货车承载量约束前提下，采用小生境遗传算法求取拣货作业的最优路径。2014年，李建斌等对双区型仓库建立TSP模型，分别采用蚁群算法、模拟退火算法和禁忌搜索对该问题进行求解，进而得出不同待拣货品数量下各算法的优劣程度，待拣货品数量较少时采用模拟退火算法收敛速度相对较快，待拣货品数量较多时采用蚁群算法可以在更短时间内得到相对较优解。在非传统仓库方面，2013年，蒋美仙等在Fishbone式仓库的基础上进行改进，并结合贯通式货架系统，有效地缩短了仓库总拣货距离。2017年，刘少华对Fishbone式仓库建立拣货路径优化模型，并分别采用遗传算法、蚁群算法和布谷鸟算法三种智能算法进行求解，将三种算法对拣货路径的优化效果进行了对比。2019年，张志等对单叶Leaf式仓库进行改进，提出了双叶Leaf式仓库，与单叶Leaf式仓库相比，在存储空间和总拣货距离上都有所改善。

    （2）增加车载能力约束的仓库拣货路径问题研究

    2009年，王宏等将传统双区型仓库拣货路径问题转化为车辆路径问题（Vehicle ?Routing ?Problem，VRP），也称车辆调度问题（Vehicle ?Scheduling ?Problem，VSP），考虑了拣货车承载量约束，将该问题分为一单一车和一单多车两种情形，并分别设计了遗传算法进行求解。2010年，雷娟娟根据双区型仓库中拣货路径问题的特点，将该问题分成不考虑拣货车辆容积和考虑拣货车容积两种情况，针对不考虑拣货车容积的情况，采用蚁群算法优化求解其拣货路径问题。但是，他们在考虑拣货车承载量约束的同时，要求每个待拣货位需要拣取的货物重量不能超过拣货车的承载量，也就是说拣货员到每个待拣货位只能经过一次。考虑到现实生活中商品的季节性需求和顾客对商品的偏好等，某个待拣货位上需要拣取的货物重量非常有可能超过拣货车的承载量，拣货员也会重复经过某个待拣货位。在此基础上，2014年，孙慧等运用TSP模型分析双区型仓库的拣货路径，基于遗传算法求解，并通过仿真对是否考虑建货车承载量约束的最优拣货路径进行了对比，说明了考虑承载量约束的有效性和实用性。

    1.1.2 关于立体仓库拣货路径问题研究

    2017年，胡国松等考虑到库存周转率的情况，以可移动式货架的立体仓库为研究对象，建立拣货路径模型，分别采用蚁群算法和遗传算法进行求解。2018年，李云以备品备件仓储系统作为研究对象，设计出一套以自动化立体货架为主体的备品备件仓库方案，并基于Flexsim仿真软件对设计方案进行建模与仿真。

    1.2 国外拣货路径问题研究现状

    1.2.1 传统仓库拣货路径问题研究

    2004年，Hwang等将商品依据每类体积指标决定储位，考虑返回策略、穿越策略和中间返回策略，并建立其在偶数及奇数储存通道下总期望行走距离的公式，并把模拟的结果作比较以确定其正确性。2005年，T.Le-Duc等建立了估计拣货巡回行走距离平均值的概率模型，并提出了一种双选择交换启发式算法来解决仓储的分区问题。2008年，Roodbergen等對单区型、双区型和多区型仓库的期望拣货距离进行了研究。2016年，Scholz等将传统仓库布局的具体结构考虑在内，运用数学规划分别对TSP问题中拣货员的订单拣货路径进行了优化。

    1.2.2 不同存储策略下的仓库拣货路径问题研究

    1991年，Jarvis同样根据仓库历史数据模拟产生了未来不同货品的入库概率，并为待入库货品设计了一种新的储位指派方法，以使其获得最佳储位点，进而便可获得更少的平均拣货时间。1996年，Hausman分别研究了自动化仓库中 ABC分类法与固定存储、随机存储和分类存储三种方式组合使用的情况。结果发现：固定存储策略所得的拣货路径长度要比随机存储策略所得的路径长度更短。

    1.2.3 非传统仓库拣货路径问题研究

    2009年，美国学者Gue和Meller突破传统仓库的特征，研究提出并实际应用了两种非传统仓库——Flying-V和Fishbone式仓库。这两种非传统仓库分别能比传统仓库在总拣货距离缩短约10%和20%，大幅提高了仓库拣货效率。同年，Pohl等研究了双项作业指令下的Fishbone式仓库优化问题。结果发现，双项作业指令情形下会显著降低Fishbone式仓库相对传统仓库的优势。2012年，.ztürkoglu等基于在传统仓库中增加主通道条数和优化主通道与拣货通道角度的思想，研究提出了Chevron、Leaf和Butterfly等三种非传统仓库。研究分析表明，这三种非传统仓库在总拣货距离上分别能比传统仓库缩短约19.53%、21.72%和22.52%。

    2 总结

    可以看出，大部分国内学者的研究局限于传统仓库，研究方法从启发式路径策略、数学最优化方法演变到现在的智能优化算法;国外学者的研究更加趋向于基于传统仓库进行布局改进，从建模优化、算法设计或仿真优化的角度对新布局进行更深入的研究。但是，国外学者的建模优化大部分是在单元货载或者是双向作业指令情形下，以托盘为拣货单位，对总拣货距离进行建模仿真分析。

    参考文献

    [1]刘少华. 多种智能算法在鱼骨布局拣选路径决策中的比较研究[D].北京物资学院，2017.

    [2]张志勇，王琴，梁艳.仓库内部布局的双叶Leaf方法及其通道角度优化[J].系统工程，2019，37（02）：70-80.