基于遺傳算法的應(yīng)急疏散中車輛路徑規(guī)劃研究

王遜，杜中軍，劉孟軻，陳海祥

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

0 引言

隨著現(xiàn)代城市發(fā)展與建設(shè)，人口越來越密集，如何在自然災(zāi)害、恐怖襲擊等安全事件發(fā)生之后，快速有效地進(jìn)行應(yīng)急疏散，近年來成為交通規(guī)劃與管理領(lǐng)域的一個(gè)新的研究方向。疏散路徑規(guī)劃是應(yīng)急疏散的關(guān)鍵，車隊(duì)運(yùn)動(dòng)問題（Convoy movement problem）是疏散路徑規(guī)劃中的一個(gè)重要子問題，在CMP中，給定一組車輛和一個(gè)用于機(jī)動(dòng)的路網(wǎng)，每一輛車都有特定的起點(diǎn)和終點(diǎn)對(duì)，且有出發(fā)時(shí)間和到達(dá)時(shí)間的約束，如何高效規(guī)劃每輛車的行駛路徑是解決問題的焦點(diǎn)。

許多研究者將車隊(duì)疏散問題抽象為網(wǎng)絡(luò)流領(lǐng)域的問題來進(jìn)行研究，Dunn和Newton提出了使用最大流方法來進(jìn)行路徑選擇，Yamada運(yùn)用最小代價(jià)流問題進(jìn)行疏散交通分配，提出了最短路撤退規(guī)劃（Shortest Evacuation Plan，SEP）方法。也有不少學(xué)者采用運(yùn)籌學(xué)方法對(duì)其進(jìn)行研究，Chardaire P等基于時(shí)間-空間網(wǎng)絡(luò)的概念建立了針對(duì)CMP問題的整數(shù)規(guī)劃模型，并通過拉格朗日松弛的方法對(duì)模型進(jìn)行了求解，Gopalan R等系統(tǒng)研究了CMP問題的計(jì)算復(fù)雜度，并給出了針對(duì)其變式的多項(xiàng)式時(shí)間算法。Guan,L.提出了一種二階段的方法，以車輛的效率最大化為標(biāo)準(zhǔn)為多任務(wù)指定車輛路徑分配方法。Pinedo,Ruben D.研究了一個(gè)在不安全環(huán)境下，多起點(diǎn)、多終點(diǎn)的路徑規(guī)劃問題，為降低車輛的危險(xiǎn)系數(shù)，給出了一種區(qū)域受限的救援車輛分配方法。

對(duì)于CMP及其衍生問題的研究，多優(yōu)化兩個(gè)方面的目標(biāo)：一是縮短車輛道路機(jī)動(dòng)時(shí)間，二是提高車輛的使用效率。然而，在應(yīng)急疏散中，通過路徑規(guī)劃改進(jìn)車輛組行駛的安全性能，同樣是一個(gè)值得關(guān)注的問題，本文擬從這個(gè)角度，對(duì)多起點(diǎn)、多終點(diǎn)、多車輛的路徑選擇問題進(jìn)行建模，并設(shè)計(jì)出一個(gè)基于優(yōu)先級(jí)對(duì)染色體進(jìn)行編碼以建立路徑樹的遺傳算法。

1 應(yīng)急疏散中車輛路徑規(guī)劃建模

為突出車輛運(yùn)動(dòng)中的安全性問題，本模型對(duì)其他問題細(xì)節(jié)進(jìn)行了合理的抽象和簡化。第一、假設(shè)車輛的機(jī)動(dòng)速度恒定不變，為某一常數(shù)；第二、假設(shè)每一路段都有明確的通行車輛上限；第三、假設(shè)在每一路段中，車輛的安全通行概率是確定的；第四、模型假設(shè)每一終點(diǎn)地最多只接收一輛車，這樣能在一定程度上避免了車群的大規(guī)模損毀。

1.1 模型符號(hào)說明

模型中使用的角標(biāo)說明：i表示起點(diǎn)地Oi，i=1,2，…，I，其中 I是起點(diǎn)地的數(shù)量；j表示終點(diǎn)地 Dj，j=1,2，…，J，其中J是終點(diǎn)地的數(shù)量；k表示k短路，對(duì)于每一個(gè)OD對(duì)，其中k=1,2,…,Kij,Kij是從起點(diǎn)地Oi到終點(diǎn)地Dj間待考慮的路徑數(shù)量；l表示路段Al，l=1,2,…,L，其中L是所有OD對(duì)間的短路徑中所有不重復(fù)的路段之和。

