基于改進(jìn)蟻群算法的公交網(wǎng)絡(luò)路徑優(yōu)化

武可心

(西安交通工程學(xué)院 交通運(yùn)輸學(xué)院，陜西 西安 710000)

0 引言

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

1 公交網(wǎng)絡(luò)模型

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

圖1 Mandl道路網(wǎng)絡(luò)示意圖

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

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

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

(1)

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

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

(2)

為了對公交線路網(wǎng)絡(luò)的優(yōu)劣進(jìn)行定量評價(jià)，需要提出公交網(wǎng)絡(luò)的評價(jià)函數(shù)，該網(wǎng)絡(luò)的性能評價(jià)函數(shù)為式(3)。

(3)

約束條件如式(4)。

(4)

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

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

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

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

圖2 蟻群搜索算法流程圖

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

2.1 線路調(diào)整規(guī)則

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

(5)

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

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

(6)

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

2.2 客流重新分配

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

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

圖3 客流分配流程圖

2.3 信息素更新問題

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

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

(7)

(8)

2.4 懲罰規(guī)則

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

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

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

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

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

(9)

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

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

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

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

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

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

對線路優(yōu)化前后的評價(jià)指標(biāo)進(jìn)行統(tǒng)計(jì)，如表3所示。

表3 評價(jià)指標(biāo)對比

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

4 總結(jié)

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