吴耕锐 郭三学 吴虎胜 薄 鸟

1(武警工程大学装备管理与保障学院 陕西 西安 710086)2(武警警官学院基础部 四川 成都 610213)3(武警警官学院信息通信系 四川 成都 610213)

0 引 言

随着科技发展，城市交通向集成化、智能化、网络化不断发展，车辆、设备、网络形成了一个共同体，为研究车辆运输路径提供海量动态信息已然成为可能，动态路径优化问题成为了研究热点。决策者应当将动态路径问题看成一个系统问题，包括数据信息采集、数据传输和路径优化计算等。

目前动态路径优化的研究较多。如刘波等[1]结合冷链物流特点，建立了以配送总成本最小为优化目标的带时间窗冷链配送动态车辆路径优化模型，提出了一种自适应改进人工鱼群算法，利于节约企业资源和提高客户满意度。李治等[2]提出了小波神经网络的速度预测模型，针对动态最优路径选择问题，确定了基于短时交通预测的动态路径求解算法。赵宏伟等[3]针对实时环境下交通特性，提出了实时环境下基于混合的动态路径优化算法，将剪枝算法和自适应A算法结合，并引入粒子群优化，更好适应了实时环境求解。

蚁群算法求解路径优化的研究也较多。如陈希琼等[4]建立了同时考虑车辆容量和距离约束的双目标模型，用蚁群算法求解多个目标，实现了运输成本和路径间最大长度差最小化的目的。徐少甫等[5]综合考虑运输风险和运输时间目标，通过ACO算法寻优，实现了对危险化学品的运输路径优化求解。孙沁等[6]采用2-opt算法扩大搜索范围，克服了蚁群算法缺陷，将其应用于电子商务配送路径优化中，达到了配送成本最低目标。开吉等[7]为解决配送效率低的问题，以淮海经济区为实例，建立了蚁群算法模型，降低了物流配送成本，提高了服务质量。

也有将智能优化算法用于动态路径优化的相关研究。如赵峰等[8]提出了一种新型自适应搜索半径的蚁群路径优化算法，能根据障碍分布自动选择搜索半径，完成路径动态规划，其环境适应能力和路径优化性能优。文献[9]应用蚁群算法来优化车辆路径，将蚁群算法与基于聚类算法相结合，进一步提高优化结果。文献[10]通过多处修改遗传算法后，将算法用于求解动态路径问题，求解优于之前很多同类求解动态路径优化算法。文献[11]设计一种基于蚁群优化和动态平台点播的优化算法，该算法在路径构建时能有效反应车辆行驶环境的变化。文献[12]求解与车辆隐私位置相关的动态路径问题，对车辆增加情况进行集约计算，可以有效避免任何类型的交通拥堵。

以上研究动态路径优化的过程中尚没有考虑实时动态路径道路因素对路径优化的影响问题，使得路径优化结果的客观性、针对性没有与实际路径情况紧密结合，优化得到路径的准确性、实用性仍需改进。且在动态路径优化后，对于车辆旅行时间窗硬要求方面，只是给出优化路径，没能给出最短抵达目的地时间路径，一方面影响了服务质量的时效，另一方面也增大了燃料油耗，没能很好地解决运输时间硬要求和资源节约问题。

本文用多目标蚁群算法求解动态车辆路径问题。在考虑车辆行程约束条件下，以动态路径优化为对象，设计了改进的多目标蚁群算法，在蚂蚁寻径过程中添加了贪婪搜索规则和禁忌表，加快了搜索速度，进行多目标局部搜索，改进蚂蚁生成的解集，防止陷入局部最优或遗漏一些帕累托解。与传统蚁群算法和多目标粒子群算法求解相同动态路径问题的解进行比较，与三种最新优化算法(改进灰狼优化算法、改进细菌菌落优化算法和鼠疫传染病优化算法)在不同条件下求解动态路径问题的旅行时间上进行对比，更全面分析改进多目标蚁群算法的求解性能，更细致掌握改进多目标蚁群算法的优劣。将动态路径道路因素适应度函数引入目标函数当中，较好地解决了动态路径优化求解中优化路径与实际道路情况结合不紧密的问题，使优化路径实用性增强，同时解决了优化路径旅行时间缩短的进一步要求，一方面提高了运输服务的时间质量，另一方面也节约了油料资源，较好地实现了运输时间硬要求和资源节约目标。

1 影响动态路径的道路因素

车辆在行驶中能采集不同道路信息，其中不同道路因素对动态路径优化问题会产生不同影响，从道路通行能力影响因素角度考虑，选择了下面三种道路影响因素。

道路质量A：道路质量取决于不同因素，如坑洞、车道数等，将此作为一个重要矩阵，用于计算路径优化问题。

