基于改進蟻群算法的公交網絡路徑優(yōu)化

武可心

(西安交通工程學院 交通運輸學院，陜西 西安 710000)

0 引言

公交網絡是城市重要交通系統(tǒng)之一，對社會經濟發(fā)展和市民出行具有重要影響。傳統(tǒng)的公交網絡規(guī)劃多采用整體重新規(guī)劃，需要消耗大量人力物力，同時會對市民出行造成不便，并不適應于大中型城市的公交網絡優(yōu)化[1]。Pacheco等[2]提出了一種局部搜索和禁忌搜索策略的算法，以優(yōu)化公交線路和車輛分配。Szeto等[3]結合遺傳算法和領域搜索算法，建立了車輛頻次和線路設計模型。Gambardella等[4]提出了一種直接修改線路方案的蟻群算法。Botee等[5]對α、β、ρ等參數(shù)進行了深入研究。本文將蟻群搜索算法應用于公交線路網絡的優(yōu)化問題上，同時改進懲罰機制，實驗結果表明該方案能夠明顯提升公交網絡性能，具有一定的研究意義和應用價值。

1 公交網絡模型

Mandl道路網絡是當前比較常用的典型道路網絡模型之一，這里以該網絡及站點客流OD數(shù)據(jù)為研究對象，分析公交線路網絡優(yōu)化問題。Mandl線路網絡[6]如圖1所示。共包含了15個公交站和22條線路，每段線路上的數(shù)據(jù)表示該段線路需要花耗的旅行時間。

圖1 Mandl道路網絡示意圖

利用G=(N,A)模型描述Mandl道路網絡，式中N表示公交站的集合，A表示連接公交站的線路集合。用OD表示客流量矩陣，其中odij代表在單位時間內第i個站點與第j

個站點間的乘客量，單位為：位/小時。乘客客流量矩陣OD可表示為式(1)。

