冷链物流车辆路径最优化模型

曾 胜，戴贤君，倪天伟，胡徐胜，滕官宏伟

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

基于我国居民对生活的质量提高，人们越来越注重绿色健康的生活节奏方式，对于冷链物流的需求量逐渐增大。传统的冷链物流车辆行驶时是无障碍物的阻挡，使得车辆行驶时变得简单，但实际车辆行驶过程中会出现障碍物的阻挡，此时车辆的行驶的路径变得复杂多变。

针对车辆在行驶过程中遇到障碍物，胡文楠[1]为研究搬运机器人的视觉识别系统，提出一种基于内容图像检索的方法识别障碍物。李彦玥[2]提出一种基于RGBD摄像头的障碍物检测方法，通过摄像头实时采集图像传输到数据处理中心，用改良的帧差法、最小矩形法匹配法和图像处理等方法来确定障碍物轮廓。王达阳[3]为了提高AGV检测障碍物的实时性，提出了一种基于连续差分图像阈值比较法的障碍物检测方法，对AGV行驶的路径划定安全区域，然后对连续的图像进行差分计算。丁斗建[4]针对稀疏型同时定位与地图构建(SLAM)算法环境信息丢失导致无法检测障碍物问题,提出一种基于视觉的机器人自主定位与障碍物检测方法。

针对冷链物流运输过程中对其路径进行最优化设计，姚佼[5]阐述了车辆行驶过程中遇到紧急情况时利用TOPSIS算法构建了应急车辆的多目标最优路径选择模型，最后采用改进的蚁群系统算法对该模型进行求解。薛明[6]考虑在恶劣环境条件下，车辆行驶路径所需时间、交叉路口密度、通行能力等因素综合变化，根据模拟退火算法模拟差异化的天气影响因素，利用遗传算法求取模型最优解。王征[7]针对行驶时间延迟下配送车辆调度的干扰管理问题，以顾客时间窗偏离程度最小化和配送成本最小化为目标，建立了问题的数学模型及其求解算法。王君[8]针对物流配送中带时间窗的车辆路径问题，以最小化车辆使用数和行驶距离为目标，建立了多目标数学模型，提出了一种求解该问题的多目标文化基因算法。万国海[9]为解决物流配送路径距离过长导致配送效率低的问题，提出改进蚁群优化算法的电子商务物流配送路径优化方法，改进了蚁群优化算法，提高物流配送效率，缩短配送距离，降低电子商务物流配送成本。张晓莉[10]为了克服传统蚁群算法易陷入局部最优且收敛速度慢的影响，采用栅格地图建立机器人实验环境仿真模型。马军[11]针对蚁群算法对路径进行最优化设计收敛速度较为缓慢，提出了一种融合蚁群A*算法对路径最优化进行求解。Wen[12]采用混合蚁群算法(HACO)寻找最优路径，将蚁群算法与线性最小二乘法进行了比较，结果表明线性最小二乘法可以用来寻找最短路径。Zeng[13]针对传统蚁群算法寻找最优路径的步长单一、容易陷入局部最优、收敛性差等缺点，提出了一种改进的无限步长蚁群算法来寻找最优路径。Ben[14]提出了一种改进的蚁群算法，采用路径优化策略对城市进行位置交换，寻找到更好的TSP求解方案。于彭涛[15]通过对基本蚁群算法启发函数的优化提出改进蚁群算法，并且以现代物流技术作为理论支撑，利用改进的蚁群算法解决现代物流运输路径规划方面的车辆调度问题。

基于冷链物流运输研究状况，本文考虑在遇到道路特殊状况下，通过图像识别出障碍物轮廓，由此改变车辆行驶路径，目的减少冷链运输成本并节约冷链运输时间。

1 模型建立

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

对于配送冷链物流车辆行驶距离必须能满足物流配送条件；车辆调度数量应满足具体使用数量；配送食品车辆须从各个调度中心出发到达使用车辆的地点；配送冷链物流车辆必须在接到配送任务时不能随意的接受其他的任务；每次调度必须满足对食品的数量需求；配送物流中心必须预先知道客户具体位置，客户也要知道冷链物流中心的具体配送位置；所有冷链食品调度车辆的硬件设施、速度与型号相同；在配送食品时保证每个车辆的油箱是加满状态，以便于调度时的费用计算；调度点车辆把冷链食品派送到客户位置所花费的每公里费用一样。

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

首先，对冷链食品调度车辆模型的目标函数进行设定：n表示冷链车辆调度点具体车辆数；B表示冷链公司调度车辆所花费的固定费用；Bij表示从地点i到地点j的车辆固定调度费用；sn表示车辆在调度过程中所产生的一个固定成本费用；n辆车中每辆车单独所花费的固定成本为r0，Q表示调度车辆所花费的总费用；dij表示调度点第i辆车与第j个客户之间的距离；λ1表示车辆在调度过程中所产生的油耗；λ2表示在调度车辆过程中单位时间产生的额外费用；t表示调度车辆所花费的具体时间；v表示在车辆行驶过程中的平均速度。p1表示运输过程中冷链食品所产生的额外费用比例，k1为运输过程中单位时间内产生的费用；p2客户在单位时间内所产生的冷链食品损失比例；k2表示在冷链食品卸货时产生的单位比例费用，rn表示调度中心有n辆车的调度固定成本且均为：

