带目标权重的物流路径优化研究—基于模拟退火蚁群算法

陈 志， 江治杰

(四川轻化工大学a.管理学院；b.数学与统计学院， 四川 自贡 643000)

引 言

随着我国经济体量增大，贸易额持续增长，货物量增多，物流行业的竞争也愈演愈烈。发改委数据显示，2018年我国社会物流总费用高达13.3万亿元，同比增长9.8%，增速比2017年同期提高了0.7个百分点，其中运输费用共计6.9万亿元，占社会物流总费用的比重为51.88%，占GDP的比重为7.7%[1]。以上数据显示，运输费用在社会物流总费用里的占比最高，也是物流配送中最重要的一个环节。因此，解决运输费用问题最关键的是寻找更好的物流路径，通过对路径进行规划，使得物流企业能有效降低物流配送成本，进一步提高配送效率。

目前，已有许多学者对物流路径问题进行研究，孙沁等人[2]建立了以配送费用为目标函数的数学模型，对基本蚁群算法的随机转移规则以及局部搜索能力进行改进，通过仿真表明改进蚁群算法的性能更好。王垚等人[3]考虑了时间和成本因素，建立了生鲜食品的选址和路径优化问题模型，通过改进的细菌觅食算法进行仿真，结果表明该算法在处理多目标物流路径优化问题上有一定优势。朱杰等人[4]考虑了配送车辆的固定成本以及运输成本，在时间窗和配送车辆载重的条件限制下，建立了带时间窗的配送车辆物流路径的数学模型，通过对基本蚁群算法进行改进，使得改进的算法能很好的解决所建立的模型。蒋丽等人[5]以时间惩罚成本和距离成本综合最小为目标函数，建立带时间约束的外卖配送路径数学模型，实验结果表明改进算法有效。张立毅等人[6]以碳排放成本为目标函数，建立了低碳物流路径的数学模型，通过引入混沌系统以及模拟退火思想对基本蚁群算法进行改进，用以解决所建立的模型，结果表明算法的改进合理有效。周显春等人[7]主要考虑了限行或施工情况下道路的实时情况，构建多约束条件下的质量评价数学模型，利用改进基本蚁群算法的启发函数和信息素来解决所建立的模型，实验取得比较满意的结果。袁亚博等人[8]通过对基本蚁群算法的初始信息素、局部信息素以及全局信息素进行改进，进而求解最短路径问题，仿真结果表明改进的算法有一定的速度优势。郭宝恩[9]将Spark并行计算融入到蚁群算法，用以解决大规模TSP问题，结果表明该改进方式有较大的速度优势。裴小兵等人[10]将配送车辆载重量以及配送车辆数融入到模型中，建立多目标配送路径优化模型，在模拟退火算法中引入记忆函数并通过GIS手段对其进行改进，实验结果表明此改进方法提高了求解精度。Kalayci等人[11]通过将变邻域搜索与基本蚁群算法相结合来解决配送车辆的车容量限制的路径优化问题，仿真表明改进的蚁群算法有效。

经研究发现，以往的研究主要考虑配送时间最少或配送距离最短或配送成本最小等单方面最优。但考虑到物流企业对物流配送时间、距离以及运输成本的要求有所不同，本文通过设置目标权重将配送时间、配送距离和配送成本三者统一起来建立物流路径数学模型，进而解决不同需求的配送问题。若企业更加看重配送时间，则可将时间权重适当放大；若企业不考虑配送时间对本次配送的影响，则可将时间权重置0处理；同样可对距离权重、成本权重做类似处理。此外，本文模型还有如下考虑：

(1)物流配送距离采用的是两地之间的实际距离(由高德地图APP获得)。目前大多数学者考虑的是两地之间的直线距离，这与实际距离偏差较大，因而考虑实际距离作为本文研究的距离。

(2)物流配送时间采用的是配送车辆在两地之间的高速路上行驶时间和非高速路行驶时间，这使得配送时间更接近实际时间。

