仓内拣货路径优化模型概述

韩同卓 许佳乐 王贞 李俊丽 任杰

摘 要 仓库的拣货顺序与货物的摆放顺序对出库效率有着重要的影响。本文参考查阅大量相关资料，利用图论加权图表示出货格与货格、货格与复核台两两之间的距离关系，再使用蚁群算法建立拣货路径模型，从而求得理想的拣货路径。

关键词 蚁群算法;多目标规划;图论;逐层优化

1问题重述

电商订单下达仓库后，商品下架出库，该过程主要包括定位、组单、拣货、复核和打包。该仓库有13个复核台，200个货架共3000个货格，每个货格最多摆放一种商品。订单下达仓库后，进行定位操作确定商品下架的货格和所需下架的商品数量。拣货员在某个复核台领取任务单后，依次访问任务单中商品所在货格并下架商品，下架完毕后拣货员返回到某个复核台[1]。

基于以上条件，需解决以下问题：

在所有复核台正常工作的前提下，给拣货员P规划从复核台FH10领取任务单T0001 进行拣货的理想拣货路线[2]

2问题二的建模与求解

2.1 数据预处理

任务单中每个订单所在货格与所有复核台抽象成图论问题，并对该模型进行如下分析：已知赋权图，其中为货格与复核台的集合;

为集合C中各货格与复核台两两连接的集合;每一条边都存在与之对应的权值，本题中表示L集合两元素之间的距离并满足

若本题中拣货员P的拣货路线为，满足函数f（L）的值最小，则路径S就是所求的最优路径。

其中：

2.2 基于蚁群算法的模型

初始化信息， 设信息素启发式因子，表示路径的相对重要性;期望值启发式因子表示能见度的相对重要性;信息素挥发系数;信息素强度，表示蚂蚁携带信息素的量;每两个城市之间的距;信息素表示路径上的信息素强度;启发式信息，反映蚂蚁对下一个城市的能见度，通常取值;城市规模;蚂蚁数量。

在初始时刻各条路径上的信息素两相等，即[3]。

设为t时段位于城市i的蚂蚁数目，为t时段路径上的信息素，有：

通过迭代寻找最佳路径，蚂蚁k不能重复经过同一个城市，因此需要建立一个禁忌表来记录蚂蚁k走过的城市，并随着时间做动态调整。每一次迭代后对信息素进行更新。

蚂蚁k由城市i转移到城市j的状态转移概率：

一次循环结束后对残留信息进行更新处理如下：

每一次循环结束后对所有路径上信息素进行更新：

表示第k只蚂蚁在本次循环中所走路径的总长度[4]。

2.3 模型求解

（1）理想拣货路径求解

由蟻群算法模型求解流程，编写MATLAB程序。输入各个参数并对主要参数进行初始化：时间，最大循环次数为100，蚂蚁所携带的信息素量，初始时刻，蚂蚁数量，节点数，信息启发式因子，期望启发式因子，信息素挥发系数

根据题目要求，起始点为复核台FH10，终点为全部13个复核台之一，在MATLAB程序中考虑由起点坐标和所以货格组成节点，采用蚁群算法遍历所有节点，并在每一次迭代中，计算终点节点与每个复核台的距离，将最短的一个距离加入到蚁群算法的目标函数之中，并记录获得最短距离的复核台[5]。

（2）出库花费时间求解

根据题目知 出库时间=拣货员行走时间+商品下架时间+订单复核和打包时间，即

其中为第个订单号的商品件数，，根据（1）中求得的最短拣货路径，得出相应出费时间为1123.1s。

参考文献

[1] 卓雪雪，苑红星，朱苍璐，等.蚁群遗传混合算法在求解旅行商问题上的应用[J].价值工程，2020，39（2）：188-193.

[2] 张帅，彭玉青，赵镇，等.蚂蚁算法在公交查询最短路径求法中的应用[J].华中科技大学学报（自然科学版），2003（S1）：313-315.

[3] 刘建胜，熊峰，陈景坤，等.基于蚁群算法的双分区仓库拣货路径的优化[J].高技术通讯，2017（1）：72-78.

[4] 刘爱军，杨育，李斐，等.混沌模拟退火粒子群优化算法研究及应用[J].浙江大学学报（工学版），2013（10）：1722-1730.

[5] 樊明，郭艺，贠超，等.基于自适应混合算法的智能存取系统动态路径规划[J].系统仿真学报，2013（7）：1543-1548.