基于多目標遺傳算法的災(zāi)后可靠路徑選擇

李 清,胡志華

(1. 同濟大學 經(jīng)濟與管理學院,上海200092；2. 上海海事大學 物流研究中心,上海201306)

?

基于多目標遺傳算法的災(zāi)后可靠路徑選擇

李 清1,2,胡志華2

(1. 同濟大學 經(jīng)濟與管理學院,上海200092；2. 上海海事大學 物流研究中心,上海201306)

為了盡快運出災(zāi)民、運進物資,災(zāi)后需要選擇最短的運輸路徑；考慮到災(zāi)害對道路的損毀,安全的路徑是道路選擇中的重要因素,基于災(zāi)后道路的損毀狀況,采用3種方法定義道路可靠性,以最小化路徑長度、最大化路徑可靠性為目標建立雙目標優(yōu)化模型,采用多目標遺傳算法求解.分別求得3種情形下的解,開展2個目標的Pareto分析；分析交叉概率和變異概率對結(jié)果的影響：交叉概率增大,覆蓋范圍波動式變化,理想積波動式下降；變異概率增大,覆蓋范圍波動式變化,理想積緩慢增長后逐漸下降.采用遺傳算法能夠有效地解決最短和最可靠路徑的搜索問題.

最短路問題；多目標遺傳算法；優(yōu)先權(quán)；可靠性

交通網(wǎng)絡(luò)承擔著大量旅客和貨物的運輸任務(wù),對國民經(jīng)濟的發(fā)展起著至關(guān)重要的作用.突發(fā)事件的頻繁發(fā)生不但延誤了整個運輸過程,而且導致道路中斷、坍塌,造成大量經(jīng)濟損失[1].近年來,突發(fā)事件和自然災(zāi)害頻發(fā),交通系統(tǒng)不斷遭受破壞,面臨嚴重挑戰(zhàn).災(zāi)后需要及時將災(zāi)民疏散到安全區(qū)域,也需盡快將救援物資和人員運送到災(zāi)區(qū),道路交通網(wǎng)絡(luò)成為災(zāi)后救援的生命線.一方面,組織者選擇最短的行駛路線,把握救援時間,提高救援效率；另一方面,道路因為災(zāi)害襲擊受到不同程度的損壞,可靠、安全道路的選擇成為運輸時間之外的又一關(guān)鍵議題.在盡可能短的時間內(nèi)進行安全、可靠的運輸是管理者追求的目標.

最短路問題是網(wǎng)絡(luò)設(shè)計優(yōu)化的核心,在實際生活中有廣泛的應(yīng)用背景.Nazemi等[2]根據(jù)神經(jīng)網(wǎng)絡(luò)模型,建立最短路問題的線性規(guī)劃模型,由神經(jīng)網(wǎng)絡(luò)模型的均衡點得到原問題的最優(yōu)解.Festa等[3]簡化了經(jīng)典最短路問題中的時間多項式,提出2種求解策略.針對不完全信息下交通網(wǎng)絡(luò)的最短路徑問題,閆化海等[1]定義了關(guān)鍵邊的概念,應(yīng)用子樹連通算法求解該問題.Amirteimoori[4]從實際問題出發(fā),考慮了路段的多種屬性(多種成本和收益),定義不同道路的相對效率,選擇效率最高的路徑.在突發(fā)事件背景下,對道路可靠性的要求應(yīng)運而生.道路網(wǎng)可靠性是網(wǎng)絡(luò)可靠性在道路交通中的具體應(yīng)用,一些學者采用可靠性方法評價路網(wǎng)的連通可靠性、行程時間可靠性和通行能力可靠性等.Asakura等[5]定義行程時間可靠度函數(shù),并以此反映道路交通網(wǎng)絡(luò)的可靠性,討論特定時間和交通需求水平下O-D(origin-destination)間成功到達的概率.Chen等[6]提出路網(wǎng)通行能力可靠度,以路網(wǎng)通行能力能成功適應(yīng)一定交通需求和提供一定服務(wù)水平的概率來評價網(wǎng)絡(luò)可靠性.

本文以最短路問題為原型,以最小化路徑長度、最大化路徑可靠度為目標,建立雙目標優(yōu)化模型,采用多目標遺傳算法求解.分別得到3種方法定義的道路可靠性下的實驗結(jié)果.