(3)配送成本采用的是动用配送车辆的固定成本、配送过程中燃料的消耗成本以及高速路上的通行成本。

20世纪90年代，意大利学者Dorigo等人通过模拟蚂蚁寻觅食物的过程而提出的一种智能算法，即蚁群算法(Ant Colony Algorithm，ACA)[12-13]。蚁群算法具有较强的正反馈性、鲁棒性以及并行计算的特性，广泛应用于求解路径优化问题。由于基本蚁群算法易陷入局部最优以及收敛速度过慢的不足，因此本文将基本蚁群算法的转移规则和信息素的更新作相应改进，在此基础上融入模拟退火算法，建立模拟退火蚁群算法来求解本文所建立的数学模型。通过实例仿真对比可知：模拟退火蚁群算法能更快搜寻到比基本蚁群算法更优的解，进而证明模拟退火蚁群算法的可行性以及模型的合理性。

1 物流路径数学模型

1.1 问题的描述

物流配送路径优化问题的描述为：已知位置的某一物流配送中心有统一车型的配送车辆，其车辆数为m辆，配送车辆的载重为W，共同向n个已知位置和需求量的客户点提供配送服务，在满足车辆载重的情况下完成货物的配送。其目的是使得目标函数值最小，即达到最优。本文综合考虑了物流配送时间、距离以及运输成本，其中，运输成本具体细化为动用配送车辆的固定成本、燃油消耗成本和道路行驶费用三个方面。建立以综合成本最优为目标的物流路径优化综合模型。为了使得本文更贴近现实，本文考虑的距离均为高德地图APP经过定位所显示的高速距离与非高速距离，这比直接对两点的坐标用距离公式求出的距离更接近于实际情况。

1.2 问题的假设

考虑到模型以外的因素对模型的影响，于是简化数学模型，对数学模型作以下假设：

(1)物流配送中心的位置以及客户节点的位置均已知；

(2)所有节点的总需求量不超过物流配送中心的总库存量；

(3)每条路线上的节点需求量总和不超过在这条路线上行驶的物流配送车辆的载重量；

(4)每个节点最多可由一辆物流配送车辆为其服务；

(5)在配送过程中，物流配送车辆到达某个客户点则必须为其服务，待服务完成后，立即离开此节点，前往下一个节点或者配送中心；

(6)物流配送车辆都是从配送中心出发，最终必须回到出发点；

(7)物流配送车辆在同等程度的道路上均为匀速行驶。

1.3 综合成本分析

本文综合考虑了配送过程中配送时间、配送距离以及运输成本，其中运输成本是指动用车辆的固定成本、运输燃油成本和道路行驶通行费用(高速收费)，建立一个综合成本最优的数学模型，以便配送公司可以根据企业的不同要求进行相应的调整，进而实现高效配送。

1.3.1 配送时间分析

在信息化时代的今天，客户的时间观念越来越强，迫使物流公司必须加强时间意识以满足客户需求，即配送时间T为：

(1)

(2)

1.3.2 配送距离分析

在物流配送过程中，随着基础设施的不断完善，通往两地的线路也趋于多样化，故物流公司会重新调整配送线路来尽可能的减少配送距离，进而降低物流公司的物流成本，即配送距离L为：

(3)

其中，dij表示节点i与节点j之间的实际距离，即高速距离与非高速距离之和。

1.3.3 固定成本分析

物流配送的固定成本为在某地区范围内动用某车辆的费用，与行驶里程无关的常量，即固定成本C1为：

(4)

其中，fk表示第k辆配送车运行的固定成本，m表示配送中心的车量数，xi0k=1表示车辆k已使用，xi0k=0表示车辆k未被使用。

1.3.4 车辆运输成本分析

车辆的运输成本包括车辆通行费用(高速路段费用)以及车辆在行驶过程中所产生的油耗费用，即运输成本C2为：