OD={odij|i,j∈[1,2,3,…，N|}

(1)

在公交網絡模型中，站點i到站點j的距離可表示lij，站點間的距離矩陣L可表示為式(2)。

L={lij|i,j∈[1,2,3,…，N|}

(2)

為了對公交線路網絡的優(yōu)劣進行定量評價，需要提出公交網絡的評價函數(shù)，該網絡的性能評價函數(shù)為式(3)。

(3)

約束條件如式(4)。

(4)

式中，l代表線路的長度；p代表線路的直達客流量，即乘客只需乘坐線路r就到達目的地的乘客數(shù)量；Z代表該線路的非直線系數(shù)；s.t.代表約束條件。

我們可以獲得的已知數(shù)據(jù)包括公交站點集合N，客流量矩陣OD和站點間距離矩陣L。公交線路網絡的目的是通過算法調整公交線路集合A，使得評價函數(shù)f的值達到最大。本文將蟻群算法引入到公交線路網絡優(yōu)化中，通過相應的改進與應用，從而實現(xiàn)對線路網絡的優(yōu)化問題。

2 蟻群搜索優(yōu)化算法

蟻群算法是通過研究蟻群覓食行為，形成的一種群體智能優(yōu)化算法。單只螞蟻的行為看似簡單且無規(guī)則，但蟻群群體卻能在巢穴與食物之間的復雜線路中尋找出一條最優(yōu)路線。蟻群搜索算法具有并行性、魯棒性、正反饋性及良好的結合性等優(yōu)勢。將蟻群算法應用于實際的公交線路網絡的優(yōu)化問題，可有效提升公交系統(tǒng)的運行能力。基于蟻群算法的公交線路優(yōu)化流程如圖2所示。

圖2 蟻群搜索算法流程圖

其中，Gen表示公交線路迭代次數(shù)；size表示蟻群大小，acogen蟻群算法迭代次數(shù)。蟻群搜索算法主要內容包括線路調整規(guī)則、客流重新分配、信息素更新、懲罰機制等幾方面內容。

2.1 線路調整規(guī)則

通過蟻群算法對每一條公交線路進行優(yōu)化調整，首先將原有的公交路線作為蟻群算法的初始值，利用評價函數(shù)f生成初始的信息素，置于初始路徑上，信息素[7]為式(5)。

(5)

式中，τ表示該線路段上的信息素值；f表示評價函數(shù)；ε表示加權常量。

然后，每只螞蟻從起始站出發(fā)，利用信息素信息搜尋下一站，直到搜尋到達終點站。通過評價函數(shù)對搜尋到的新線路進行判斷，假如搜尋獲得的新線路優(yōu)于當前的線路，則對當前線路進行更新替換。在線路搜索過程中，螞蟻主要是基于信息素強度和啟發(fā)式信息對下一站做出選擇，第k只螞蟻在站點i處選擇下一站為j站的概率yij可表示為式(6)。

(6)

式中，τij表示信息素強度；ηij表示啟發(fā)式信息；α和β分別表示信息素和啟發(fā)式信息的影響因子；Tk表示第k個螞蟻當前已經走過的站點集合。

2.2 客流重新分配

通過蟻群算法迭代出的一條新公交線路，將其替代原有公交線路，從而與原有的其他公交線路共同組成了一個新的公交網絡。在對新的公交網絡進行性能評價前，由于公交路線的改變，需要對網絡中的客流量進行重新分配。公交網絡進行客流重新分配后，再通過評價函數(shù)計算其函數(shù)值，才能真實反映出新公交網絡的運行性能。

客流重新分配方法常用的有均衡分配和最短路徑分配兩種。其中，均衡分配方法具有較高質量的分配解，但不適應于大規(guī)模的道路網絡。最短路徑分配方法運行速度快，但忽略了公交線路的運載能力，假定公交路線的運載能力是無上限的，與實際情況不符。一輛公交車輛的運營能力為發(fā)車頻次與標準載客量的乘積，本文采用最短路徑分配法對OD矩陣中的客流量進行重新分配，并對最短路徑中的每條線路進行了容量限制。分配方案流程圖[8]如圖3所示。

圖3 客流分配流程圖

2.3 信息素更新問題

信息素是蟻群個體間進行信息交流的重要信號，需要在蟻群完成路徑搜索后進行更新。在進行信息素更新前，首先對蟻群搜索到的路線按照上節(jié)客流量重新分配流程進行客流的重新分配，進而利用評價函數(shù)計算函數(shù)值，依據(jù)新的評價函數(shù)值進行信息素的更新。

信息素的更新主要包括消退和加強兩個部分[9]。消退是指模擬自然界的信息素特性，隨時間蒸發(fā)減少每條線路的信息素強度。加強是指對蟻群經過的路徑上的信息素進行加強。更新式如式(7)。

(7)

(8)

2.4 懲罰規(guī)則

公交網絡模型中對線路提出了約束條件，若蟻群搜索過程中出現(xiàn)過多不符合約束條件的解，將會降低公交網絡的運行性能。為抑制不符合約束條的解，引入了懲罰機制。主要對以下3種情況進行抑制。

(1)搜索路徑出現(xiàn)回路；

(2)路徑解的長度超出上限或下限；

(3)路徑解超出非直線系數(shù)。

當出現(xiàn)以上情況，信息素更新后，對應受懲罰的路徑進行信息素的額外削弱，削弱式[10]如式(9)。

(9)

式中，ρ表示信息素消減系數(shù)，通過調節(jié)系數(shù)的數(shù)值，可控制懲罰的強度。

3 實驗結果

將Mandl道路網絡作為實驗對象，利用蟻群搜尋算法進行公交線路的優(yōu)化，蟻群算法參數(shù)如表1所示。

表1 蟻群搜尋算法參數(shù)

公交線路優(yōu)化調整前后的公交線路站點順序如表2所示。

表2 公交線路站點順序優(yōu)化

對線路優(yōu)化前后的評價指標進行統(tǒng)計，如表3所示。

表3 評價指標對比

表3為優(yōu)化前后的評價指標對比。d0表示乘客直達目的地的占有率；d1表示乘客需換乘一次的占有率；d2表示乘客需要進行兩次換乘的占有率；du表示公交路線不滿意的占有率(即換乘大于2次或公交未能覆蓋)。通過實驗數(shù)據(jù)的對比可知，乘客的直達率由64.5%上升到84.7%，乘客的一次換乘率由22.8%下降至15.3%，乘客的不滿意概率由12.6%下降至0%，公交網絡的整體運行性能得到提升。

4 總結

本文將蟻群搜索算法應用于公交網絡的優(yōu)化問題，實現(xiàn)對公交網絡的局部性調整及優(yōu)化。設計了新型評價函數(shù)，并引入對不符合約束條件線路的懲罰規(guī)則，實驗結果可知公交網絡性能明顯提升，驗證了該方案的有效性。另外，可對線路調整規(guī)則問題進行更深入的研究，以進一步提升公交網絡運行性能。