基于模糊不確定需求條件下疏散計(jì)劃優(yōu)化方法的研究

李　峰,曾賽峰,張益星,高德翔

(湖南工程學(xué)院 計(jì)算機(jī)與通信學(xué)院，湘潭 411104 )

?

基于模糊不確定需求條件下疏散計(jì)劃優(yōu)化方法的研究

李峰,曾賽峰,張益星,高德翔

(湖南工程學(xué)院 計(jì)算機(jī)與通信學(xué)院，湘潭 411104 )

疏散計(jì)劃是災(zāi)害管理的一項(xiàng)重要的內(nèi)容.針對(duì)疏散計(jì)劃固有的不確定特性,提出了一種公共交通疏散路線設(shè)計(jì).設(shè)計(jì)中，每個(gè)受災(zāi)點(diǎn)災(zāi)民的需求用模糊數(shù)據(jù)表示，車輛線路的分配用置信指數(shù)表示，通過(guò)實(shí)驗(yàn)分析和討論了最后結(jié)果中不確定因素對(duì)疏散計(jì)劃的不利影響，評(píng)估了置信偏好指數(shù)對(duì)設(shè)置線路的影響，設(shè)計(jì)了解決疏散計(jì)劃的最佳方案，并獲取了最佳參數(shù).

疏散計(jì)劃；模糊不確定需求；優(yōu)化；路線設(shè)計(jì)

0　引　言

最近發(fā)生在城市地區(qū)的災(zāi)害(如地震、洪水、颶風(fēng)、化學(xué)品泄漏、核事故)凸顯應(yīng)急管理的重要性.雖然災(zāi)難發(fā)生的概率相對(duì)較低，但其悲劇性的后果使得人們?cè)谒鼈儼l(fā)生之前就應(yīng)該有所防備.

緊急疏散是一個(gè)重大的戰(zhàn)略性應(yīng)急管理計(jì)劃.通過(guò)緊急疏散人們從危險(xiǎn)區(qū)域移到的安全區(qū)域，減少了損失.在疏散行動(dòng)中，一些人可能會(huì)使用私家車自行疏散，但是還有一些人沒(méi)有私家車是不能自行疏散的.這些人群主要包括青少年，老人、殘疾人、游客或低收入居民，他們只得依靠公共交通疏散.

公共交通系統(tǒng)在提高疏散效率中發(fā)揮著至關(guān)重要的作用[1,2,3,4].Naghawi和Wolshon[5]認(rèn)為公交巴士能夠增加疏散人口的總數(shù)并最小限度地減少對(duì)疏散路線交通的影響.陳、周[11]認(rèn)為有條理的逃生時(shí)間安排可大大提高疏散效率.因此疏散計(jì)劃應(yīng)該計(jì)劃周全，以提高應(yīng)急管理水平.

疏散規(guī)劃是復(fù)雜的而且具有挑戰(zhàn)性的問(wèn)題，因?yàn)樵诰o急情況下留給決策者的信息是不確定性的.在使用公共交通進(jìn)行疏散時(shí)，疏散人員的信息和他們的及時(shí)位置、疏散車輛和交通網(wǎng)絡(luò)都有可能不確定、不完整甚至錯(cuò)誤.車輛的數(shù)量，承載力量和位置也可能是不確定的.交通網(wǎng)絡(luò)中有限的接入容量、行車時(shí)間以及有限的網(wǎng)絡(luò)接入等等造成網(wǎng)絡(luò)的不確定性.此外，如圖1所示的災(zāi)難發(fā)生時(shí)間和其嚴(yán)重性的不可預(yù)測(cè)性也是疏散計(jì)劃的不確定性因素.

絕大多數(shù)疏散計(jì)劃很可能忽視不確定性因素.而一個(gè)實(shí)際疏散操作是難以完全遵循預(yù)定的計(jì)劃的.因此，最優(yōu)疏散計(jì)劃應(yīng)該考慮不確定性因素以保證較高的執(zhí)行概效率.

圖1　疏散計(jì)劃中公共交通的不確定因素

