低层人工拣货仓库货位优化问题研究*

罗嫚玲，林 海，刘 威

(武汉大学国家网络安全学院空天信息安全与可信计算教育部重点实验室，湖北 武汉 430000)

1 引言

B2C电商企业订单数量庞大、零散、交易时限极短，这种小批量、高频次的出库对其仓储物流构成巨大成本。因此，如何合理规划储位成为提高空间利用率和货物拣选效率以及降低成本的核心所在。现阶段国内的大部分配送中心、中小型企业等因受到资金、技术和环境等因素的限制，只能采用人工拣货仓库[1]。相较于自动化立体仓库，人工拣货仓库货架布局与拣选路线更加灵活，没有太多规律，关于其货位优化问题的研究也很少。

当前国内外研究人员大多通过建立货位优化模型实现仓库货位优化，主要优化目标为设备或拣货人员的行走路径或时间，同时根据仓库特点或仓储需求考虑是否结合其它优化目标[2-14]。例如，自动化立体仓库由于货架高、货物重需借助堆垛机或叉车完成拣货，此时除以设备行走时间为主要优化目标外还需考虑货架稳定性、货物周转频率、作业能耗等其它优化目标或相关约束[15-17]。而低层人工拣货仓库由于存储商品体积小且重量轻，此时商品之间的关联性显得更重要，可不考虑货架稳定性、货位载重等因素[1,8,10]。在模型求解方面，由于该类问题属于组合优化问题，大多采用改进遗传算法、蚁群算法、粒子群算法、模拟退火算法、贪心算法和混合粒子群等搜索算法[1,3,5-8,10,12,14,16,18,19]，少部分根据问题本身设计启发式算法[6,11,20]。

行走路径或时间作为货位优化模型的主要优化目标，其求解复杂度直接关系到货位优化效率。不管是自动化立体仓库还是基于自动导引运输车AGV(Automated Guided Vehicle)的货到人系统的普通立体仓库[21]，每次拣选只需将指定位置的某一商品或货架搬运到指定出口[10,16,17]，此时路径计算时间复杂度为线性复杂度。而低层人工拣货仓库，由于一次拣货需在不同货架间行走，故行走路径计算属于旅行商问题的特例，而旅行商问题是非常经典的NP问题，当问题规模很大时，几乎不可能在有限的时间内求得最优解。现有人到货系统的货位优化研究几乎都集中在布局规则的单深区或双深区仓库，该类仓库有多条巷道，每条巷道两边多个货架并排，这使得拣选某一货架的商品时只能从该货架所在巷道两端进入巷道，此时可通过指定合理的启发式路径策略求得最短行走路径，这使得时间复杂度大大降低[6]。但是，事实上很多中小型企业的仓库是人到货仓库，一般由拣货人员携带拣货小车或其它装载设备进行拣货，为减少不同拣货人员同时拣货时的相互干扰，仓库布局并不会采用多个货架并排形成巷道，而是使拣货通道宽敞且相互连接，导致拣货路径灵活，难以直接采用启发式路径策略降低时间复杂度。

由于电商企业仓库的一次拣选都包含多种商品，故在货位优化问题中商品关联性成为了研究热点。就关联关系分析方面，大部分研究集中在利用数据挖掘算法分析不同商品的内在关联性，如采用Apriori算法[21-24]挖掘商品之间的关联关系，但在电子商务环境中，对小批量、高频次订单数据进行商品关联规则挖掘时，该算法计算速度缓慢，易导致货位分配时间过长。因此，在上述条件下采用了一种不产生候选集的发现频繁项集的FPGrowth算法[6,25]，其运算速度相比于Apriori算法提升几个数量级，但相应的内存开销也会较大。少部分研究基于矩阵或集合理论自定义启发式算法[8,26,27]或者构建聚类模型[28]来测量不同商品之间的相似度。目前几乎所有的商品关联性分析都没有考虑商品本身的热销程度对该商品与其它商品之间的关联关系的影响。考虑商品关联性进行货位优化时，不同的商品拣选方式对应的聚类要求也不同[23,28-30]。例如，货到人系统中只有将相关性高的多个商品存放在同一个货架才会缩短行走路径，而人到货系统将其存放在相邻货架同样有效。此外，结合商品关联性进行货位优化不仅可以缩短路径，还可用于缓解拥塞和平衡工作量，如货到人系统可通过分析货品组之间的关联度来缓解堵塞[8,31]。调研发现针对人到货系统考虑商品关联性进行货位优化以及考虑关联度缓解堵塞的研究还很少。故本文在分配货位时考虑了商品相关性因素，即将相关性高的商品存放到相同或相邻货架，此时相关性较高的不同商品可视为一个社区；然后通过社区划分算法对不同商品及其相关性组成的网络进行社区挖掘，使得社区内部商品节点连接紧密，不同社区商品节点之间连接稀疏。