rn=(1,2,3,4,…，n)

(1)

运输过程中车辆所花费固定成本Q1(司机的费用等)：

(2)

运输过程成本分别为车辆行驶成本Q2(主要是车辆行驶所花费的油费)，冷链产品运输过程中的损耗Q3(车辆行驶过程中的冷冻食品的损耗)，冷链食品卸货过程中产生的损耗Q4(冷链食品在卸货过程中会产生损耗)。

(3)

(4)

(5)

调度过程中产生损耗的运算公式即为Q5(此损耗主要包括调度车辆人为搬运冷链食品损耗和车辆的机械损耗)：

(6)

即以下是整个冷链运输公司调度的总费用：

Q=Q1+Q2+Q3+Q4+Q5

(7)

1.3 蚁群算法模型建立

(8)

对于蚂蚁爬行过程中必须设置不可重复的爬行概率，此公式如下：

(9)

设定P表示信息素挥发程度，即公式为：

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

(10)

ΔCij=∑ΔCijk

(11)

其中，Cijk为第k只蚂蚁在爬行位置点i与爬行位置点k之间释放的信息素浓度；ΔCij为所以蚂蚁在i与j之间释放的增加的信息素浓度；其信息素增加公式如下:

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

(12)

(13)

(14)

比较Nc和Nmac的具体大小，输出计算结果。设置该蚂蚁的总体数量为100，但其信息素浓度也会随路径改变而发生变化。Ncmax=2 000表示最大路线迭代次数。

2 实验结果

2.1 传统算法的仿真模拟结果

正常冷链物流车辆行驶路径图是没有遇到障碍物，此时车辆行驶的路径图也是最优路径，如下图1为车辆没有遇到障碍物的行驶路径。

(a)坐标图 (b)路径图

(c)收敛图图1 基于蚁群算法的路径仿真图

车辆正常情况下基地到目的地没有障碍物，其车辆行驶坐标与路径如图1(a)、(b)所示。

2.2 基于Robert算法对障碍物的边缘进行检测

基于蚁群算法的路径研究，对于车辆的路径进行最优化设计，但如果遇到障碍物时，此时车辆的行驶路径会发生改变，其下为Robert的算法边缘检测算法研究，其公式为：

(15)

为了简化运算，一般梯度算子可以近似为：

G(x,y)=|Δxf(x,y)|+|Δyf(x,y)|

(16)

由此，可以得出图像离散化的对角线Roberts算子：

(17)

该实验首先通过冷链物流车辆的摄像头识别出障碍物，此时车辆应该避开障碍物寻找出其它路径。如下图2所示为识别障碍物物体。

(a)路障图 (b)障碍物识别图图2 障碍物识别图

后台通过采集到有障碍物图片，并通过图像处理分析出道路障碍物，通过算子边缘检测，车辆选择其他的行驶路径，车辆行驶有两条路径，从A点到B点位置时，正常行驶过程中有障碍物的出现，此时应改变传统的路线，走下面的路径，避开障碍物。图3为车辆遇到障碍物的路径模拟图。

图3 车辆行驶路径障碍图

2.3 基于蚁群算法的模拟结果

传统的蚁群算法只是针对无障碍物的情况，路径为最优化路径。但当有障碍物时，此时车辆的行驶路径会发生改变。两种路径的行驶坐标如表1所示：

表1 坐标路径图

由表1可以看出，假设车辆行驶过程中只遇到一处障碍物(障碍物坐标如上表所示)，此时的车辆行驶路线会发生相应的改变。下图4为车辆遇到障碍物时改变的行驶路径图。

(a)改进后坐标图 (b)改进后路径图

在同样的条件下，不改变车辆的外在因素，此车辆行驶路径发生改变。通过以上几种实验分析，即车辆在无障碍时其行驶路径与有障碍时，其行驶路径完全不相同，其运输成本也不同。

2.4 无障碍物运输与有障碍物的成本计算

传统的冷链物流运输过程中遇到路径的障碍与无路径障碍两种情况，所产生的成本也不相同。以马鞍山到南京的运输过程为例，比较两种路径所产生的费用对比，如下表2所示。

表2 两种路径的运算对比表 单位：元

可以看出正常车辆调度费用较低，但当遇到路径阻碍时，改变路径其成本比在等待时的所花费的成本低，所以应选择其它的路线进行运输冷链物流产品，既可以节约成本，也可以大大缩短运输时间，防止因车辆堵塞导致的食品腐烂。