基于蚁群算法的应急物资运输路径优化*

杨菊花，朱昌锋，田志强

(兰州交通大学交通运输学院，甘肃 兰州 730070)

地震、火灾、流行性传染病等突发事件的频发，给人民群众生命财产和社会安全造成极大的危害。在突发性很强的自然灾害和公共卫生事件发生的地区，往往平时没有赈灾物资储备，或储备的数量和种类有限，在应急物资供应方面表现出被动局面，需要大量从全国各地紧急调运。为此，有关专家学者就该问题开展了大量的研究。刘志学等［1－2］从供给的角度提出了路网的容量可靠性指标，以考虑在交通事件影响下路网能够容纳一定水平交通量的概率;Sumalee等［3］建立了不确定需求下的以总行程时间可靠性最大化为目标的网络设计问题的数学模型;Chootinan等［4］建立了以容量可靠性最大化为目标的网络设计问题的双层规划模型;欧忠文等［5］就应急物流保障机制开展了相应的研究，张晓波等［6－7］对应急物资公路运输的最短路径进行研究和求解。由于应急物资的特殊性，单从公路一种运输方式探讨其路径的选择问题难以满足实际的需要。此外，从多种运输方式角度探讨应急物资的调运路径问题，由于存在多目标、多种类货物等约束条件，使得应急救援物资运输问题的构建与解决非常复杂。目前讨论此问题的文献较少，不能与其重要性及目前应用需要相适应。且大多内容重点研究了如何将应急物资快速有效的从灾区救灾中心运往各个受灾点，而没有涉及应急物资的全程调运问题。鉴于此，本文拟结合有关研究成果，建立应急物资全程调拨时运输方式和路径选择问题的综合优化模型，为应急决策提供一定的参考。

1 研究的理论基础

1.1 多式联运理论

应急物流需要综合考虑运输的时效性和各种运输方式的通行能力，以最短的时间、最快的速度、最大限度的流量将应急物资运送至目的地［8］。本文尝试将多式联运引入应急物资调运径路的选择中，建立最短运输时间最大流的模型，运用于自然灾害等突发性事件的应急物资运输路径选择。同时，考虑突发性事件引发的路面变化对车辆的延误，增强了对时效性的约束。

1.2 交通网络脆弱性

当发生地震、泥石流等自然灾害事件时，很可能对原有路径造成破坏，必须考虑原有运输路径被破坏引起的最优路径的变化。因此，本文引入交通网络脆弱性理论。1981年，Timmerman［9］提出了脆弱性的概念，即在灾害事件发生时系统受不利因素影响退化的程度。目前国内外关于交通网络脆弱性指标的构建主要是从网络的拓扑结构和居民出行行为2个方面考虑的，本文拟采用Kalika Suksomboon［11］等提出的期望可达通行能力脆弱性指标(Expected achievable capacity EAC)来定义运输网络的可靠性。

定义应急物资路径k的可达通行能力为

式中:L(k)表示路径k所包含的各种运输方式的路段集;ce表示路径k的通行能力。

假设qj为第j种灾害发生的概率，ce，j为运输网络在第j种灾害发生情况下路段e的通行能力:

基于以上定义，第j种灾害发生的情况下，路径k的可达通行能力可表示为:

在多用户需求的网络中，K为单个OD对之间的路径数，网络在非正常情况 J={1，2，3，…，j}下，网络可达通行能力矩阵可定义为:

假设用户选择各路径的概率为HT={H1，H2，H3，…，HK}，各情景发生的概率为 QT={q1，q2，q3，…，qJ}。在用户选择路径概率HT和情景概率QT已知的情况下，系统期望可达通行能力CEA定义为:

2 优化模型构建

综上，目标函数包含两部分，第一部分为运输流量最大，选择在不同节点之间运输流量最大的方式为最优路径，并考虑因非正常情况引起路网容量的变化。该部分目标函数为:

第2部分为运输总时间最省，该部分目标函数为:

运输总时间包括运输时间、中转接续时间和延迟时间。目标函数的约束条件为:

其中:式(8)表示在相邻阶段的节点之间，若存在路径，则只能选择1种运输方式.即运量不能分割;式(9)表示在每个节点只有1次运输方式的改变;式(10)可以确保运输的连续性;式(11)表明货物必须在规定的期限内运到，决策变量取整数变量0或1。

将上述2个模型汇总加以变换，则总目标函数为:

该目标函数表示运输单位流量物资花费的时间最短，与原目标函数一致。

3 算法设计

蚁群算法是一种典型的基于构建式求解过程的群智能优化算法，该算法利用了正反馈原理，在一定程度上可以加快进化过程，是一种本质上并行的算法［12］。

3.1 解构建图的表示

根据本文优化的目标，对于结点i，若存在m种运输方式能够到达该结点，则在解构建图中为结点i复制m个虚拟结点，分别为Vi1，Vi2，…，Vim。最终的解构建图如图1所示。需要指出的是，该解构建图是一个无环的网络，当从结点i出发只能以一种运输方式到达唯一的网络结点j时，结点i和j间仅以弧 arc(i，j)相连(如图1 中 arc(v6，vt2))，当从结点i出发可以选择n个路段及相应的m种运输方式时，分 别 对 应 弧 arc(i，j11)，arc(i，j12)，…，arc(i，jnnm)(如图 1 中 arc(vs，v11)，arc(vs，v12)，…，arc(vs，v22))。

图1 解构建图Fig.1 The construction diagram of solution

图中的实线表示从上一结点选择第m种可能的运输方式到达当前结点;虚线表示虚拟的连接，意味着无论选择何种方式到达该结点，下一步都可以认为实际上仍是从该结点出发。

3.2 解的构建

在构建解时，若选择的下一路段arc(i，j)的流量fij小于当前流量fnow，则将当前流量fnow更新为fij，同时，对于除起点及终点外的所有结点，若到达该结点的路段与从该结点出发的路段的运输方式不同时，需要计算相应的中转接续时间。

3.3 信息素的表示、初始化及更新

τij是指当蚂蚁处于网络结点i时，选择从结点i出发的第j条路线的期望程度。第j条路线包含两层含义，分别对应之前描述的2种不同情况。执行迭代前，各路径上的信息素初值均按下式确定:

其中:ni为在结点i时可以选择的路径(包括到达不同结点的路径以及到达相同结点的不同运输方式)的总数。

每次迭代之后，各路径上的信息素可按下式更新:

式中:ρ为信息素的挥发系数，0＜ρ＜1;n为迭代次数;Δτij为本次迭代的信息素增量。

设sib为第n次迭代的最优解，fib为sib的目标函数值，则Δτij可由下式确定:

3.4 选择策略

启发式信息ηij按下式取值:

其中:θij是1个与当前流量以及各路段流量相关的函数。其计算公式如下:

在初始状态，有f0=max{fij}。θij的设置能够使蚂蚁在构建解的过程中，更倾向于选择流量较大(大于等于当前流量)的路段。

3.5 评价函数的建立

当给定解构建图中1条从源点至汇点(起点至终点)的路径后，可以很快的计算出该路径的最大流量以及相应的走行时间，因此，本文直接选取问题的优化目标式(12)作为蚁群算法的评价函数来衡量蚂蚁构建出的解的质量。

3.6 算法终止条件

当蚁群算法连续若干次迭代找到的解不发生改变时，算法停止。

4 实例分析

假设以兰州可达汶川的公路和铁路两种运输方式的有效路径为基本的网络图，兰州至汶川的可达路径、每2个结点间的运能和运输时间如图2所示。该路网图中的数据均为参考历年统计年鉴后的平均值。

在图2所示的路网图中只选取了运量较大且在路网中比较重要的城市作为结点，在不影响其计算结果的情况下对兰州至汶川的路网图进行了简化。具体求解的流程图如图3所示。