综上所述，本文针对仓库布局不规则、商品关联性重视程度不够且现有的低层人工拣货仓库的储位优化研究非常不足等问题，在考虑商品热销度、相关性等因素的基础上，提出基于社区划分的货位优化算法，同时构建多个指标从不同优化方面对多个货位摆放方案进行评估和选择。

2 问题描述

本文所研究的B2C电商企业低层人工拣货仓库布局不规则且货架大小不一，与单深区或双深区仓库的巷道相比，拣货通道更宽、更多且相互连通，使得拣选人员行走路径更灵活。

仓库的订单拣选过程：拣货员从仓库复核打包区出发开始拣货，当访问完当前订单所需访问的所有货架后，回到打包区。

因为行走是主要人力消耗，所以货位优化的主要优化目标为缩短行走路径或时间，其求解复杂度直接关系到优化效率，而订单拣选的灵活性使其难以采用启发式路径策略来降低求解耗时。

低层仓库存放的商品具有体积小、重量轻的特点，不需考虑货架承重及其稳定性。但是，若只考虑行走路径这一优化目标，则很可能导致某些距离出口很近的货架被放满热销商品，造成严重的堵塞问题，反而降低拣货效率，因此还需将缓解堵塞作为优化目标。此外，本文还在仔细分析仓库人力消耗的基础上，提出了减少仓库拣货人员工作时间进而减少人员数量的优化目标。

3 基于社区划分的货位优化算法

货位优化算法的目标包括缩短行走路径，缓解堵塞，减少拣货人员数量。打包点是将复核打包区抽象为一个点，其坐标为复核打包区的位置中点。

3.1 算法描述

B2C电商企业商品多种多样，商品之间的关系可根据订单来衡量，一个订单可将多种商品连接起来，而成千上万的不同订单各自连接不同的商品。从某种程度上讲这是复杂网络在现实世界中的一种表现形式，通过对复杂网络进行社区挖掘，使得社区内部节点连接紧密，不同社区节点之间连接稀疏。本文正是基于这种对复杂网络进行划分的思路，提出了基于社区划分的货位优化算法。

基于社区划分的货位优化算法首先根据商品之间的关联度，抽象出以商品为顶点的无向有权网络，并对此复杂网络进行社区挖掘，生成多个具有一定的内聚度的社区。然后以社区为单位进行放货，此阶段主要考虑社区热度、货架位置等影响因素。以社区为单位进行存放可保证同一社区的商品被存放到相邻或同一货架，且同一社区的商品是根据商品关联度被划分到同一社区，通常不会都是热销商品，所以本文算法在满足缩短行走路径的条件下还能在一定程度上缓解堵塞。

由于无法预测社区划分算法的划分结果，也无法直接判断商品关联度对货位优化的影响程度，故本文通过设置最大子社区阈值对社区划分结果进行约束，以控制商品关联度因素在货位优化算法中的影响。之后对不同划分结果以社区为单位进行存放和调整可得到不同的摆放方案，最后根据指标对多个方案进行评估和选择。基于社区划分的货位优化算法流程如图1所示，详细描述如下：

