多区型仓库多复核台场景的拣货路径优化研究

2022-01-19叶楠毕忠勤魏恒达吴迪

应用科学学报 2021年4期

叶楠，毕忠勤，魏恒达，吴迪

1.武汉大学测绘学院，湖北武汉430079

2.武汉大学数学与统计学院，湖北武汉430079

3.上海电力大学计算机科学与技术学院，上海200090

随着电子商务的蓬勃发展，海量、个性化已成为当今网络购物订单的主要特点。而仓库作为各类商品重要的中转站之一，承担着货物入库、存储、管理、拣货、派出等一系列作业过程。其中，拣货作业过程是仓库作业的核心环节。数据显示，就配送中心等劳动密集型仓库来说，与拣货直接相关的人力占50%以上，货物拣选时间大概占整个仓库作业的30%～40%，而配送中心总物流成本大约60%用于拣货[1]。因此，优化拣货路径、缩短拣货时间不仅能够更快地完成订单商品出库，而且对于降低仓储成本、提高配送中心的运行效率具有极其重要的意义。

在仓库货物的摆放布局方面，已有研究表明，双区型仓库比单区型仓库在拣货效率上具有明显提升[2-3]。随着仓储系统的创新发展，出现了V型布局和鱼骨型布局等新型仓储布局方式，且在单命令模式下，鱼骨型仓储布局的拣货效率相对于普通仓库提升约20%[4]。现实应用中的仓库大多为双区型或多区型[5]，特别是对于规模较大的配送中心，多区型仓库布局已成为主要模式。基于此，结合京东物流实际布局模式，本文选择多区型仓库作为研究对象，并设计了相应的路径优化算法。

在路径优化方面，基于遗传算法、蚁群算法、模拟退火等智能算法的改进和混合算法已被广泛应用于大型仓储拣选系统的路径优化策略[6-8]。文献[9]结合传统启发式优化算法和动态规划思想，提出了适用于双区型仓库的拣选路径优化算法；文献[10]基于禁忌搜索算法提出了一种在不同场景下，适用于仓库同时优化货位分配及拣货路径的方法，表明算法能较好地优化货位分配与拣货路径；文献[11]提出了基于混合遗传模拟退火算法，且认为该算法在静态拣货路径优化基础上，可以进一步提升仓库拣货效率，且拣货单越多，算法优化效果越明显。

此外，部分学者尝试从订单分配和路径规划两个层次对拣货作业进行优化。文献[12]采用动态的拣货策略，在拣货周期中进行拣货单分配和路径优化；文献[13]针对不同拣货单分配方式下的拣货路径规划问题，采用S型启发算法和遗传算法进行优化，结果显示将拣货单分批策略和遗传算法的路径规划相结合能够得到更为合理的拣货作业规划；文献[14]针对上述拣货单分配和拣货路径分布优化难以获得最优解的缺陷，提出了一种基于嵌套遗传算法的拣货单分批和路径优化的联合拣货策略，采用外层优化拣货单分批结果、内层优化拣货路径相结合的方式，为配送中心拣选系统优化提供依据。

然而，目前对于路径优化的研究主要集中在单出入口或单复核台，即拣货员从该位置出发，拣货完成后需返回起始点。但对于大型配送中心来说，往往设置有多个复核台、出入口进行货物的复核与打包工作，以尽可能地提升订单货物出库的效率。于是，结合京东物流仓储系统实际情况，本文提出替换复核台以解决多复核台起始点与终点不确定的复杂场景，并在此基础上给出多拣货员、多复核台情况下的仓储拣货路径优化策略，以解决大规模复杂场景下的拣货作业。

本文引用了图论相关知识，提出了替换复核台的概念，并解决多复核台场景下因始终点不确定而导致的遍历搜索困难，根据实际情况给出在多复核台多拣货员情况下多拣货单的路径优化与合理分配的动态调整策略。研究表明，本文给出的算法在同等条件下相比其他算法计算效率更高、拣货路径更短、路径规划更准确，满足了大规模拣货要求，也为多复核台的后续研究奠定了基础。

