房殿军，彭一凡

（同济大学 中德学院，上海 201804）

含多条横向巷道的仓库拣选路径优化研究

房殿军，彭一凡

（同济大学 中德学院，上海 201804）

以含有多条横向巷道的仓库为对象，以行走总距离最短为目标，对其拣选作业路径问题进行了研究，在对该问题进行了数学描述的基础上，通过设定拣选点在去程或回程上的分布规则以及相邻巷道拣选点的作业顺序，开发和实现了一种新的基于组合式规则的启发式算法。同时，分析了不同的拣选巷道长度、拣选巷道数量、拣选点数及横向巷道数量对拣选作业行走总距离的影响。实验结果表明，横向巷道能够明显优化拣选距离，但其数量不宜超过4条。

仓库；拣选作业；路径优化；多横向巷道

1 引言

越来越多的企业为了削减成本和提高生产效率，将目光放到仓储设施和配送中心上，订单拣选作业开始受到管理人员和研究学者的重视。研究表明，拣货作业占仓库总作业成本的比例约为60%［1］。

订单拣选作业是指基于顾客的订单从特定的储存位置获取货物的过程，订单拣选作业的效率取决于储存系统、仓库布局、控制机制等诸多因素，可以通过降低拣选订单所需的时间来减少拣选作业时间，从而提高拣选作业效率。总的拣选时间可粗略地分为订单准备时间、拣货行走时间、搜索货物时间、拣取货物时间等，其中，在人工拣选系统中，行走时间是总拣选时间最大的组成部分，占到50%左右［2］。

为了减少行走时间，可从从以下五个方面着手：（1）通过优化不同待拣选货物的拣选顺序，寻求更好的拣选路径；（2）将拣选区域分成数个工作区即进行作业分区，拣选人员只完成其所委派区域内的待拣选货物；（3）根据特定的分配策略，对货物进行储位分配；（4）对订单进行分批处理，处于同一批次的订单将在一次拣选作业中完成；（5）对仓库的布局进行优化，通过调整和改变仓库设备的尺寸和位置包括存储区的设置，提高仓库的利用率和拣选效率［3］。

本文将提出一种新的拣选路径优化算法，通过对待拣选点的优化排序，缩短拣选路径的距离，从而减少行走时间，提高拣选作业效率。除此之外，并将其运用到含有多个横向巷道的仓库中，通过实验仿真探索横向巷道的数量对拣选距离的影响，并对仓库布局时横向巷道的数目提出了建议。

2 问题描述

本文所考虑的是含多条横向巷道的仓库的拣选路径问题。在仓库中，至少含有两条横向巷道，即位于仓库两端的“前横向巷道”和“后横向巷道”。加入额外的横向巷道，为拣选路径的选择提供更大柔性，从而可能获得更短的行走距离。本文中，将横向巷道编号依照距出入口的远近依次编号，记为“横向巷道1”、“横向巷道2”等。横向巷道将仓库分为多个区，按距出入口的远近，依次被称为“区1”、“区2”等。仓库布局的简图如图1所示。图1中的每个小方格都代表一个储位，黑色填充的方格代表按订单需要拣取的货物所在的储位［4］。

图1 仓库布局简图

仓库呈矩形，竖直方向上的巷道称为拣选巷道，水平方向上的巷道称作横向巷道，横向巷道中并不包含储位，仅被用来转换巷道，即只有进入到拣选巷道中才能拣选货架上的货物。本文假设货架的列数为偶数，每条拣选巷道左右两侧都含有一列货架。在仓库中，拣选人员能够沿着巷道自由通行，并且拣选巷道足够窄，忽略同一拣货通道中左右两边拣货时拣货人员移动的距离。鉴于仓库的出入口位于第一条横向巷道的边缘和中间，对平均拣选路径的影响不超过1%［5］，本文中假设出入口位于仓库的左下角，第一拣选巷道和第一条横向巷道的交界处，同时是拣选任务起始点和终点。

通常情况下，这些横向巷道将仓库分为多个区块，形成多区块的仓库，在拣选路径规划时，按照待拣选点所处分区的不同进行分类，逐个分区进行拣选［6］。在本文中，拣选员将逐条巷道依次拣选货物，横向巷道仅作为拣选员在拣选巷道间移动的通道，而根据横向巷道对仓库所进行的分区，仅作为拣选员在拣选巷道间移动时选择经过的横向巷道的参照。

3 模型介绍及算法求解

