基于模拟退火算法仓内拣货的优化问题

冯爱芬， 闻博卉， 黄 宇

(河南科技大学 数学与应用数学系， 河南 洛阳 47100)

随着消费模式的转变，网络购物成为当今市场的一种重要消费模式。人们使用网络购物，不仅追求方便，也追求快捷[1]，物流运输的效率成为人们关注的内容。仓库作为商品出库的起始点，对物流运输效率有重要的影响。针对没有任何规划的拣货模式，需要对拣货路线进行规划，以达到“效率高”的目的。本文对仓库拣货员接到订单后拣货过程的路线进行最优规划。

1 数据来源

数据来自于2020年第十届MathorCup高校数学建模挑战赛C题：

仓库有13个复核台，4排货架，每排25组，每组2个，共2000个货架，每个货架包含15个货格如图1所示。水平方向每组货架之间的距离l1为1 500 mm，竖直方向相邻两排货架纵向距离l2为2 000 mm，货格长宽p1都是800 mm，复核台长宽p2都是1 000 mm[2]。

图1 仓库平面示意图

说明：

① 当绕障碍物折线行走时横向和竖向偏移都取d=750 mm；

② 复核台之间距离简化为两复核台坐标差的绝对值之和；

③ 货格与复核台距离简化为货格中点到复核台最近一条边中点的距离。

2 问题的描述与模型

2.1 问题描述

本文主要研究在单层二维情况下，多个订单的路线选择以及多个拣货员的订单分配问题。该仓库由多排平行的货架组成，每个货架包含相同个数的货格用来存放货物，复核台负责发放订单以及对拣货完成的订单进行打包。拣货员在开放的复核台领取订单，根据订单需求在对应的货格上取走货物，在开放的复核台进行货物打包。

2.2 数学模型

2.2.1 距离函数的建立

在求解过程中求得任意两个货格之间、任意一个货格与任意一个复核台之间、任意两个复核台之间的距离。构建以穿过下侧复核台中点的直线为x轴，以穿过左侧复核台中点的直线为y轴形成的坐标系，货格坐标由所给距离依次可得。

(1)货格与货格之间的距离

由于货格间的位置关系不同，距离D的计算方法有所不同，分为4种情况(为方便叙述，“任意两个货格”分别称为“货格1”与“货格2”,货格1的坐标为(x1,y1)，货格2的坐标为(x2,y2))：

① 货格1与货格2属于同一个货架组。当二者属于同一个货架组，二者的距离为他们各自到达过道的距离加上两个货格的距离以及为避开障碍物所需要的偏移距离。

D=|x1-x2|+|y1-y2|+2d

(1)

② 货格1与货格2位于同一过道的两侧。当二者位于同一过道的两侧，二者的距离可分解为竖向相距距离与横向相距距离，偏移距离在该种情况下不需要计算。

D=|x1-x2|+|y1-y2|

(2)

③ 货格1位于所在货格组的左侧(右侧)，货格2位于所在货格组的右侧(左侧)。二者的距离可分解为偏移距离，货架组的宽度以及二者各自到同一过道的距离。

D=|x1-x2|+|y1-y2|+2l1+2min[x1,x2,|15-x1|,|15-x2|]p1

(3)

④ 货格1与货格2位于所在货架组的同侧(同在左侧或右侧)。二者的距离可分解为偏移距离货架组的宽度以及二者各自到同一过道的距离。

D=|x1-x2|+|y1-y2|+3l1+2min[x1,x2,|15-x1|,|15-x2|]p1

(4)

(2)货格与复核台的距离

货格与复核台距离简化为货格中点到复核台最近一条边中点的距离，附件所给坐标简化为中点坐标。由于复核台与货格位置关系不同，会导致二者距离的计算方法也有所变化，仍将其距离分情况进行计算(为叙述方便，将任意复核台的坐标记为(x1,y1)，任意货格的坐标为(x2,y2))。

① 复核台位于左侧(x1=0)

(a)货格在复核台对面。该种情况类似于货格位于同一过道的两侧，此时二者的距离分解为竖向相距距离以及横向相距距离：

D=|x1-x2|+|y1-y2|

(5)

(b)货格位于所在货架组的右侧。二者的距离分解为一个偏移距离，横向相距距离以及 二者到最近同一过道的距离：

D=|x1-x2|+|y1-y2|+d+2l1

(6)

(c)货格位于所在货架组的左侧时。二者的距离分解为横向相距距离、二者到最近同一过道的距离：

D=|x1-x2|+|y1-y2|+d

(7)

② 复核台位于下侧(y1=0)

(a)货格位于所在货架组的左侧 。二者的距离分解为横向相距距离、竖向相距距离以及偏移距离：

D=|x1-x2|+|y1-y2|+d

(8)

(b)货格位于所在货架组的右侧。二者的距离分解为横向相距距离、竖向相距距离：

D=|x1-x2|+|y1-y2|

(9)

(c)货格位于复核台右侧