本文提出了一種在城市地區(qū)使用公共交通工具來(lái)疏散車輛的問(wèn)題(EVRP).在此問(wèn)題中疏散需求是不確定的.在這里，在每個(gè)疏散點(diǎn)的需求(疏散)用模糊變量表示并用模糊置信理論來(lái)處理這種不確定性.文中使用隨機(jī)模擬方法評(píng)估解決方案.使用模糊置信理論對(duì)行車路線分配尚屬首次.

1　模糊置信理論

現(xiàn)實(shí)中許多模糊現(xiàn)象不能明確描述.Zadeh[7]引入了模糊集合的數(shù)學(xué)理論，通過(guò)其中的元素能夠更好地處理不確定現(xiàn)象.Zadeh使得處理模糊事件變?yōu)榭赡?Liu[6]發(fā)現(xiàn)了置信理論，是研究不確定現(xiàn)象一個(gè)分支.其中的可能性，必然性和可信度可以描述如下.

定義1：讓?duì)瘸蔀榉强占?P(θ)就是其概率集合.其中的每一個(gè)元素稱為事件，?是空集.對(duì)于每一個(gè)A屬于P(θ)可以得到非負(fù)數(shù)Pos(A)，其表示事件A發(fā)生的概率(公式1).

(1)

三元集合(θ，P(θ)，Pos)稱為概率空間，函數(shù)Pos是概率衡量函數(shù).

定義2：定義三元集合(θ，P(θ)，Pos)為概率空間，A是P(θ)的集合.A必定發(fā)生概率由公式2定義.其中AC是A的互補(bǔ)事件.

Nec{A}=1-Pos{AC}

(2)

定義3：定義三元集合(θ，P(θ)，Pos)為概率空間，A是P(θ)的集合.則A的可信度函數(shù)可以描述如下：

(3)

(4)

正如所描述的，模糊事件的可信度等于其可能發(fā)生和必定發(fā)生的平均值.假如可信度為1，模糊事件一定發(fā)生；若為0，則一定不發(fā)生.

2　詳細(xì)方法

這章闡述了技術(shù)的細(xì)節(jié).在2.1、2.2 、2.3節(jié)分別闡述了EVRP模型.該模型描述了模糊置信理論并用GA[8]模型解決EVRP問(wèn)題.

2.1模型描述

本文模擬了城市公共交通疏散計(jì)劃.計(jì)劃中人們?cè)诤蜍噮^(qū)等待公共車輛的到來(lái).這里傳統(tǒng)的公交車站被設(shè)置為候車區(qū).受災(zāi)群眾被轉(zhuǎn)運(yùn)到附近的避難所.假設(shè)有充足的車輛提供輸送.

疏散問(wèn)題常建模在行車線路問(wèn)題上.在經(jīng)典版本的VRP[9]，問(wèn)題的目的是設(shè)計(jì)出一整套線路，如圖2所示車輛按照行車線路能夠從停車點(diǎn)穿過(guò)所有受災(zāi)點(diǎn)提供服務(wù)，最后重返停車點(diǎn).線路設(shè)計(jì)要求耗費(fèi)最少.這里的耗費(fèi)用行車距離和行車時(shí)間衡量.

圖2　經(jīng)典車輛行車線路(VRP)

本文中VRP被擴(kuò)展到EVRP.在EVRP中，每一部車從停車點(diǎn)開(kāi)始穿過(guò)每個(gè)受災(zāi)點(diǎn)，運(yùn)送災(zāi)民，當(dāng)車滿了會(huì)疏散到最近的避難所，如圖3所示.這里災(zāi)民點(diǎn)的位置設(shè)計(jì)應(yīng)盡量使行車花費(fèi)時(shí)間最少.這樣可以減少救援時(shí)間.整個(gè)救援時(shí)間由運(yùn)輸網(wǎng)絡(luò)模型計(jì)算.

圖3　疏散車輛路徑問(wèn)題(EVRP)