1 問題描述與定義

運輸規(guī)劃、旅行商路線安排和通信系統(tǒng)中的信息傳遞是最短路問題在實際生活中較常見的應(yīng)用,這些問題往往給定2個特定的點(起點和終點),要求以較快、成本較少、較可靠的方式完成運輸任務(wù).可靠性路徑優(yōu)化問題是指：道路網(wǎng)絡(luò)中包含有限數(shù)量的節(jié)點以及連接節(jié)點的弧(道路),存在一個起始點和一個終點.不同節(jié)點之間有道路連接,每條道路的長度和可靠性均不相同.現(xiàn)已知起點和終點的位置,已知節(jié)點間的連接關(guān)系及每條道路的長度和可靠性,求解一條從起點到終點長度最短、且可靠性最高的道路.

1.1 最短路問題求解方法

最短路徑問題是圖論研究中的一個經(jīng)典算法問題,旨在尋找圖(由結(jié)點和路徑組成)中兩結(jié)點之間的最短路徑.Ardakani等[7]采用A*算法研究動態(tài)網(wǎng)絡(luò)中的最短路問題,使用遞減方法減小網(wǎng)絡(luò)規(guī)模,加快問題的優(yōu)化過程.靳凱文等[8]采用蟻群算法解決車載導航系統(tǒng)中的最短路徑搜索問題；Lozano等[9]采用精確算法求解大規(guī)模的有約束最短路問題.Cheng等[10]使用二階錐規(guī)劃求解連續(xù)松弛問題,應(yīng)用分支定界法求解隨機組合問題.以隨機Dijkstra為基礎(chǔ),鄒亮等[11]運用遺傳算法求解動態(tài)路徑誘導系統(tǒng)中的最短路徑問題.Niksirat等[12]研究多重模式交通網(wǎng)絡(luò)中的K最短可行路徑問題,采用元啟發(fā)式算法：貪婪算法模擬退火(GASA)和雙向搜索蟻群算法求解(BACS).

在雙目標優(yōu)化問題方面,Hasuike[13]以最小化總成本、最大化置信區(qū)間變化范圍為目標建立模型.采用模糊目標和聚合函數(shù),考慮決策者在多目標決策中的偏好,利用基于Dijkstra算法的精確算法和基于Lagrange松弛算法的啟發(fā)式算法求解.Chen等[14]采用分段線性函數(shù)估計道路成本中的非線性成本,根據(jù)有效路徑集合更新問題的上界和下界,并從中確定子問題的解.

1.2 可靠性計算方法

對網(wǎng)絡(luò)可靠性的研究一般從持續(xù)性、穩(wěn)健性和有效性3個方面進行分析.持續(xù)性描述路網(wǎng)在隨機因素干擾下的可靠性,穩(wěn)健性指網(wǎng)絡(luò)受到外界破壞后的可靠性,有效性指路網(wǎng)在阻塞情況下滿足最低可接受服務(wù)水平的程度.

Lee等[15]假設(shè)路段通行能力服從正態(tài)分布,路段可靠性由下式計算：

(1)

對于串聯(lián)系統(tǒng)S和并聯(lián)系統(tǒng)P,可靠性分別由下式計算：

(2)

(3)

陳富堅等[16]綜合人、車、路、環(huán)境和管理等因素全面評價路網(wǎng)運營安全狀態(tài),將道路交通系統(tǒng)按車輛數(shù)量和道路特征分成以下4類.UTS：由單車及其行駛的單元路段組成；USTS：由單元路段及其上的交通流組成；STS：由若干個單元路段及其上的交通流組成；NTS：由多條道路的路段交通系統(tǒng)組成.前3類交通系統(tǒng)的可靠性分別如下式所示：

Ruts=Rd·Rv·Rr.

(4)

Rusts=Rd,e·Rv,e·Rr.

(5)

(6)

式中：Rd、Rv、Rr分別為司機、車輛和道路的可靠度.USTS中分別用司機群體特征和路段上車輛群體特征可靠度的期望值表示司機和車輛的可靠度,STS由2個相反交通流的USTS組成.引入貝葉斯模型構(gòu)造NTS的可靠性模型,分別確定人、車輛、道路和外界環(huán)境對道路交通系統(tǒng)可靠度的影響.