① 货格位于所在货架组的左侧。二者的距离分解为横向相距距离、竖向相距距离:

D=|x1-x2|+|y1-y2|

(10)

② 货格位于所在货架组的右侧 。二者的距离分解为横向相距距离、竖向相距距离以及偏移距离：

D=|x1-x2|+|y1-y2|+d

(11)

(3)复核台与复核台的距离

两复核台的坐标记为(x1,y1)和(x2,y2)，二者的距离与货格位于同一过道两侧的情况相同，求解方法也相同：

D=|x1-x2|+|y1-y2|

(12)

2.2.2 拣货员对一个货单进行拣货时最短路线的模型

设订单中有y件位于不同货格的商品需要进行取件，第i件商品与第j件商品所处货格之间的距离为xij,d1和d2分别表示第一个货格与其距离最近复核台之间的距离和最后一个货格与其距离最近的复核台之间的距离。则该问题的数学模型为：

(13)

s. t.

xi,i+1≥0(i=1,2,…,y)

(14)

di≥0(i=1,2)

(15)

其中，xi,i+1(i=1,2,…,y)表示在确定的一条行驶路线中第i个货格与第i+1个货格之间的距离。

2.2.3 多个拣货员对多个货单进行拣货时最短路线的模型

(1)模型假设

假设共有z个订单和x个拣货员进行拣货。每个拣货员每次只能执行一个订单的拣货任务，多个拣货员在同一个货格拣货时不需要等待，若多个拣货员同时在同一复核台进行打包时需要考虑等待时间。

(2)符号说明

表1 符号说明

(3)模型建立

求解拣货员的订单分配问题以及每个订单的拣货路线，使多个拣货员同时拣货的总时间达到最小，故有：

(16)

s.t.

Di=D(yi，S1i,S2i)

(17)

Di≥0,(i=1,2,…,z)

(18)

Wi≥0，(i=1,2,…,z)

(19)

2.3 模拟退火算法求仓内拣货优化问题

2.3.1 拣货员对一个货单进行拣货时最短路线问题的算法设计

到达货格的顺序可以自由选择，返回的复核台也是自由选择的。采取模拟退火算法进行最优路线的选择，通过结合概率的突跳特性在所有路线中随机寻找目标函数的全局最优解，即在从局部最优解中概率性地跳出并最终趋于全局最优，有效避免陷入局部极小[3]。进行多次迭代扰动，使其更快得到最优解。

步骤1：根据任务单i,找到任务单对应的所有货格的坐标，存储起来；

步骤2：设定初始温度temperature0=1 000*yi，初始迭代次数t=0[4]；

步骤3：输入货格坐标，计算初始路线下的行走距离距离d；

步骤4：使用蒙特卡洛方法中的多次迭代扰动，求出任意交换两个货格的行走顺序后的新路线的行走距离d′；

步骤5：比较新老路线的差值Δ=d-d′;

步骤7：令temperature=temperature*0.99，t=t+1;

步骤8：由已求得的最优路线，通过for循环找到与其第一个货格与最后一个货格最近的复核台，计算距离，求出总距离。根据商品的下架速度和拣货员的行走速率求所有任务复核打包完成所花费的时间。

2.3.2 多个拣货员对多个货单进行拣货时最短路线问题的算法设计

假设n个复核台正常工作，m个任务单等待拣货，一共有r个拣货员负责拣货。可能会出现拣货员完成拣货，在复核台排队等候的问题。具体步骤如下。

步骤1：分别计算出完成每个任务单所需要的时间，令第i个任务单的完成时间为ti(i=1,2,…,m)[6]。

步骤2：根据排队理论安排领取顺序，将任务单所需时间按从小到大的顺序进行排列，令r个拣货员按照新的货单顺序依次领取任务单。

步骤3：按照拣货员对一个货单进行拣货时最短路线问题的计算方法计算每个拣货员完成自己的任务单所需的时间Tj(j=1,2,…,r)，此时Tj(j=1,2,…,r)不包括不同拣货员在复核台等待的时间。

3 算例及结果分析

先假设有4个复核台(FH01、FH03、FH10、FH12)正常工作，40个任务单(T0001～T0040)等待拣货，一共有9 个拣货员(P1～P9)负责拣货。利用模拟退火算法得到的行走路线与按订单原始路线进行对比如表2所示。

表2 模拟退火算法的计算结果与订单顺序行走路线计算结果的对比

由表2看出，利用模拟退火算法得到的路线进行拣货，拣货员的拣货时间与按照订单顺序进行拣货所需时间明显减少，复核台的利用效率得到了大幅度提升。

4 结 语

运用模拟退火算法，提供一种解决多个拣货员面对大量订单时的路线规划和订单分配的解决方法。结论表明：多个拣货员及拣货台的情况下，合理的分配订单并选择路线可以大幅度提升拣货效率，证明模拟退火算法对仓内拣货的订单分派及路线规划有指导意义，对物流运输行业也有一定的指导意义。