改進(jìn)的蟻群算法在定制公交路徑規(guī)劃中的應(yīng)用*

王 奔 張 森 劉月錕 武 曲 劉秀燕

（青島理工大學(xué)信息與控制工程學(xué)院 青島 266525）

1 引言

近年來市民出行需求趨向多元化，公交服務(wù)模式單一問題日益凸顯，公共交通多元化已經(jīng)成為必然趨勢［1］。定制公交旨在解決高峰期居民上下班和傳統(tǒng)公交服務(wù)質(zhì)量差等問題。為客戶群規(guī)劃路線，一站直達(dá)，能夠很好地彌補(bǔ)傳統(tǒng)公交在靈活性、舒適性和便捷性等方面的不足。早期，國內(nèi)外在定制公交研究上重點集中在運(yùn)營方式、監(jiān)管政策的制定［2］。而定制公交的線路規(guī)劃作為公交運(yùn)營發(fā)展的重要環(huán)節(jié)和核心問題，對提高定制公交的實踐價值具有重要作用［3］。

對于定制公交路徑規(guī)劃的研究應(yīng)用，在站點的選址與布局方面，文獻(xiàn)［4］將選址布局抽象為聚類問題，通過K-means 算法求得站點分布，并根據(jù)運(yùn)營成本最低原則設(shè)計公交路徑。文獻(xiàn)［5］將成本因素考慮在內(nèi)，依托現(xiàn)有公交站點進(jìn)行路線規(guī)劃，提升了公交站點利用率。在線網(wǎng)優(yōu)化方面，文獻(xiàn)［6］將乘客抵達(dá)時間和運(yùn)營成本作為優(yōu)化目標(biāo)，并以直接連接能力和換乘次數(shù)為約束條件，構(gòu)建線路優(yōu)化模型。文獻(xiàn)［7］將快速軌道交通系統(tǒng)中的“一路一線”思想融入公交路網(wǎng)規(guī)劃，設(shè)計了一種“逐條布設(shè)，優(yōu)化成網(wǎng)”和“一路一線”的線網(wǎng)優(yōu)化方法。文獻(xiàn)［8］將時間、上座率、路徑長度三大指標(biāo)作為約束，建立以最大運(yùn)營效益和最大服務(wù)覆蓋率雙目標(biāo)線路優(yōu)化模型，并給出了求解的改進(jìn)蟻群算法。文獻(xiàn)［9］從公司運(yùn)營成本和乘客利益出發(fā)，建立了可變線路式公交調(diào)度模型，并采用遺傳算法求解。文獻(xiàn)［10］以經(jīng)營費(fèi)用、乘客的出行時間為優(yōu)化目標(biāo)，車輛人數(shù)限制、乘客上下車時間窗、不確定乘客等車時間為約束，建立了多目標(biāo)魯棒優(yōu)化模型并采用改進(jìn)的NSGA-Ⅱ算法進(jìn)行求解。在線路規(guī)劃求解算法方面，傳統(tǒng)的路徑規(guī)劃算法有Dijkstra算法［11］、A*算法［12］等。隨著智能仿生學(xué)算法的不斷發(fā)展，蟻群算法［13］、粒子群算法［14］等智能算法被應(yīng)用到路徑規(guī)劃上。蟻群算法最早用來求解旅行商問題。現(xiàn)主要應(yīng)用于車輛運(yùn)輸調(diào)度、機(jī)器人路徑規(guī)劃等問題。螞蟻在覓食過程中分泌信息素，蟻群通過信息素進(jìn)行交流，利用群體智能逐漸找到最優(yōu)路線。但隨著不同路徑信息素的差異增大，存在易陷入局部最優(yōu)解，前期隨機(jī)性較大，導(dǎo)致收斂速度慢等問題。文獻(xiàn)［15］提出首尾雙向搜索思想來提高算法的全局搜索能力。文獻(xiàn)［16］提出變異因子策略和狼群分配策略，改進(jìn)轉(zhuǎn)移公式，提高了蟻群尋優(yōu)效率。文獻(xiàn)［17］改變了按照經(jīng)驗設(shè)置參數(shù)的慣用模式，用粒子群算法對參數(shù)進(jìn)行優(yōu)化，節(jié)省了時間，尋優(yōu)結(jié)果得到改善。