1 问题描述

1.1 多区型仓库简介

结合京东物流仓库实际情况，本文所考虑的大规模多区型仓库由5条平行的横向通道和26条纵向巷道构成；每条通道的宽度相等，每条巷道的宽度也相等。仓库共有4排货架，每排25组货架，每组两个货架，所有货架均采用背靠背模式；每个货架包含15个货格，共3000个储位。仓库共有13个复核台，其中8个复核台(FH01-FH08)设置在仓库通道1南侧、另外5个复核台(FH09-FH13)设置在巷道1西侧，仓储系统会根据实际情况选择开启部分或全部复核台以满足拣货单拣货效率的最大化，具体仓库布局如图1所示。

图1 多区型仓库平面示意图Figure 1 Multi-zone warehouse plan diagram

1.2 参数设置

关于货架与货格的符号说明如下：

1）xi,yi分别为第i个货格左下角的坐标信息，i=1,2,···,3 000。

2）Xj,Yj分别为第j个复核台左下角的坐标信息，j=1,2,···,13。

3）Di1i2,Dij,Dj1j2分别为货格i1与货格i2之间、货格i与复核台j之间、复核台j1与复核台j2之间的距离。

4）ri,ci分别为第i个货格所在货架紧邻巷道的行数与列数；因多区型仓库包含4行货架、26列巷道，故ri=1,2,3,4;ci=1,2,···,26。

5）ai,bi分别为第i个货格所处的货柜号与货格号，ai=1,2,···,200；bi=1,2,···,15。

6）l1,w1分别为货格的长度与宽度，l2,w2分别为复核台的长度与宽度，lroad,wroad分别为纵向巷道与横向通道的宽度。

关于拣货单的符号说明如下：

1）T表示所有拣货单的数量，编号t=1,2,···,T；

2）Nt为第t个拣货单待拣选商品总数，nt为第t个拣货单中的第n个商品，nt=1,2,···,Nt；

3）Hnt为第t个拣货单中第n个货物所在的货格编号，其中包含货柜号a和货格号b。

关于拣货员的符号说明如下：

1）V为拣货人员的平均行走速度；

2）T为拣货人员拣取每个货物商品所消耗的平均时间；

3）d为拣货员绕障碍物折线行走时横向及竖向偏移量。

1.3 模型假设

1）拣货员均按照拣货单拣取货物，到达复核台后拣货员无需等待，继续开始下一个拣货单的拣货流程；

2）货架和复核台为障碍物，不可通行，其余位置均可通行；

3）商品摆放在货格中，且每个货格最多摆放一种商品，一件商品只能存放在一个货格；

4）当开启的复核台数量为多个时，拣货员开始和结束复核台可以不一致；

5）拣货员只有在完成一个拣货单的拣选作业后，才能进行下一拣货单货物的拣选，即不存在跨单取货的情况出现。

2 模型准备——元素间距离求解

基于上述假设，下面详细说明如何求解货格之间、货格与复核台之间、复核台之间各元素的距离。

2.1 构建坐标偏移矩阵C

考虑到货格坐标表示为该货格左下角点的坐标信息，与拣货员在该货格进行货物拣取时所处坐标存在差异，且同一组中左右两货架的计算方式不同。因此，为了避免对该情况进行复杂的分类讨论，本文在计算货格距离之前，构建了各货格坐标的偏移矩阵C(3013,2)，将坐标值换算到该货格紧邻的巷道中心点位置，即拣货员在取货时所处位置的外偏移量，得到的左右两货架坐标偏移的计算公式为

图2 货格坐标偏移示意图Figure 2 Schematic diagram of coordinates offsets of goods grid

此外，复核台坐标偏移的计算公式为

2.2 各货格之间距离计算

考虑到仓库货格分布的实际情况，结合货格紧邻巷道的行列号，可以将货格距离的计算分成同一排同一巷道、同一排不同巷道、不同排同一巷道、不同排不同巷道4种情况。下列分别对上述4种情况进行分类讨论：

