基于蚁群算法冷链物流运输路径最优化设计

曾 胜,戴贤君,肖 文,倪天伟,胡徐胜,滕官宏伟

(1.皖江工学院 电气工程学院,安徽 马鞍山 243000;2.中国计量大学 生命科学学院,浙江 杭州 310018;3.中国人民解放军陆军装备部,湖南 株洲 4120022)

本文以冷链运输过程中的车辆为监测对象,对冷链物流车调度展开研究,同时对冷链物流调度算法进行仿真优化,利用传统的蚁群算法来对冷链物流路径进行优化设计并与改进过后的算法进行对比。

1 车辆调度模型的建立

1.1 车辆调度模型基本条件的设定

配送车辆行驶距离必须能满足现实条件;每个冷链物流车辆调度必须满足冷链物流公司的产品运输量;冷链物流车须从调度中心出发,收到货物需回到调度车辆的出发点;调度车辆在接收到产品调度时,冷链物流公司不能够临时增加任务情况;每次调度冷链物流产品时,必须使调度车辆的数量足够;调度车辆的司机必须知道冷链物流产品具体位置,冷链物流公司也必须知道调度车辆的具体位置;所有冷链物流车配置与型号相同;对于每辆车的温湿度等参数设定保持不变。另外对冷链物流车空车与载物时的行驶路径不同,但是正好能够形成一个完整的闭合行驶路线。

1.2 调度车辆相关参数的设定

首先建立目标函数并对基本条件进行界定:m表示每个调度点冷链物流车的数量;C表示冷链运输公司的运输成本;rm表示第m辆车的运行成本;R0表示每辆车的运行成本;U表示运输车辆每行驶1 km所需要的费用;Sij表示第i辆车与第j个物流公司之间的距离(其一是调度中心的车辆行驶到物流中心距离,此路径必须保证物流车是空车,距离较近,即次路;二是调度车装满货物过后行驶到调度中心距离,此路径必须行驶正常路况,即主路);λ1表示配送过程中单位时间内维持车内温度的能源损耗;λ2表示卸载货物时外界热量进入车厢内使温度降低而产生的损失;p表示冷链物流公司装载货物消耗的时间;v表示冷链运输车辆配送货物过程的平均速度;ρ1为冷链物流配送过程中单位时间货物所产生损失比例;k1为单位时间内产生的费用;ρ2为冷链物流货物卸载时所产生损失比例;k2为卸货时所产生的单位比例费用。

若供货中心有M辆车的成本固定且均为rm=(m=1,2,3…M),即运输车辆固定成本为:

(1)

只与车辆行驶距离有关的运输过程成本分别为空车行驶成本、载物行驶成本、冷链物流运输车的冷却成本为:

(2)

运输过程中产生损失的运算公式为:

(3)

冷链运输过程中产生的总成本即为以下几种冷链运输过程中的损耗与成本之和:

水泥缓凝剂是用于改善水泥凝结时间的添加剂，使用量为水泥质量的3%-5%。磷石膏可替代天然石膏、脱硫石膏作为水泥缓凝剂，延长水泥的凝结时间，减缓水泥水化速度。目前，磷石膏产量最大的瓮福集团与周边水泥厂合作，提供磷石膏作为水泥厂的水泥缓凝剂，同时给予消耗磷石膏的企业一定的补贴。根据调查，西南水泥厂目前利用瓮福集团产生的磷石膏作为水泥缓凝剂，近三年磷石膏用量在水泥中的占比大约为2%左右。

C=C11+C12+C13+C2+C3

(4)

2 传统蚁群算法的模型建立

2.1 ACA蚁群算法具体步骤

(5)

蚂蚁单词循环不可重复访问的转移概率由下式确定:

(6)

设定ρ表示信息素挥发程度。即公式为:

Cij(t+1)=(1-ρ)*Cij(t)+ΔCij

(7)

ΔCij=∑ΔCijk

(8)

ΔCijk为第k只蚂蚁在车辆行驶位置点i与车辆行驶位置点j之间释放增加信息素浓度;ΔCij为所有蚂蚁在i与j之间释放增加的信息素浓度;其信息素增加公式如下

τi+1=στij(t)+Δτij(t,t+1)

(9)

(10)

(11)

比较NC和Nmax的大小,计算结果并输出。Lk表示蚂蚁走过的路线总长度;Nmax表示最大路线迭代次数;Q表示释放的信息素总量。

2.2 仿真计算结果

由于该冷链物流车的行驶路径较多,本论文以五条路径线作为模型,但是车辆调度过程中调度中心空车行驶到物流中心的路径与物流中心满载货物行驶到调度中心的路径不同,此外空车与满载过程中的路径正好形成一个完整的闭合路线。如图1所示。

对冷链物流车最近距离进行蚁群算法的仿真,图1中路径3即为最优路径。表1是冷链物流车行驶的52个坐标位置,即为本次行驶最优路径距离,用MATLAB2014平台对路径3进行仿真。路径坐标如表1所示。

