基于时变性和可靠性的地震灾害应急物流运输路径选择＊

蔡鉴明，李夏苗，杨光华

(1.中南大学交通运输工程学院，湖南长沙 410075;2.湖南交通职业技术学院物流管理系，湖南长沙 41004)

基于时变性和可靠性的地震灾害应急物流运输路径选择＊

蔡鉴明1，李夏苗1，杨光华2

(1.中南大学交通运输工程学院，湖南长沙 410075;2.湖南交通职业技术学院物流管理系，湖南长沙 41004)

在地震灾害应急物流运输路径选择中，时效性和可靠性是主要评价指标。考虑到地震灾害情况下运输网路特征的时变性，分析应急物流运输路径行驶时间的时变性计算问题，并对该网络的时变安全可靠性计算进行分析。在评价指标进行无量纲化处理的基础上构建预测和评价应急物流运输路径的多目标决策模型，通过算例说明其应用方法，并验证其有效性。

应急物流;运输路径;时变性;可靠性;地震灾害

应急物流是指为控制突发事态的进一步发展，采取非常规方式，向事件影响范围内供应紧急救援物资的具有动态特征的特种物流活动，具有突发性、不确定性、弱经济性、非常规性等特点［1］。为了应对各种突发事件，国家有关部门制定了相应的应急救援预案，其中应急救援物资的运输是救援工作的重点，而应急救援物资运输路径的选择问题是确保这一工作顺利进行的关键。应急物流运输路径问题也是网络路径优化问题之一，在网络上，根据网络弧(边)的权值是否随时间发生变化，把路径分为静态路径和动态路径2种，相应的网络称为静态网络和动态网络。目前对于应急物流运输路径的研究主要在静态网络方面［2－4］。但是，静态网络弧权所赋的值都是静态的、确定的，这与应急突发的实际情况不太相符，应急物流网络常常具有动态性。尤其在强地震灾害情况下，其引发的次生灾害具有不确定性和强破坏性，导致运输网络的结构特征、功能不断发生变化，弧权值随时间发生动态变化，运输配送网络的连通可靠性和车辆行驶在路径上各弧和节点的速度呈现时变性。所以应急物流运输路径的选择应综合考虑多种影响因素，强调运行的时变性、速度性以及运输路线的可靠性，是一种典型的多目标决策问题，其中时变性和可靠性是主要的2个目标。目前，关于时变路径选择问题已有一些研究，但主要是基于单一时变网络的最小时间路径选择。Sung等［5］为了求解时变网络的旅行时间最短路径问题，提出了一个依赖于时间间隔及车辆速度的流速模型，其求解算法是从Dijkstra的标号设置算法修改而来。Davies等［6］针对动态随机网络中权值(旅行时间)是已知时间函数的情况，设计了一个寻找最短路径的遗传算法，以应用于计算机和公路网络的路径选择。Cai等［7］考虑到运输时间和成本是弧的起始点的出发时间的函数，对在有向图中寻找具有最小可能成本的路径问题进行了研究，其约束条件是总的旅行时间，允许出发时间延迟，并对在各个顶点可以有任意等待时间、禁止等待和具有上限的等待时间3种情况进行了分析。Miller－ hooks等［8－10］认为在拥堵的交通网络中，弧权(旅行时间)是具有时变概率函数的随机变量，其中，Miller－ hooks等［8］研究的是确定从起点到目标点的路径的最小可能时间及概率分布;Miller－hooks等［9］研究的是在随机时变网络中确定一个先验的最小期望时间路径;Miller－hooks等［10］则考虑了在某一给定时间内，从起点到目标点之间的路径不只一条，每一条都具有最小旅行时间的概率，研究的目标是在这样的情况下去选择一条合适的路径。魏航［11］针对时变条件下具有时间约束的有害物品运输路径选择问题，分别就单一运输方式有宵禁限制的情况和多式联运方式进行了研究，设计了最短路径求解模型和算法。海军［12］研究了时变动态军事配送运输网络最短时路径、最小时间最大能力路径问题。谭国真等［13］分析了时变网络与一般网络中最短路径求解的差别，从理论上证明了传统最短路径算法如Dijkstra算法和标号设置算法不能有效地求解时变网络中的最短路径问题，并给出了在没有任何限制性条件的情况下时变网络最小时间路径的求解算法。从现有相关研究文献来看，关于应急物流的运输路径选择中把时变性与时效性和可靠性结合研究的成果很少。因此，该研究有助于丰富和拓展应急物流理论。