道路长度B：多重长度在两个道路连接点间是同时存在的。选择道路时不仅要考虑道路质量最高，还要考虑路径最短。

道路拥堵C：有些道路比其他道路要拥堵。因为最优路径的形式可能多样化，有时长但不拥堵的路径会比短而拥堵的路径更好，因此道路拥堵情况也需要重点考虑。

这里定义一个数组,用来代表网络中的道路长短、拥堵情况和质量因素。用适应度函数计算在特殊出发点和终点间的最优路径，适应度函数表示如下：

(1)

式中：n是度量数，Cixy定义为从节点x到节点y的道路要素的第i个矩阵值。当函数D值越小，则道路通行能力越大，路径越优；相反，函数D值越大，则道路通行能力越弱，路径越差。

2 改进的多目标蚁群优化算法

2.1 改进算法步骤

构造一种具有贪婪转移准则的多目标蚁群算法MT-ACO，对产生的解进行多目标迭代搜索，进一步优化替换帕累托解集和目标函数值。具体步骤如算法1所示。

算法1MT-ACO

初始化信息素矩阵T；

令全局帕累托解集Q为空集φ；

令目标函数值矩阵F1=[-∞,+∞];

当迭代次数IT≠max_IT进行循环1：

令QIT为空集φ；

令FIT=[∞,∞]；

令x=1 ton，进行循环2：每只蚂蚁依次寻觅其路径，n为蚂蚁数；

采用贪婪搜索办法寻觅路径Aij(详见2.2节)；

对路径Aij进一步进行多目标迭代搜索优化，生成新解Qo；(详见第2.3节)

更新局部信息素(I,Qo)；

如果FQo>FIT，则FIT=FQo，QIT=Qo；

如果FQo

令FIT=(FIT,FQo)，扩充函数值矩阵；

令QIT=QIT∪Qo；

循环2结束；

更新全局信息素(I,Q,QIT)；(详见第2.4节)

循环1结束；

返回Q、F1两个值。

2.2 蚂蚁寻径原则

迭代过程中，蚂蚁在走过的路径上会留下信息素。假设信息素初始浓度为Tij0=1/Dij，令Tijk代表第k次迭代中弧(i,j)的信息素浓度，蚂蚁x在运动中根据路径信息素浓度和效用函数(φij)α(φij)β选择下一步前往的节点，当蚂蚁x在节点i时，通过式(6)式(7)的寻径原则转移到节点j，Pxij表示蚂蚁x由节点i转移到节点j的概率。其中B1为均匀分布在[0,1]上的随机数，B1值可预先设定。当B≤B1时，蚂蚁转移到使效用函数Tijk(φij)α(φij)β值最大的节点j，否则按式(8)进行选择转移到节点j，B1越大说明蚂蚁贪婪概率越大，Cxik表示蚂蚁x在第k次迭代中达到节点i时未访问节点的集合。

(2)

(3)

(4)

(5)

式中：φij为节点i和节点j在同一条路径与不同路径距离的差值与节点i和节点j间距离的比值，φij为节点i和节点j在同一路径上额外需要的载重容量的倒数。φij、φij和寻径规则体现了蚂蚁服务需求差最小客户时，偏好距离最短的贪婪性。参数α和β代表φij和φij对转移概率的影响因子。每只蚂蚁从中心节点出发，根据式(2)-式(3)选择下一个节点，生成路径，当Cxik=φ时，蚂蚁返回中心节点，并再次从中心节点出发，开始新的寻径，直到所有节点都被访问过。

蚂蚁寻径过程中，按寻径规则转移到下一个节点，到达该节点后，对其载重容量和距离约束进行判断，如果达到最大行驶距离，则蚂蚁回到中心节点;如果超出载重容量，则将该节点从未访问的节点中删除，在未访问节点集合中重新搜索下一个节点，直到找到能访问的节点，或者所有未访问点均被禁忌则回到中心节点。

蚂蚁寻径过程如算法2所示。

算法2 蚂蚁寻径过程

初始化：中心节点A0=1，路径R=[Ai]，Ai为当前节点，未访问节点U，每条路径长度RD，禁忌表tabu=∅；

当U=∅时，进行循环：

按寻径准则选择下一个节点N；

令当前巡回长度tD=0，Ra=[R,N]；

令Ra中最后一次到达中心节点后访问的节点为当前巡回Y；

计算Y连接弧上的车辆载重量Zc和当前巡回长度tD；

如果(1)max(L)≤Z，即容量未超出；

如果(2)tD+D(N,1)≤L，即从下一点回中心节点的距离没有超出距离约束；

则R=Ra；Ai=N；U=(U,N)∪tabu；

tabu=[]；即释放禁忌表；