图1 调度车辆行驶路径图Figure 1 Travel route diagram of dispatching vehicle

表1 路径坐标表格Table 1 Path coordinate

由于两直线距离最短,利用如下公式进行计算:(此距离是理论距离计算公式的1.2倍)。

(12)

运行参数设置为:蚁群中蚂蚁数量m为52(蚂蚁数量取各个坐标位置数量);a是信息素浓度因子为1;期望启发因子b为5;信息素挥发系数ρ为0.5;最大迭代次数Ncmax=100。ACA蚁群算法其仿真运行结果如图2所示。

由图2可知:由于车辆在调度过程中调度车辆在空车时与满载时行驶路径不同且能够形成一个完整的折线包围圈,本文设置第45点坐标为车辆调度点,第52点坐标为物流中心点,且车辆来回是两条不同的路线。

图2 ACA最优化车辆调度路径轨迹图Figure 2 Scheduling path trajectory of ACA optimal vehicle

空车路径一:52-11-51-33-43-10-9-8-41-19-45(空车行驶3.1 km)。满载路径二:余下的路径坐标点(满载行驶4.7 km)。蚁群经过10次运算结果:空车与满载最优路径为7 753.117 6 m;假设所涉及到的运输成本为:每辆车司机成本300元,冷链物流公司需要每个调度点调度车辆为10辆,每公里花费运输成本为5元;车辆运输过程中单位时间汽油损耗λ1为6元/h;当给客户卸载货物时车门开启单位时间能源损耗λ2为12元/h,车辆空车速度与满载速度为40 km/h;车辆在卸装货物时消费时间为2 h,ρ1为0.5,ρ2为0.3,k1单位损失为5元,k2单位损失为4元。成本计算:运输车辆固定成本即司机成本C11=3 000元;空车驾驶成本C12=3.875元;载物成本C13=5.875元;冷却成本C2=247.05元;损失费用C3=12.95元;总成本C=3 269.75元。

3 蚁群算法改进

3.1 引入搜索方向机制

在ACA蚁群算法的启发信息(13)中,dij表示可选路径的长度,即蚂蚁dij距离越短,则该蚂蚁行驶的边际路线被选取的可能性较大。在求解冷链物流路径最优化问题时,假如启发信息仍然用式(13)表示,则没有考虑到由车辆调度源点到物流中心具体搜索方向性的问题,导致的结果是没能够完成最优搜索方向性问题与整体路径最优化问题。由此对启发信息因子修改如下:

ηij=1/dij

(13)

3.2 引入搜索热区机制

引入搜索公式:

(14)

其中Φij(t)表示在t时刻根据边(i,j)是否在搜索热区中而取不同的值。

(15)

公式(14)与(15)代表了搜索概率与搜索边缘的问题。在蚂蚁进行热搜索时有热搜索区域与非热搜索区域,导致的的结果是蚂蚁爬行距离不相同。

3.3 实验结果

运行参数设置为:蚁群中蚂蚁数m为52(蚂蚁数量取城市数量);a是信息素浓度因子为1;期望启发因子b为5;信息素挥发系数ρ为0.5;最大迭代次数Ncmax=100,Q=1 000,信息素初始值为τij=20。通过算法改进对路径3的距离、行驶时间重新优化。

表2 两种算法路径与时间对比图Table 2 Comparison of paths and spending time from the two algorithms

传统蚁群算法调度车辆它的最优行驶距离为7.75 km,此路径虽然选取了最优路径,但是行驶过程中传统算法进行优化的路径偏长,其空车行驶距离与满载行驶距离都较长,所以冷链物流所花的成本较高。而ACA蚁群算法改进后此冷链物流车的行驶距离明显缩短,则所花费用较少。

3.2 实际运算结果

实际冷链物流车行驶路径是从杭州江干区市中心到马鞍山市,行驶过程中有多条路径,选取最优化路径进行计算。实际两城市距离为300 km,公路国道行驶距离:345 km,高速行驶距离:314 km,车辆行驶在公路时间大约为3.5 h,行驶在高速路上的时间大约为4 h,实际改进算法的行驶时间为3.4 h。通过实际计算结果进行对比,对冷链物流运输成本进行分析。由表3所示可以看出该冷链物流实际距离与车辆优化后行驶的距离基本上差不多,虽然有点差距但足以说明该冷链物流调度算法完全符合车辆调度,符合该冷链物流监控系统。

表3 实际路程运算结果Table 3 Calculation results of actual distance

注:实际距离计算结果。

4 结 语

本文通过调度算法与冷链物流进行结合设计路径最优化,使得此冷链物流的监控方案与运输方案得到最优化设计,减少了整个运输成本与运输时间。利用蚁群算法仿真模拟来实现,目的是降低冷链物流运输过程中运输成本。同时本文主要介绍了设计中所有的车辆调度算法,建立了基于蚁群算法的车辆调度模型并对算法进行了仿真实验。实验结果显示通过该调度算法能够设计出距离优、成本低的路径进行车辆调度。