B2C电子商务仓库拣货路径优化策略应用研究

第２３卷第１期　２０１４年２月　运　筹　与　管　理　

０ＰＥＲＡＴＩＯＮＳ　ＲＥＳＥＡＲＣＨ　ＡＮＤ　ＭＡＮＡＧＥＭＥＮＴ　ＳＣＩＥＮＣＥ　Ｖｏ１．２３．Ｎｏ．１　Ｆｅｂ．２０１４　

Ｂ２Ｃ电子商务仓库拣货路径优化策略应用研究　

李建斌　，　周玮　，　陈峰　

（１．华中科技大学管理学院，湖北武汉４３００７４；２．上海交通大学工业工程与物流工程系，上海２００２４２）　

摘　要：当前国内Ｂ２Ｃ电子商务仓库多为人至物的拣货模式，拣货作业成为其核心作业之一，占据仓库大量时　间成本和资金成本，拣货路径优化成为企业亟需解决的问题。本文基于ＴＳＰ对拣货路径进行建模，利用蚁群算　法、模拟退火算法和禁忌搜索对该ＮＰ—ｈａｒｄ问题进行求解，并同当前企业普遍采用的ｓ型启发式策略进行对比，　拣货时间节约１３．３５％。进一步得出当拣货品数量较少时应采用模拟退火算法求解，而当拣货品数量较大时采　用蚁群算法仅进行一次迭代，则可以实现短时间得到相对较优的解。所得结果已应用于某大型电子商务企业，　效果明显。　关键词：拣货路径问题；电子商务；蚁群算法；Ｓ型启发式策略　中图分类号：Ｆ２２４　文章标识码：Ａ　文章编号：１００７—３２２１（２０１４）０１—０００７．０８　

Ａｐｐｌｉｅｄ　Ｏｐｔｉｍａｌ　Ｓｔｒａｔｅｇｉｅｓ　ｆｏｒ　Ｗａｒｅｈｏｕｓｅ　Ｐｉｃｋｉｎｇ　Ｒｏｕｔｉｎｇ　ｉｎ　Ｂ２Ｃ　

