改進的蟻群算法在定制公交路徑規劃中的應用*

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

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

1 引言

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

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

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

2 環境建模

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

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

圖1 定制公交路網模型

3 傳統蟻群算法

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

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

式（3～4）中，Q 為常量，表示信息素強度；ρ為信息素揮發系數，取值為0～1；m為螞蟻數量；為螞蟻k在路徑（i，j）中留下的信息素；Lk為螞蟻k 在本次循環中走過的路徑總長度。

4 改進的蟻群算法

4.1 改進的雙向路徑搜索策略

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

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

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

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

4.3 綜合評估模型

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

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

4.4 基于改進粒子群的參數優化

蟻群算法中，參數取值有非常大的影響。為此利用粒子群算法較強全局收斂的能力，對蟻群算法中的重要參數進行優化，通過重復調用蟻群算法在多次迭代過程中完成算法的參數優化，在此過程中根據式（15）作為評判參數優劣的標準。

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

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

式（16～17）中，c1和c2為學習因子；ω為慣性因子；r1和r2是取值0～1 的隨機數，用于調整粒子的搜索空間；pbest 和gbest 分別為個體最優值和群體最優值。

由于傳統的粒子群算法極易陷入局部最優問題，常常會對其參數進行改進［20］，采用動態改變慣性因子的方法來跳出局部最優。若使用遞減函數來改變慣性因子，當算法陷入局部最優時，慣性因子也會變得比較小。因此使用一個函數來使其陷入局部最優時的慣性因子變得比較大，這樣算法可以繼續搜索，從而增強全局搜索能力。

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

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

5 結果與分析

為驗證改進算法的有效性，采用Matlab進行仿真實驗。構建多個不同規模的路網模型，分別從最短路徑規劃、最優綜合指標路徑規劃兩方面來驗證改進后算法的優越性。

5.1 最短路徑規劃

由于定制公交路徑規劃涉及到路徑長度、乘車人數等因素，若直接采用綜合評估函數很難直觀體現改進算法在常規路徑規劃上的優勢，因此，本文先將路徑長度作為唯一指標進行驗證仿真。為充分體現改進算法的性能，選用規模為50×50 的路網結構進行仿真。

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

圖2 三個算法最優路徑

圖3 三個算法指標比較

傳統蟻群算法得到的最優路徑長度為302.4。文獻［15］對應的路徑長度為290.94，相比之下，文獻［15］在全局搜索能力方面有所提升。而本文算法進一步增強了算法的全局搜索能力，找出了長度為285.88的最優路徑。

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

5.2 綜合模型路徑規劃

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

為了驗證本文算法綜合性能的優越性，將綜合評估函數作為適應度函數的指標進行驗證仿真。如式（14）所示，綜合評分越低，代表該路徑越好。為了更直觀證明算法的有效性，選用6×6 的簡易路網結構。

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

表1 傳統與本文算法指標對比

圖4 傳統與改進算法解得的路徑

圖5 傳統與本文算法綜合得分

分析可知，6×6 的路網結構比較簡單，兩種算法皆能對所有路徑進行遍歷。傳統算法將行駛距離作為唯一指標，求得該路網模型的最短路徑。而本文算法綜合考量行駛距離和乘車人數，求得該路網模型在兩指標下的最優路徑。相比之下，本文算法更加符合公司利益，達到了便捷乘車和經濟效益的統一。

6 結語

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