本文从运输路径的行驶时间和可靠性的角度，分析了地震灾害情况下应急物流运输网络的时变性，通过对行驶时间和可靠性这2个指标做无量纲化处理，再根据时效性和可靠性在不同情况下对于应急物流运输配送时，选择路径决策影响的不同，给出不同的权重值，供决策者在时效性和可靠性之间进行权衡决策，以便进行应急物资运输路径的合理选择。

1 地震应急物流运输路径时变性分析

1.1 问题表述

这里，应急物流运输路径时变性是指在地震灾害情况下应急物流运输配送网络中的弧、节点的可靠性及运输工具在各条弧上的行驶时间，由于受灾害的影响会随时间发生变化。这样的时变动态运输网络简称为时变网络。其优化目标是使运输通过的路径的总时间最短，而可靠性最大。该问题可描述如下:设时变网络为TVN=(V，A，W，R)，其中:V={v1，v2，v3，…，vn}是有限节点集;A是有限弧集，A∈V×V;W=Tij(t)是对每个弧对(vi，vj)∈A，在时间t∈t0，t[ ]e区间上定义的矩阵函数;[t0，te]为感兴趣的时间闭区间;t0是时变网络中从任一节点出发的最早时间;te是感兴趣区间的端点;其值为非负实数，表示从节点vi在时刻t0出发到达节点vj所需的时间。时间段可分为连续性时间和离散性时间情况。R是每个弧对(vi，vj)∈A及每个节点vi∈V，在时间t∈t0，t[ ]e区间上定义的矩阵函数，表示各弧对和各节点在t时间的可靠性。

1.2 时变网络运输路径通行时间分析

设Pst(t0)表示时变网络中从节点vs在t0时刻出发到达节点vt的路径，即:

式(2)表示沿此路径运动所需要的总时间。如果需求时变网络最短时路径为Tmin(t)，即是从源点vs在时刻t0出发到达终点vt的所有路径中走行总时间最短的路径。同样可得时变网络最大时路径Tmax(t)。即满足:

在时变网络中，当源点、终点和出发时刻t0确定后，就可以确定其路径和通过的时间。

时变网络时间路径问题的数学模型定义如下:

式(5)为目标函数，Tij(t)为时变网络TVN中从vi到vj的通行时间，如果(vi，vj)∉A，则时间为+∞。xij(t)∈0，{}1，如果路径在t时间经过弧(vi，vj)，则为 1，否则为 0。

式(6)为离散时变函数，是将时间分为若干段，各段内车辆通行时间不发生变化，这样，式(6)表示为第k个时段的时间阻抗Tkij(k=1，2，…，n)，而得到的路段 (vi，vj)的时间阻抗函数Tij(t)，其中[tkp，tkq]为第k个时段的起止时间。其实际意义是地震余震及其次生灾害的发生，会造成路段在不同时间段内的部分损坏或完全损坏，如路段塌陷、建筑物倒塌或山体滑坡造成路段堵塞等，这些情况就需要对道路进行修补、清理和疏通，此时行驶在该路段的车辆就有可能需要等待路段的修复，或者减速行驶;当路段修复好后，车辆又可以恢复到正常速度行驶。这样的情况，很可能会造成同一路段在不同的时段内车辆的旅行时间不同。

时变网络与静态网络有很大不同，由于时变网络具有实时动态性，所以，时变网络中可能会出现先出发后到达或者后出发先到达的现象，故时变网络将会存在着2类弧:一类为先进先出弧，记为FIFO弧;另一类为后进先出弧，记为NFIFO弧。

FIFO网络的理论基础与静态网络最短路算法的理论基础相同，可用传统静态网络最短路径算法求出。由于时变网络中可能存在NFIFO弧，而NFIFO弧不满足FIFO原则的一致性假设，因此不能用传统的静态网路最短路径算法求出。所以，时变网络最短时路径问题的关键，是解决时变NFIFO网络问题。NFIFO网络时间路径算法可参考文献［12－13］。

1.3 应急物流运输路径时变可靠性分析

