具有模糊抢修时间的震后道路抢修排程研究

霍建顺，薛 梅，李爱庆

（西南交通大学 经济管理学院，成都 610031）

0 引言

强震对于交通网络的影响非常巨大，会造成地面塌陷、龟裂，山体滑坡掩埋道路，桥梁的垮塌等等，这些都使得救援工作受阻。在5.12汶川地震中，多次由于道路受阻使得对汶川救援工作进展缓慢。由于地形复杂，强余震不断、恶劣天气、次生灾害等，又使得道路抢修工作进行地极为艰难。再者震后应急期，紧急救援资源(营救设备、营救车辆、救护车和相关营救人员、通讯电力抢修人员等)通常都很有限，因而如何最有效地利用这些有限的资源，尽快地将道路抢通变得非常重要。实际中，应急阶段对道路抢修的排程计划通常根据决策者的经验进行安排，没有考虑整个系统的目标，所做方案在理论上只是可行解，在实际运作时这些方案的实施效果可能会非常差。目前对震后道路灾点的抢修排程问题，国内外学者有了一定的研究。Cheng-Min Feng[1]将应急期界定为灾后的72小时，并对高速公路的道路灾点抢修排程进行了研究。Hitoshi FURUTA et al[2]则考虑了震后不确定性环境，如：余震，火灾，天气等因素，应用遗传算法得到一个具有鲁棒性的道路恢复排程的决策支持系统。Shangyao Yan et al[3,4]提出一种时空网络模型来解决震后道路抢修排程的模型，并进一步地结合赈灾物流情形进行讨论。

本文考虑到强震后情况的复杂性，道路抢修不确定性很高，拟将道路灾点的抢修时间设为三角模糊变量，使道路灾点抢通时间满足一定的置信度水平，并用机会约束规划建构数学模型，针对5.12地震后四川省什邡市的道路灾点数据进行求解，并进行分析。

1 模型及算法

机会约束规划是由Charnes和cooper提出的第二类随机规划，其显著特点是约束条件至少以一定的置信水平成立。Baoding Liu et al[5,6]提出了模糊的机会约束规划，并在文献[7]中针对模糊决策系统构建了minmax的机会约束模型。Yongshuang Zheng et al[8]针对旅行时间为模糊变量的车辆路径问题构建了一个机会约束规划的模型，在有时间窗的情形下，最小化行驶距离，并设计了一种混合算法来求解此模糊车辆路径问题。张建勇等[9]通过引入决策者主观偏好值的概念，建立具有模糊特征的车辆路径问题的模糊机会规划模型，并设计了混合遗传算法，在最小化总行驶距离的目标下进行了求解。

在强震应急期，政府交通主管部门根据收集到的道路受损情况，派出抢修工作队进行道路抢修，对道路灾点抢通的界定为至少有一条车道可通过即可。根据实际情况，本文对有关情形作如下假设：

（1）每个道路灾点仅有一个工作队进行抢修；

（2）各个工作队的工作能力相同；

（3）在交通网络中，工作队的车辆优先或专用道路；

（4）工作队已掌握所有道路灾点信息。

因为在震后应急期内人民的生命依然受到直接威胁，为了尽快的开展救援工作，必须使得道路尽快抢通，因此在应急阶段考虑的目标为最小抢修时间。在整个交通网路图中，我们将有关符号进行如下说明：

i=0：工作站；

i=1,2,3,…,n：灾点；

k=1,2,3,…,m：工作队；

Lij：从灾点i到j的旅行距离；

Tij：从点i出发至灾点j的时间，由于旅行时间相对于维修时间非常小，故将旅行时间忽略。将Tij表示为从点i到点j的模糊维修时间；

[ai,bi]：维修 i点的时间窗，ai，bi分别为 i开始的时间和结束的时间。

我们用x，y和t三个决策变量刻画运行计划，其中：

x=(x1,x2,…,xn)：整数决策变量，表示n个不同的灾点，对于所有的 i≠j，有 1≤xi≤n 和 xi≠xj，i,j=1,2,…,n。 实际上它是序列{x1,x2,…,xn}的一个重排。