綜上所述，國內(nèi)外線路優(yōu)化問題主要集中在公交選址布局與線路優(yōu)化模型的建立層面，僅有少量關(guān)于定制公交路徑求解算法及其優(yōu)化問題的研究。在路徑規(guī)劃算法中，蟻群算法求解精確度高、收斂速度快、尋優(yōu)能力強(qiáng)，能很好地和定制公交路徑規(guī)劃問題結(jié)合起來，但存在易陷入局部解、收斂速度慢、參數(shù)設(shè)定優(yōu)劣直接影響最優(yōu)解等缺點。因此，本文提出一種改進(jìn)的蟻群算法綜合路徑規(guī)劃方案，通過改進(jìn)雙向搜索策略，加入狼群分配策略，從而增強(qiáng)算法的全局搜索能力，提升收斂效率。另外，以定制公交運(yùn)營成本和乘客上座率為優(yōu)化目標(biāo)，公交容量限度、乘客預(yù)定上車時間為約束條件構(gòu)建綜合評估模型，作為路網(wǎng)優(yōu)化的評價標(biāo)準(zhǔn)。為合理設(shè)定參數(shù)，本文使用收斂能力強(qiáng)的粒子群算法對參數(shù)調(diào)優(yōu)。最后，通過實驗仿真驗證了算法的有效性。

2 環(huán)境建模

本文針對定制公交所處的工作環(huán)境進(jìn)行二維空間建模。由于公交行駛路徑是點對點的交互模式，因此可將公交路線抽象成多個點連接而成的復(fù)雜網(wǎng)絡(luò)，采用可視圖法進(jìn)行建模。

如圖1 所示，本文定制公交站點布局依托實際公交站點，將路網(wǎng)結(jié)構(gòu)抽象為二維網(wǎng)格。用節(jié)點表示公交站點，節(jié)點間連線表示路段。另外，每一個站點根據(jù)所在的位置編號為xij，并假設(shè)x11為始發(fā)站，x66為終點站。相鄰站點之間距離用disij表示，各站點的預(yù)計乘車人數(shù)用peoij表示。從理論上講，定制公交在行駛過程中會有很多方向，但考慮到環(huán)境模型的復(fù)雜性，本文設(shè)定公交車定向行駛過程中共有兩個運(yùn)動方向：U和L，定制公交每步只能移動到相鄰的一個站點。

圖1 定制公交路網(wǎng)模型

3 傳統(tǒng)蟻群算法

傳統(tǒng)蟻群算法應(yīng)用在定制公交路徑規(guī)劃中的大致流程為：初始化、搜索路徑、更新禁忌表和信息素［18］。首先初始化蟻群算法的參數(shù)，將螞蟻放置在起點，根據(jù)移動規(guī)則，螞蟻不斷向前行走直至找到終點，并將移動的位置加入到禁忌表中。對于螞蟻k從當(dāng)前節(jié)點i選擇節(jié)點j的轉(zhuǎn)移概率是根據(jù)信息素濃度和啟發(fā)式函數(shù)確定的，轉(zhuǎn)移概率由式（1～2）確定。

為避免殘留信息過多使得算法陷入局部最優(yōu)，在螞蟻循環(huán)一次之后，要對每條路徑上的信息素按式（3～4）進(jìn)行更新。

式（3～4）中，Q 為常量，表示信息素強(qiáng)度；ρ為信息素?fù)]發(fā)系數(shù)，取值為0～1；m為螞蟻數(shù)量；為螞蟻k在路徑（i，j）中留下的信息素；Lk為螞蟻k 在本次循環(huán)中走過的路徑總長度。

4 改進(jìn)的蟻群算法

4.1 改進(jìn)的雙向路徑搜索策略

在傳統(tǒng)的蟻群算法中，所有螞蟻全部從起始點向目標(biāo)搜索，為此文獻(xiàn)［15］將所有螞蟻平均分為兩組：A 組、B 組，A 組由起始點向終點搜索，B 組由終點向起始點搜索。兩組的螞蟻相遇時，將兩者的路徑連接得到一條搜索路徑，提高了搜索效率，但是使得算法的全局搜索能力提升不足。因此，本文引入信息交流轉(zhuǎn)移因子，使相遇的兩只螞蟻可以選擇走彼此已走過的路線，也可以繼續(xù)隨機(jī)搜索。

式（5）表示兩只螞蟻相遇的條件，其中meetij為螞蟻i與螞蟻j是否相遇。式（6）表示兩只螞蟻是否選擇彼此路徑的判斷條件，1 為選擇，0 則不選擇；rand為隨機(jī)值，表示信息交流轉(zhuǎn)移概率；ps為常數(shù)，表示信息交流轉(zhuǎn)移因子，如果rand大于此常數(shù)表示兩螞蟻選擇彼此的路徑而進(jìn)行轉(zhuǎn)移。

4.2 基于狼群分配的信息素更新策略

隨著迭代次數(shù)的增加，各路徑信息素會存在堆積或揮發(fā)至0 的情況。本文參照文獻(xiàn)［16］使用狼群分配策略，依照“強(qiáng)者生存”的更新機(jī)制進(jìn)行分配［19］。在迭代過程中，參照狼群算法中的“論功行賞”分配策略，對每代效果好的路徑進(jìn)行獎賞，對效果差的路徑進(jìn)行懲罰。加入狼群分配策略后，信息素的更新規(guī)則如式（7～9）所示。