模型中使用的參數(shù)說明：wi表示從起點(diǎn)地Oi發(fā)出的車輛數(shù)；Pijk表示在從起點(diǎn)地Oi到終點(diǎn)地Dj間的第k短路可安全通行的概率；Rijk表示一個(gè)路段集合，包含從起點(diǎn)地Oi到終點(diǎn)地Dj間的第k短路中包含的所有路段；tl表示車輛通過路段Al所花費(fèi)的時(shí)間，由路段長度和行駛速度計(jì)算得到；Te表示可用于車輛行駛的時(shí)間上限，應(yīng)急疏散任務(wù)開始后，在該時(shí)間段內(nèi)所有車輛必須完成行駛；αlijk為0–1變量，當(dāng)從起點(diǎn)地Oi到終點(diǎn)地Dj間的第k短路中包含路段Al時(shí)取1，否則取0；λl表示路段Al的車輛通行上限。

模型中的決策變量：xijk為0-1變量，當(dāng)存在一輛車從起點(diǎn)地Oi向終點(diǎn)地Dj經(jīng)由該OD對(duì)間的第k短路機(jī)動(dòng)時(shí)取1，沒有車經(jīng)過該路徑時(shí)取0。

1.2 模型構(gòu)建及解釋

模型旨在對(duì)路網(wǎng)中車輛行駛路徑選擇的安全性問題進(jìn)行優(yōu)化。

公式（1）是模型的目標(biāo)函數(shù)，它表示最大化各車輛安全完成行駛?cè)蝿?wù)的概率之和。公式（2）表示從起點(diǎn)地發(fā)出的車必須被制定一條路徑和一個(gè)可用的終點(diǎn)地；公式（3）對(duì)應(yīng)假設(shè)四，表示每一終點(diǎn)地最多接收一輛車；公式（4）指出每一輛車進(jìn)行路徑選擇時(shí)必須滿足任務(wù)時(shí)間限制；公式（5）表示從Oi到Dj間的第k短路徑的安全通行概率為該路徑內(nèi)各個(gè)路段安全通行概率之乘積；公式（6）表示在整個(gè)行駛過程中，各個(gè)路段中通行的車輛總數(shù)小于或等于該路段的通行上限。

2 基于遺傳算法的模型求解過程

模型的遺傳算法借鑒Altiparmak Fulya給出的一種基于優(yōu)先權(quán)的編碼方法，每一個(gè)基因位表示一個(gè)起點(diǎn)或終點(diǎn)，基因位上的值表示對(duì)應(yīng)點(diǎn)在構(gòu)建路徑樹時(shí)的優(yōu)先權(quán)，數(shù)值越大，優(yōu)先權(quán)越高，這類方法將不同染色體解碼為同一路徑樹的概率極低，性能也非常穩(wěn)定。

2.1 編碼設(shè)計(jì)

模型中染色體長度為I+J位，其中I為起點(diǎn)地?cái)?shù)量，J為終點(diǎn)地?cái)?shù)量，前I個(gè)基因代表I個(gè)起點(diǎn)地，后J個(gè)基因代表J個(gè)終點(diǎn)地，每一位基因上表征一個(gè)數(shù)字，代表該起點(diǎn)或者終點(diǎn)地的優(yōu)先權(quán)。同時(shí)，生成一個(gè)輔助算子與染色體長度相同，同為I+J位，輔助算子上每一位表征一個(gè)數(shù)字，代表該起點(diǎn)地或者終點(diǎn)地還可以發(fā)車或者接車的數(shù)量，如圖1所示，染色體中前三位基因表示三個(gè)起點(diǎn)地，優(yōu)先權(quán)分別為4、1、8，后五位基因表示五個(gè)終點(diǎn)地，優(yōu)先權(quán)分別為 5、2、6、3、7，輔助算子中前三位分別表示三個(gè)起點(diǎn)地要發(fā)出車輛的數(shù)量分別為1、1、2，后五位分別表示五個(gè)終點(diǎn)地可以接車的數(shù)量，均為1。

圖1 染色體與輔助算子實(shí)例

2.2 遺傳操作

遺傳操作中，主要有選擇、交叉和變異三個(gè)階段。