拣选路径问题主要是考虑怎样将一次拣选任务中的货物从储位中依次取出，使得此次拣选任务的行走路径最优。这类问题类似于Steiner TSP问题，与经典的TSP问题不同，其所求得的路线不需要经过所有的节点，而且在必要的情况下可以多次经过同一个节点。

3.1 模型假设

（1）各个待拣选点间相互独立；

（2）拣选员在每个待拣选点取货花费的时间是相同的；

（3）拣选通道和横向通道均无行走方向限制；

（4）拣货员执行的拣选任务在出发前既已确定，且拣选过程中不发生变动；

（5）拣选员沿拣选巷道和横向巷道的中间行走；

（6）除最后一个分区外，其余所有分区含有相同排数的货架，且最后一个分区所含有的货架排数不少于其他任一分区含有的货架排数。

3.2 数学模型

Steiner TSP问题一般可以根据0-1规划模型进行求解：

其中：i，j∈Ω—拣选员要经过的拣选点以及Depot，其中i=0表示Depot；dij—拣选点i和j之间的行走距离；ui—拣选点i的拣选顺序，其中u0=1；ω—拣选点和Depot数量总和。

决策变量xij=1表示拣选员决定在完成i点的任务后前往j点（i，j∈Ω，i≠j）。目标函数式（1）要求取得完成一个订单的行走路线的最小值；约束（2）和（3）确保每个任务点有且只有一个前项和后项任务；约束（4）确保拣选路线中不出现子回路；约束（5）是定义决策变量的取值域。拣选路线规划问题的研究目的就是确定拣货点间的拣选顺序，即xij的取值。

3.3 基于组合算法的路径优化原理

本文所提出的组合算法是一种新的启发式算法，在解决拣选路径优化问题上，首先假设拣选员是按照待拣选点的分布状况逐条巷道依次完成拣选任务，其次，联系到mid-point算法和Largest Gap算法，将分布较分散的待拣选点放入回程上拣选，然后，根据拣选员所处的位置同待拣选点的相对位置关系决定待拣选点的拣选顺序。新的组合算法利用了回程时的行走路径，同时，拣选员到达下一待拣选点时总是将行走距离最短的路径作为拣选路径，因而，其在路径优化中体现出更加有效的优化效果。

3.3.1 确定回程中拣选的待拣选点。在mid-point策略中，除了第一个和最后一个有拣选点的巷道要完整穿过，其他巷道根据中点分成前后两部分，位于后半部分的拣选点放入回程中拣选，

在Largest Gap策略中，巷道被最大间隔而不是中点划分成前后两个部分。将以上两种算法所考虑的巷道前后两部分划分依据综合考虑，本文中假设出现以下两种情况巷道内的待拣选点将放到回程中拣选：（1）此拣选巷道中所有的待拣选点都位于仓库的前端，将此巷道内所有的待拣选点放入回程中拣选，如图2a所示；（2）此拣选巷道中拣选点间的最大间隔不小于货架总长的一半时，将此巷道内位于前端的待拣选点放入回程中拣选，如图2b所示。

图2 在回程时拣选的拣选点示意图

3.3.2 拣选巷道内拣选点拣选顺序。拣选员在逐条巷道依次完成拣选任务时，拣选巷道内拣选点拣选顺序的确定原则是从拣选员所在的位置到达下一待拣选巷道内最后一个拣选点时所行走的距离最短。当拣选员到达某条拣选巷道中的最后一个待拣选点时，将此位置作为参照点，在示意图中用实心圆圈表示。根据参照点和下一待拣选巷道内待拣选点的位置关系，确定下一待拣选巷道内的待拣选点的拣选顺序。

记拣选员所处参照点位于分区Z0，第y0排；下一待拣选巷道内最前方的待拣选点位于分区Z1，第y1排；下一待拣选巷道内最后方的待拣选点位于分区Z2，第y2排。若下一待拣选巷道仅含一个待拣选点，则Z1=Z2且y1=y2。则：

当Z0≠Z1≠Z2，即三者不位于同一分区时：

图3 当时，拣选顺序确定示意图

图4 当时，拣选顺序确定示意图

当Z0=Z1=Z2，即三者位于同一分区时，

假设分区Z0由第y3排至第y4排货架构成，则：

图5 拣选顺序确定示意图二

鉴于回程上拣选人员在拣选巷道间移动时，对待拣选点的拣选排序规则仍与去程时相同，因而，在本文的图例中，仅列出了去程时的情况，回程时类似，不再重复说明。