在EVRP中假定車輛都有相同的承載量，當(dāng)它們開(kāi)始出發(fā)時(shí)都是空車.

EVRP的數(shù)學(xué)公式描述如下.問(wèn)題用圖描述.在圖中，N和E分別表示邊和節(jié)點(diǎn).

節(jié)點(diǎn)是停車點(diǎn)、受災(zāi)點(diǎn)和避難所的集合.邊是在節(jié)點(diǎn)和運(yùn)送網(wǎng)絡(luò)之間的最短路徑.在接下來(lái)的數(shù)學(xué)描述中，我們用到了節(jié)點(diǎn)的子集合.為了便于理解，變量的注釋在圖4給出.

圖4各變量含義

2.2EVRP模糊置信理論

為了處理逃生過(guò)程中的不確定性，一個(gè)三維模糊變量被用來(lái)評(píng)估受災(zāi)點(diǎn)的災(zāi)民人數(shù).

防災(zāi)抗災(zāi)指揮人員可以憑借他們的經(jīng)驗(yàn)、直覺(jué)或歷史數(shù)據(jù)估計(jì)出受災(zāi)人數(shù)不會(huì)少于e1或大于e3.e2介于兩者之間，可以人為評(píng)估如圖5所示.

圖5　用來(lái)評(píng)估災(zāi)民數(shù)量的三維模糊變量

根據(jù)基本定義模糊變量E發(fā)生的可能性、必然性和可信度可以描述為公式(5)-(7).

(5)

(6)

(7)

救災(zāi)時(shí)車輛是否能順利從一個(gè)受災(zāi)點(diǎn)行走到另一個(gè)在于它的承載能力和災(zāi)民的數(shù)量.若車輛的承載力大于等于下一個(gè)受災(zāi)點(diǎn)的災(zāi)民.該車輛可以根據(jù)其預(yù)設(shè)路徑駛向受災(zāi)點(diǎn)運(yùn)送災(zāi)民.否則其應(yīng)該駛離到附近避難所.

若災(zāi)民數(shù)量確定，容易決定車輛是駛向下一個(gè)受災(zāi)點(diǎn)還是駛離到附近避難所.但是，當(dāng)災(zāi)民人數(shù)變量用三維模糊變量描述時(shí)，救災(zāi)的決策就會(huì)很復(fù)雜.下一個(gè)受災(zāi)點(diǎn)的災(zāi)民數(shù)量比車輛的承載量相比越少，車輛駛向下一個(gè)受災(zāi)點(diǎn)的可能性也就越大.

在駛離第m個(gè)受災(zāi)點(diǎn)后車輛k的承載能力可以描述如公式(8).

(8)

此處C是車輛的初始承載能力，ei表示在受災(zāi)點(diǎn)i的災(zāi)民數(shù)量.

(9)

根據(jù)公式(7)-(9)，衡量車輛在下一個(gè)運(yùn)點(diǎn)的承載量可以描述為公式如下.

Cr的值表示車輛駛向下一個(gè)節(jié)點(diǎn)的概率.當(dāng)其值1,表示車輛應(yīng)該駛向節(jié)點(diǎn)，若為0則車輛不能駛向下一個(gè)受災(zāi)點(diǎn)而應(yīng)該駛離到附近避難所.

若基于Cr作決定，應(yīng)該考慮Cr的值.若Cr>-Cr，車輛應(yīng)該駛向?yàn)?zāi)區(qū)，低值Cr表示可以盡可能使用車輛的承載力，但也很可能表示到達(dá)下個(gè)災(zāi)區(qū)時(shí)車輛無(wú)法承載該災(zāi)區(qū)所有災(zāi)民.

而高值Cr可以通過(guò)大量地增加路線的數(shù)量減少失敗的概率.

2.3Cr參數(shù)的優(yōu)化

逃生路徑可以基于難民的數(shù)量模糊估計(jì)而設(shè)計(jì).實(shí)際中車輛按照計(jì)劃線路行駛，但承載的是實(shí)際的難民人數(shù).