大地震后往往有多次余震。主震已将震区运输网络及路段周边的环境进行了不同程度的破坏，余震将会进一步增加对路段及周边环境的影响而引发次生灾害，如部分损坏的路段会被完全中断，路段旁边已开裂倾斜的建筑物或山坡上松动的岩石可能会突然垮塌冲向道路等，从而影响运输路径的安全可靠性。各路段的安全可靠性可根据各路段的周边环境因素和余震可能引起的次生灾害情况，并结合专家的知识和经验进行评估和预测。余震的发生可能会引起新的安全隐患，安全隐患一旦爆发，隐患也就有可能被解除。因此，同一路段在不同的时间段内，其安全可靠性是不同的，也就是说具有时变性。

在地震灾害应急物流运输时变网络TVN=(V，A，W，R)中，假设路径P经过的节点集合Vp={v1，v2，…，vx}，弧集合AP={e1，e2，…，ex－1}，那么，路径相当于经过该路径所有节点和弧的串联系统。根据系统可靠性理论，路径的可靠性是这些节点和弧在给定时间内的可靠性的乘积。这里，可靠性指在规定条件下和给定时间内路径、节点和弧正常运行的概率。时变路径可靠性可用公式(7)来描述:

式中:Pr(t)为路径在时间段t的可靠性;x为节点数量;Px(t)为第x个节点在时间段t的可靠性;Pv，i(t)为第i个节点在时间段t的可靠性;Pe，i(t)为第i个弧在时间段t的可靠性。则网络在时间段t的最大可靠性Pmax(t)，为:

Pr(t)越大，表示该路径在时间段t的可靠性就越大。

2 目标决策分析

根据问题的特点，本文设计基于线性加权法的最优路径选择多目标规划模型求解算法，其主要步骤如下。

由于上述模型目标的量纲不同，本文采用极值处理方法进行目标无量纲化处理。首先确定应急物流在t时间的时效限制T*(t)值，即在t时间内，应急物流备选的运输路径旅行时间不能超过T*(t)，否则该路径不予考虑。根据模型，分别求出应急物流运输路径出发点和接受点之间的最小行驶时间Tmin(t)的运输路径，和行驶可靠性最大Pmax(t)的路径。再选出其他K条备选路径，求出Tk(t)和Pk(t)，其中k∈K，标示k表示第k条路径，选出Tmax(t)和Pmin(t)。假设最短和最长行驶时间分别为Tmin(t)和Tmax(t)，最小和最大可靠性分别为Pmin(t)和Pmax(t)。设:

式中:规定T*(t)≥Tmax(t)＞Tmin(t)＞0;g1k(t)为在t时间，第k条路径时效性的无量纲指标。由于Tmax(t)≥Tk(t)≥Tmin(t)，所以1≥g1k(t)≥0，而且Tk(t)越小g1k(t)取值越大，即时效性越好。公式(9)的分母不能为0，否则所有备选路径的旅行时间相同，这种情况无需考虑路径的旅行时间。

同理，在t时间，第k条路径可靠性的无量纲指标g2x(t)为:

公式(10)的分母不能为0，否则所有备选路径的可靠性相同，这种情况无需考虑路径的可靠性。由于可靠性为概率测度，所以有1≥Pmax(t)＞Pmin(t)≥0。

假设决策者在t时间对时效性和可靠性分量确定的权重为 λ(t)=(λ1(t)，λ2(t))T，其中，λ1(t)为在t时间的时效性决策权重，1≥λ1(t)≥ 0;λ2(t)为在t时间的可靠性决策权重，1≥λ2(t)≥ 0;λ1(t)+λ2(t)=1。应急物流备选路径优化多目标规划模型可化为:

式中，g(t)为最终决策指标，其值越大效果越好，g(t)值最大的路径作为决策最终结果。λ1(t)，λ2(t)值反映决策者对时效性和可靠性的关注程度，由决策者根据事态和任务确定。如果任务时效性要求很高，则λ1(t)取较大数值，如果路径运输安全可靠性要求很高，则λ2(t)取较大数值。

3 算例