(1)构建无向有权网络：无向有权网络由节点集合及节点之间的边集合组成，每种商品为一个节点，网络节点总数为历史订单中的商品种类数总和。任意2个节点ci和cj之间的权重wci,cj为2个商品之间的关联度c_rci,cj，表示历史订单中同时包含2个商品节点的订单总数；商品热度c_hotci是指历史订单中，所有包含商品ci的订单总数；社区热度co_hotcoi,coj是指社区内商品的热度总和；社区之间的关联度co_rcoi,coj是指2个社区之间的连边权重之和。

(2)初次划分阶段：首先利用满足划分要求的社区划分算法(见3.2节)对构建的无向有权网络进行划分，初次划分结果为part，然后将part中的最大子社区所包含的节点总数设置为初始阈值part_T，并转到存放阶段。

(3)存放阶段：目的是将划分阶段(初次划分或再次划分)的划分结果以社区为单位存放到货架，主要考虑社区热度、社区之间的关联度及货架位置等因素为各个子社区寻找最佳存放货架。

存放阶段伪代码如下所示：

1.funcationpartion_deposit_to_shelf(c_part,graph)/*社区划分阈值part_T对应的当前社区划分结果c_part，货架布局graph*/

2.ininitialize(F_Allo);/*初始货位摆放方案F_Allo*/

3.new_part=sort(c_part,co_hot);/*按社区热度排序*/

4.forparttonew_part//存放

5.b_shelfs=find_Bshelfs(c_part,graph,F_Allo);

6.F_Allo=deposit(b_shelfs,c_part,F_Allo);

7.endfor

8.returnF_Allo;

9.endfuncation

详细步骤如下所示：

①确定子社区的存放顺序：将子社区按照社区热度从大到小排序。

②按顺序为每一个子社区寻找当前最优货架群并将其存放到指定货架：

首先，为社区coj指定中心存放货架：当j=0时，coj为第1个存放的社区，其中心存放货架为距离打包点最近的货架；当j>0时，评估当前所有可用货架的存放优劣度，从中选出最优货架作为中心货架。货架优劣度计算如式(1)所示：

(1)

其中，shelf_rets表示当前可用货架s存放社区coj时的货架优劣度，该值越大表示该货架越可能成为社区coj的实际存放货架；co_rcoi,coj表示社区coi和coj之间的关联度；cs(coi)为社区coi的中心存放货架；discs(coi),s表示社区coi的中心存放货架与货架s之间的距离。如果两货架相同时，为避免发生零除错误，此时将其设置为一个小于最近货架距离的常数A。diss,sp表示当前评估货架s与打包点sp之间的距离。

其次，计算当前仓库中所有可用货架与中心货架的距离，并将可用货架按照距离从小到大排序，得到以该中心货架为首的可用货架序列。

最后，将子社区商品依次存放到可用货架序列。

③存放结束后，输出划分阈值part_T所对应的一个初始摆放方案F_Allo，之后转到调整阶段。

(4)调整阶段：当商品种类数小于总货位数时，初始摆放方案并不能把货架存满，所以调整阶段在这时主要根据热度和距离因素补齐存在空位的货架，其伪代码如下：

1.funcationjust_First_Placement_result(F_Allo,graph)/*初始货位摆放方案F_Allo,货架布局graph*/

2.forktolen(shelf)//货架若存在空位则补齐

3.ifget_Cnum(shelf[k])

4.E_Allo=complete_shelf(shelf)

5.endif

6.endfor

7.returnE_Allo;//最终货位摆放方案E_Allo

详细步骤如下所示：

步骤1判断所有货架中是否存在货架具有空位，若没有则转到步骤3。否则，转到步骤2进行调整。

步骤2调整主要考虑热度与距离因素，首先确定一个未存满货架se，然后找出没有被存放在货架se上的其它商品种类，并记录其热度与所在的货架，之后评估哪些类型的商品适合存放在该货架，如式(2)和式(3)所示：

(2)

(3)