實(shí)際中若因?yàn)檐囕v有限的承載力而不能走遍所有受災(zāi)區(qū)時(shí)，它應(yīng)該駛離到最近的避難所，放下車上所有災(zāi)民，重新回到受災(zāi)區(qū)運(yùn)送災(zāi)民.

如圖6所示，車輛由于運(yùn)送的失敗，不得不占用額外的運(yùn)送時(shí)間，從而增加了總時(shí)間的開(kāi)銷.

圖6　逃生路徑狀況圖

Cr的值極大地影響了失敗的次數(shù)和額外運(yùn)送時(shí)間.因此我們應(yīng)該用最少的運(yùn)送時(shí)間來(lái)決策逃生計(jì)劃.

為了選擇一個(gè)最優(yōu)參數(shù)，本文用在0～1之間變化的Cr值來(lái)測(cè)試EVRP.然后對(duì)所有生成的路徑進(jìn)行評(píng)估.首先每個(gè)受災(zāi)點(diǎn)確切的災(zāi)民數(shù)量應(yīng)該知道.但實(shí)際上我們只知道模糊數(shù)量.為了解決這個(gè)問(wèn)題，我們引入了隨機(jī)仿真方法來(lái)模擬每一個(gè)受災(zāi)點(diǎn)確切的災(zāi)民數(shù)量.

對(duì)每一個(gè)受災(zāi)點(diǎn)i,我們?cè)趀i1和ei2之間取值d并以此計(jì)算模糊成員函數(shù).因此產(chǎn)生隨機(jī)變量r.當(dāng)r

在仿真了災(zāi)民實(shí)際數(shù)量后，通過(guò)比較每個(gè)受災(zāi)點(diǎn)的災(zāi)民的累加數(shù)量和車輛的承載能力可以計(jì)算出額外時(shí)間開(kāi)銷.最后，由Cr值計(jì)算出整個(gè)運(yùn)輸時(shí)間.

隨機(jī)仿真逃生路線可以重復(fù)實(shí)驗(yàn)M次.計(jì)算出結(jié)果的平均值來(lái)確定相應(yīng)指數(shù)Cr.

2.4經(jīng)典解決方案

算法中每一個(gè)完全方案都由一串?dāng)?shù)字編碼.每一個(gè)數(shù)字表示一個(gè)受災(zāi)點(diǎn).插入虛設(shè)的零值表示每條獨(dú)立的行車路徑.例如 圖7表示能同時(shí)處理4輛車和10個(gè)受災(zāi)點(diǎn)的方法.每一條行車路徑從發(fā)車點(diǎn)開(kāi)始到最近的避難所結(jié)束.

每種方案都需要簡(jiǎn)單的定位.這種定位不包括車輛行進(jìn)路線的預(yù)先規(guī)劃，而且由虛設(shè)的零值分割.

圖7　經(jīng)典方案

2.5初始化人口

初始化人口的數(shù)量就是方案中PopSize值.

3　Taguchi試驗(yàn)設(shè)計(jì)

Taguchi用健壯參數(shù)設(shè)置方法優(yōu)化了GA模型的參數(shù)[10].Taguchi實(shí)驗(yàn)中的質(zhì)量驅(qū)動(dòng)方法對(duì)優(yōu)化線路設(shè)計(jì)的性能、質(zhì)量、耗費(fèi)不失是一種高效系統(tǒng)的方法.

設(shè)計(jì)算法參數(shù)也就是設(shè)計(jì)不同優(yōu)化級(jí)別的參數(shù).因此算法對(duì)于外部干擾很健壯.但是通過(guò)實(shí)驗(yàn)確定微小的參數(shù)耗費(fèi)巨大.Taguchi實(shí)驗(yàn)可以減少實(shí)驗(yàn)的次數(shù)，獲得近似的優(yōu)化參數(shù)集合.實(shí)驗(yàn)簡(jiǎn)化了數(shù)組，重點(diǎn)研究在少量試驗(yàn)中產(chǎn)生的大量參數(shù).實(shí)驗(yàn)提供了信噪比來(lái)衡量算法質(zhì)量并確定優(yōu)化參數(shù).