在選擇階段，需要對(duì)候選染色體進(jìn)行解碼，每一染色體解碼后會(huì)生成一套車輛路徑規(guī)劃方案，帶入目標(biāo)函數(shù)，可以計(jì)算出該方案獲得車輛的總安全通信概率，將此作為該染色體的適應(yīng)度，從而進(jìn)行遺傳選擇。一般而言，設(shè)置固定選擇比例，適應(yīng)度較優(yōu)的染色體保留，適應(yīng)度較差的染色體進(jìn)行交叉或變異階段。

在交叉階段，在兩個(gè)父代染色體中隨機(jī)選取兩個(gè)位置，兩個(gè)父代染色體中兩個(gè)位置之間的基因段定義為映射區(qū)，將兩映射區(qū)的基因進(jìn)行互換，互換后會(huì)出現(xiàn)同一染色體中出現(xiàn)基因位優(yōu)先權(quán)數(shù)字一樣的情況，在保持互換的基因段和非重合基因不變的情況下，將重復(fù)的基因進(jìn)行沖突消除，這樣就可以交叉得到兩條沒有沖突的子代染色體。

在變異階段，隨機(jī)選擇變異染色體，然后在待變?nèi)旧w上隨機(jī)選擇兩個(gè)位置，將這兩個(gè)位置的基因進(jìn)行互換，變可得到變異后的新染色體。

2.3 解碼設(shè)計(jì)

解碼的過程就是一個(gè)逐漸生成車輛規(guī)劃路徑的過程，先給染色體中優(yōu)先權(quán)最高的基因進(jìn)行路徑選擇，優(yōu)先權(quán)最高的路徑選擇完畢后更新優(yōu)先權(quán)，再給優(yōu)先權(quán)最高的基因進(jìn)行路徑選擇，直到所有車輛都已經(jīng)完成路徑選擇，則完成了該染色體解碼。在路徑選擇中，一般采用貪婪算法，即為優(yōu)先權(quán)最高的基因分配最佳的行駛路徑，只要該路徑滿足其他約束條件，例如時(shí)間的約束、資源的約束和最大通行量的約束等。

本模型染色體的解碼流程如下：

輸入：染色體和輔助算子。

輸出：車輛行駛路徑樹。

Step1:選擇染色體中優(yōu)先權(quán)最高的基因，使用貪婪算法，為該基因選擇一條最佳路徑；

Step2:若選擇成功，則將該路徑加入路徑樹，同時(shí)，將該路徑的起點(diǎn)和終點(diǎn)基因位上輔助算子的數(shù)字減1；

Step3:若選擇失敗，則標(biāo)記該染色體無效，退出解碼。

Step4:輔助算子中數(shù)字為0的位置，將染色體中該位置的優(yōu)先權(quán)數(shù)字變?yōu)?；

Step5:若染色體中前I位基因或者后J位基因均為0，則停止解碼，輸出路徑樹，否則，繼續(xù)Step1。

2.4 求解過程

模型中目標(biāo)函數(shù)多為概率值構(gòu)成，且數(shù)值均較小，為突出各染色體的性能各異，可將概率值取負(fù)對(duì)數(shù)處理，由此將模型的目標(biāo)函數(shù)轉(zhuǎn)為：

相應(yīng)的，約束條件（5）也轉(zhuǎn)化為：

在遺傳算法中進(jìn)行最佳路徑的選擇，需要先使用A*算法對(duì)路徑進(jìn)行預(yù)處理計(jì)算，求得每一個(gè)起點(diǎn)地與每一個(gè)終點(diǎn)地的k最短路徑，以備遺傳算法中進(jìn)行路徑選擇。

由此，求解過程如下：

Step1：使用A*算法生成所有起點(diǎn)地和終點(diǎn)地對(duì)的k最短路徑；

Step2：初始化染色體和輔助算子種群；

Step3：計(jì)算染色體適應(yīng)度，迭代進(jìn)行選擇、交叉、變異操作；

Step4：迭代過程中國，持續(xù)N代未出現(xiàn)更優(yōu)解，則停止計(jì)算，輸出結(jié)果。

3 實(shí)驗(yàn)案例

3.1 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)的運(yùn)行環(huán)境是，64位Windows 7操作系統(tǒng)，Intel Core i7 3.6GHz處理器和12GB的內(nèi)存，其實(shí)現(xiàn)平臺(tái)為MATLAB軟件。實(shí)驗(yàn)對(duì)象為系統(tǒng)隨機(jī)生成的10個(gè)不同大小規(guī)模的車輛行駛路網(wǎng)，其中實(shí)驗(yàn)參數(shù)設(shè)置為，每一路段的最大通行量為5，各路段的安全通行概率，通行時(shí)間等參數(shù)為隨機(jī)生成。遺傳算法中的選擇概率為0.85，交叉概率為0.85，變異概率為0.15，持續(xù)10代未出現(xiàn)更優(yōu)解，則停止計(jì)算。

