基于免疫算法的物流拣货路径优化问题的研究

贾 鹏 管 铮 徐善顶* 吴天豪

（1、南京工程学院电力工程学院，江苏 南京210000 2、南京工程学院数理部，江苏 南京210000 3、南京工程学院机械工程学院，江苏 南京210000）

当今社会的互联网技术在不断地高速革新，也因此造成了整个电商市场的蓬勃发展。而众多电商公司的客户会下达很多的订单，由此造成了订单下达仓库后，商品开始下架出售。而在仓库中有多个货架，每个货架有多个货格。每个货格中最多摆放一种商品，而商品可以摆放在多个货格中。

电商公司客户订单下达仓库后，商品开始下架出库，出库主要包含5 个流程：

定位→组单→拣货→复核→打包

定位：订单下达仓库后，确定商品下架的货格和每个货格下架的商品数量。

组单：将多个客户的订单合并，构成任务单。

拣货：拣货员在某个复核台领拣货车及任务单，然后按推荐顺序依次访问任务单中商品所在的货格，并将商品放在拣货车上，再送往某个复核台。到达复核台后，拣货员继续领取拣货车和任务单，开始下一个任务单的拣货流程。

复核和打包：拣货车放到复核台对任务中商品复核，审核是否多拣或者漏拣商品，然后将商品按照订单打包。

1 拣货路径距离模型的基础

在物流中心的某个仓库中，有着13 个复核台，4 排货架，其中每排25 组货架，每组2 个货架，共50 个货架，每个货架包含15 个货格。水平方向每组货架之间的距离为1500 毫米，竖直方向相邻两排货架纵向距离为2000 毫米，货格长宽都是800 毫米，复核台长宽都是1000 毫米。由于货架和复核台均为障碍物，拣货员们在此处时均不能通行，其余位置均可通行。为了方便距离的计算，此处不考虑拣货车的尺寸，货架和复核台高度。具体的3000 个货格与13 个复核台的示意图如图1 所示。

图1

本模型有关货架，货格，复核台，任务单的数据来源于第10届Mathorcup 挑战杯C 题，我们在计算拣货员在仓库中拣货时的行走距离时，将其分成复核台与复核台、复核台与货格、货格与货格三种类型。而复核台之间的距离可以简化为其坐标差的绝对值直接得出，复核台与货格之间的距离分成7 小类将其求出，货格与货格之间的距离分成5 小类来解出，最后将这三种类型的距离进行汇总，得出一个3013×3013 的距离矩阵。求解的部分结果如图2 所示。

图2

2 问题分析

我们已经了解到所有的复核台正常工作，任务单T0001 等待拣货，如何给一个拣货员P 规划出理想的拣货路线，从而获得最短的出库时间，这是我们现在需要解决的问题。该问题的约束条件是固定起点为复核台FH10，终点为运行正常的复核台FH01-FH13，任务单的数量仅有1 个（T0001）。我们可以看出这是一个典型旅行商（TSP）的问题，在众多的非线性约束条件下，可以通过免疫算法来求解出最优的拣货路线和出货最短时间。

3 免疫模型的建立

免疫算法是一种对多峰值函数进行多峰值检索，经过多次迭代，寻找全局最优的算法。为了抵御外来病毒的入侵，免疫系统对于其引入的抗原则产生相应的抗体。为了衡量抗原和抗体之间的匹配程度，我们引入亲和力的概念来判别出最好的匹配效果。因此，免疫算法适合该类路径优化问题。

下面基于本仓内拣货路径优化问题，建立免疫算法的模型：

（1）通过对采集的冀北地区中生代岩浆岩标本进行分类、测量密度等操作，基于统计数据得出：冀北地区偏基性的岩浆岩密度较高，而偏酸性岩浆岩的密度较低。两种岩浆岩密度在空间分布上呈现一定的规律。

（1）抗原的识别阶段：输入目标函数和各种约束作为免疫算法的抗原；

（2）初始抗体的产生阶段：在解空间中用随机方法产生抗体；

（3）适应度（亲和力）的计算：

抗体V 和抗原W 之间的适应度公式为：

axv=optw

抗体m 和抗体n 之间的适应度公式为：

（4）记忆单元的更新：将适应度高的个体加入到记忆库中，这保证了对优良解的保留，使能够延续到后代中；

（5）基于解的选择：选入适应度较高的个体，记其产生后代。所以适应度较低的个体将受到抑制；

（6）产生新抗体：通过交叉，变异，逆转等算子作用，选入的父代将产生新一代抗体；

（7）终止条件：条件满足，则终止；不满足，跳转到第（3）步。

图3

4 模型的求解

我们分别以13 个复核台作为终点，得到的最短遍历距离依次为：

399200，415600，438200，433700，429200，424700，420200，4 18900，454400，453500，449000，448000，452500。

由上数据比较，可知：当起点固定为复核台FH10，终点为复核台FH01 时，路程s 最短，为399200mm，即399.2m。

具体的拣货路线如下：

图4

下面我们求解出库花费的时间：

（1）路程时间t：

由上可得，最短路程smin=399200mm；

因此，

（2）取货时间t2：

由表中的数据可知，商品件数为1 的有13 个货格；

商品件数为2 的有4 个货格；

商品件数为3 的有6 个货格。

因此，t2=1×5×13+2×5×4+3×4×6=177s。

（3）复核和打包时间t3：

由于任务单t0001 打包了合计10 个订单，

因此，t3=10×30s=300s

综上所述， 出库花费的时间为：Tmin=t1+t2+t3=266.13+177+300=743.13s。

5 结论

通过建立免疫算法的模型，在解决物流规划问题的时候是非常合理的。比起常见的优化算法，例如蚁群算法、模拟退火算法、最小粒子群算法，该算法的收敛速度更快，在产生满足要求的最优解时所用时间较短。在真正的实际生活当中，根据预算成本的不同设置物流中心仓库货物的防置，从而快速计算出最短的拣货路径和出库时间，此算法在仓库货物配送规划当中也因此具有一定的参考意义。