情况1两货格位于同一排同一巷道，即ri1=ri2且ci1=ci2时

情况2两货格位于同一排不同巷道，即ri1=ri2且ci1/=ci2时，拣货员最短路径的选取按照其所处货格的位置决定；即当两件货物均处在货架偏上方时，选择从上方巷道行走距离较近；反之，拣货员应选择下方。

在图3同一排不同巷道的讨论示意图中，对偏移量d也有了直观的解释：拣货员在货格之间行走移动时默认货格为障碍物，拣货员需要与其保持一定的距离，本文将该距离定义为偏移量d，为拣货员绕障碍物折线行走时横向及竖向偏移量，且将横向偏移量与竖向偏移量默认为相等的值。

图3 同一排不同巷道讨论示意图Figure 3 Schematic diagram of the same row but different columns

情况3两货格位于不同排同一巷道，即ri1/=ri2且ci1=ci2时

情况4两货格位于不同排不同巷道，即ri1/=ri2且ci1/=ci2时

2.3 货格到复核台之间距离

基于对仓库货架布局情况分析，定义货格与复核台距离为货格中点到复核台最近一条边中点的距离；即当复核台处于通道1南侧时(FH01～FH08)，从复核台上方进入距离最短。同理，对于巷道1西侧的复核台(FH09～FH13)，最短距离与拣货员所处的位置有关。

此外，还需要考虑巷道在第1列，即处在复核台旁的特殊情况

2.4 复核台之间距离计算

两个复核台之间距离的计算应该分为在同一排（均在左侧/均在下方）以及不在同一侧两种情况。

情况1复核台处于货架同一侧时

情况2复核台处于货架不同侧时

3 多复核台下拣货路径优化策略

3.1 拣货路径优化策略

传统的单出口、单复核台拣货路径优化往往是起始点与终点均固定，针对此情况，文献[15-16]基于TSP对仓库的拣货路径进行建模，并利用模拟退火、蚁群算法和禁忌搜索等诸多算法对模型进行求解，得到了较为理想的拣货路径。

与上述不同，多复核台的路径优化往往是始终点均未固定的情况。假设仓库开设n个复核台，倘若对所有复核台进行最短路径遍历，则单就复核台选择的复杂度就达到O(n2)，再加上智能优化算法本身，其计算效率会随着复核台数量增多而急剧降低。基于此，本文将引入替换复核台的概念，将始终点未固定的多复核台路径规划问题转化为已知起点与终点的拣货路径优化问题；并在此基础上，给出针对多拣货单的合理分配策略，以使拣货员工作时间最短。

3.1.1 模型准备——替换复核台的引入

下列先以一个简单的图论问题为例引入替换终点的概念。

在左图中以A为起点，途径B1、B2两点，以C1或C2为终点的路径有两种，分别为A-B1-B2-C2、A-B2-B1-C1。注意到当最后一个途径点为B1时会选择更近的C1为终点，当最后一个途径点为B2时会选择更近的C2为终点，故可引入一个替换终点C，使得d(B1,C)=d(B1,C1),d(B2,C)=d(B2,C2)，即可确定一个终点C，如上右图所示。从而问题即被转化为以A为起点，途径B1、B2两点，以C为终点的最短路径规划问题。

图4 替换终点的引入示意图Figure 4 Schematic diagram of introduction of replacement endpoints

上文的例子是替换终点，而替换起点的方法也是一样。下文将替换终点复核台和替换起始复核台统称为替换复核台。

本文通过引入替换复核台来解决终点待固定的路径优化问题。假设该拣货单中含有的货格数为Nt，以Hi(i=1,···,Nt)表示这些货格点，起始点与终点均可在所有复核台(FH01～FH13)中任意选择。

为了得到最短的路线，引入替换复核台FH∗，使得对于任意i=1,···,N满足

图5中距离下标im,in表示N个货格中任意两个货格。