1 setp//災(zāi)民點(diǎn)數(shù)量

C//車輛承載力，Cr*//可信指數(shù)

2X←Smax

3k,i=1

4Vehicle(1)←X1

6Whilei

10ifCr≥Cr*do

11Vehicle(k)←Xi+1

12Else

13k=k+1

14Vehicle(k)←Xi+1

16EndIf

17i=i+1

18EndWhile

圖8構(gòu)建函數(shù)的過(guò)程

簡(jiǎn)而言之，信噪比就是平均信號(hào)和標(biāo)準(zhǔn)信號(hào)的比例.信噪比的標(biāo)準(zhǔn)不同，但表示方式一致.信噪比越大越好.

3.1選擇參數(shù)和適合級(jí)別

GA參數(shù)包括：繁殖、種群、突變、雜交，這些都極大影響了算法的健壯性.根據(jù)作者經(jīng)驗(yàn)和相關(guān)文獻(xiàn)類似問(wèn)題，對(duì)于每個(gè)參數(shù)都能有3種級(jí)別.如表1所示.

表1　GA參數(shù)的級(jí)別

3.2選擇合適的正交矩陣

應(yīng)該做的實(shí)驗(yàn)數(shù)量接近于LP，這里L(fēng)和P分別表示級(jí)別和參數(shù).實(shí)驗(yàn)需要重復(fù)81次才能獲得GA參數(shù)，這樣既費(fèi)時(shí)又費(fèi)錢.因此，Taguchi方法轉(zhuǎn)而尋找合適的正交矩陣來(lái)解決這個(gè)問(wèn)題.據(jù)文獻(xiàn)[1]合適的正交矩陣由九個(gè)參數(shù)構(gòu)成，如表2所示.

表2　正交矩陣

3.3運(yùn)行實(shí)驗(yàn)

Taguchi實(shí)驗(yàn)參數(shù)L9在表2給出.GA在裝有MATLAB的戴爾個(gè)人電腦下運(yùn)行.結(jié)果用相對(duì)偏移百分比(RPD)來(lái)衡量.RPD是平均值，可以縮小結(jié)果取值范圍.

4　試驗(yàn)結(jié)果與分析

RPDS在相應(yīng)參數(shù)下比例的平均值在圖9中表示.考慮RPD的在不同參數(shù)下的變化，遺傳代和種群對(duì)于計(jì)算結(jié)果有很大的影響.

RPD越小，就越接近最佳算法.在此基礎(chǔ)上每個(gè)優(yōu)化參數(shù)在表3中給出.

表3　GA參數(shù)的優(yōu)化級(jí)別

5　結(jié)果和探討

我們使用了優(yōu)化后的GA.參數(shù)Cr在0～1之間變化，每次變化步長(zhǎng)為0.05.對(duì)于每一個(gè)Cr值，GA都運(yùn)行三遍以獲得總的行車時(shí)間和逃生時(shí)間.為了對(duì)計(jì)劃路線進(jìn)行評(píng)估，對(duì)額外行車時(shí)間隨機(jī)仿真重復(fù)計(jì)算了20遍.計(jì)劃總行車時(shí)間由災(zāi)民的模糊數(shù)量決定；額外行車時(shí)間由隨機(jī)仿真程序獲得的災(zāi)民數(shù)量決定.最終總行車時(shí)間=計(jì)劃時(shí)間+額外時(shí)間.

圖9　在不同參數(shù)下GA對(duì)應(yīng)的RPDs均值

當(dāng)分配偏好指數(shù)Cr變化時(shí)，圖10表示PTTT、 ATT和FTTT隨之變化的曲線圖.根據(jù)圖10，PTTT隨著Cr值增大而增大，同時(shí)ATT降低.

圖10　行車時(shí)間隨Cr*變量改變曲線