ＬＩ　Ｊｉａｎ．ｂｉｎ　，ＺＨＯＵ　Ｗｅｉ　，ＣＨＥＮ　Ｆｅｎｇ　（１．Ｓｃｈｏｏｌ　ｏｆ　Ｍａｎａｇｅｍｅｎｔ，Ｈｕａｚｈｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ　４３００７４，Ｃｈｉｎａ；　２．Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｉｎｄｕｓｔｒｉａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ｌｏｇｉｓｔｉｃｓ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｓｈａｎｇｈａｉ　Ｊｉａｏ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ　２００２４０，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｍｅｎ—ｔｏ—ｔｈｉｎｇ　ｐｉｃｋｉｎｇ　ｍｅｔｈｏｄ　ｉｓ　ｗｉｄｅｌｙ　ｕｓｅｄ　ｉｎ　ｅｘｉｓｔｉｎｇ　Ｂ２Ｃ　ｗａｒｅｈｏｕｓｅ　ｉｎ　Ｃｈｉｎａ，ｉｎ　ｗｈｉｃｈ　ｐｉｃｋｉｎｇ　ｉｓ　ｏｎｅ　ｏｆ　ｔｈｅ　ｃｏｒｅ　ｗｏｒｋｌｏａｄｓ　ａｎｄ　ｉｔ　ｔａｋｅｓ　ａ　ｌｏｔ　ｏｆ　ｔｉｍｅ　ａｎｄ　ｃａｐｉｔａ１．Ｗａｒｅｈｏｕｓｅ　ｐｉｃｋｉｎｇ　ｒｏｕｔｉｎｇ　ｉｓ　ａｎ　ｉｍｐｏｒｔａｎｔ　ｐｒｏｂ－　ｌｅｍ　ｉｎ　ｅ—ｃｏｍｍｅｒｃｅ．Ｂａｓｅｄ　ｏｎ　ＴＳＰ．ｗｅ　ｂｕｉｌｄ　ａ　ｐｉｃｋｉｎｇ　ｒｏｕｔｉｎｇ　ｍｏｄｅｌ　ｗｈｉｃｈ　ｉｓ　ＮＰ—ｈａｒｄ　ａｎｄ　ｓｏｌｖｅｄ　ｂｙ　ａｎｔ　ｃｏｌｏｎｙ　ａｌｇｏｒｉｔｈｍ，ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ａｌｇｏｒｉｔｈｍ，ｔａｂｕ　ｓｅａｒｃｈ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　Ｓ—ｓｈａｐｅ　ｈｅｕｒｉｓｔｉｃ　ａｌｇｏｒｉｔｈｍｓ，ｒｅｓｐｅｃｔｉｖｅｌｙ．　Ｔｈｅ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｐｉｃｋｉｎｇ　ｔｉｍｅ　ｂｙ　ａｎｔ　ｃｏｌｏｎｙ　ａｌｇｏｒｉｔｈｍ　ｓａｖｅｓ　ｔｉｍｅ　ｂｙ　１　３．３５％ｃｏｍｐａｒｅｄ　ｗｉｔｈ　ｔｈａｔ　ｂｙ　Ｓ－ｓｈａｐｅ　ｈｅｕｒｉｓｔｉｃ　ａｌｇｏｒｉｔｈｍｓ．Ｆｕｒｔｈｅｒｍｏｒｅ．ｗｅ　ｏｂｔａｉｎ　ａ　ｒｅｌａｔｉｖｅ　ｏｐｔｉｍａｌ　ｓｏｌｕｔｉｏｎ　ｉｎ　ｓｈｏｒｔｅｒ　ｔｉｍｅ　ｗｉｔｈ　ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｗｈｅｎ　ｔｈｅ　ｎｕｍｂｅｒ　ｏｆ　ｐｉｃｋｉｎｇ　ｇｏｏｄｓ　ｉｓ　ｓｍａｌｌ，ｗｈｉｌｅ　ｔｈｅ　ａｎｔ　ｃｏｌｏｎｙ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ａｃｈｉｅｖｅ　ｔｈｅ　ｒｅｌａｔｉｖｅ　ｏｐｔｉｍａｌ　ｒｅｓｕｌｔｓ　ｗｉｔｈ　ｏｎｌｙ　ｏｎｅ　ｉｔｅｒａｔｉｏｎ．Ｔｈｅｓｅ　ｒｅｓｕｌｔｓ　ｈａｖｅ　ｂｅｅｎ　ａｐｐｌｉｅｄ　ｔｏ　ｏｎｅ　ｅ—ｃｏｍｍｅｒｃｅ　ｂｕｓｉｎｅｓｓ　ａｎｄ　ｈａｖｅ　ｂｅｅｎ　ｅｆｆｅｃｔｉｖｅ．　Ｋｅｙ　ｗｏｒｄｓ：ｐｉｃｋｉｎｇ　ｒｏｕｔｅ　ｐｒｏｂｌｅｍ；Ｅ－ｃｏｍｍｅｒｃｅ；ａｎｔ　ｃｏｌｏｎｙ　ａｌｇｏｒｉｔｈｍ；Ｓ－ｓｈａｐｅ　ｈｅｕｒｉｓｔｉｃ　ａｌｇｏｒｉｔｈｍｓ　

０　引言　

电子商务的迅猛发展使得仓库效率成为了焦点话题，拣货作业作为仓库的核心作业之一，在整个仓库　

的作业中占有十分重要的地位。拣货作业是指根据订单要求，在尽可能短的时间内将拣货位的货品拣出，　并依照特定的方式集中货品待分拣的作业。常规的拣货作业劳动量占用仓库作业量的６０％，而其移动成　

本占９０％左右，拣货作业时间至少要占配送中心全部作业时间的３０％～４０％。所以说，拣货作业是仓库作　

业的核心部分。尤其是在采取人至物的拣货方式的仓库中，拣货路径对仓库效率的影响尤为突出。如何　能在短时间内得出最优的拣货路径以缩短拣货行走距离，成为现在研究者感兴趣的一个问题。　

传统仓库为单区型仓库，即仓库内仅有一排并列摆放的货架，与货架垂直的过道仅有仓库边缘处两　