其中，c_retc表示商品c的存放价值，该值越大，则说明商品c越适合被添加到当前有空位的货架se；c_hotc表示商品c的商品热度；c_hotmax表示所有商品中的最高热度值，做归一化处理；se表示当前未存满货架，sc表示存放商品c的所有货架中距离se最近的货架；dis(se,sc)表示货架se与sc之间的距离；dismax表示当前仓库中不同货架之间的最大距离，做归一化处理；dis(se,shc)表示货架se与货架shc之间的距离；Shc表示存放商品c的所有货架集合。

步骤3根据评估值对商品从大到小排序，将前e种商品添加到当前有空位货架se,e为空货位个数。

步骤4货架遍历调整结束后得到阈值part_T对应的最终摆放方案，之后转到再次划分阶段。

(5)再次划分阶段：本阶段通过设置不同的阈值part_T可得到不同的划分结果，作为存放阶段的输入，最终可以得到多个不同的货位摆放方案。再次划分阶段的输入为初次划分结果及其划分阈值part_T，该值大小为初次划分结果中最大子社区所包含的节点总数。本阶段通过不断减小part_T以获得不同的社区划分结果，直到part_T减小到1时再次划分阶段结束。每一个阈值获得的再次划分结果除了进入存放阶段和调整阶段获得最终的货位摆放方案外，也是下一轮的再次划分输入。再次划分阶段伪代码如下所示：

1.funcationagain_part(part_T,c_part)/*初次划分结果c_part对应的划分阈值part_T*/

2.whilepart_T≠1//货架若存在空位则补齐

3.part_T-=1;

4.Whileexist_big_part(c_part)

5.forparttoc_part

6.iflen(part)>part_T

7.part_g=build_g(part);

8.spart=again_part(part_g);

9.iflen(spart)>part_T

10.spart=rand_part(part,part_T);

11.endif

12.update(c_part,spart);

13.endif

14.endfor

15.endwhile

16.a_parts=update_apart_result(T,c_part)

17.endwhile

18.returna_parts/*不同划分阈值及其对应的再次划分结果*/

19.endfuncation

详细步骤如下所示：

步骤1判断当前part_T是否为1，若是，则转到评估选择阶段；否则设置当前社区划分结果c_part为阈值part_T时的划分结果，part_T-=1，part_Flag=False。

步骤2判断c_part是否存在子社区所包含的节点数大于part_T，若不存在则转到步骤3，否则转到步骤5。

步骤3如果part_Flag为False，转到步骤4，否则转到存放阶段。

步骤4设置最大子社区阈值为part_T的最终货位摆放方案与阈值part_T+1的最终货位摆放方案相同，然后转到步骤1。

(6)评估选择阶段：根据评估指标从多个货位摆放方案中选出最优方案。

3.2 社区划分算法选择

基于社区划分的货位优化算法中的划分步骤由社区划分算法完成，而划分算法的好坏会影响货位优化算法的效率。

3.2.1 社区划分算法要求

社区划分算法具有以下几个特点：(1)电商企业商品种类较多，订单数量庞大且零散，这使得无向有权网络规模较大，复杂度高且往往是多分量而非单分量；(2)本文提出的货位优化算法采用最大子社区阈值来控制关联度的影响程度，需多次划分，故划分速度会影响货位优化算法的运行效率；(3)划分质量的好坏直接关系到划分次数的多少以及最终货位摆放方案的质量。综上可知，社区划分算法需满足在划分规模较大且复杂的网络时运算速度快且划分质量高。

3.2.2 FU算法

根据划分算法需求，本文对多种经典社区划分算法进行了理论与实验分析，发现FU(Fast Unfolding)算法最适用于无向有权稠密网络。因此，本文提出的基于社区划分的货位优化算法中的划分步骤将由FU算法来完成，后文将其称为基于社区划分FU的货位优化算法。

需要说明的是,无论是速度合适、划分质量高的非重叠算法，还是在处理有权稠密网络时运算速度快、划分性能好且可控制重叠点数量少于或等于多余货位数的重叠算法都可直接替换本文选定的社区划分算法。

FU算法，又称Louvain算法[32],可以分为2个阶段反复迭代计算。首先将网络中每个节点看成一个单独的社区，并对社区进行编号;然后，对每个节点i，计算其加入邻居节点j所在社区后模块度增量ΔQ的变化，如果ΔQ>0，则将其放到对应模块度变量变化最大的邻居节点，否则，节点停留在原社区。将节点i放入社区C后，对应的模块度增量计算公式如式(4)所示：