3.3.3 拣选巷道间移动时所经由的横向巷道的确定。在确定下一待拣选巷道内待拣选点的拣选顺序之后，需要根据拣选员此时所处的位置和下一时刻将要到达的待拣选点的位置，来确定拣选员在拣选巷道间移动时所经由的横向巷道。不妨假设，假设下一拣选点位于分区Z1，第y1排。

根据拣选员所处的参照点与下一拣选点间相对位置的不同，可以分为以下三种情况考虑：

（1）参照点位于下一拣选点所处分区之前的分区，即：Z0＜Z1；拣选员将经由横向巷道Z0+1进入下一待拣选巷道，如图6a所示；

（2）参照点位于下一拣选点所处分区之后的分区，即：Z0＞Z1，拣选员将经由横向巷道Z0进入下一待拣选巷道，如图6b所示；

（3）参照点同下一拣选点位于同一分区，即Z0=Z1，若y0+y1≥y3+y4，则拣选员将经由横向巷道Z0+1进入下一待拣选巷道，如图6c所示；若y0+y1＜y3+y4，则拣选员将经由横向巷道Z0进入下一待拣选巷道，如图6d所示。

图6 拣选员进入下一待拣选巷道示意图

组合算法的具体流程如下：

Step 1：找出所有含有待拣选点的拣选巷道，并定义拣选巷道编号最小即最靠左的拣选巷道为最左巷道，定义编号最大即最靠右的为最右巷道。

Step 2：拣选员从Depot出发，到达最左巷道，沿着拣选巷道由近及远拣选最左拣选巷道内所有的待拣选点。

Step 3：如果当前拣选巷道是最后一条含有待拣选点的巷道，则前往Step 4；如果当前拣选巷道不是最后一条含有待拣选点的巷道，则前往Step 6。

Step 4：接下来分为两种情况：

Step 4.1：拣选员尚未到达过最右巷道，下一待拣选巷道为当前拣选巷道右边的待拣选巷道，根据下一条待拣选巷道内待拣选点的分布状况，将下一待拣选巷道内的待拣选点分为去程上拣选和回程上拣选两类，按照上文所说的动态规划规则，确定其中的去程上拣选的待拣选点的拣选顺序。

Step 4.2：拣选员到达过最右巷道，下一待拣选巷道为当前拣选巷道左边的待拣选巷道，根据上文所述的动态规划原则，确定下一待拣选巷道内的待拣选点的拣选顺序。

Step 5：拣选员按照最短的行走路线到达下一个待拣选点，并依照拣选顺序依次拣选当前拣选巷道内的拣选任务。前往Step 3。

Step 6：最终，返回Depot。

4 仿真结果分析

4.1 实验设计

通过实验寻找在不同的货架规模和一次拣选作业中不同数量的待拣选点数的情况下，横向巷道数量同拣选路径长度间的关系，及若将横向巷道作为拣选巷道间的连接通道时，最佳的横向巷道数量。

实验分为两个步骤进行：第一步是在一个指定的布局下，逐渐增加横向巷道的数量，以考察在拣选不同数量的拣选点情况下，拣选路径长度的变化以及最优的横向巷道数量；第二步是变化仓库布局及仓库大小，重复第一步的实验，以观察在不同的仓库布局及大小的情况下，最优的横向巷道数量。仓库内的基础参数如下：单个货格长1m，单个货格宽0.5m，拣选巷道宽1m，横向巷道宽1m。实验参数设计见表1，实验参数组合示例见表2。

表1 实验参数表

表2 实验参数组合示例

在本文中，订单随机生成，订单指定的拣货点都服从独立同分布，随机地从库区中选取，不考虑由于需求带来的每个货位的不同拣选频率，这些与文献［7］假设相同。

4.2 实验结果与分析

随机生成待拣选点位置，实验程序是在VB平台上实现，共进行了8×5×10×5=2 000组实验，每个实验数据组合均进行100次实验，取得平均行走距离（单位：m），作为实验结果。

以组合算法为基础，通过变化拣选巷道长度L，拣选巷道数量N及待拣选点数K对行走距离s的影响，并在此基础上，进一步分析，增加横向巷道的数量对行走距离s的影响，最终总结出最优的横向巷道数量。

通过对数据结果（如图7所示）的分析可以发现，当横向巷道数量为M=2时，行走距离s随着L、N、K的增加而增加，但增加的幅度逐渐减少。同时，在相同的仓库布局下，即拣选巷道长度和数量均相同，待拣选点的数量越多，行走距离越多；但当待拣选点数量增加到一定程度，即平均每条拣选巷道的待拣选点数量较多，拣选密度较高时，拣选员不得不穿越每条巷道，此时行走距离达到极限值，再增加待拣选点数量，行走距离基本不变。