(5)

其中，f表示高速路段单位距离收费标准，g表示车辆平均每公里消耗的燃料费用。

1.4 数学模型

基于上述描述，建立带目标权重的物流路径优化问题的综合模型：

目标函数：

minZ=p1T+p2L+p3C1+p4C2

(6)

约束条件：

(7)

(8)

(9)

(10)

(11)

(12)

(13)

其中：(6)式表示目标函数综合成本最小，p1，p2，p3，p4分别表示时间、距离、固定成本和配送成本的目标权重且均为大于等于0的数，各企业可根据不同需求进行调整；(7)式表示车辆必须从配送中心出发，最终又返回配送中心；(8)式表示完成此次配送任务需要的车辆总数；(9)式表示此次配送任务中，此路径上的节点总需求量不超过车辆的最大装载量，qi指节点i的需求量；(10)式表示车辆k到达节点j则必为节点j提供服务；(11)式表示车辆k为节点i提供服务，然后必须离开节点i；(12)式与(13)式表示一个节点只能被访问一次。

2 模拟退火蚁群算法

2.1 基本蚁群算法的改进

2.1.1 转移规则的改进

由于基本蚁群算法在搜索过程中的随机性容易导致局部最优，于是本文将随机搜索和确定搜索相结合，扩大搜索范围，进而使蚁群算法尽可能的避免局部最优[7]，即：

(14)

(15)

表示蚂蚁k在t时刻节点i与节点j的转移概率；τij指节点i到节点j的信息素浓度，α指信息素的程度因子；ηij指启发函数，即蚂蚁从节点i到节点j的期望程度，β指启发函数的程度因子；ωij指节约值，ωij=di0+d0j-dij，ε指节约值的程度因子；allowk表示车辆在满足载重情况下可访问的节点集合。若q

2.1.2 信息素的更新改进

本文对蚁群算法信息素的更新方式提出了新的理解，即蚂蚁在搜寻过程中，就路径上原有的信息素而言，其浓度会随着时间的推移而逐渐降低；就蚂蚁经过此路径携带的信息素而言，通过归一化去量纲的方式将携带的信息素Q分布到其途径的路径上，其更新公式如下：

τij(t+1)=(1-ρ)τij(t)+Δτij(t)

(16)

(17)

(18)

其中，Zmax表示蚂蚁在搜寻过程中综合成本的最大值，Zmin表示蚂蚁在搜寻过程中综合成本的最小值，Zk表示蚂蚁k在此次搜寻中的综合成本。

2.2 引入模拟退火算法思想

模拟退火算法是模拟固体退火过程的一种随机搜寻算法。由于算法具有概率突跳的特性，这恰好能解决蚁群算法在搜索过程中陷入局部最优的不足，使得算法概率性的跳出局部最优，逐渐向全局最优方向转化，进而缩短算法收敛用时。因此，本文将模拟退火思想与改进的蚁群算法相结合。

具体结合方式如下：当蚁群中的每一只蚂蚁都完成了一次搜索之后，必然存在一个属于此次搜索的最优解，然后在此最优解的基础上随机生成除当前最优解之外的解集，最后再由模拟退火算法中的概率来判断算法是否接受新解替代此前的最优解[10]。

由于模拟退火算法中的退火过程涉及到温度变量，故引入模拟退火算法思想时需要设定一个温度变量T，其范围为[Tmin,Tmax]且随迭代次数的变化而变化。算法的初始温度设置为T(0)=Tmax。当蚁群中每只蚂蚁都完成了一次搜寻后，必有一个属于此次搜寻结果的最优解，不妨设为蚂蚁i在此次搜寻过程中搜寻到的最优解，记为Zi。蚂蚁i在此次搜寻过程中走过的路径全部放入禁忌表中，这就表示得到了模拟退火算法中的初始解集[14-15]。在此初始解的基础上随机生成除初始解之外的新的可行解，计算新的可行解对应的目标函数值为Zj。由初始解到新的可行解的目标函数值的变化量ΔZ为：