(4)

其中，Σin和∑tot分别表示社区C内部边权重之和以及所有与社区C内节点相连的边权重之和；ki表示指向节点i的连边权值之和，ki,in表示节点i与社区C内节点之间连边的权重之和,E表示网络中边的数量。

重复上述过程直到所有节点所属社区不再发生变化，第1阶段结束。第2阶段是利用其在第1阶段发现的社区构建新的网络，节点即为上一阶段发现的社区，此时对社区内的节点进行压缩，社区内节点之间的权重转化为新的节点环的权重，社区间的边权重转化为新节点间的边权重，当新的网络建立完成后，重复第1阶段的过程直到得到局部模块度最大的社区为止。

4 评估指标及优化模型

基于社区划分的货位优化算法最后一步是评估和选出最优的方案，故本节主要针对不同优化目标构建评估指标。

4.1 评估假设及变量说明

货位优化目的是提高订单拣选效率，故通过模拟与分析工作人员的拣选流程，构建评估指标对优化方案进行效果评估。为便于模拟拣选流程，需对其做出如下合理假设：

假设1仓库拣货人员数目大于1，所有人以相同行走速度共同负责仓库拣选。

假设2每个拣货人员每次拣选一个订单，根据下单时间顺序进行拣选，拣选一个订单的行走路径为当前可走路径中的最短路径，另外不考虑小车载重问题。

假设3每个货位只存放一种商品，任意货位的商品数量能够满足任意一个订单所需该种商品的数量要求，即不考虑商品数量与缺货问题。

本文中使用的变量说明如表1所示。

Table 1 Variable description

4.2 评估指标

本文提出了3个单一评估指标和1个综合指标用于评估货位摆放方案的优劣，3个单一指标对应3个优化目标，包括缩短行走路径、缓解堵塞及减少拣货人员数量。

4.2.1 缩短行走路径

由于行走时间占整个配送中心总作业时间的60%，所以从缩短拣货人员的行走路径为主要优化目标。由假设可知拣货人员以订单为单位进行拣选，故需累加拣选所有订单的行走路径。由于低层人工拣货仓库布局不规则，无法指定启发式行走策略来降低计算复杂度，故为了满足时间复杂度要求，本文选择了2种算法求解各订单的行走路径:动态规划算法与贪心算法。当单次访问货架节点很少时，采用动态规划求解精确最短路径，否则采用贪心算法求解近似最短路经，以减少计算耗时。

第1个评估指标为拣选所有订单的行走路径总和Zdis，后文简称行走总路程，其计算如式(5)和式(6)所示：

(5)

(6)

其中,Zk表示拣选订单k的最短行走路径；MDk表示拣选订单k的所有可能的取货方案。取货方案是指完成该订单所需访问的货架点集合及打包点，由于不同的货架可能存放相同的商品，而在取货时一个订单对应的某种商品只需访问其中一个货架即可，故单个订单可能存在多个取货方案；SDk表示订单k的任意一个取货方案；len(SDk)表示取货方案SDk所包含的访问点个数。虽然订单具有小批量、高频次的特点，但难免存在包含访问节点数过多的大订单，若继续采用动态规划计算行走路径会耗时过多。故为提高算法效率，通过设置拣选单个订单访问节点个数阈值len_k来决定采用何种方式计算行走路径，如果当前拣选订单需访问节点个数超过该阈值，则采用贪心算法，否则采用动态规划算法。

(7)

(8)

(9)

s.t.xij∈{0,1},xii=0,i,j∈SDk

(10)

(11)

(12)

(13)

4.2.2 缓解堵塞

