秦进，杨淑钧，戴博
(1. 中南大学 交通运输工程学院，湖南 长沙 410075；
2. 湖南工商大学 工商管理学院，湖南 长沙 410205；
3. 特鲁瓦技术大学 工业系统优化实验室，法国 特鲁瓦 10004)
随着经济社会快速发展和互联网技术的日益更新，电商行业发展迅猛。在面对海量客户需求的环境下，电商订单还呈现出高频率、多品种、小批量等特性，这都使订单处理变得极为复杂，也对电商物流的运营水平等提出更高要求[1]。在电商物流中心日常运营中，特别是在双十一、双十二等大促时期，如何准确快速处理海量订单、缩短商品交付时间，已成为电商企业核心竞争力的关键所在。订单拣选是电商物流仓储的关键环节，是指按订单从存储位置取出商品的全过程。在传统的“人到货”拣选系统中，人员行走时间占拣货总时间的50%+，导致拣选效率低下[1-2]，难以满足电商时代对订单处理的需求。为节省人工并提高拣选速度，在智能化趋势下，越来越多电商企业开始使用移动机器人拣货系统(Robotic Mobile Fulfillment System, RMFS)完成订单拣选[3]。以亚马逊Kiva系统为代表，RMFS采用机器人进行货物存储、搜索、选择和运送工作，实现“货到人”拣选模式的转变。然而RMFS系统也带来一系列新的挑战。一方面，如何根据订单信息快速匹配货架和拣选站，合理规划机器人行走路径，对系统协同调度能力提出了考验；
另一方面，目前常用的“先到先拣选”(First-Come-First-Service, FCFS)策略往往会造成货架重复进出和机器人行走路线迂回，一定程度上会影响拣选设备性能的充分发挥和拣选作业效率。近年来，RMFS优化研究受到越来越多关注。TOMPKINS 等[2]指出Kiva系统中AGV取回货架的时间占比较大。WEIDINGER等[4]以货架往返总距离最小化为目标优化返回货架的位置分配。订单分配是按一定规则对订单进行分批或排序，以尽可能地满足多个订单的需求，减少人工或设备的重复作业，缩短拣选作业时间。对于人工拣选系统，王转等[5]指出里程节约的订单分批方法效果优于相似度分批法和传统先到先分批规则。MENÉNDEZ等[6]运用常规变邻域搜索算法解决订单分批和排序问题。相比于人工拣选系统，RMFS系统订单分配相关研究较少。YANG等[3]将订单排序与货架调度问题结合起来。BOYSEN等[7]研究了货架移动机器人系统中的订单分批、订单排序和货架顺序问题，但只关注单个拣选站处理过程，现实情况中往往是多个拣选站并行处理订单。拣选路径规划，目的是找出一条从起始点到目标点的最优路线，缩短拣选员或设备的移动距离。在人工拣选系统中，TOMPKINS等[2]总结了穿越法、最大间隙法、通道接通道法、返回法和中点回转法等常用的拣货路径策略。王宏等[8]考虑了传统双区型仓库下的拣选员行走路径问题。而RMFS系统下的路径规划问题，需要在人工拣货路径规划经验的基础上充分考虑机器人移动特性。夏扬坤等[9]将多种类AGV物料配送规划问题归结为带软时间窗的需求依订单拆分车辆路径问题。张喜妹[10]针对Kiva系统的路径规划问题提出了改进的A*算法。综上所述，在RMFS订单分配决策的既有研究中，较少考虑多订单、多货架、多拣选站之间的分配关系和机器人运输距离。同时，研究多集中于订单分配或路径规划的单独决策，针对两者的联合优化问题目前才开始得到重视。因此，本文立足电商企业场景下的RMFS系统特性，考虑多个拣选站和距离因素，以机器人负载距离最小化为目标，构建订单分配和路径规划联合优化模型，并设计A*和自适应大领域搜索(Adaptive Large Neighborhood Search, ALNS)算法进行求解和分析。
RMFS系统由可移动货架、移动机器人、拣选站台等部分组成，采用网格排列的模式。可移动货架是RMFS系统中的存储设备，货架上的料箱用于存放商品，底部一层中空留出机器人运输空间。当系统下达订单任务时，机器人沿着指定路线到达待拣选货架位置，将货架顶起离开地面后搬运货架前往目标拣选站，等待人工拣出商品再运送货架回到存储位置。拣选作业区域并行排列多个拣选站，每个拣选站可同时处理的订单数量有限。在拣选站台内，拣选员借助激光指示器、条码扫描仪等设备，从货架上取出商品放入货箱中[4]，拣选完毕后订单对应货箱经传送带输送到出库区打包，重复上述过程直到完成所有订单。
在此场景下，RMFS系统订单分配的决策问题包括：1) 如何划分订单批次；
2) 寻找能够满足每个批次订单商品需求的待拣选货架；
3) 为每个批次订单和待拣选货架指定一个拣选站。由于待拣选货架需要借助机器人搬运至拣选站，完成拣货作业后机器人再运送其返回货架存储区域，因此机器人行走距离是影响订单分配的重要因素。
图1 RMFS系统仓库布局示意Fig. 1 Schematic layout of a warehouse section in RMFS
RMFS系统路径规划的决策问题是确定机器人行走路线及距离。机器人的行走路径包含3个部分：1) 从当前位置到目标货架；
2) 运送待拣选货架至目标拣选站；
3) 从拣选站运送货架返回存储位置。其中，1) 为空载距离，机器人可以无负荷穿梭于货架底部；
2)和3)为负载距离，机器人只能在通道内运输货架。由于机器人在货架和拣选站之间来回的负载距离占据总距离的主要部分，对负载距离进行优化可以替代机器人行走总距离实现缩短订单拣选时间、降低机器人能耗的目标[4]。因此，本文以机器人负载距离最小化为目标，将订单分配与路径规划问题联合起来，并划分为2个阶段：第1阶段路径规划，找出货架到不同拣选站之间的最短路径，即机器人负载距离，标记路线和长度；
第2阶段订单分配，根据第1阶段所得到的最短距离，以最小化机器人负载距离为目标，生成订单分批计划，确定合适的批次出库货架及任务拣选站，从而建立起订单、批次、货架、拣选站之间的顺序关系。
为了便于开展研究且不失一般性，本文做出下列假设：1) 订单需求信息、货架存储信息已知，仓库采取随机存储策略，商品可以存储在任何可用货位；
2) 无缺货现象，所有货架上的商品库存数量总和大于所有订单的需求数量；
3) 订单交付时间相同，批次内订单顺序、待拣选货架到达拣选站顺序任意；
4) 一个批次订单只能由同一个拣选站完成拣选，不能拆分到其他拣选站；
5) 待拣选货架不在拣选站之间移动，在一个拣选站完成拣选任务后随即返回存储区域；
6) 每个货架规格属性相同，存储位置不变，货架出库完成拣选任务后回到初始存储位置；
7) 静态路径规划，不考虑机器人行进过程中的拥堵或避碰情况。
在建立模型前，对参数和变量进行定义，具体如表1所示。
表1 符号定义Table 1 Notation definitions
由此，以机器人负载总距离最小为目标，建立RMFS系统订单分配与路径规划混合整数规划模型如下：
目标函数(1)表示所有批次出库货架往返于存储位置和拣选站之间的距离，即机器人负载总距离最小，drs为机器人运送货架r到拣选站s的最短距离。式(2)～(10)表示约束条件。式(2)和(3)确定订单与批次的对应关系，式(2)表示一个订单只能被分配到一个批次，式(3)表示批次容量，每一批次中最多包含C个订单。式(4)～(6)确定批次订单与货架的对应关系，式(4)表示从待拣选货架上拣出的商品数量必须满足每一批次订单需求，式(5)表示初始库存限制，式(6)建立拣选商品数量与货架是否被选择之间的关系，使约束线性化。式(7)和(8)确定批次订单与拣选站、批次货架集与拣选站之间的对应关系，式(7)表示一个批次订单只能在同一个拣选站中进行拣选作业，式(8)表示每一批次出库货架集前往该批次指定的拣选站。式(9)和(10)表示变量的取值范围。
RMFS系统订单分配与路径规划联合问题在订单分批问题的基础上增加了货架和拣选站的任务指派及机器人路径规划，是NP难问题。精确算法求解此类问题需要耗费较长时间，本文设计了两阶段的启发式算法对订单分配和路径规划联合问题进行求解。
由于A*算法是静态路网中求解最短路径的有效方法，被广泛应用于机器人路径规划[11-12]，第1阶段首先使用A*算法求解路径规划问题。自适应大领域搜索算法(Adaptive Large Neighborhood Search, ALNS)最初由ROPKE等[13]提出用于解决带时间窗的取送货车辆问题，算法通过动态选择移除算子和修复算子不断对解进行破坏和重构，具有快速收敛的特性，容易跳出局部最优，已适应越来越多的优化场景。ŽULJ等[14]构建了ALNS和TS禁忌搜索的组合方法解决大规模订单分批问题。王新等[15]根据车辆与无人机联合配送路径问题特性设计了相应的ALNS算法。李婷玉[16]指出在多商户多车程同城物流配送车辆路径问题中，ALNS算法能够以较低成本获得最优解，效果优于TS算法。因此，第2阶段使用ALNS算法对订单分配问题进行求解。
3.1 A＊算法
A*算法结合了Dijkstra算法和最佳优先搜索的思想，通过选择合适的估价函数计算当前节点到目标节点代价最小的距离，启发式选择路径的搜索方向，最终确定整条路径。A*算法的估价函数可表示为：f(n)=g(n) +h(n)。其中，f(n)表示从起点到终点的估价函数，g(n)表示从起点到当前节点n的实际代价，h(n)表示当前节点n到终点的估计代价。
由于RMFS系统通常设置在网格上，而且机器人只能朝正北、正南、正东、正西4个方向直线移动，选择栅格法对仓库环境进行建模，对机器人运动的二维平面区域建立直角坐标系，以1为单位建立一个栅格，采用曼哈顿距离对距离进行度量，两点之间的曼哈顿距离为南北方向距离加上东西方向距离，即：d=|x1-x2|+|y1-y2|，其中，(x1， y1)和(x2， y2)分别表示2点坐标。
3.2 自适应大领域搜索算法(ALNS)
在传统ALNS算法的基础上，根据RMFS订单分配问题特性，设计改进ALNS算法进行模型求解。
3.2.1 初始解生成
采用随机方法生成初始解。首先在不违反批次容量约束的前提下，依次将订单随机放入候选批次，生成订单分批方案。接着根据商品库存信息，寻找满足每个批次订单需求的货架，为批次随机分配任务拣选站，得到初始解决方案。为了更好地表示订单分批以及货架拣选站分配的过程，设计了对应解的编码。
订单分批时按订单编号顺序排列，每一订单i位置上的数字对应着批次b。例如编码[1, 3, 2, 1]表示订单1和4划分到批次1中，订单2划分到批次3中，订单3划分到批次2中。分配货架和拣选站时，建立如图2所示的二维数组，纵轴为批次，横轴为货架。货架出库状态用0和正整数表示，0表示在批次订单b中货架r不出库；
正整数表示拣选站编号，即货架r出库执行批次订单b的拣选任务，去往批次指定的拣选站s。示例中批次1的出库货架为2，3和5，前往拣选站3进行拣选。
图2 货架和拣选站分配编码Fig. 2 Rack and picking station assignment code
3.2.2 移除算子和修复算子
在生成初始解后，ALNS算法采用移除算子将一定比例ξ的节点从解中删除，再利用修复算子将移除列表里的节点重新插入到不完整的解中，形成新解。
对于订单分批问题，设计了2种移除算子和2种修复算子。1) 随机移除订单。在当前解中随机选择一定数量的订单，将它们移出原来所在的批次。该操作可增加解的多样性，使其不易陷入局部最优解。2) 最差距离订单移除。计算每一订单对应的批次负载距离，移除距离较长的订单。3)随机修复订单。随机生成批次编号，插入到被破坏的解中。4) 贪婪插入批次。将移除的订单插入到距离最短的批次中。
对于货架和拣选站的分配，同样设计2种移除算子和2种修复算子。1) 随机移除货架和拣选站。选择一定数量的批次，移除批次中对应的任务货架和拣选站。2) 移除最差批次货架和拣选站。计算负载距离较长的批次，移除货架和拣选站。3) 随机修复货架和拣选站。随机分配货架和拣选站给被破坏的批次解。4) 贪婪修复货架和拣选站。比较货架和拣选站的不同分配情况，选择使批次负载距离增加最少的分配结果。
3.2.3 自适应机制
自适应机制是ALNS算法的核心部分，其基本思想是根据产生的新解情况为移除算子和修复算子赋予相应的分数。当得到新的全局最优解时，算子加分σ1；
当得到一个尚未接受过但比当前解更好的解时，算子加分σ2；
当得到一个尚未接受过且比当前解差，但满足接受准则的解时，算子加分σ3。将ALNS算法分为若干阶段，算法根据前一个阶段的表现更新算子的权重，权重更新公式如下：
其中：wi表示算子第i阶段的权重；
βi表示算子评分；
αi表示算子累计的调用次数；
ρ为权重更新系数，控制权重变化速度。算子的表现越好，得分和权重越高，下一阶段被轮盘赌选择的概率越大。
3.2.4 接受准则和终止条件
为了避免陷入局部最优，根据模拟退火算法的Metropolis准则以一定概率P=e-[f(xnew)-f(xcurrent)/T]接受劣解。其中，T为当前温度，每次迭代T=T0·θ，T0为模拟退火初始温度，θ∈[0， 1]为降温速率；
f(xnew)为新解的目标函数值；
f(xcurrent)为当前解的目标函数值。每次迭代中内层模拟退火过程的终止温度为Tend，算法达到最大迭代次数后停止搜索。
4.1 算例构造
如图3所示，生成小规模(10×8)、中等规模(10×15)、大规模(10×30)3种不同大小的仓库栅格地图进行仿真实验。货架、拣选站、机器人大小相同且占用一个栅格，机器人行走步长为1。小、中、大3种规模算例的参数设置分别如下：货架个数为25，50和100，拣选站个数为2、3和4，订单分批容量为5，10和15，SKU商品总数为50、100和200，每张订单上SKU种类范围为[1, 3]，[1, 5]和[1, 7]。另外，仓库内每个货架随机存储1～6种SKU，每种SKU的库存量范围为[10, 50]，订单需求量范围为[1, 5]。仿真实验测试的最大订单数量为500。
图3 小规模、中等规模、大规模仿真仓库栅格地图Fig. 3 Small scale， medium scale， large scale simulation warehouse grid map
根据ROPKE等[13]的分析，通过多次实验确定ALNS算法参数：自适应机制中算子分数设置为σ1=33，σ2=9，σ3=13，权重更新系数ρ=0.1；
根据文献[16]，破坏解的长度比例ξ=0.2；
在接受准则中，每次迭代内层模拟退火过程的初始温度T0=100，终止温度Tend=10，降温速率θ=0.99，外层最大迭代次数为100。
4.2 结果分析
所有实验均在Python 3.6中编程实现，运行环境Intel(R) Core(TM) i5-1135G7 @ 2.40 GHz ，16 GB内存，调用IBM ILOG CPLEX12.8，最大运行时间设为5 h(18 000 s)，每组实验重复10次取均值。
在A*算法得到货架至拣选站最短距离及机器人搬运路线的基础上，使用FCFS、CPLEX和ALNS算法分别求解小、中、大3种规模算例的结果如表2～4所示，并将实际运营中常采用的先到先拣选结果(FCFS)作为对比基准。其中Obj表示目标函数即机器人负载总距离，Imp表示CPLEX或ALNS求解结果对比FCFS基准数值的改进程度，Gap表示ALNS与CPLEX求解结果之间的差异程度。
表2 小规模算例求解结果Table 2 Results of small-scale experiments
从小规模算例求解结果中可以看出，相比简单的FCFS规则，进行订单分配后优化效果明显。其中CPLEX求解平均减少49.3%的机器人负载距离，在订单数量I=20时效果最佳，减少52.5%负载距离。ALNS算法的求解质量也较高，平均减少31.1%的机器人负载距离，在I=10时最大可减少47.6%的负载距离，与CPLEX求解差距均值15.2%，最少为5.8%，得到与CPLEX质量相近的解。
求解时间方面，当订单数量较少时(I≤20)，CPLEX可以在1 s内求得最优解。但随着订单数量的增加，CPLEX求解时间呈指数级增长，在I=40时，计算时间已高达7 027.4 s，当订单数量为50时已无法在可接受的时间(5 h)内获得可行解。
对于仓库规模大、订单数量多、时间要求高的场景来说，使用CPLEX对订单进行优化分配实用性差。而ALNS算法受订单数量增加变化的影响较小，在订单数量达到100时仍可在较短时间内(588.1 s)获得21.1%的优化效果，时间优势明显，相比CPLEX求解器更适合求解规模较大的订单分配问题。
由于CPLEX在订单数量较大的小规模算例中已难生成可行解，中等规模算例中仅对比FCFS和ALNS算法的求解结果。ALNS算法在中等规模算例中仍保持着平均20.1%的优化效果，时间成本低，可在较短时间内获得高质量的解。
表3 中等规模算例求解结果Table 3 Results of medium-scale experiments
表4 大规模算例求解结果Table 4 Results of large-scale experiments
在大规模算例中，ALNS算法平均可减少10.7%的机器人负载距离，最大可减少15.8%的负载距离(I=360)。当订单增加到500时，ALNS算法的运行时间也仍保持在合理范围内(3 967.9 s)。
图4记录了ALNS算法在不同规模算例下的计算迭代过程。可以看出ALNS算法基本不依赖初始解的状态，能显著减少机器人负载距离，算法收敛较快，性能稳定。
图4 ALNS算法迭代过程Fig. 4 Iterative process of ALNS algorithm
1) 研究电商物流中心RMFS拣选系统多订单、多货架、多拣选站场景下的订单分配和路径规划联合优化问题，构建了以机器人负载距离最小为目标的混合整数规划模型，并使用A*算法和自适应大邻域搜索算法(ALNS)进行求解。
2) 仿真结果表明，提出的优化模型和算法最大可缩短47.6%的机器人负载距离，ALNS算法可在较短时间内获得高质量的解，优化效果良好，能够有效缩短机器人行走距离，提高订单拣选效率，降低仓储成本，研究结论可为电商企业提供运营指导。
3) 未来的研究可以引入更多决策因素，如订单顺序、到达时窗、动态货位、机器人任务分配等，细化订单分配与路径规划联合问题特征，使问题更符合RMFS系统实际运营场景。
猜你喜欢算例货架算子与由分数阶Laplace算子生成的热半群相关的微分变换算子的有界性数学物理学报(2022年5期)2022-10-09拟微分算子在Hp(ω)上的有界性数学物理学报(2021年2期)2021-06-09各向异性次Laplace算子和拟p-次Laplace算子的Picone恒等式及其应用应用数学(2020年2期)2020-06-24一类Markov模算子半群与相应的算子值Dirichlet型刻画数学年刊A辑(中文版)(2018年2期)2019-01-08邵国胜：实现从“书架”到“货架”的跨越科学中国人(2018年1期)2018-06-08投资无人货架适合吗？中国储运(2018年4期)2018-04-08货架行业:需求变化带动创新发展物流技术与应用(2017年3期)2017-05-17基于振荡能量的低频振荡分析与振荡源定位（二）振荡源定位方法与算例中国学术期刊文摘(2016年2期)2016-02-13互补问题算例分析新乡学院学报(2015年6期)2015-11-06基于CYMDIST的配电网运行优化技术及算例分析电网与清洁能源(2015年2期)2015-02-28