ΔZ=Zj-Zi

(19)

若ΔZ<0，那么算法接受新解作为当前最优解，否则就要考虑退火概率：

(20)

此时算法生成一个随机数rand，介于0与1之间。若p>rand，那么算法接受新解Zj作为当前最优解；否则，拒绝新解Zj，保持原来的解Zi。

在一次搜索完成及信息素的更新完成后，对算法进行降温操作，其降温函数为：

T(t+1)=(1-ζ)T(t)

(21)

其中，1-ζ为降温系数且为介于0与1之间的常数。当温度T较高时，算法将以较高的概率来接受相对较差的解加入可行解集，使得更多的路径上分布有更多的信息素，避免遗漏最优解，即避免陷入局部最优。随着温度T的降低，其接受概率也随之减少，同样对相对较差的解接收概率也随之变小，从而使得信息素集中分布在路径上，故算法能很快的收敛。为了提高算法的收敛速度，缩短算法的搜索时间，一般情况下，算法常常采用相对较小的降温系数ζ。即使如此，算法也会增加陷入局部最优解的风险，为此，在算法中引进回火机制，当T

3 带目标权重的物流路径优化模型求解步骤

利用模拟退火蚁群算法求解带目标权重的物流路径问题的具体步骤如下：

步骤1录入数据。录入节点的规模n及各节点的经纬度坐标(x,y)，构造无向图G；录入高德地图APP测算的两地之间的高速路段距离和非高速路段距离；录入各节点的需求量q及车辆最大装载量W。

步骤2参数初始化。设蚂蚁数为m，令算法的循环次数Nc=0，再设置算法的最大循环次数Ncmax，各路径信息素的初始化，基本蚁群算法中各参数以及模拟退火算法思想中的参数设置。

步骤3建立解空间，将所有蚂蚁全部放置在配送中心，建立禁忌表Tabuk，即蚂蚁目前已经访问的节点和配送中心构成的集合；建立allowk表，即没有访问的但可以进行访问的节点的集合。

步骤4在满足车辆载重的限制下，每只蚂蚁按照(14)式与(15)式确定性以及随机性概率的搜索下一个将访问的节点，并将其放入Tabuk中，表示蚂蚁在这次搜寻过程中途经了该节点。更新车辆的载重信息，判断车辆是否出现超载，若超载，则车辆返回配送中心，并将配送中心放入Tabuk中，如此反复执行此步骤，直到所有蚂蚁访问完全部节点，即将所有节点都放入Tabuk中，并返回物流配送中心。

步骤5所有蚂蚁都完成了一次搜寻任务，即得到了模拟退火算法中的初始解集。计算每只蚂蚁所经过的路径所产生的综合成本Zk，再根据退火机制生成一组新的可行解，然后由(19)式表示退火概率来进行判定是否接受刚刚所生成的新可行解为当前解，并判定车辆是否超载；若超载，则重新生成有别于超载时的可行解；若未超载，则算法接受该可行解作为当前最优解。

步骤6得到当前的最优解后，根据(16)式～(18)式进行信息素的更新操作，清空当前的Tabuk，循环次数自加1。

步骤7当循环次数达到设定的最大循环次数时，则算法终止；否则跳转至步骤4继续进行迭代，循环次数Nc=Nc+1，同时清空Tabuk；当连续多次迭代后均无更优的解出现时，算法终止，输出配送路径以及综合成本最优值。

4 仿真实验

经多次重复仿真实验，基本蚁群算法的参数设置为：α=1.5，β=2，m=40辆，ρ=0.7,Q=100,Ncmax=200；模拟退火蚁群算法的参数设置为：α=1，β=3.5，ε=2，ρ=0.3，m=40辆，Tmax=100 000,Tmin=500,ξ=0.4，Q=100，Ncmax=200。