将热销商品聚集到离打包点近的货架可使行走路径大大缩短，但很可能引起堵塞。是否发生堵塞与订单到来时间、订单包含的商品种类数、订单被拣选的开始时间、订单实际拣选路径、人员数量、行走速度等因素有关。难以通过模拟拣选来记录不同工作人员在仓库中的时间与位置，进而计算堵塞的频率和累积耗时。故本文通过统计某一段时间内各个货架的取货频次标准差，来表征该时间段内可能的堵塞情况。某货架的取货频次是指拣选人员在该货架的取货次数。取货1次是指任意1个工作人员在拣选任意1个订单的过程中，只要在某个货架处停下拣货，则为1次取货，那么该货架的取货频次加1。

因为订单处理存在拣选时限，不同处理时间段的订单拣选不会相互影响，所以直接对很长一段时间内的订单统计取货频次计算标准差来表征堵塞程度并不是很合理。因此，本文首先对订单分批，不同批次的订单拣选不会发生堵塞，然后计算各个批次对应的取货频次标准差，最后累加求和，以此表征堵塞程度。订单分批主要按时间窗口处理，通过考虑拣货人员的工作时间段，商家指定的订单拣选时限或当天发货截止时间，在满足不出现超时订单影响顾客购物体验的条件下为各个订单指定处理时间段。

在本文算例中,上海某电商物流企业指定每天t点前下单可当天发货,订单发货时限tf为24 h，故可知当天t点后到第2天t点前之间的所有订单须在第2天工作时间段内发出，分批时间窗为当天t点至第2天t点，在此时间段内到来的所有订单为一个批次，最终得到多个批次。

虽然标准差越大发生堵塞的可能性越大，但也不是越小越好。因为优化的最终目的是减少拣选时间，而它不仅和堵塞耗时有关，还和行走耗时有关。由于不同货架距离打包点的位置不同，行走耗时也不同，故允许不同货架的取货频次不同。本文考虑距离得到表征不同货架之间的允许取货频次差异的变量F，然后在此基础上计算取货频次标准差。Fi表示在货架si拣货1次相当于在距离sp最近的货架处等待拣货Fi-1次后取货1次，即允许在距离打包点最近的货架取货频次是在货架si取货频的Fi倍，Fi计算如式(14)所示：

(14)

其中,dissi表示货架si到打包点sp的距离；dismin表示所有货架中距离打包点最近的货架与sp的距离。tq表示拣选单个订单的过程中在某个货架处拣货1次需要花费的平均时间，也表示堵塞1次需要等待的平均时间，其计算如式(15)所示：

(15)

其中,s_m表示平均1个订单包含的商品数。

通过Fi可确定不同货架的最佳取货频次，只要各个货架实际取货频次满足此条件，则认为达到了最佳取货频次状态，此时衡量堵塞程度的标准差应为0。本文利用Fi与货架si实际取货频次计算在考虑货架差异情况下的取货频次标准差之和Zstd，后文简称堵塞指标,其计算如式(16)所示：

(16)

其中,M表示批次数；ZK表示拣选完批次K的所有订单后各个货架的取货频次的方差，其计算如式(17)所示：

(17)

其中,N表示当前仓库的总货架数；fi表示货架i的实际取货次数；fmean表示对各个货架的实际取货频次乘以对应Fi后的平均取货频次，其计算如式(18)所示：

(18)

4.2.3 减少人员数量

拣货人员的工作时间主要花费在行走、拣取商品和打包3个方面。行走时间与行走速度、距离有关；拣选商品时间与拣取1次的平均时间、拣取频次有关；打包时间与打包速度、订单数量有关。所有影响拣选时间的因素中无论是行走速度、打包速度还是订单数量都无法通过合理的货位摆放得到优化，只有行走路径和拣取频次能够优化。通过计算工作总耗时便可计算出所需拣货人员的数量。首先，将行走速度、打包速度简化为平均速度定值，捡取1次商品的平均时间tq根据式(15)求得;然后,通过货位优化缩短行走路径和降低拣货频次，进而减少拣选总时间和所需拣货人员的数量。由前文分析可知，为防止订单超时，拣选人员须按时处理完各个批次的所有订单，即人员数量需满足花费时间最多的批次不能出现超时订单。故此优化目标需分别计算各个批次所需花费的总时间，包括行走时间、拣取时间和打包时间，从中找出花费总时间最多的批次，并记录该批次的行走路径与拣取总频次，即2个评估指标。而行走路径已作为第1个指标被单独提出，所以只需评估耗时最多的批次对应的拣货总频次之和即可。综上可知，为花费时间最多的批次j对应的取货总频次Zq,后文简称取货总频次，其计算如式(19)～式(24)所示：