图1所示为简单的地震灾害应急物流网络图，起点v1为应急物资配送中心，终点v6为应急物资需求点，v2，v3，v4，v5为配送运输网络通过的中间点，从v1到v6间共有5条备选出行路径，且都满足救援时效限制值。路权函数为分段函数，由于天气情况、各路段的周边环境、各路段的等级、损坏程度及修复情况等不同，不同时间各路段的通行时间不同，各路段的安全可靠性参数也不一样。该网络各路段的通过时间和安全可靠性参数如表1所示(为了便于计算，假定各节点可靠性参数为1)。应急管理决策人员给出的时效性和可靠性决策权重向量分别是 (0.9，0.1)T和 (0.2，0.8)T，现在考虑第1 d和第2 d的应急物资运输情况，每天都分别从上午6∶30和7∶20发车，需要确定符合决策意图的最佳行驶路径。

图1 应急物流运输网络图Fig.1 Transportation network diagram for emergency logistics

(1)路径的时变旅行时间和可靠性计算。根据表1的数据可知，图1网络中存在NFIFO弧，因此图1为NFIFO网路。依时间路径计算，出发时间为6∶30的应急网络最小时间运输路径是v1－v4－v5－v6，时间为210 min;出发时间为7∶20的应急网络最小时间运输路径是v1－v4－v5－v6，时间为230 min。按公式(7)和(8)计算，在第1 d求得最大安全可靠的路径是v1－v2－v3－v6，其安全可靠性参数为0. 315;在第2 d求得最大安全可靠的路径是v1－v2－v3－v5－v6，其安全可靠性参数为0.358 4。再选出其他备选路径，计算行驶时间和安全可靠性。如表2所示。

表1 运输网络各路段通过时间和可靠性参数(时间单位:min)Table 1 Travel time and reliability parameters for the arcs of the transportation networks(time unit:min)

表2 应急物流运输路径通行时间和安全可靠性参数Table 2 Travel time and safety reliability parameters of the transportation routes for emergency logistics

(2)无量纲化处理。在2 d的应急物资运输中，出发时间为6∶30时，路径3为Tmin(t)=210 min，路径5为Tmax(t)=395 min;出发时间为7∶20时，路径3为Tmin(t)=230 min，路径5为Tmax(t)=455 min。在应急物资运输的第1 d，路径1的可靠性为Pmax(t)=0.315，路径 5的可靠性为Pmin(t)=0.043 2;在应急物资运输的第2 d，路径2的可靠性为Pmax(t)=0.358 4，路径4的可靠性为Pmin(t)=0.168。利用公式(9)和(10)对各备选路径属性分量进行无量纲处理，再利用式(11)计算各备选路径的决策效用指标g(t)，结果如表3和表4所示。

表3 第1 d备选路径决策指标计算结果Table 3 The results of decision indexes of the routes for the first day

表4 第2 d备选路径决策指标计算结果Table 4 The results of decision indexes of the routes for the second day

从表3可以分析，在应急物资运输的第1 d，决策权重为 λ1(t)=0.9，λ2(t)=0.1 时，路径3，即v1－v4－v5－v6为最优路径。决策权重为λ1(t)=0.2，λ2(t)=0.8时，路径1即v1－v2－v3－v6为最优。

根据表4可知，在给定的决策权重和出发时间情况下，第2 d应急物资运输的最优路径是路径3。

由于篇幅限制，这里只是一个简单的算例，在大地震灾害实际中，路径的旅行时间和可靠性参数变化要比该算例复杂得多。

4 结论

(1)根据地震灾害应急物流运输路径的实际情况，考虑到运输网络各路段的旅行时间和可靠性的时变性，以及决策者的决策权重等因素作为指标，给出了路径选择问题分析和计算模型。

(2)通过仿真算例可知，该模型的求解结果与只考虑旅行时间的模型的求解结果是不同的。例如在应急物资运输的第1 d，只考虑旅行时间的模型求得的最小时路径是路径 3;而本文提出的模型求得的结果是:当决策权重为 λ1(t)=0.9，λ2(t)=0.1时，路径3为最优路径，当决策权重为λ1(t)=0.2，λ2(t)=0.8 时，路径1 为最优。与现有应急物流运输路径选择研究中使用的静态模型或只考虑旅行时间变化的动态模型相比，本文提出的模型更符合实际情况，具有更好的实用价值。

(3)在实际应用中，可以通过建立数据库、应用计算机编程技术将该模型程序化，以实现问题分析和计算的自动化。对于复杂、巨大的运输网络，可以应用计算机网路分布式并行计算技术实现问题的求解，以保证决策的时效性，为管理者提供决策支持。