图2 兰州至汶川路网图Fig.2 Network diagram from Lanzhou to Wenchuan

图3 蚁群算法流程图Fig.3 Flow chart of ant colony algorithm

在自然灾害或公共卫生事件突发的情况下，很可能会对路网的可达性以及通行能力造成影响。

4.1 对路网可达性未造成影响时的最优路径

通过多次搜索和叠代，图2中兰州至汶川的最优路径为:

目标函数值为0.1418。

4.2 对路网可达性造成影响时的最优路径

假设上述最优路径中广元至绵阳段的公路运输无法通行，则图2中兰州至汶川的最优路径为:

目标函数值为0.2222。

5 结论

为了尽快地将尽可能多的应急物资运往灾区，避免将“天灾”变成“人祸”，需要动员全社会的力量，各种运输方式必须全力以赴，共同完成应急物资的运送。本文将多式联运理论引入对应急物资运输路径的研究，可以清楚地发现路网中结点之间的运输时间、通过能力以及路网的可靠性，都对应急物资的运输产生重要的影响。由于航空运量相较公路和铁路比较小，在应急物资的大批量长途调运中并不能担当重要作用，因此，本模型的算例结果种并没有包含兰州可达汶川的航空运输。这并不是说航空运输不重要，在涉及挽救生命的特殊物资时，航空运输的快捷性是其他运输方式无法比拟的。

［1］刘志学.现代物流［M］.北京:中国物资出版社，2002.LIU Zhi－xue.The modern logistics［M］.Beijing:China Materials Press，2002.

［2］Chen J，Huang J，Chen S Q.A simple linear time approximation algorithm for multiprocessor job scheduling on four processors［C］//Shenged H T.Algorithms and computation，LNCS 1969.Berlin:SPringer，2000:60 －71.

［3］Sumalee A.Optimal implementation－path of road pricingschemes with time－dependent model［C］//The sixth annual conference of the international emergency management society.Deltf，Netherlands，2008:8 －11.

［4］Chootinant P，Wong S C，Anthony Chen.A reliabilitybased network design problem［J］.Journal of Advanced Transportation，2005，30(30):247 －270.

［5］欧忠文，王会云，姜大立.应急物流［J］.重庆大学学报，2004(3):164－167.OU Zhong－wen，WANG Hui－yun，JIANG Da－li.Emergency logistics［J］.Journal of Chongqing University，2004(3):164－167.

［6］张晓波，谢红薇.并行遗传算法求解应急系统最短路径的研究［D］.太原:太原理工大学，2005.ZHANG Xiao－bo，XIE Hong－wei.Research on shortest path in emergency system using parallel genetic algorithm［D］.Taiyuan:Taiyuan University of Technology，2005.

［7］卢 茜，施先亮.地震灾害应急物流系统中公路运输路径选择的研究［D］.北京:北京交通大学，2009.LU Qian，SHI Xian－liang.Research of route choosing in road transportation of logistics emergency system for earthquake disaster［D］.Beijing:Beijing Jiaotong University，2009.

［8］段满珍.国际集装箱运输与多式联运［M］.北京:清华大学出版社，2011.DUAN Man－zhen.The international container transportation and multimodal transportation［M］.Beijing:Tsinghua University Press，2011.

［9］Timmerman P.Vulnerability，resilience and the collapse of society［M］.Institute for Environmental Studies，University of Toronto in Toronto，1981.

［10］Berdica K.Vulnerability in the road transportation system－ basic concepts and theoretical framework［C］//TRITA－ IP AR 99－73，Institutionen för infrastruktur och samhällsplanering，KTH，Stockholm，1999.

［11］Piwat P S，Suksomboon K，Aswakul C.Vulnerability analysis in multicommodity stochastic networks by game theory［C］//Proceedings of ECTI－ CON，357－360.IEEE，2008.

［12］段海滨.蚁群算法原理及其应用［M］.北京:科学出版社，2005.DUAN Hai－bing.Theory of ant colony algorithm and implement［M］.Beijing:Science Press，2005.