基于混合優化算法的城市應急疏散公交車輛路徑優化研究

陳柯 劉曉莉

（長安大學，陜西 西安 710064）

基于混合優化算法的城市應急疏散公交車輛路徑優化研究

陳柯 劉曉莉

（長安大學，陜西 西安 710064）

本文就突發事件條件下，研究用公交車進行疏散的路徑選擇的模型，叫做混合優化算法求解模型，該模型是基于粒子群算法和螞蟻群算法。用粒子群算法的粒子位置向量得到每輛公交車所需運送的人群種類，用蟻群算法優化單車路徑，根據優化的總路徑評價得到最優解。

車輛路徑；粒子群算法；螞蟻群算法

目前城市交通應急管理大多集中在宏觀管理體系建設方面，針對公交應急疏散救援理論和方法的研究幾乎沒有進行。考慮到這一方面，本文將公交車作為疏散主要研究對象，研究在應急情況下，如何選擇道路最優疏散路徑的問題。運用了粒子群算法和螞蟻群算法，建立一種混合算法的城市公交應急疏散公交車輛路徑優化模型。

1 粒子群算法與螞蟻群算法模型的改進

1.1 粒子群算法

粒子群算法是模仿鳥之間的集體協作使群體覓食路徑達到最優。本文將其運用到城市公交應急疏散公交車輛路徑優化中，并進行適當的修改。先構造一個有R個粒子的D維空間，每一維對應需運送的一種人群體，記為隨機的公交車號l，即粒子r的D維位置向量Xr（Xr=xr1，xr2，…，xrd）表示所有車輛分配到的一種人群體。由于粒子群算法的位置向量得到的是每輛公家車所需運送的人群體，但得不到車輛所走的順序，所以單車優化路徑還要另算出。

1.2 螞蟻群算法

螞蟻群算法是一種基于種群的模擬進化算法。先進行參數和初始化種群的設置，接著進行螞蟻構造路徑，采用局部更新的規則，循環結束后，若不符合要求則重新構造，若符合要求則進入找出最短路徑并應用全局更新規則，不滿足終止條件則重新進行螞蟻構造路徑，直至滿足終止條件再結束，該路徑就為最優路徑。

2 城市公交應急疏散公交車輛路徑優化研究

城市應急疏散公交車輛路徑優化研究問題中要求將每個乘客安全快速地疏散，這就要求至少訪問一次與乘客相關的所在地、疏散目的地，而一輛公交車一次運輸能力常滿足不了疏散中心的總乘客數，所以需要單輛公交車多次訪問或多輛公交車一次訪問。為了方便，本文把乘客相關的所在地、疏散地統稱為節點。由于疏散地的乘客要送往的目的地不同，將乘客按照從所在地到疏散地不同進行分類，成為人群種類。

2.1 模型參數確定

路網G=（P，A），V表示網絡圖中的全部點集，即節點i,j∈P，A表示網絡圖中全部弧；mv表示公交車的荷載量；T表示公交車輛總數，l表示第l輛公交車，l∈T；x1ij表示公交車輛l是否從節點i直接到節點j，取1表示是,取0表示否；di表示節點i到節點j的距離；Lvmax表示公交車輛最大出行里程；表示公交車輛l的固定成本。

2.2 路徑優化模型

為了使作用的公交車輛總路徑級車輛數最優為目標，本文將系統優化的最優方案為：

2.3 模型基本步驟的構想

本文研究的算法是利用粒子算法、蟻群算法組成的混合算法進行城市公交應急疏散公交車輛路徑優化研究，使得優化結果全局最優。先用粒子群算法的位置向量產生每輛公交車需要運送的人群，再用螞蟻群算法為每輛公交車設計出路徑，最后進行綜合評價，選出最優路徑，使得全局盡可能最優。

具體實現步驟：（1）確定粒子群算法；（2）蟻群算法的所需參數；（3）確定每個粒子位置向量Xr，其每一維隨機取[0，M-1]中的整數；（4）確定速度向量vr，其每一維隨機取[-（M-1），M-1]中的數；（5）找出每輛車需要配送的訂單號；（6）用蟻群算法得到車輛優化路徑；（7）用評價函數評價所有粒子；（8）當某一粒子的歷史最優評價值劣于其現評價值時，記該粒子歷史最優評價值為當前評價值，記該粒子歷史最優位置Pr為當前位置，并優化出車輛路徑；（9）尋找總群體內最優解，當優于歷史為最優解時，則更新Pg及每輛車的出行路徑。當有多個都為最優值時，則隨機取其中一個為最優解。

3 總結

在城市公交應急疏散公交車輛路徑優化模型中將疏散始、終地點的關系,疏散的人與公交車之間的關系模型化。對所有車輛及所有始、終點進行路徑搜索,這樣能夠全面而科學地求解，并將粒子群算法和螞蟻群算法運用到城市公交應急疏散公交車輛路徑優化中，易于實現全局最優的目的。但是由于現實因素與自身條件的關系，本文所提出的方法還處于理論階段，未在現實中應用，這既是本文模型的一個缺陷，也是進一步研究的方向。

[1]Dorigo M,Maniezzo V,Colorni A.Ant system:optimization by a colony of cooperating agents[J].Systems,Man and Cybernetics: Part B,1996,26(1):29-41.

[2]張麗艷,龐小紅,夏蔚軍,吳智銘,梁碩.帶時間窗車輛路徑問題的混合粒子群算法[J],上海交通大學學報,2006(11):130-134.

U491

A

1003-5168(2014)03-0155-01