(19)

(20)

(21)

(22)

(23)

(24)

4.2.4 综合评估指标

采用不同的评估指标从不同优化角度来衡量货位摆放方案的优劣时，目标函数可能朝不同的方向收敛，故无法利用多个指标同时评估以选出最优摆放方案。因此，本文采用简单加权方法将多个指标值加权成综合指标进行评估，各个单指标如下所示：

(1)平均每批次行走总时间Ztd如式(25)所示:

Ztd=Zdis/(M×v)

(25)

(2)取货频次标准差之和Zstd见式(16);

(3)耗时最多批次所对应的取货时间Ztq如式(26)所示：

Ztq=Zq×tq

(26)

最后利用简单加权法将3个指标组合为如式(27)和式(28)所示的综合评估指标Z：

Z=αZtd+βZstd+λZtq

(27)

s.t.α+β+γ=1

(28)

5 实验结果及分析

本文基于上海某电商物流企业的多个实际订单数据和4种货位优化对比算法，验证了本文提出的基于社区划分FU的货位优化算法的有效性。

5.1 对比算法

(1)基于随机的货位优化算法：首先随机生成多个货位摆放方案，再利用评估指标从中选出较优方案。

(2)基于社区划分Infomap的货位优化算法：该算法是指本文提出的基于社区划分的货位优化算法中的划分步骤由Infomap划分算法完成，设置该算法的目的是探究不同划分算法对本文所提算法的影响。

(3)基于贪心算法的货位优化算法：该算法的思想是将最好的商品及其部分关联商品摆放到最优货架。最好的商品是指热度最高的商品，部分关联商品是指与该商品的密切度高于指定阈值的所有商品。某商品与其它商品的密切度为两者的关联度除以该商品与所有商品的关联度之和。最优货架通过评估值找出，货架ex_si的评估值计算如式(29)所示：

(29)

其中，c表示常数；J表示所有货架集合；freespace(sj)表示货架sj的剩余空位;dis(si,sj)表示货架si与sj之间的距离,如果si=sj，则dis(si,sj)为常数A；dis(si,sp)表示货架si与打包点sp之间的距离。

(4)基于遗传算法的货位优化算法：主要根据4.2.4节中的综合指标建立货位优化模型，之后采用改进的遗传算法进行求解。首先，生成一定数量的随机货位摆放方案，单个摆放方案可指定任意货架上的任意货位存放何种商品，即为一条染色体；然后，进行大规模的随机探索求得最优方案。随机探索过程包括交叉、变异、调整修复和适应度计算。

5.2 实验数据及变量设置

本文实验数据来自上海某电商物流企业2019年某月的订单，总共25 397个订单，包括560个商品种类，商品体积小且重量轻。该企业仓库的部分实际布局如图2所示，共48个货架且每个货架都有固定取货点，包括2种货架类型：类型1(虚线框)有14个且每个货架有22个储位，类型2(实线框)有34个且每个货架有9个储位。

为计算拣选路径，设置了2个假设：(1)拣货人员拣选时靠近货架边缘；(2)拣货人员走矩形路线而不进行斜线移动。基于假设抽象出用于路径计算的无向有权图如图2所示，任意2点之间的连线权重为2点之间的距离。

实验中使用的评估指标中的变量值如表2所示。本文考虑以行走路径为主要优化目标，综合评估指标和评估模型中的权重系数设置为α=0.8,β=0.15,γ=0.05。

Table 2 Variable settings

5.3 结果分析

本文评估指标包括3个单一指标和1个综合指标，其中单一指标包括行走总路径、堵塞指标和取货总频次。本节先分析本文基于社区划分的货位优化算法结果，然后对比不同方案的平均解和最优解。