［1］王 丰，姜玉宏，王 进.应急物流［M］.北京:中国物资出版社，2007.

WANG Feng，JIANG Yu-hong，WANG Jin.Emergency logistics［M］.Beijing:China Logistics Publishing House，2007.

［2］郑 斌，马祖军，方 涛.应急物流系统中的模糊多目标定位－路径问题［J］.系统工程，2009，27(8):21－25.

ZHENG Bin，MA Zu-jun，FANG Tao.Fuzzy multi－ objective location－routing problem in emergency logistics systems［J］.Systems Engineering，2009，27(8):21 －25.

［3］李博文，余 博，杨晓明.基于模糊神经网络的应急物流最优路径选择［J］.物流技术，2009，28(12):162 －163.

LI Bo-wen，YU Bo，YANG Xiao-ming.How to select the optimal route for emergency logistics based on fuzzy neural network［J］.Logistics Technology，2009，28(12):162 －163.

［4］佟常青，王景国，陈博文.军队应急物资配送备选路径优化多目标规划模型研究［J］.物流技术，2010(2):206－208.

TONG Chang-qing，WANG Jing-guo，CHEN Bo-wen.A multi－objective programming model of routing optimization for military emergency material distribution［J］.Logistics Technology，2010，(2):206 －208.

［5］Sung K，Bell M，Seong M，et al.Shortest path in a network with time － dependent flow speeds［J］.European Journal of Operational Research，2000，121(1):32 －39.

［6］ Davies C，Lingras P.Genetic algorithms for rerouting shortest paths in dynamic and stochastic networks［J］.European journal of operational research，2003，144(1):27－38.

［7］Cai X，Kloks T，Wong C K.Time－varying shortest path algorithm for problems with constraints［J］.Networks，1997，29(3):141 －150.

［8］Miller－hooks E，Mahmassani H.Least possible time paths in stochastic，time － varying networks［J］.Computers and Operations Research，1998，25(12):1107－1125.

［9］Miller－ hooks E，Mahmassani H.Least expected time paths in stochastic，time－varying transportation networks［J］.Transportation Science，2000，34(2):198 －215.

［10］Miller－hooks E，Mahmassani H.Path comparisons for a priori and time－adaptive decisions in stochastic，time－ varying networks［J］.European Journal of Operational Research，2003，146:67 －82.

［11］魏 航.时变条件下有害物品运输路径选择研究［D］.成都:西南交通大学，2006.

WEI Hang.Routing for hazardous materials transportation with time－varying［D］.Chengdu:Southwest Jiaotong University，2006.

［12］海 军.战区联勤配送运输路径优化问题研究［D］.北京:清华大学，2008.

HAI Jun.Research on the distribution transport path optimization of joint logistics in the theater of operations［D］.Beijing:Tsinghua University，2008.

［13］谭国真，高 文.时间依赖的网络中最小时间路径算法［J］.计算机学报，2002(2):165－172.

TAN Guo-zhen，GAO Wen.Shortest path algorithm in time － dependent networks［J］.Chinese Journal of Computers，2002(2):165 －172.

The routing problem for emergency logistics considering the reliability and time－varying in the earthquake disasters

CAI Jian-ming1，LI Xia-miao1，YANG Guang-hua2

(1.School of Traffic＆ Transportation Engineering，Central South University，Changsha 410075，China;2.Department of Logistics Management，Hunan Communication Polytechnic College，Changsha 410004，China)

Timeliness and reliability are the main evaluation indexes when the transportation routes for emergency logistics are selected under earthquake disasters.Considering the time－varying characteristics of the transportation networks in earthquake disasters，the time－varying calculation method of the travel time on the paths for emergency logistics transportation，and the time－varying reliability of the transportation networks were analyzed.By the dimensionless evaluation indexes，the multi－objective decision－making model for the prediction and evaluation of emergency logistics transportation route was proposed.Finally，a simulation example demonstrates that the proposed method is effective and applicable.

emergency logistics;transportation route;time－varying;reliability;earthquake disaster

F252

A

1672－7029(2011)05－0101－06

2011－05－12

国家自然科学基金资助项目(71071165)

蔡鉴明(1964－)，男，湖南长沙人，高级实验师，博士，从事物流系统与供应链管理、计算机应用技术和交通运输规划与管理的研究