基于蚁群算法对调度车辆进行路径最优化设计
2022-04-27戴贤君胡徐胜滕官宏伟
曾 胜,戴贤君,胡徐胜,滕官宏伟
(1.皖江工学院 电气工程学院,马鞍山 243000;2.中国计量大学 生命科学学院,杭州 310018;3.中国人民解放军陆军装备部,株洲 412002)
冷链物流泛指冷链产品在运输、销售、消费的全过程,冷链运输是一项非常复杂的系统工程,自从物联网大会成立以来,国家重视发展冷链物流行业,但是随着新冠疫情的来临,冷链行业受到重挫,但是其功能的强大是不容忽视的。文献[1]针对已知工作环境,研究了移动机器人在复杂三维环境的路径规划的问题,提出一种改进的蚁群优化算法。文献[2]基于蚁群算法对水下潜器三维空间路径规划问题进行了研究。文献[3]基于改进蚁群算法,提高了在仓储系统三维空间内路径规划的效率与速度。文献[4]针对传统二维平面的随机搜索算法—蚁群优化算法不能满足三维空间路径搜索以及快速性要求等问题,提出了改进的方法。文献[5]针对蚁群优化(ACO)算法存在收敛速度慢以及易陷入局部最优的问题,提出了一种改进的ACO 算法来解决机器人路径规划问题。文献[6]提出一种改进的蚁群算法,引入了障碍探索的方法,将下一节点附近一定区域的障碍状况作为影响因素,如果影响蚂蚁寻找最优路径,则会规避此节点。文献[7]提出一种基于多目标优化的改进蚁群算法,在考虑路径长度的基础上将转向次数加入启发函数中。文献[8]提出一种基于资源状态的自适应蚁群优化算法 (MACO),利用虚拟机的状态来修正启发式因子和释放信息素浓度。文献[9]提出了基于改进蚁群算法规划机器人全局路径,在栅格地图中划定优选区域,并建立新的初始信息素浓度设置模型,对各点初始信息素浓度进行差异化设置,避免寻优的盲目性。文献[10]提出改进蚁群算法的有效性和合理性,其降低了复杂程度,优化了传统蚁群算法容易陷人局部最优的问题,提升了迭代运算的收敛速度。文献[11]在传统蚁群算法基础上提出一种改进的蚁群算法,先后分别采用局部最优和全局最优两种方式对传统蚁群算法的信息素更新方式加以扩大至最优解寻觅范围。文献[12]采用改进的蚁群算法对静态交通网络和动态交通网络分别进行最短路径的求解。本文利用传统的蚁群算法对配送车辆以及配送路径作出最优化选择并建立模型,达到节约运输成本并准时运送货物的目的。
1 车辆调度模型的建立
1.1 模型条件的假设
此模型设计假设只有一个物流中心点并把冷链物流食品运送到各个网点,确保冷链食品快速运输到目的地,要求每个配送点只能由一辆车进行配送且完成配送任务后需重返配送中心,其目标是优化配送车辆的路径使得在时间窗约束下总成本最低。图1所示为冷链物流中心点到各个城市的调度点。
图1 车辆行驶路径示意图Fig.1 Schematic diagram of vehicle driving path
对于冷链物流调度设置以下几个条件:
(1)调度中心只有一个调度点。
(2)不同的城市所对应的路径不同。
(3)中途配送过程中不增加新的任务。
(4)调度过程中要保证道路行驶过程通畅,无障碍物阻挡。
(5)配送车辆行驶距离必须能满足车辆配送条件。
(6)车辆调度数量应满足具体使用数量;配送车辆必须集中到唯一的调度中心点。
(7)每次调度车辆的数量必须满足客户需求;调度车辆中心必须知道客户使用车辆的具体位置,客户也必须知道调度车辆的具体位置。
(8)所有调度车辆的硬件设施、速度与型号相同;在配送车辆时保证每个车辆的油箱是加满状态以便于调度时的费用计算;调度点把车驾驶到客户的具体位置时其花费的每公里费用一样。
1.2 调度模型相关参数的设定
首先对调度车辆模型的目标函数进行设定:n 表示车辆调度点具体车辆数;B 表示用户调度车辆所花费的固定费用;sn表示所有车辆调度花费的固定成本;n 辆车中每辆车单独所花费的固定成本为r0;Q 表示调度车辆每行驶1 km 所花的行驶费用;dij表示调度点第i 辆车与第j 个客户之间的距离;λ1表示车辆在调度过程中所产生的油耗;λ2表示在调度车辆过程中单位时间产生的额外费用;t 表示调度车辆所消耗的时间;v 表示在调度过程中的车辆行驶的平均速度;ρ1表示用户在等待时所产生的额外费用系数;k1表示单位时间内产生的费用;ρ2表示客户在还车时单位时间内所产生的损失系数;k2表示在还车时产生的单位比例费用。
运输车辆固定成本为
假设本模型的运输过程中的成本只与车辆行驶的距离有关,其运输过程成本分别包括车辆行驶成本、车辆行驶额外成本、车辆还车时的成本为
调度过程中产生损失的运算公式即为
即整个车辆调度费用为
2 传统蚁群算法的模型建立
2.1 ACO 蚁群算法具体步骤
对蚁群中各蚂蚁的爬行路径进行仿真模拟,根据具体情况定义各个参数:设m 表示蚂蚁爬行的总体数量;bi(t)表示在某个t 时刻某个位置i 的蚂蚁个数;dij表示位置点i 与蚂蚁爬行位置点j 之间的距离;ηij表示坐标(i,j)的蚂蚁爬行能见度,反映了由调度点第i 个蚂蚁爬行位置点移到调度点j 的启发程度;τij表示蚂蚁位置(i,j)上的信息素强度;Δτij表示蚂蚁在坐标(i,j)上留下的轨迹信息素量单位长度;表示蚂蚁的转移概率,i 是蚂蚁目前的具体坐标,j 是蚂蚁还没有访问的具体位置;Lk表示蚂蚁爬行的总路程;Nc表示此路线迭代次数;Nmax表示此路线最大迭代次数;Q 表示蚂蚁在爬行过程中释放的信息素浓度。
蚂蚁总数为
两地行驶距离为
蚂蚁单次循环不可重复访问的转移概率为
设定ρ 表示信息素挥发程度,挥发程度表示为
式中:ΔCijk为第k只蚂蚁在车辆行驶位置点i 与车辆行驶位置点k之间释放的增加的信息素浓度;ΔCij为所有蚂蚁在i 与j 之间释放的增加的信息素浓度,其信息素增加公式为
比较NC和Nmax的大小,计算结果并输出。该算法中蚂蚁个数为m=100,信息素浓度随路径改变进行设定。Nmax=200 表示最大路线迭代次数。
2.2 传统蚁群算法仿真模型
(1)假设迭代次数为N=200,蚂蚁数量为100,信息素浓度为0.1,Alpha=1。图2所示为迭代次数与行驶路径图。
图2 蚁群算法仿真Fig.2 Ant colony algorithm simulation
(2)假设迭代次数为N=200,蚂蚁数量为100,信息素浓度为0.2,Alpha=2。图3为迭代次数与行驶路径图。
图3 蚁群算法仿真Fig.3 Ant colony algorithm simulation
(3)假设迭代次数为N=200,蚂蚁数量为10,信息素浓度为0.3,Alpha=3。图4为迭代次数与行驶路径图。
图4 蚁群算法仿真Fig.4 Ant colony algorithm simulation
2.3 基于传统蚁群算法模型改进
n 表示路径数量,蚂蚁在爬行过程中适当改变信息素浓度,即引入参数α,称为信息素减弱系数,其取值范围为(0,1),针对信息素增量调整如下:
信息素更新公式为
通过这种优化信息素更新的方法,不仅能够加快算法的收敛速度,同时还会增加最优路径被选中的机率,但又不会完全排除其它路径成为最优路径的可能性。
由三维的路径公式可知,其m 只蚂蚁当中的第k 只蚂蚁的转移公式为
式中:q0为[0,1]随机分配函数,为其中一个函数。
基于启发函数的基础,Πβ(β=1,2,3,…,n)上的任一点Pβ(iβ,jβ,kβ)的蚂蚁选择平面上Πβ+1(iβ+1,jβ+1,kβ+1)的概率为
式中:τβ+1为Πβ+1平面上点Pβ+1(iβ+1,jβ+1,kβ+1)的信息素量。
传统的二维蚁群路径优化算法已不能满足复杂众多的数据,三维蚁群算法的改善增强了其优化功能,如下取迭代次数为N=200,蚂蚁数量为100,信息素浓度为0.1,Alpha=3。其车辆调度路径添加其优化函数,则改进后的三维蚂蚁爬行路径与迭代次数如图5所示。
图5 改进后蚁群算法路径图Fig.5 Path diagram of improved ant colony algorithm
3 调度实际花费计算
3.1 配送路径规划
传统的车辆调度只是利用二维调度,没有考虑实际因素,而三维调度可以把实际情况考虑到调度因素上。表1为二维与三维坐标表。
表1 8 个调度点二维与三维坐标Tab.1 Two-dimensional and three-dimensional coordinates of 8 scheduling points
设定蚁群蚂蚁数量N=100,运算次数为200 次,其释放信息素浓度随之改变,Alpha 也随之改变。表2为车辆行驶实际距离所示。
表2 给客户派送车辆时其实际距离Tab.2 Actual distance when sending vehicles to customers
3.2 配送费用函数
配送中心对各个客户点进行配送,在同一个配送中心进行调度车辆。每辆车每公里运输费用为3元,平均车速为60 km/h,驾驶员正常工作费用为每小时10 元。利用上述模型,应用Matlab 进行算列求解,表3为两种算法的成本对比。
表3 算法改进前后具体调度成本Tab.3 Specific scheduling costs before and after algorithm improvement
在应用Matlab 仿真后,利用蚁群算法求解物流路径最优解。在相同的迭代次数情况下,未优化路径之前物流配送路径的平均长度要远远大于最优路径长度。在人员调度的情况下行驶里程最大节约了将近22 km,在二维算法调度距离为22 km,三维则为20.5 km。在模拟实现物流运输车配送轨迹时,根据不断调整道路的拥堵情况时物流车的配送轨迹也会得到相应的改变,从表3可以看出三维路径其优化距离更短。在算法中,路径是不断变化的,所以需要实时观察,选取接近直线路径的最优解。
4 结语
本文对冷链物流路径优化的研究是围绕路径优化求解算法和数学模型展开的,首先给出了冷链物流研究的背景和意义,根据冷链物流配送路径优化问题的特性,分析其成本构成要素,给出货损成本的数学模型,以配送过程中总成本最小为优化目标,建立对应的目标函数,并一一列出存在的约束条件;接着对求解路径优化问题的算法做简要阐述,同时说明了蚁群算法的特性和适用性,并将蚁群算法应用到冷链物流路径优化配送问题中。之后,给出基础蚁群算法的基本步骤和原理,验证模型和算法的有效性和优越性,假设某种模型配送为例,从软件分析结果找到配送方案,给出一系列分析数据,最终结果表明,利用三维蚁群算法求解最优路径时具有一定的优越性。