y=(y1,y2,…,ym-1)：整数决策变量，y0≡0≤y1≤y2≤…≤ym-1。

t=(t1,t2,…,tm)：tk代表车辆k从工作站出发的时间，k=1,2,…,m。因工作队投入抢修工作有序，其出发时间可能有差别。本文假定工作队同时被指派，仅仅指派时间不全相同的情况，考虑在满足道路抢修的时间窗下，各队应在何时出发。

注意到运行计划可以由x，y和t按下面的方式完全确定。对于每个k(1≤k≤m)，如果yk=yk-1，表示车辆k没有运行；如果yk＞yk-1，则表示车辆k已运行，并且离开配送中心的时间为tk，它的行驶路线为

这种方法比较直观，且只有n+2m-1个决策变量。另外，注意到以上定义的决策变量x，y和t保证了：（1）每个维修队最多被派遣一次；（2）所有的路线都以工作站为出发和结束点；（3）每个灾点有且仅有一个维修队进行维修；（4）路线中没有子圈。

设fi(x,y,t)为维修队抵达灾点i处的时间函数，它由决策向量x，y和t决定，i=1,2,…,n。由于当维修队到达灾点时候，应该立即进行维修，以争取最短时间内将道路抢通。如果维修队 k 被派遣维修（即 yk＞yk-1），1≤k≤m，则对任何 2≤j≤ykyk-1，有

其中∧表示在两者中取小（即抢修队如果早到，立即投入抢修），由于Tij是模糊的，因此抵达时间 fi(x,y,t)，也是模糊变量，并且完全由上面两式决定。

设g(x,y)是所有维修队的旅行距离，有

其中

决策者根据实际情况给出灾点i以置信水平βi在其指定的时间窗口[ai，bi]内维修完成，于是 Cr{fi(x,y,t)∈[ai,bi]}≥βi,i=1,2,…,n。

可以应用痕迹检验方法检验油漆附着物，在发生多车碰撞交通事故的情况下，可以对同一部位印压、刮擦痕上的油漆附着物进行检验，从而明确碰撞顺序。具体而言，交通事故往往发生于瞬间，车辆相互作用力较大，车表面在外力的相互作用下容易出现破损、变形等情况。车辆表面往往会具有装饰、保护功能的漆膜，因外力作用可能发生脱落、破损等状况，遗落在其它相关车辆表面。基于此，当发生多车碰撞的事故时，以着力点为中心，进行痕迹检验，对油漆附着情况进行分析，即最上层所附着的油漆，为车辆最后碰撞所留，依次展开分析，有助于交通事故处理人员判断车辆碰撞顺序。

最后给出机会约束规划模型

本文的利用随机模拟和遗传算法融合而成的混合智能算法进行求解，见Yongshuang Zheng[9]，刘保碇等[10]文中的算法描述。

2 案例

本文收集5.12汶川地震后四川省什邡市的有关数据，对什邡市的震后道路抢修排程问题进行研究。什邡市民政局提供的5.12汶川地震受灾人口及其受灾程度，如表1。

根据什邡市交通局提供的道路的受损情况，对道路灾点进行整理如表2，其中连接重灾区的道路灾点以“*”表示。

由于什邡市的重灾区很多，连接重灾区的道路灾点很多，假定工作队每小时可抢修的受灾路段长度为1km。抢修时间由前置灾点的抢修时间加前置灾点中最大的抢修时间表示。因震后道路抢修不确定性因素很多，本文将道路灾点的抢修时间用三角模糊数表示，抢修时间列表略。

各灾点由于连接的灾区受损程度不同，因此在设定时间窗时，将结合灾区情况予以考虑。本文将连接重灾区的道路灾点抢通须在60小时内，连接一般灾区的道路灾点须在72小时内抢通。将地震发生时点定义为0时，道路灾点的抢修须在72小时内完成，以便及时地对重灾区民众进行救助。各灾点时间窗如表3。