3.2 實(shí)驗(yàn)結(jié)果

隨機(jī)生成10個(gè)不同大小規(guī)模的車輛行駛路網(wǎng)，其具體情況如表1所示。

表1 10個(gè)不同規(guī)模的路徑網(wǎng)絡(luò)情況

經(jīng)過建模及求解過程，可得車輛路徑規(guī)劃結(jié)果，其中選取路網(wǎng)6中的車輛路徑規(guī)劃結(jié)果如表2所示。

表2 路網(wǎng)6中遺傳算法計(jì)算出的最優(yōu)車輛行駛方案

在不同路網(wǎng)中進(jìn)行實(shí)驗(yàn)，遺傳算法對(duì)解的性能提升率如表3所示。

表3 各路網(wǎng)中遺傳算法的性能提升情況

3.3 結(jié)果分析

在10個(gè)規(guī)模大小不同的路網(wǎng)中進(jìn)行實(shí)驗(yàn)，根據(jù)表3.3可以分析得出，對(duì)于小規(guī)模路徑規(guī)劃，遺傳算法的性能提升并不太大，因?yàn)槠涑跏冀庵锌赡芫鸵呀?jīng)包括了優(yōu)化解，而隨著問題的規(guī)模變大，遺傳算法的逐步得到體現(xiàn)，在路網(wǎng)7和路網(wǎng)9中，性能提升率均超過了300%，同時(shí)由于遺傳算法的收斂性，本實(shí)驗(yàn)均在有效時(shí)間內(nèi)完成了計(jì)算。

4 結(jié)語

源和通行限制等外部約束，為了有效地對(duì)模型進(jìn)行求解，引入遺傳算法，針對(duì)車輛路徑規(guī)劃問題，提出了基于優(yōu)先權(quán)的染色體設(shè)計(jì)和等長輔助算子的設(shè)計(jì)，使得遺傳算法能更好地適用于本問題，最后通過對(duì)10個(gè)不同規(guī)模大小的路徑規(guī)劃問題進(jìn)行實(shí)驗(yàn)，驗(yàn)證了本文提出的模型及遺傳算法求解的有效性。當(dāng)然，該問題并未徹底解決，本文中提出的算法也存在隨著車輛的數(shù)量、起點(diǎn)地的數(shù)量和終點(diǎn)地的數(shù)量增加，運(yùn)算時(shí)間會(huì)大幅增長，原因在于解碼的效率問題，這也是筆者下一步要研究的方向。

本文首先對(duì)應(yīng)急疏散中車輛路徑規(guī)劃問題進(jìn)行了建模，其目標(biāo)旨在車輛的安全性，綜合考慮了時(shí)間、資

參考文獻(xiàn)：

[1]Yamada T.A Network Flow Approach to a City Emergency Evacuation Planning[J].International Journal of Systems Science，1996,27（10）:931-936.

[2]Chardaire P,Richardson S B.Solving a Time-Space Network Formulation for the Convoy Movement Problem[J].Operations Research,2005,53（2）:219-230.

[3]Gopalan R.Computational Complexity of Convoy Movement Planning Problems[J].Mathematical Methods of Operations Research,2015,82（1）:31-60.

[4]Guan L.The Research of The Optimal Distribution for the Multitask using Types of Vehicles[C].International Conference on Transportation Engineer 2007.ASCE,2015:539-544.

[5]Pinedo Y,Ruben D.Route Optimization While Improving Safety Using Escort Vehicles[J].Dissertations&Theses-Gradworks，2013.

[6]陳華華,杜歆,顧偉康.基于遺傳算法的靜態(tài)環(huán)境全局路徑規(guī)劃[J].浙江大學(xué)學(xué)報(bào)，2015,32（1）:49-53.

[7]馬超,郭健,闞映紅,王卉,唐金龍.基于遺傳算法的應(yīng)急疏散方案研究[J].測(cè)繪科學(xué)學(xué)報(bào)，2013，29（6）.

[8]Aljazzar H,Leue S.K:A Heuristic Search Algorithm for Find The K-shortest Paths[J].Artificial Intelligence,2011,175（18）:2129-2154.