否则，距离超出，则在访问节点N前返回中心节点；

蚂蚁回到中心节点，生成巡回路径(R,tD,RD)=[RD,tD]；

开始新的巡回，令新巡回长度tD=0，Ai=1；

如果(2)结束；

否则，容量超出时，将下一个节点N添加到当前节点Ai不能访问的禁忌表中；

tabu=[tabu,N]；

U=U/N；

如果(3)U=∅且tabu=∅，当前节点到未访问节点间均超出容量；

蚂蚁回到中心节点，记录生成的路径信息(R,tD,RD)=[RD,tD]；

开始新的巡回，令新巡回长度tD=0，Ai=1；

U=tabu，tabu=[]，释放被禁忌的节点；

如果(3)结束；

如果(1)结束；

大循环结束；

记录完成路径Rw，并根据RD计算目标函数。

2.3 多目标局部搜索

蚂蚁找到一条路径后，采用局部搜索法来进一步优化路径。这里采用两种Swap交换法：交换一条路径上任意两个节点，交换两条不同路径上任意两个节点。因为节点需求不同，交换节点后就可能出现不可行解或者原解更优的情况，因此进行交换后，需要对新生成路径进行验证，如果该解更优，则择优保留，如果生成新的帕累托解，则生成新的解集K。

2.4 信息素浓度更新准则

蚂蚁在找到一个解后，按下式更新路径上的信息素浓度:

(6)

式中:ρ为信息素挥发程度，Q为信息素强度，Lgb为当前最优解，取Q为100。

每次迭代完成，从所有蚂蚁找到的解中，将所有帕累托解作为迭代最优帕累托解集，将迭代最优帕累托解集与全局最优帕累托解集进行对比，保留并更新最优帕累托解集。

2.5 目标函数

目标函数设定为：

S=S1+S2

3 实验环境

实验配置是由两个开源软件NS2和SUMO共同组成。应用两个时间窗，长时间窗tl和短时间窗ts，分别为120 s和60 s。在每个短时间间隔后对数据进行初始化，在每个长时间间隔后进行路径优化计算。所以，任何路径重构都是在长时间间隔后才完成的。实验初始化流程如图1所示，相关实验参数如表1所示。

图1 实验初始化流程图

参数参数值技术IEEE80211.P频带15 MHz～2.7 GHz衰变对数距离能量大小10 dBm长时间窗tl120 s短时间窗ts60 sTSD、TSM大小100字节仿真周期3 600 s

地点选择了西安市市中心，应用ArcGIS10.3软件生成道路网络图，如图2、图3所示。每条边与包含道路元素的节点的端点相对应，主要考虑以市中心钟楼为圆点，半径3～5 km范围内500组不同目标点道路的行驶，车速为40～60 km/h，车辆载重为5 t，车型为普通卡车。

图2 西安市道路网络图

图3 局部道路详图

4 实验部分

4.1 算法与传统优化算法对比

仿真中可知，在求解动态路径优化问题时，多目标粒子群算法求解结果优于蚁群算法，改进的多目标蚁群算法求得的解优于多目标粒子群算法，其车辆平均旅行时间更短。在时间窗要求下随机选择路径就可能造成交通拥堵。然而，当道路拥堵可以用一些特殊的道路因素来估计时，就可以用特定算法来估计动态路径，为决策者提供一条更优的路径。在优化过的路径上行驶，车辆能更好地避免道路拥堵，更早抵达目的地。

不同迭代次数后蚁群算法、多目标粒子群算法和改进的多目标蚁群算法优化后的旅行时间对比情况如图4所示。由图4可知，蚁群算法的平均旅行时间最长，基本都在350 s以上，最长在500 s左右，多目标粒子群算法则相对短一些，最短在285 s，改进的多目标蚁群算法平均旅行时间最短，最长也在400 s以内，平均旅行时间比多目标粒子群算法短13.2%，比蚁群算法短20%。当城市中车辆数量增加时，平均旅行时间也将因为道路拥堵和车速的变化而逐渐增加，三种算法在不同车辆数量时旅行时间求解情况如图5所示。蚁群算法在车辆数量相同时，平均旅行时间要比多目标粒子群算法长9.9%，而改进的多目标蚁群算法在车辆数量相同时，平均旅行时间比多目标粒子群算法短11.4%。蚁群算法在优化车辆路径时，收敛比多目标粒子群算法要快，改进的多目标蚁群算法则比蚁群算法收敛得更快些。因此，用改进的多目标蚁群算法优化车辆动态路径时，会更快地获取路径更新信息，与之前路径信息形成对比。

图4 不同迭代次数条件下三种算法求解的旅行时间对比

图5 不同车辆数量条件下三种算法求解旅行时间对比