图5 替换复核台下最短路径转化示意图Figure 5 Schematic diagram of the shortest path transformation under replacement review station

于是得到含FH∗、Hi(i=1,···,N)、FH∗共N+2个点在内的无向带权图，权值即为两点之间的距离，从而将问题转化为求解以已知始终点、途径Hi的最小距离问题。

3.1.2 仓内拣货最短路径模型

优化目标函数如下所述。

假设一个拣货单中含有的货格数为N，规定用0表示拣货员开始拣货的起点，该点通常是某一个复核台；用N+1表示完成拣货后所到达进行复核/出库的终点。

拣货路径优化问题的目标是使拣货完成的总距离D最小[17]

式中，D(i,j)为任意两个元素之间的距离；xij表示拣货所经过的路径，且

考虑到仓库的实际情况，该问题中约束条件主要包含路径约束、货格约束。构建模型时，应保证在拣货过程中拣货单上的每个点访问数有且仅有1次，即货格约束条件可以表示如下：

①对于i=0,1,2,···,N+1来说，即对于替换复核台FH∗与中间所经过的每个货格均会有下一个元素与之相连，其出度为1；

②对于j=0,1,2,···,N+1来说，即对于中间经过的货格与替换复核台FH∗均会有上一个元素与之相连，其入度为1。

3.1.3 求解算法

通过拣货路径优化策略，可以将多复核台路径求解转化为已知起点与终点的拣货路径优化问题。该问题为NP-hard问题，目前解决这类问题采用最多的是启发式算法、遗传算法、蚁群算法等一系列智能算法[15-16]。遗传算法基于“优胜劣汰”思想的群体遗传操作来实现优化；在求解较为复杂的组合优化问题时，相对常规的优化算法通常能够更好地优化结果。因此，本文基于遗传算法进行路径规划策略求解。

3.2 多拣货单合理分配策略

基于上述拣货单路径优化策略，可以得到各拣货单最优拣货路径；为了尽可能减少各拣货员行走路程，应优先将具有相同起止点的拣货单进行拼接。考虑到所构建的图结构为无向带权图，即可通过调整各拣货单最短路径的方向或者端点的选择尽可能使得拣货单之间首尾相连，即在完成一单拣货到达复核台后，可以立即将此复核台作为下一个拣货单的起点。于是，本文合理分配拣货单顺序，以减少在复核台之间不必要的路径损耗。

得到首个拣货单最优拣货路径的基础上，结合式(11)可知Hi已经确定后，遍历所有复核台计算该复核台与Hi的距离，即可以选择距离最短的复核台作为首次拣货的起始复核台。终点复核台的确定过程同理。

此外，在完成拣货单库中所有拣货单遍历后，对于仍不能合理分配的拣货单，可通过对比下列两种行走路径方案，优先选择行走距离较短的方案，以使得该拣货员在当前状态下路径最优。

1）直接行走至下一拣货单所在复核台，进行下一拣货单的拣货操作。

2）改变下一拣货单起始点，使之与当前拣货单终点相同；并在此基础上，通过拣货路径优化策略寻找较优的拣货路径。

显然，多拣货单的合理分配方案会随着单数的增加而呈现指数型增长，属于NP-Hard问题。因此，本文尝试通过将贪婪算法和动态调整相结合，给出在多拣货单情况下，各拣货员的拣货单分配策略，具体算法如下。

Algorithm 1基于动态调整的拣货单拼接策略

4 实例分析

4.1 仓库参数设定