收稿日期：２０１２－１１－２７　基金项目：国家自然科学基金资助项目（７１１７１０８８，７０９０１０２９，７１１３１００４）；教育部新世纪人才支持计划（ＮＣＥＴ．１３．０２２８）　

作者简介：李建斌（１９８０－），男，博士，研究方向：物流与供应链管理、电子商务。　８　运　筹　与　管　理　２０１４年第２３卷　

条，无中间过道。Ｇｏｅｔｓｃｈａｌｃｋｘ和Ｒａｔｌｉｆ　针对此类传统仓库拣货策略提出了穿越策略、分离穿越策略、返　回策略、分离穿越策略、ｚ一启发式策略等共计五种优化拣货方法。Ｈａｌｌ　提出穿越策略、中点策略及最大　

间距法共三种拣货策略并进行比较，结果显示最大间距法拣货较其他二者更优。Ｐｅｔｅｒｓｅｎ　研究指出，当　

待拣货品品种数较多时，建议使用合成策略和穿越策略。Ｈｗａｎｇ等　建立交叉通道返回策略和交叉通道　

穿越策略的求解方法。Ｐｅｔｅｒｓｅｎ和Ｓｃｈｍｅｎｎｅｒ　给出启发式拣货路径的求解方法并考虑基于产品数量的　库存策略。Ｊｅｒｏｅｎ和Ｇａｄｅｍａｎｎ　考虑固定库存策略下的自动化立体仓库最优拣货路径。　

当仓库带有除多条中间过道时成为多区型仓库，特殊地，将只有一条中间过道的仓库称为双区型仓　

库。Ｒｏｏｄｂｅｒｇｅｎ和Ｋｏｓｔｅｒ　比较带过道的仓库和不带过道的仓库，对此二者进行比较后结果显示，前者较　后者在拣货距离上有很大改善。Ｖｓｕｇｈａｎ和Ｐｅｔｅｒｓｅｎ　研究带有过道的仓库，得出中间过道的设计若处于　

最有条件下时，仓库拣货更加灵活，拣货路程缩短，但过多的中间过道将导致拣货效率降低。Ｒｏｏｄｂｅｒｇｅｎ　

和Ｋｏｓｔｅｒ　利用动态规划方法求解最优拣货路径，并比较在不同规模的仓库中的平均拣货时间，结果显示　双区型仓库平均拣货时间最短。李诗珍等　研究在对配送时限要求越来越短的多区型仓库中，配置电子　

标签和ＲＦ手持终端，运用ｓ型启发式方法进行拣货，可以减少大量拣货劳动量。Ｔｈｏ和Ｒｅｎｅ　研究双区　型仓库拣货路径优化问题，文章假定订单以Ｐｏｉｓｓｏｎ分布，研究拣货人员利用Ｓ型启发策略时的优化效果。　

林雨秦等¨　利用蚁群算法求解传统物流仓库的拣货路径问题，并将其同穿越策略进行比较，得出蚁群算　

法可以大幅度减少拣货行走距离。　上述文献对各种策略或算法的原理和效果作了细致研究，但是对策略和算法的在实际应用过程中的　

具体实施方法少有涉及。实际情况中算法运行时间计入拣货总时间，所以要求在保证一定的结果质量的　

同时运行时间尽可能的短，寻求这样的算法以及将模型运用于实际情况的方法即为本文目的。本文以双　区型仓库为例，假设库存策略不变，基于实体仓库基本信息逐步建立拣货路径优化模型，同时优化算法的　

运行时间和收敛度成为是否实用的两大关键指标，将蚁群算法与ｓ型启发式策略、模拟退火算法和禁忌搜　索算法进行计算时间和结果收敛度上的比较，得出不同水平下的各算法或策略的相互间优劣程度。文中　

所述建模和求解过程已在实际拣货系统应用中实现。　

１　仓库拣货路径优化模型描述　

１．１　定义仓库货位编码　

现代电子商务仓库平面图如图１所示，仓库共有多排货　架，每一排称为一个区。仓库边缘处和相邻区之间均有过道，　

每区的货架均有若干列货架并列背对背式摆放，货架间形成　拣货巷道。每列每一列货架含多个ｂａｙ，而每一个ｂａｙ又划分　