在交通網(wǎng)絡(luò)中,每條路徑由若干路段連接而成,侯立文等[17]定義路段的可靠性為一定時間內(nèi)路段上行使的車輛數(shù)小于其通行能力的概率.根據(jù)交通流隨機的特點,用非齊次泊松過程計算每一路段的可靠性,如下：

(7)

(8)

(9)

式中：rij為第i個OD對中第j條路徑的可靠性,n為網(wǎng)絡(luò)中OD對總數(shù),m為第i個OD對中的路徑總數(shù).

1.3 路徑可靠性衡量方法

在災(zāi)害及突發(fā)事件背景下,公路交通系統(tǒng)受到嚴重破壞,道路可靠性與其受破壞程度密切相關(guān).秦軍等[18]選擇損毀類型、損毀規(guī)模、損毀比例3個因子評價道路損毀程度.損毀比例表示評估路段中損毀路程占總路段長度的比例；根據(jù)不同的道路損毀類型進行量化取值,形成受損系數(shù)指標；采用道路受損的絕對長度形成規(guī)模系數(shù)評價指標.

定義路段的可靠性為路段損毀度的倒數(shù),分別用dij、pij、cij、fij表示連接i、j兩點路段的損毀度、損毀比例、受損系數(shù)和規(guī)模系數(shù).本文的路段可靠性定義如下：

(10)

1)最小值法.一條道路能否通行,往往取決于組成該道路的路段中損毀最嚴重的路段的狀況.若道路中損毀最嚴重的路段可以使用,則該條路徑可以保證車輛正常運行；若連接起訖點的路徑中存在毀壞或嚴重破壞的路段,則該條路徑不能使用.基于該定義OD間路徑的可靠度為

最小值法適用于路徑中存在嚴重損壞路段的情況.

2)平均值法.災(zāi)后運輸物資、疏散災(zāi)民時,首先剔除損壞的路段,然后從可以使用的路段中選擇一些連接起訖點.目標是從余下的路段中選擇距離最短且可靠性最高的路段,組成連接起訖點的道路.當路徑中的路段狀態(tài)相似,所受破壞情形相差不大時,采用平均值法估計該條路徑的整體可靠性：

式中：n為道路OD經(jīng)過的路段數(shù)量.

2 模型的建立

(11)

道路的距離通過下式計算：

(12)

道路可靠性可以采用最小值、平均值和串聯(lián)法進行計算,分別如下式所示：

(13)

(14)

(15)

根據(jù)道路可靠性的計算方法,得到[M1]～[M3]三個模型,如下：

(16)

(17)

(18)

3 多目標遺傳算法設(shè)計

遺傳算法模擬生物進化的過程是一種新的全局優(yōu)化搜索算法,簡單通用、魯棒性強、適于并行處理且應(yīng)用范圍廣[11].具體步驟主要如下：編碼——生成初始種群——構(gòu)造適應(yīng)度評估函數(shù)——交叉——變異——選擇——解碼.

遺傳算法通過多方位和全局的搜索方式獲得種群中的解,是解決多目標優(yōu)化問題的良好工具[19].非支配分類遺傳算法(nondominated sorting genetic algorithm, NSGA-II)改進原多目標遺傳算法中的等級程序,根據(jù)帕累托最優(yōu)解劃分種群的等級,分配共享適應(yīng)度.分類個體的適應(yīng)度函數(shù)值維持群體的多樣性,采用隨機剩余比例選擇法.在帕累托前端面中,第一前端面上個體的適應(yīng)度最高,能夠保證較高的復制率.NSGA的性能優(yōu)于多目標遺傳算法(multi-objective genetic algorithm,MOGA)和仿帕累托遺傳算法(Niched Pareto genetic algorithm,NPGA),它對已知區(qū)域有良好的搜索能力和較快的收斂能力.NSGA-II算法的主要步驟如下.

1)生成初始種群P′,隨機生成N′的種群規(guī)模.

2)評估目標函數(shù)值,基于帕累托最優(yōu)分類分配等級,產(chǎn)生子代種群.

3)采用二元錦標賽選擇方法,重組、變異.