实验数据来自京东物流的实际拣货单数据1数据来源：京东物流(https://www.jdl.cn/)，包括各元素(货柜、货格、复核台)的名称、长宽及坐标信息，其中货格名称前3位为所在货柜编号a、后2位为在该货柜下货格编号b；各拣货单编号及其所包含货物的货格名称等信息。

实验假设水平方向每组货架之间的距离为1.5 m，竖直方向相邻两排货架纵向距离为2 m，货格长宽都是0.8 m，复核台长宽都是1 m，横向通道与纵向通道宽度均为1.5 m；拣货员绕障碍物折线行走时均沿道路中心线横向和竖向偏移，都取d=0.75 m。对于拣货操作，假定拣货员平均行走速度为1.5 m/s，对每一待拣取货物进行下架操作（包括拣取、扫描、检查、确认等步骤）所需时间为5 s。

考虑到实验拣货单共49个，本文基于合理假设，设置拣货员5人、复核台开启4台，以尽可能降低仓库运营成本。不失一般性，假设通道1南侧与巷道1西侧各开启2个复核台，分别为FH01、FH03与FH10、FH12。

4.2 多复核台下拣货路径优化

4.2.1 各拣货单拣货路径优化

基于3.1.2构建的模型，引入替换复核台将问题转化为已知起点与终点的最短路径问题；本文采用遗传算法进行求解。算法具体步骤可参考文献[14,18]的阐述，此处不再赘述。

对于实际给出的49个拣货单采用拣货路径优化策略，得到各拣货单最优拣货路径。限于篇幅，此处仅给出对T0001拣货单计算得到的最优路径顺序为：FH03→S07305→S10508→S10501→S12103→S13004→S13809→S14510→S13812→S14908→S14401→S15911→S13509→S12608→S11205→S11106→S10115→S06213→S07212→S08502→S07515→S01308→S01713→S00107→FH01，总拣货距离为388.5 m，总拣货时间为454.0 s，拣货路径见图6，其中黑色标记为待拣取货物所在位置。

图6 拣货单T0001拣货的实际路径图Figure 6 Order T 0001 picking actual path diagram

4.2.2 多拣货单合理分配策略

基于算法1得到的各拣货员拣货单分配集合如表1所示，其中拣货单编号顺序即代表拣货员拣货顺序。

表1 各拣货单分配结果Table 1 Results of each order allocation

为了验证本文提出算法的效果，引入对比实验1和2。

实验1基于下一拣货单起点驱使的随机游走：依靠拣货路径优化策略，得出各拣货单最优路径下的起始点。当拣货员完成此单拣货工作时，需行走至下一拣货单的起始复核台处，进行下一拣货单的拣货操作。

实验2基于当前拣货单终点驱使的逐步优化：按照拣货所需时间对各拣货单进行排序，优先完成所需时间较长的拣货单的拣货工作依次完成，对于下一拣货单起止点与当前拣货单终点不同的情况，即不能完成拣货单的拼接；选择将当前拣货单终点作为下一拣货单起始复核台，重新进行下一拣货单的路径规划。

将上述方法与本文动态调整的仿真结果进行对比，表2为各拣货员行走距离对比表，表3为拣货员拣货耗时结果。

表2 拣货员行走距离计算结果对比Table 2 Comparison of picker walking distance calculation results m

表3 拣货员拣货耗时计算结果对比Table 3 Comparison of picker picking time calculation results s

需要特别说明的是，由于随机游走是按照拣货单顺序进行分配、逐步优化是按照拣货单拣选时间长度排序后分配，而动态调整则是基于贪婪算法和动态规划相结合得到的分配方案；换言之，分配同一拣货员的拣货单编号会因为不同算法而产生差异。因此，单个拣货员的拣货距离与所耗时间不具有可比性。

通过比较拣货员行走总距离可以发现，本文所提出的动态调整的解决策略中所有拣货员行走总距离为19 443.2 m，相对于随机游走和逐步优化算法分别缩短239.6 m和657.7 m。此外，就拣货总耗时来说，动态调整相较于逐步优化节约的拣货时间为55.4 s，相较于随机游走节约109.8 s；可以看出，本文所提出的动态调整的解决方案能够缩短拣货员行走距离，提升拣货效率。

从算法运行的效率来看，逐步优化算法的计算耗时为3.5 s，大约是动态调整方案耗时0.4 s的8倍。换言之，本文所提出的动态调整策略在解决49个大规模拣货单情况下，仍然能够完成亚秒级的规划响应。