为多个库位，可存放多种货物，假定仓库西南角为仓库的出入　口。拣货员沿过道和巷道行走，拣选巷道两旁货架上的货品，　图１　电子商务企业仓库平面图　

形成拣货路径。实际应用中仓库多采用多层货架，所以仓库编号普遍用以描述三维空间。但由于拣货位　

多在底层，故在此文中可忽略垂直距离影响，将拣货路径转化为平面路径，并且假设为折线路径，以此制定　

平面编号规则——ＲｃＢＰ编号规则如表１，其名称中的四个字母分别代表仓库的排（ｒＯＷ）、列（ｃｏｌｕｍｎ）、货　架（ｂａｙ）和货位（ｐｏｓｉｔｉｏｎ）。在后文中以双区型拣货仓库为对象进行拣货路径优化研究，即Ｒ…＝２。　表１　ＲＣＢＰ平面编码　

１．２建立坐标系定义库位坐标　本小节建立仓库内部的坐标系对每一个给定编码的货位求出其坐标。

　第１期　李建斌，等：Ｂ２Ｃ电子商务仓库拣货路径优化策略应用研究　９　

如图２，在双区型仓库里，除仓库边缘两条过道外，仅有双　区间的一条过道，其余为拣货巷道。以仓库西南角进出口０点　为原点，由南向北为Ｙ正方向，由西向东为　正方向建立坐标　系。设西南货架的西南角为点ｓ，坐标为ｓ（　，Ｙ　）。设托盘货架　间距宽为ｄ，每列货架宽度为ｄ　，则两列货架总宽度为２ｄ。。假设　拣货员沿货架边缘行走并拣选货物，拣选时取货位中点计算。　假设某货位编码为Ｒ—Ｃ—Ｂ—Ｐ，其坐标为Ｗ（　，Ｙ）。则货位横　坐标由下式（１）给出：　１　ｆ　＋　ｄ＋（Ｃ一１）・ｄ　Ｃ为奇数时　

＝｛　二　（１）　＋（詈一１）ｄ＋Ｃ・ｄ。　Ｃ为偶数时　图２仓库坐标系　

如图２，记ｙ为货位相对于点ｓ的纵向距离，则货位纵坐标Ｙ为ｙ与Ｙ　之和。　

设一列货架长度（取每排最长货架）为ｚ，两排货架间垂直相距△ｚ。每节（Ｂａｙ）货架内长ｚ　，每节货架　安排Ｐ　ｍａｘ个货位，每个货位占用长度为ｚ　，忽略货架立柱的影响，则有如下关系式：　Ｚ　＝Ｐ　ｍａｘ・ＺＰ　（２）　Ｚ＝Ｂ　ｍａｘ・Ｚ　（３）　而：　Ｙ＝（Ｒ一１）（Ｚ＋△Ｚ）＋（　一１）ＺＢ＋（Ｐ一１）ＺＰ＋ＺＰ÷２　（４）　则货位纵坐标Ｙ为：　Ｙ＝Ｙ＋Ｙ　＝（尺一１）（Ｚ＋△Ｚ）＋（日一１）Ｚ口＋（ＪＰ一１）ｌｐ＋ＺＰ÷２＋Ｙ　（５）　由式（１）～（５）可根据货位编号得出任一货位的坐标。　１．３　生成距离矩阵并建立模型　当波次已生成，待拣ＳＫＵｓ货位已明确时（推荐路线时不需考虑数量），根据货位编号建立距离矩阵，　即求出货物两两间最短行走距离。　．　现考虑任两个ＳＫＵ货位的坐标分别为Ｗ　（　。，Ｙ。），Ｗ２（　，Ｙ　），编号相应为ＥＲ　Ｃ　Ｂ　Ｐ。、ＥＲ　Ｃ　Ｂ：Ｐ　。　设二者最短折线行走距离为ｓ。：。由于货架的存在，ｓ。：有别于坐标系上的两点间最短折线距离。可设：　ｓ１２＝Ｘ１２＋ｙ１２　（６）　式（６）中　：为两点间最短折线行走路径的横向长度总和，ｌ，。　为同一路径纵向长度总和，记ＡＹｉ（ｉ＝１，　２）为货位Ｗ　（　，Ｙ　）与所在货架最南端的距离，即：