本文模型参数设置为：配送车辆载重量为20 t，使用一辆配送车辆的费用为fk=500元，配送车辆平均每公里消耗的燃油费用g=1.7元，配送车辆在高速路段上平均每公里的通行费用k1=1.75元，配送车辆在高速路段上的行驶速度v1=80 km/h，在非高速路段上的行驶速度v2=30 km/h，四个目标权重p1，p2，p3，p4分别为1，1，1，1。企业可根据自身的需要对目标权重进行赋值使得满足其配送需求。

本文以西南地区各市某物流为研究对象，共计40个市，其经纬度坐标(由高德地图获取)及需求量见表1。

表1 西南地区40个市的经纬度坐标及需求量

由表1可知，城市节点1的需求量为0，即为配送中心，向其余39个城市进行物流配送。其余39个城市节点的需求量总和为100.43 t，,需要6辆载重量为20 t的车辆为其进行物资配送。

设计适合本文模型的蚁群算法，再由MATLAB 2014a软件对蚁群算法程序进行多次重复实验选取最优的解，其迭代寻优曲线如图1所示，所有车辆的配送线路如图2所示，由于城市节点比较密集，故没有对城市节点进行标号处理。

图1 蚁群算法迭代曲线

由图1及程序运算结果可知，蚁群算法在第162次迭代时搜寻到较好的综合成本。

图2 蚁群算法配送线路图

由图2及程序运算结果可知：蚁群算法在解决本文模型所需综合成本为89 018.547 9元，且6辆车的具体配送情况见表2。

表2 蚁群算法配送车辆配送情况

由MATLAB 2014a软件对本文的模拟退火蚁群算法程序进行多次重复实验选取最优的综合成本，其迭代寻优曲线如图3所示，所有车辆的配送线路如图4所示。

图3 模拟退火蚁群算法迭代曲线

由图3及程序运算结果可知，模拟退火蚁群算法在第13次迭代时搜寻到较好的综合成本。

图4 模拟退火蚁群算法配送线路图

由图4及程序运算结果可知：模拟退火蚁群算法在解决本文模型所需综合成本为62 502.152 1元，且6辆车的具体配送情况见表3。

表3 模拟退火蚁群算法配送车辆配送情况

实验结果比较分析：由图1与图3对比可知，模拟退火蚁群算法的收敛速度明显比基本蚁群算法快，说明模拟退火蚁群算法能扩大其搜索范围，很好的跳出了局部最优；由图2与图4对比可知，模拟退火蚁群算法安排的配送线路图比基本蚁群算法更有序，且综合成本更低，低了26 516.395 8元；由表2与表3可知，两种算法都将100.43 t物资配送完毕，模拟退火蚁群算法得出的配送时间、配送距离以及运输成本都分别优于基本蚁群算法。由此可见，模拟退火蚁群算法的综合成本和收敛速度都比基本蚁群算法低，这证明了本文模型的合理性以及模拟退火蚁群算法解决物流配送问题的有效性。

5 结束语

本文以西南地区各市某物流为研究对象，通过目标权重将配送时间、配送距离以及配送运输成本构建为一个综合成本最优的数学模型，企业可根据自身的需要对目标权重进行重新赋值即可满足其配送需求。由于考虑到时间和距离，因此本文将实际距离分为高速距离与非高速距离，车辆在不同程度的道路上行驶速度不同，进而使得配送时间更准确。将基本蚁群算法的转移规则和信息素更新作相应修改，再融入模拟退火思想，进而对文中所建立的模型进行求解。实验结果表明：模拟退火蚁群算法能搜寻到比基本蚁群算法更优的综合成本，且收敛速度更快，表明本文模型的合理性以及模拟退火蚁群算法的有效性。由于影响物流配送的因素很多，本文所考虑的因素有限，因此，在今后的研究中将考虑其它他更多的影响因素，使得更接近于现实生活。