4)基于帕累托最優(yōu)分類分配等級,產(chǎn)生非支配向量集,將第一個前端面上的解依次放入下一代,循環(huán)直到確定N′個個體在每個前端面上點與點間的擁擠距離.

5)重復4),直到迭代次數(shù)滿足g(g為一設(shè)定的數(shù),如100、300或500等).

6)選擇較低等級前端面上且不在擁擠距離范圍內(nèi)的點,產(chǎn)生下一代,采用二元錦標賽選擇方法,重組、變異.

3.1 編碼和解碼方法

采用基于優(yōu)先權(quán)的編碼和解碼方法.基因位置上的數(shù)字表示節(jié)點的序列號,基因值表示節(jié)點的優(yōu)先值,優(yōu)先值隨機生成,如圖1所示.首先確定起點,尋找可與起點相連的其他節(jié)點,選擇優(yōu)先值最高的節(jié)點放入路徑.根據(jù)該方法選擇其他節(jié)點,直至構(gòu)成一條連接起訖點的道路.基于優(yōu)先權(quán)的編碼方法具有如下優(yōu)點：通過編碼得到的任意排列都能與一條路徑對應(yīng)(可行性)；可以較容易地將現(xiàn)有的遺傳算子應(yīng)用于該方法；任一道路與一個編碼相對應(yīng)(合法性)；遺傳搜索可以搜索到解空間的任意一點.

圖1 基于優(yōu)先權(quán)的編碼和解碼方法Fig.1 Coding and decoding method based on priority

圖2 基于位置的交叉方法Fig.2 Position-based crossover

3.2 交叉算子

采用基于位置的交叉方法(position-based crossover, PX).PX交叉方法結(jié)合了均勻交叉與修復程序,是對順序交叉方法的改變,該方法選擇的交叉點不連續(xù).如圖2所示,首先從第一個父代中隨機選擇隨機個位置,將這些位置的基因值復制到子代中相同的位置；然后從第二個父代中刪除第一個父代中已被選中的基因,并將剩下的基因值按從左到右的順序依次填入子代中的其他位置.

3.3 變異算子

采用逆轉(zhuǎn)變異(inversion mutation)方法：首先從父代中隨機選擇2個位置,然后逆轉(zhuǎn)這2個點內(nèi)的子串.具體如圖3所示.

圖3 逆轉(zhuǎn)變異方法Fig.3 Inversion mutation

3.4 多目標遺傳算法性能衡量

1)一元績效指標——體積比例(hypervolume ratio, HVR).

HVR綜合衡量帕累托近似集的分布性和收斂性,用以判斷帕累托前端面上個體的絕對質(zhì)量,計算如下：

(19)

2)二元績效指標——集合覆蓋指標(C: set coverage)

二元績效指標通過比較2個多目標算法產(chǎn)生的帕累托近似解集衡量2種方法的績效,計算如下：

(20)

式中：p屬于帕累托近似集P,q屬于帕累托近似集Q,pq表示解p弱支配解q(在最小化目標值的問題中).式(21)表示：相對于帕累托近似集Ω,近似集P中解的平均質(zhì)量.

(21)

4 實驗分析

4.1 實驗數(shù)據(jù)

1)算例數(shù)據(jù).災(zāi)后需要將災(zāi)民及時疏散到安全

區(qū)域,避免二次災(zāi)難對人員造成傷害.為了爭取救援時間,提高救援效率,鄰近災(zāi)民往往自行聚集到一個地點,等待救援.組織者在災(zāi)區(qū)附近的安全區(qū)域建立避難所,以供疏散的災(zāi)民臨時居住.基于上述背景,搜集212個點的坐標及各點之間的連接關(guān)系,構(gòu)成疏散物流網(wǎng)絡(luò)的弧的數(shù)量是390.整個網(wǎng)絡(luò)的分布如圖4所示,設(shè)定212個地點的位置,連接這些地點的路段總共有390個.已知起點(圖4的小圓點)和終點(圖4的大圓點),要求選擇長度最短且可靠性最高的道路完成疏散任務(wù).在所研究的災(zāi)區(qū),有2個地方受到災(zāi)害的破壞最嚴重,采用0.7+0.3(r/R)作為距離重災(zāi)中心為r的道路的可靠性,其中R為參考半徑.由于道路上各點到重災(zāi)中心的距離不斷變化,為了方便計算,采用道路中心點代表道路的位置,由此計算每條道路的可靠性.2個重災(zāi)中心及其輻射如圖4的同心圓所示,路線的起點和終點如圖4的深色圓圈所示.