4.3 綜合評估模型

啟發(fā)式函數(shù)ηij表示螞蟻由節(jié)點i 轉(zhuǎn)移至節(jié)點j的期望程度，傳統(tǒng)蟻群算法中的定義如式（2）。而對于定制公交路徑規(guī)劃問題來說，衡量一條路線的標(biāo)準(zhǔn)不僅僅是參考路線的長度，應(yīng)額外考慮公交車在行駛過程中載客的數(shù)量以及消耗的成本等因素。因此本文以公交運(yùn)營成本和乘客上座率作為優(yōu)化目標(biāo)，車輛核載人數(shù)、乘客預(yù)定時間為約束條件建立綜合評估模型，模型的解充分反映了由節(jié)點i轉(zhuǎn)移至節(jié)點j的綜合消耗，并以此來改進(jìn)啟發(fā)式函數(shù)。

式（10～12）表示綜合評估模型，式（13）表示改進(jìn)的啟發(fā)式函數(shù)，其中evaij為節(jié)點i 轉(zhuǎn)移至節(jié)點j 的綜合消耗；peoj為下一站j的實際乘車人數(shù)；N為定制公交核載人數(shù)，n 為所經(jīng)站點總數(shù)；Vj 表示站點j 的預(yù)計乘車人數(shù)；ptji為j站點中第i個人預(yù)定上車時間，pt∈[T，T+X]，其中T 表示當(dāng)前班次車輛發(fā)車時間，X 為不確定乘車等車時間；a、b 為調(diào)整參數(shù)，取值為0～1，當(dāng)a取值為1、b取值為0時式（13）退化為式（2）。

4.4 基于改進(jìn)粒子群的參數(shù)優(yōu)化

蟻群算法中，參數(shù)取值有非常大的影響。為此利用粒子群算法較強(qiáng)全局收斂的能力，對蟻群算法中的重要參數(shù)進(jìn)行優(yōu)化，通過重復(fù)調(diào)用蟻群算法在多次迭代過程中完成算法的參數(shù)優(yōu)化，在此過程中根據(jù)式（15）作為評判參數(shù)優(yōu)劣的標(biāo)準(zhǔn)。

式（14）中，i、j 為路徑Mt中的相連節(jié)點，evaij的定義如式（10）。式（15）中，fit 為適應(yīng)度函數(shù)值；syn(Mt)由式（14）計算得來；ite 為算法得出最優(yōu)解時的最少迭代次數(shù)；λ和μ為取值0～1 的常數(shù)，表示適應(yīng)度函數(shù)和最少迭代次數(shù)的權(quán)重系數(shù)。

首先初始化粒子群體，將每個粒子搜索到的參數(shù)帶入改進(jìn)后的蟻群算法中，根據(jù)式（15）計算出粒子的適應(yīng)度，最后選擇最優(yōu)的參數(shù)。在搜索過程中，每個粒子的移動速度和位置按式（16～17）進(jìn)行變化。

式（16～17）中，c1和c2為學(xué)習(xí)因子；ω為慣性因子；r1和r2是取值0～1 的隨機(jī)數(shù)，用于調(diào)整粒子的搜索空間；pbest 和gbest 分別為個體最優(yōu)值和群體最優(yōu)值。

由于傳統(tǒng)的粒子群算法極易陷入局部最優(yōu)問題，常常會對其參數(shù)進(jìn)行改進(jìn)［20］，采用動態(tài)改變慣性因子的方法來跳出局部最優(yōu)。若使用遞減函數(shù)來改變慣性因子，當(dāng)算法陷入局部最優(yōu)時，慣性因子也會變得比較小。因此使用一個函數(shù)來使其陷入局部最優(yōu)時的慣性因子變得比較大，這樣算法可以繼續(xù)搜索，從而增強(qiáng)全局搜索能力。

通過以上分析可知，這樣的函數(shù)應(yīng)先遞增后遞減，在陷入局部最優(yōu)的點附近達(dá)到最大值。設(shè)定一個二次函數(shù)來改變慣性因子的大小，如式（18）。

式（18）中，k 為迭代次數(shù)。a、b 和c 是常數(shù)，通過待定系數(shù)法來求出它們的取值。

5 結(jié)果與分析

為驗證改進(jìn)算法的有效性，采用Matlab進(jìn)行仿真實驗。構(gòu)建多個不同規(guī)模的路網(wǎng)模型，分別從最短路徑規(guī)劃、最優(yōu)綜合指標(biāo)路徑規(guī)劃兩方面來驗證改進(jìn)后算法的優(yōu)越性。

5.1 最短路徑規(guī)劃