基于社区划分的货位优化算法的多个货位摆放方案的各项评估指标值随着最大子社区阈值增大的变化情况如图3所示。从图3可以看到，基于社会划分FU的货位优化算法的综合指标值与单一指标值最优解都优于基于社区划分Infomap的货位优化算法的。此外，虚线一直存在波动，说明需要评估的方案较多；实线存在多个直线段，说明需要评估的方案较少。故基于社区划分FU的货位优化算法不论在方案质量还是评估时间上都优于基于社区划分Infomap的货位优化算法。这表明选择符合划分要求的社区划分算法对于改进本文所提货位优化算法非常重要。

表3是不同算法最终多个货位摆放方案的整体质量情况。由于各个算法的时间主要耗费在指标评估阶段，评估时间与评估方案个数呈正比，表3最后一列统计了每种算法需评估的方案个数。从表3可以看出，基于社区划分FU的货位优化算法仅需评估44个货位摆放方案，时间耗费上小于其余算法，仅占基于遗传算法评估时间的0.55%，占基于社区划分Infomap的12.43%，占基于随机方案的44%，占基于贪心方案的62.86%。基于社区划分FU的44个方案的行走总路径均值比随机100个方案的高31.98%，比基于贪心算法的高11.28%，比基于社区划分Infomap的高10.22%，比基于遗传算法迭代400轮后的最优20个方案的高9.54%。在主要优化目标为行走总路程时，基于社区划分FU的货位优化算法与其它算法相比能更快剔除大量的劣质摆放方案，找出优秀方案。

表4是5种优化算法的最优方案各项指标对比情况。基于社区划分FU的货位优化算法最优解的综合指标优于基于随机最优解28.61%，优于基于遗传算法最优解14.55%，优于基于社区划分Infomap最优解5.83%，优于基于贪心算法最优解5.06%；就行走总路径而言，基于社区划分FU的货位优化算法优于基于随机最优解29.67%，优于基于遗传算法最优解12.72%，优于基于贪心算法最优解9.34%，略高于基于社区划分Infomap最优解1.51%；基于社区划分FU最优解的堵塞指标优于基于随机最优解和基于社区划分Infomap的最优解，但高于基于遗传算法最优解与基于贪心算法最优解。显然这是行走总路程与堵塞指标朝不同方向收敛导致的结果，只需调整综合指标中相应的权重系数即可使得堵塞指标更小。

Table 3 Evaluation of the average solutions of different slotting optimization algorithms

Table 4 Evaluation of the optimal solutions of different slotting optimization algorithms

综上，本文提出的基于社区划分FU的货位优化算法与随机货位优化算法、基于遗传算法的货位优化算法及基于社区划分Infomap的货位优化算法相比，其方案质量更好，评估时间也占据优势；与基于贪心算法的货位优化算法相比，不仅在速度与方案质量上有一定优势，还在控制关联度的影响程度上有优势。因为基于贪心算法的货位优化算法根据密切度阈值控制热销商品周围应该存放的关联商品数，这使得它只能通过测试找出最优解可能出现的密切度阈值区间，然后再以更细粒度搜寻最优方案。与其相比，基于社区划分FU的货位优化算法在主要目标为行走路径，次要目标为缓解堵塞、减少工作人员数量时能够更快地剔除大量劣质摆放方案，直接获得多个优秀方案。

6 结束语

仓储优化一直是仓储发展的重要方向之一。本文根据实际问题需求，提出了基于社区划分的货位优化算法以及多个评估指标，并通过实验验证了该算法可有效提高仓储拣选效率，降低成本。

在后续工作中，可在以下方面继续展开研究：(1)基于社区划分的货位优化算法中的划分步骤可由不同的划分算法来完成，是否还有其它更高效的已有划分算法以及能否根据问题背景设计更加高效的划分算法还有待进一步研究；(2)本文货位优化算法主要针对人到货系统，也可通过改进算法的某些步骤使其适用于基于AGV的货到人智能仓储系统，例如划分阈值的上限、评估指标中的路径计算等，具体改进方法及适用效果还需进一步研究。