圖4 災(zāi)后路徑選擇實驗背景地圖Fig.4 Example’s base map for route selection after disaster

2)算法參數(shù).遺傳算法中主要涉及到以下參數(shù),設(shè)置如表1所示,表中，ns為種群規(guī)模，ni為迭代次數(shù)，PP為帕累托概率，Pc、Pm分別為交叉概率和變異概率.

表1 遺傳算法參數(shù)表

4.2 實驗設(shè)計

設(shè)計如表2所示的6個實驗.

表2 災(zāi)后路徑選擇實驗?zāi)繕?、實驗場景設(shè)置

4.3 實驗結(jié)果及說明

1)實驗1的結(jié)果如圖5所示.

圖5 采用最小值法計算道路可靠性Fig.5 Road reliability based on minimum value method

圖6 采用平均值法計算道路可靠性Fig.6 Road reliability based on mean value method

分別選取Pareto front上的3點分析路線長度及可靠性.解1中路線長度為583,道路可靠性為0.701；解2中路線長度為883,道路可靠性為0.708；解3中路線長度為1 561,道路可靠性為0.709.

2)實驗2的結(jié)果如圖6所示.

分別選取Pareto front上的3點分析路線長度及可靠性.解1中路線長度為689,道路可靠性為0.701；解2中路線長度為969,道路可靠性為0.714；解3中路線長度為1 303,道路可靠性為0.721.

3)實驗3的結(jié)果如圖7所示.

圖7 采用串聯(lián)法計算道路可靠性Fig.7 Road reliability based on series connection method

分別選取Pareto front上的3點分析路線長度及可靠性.解1中路線長度為568,道路可靠性為0.001 88；解2中路線長度為712,道路可靠性為0.003 84；解3中路線長度為728,道路可靠性為0.016 46.

采用串聯(lián)法時,道路的可靠性由構(gòu)成道路的每條路段的可靠性相乘得到,串聯(lián)法下道路的可靠性最小.當可靠性都為0.701時,采用最小值法模型得到的路線比平均值法模型短.隨著道路可靠性的提高,路線長度顯著增加.在串聯(lián)法模型中,解2的可靠性比解1提高了104.26%,長度僅增加了25.35%；最小值模型中解2的可靠性比解1提高了1%,長度增加了51.46%；平均值模型中解2比解1的可靠性提高了1.85%,長度增加了40.64%.串聯(lián)法中路線長度的小幅度增長能夠帶來道路可靠性的大幅提高.

4)實驗4的結(jié)果如圖8所示.

圖8 理想的帕累托前端面Fig.8 Ideal Pareto front

采用平均值法計算道路可靠性,運行結(jié)束后將最后得到的染色體解碼成相應(yīng)的行駛路線.根據(jù)每條路線出現(xiàn)的頻率大小進行排序,形成不同等級的解,據(jù)此繪制成不同等級的帕累托前端面.圖8分別展示了2個等級的帕累托前端面.圖中，rf、sf分別為前端面的比例和面積.圖8(a)中前端面的比例為0.997 9,面積為686.267；圖8(b)中比例為0.998 01,面積為686.344 2.不同等級的前端面上的解均是可行解,第一前端面上個體的適應(yīng)度最高.

5)實驗5的結(jié)果如圖9所示.

圖9 交叉概率的影響Fig.9 Influence of crossover ratio

隨著交叉概率的逐漸增大,覆蓋范圍波動式變化,理想積波動式下降.當交叉概率為0.9時,覆蓋范圍最??；當交叉概率為0.1或0.8時,覆蓋范圍最大(見圖9(a)).當交叉概率取0.9時,交叉操作較頻繁,得到最小的理想積(見圖9(b)).

6)實驗6的結(jié)果如圖10所示.圖中，COV為覆蓋范圍，VI為理想積.

圖10 變異概率的影響Fig.10 Influence of mutation ratio