计算复杂度对比情况如图6所示。由图可知，同样在3 600 s的仿真周期内，蚁群算法的求解时间在2 000 s左右，多目标粒子群算法在2 103 s左右，而改进的多目标蚁群算法在2 187 s左右，也就是在计算复杂度上比蚁群算法增加8.9%，比多目标粒子群算法增加3.5%，增加幅度较小，且增加量在可接受范围之内。

图6 三种算法计算复杂度对比

4.2 算法与三种最新优化算法对比

与改进灰狼优化算法[14]、改进细菌菌落优化算法[15]和鼠疫传染病优化算法[16]三种最新优化算法在不同条件下对动态路径问题求解旅行时间进行对比，分析本文改进优化算法优劣。

4.2.1与改进灰狼优化算法(GWO)对比

在相同迭代次数条件下，改进多目标蚁群算法求解的路径平均旅行时间比改进灰狼优化算法要短3.33%，具体如图7所示。由图7可知，两者最优解基本相似，收敛速度上多目标蚁群算法要快一些。

图7 不同迭代次数条件下求解旅行时间与GWO优化算法对比

在不同车辆数量条件下，改进多目标蚁群算法求解的路径平均旅行时间比改进灰狼优化算法要短4.82%，具体如图8所示。由图8可知，在车辆数量小于250辆时，改进灰狼优化算法总体与改进多目标蚁群算法求解的旅行时间很接近，尤其当车辆数量在200～250辆之间，求解旅行时间几乎差不多，但当车辆数量较大时，多目标蚁群算法的优势得到凸显，比GWO算法求解旅行时间要短5%以上。

图8 不同车辆数量条件下求解旅行时间与GWO优化算法对比

4.2.2与改进细菌菌落优化算法(BCO)对比

在相同迭代次数条件下，改进多目标蚁群算法求解的路径平均旅行时间比改进细菌菌落优化算法要短5.21%，具体如图9所示。由图9可知，多目标蚁群算法最优解要比BCO算法好一些，但BCO算法收敛速度较快些。

图9 不同迭代次数条件下求解旅行时间与BCO优化算法对比

在不同车辆数量条件下，改进多目标蚁群算法求解的路径平均旅行时间比改进细菌菌落优化算法要短5.36%，具体如图10所示。由图10可知，当车辆数量小于150辆时，BCO算法与改进多目标蚁群算法在求解旅行时间上几乎一致，在车辆数量达到中等规模(150～250辆之间)时，多目标蚁群算法的求解旅行时间相对短的优势就逐渐凸显，当车辆数量较大时，BCO算法与多目标蚁群算法的时间差距进一步增大，旅行时间要长6%左右。

图10 不同车辆数量条件下求解旅行时间与BCO优化算法对比

4.2.3与鼠疫传染病优化算法(PIDO)对比

在相同迭代次数条件下，改进多目标蚁群算法求解的路径平均旅行时间比鼠疫传染病优化算法要短5.63%，具体如图11所示。由图11可知，多目标蚁群算法求解旅行时间比PIDO算法要总体短得多，且收敛速度较快。

图11 不同迭代次数条件下求解旅行时间与PIDO优化算法对比

在不同车辆数量条件下，改进多目标蚁群算法求解的路径平均旅行时间比鼠疫传染病优化算法要短6.21%，具体如图12所示。由图12可知，总体来说PIDO算法与多目标蚁群算法在求解旅行时间上保持着6%左右的时间差距，但当车辆数量达到250辆左右，其求解旅行时间非常接近。

图12 不同车辆数量条件下求解旅行时间与PIDO优化算法对比

5 结 语

改进的多目标蚁群优化算法考虑了行车距离约束，引入了贪婪搜索与禁忌表，应用多目标搜索改进求解收敛。算法与传统优化算法相比，虽然在计算复杂度上有小幅度增加，但其求解动态路径优化时，路径的旅行时间在同等迭代次数时更短，平均有13%的浮动差，在同样车辆数量条件下旅行时间也更短，平均短10%。与三种最新优化算法(GWO、BCO、PIDO)对比，在不同迭代条件下求解旅行时间时，虽然收敛速度存在差异，但平均分别缩短了3.33%、5.21%和5.63%。在不同车辆数量条件下求解旅行时间时，多目标蚁群算法求解的平均旅行时间要比三种最新优化算法分别短4.82%、5.36%和6.21%。说明其生成的路径更优，能更好地避免道路拥堵、满足运输时间硬要求，实现燃料节约，路径实用性更强。另外，改进的多目标蚁群算法的可变性和应用性也非常强，在其他组合优化问题中也可进一步探索，是非常值得深入研究的优化领域，为未来复杂环境下动态路径问题的研究提供参考。