若考虑横向巷道对行走距离的影响问题，如图8所示，发现当拣选密度较大时，增加横向巷道，反而会增加行走距离；当拣选密度较小时，随着横向巷道数量的增加，行走距离先逐渐减少到最小值，再由最小值慢慢增加；在最小值附近，减少或增加横向巷道的数量，对行走距离的影响不大；在横向巷道数量为最优值之前，每减少一条横向巷道数量，行走距离增大地越来越剧烈。

当将横向巷道作为拣选员在拣选巷道间移动时的连接通道时，一条额外的横向巷道，也就是第三条横向巷道，为拣选员的行动提供了一种额外的可能性，即从仓库的1/2处由拣选员现在所处的拣选巷道转入下一条待拣选巷道；两条额外的横向巷道，也就是第三和第四条横向巷道，为拣选员的行动提供了两种额外的可能性，即从仓库的1/3和2/3处由拣选员现在所处的拣选巷道转入下一条待拣选巷道；更多的额外的横向巷道为拣选员的行动提供更多的可能性，但每一次增加横向巷道都在原有的横向巷道提供的优化的基础上，对拣选路径进行优化，并且，每一次增加横向巷道都会引起额外的拣选路径的增加。所以，每增加一条横向巷道，其对拣选路径的优化距离在快速降低，并且当横向巷道的数量增加到一定程度时，它反而会造成拣选路径的增加。

虽然最佳的额外横向巷道的数量受到拣选点数量、拣选巷道长度以及拣选巷道数量的影响，但是，若将额外的横向巷道仅作为连接通道使用时，第三条额的横向巷道对拣选路径的优化不超过原始路径的5%。

图7 行走距离变化趋势图

图8 横向巷道对行走距离影响

5 结束语

拣选路优化是提拣选效率重要的手之一，受到多企业管者和学者关注和研究。本文提出了一种针对含有多条横向巷道的仓库布局的拣选路径优化算法—组合算法，仿真结果显示，在含有多条横向巷道的仓库中，若将除“前横向巷道”和“后横向巷道”之外的横向巷道作为连接巷道，在拣选密度较低的情况下，能够显著地优化拣选路径的距离，但是，过多的横向巷道对拣选距离的优化效果不明显，甚至可能会造成拣选距离的增加，额外的横向巷道数量不宜超过2条，即仓库内的横向巷道数量不宜超过4条。

［1］吴政洁.物流中心即时批次订单的拣货研究［D］.台湾:国立中央大学，2007.

［2］Tompkins J A，White J A，Bozer Y A，et al.Facilities Planning［M］. NJ:John Wiley&Sons，2003.

［3］陈方宇.多区块仓库环境下订单拣选路线规划研究［D］.武汉:华中科技大学，2014.

［4］王宏，符卓，左武.基于遗传算法的双区型仓库拣货路径优化研究［J］.计算机工程与应用，2009，45（6）:224-228.

［5］Petersen C G.An evaluation of order picking routeing policies［J］. International Journal of Operations and Production Management，1997，17（11）:1 098-1 111.

［6］Roodbergen K J，Koster R.Routing methods for warehouses with multiple cross aisles［J］.International Journal of Production Research，2001，39（9）:1 865-1 883.

［7］Caron F，Marchet G，Perego A.Routing policies and COI-based storage policies in picker-to-part systems［J］.International Journal of Production Research，1998，36（3）:713-732.

Study on Picking Path Optimization in Warehouse with Multiple Transverse Alleys

FangDianjun，PengYifan
（Chinesisch-DeutschesHochschulkolleg，TongjiUniversity，Shanghai 201804，China）

In this paper，with a warehouse with multiple transverse alleys as the object and with the shortest total travelling distance as the objective，we studied the picking path optimization of the warehouse，and then on the basis of a mathematical description of the problem，developed and realized a heuristic algorithm based on combination rules.Meanwhile，we analyzed the influence of different length and quantity of the picking alleys，the number of picking stations and the quantity of transverse alleys on the total travelling distance，through which we found that through the transverse alleys we can remarkably optimize the picking distance，but there should not be more than 4 of theminawarehouse.

warehouse；pickingactivity；pathoptimization；multipletransversealley

TP273

A

1005-152X（2016）05-0130-06

10.3969/j.issn.1005-152X.2016.05.029

2016-04-03

房殿军（1961-），男，山东人，博士，教授，主要研究方向：物流系统规划、供应链管理。