隨著變異概率的逐漸增大,覆蓋范圍波動式變化,理想積緩慢增長后逐漸下降.當變異概率為0.05時,覆蓋范圍最??；當變異概率為0.04時,覆蓋范圍最大(見圖10(a)).當變異概率取0.09時,可以得到最小的理想積(見圖10(b)).

5 結(jié) 語

基于最短路問題,本文考慮災(zāi)后道路損毀嚴重的情況,定義道路可靠性,構(gòu)建雙目標優(yōu)化問題.一方面最小化給定起訖點間的道路長度,另一方面最大化道路的可靠性.本文給定212個點的坐標,設(shè)定各點間的連接關(guān)系,采用歐式距離計算兩點間的距離,設(shè)定其中兩個地方為重災(zāi)點.采用NSGA- II多目標遺傳算法求解,在Matlab軟件下進行仿真實驗.分別得到3種不同可靠性確定方法下的解,開展2個目標的Pareto分析,最后分析交叉概率和變異概率對結(jié)果的影響.帕累托前端面上的解均為最優(yōu)解,決策者可以根據(jù)其對某一目標的偏重選擇合適的解；交叉概率和變異概率對結(jié)果的影響不明顯,可能與選擇的案例數(shù)據(jù)有關(guān).未來的研究可以基于災(zāi)后的真實信息進行,實際考察災(zāi)區(qū)的道路狀況,選擇坡道轉(zhuǎn)彎少的最短最可靠的道路完成物資輸送、災(zāi)民疏散等任務(wù),為災(zāi)后救援提供實際的參考.考慮道路修復等因素,實時衡量道路的可靠性,進行動態(tài)決策,更貼近實際生活.

[1] 閆化海, 徐寅峰. 不完全信息下交通網(wǎng)絡(luò)最短路徑關(guān)鍵邊問題[J]. 系統(tǒng)工程, 2006, 24(2): 37-40． YAN Hua-hai, XU Yin-feng. The most vital edge of the shortest path with incomplete information in traffic networks [J]. Systems Engineering, 2006, 24(2): 37-40．

[2] NAZEMI A, OMIDI F. An efficient dynamic model for solving the shortest path problem [J]. Transportation Research Part C, 2013, 26(2013): 1-19．

[3] FESTA P, GUERRIERO F, LAGANA D, et al. Solving the shortest path tour problem [J]. European Journal of Operational Research, 2013, 230(2013): 464-474．

[4] AMIRTEIMOORI A. An extended shortest path problem: a data envelopment analysis approach [J]. Applied Mathematics Letters, 2012, 25(2012): 1839-1843．

[5] ASAKURA Y, KASHIWADANI M. Road network reliability caused by daily fluctuation of traffic flow [C]∥Proceedings of the 19th PTRC Summer Annual Meeting. Brighton: [s. n.], 1991: 73-84．[6] CHEN A, YANG H, LO H. Capacity reliability of a road network: an assessment methodology and numerical results [J]. Transportation Research Part B: Methodological, 2002, 36(3): 225-252．

[7] ARDAKANI M K, TAVANA M. A decremental approach with the A*algorithm for speeding-up the optimization process in dynamic shortest path problems [J]. Measurement, 2015, 60(2015) : 299-307．[8] 靳凱文, 李春葆, 秦前清.基于蟻群算法的最短路徑搜索方法研究[J]. 公路交通科技, 2006, 23(3): 128-131． JIN Kai-wen, LI Chun-bao, QIN Qian-qing. Study on shortest path search method based on ant algorithm [J]. Journal of Highway and Transportation Research and Development, 2006, 23(3): 128-131．

[9] LOZANO L, MEDAGLIA A S L. On an exact method for the constrained shortest path problem [J]. Computers and Operations Research, 2013, 40(2013): 378-384．

[10] CHENG J, LISSER A.Maximum probability shortest path problem [J]. Discrete Applied Mathematics, 2015, 192(2015): 40-48．

[11] 鄒亮, 徐建閩. 基于遺傳算法的動態(tài)網(wǎng)絡(luò)中最短路徑問題算法[J]. 計算機應(yīng)用, 2005, 25(4): 742-744． ZOU Liang, XU Jian-min. Method of shortest paths problem on dynamic network based on genetic algorithm [J]. Computer Applications, 2005, 25(4): 742-744．