在应急阶段，道路抢修的目标是在最短时间内抢通道路。因每个道路灾点都需要抢修，因此道路灾点抢修时间不再考虑，仅考虑旅行时间，旅行时间又依赖于旅行距离，所以将旅行时间最小化转化为旅行距离最小化，各灾点之间的距离见表4。

表1 什邡市“5.12”地震灾害受灾范围表

表2 道路灾点分布情况

续表

表3 时间窗

所有的工作队从什邡市出发进行抢修，本文设定有4个工作队，在0.9的置信水平下抢修灾点。本文使用混合算法，用vc++6.0编程求解，其结果如下

工作队1：什邡市→14→什邡市

工作队 2： 什邡市→12→2→7→6→8→9→10→3→5→17→13→15→4→什邡市

工作队3：什邡市→11→什邡市

工作队4：什邡市→1→16→什邡市

此时的置信度为 Cr{fi(x，y，t)∈[ai，bi]，i=1，2， …，17}=0.985，四队最迟分别于震后的4.9小时，3.0小时，1.2小时和3.1小时出发。从结果可以看出工作队2承担的工作量非常重，也说明在工作队2的工作线路在满足整个时间窗非常重要，这也符合什邡市交通网路“一纵两横”的特点，在实际中则需加强工作队2的工作能力，如可以协调工作队1，3，4协助工作队2完成这条工作线路。

在变换工作队数目时，在规定的时间内完成的置信水平0.9的情况下，其置信度水平及总距离改变如表5。

表4

表5

从表中可以看出，随着工作队数目的增加，在时间窗内修通道路灾点的置信水平是增加的，增加的幅度逐渐降低，但工作队行驶的距离也是增加的，其与本文设置的M有关，使得工作队在通过某些灾点时其行驶距离有很大增加。

3 结论

地震应急期内，对交通路网的抢修工作面临的不确定性条件很多，在此种情况下，本文将抢修时间视为模糊变量，在总成本最小化的目标下，采用模糊约束规划的方法构建模型，并使用混合算法对问题进行了求解。

本文仅考虑一个灾点仅被一个工作队抢修的情况，实际中往往是会有多个工作队抢修一个灾点，将此假设条件放松，进而求解该问题是今后应继续讨论的。

[1]Cheng-Min Feng,Tsai-Chu Wang.Highway Emergency Rehabilitation Scheduling in Post-Earthquake 72 Hours[J].Journal of the Eastern Asia Society for Transportation Studies,2003,.5.

[2]Hitoshi Furuta,Ken Ishibashi,Koichiro Nakatsu,Shun Hotta.Optimal Restoration Scheduling of Damaged Networks Under Uncertain Environment by Using Improved Genetic Algorithm[J].Tsinghua Science And Technology,2008,13.

[3]Yan S.,Shih Y L.A Time-Space Network Model for Work Team Scheduling after a Major Disaster[J].Journal of the Chinese Institute of Engineers,2007,30.

[4]Shangyao Yan,Yu-Lin Shih.Optimal Scheduling of Emergency Roadway Repair and Subsequent Relief Distribution[J].Computers&Operations Research,2008.

[5]Baoding Liu,Kakuzo Iwamura.Chance Constrained Programming with Fuzzy Parameters[J].Fuzzy Sets and Systems,1998,94.

[6]Baoding Liu,Kakuzo Iwamura.A Note on Chance Constrained Programming with Fuzzy Coefficients[J].Fuzzy Sets and Systems,1998,100.

[7]Baoding Liu.Minimax Chance Constrained Programming Models for Fuzzy Decision Systems[J].Information Sciences,1998,112.

[8]Yongshuang Zheng,Baoding Liu.Fuzzy Vehicle Routing Model with Credibility Measure and Its Hybrid Intelligent Algorithm[J].Applied Mathematics and Computation，2006,176.

[9]张建勇,李军.模糊车辆路径问题的一种混合遗传算法[J].管理工程学报,2005.

[10]刘保碇，赵瑞清，王纲.不确定规划及应用[M].北京：清华大学出版社，2003.

[11]李军，曾鹦，李妍峰.基于汶川地震的震后交通受损评估研究[J].管理评论，2008,(12).