Cr值越低，ATT值越高，PTTT值越低.相反Cr值越高，ATT值越低，PTTT值越高.如圖10所示，Cr小于0.35時(shí)PTTT的增長(zhǎng)率與ATT的下降率成反比.但是，當(dāng)Cr大于0.35，PTTT的增長(zhǎng)率超過(guò)ATT的下降率.因此當(dāng)Cr從0.35增長(zhǎng)到1時(shí)FTTT也隨著增長(zhǎng).

[1] M.A . Schwartz, T.A . Litman, Evacuation Station: the Use of Public Transportation in Emergency Management Planning[J]. Inst. Transp. Eng., 2008, 78(1):69-73.

[2] Transporatation Research Board (TRB). The Role of Transit in Emergency Evacuation: Special report 294, Committee on the Role of Public Transportation in Emergency Evacuation[R]. Washington, DC, 2008.

[3] F. Sayyady, S. Ek sioglu. Optimizing the Use of Public Transit System During no Notice Evacuation of Urban Areas, Comput[J]. Ind. Eng. 2012, 59: 488-495.

[4] E.I. Kaisar, L. Hess, A . Benazir. An Emergency Evacuation Planning Model for Special Needs Populations Using Public Transit Systems[J]. Public Transp, 2012, 15(2):45-68.

[5] H. Naghawi, B. Wolshon. Performance of Traffic Networks During Multimodal Evacuations: Simulation-Based Assessment[J]. Nat. Hazard. Rev, 2012, 13(3): 196-204.

[6] B. Liu. A Survey of Credibility Theory, Fuzzy Optim[J]. Decis. Mak, 2014(5): 387-408.

[7] L.A . Zadeh. Fuzzy Sets, Inf. Control[J]. 1965, 8: 338-353.

[8] G. Taguchi. Introduction to Quality Engineering, Asian Product[R]. Organ./UNIPUBWhite Plains, 2013.

[9] G.B. Dantzig, J.H. Ramser. The Truck Dispatching Problem[J]. Manag. Sci., 2012, 6(1): 80-91.

[10] G. Taguchi. Introduction to Quality Engineering, Asian Product[R]. Organ./UNIPUB,White Plains, 2011.

[11] C. Chen, C. Chou. Modeling and Performance Assessment of a Transit-Based Evacuation Plan Within A Contra-Flow Simulation Environment, Transp[J]. Res. Rec.: J. Transp. Res. Board, 2009(2): 40-50.

Study on Optimization of an Evacuation Plan with Uncertain Demands

LI Feng, ZENG Sai-feng, ZHANG Yi-xing, GAO De-xiang

(College of Computer and Communication,Hunan Institute of Engineering, Xiangtan 411104， China)

Evacuation planning is an important activity in disaster management. Due to the sudden occurrence of disasters, evacuation should be preplanned. It is necessary for evacuation plan to be as close as possible to a real evacuation operation. However, evacuation planning is a challenge because of inherent uncertainty in required information. One important source of uncertainty in evacuation is the uncertainty in evacuation demands. This paper presents an evacuation vehicle routing problem to design evacuation routes for public vehicles. In this problem, demand (number of evacuees) at each pick-up point is introduced as a fuzzy number and the assignment of the pick-up points to the vehicle routes happens based on a credibility preference index. A genetic algorithm based on fuzzy credibility theory is designed to optimize the problem. The optimum parameter set for genetic algorithm is obtained by Taguchi experimental design. The presented problem and algorithm are applied to a part of Tehran transportation network. The impact of credibility preference index on the achieved solutions is evaluated and its best value is determined for the case study. Moreover, different tests are implemented to analyze and discuss the influence of uncertainty level on the final results.

evacuation planning；uncertainty level；vehicle routes;optimization

2016-04-08

湖南工程學(xué)院青年重點(diǎn)項(xiàng)目(XJ1504)；湖南工程學(xué)院校級(jí)大學(xué)生創(chuàng)新項(xiàng)目[校辦字83號(hào)文件47號(hào)].

李峰(1975-)，男，碩士，講師,研究方向：計(jì)算機(jī)應(yīng)用技術(shù).

U491.1

A

1671-119X(2016)03-0049-07