由于定制公交路徑規(guī)劃涉及到路徑長度、乘車人數(shù)等因素，若直接采用綜合評估函數(shù)很難直觀體現(xiàn)改進(jìn)算法在常規(guī)路徑規(guī)劃上的優(yōu)勢，因此，本文先將路徑長度作為唯一指標(biāo)進(jìn)行驗證仿真。為充分體現(xiàn)改進(jìn)算法的性能，選用規(guī)模為50×50 的路網(wǎng)結(jié)構(gòu)進(jìn)行仿真。

首先，傳統(tǒng)蟻群算法、采用雙向搜索策略的文獻(xiàn)［15］和本文算法各自得出的路徑如圖2 所示，每代最優(yōu)路徑長度和迭代次數(shù)對比如圖3 所示。最終結(jié)果表明，本文算法的全局搜索能力有了明顯提升，得出的路徑更短，但收斂能力提升不足。

圖2 三個算法最優(yōu)路徑

圖3 三個算法指標(biāo)比較

傳統(tǒng)蟻群算法得到的最優(yōu)路徑長度為302.4。文獻(xiàn)［15］對應(yīng)的路徑長度為290.94，相比之下，文獻(xiàn)［15］在全局搜索能力方面有所提升。而本文算法進(jìn)一步增強(qiáng)了算法的全局搜索能力，找出了長度為285.88的最優(yōu)路徑。

此外，傳統(tǒng)蟻群算法在迭代41 次后收斂，文獻(xiàn)［15］所用算法在迭代29 次后收斂，而本文算法在迭代36 次后收斂。分析可知，文獻(xiàn)［15］和本文算法相較傳統(tǒng)算法在收斂速度方面有所提升，但本文算法在收斂速度上弱于文獻(xiàn)［15］。

5.2 綜合模型路徑規(guī)劃

由上述結(jié)論可知，本文算法相比于傳統(tǒng)蟻群算法有了明顯提升。而在定制公交路徑規(guī)劃問題中，路徑長度不再是唯一指標(biāo)，還需考慮到上座率。在兩者之間達(dá)到平衡點，才能獲得利潤最大值。

為了驗證本文算法綜合性能的優(yōu)越性，將綜合評估函數(shù)作為適應(yīng)度函數(shù)的指標(biāo)進(jìn)行驗證仿真。如式（14）所示，綜合評分越低，代表該路徑越好。為了更直觀證明算法的有效性，選用6×6 的簡易路網(wǎng)結(jié)構(gòu)。

首先，傳統(tǒng)蟻群算法和本文算法所求路徑如圖4 所示。各算法綜合得分對比圖如圖5 所示。另外，將兩種算法的各類指標(biāo)列入表1 中。由表1 可知，本文算法所求路徑在長度上稍長于傳統(tǒng)算法，但是乘車人數(shù)明顯增多，綜合評分也低于傳統(tǒng)算法，故而說明了本文算法以綜合評分為標(biāo)準(zhǔn)，很好地兼顧了行駛距離和乘車人數(shù)，綜合優(yōu)化性能相較傳統(tǒng)算法得到提升。

表1 傳統(tǒng)與本文算法指標(biāo)對比

圖4 傳統(tǒng)與改進(jìn)算法解得的路徑

圖5 傳統(tǒng)與本文算法綜合得分

分析可知，6×6 的路網(wǎng)結(jié)構(gòu)比較簡單，兩種算法皆能對所有路徑進(jìn)行遍歷。傳統(tǒng)算法將行駛距離作為唯一指標(biāo)，求得該路網(wǎng)模型的最短路徑。而本文算法綜合考量行駛距離和乘車人數(shù)，求得該路網(wǎng)模型在兩指標(biāo)下的最優(yōu)路徑。相比之下，本文算法更加符合公司利益，達(dá)到了便捷乘車和經(jīng)濟(jì)效益的統(tǒng)一。

6 結(jié)語

本文研究了面向定制公交路徑規(guī)劃問題的蟻群算法，分析了傳統(tǒng)蟻群算法解決定制公交問題的優(yōu)缺點，并提出了一種改進(jìn)的蟻群算法。本文首先引入改進(jìn)的雙向搜索策略，擴(kuò)大算法前期搜索范圍；引入狼群分配策略改進(jìn)信息素更新原則，進(jìn)一步增強(qiáng)了全局搜索能力；另外，建立了綜合評估模型，既降低了運(yùn)營成本，又增加了乘客上座率；最后，引入改進(jìn)的粒子群算法進(jìn)行優(yōu)化，將綜合指標(biāo)帶入適應(yīng)度函數(shù)調(diào)校出最優(yōu)參數(shù)。實驗結(jié)果表明，改進(jìn)后的算法在最短路徑規(guī)劃和綜合指標(biāo)路徑規(guī)劃方面有了顯著提升，但是算法收斂速度有待加強(qiáng)。