[12] NIKSIRAT M, GHATEE M, HASHEMI S M. Multimodal K-shortest viable path problem in Tehran public transportation network and its solution applying ant colony and simulated annealing algorithms [J]. Applied Mathematical Modeling, 2012, 36(2012): 5709-5726．

[13] HASUIKE T.Robust shortest path problem based on a confidence interval in fuzzy bicriteria decision making [J]. Information Sciences, 2013, 221(2013): 520-533．

[14] CHEN P, NIE Y. Bicriterion shortest path problem with a general nonadditive cost [J]. Procedia-Social and Behavioral Sciences, 2013, 80(2013): 553-575．

[15] LEE S, MOON B, ASAKURA Y.Reliability analysis and calculation on large scale transport networks, in reliability of transport networks [M]. England: Research Studies Press Limited, 2000: 173-189．

[16] 陳富堅, 柳本民, 郭忠印, 等. 基于貝葉斯分析的道路交通系統(tǒng)可靠性模型[J]. 同濟大學學報：自然科學版, 2011, 39(2): 220-225． CHEN Fu-jian, LIU Ben-min, GUO Zhong-yin, et al. Reliability models of road traffic systems based on Bayesian analysis [J]. Journal of Tongji University: Natural Science, 2011, 39(2): 220-225．

[17] 侯立文, 蔣馥. 城市道路網(wǎng)絡(luò)可靠性的研究[J]. 系統(tǒng)工程, 2000, 18(5): 44-48． HOU Li-wen, JIANG Fu. Study on the reliability of urban road network [J]. Systems Engineering, 2000, 18(5): 44-48．

[18] 秦軍, 曹云剛, 耿娟. 汶川地震災(zāi)區(qū)道路損毀度遙感評估模型[J]. 西南交通大學學報, 2010, 45(5): 768-774． QIN Jun, CAO Yun-gang, GENG Juan. Evaluation model for damage extent of roads in Wenchuan earthquake-stricken areas based on remote sensing information [J]. Journal of Southwest Jiaotong University, 2010, 45(5): 768-774．

[19] GEN M, CHENG R, LIN L. Network models and optimization: multiobjective genetic algorithm approach[M]. Germany:Springer, 2008: 15-74.

Reliable path selection after disaster based on multi-objective genetic algorithm

LI Qing1,2, HU Zhi-hua2

(1.SchoolofEconomicsandManagement,TongjiUniversity,Shanghai200092,China; 2.LogisticsResearchCenter,ShanghaiMaritimeUniversity,Shanghai201306,China)

The shortest path is needed to transport victims and materials as soon as possible. Safe path becomes the critical factor in road selection considering the road damage in the disaster. Three means were adopted to define the road reliability based on the damage condition of roads after a disaster, and a bi-objective optimization model was established. The model tries to minimize the length of road and maximize the roads’ reliability. The priority-based multi-objective genetic algorithm was used to handle the problem. The solutions were respectively got under three situations. Pareto analysis was conducted. The impacts of crossover rate and mutation rate on the results were analyzed. With the crossover ratio increases, the coverage fluctuates and the fluctuated ideal volume decreases. With the mutation ratio increases, the coverage fluctuates and the ideal volume grows slowly and then gradually declines. The genetic algorithm can effectively solve the shortest and most reliable path problem．

shortest path problem; multi-objective genetic algorithm; priority; reliability

2015-02-17. 浙江大學學報(工學版)網(wǎng)址： www.journals.zju.edu.cn/eng

國家自然科學基金青年資助項目(71101088)；國家自然科學基金面上項目(71171129)；國家自然科學基金資助項目(71390521)；上海市曙光計劃資助項目(13SG48)；教育部博士點基金資助項目(20113121120002，20123121110004)；上海市科委資助項目(11510501900，12510501600，12ZR1412800)；上海市教委科研創(chuàng)新資助項目(14YZ100)；上海海事大學研究生學術(shù)新人培育項目(YXR2014075).

李清(1991-)，女，碩士生，從事應(yīng)急物流的研究.ORCID: 0000-0001-7134-4941.E-mail：mzsq126@126.com 通信聯(lián)系人：胡志華，男，副教授.E-mail: zhhu@shmtu.edu.cn

10.3785/j.issn.1008-973X.2016.01.006

U 491

A

1008-973X(2016)01-0033-08