基于遺傳算法的應急疏散中車輛路徑規劃研究

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

（四川大學計算機學院，成都 610065）

0 引言

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

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

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

1 應急疏散中車輛路徑規劃建模

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

1.1 模型符號說明

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

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

模型中的決策變量：xijk為0-1變量，當存在一輛車從起點地Oi向終點地Dj經由該OD對間的第k短路機動時取1，沒有車經過該路徑時取0。

1.2 模型構建及解釋

模型旨在對路網中車輛行駛路徑選擇的安全性問題進行優化。

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

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

模型的遺傳算法借鑒Altiparmak Fulya給出的一種基于優先權的編碼方法，每一個基因位表示一個起點或終點，基因位上的值表示對應點在構建路徑樹時的優先權，數值越大，優先權越高，這類方法將不同染色體解碼為同一路徑樹的概率極低，性能也非常穩定。

2.1 編碼設計

模型中染色體長度為I+J位，其中I為起點地數量，J為終點地數量，前I個基因代表I個起點地，后J個基因代表J個終點地，每一位基因上表征一個數字，代表該起點或者終點地的優先權。同時，生成一個輔助算子與染色體長度相同，同為I+J位，輔助算子上每一位表征一個數字，代表該起點地或者終點地還可以發車或者接車的數量，如圖1所示，染色體中前三位基因表示三個起點地，優先權分別為4、1、8，后五位基因表示五個終點地，優先權分別為 5、2、6、3、7，輔助算子中前三位分別表示三個起點地要發出車輛的數量分別為1、1、2，后五位分別表示五個終點地可以接車的數量，均為1。

圖1 染色體與輔助算子實例

2.2 遺傳操作

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

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

在交叉階段，在兩個父代染色體中隨機選取兩個位置，兩個父代染色體中兩個位置之間的基因段定義為映射區，將兩映射區的基因進行互換，互換后會出現同一染色體中出現基因位優先權數字一樣的情況，在保持互換的基因段和非重合基因不變的情況下，將重復的基因進行沖突消除，這樣就可以交叉得到兩條沒有沖突的子代染色體。

在變異階段，隨機選擇變異染色體，然后在待變染色體上隨機選擇兩個位置，將這兩個位置的基因進行互換，變可得到變異后的新染色體。

2.3 解碼設計

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

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

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

輸出：車輛行駛路徑樹。

Step1:選擇染色體中優先權最高的基因，使用貪婪算法，為該基因選擇一條最佳路徑；

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

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

Step4:輔助算子中數字為0的位置，將染色體中該位置的優先權數字變為0；

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

2.4 求解過程

模型中目標函數多為概率值構成，且數值均較小，為突出各染色體的性能各異，可將概率值取負對數處理，由此將模型的目標函數轉為：

相應的，約束條件（5）也轉化為：

在遺傳算法中進行最佳路徑的選擇，需要先使用A*算法對路徑進行預處理計算，求得每一個起點地與每一個終點地的k最短路徑，以備遺傳算法中進行路徑選擇。

由此，求解過程如下：

Step1：使用A*算法生成所有起點地和終點地對的k最短路徑；

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

Step3：計算染色體適應度，迭代進行選擇、交叉、變異操作；

Step4：迭代過程中國，持續N代未出現更優解，則停止計算，輸出結果。

3 實驗案例

3.1 實驗環境

本實驗的運行環境是，64位Windows 7操作系統，Intel Core i7 3.6GHz處理器和12GB的內存，其實現平臺為MATLAB軟件。實驗對象為系統隨機生成的10個不同大小規模的車輛行駛路網，其中實驗參數設置為，每一路段的最大通行量為5，各路段的安全通行概率，通行時間等參數為隨機生成。遺傳算法中的選擇概率為0.85，交叉概率為0.85，變異概率為0.15，持續10代未出現更優解，則停止計算。

3.2 實驗結果

隨機生成10個不同大小規模的車輛行駛路網，其具體情況如表1所示。

表1 10個不同規模的路徑網絡情況

經過建模及求解過程，可得車輛路徑規劃結果，其中選取路網6中的車輛路徑規劃結果如表2所示。

表2 路網6中遺傳算法計算出的最優車輛行駛方案

在不同路網中進行實驗，遺傳算法對解的性能提升率如表3所示。

表3 各路網中遺傳算法的性能提升情況

3.3 結果分析

在10個規模大小不同的路網中進行實驗，根據表3.3可以分析得出，對于小規模路徑規劃，遺傳算法的性能提升并不太大，因為其初始解中可能就已經包括了優化解，而隨著問題的規模變大，遺傳算法的逐步得到體現，在路網7和路網9中，性能提升率均超過了300%，同時由于遺傳算法的收斂性，本實驗均在有效時間內完成了計算。

4 結語

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

本文首先對應急疏散中車輛路徑規劃問題進行了建模，其目標旨在車輛的安全性，綜合考慮了時間、資

參考文獻：

[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]陳華華,杜歆,顧偉康.基于遺傳算法的靜態環境全局路徑規劃[J].浙江大學學報，2015,32（1）:49-53.

[7]馬超,郭健,闞映紅,王卉,唐金龍.基于遺傳算法的應急疏散方案研究[J].測繪科學學報，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.