基于和聲搜索算法的公交線路規(guī)劃方法研究

周 楊，王景升

(中國人民公安大學(xué)，北京 100038)

隨著車輛保有量的增加，城市交通壓力不斷增大，交通管理部門對公共出行方式越發(fā)重視。公交系統(tǒng)作為城市公共出行系統(tǒng)的骨架，連接城市的不同分區(qū)，在整合城市資源、提高城市路網(wǎng)運行效率等方面起到了重要作用。公交線路設(shè)計優(yōu)化需要解決居民換乘、等車耗時和公交運行成本等問題，涉及城市居民出行、便利、安全、環(huán)保和效益等方面，是城市公交系統(tǒng)的重點課題。我國關(guān)于公交線路的研究起步較晚，從20世紀80年代初開始，逐步形成建立數(shù)學(xué)模型，利用算法對模型求解的問題解決模式。

公交線路規(guī)劃問題可以視作最優(yōu)化問題，目前廣泛使用的既有Dijkstra(迪克斯特拉)算法和Floyd(弗洛伊德)算法等最短路徑算法，也有動態(tài)規(guī)劃算法、蟻群算法、粒子群算法、遺傳算法以及和聲搜索(harmony search, HS)算法等全局性搜索算法。較為傳統(tǒng)的最短路徑算法可以與圖論方法相結(jié)合，計算場景內(nèi)節(jié)點之間的最短線路[1-2]。全局性搜索算法通過引入不同參數(shù)對模型進行調(diào)節(jié)，在計算量較大時，擁有更強的全局搜索能力[3-4]。在大數(shù)據(jù)智能化的條件下，融合遙感技術(shù)、電子信息技術(shù)等技術(shù)理論，分析現(xiàn)有城市交通公交線路節(jié)點，以確定公交線網(wǎng)的優(yōu)化方向，例如：運營者運營成本最低，公交線路服務(wù)能力最大，居民換乘次數(shù)最少，出行時間最短等。再根據(jù)優(yōu)化方向建立線路或線網(wǎng)優(yōu)化的數(shù)學(xué)模型，結(jié)合約束條件選擇算法求解，進一步分析結(jié)果，進而得出公交線路或線網(wǎng)優(yōu)化方案。

但在實際應(yīng)用過程中，部分算法表現(xiàn)出一些不足。最短路徑算法無法同時考慮換乘次數(shù)和服務(wù)人數(shù)等問題，在解決多目標決策問題時表現(xiàn)不佳；智能搜索算法依賴參數(shù)設(shè)置，在不同適用條件下的計算能力有所差異，如：遺傳算法擴展性大，搜索能力強，但計算空間有限，易早熟收斂，形成局部最優(yōu)[4]；粒子群算法只利用最優(yōu)粒子傳遞信息，計算速度快，但缺乏速度的動態(tài)調(diào)節(jié)，易導(dǎo)致收斂精度低或不易收斂，不能有效解決組合優(yōu)化問題。

本文利用和聲搜索算法，基于不同算例和約束條件進行公交線路規(guī)劃計算，并通過與遺傳算法計算結(jié)果進行對比，驗證其實用性。

1 和聲搜索算法

和聲搜索算法是一種新近問世的啟發(fā)性全局搜索算法。靈感源自樂師創(chuàng)作和聲的過程。在音樂演奏中，樂師憑借記憶對不同樂器發(fā)出的音調(diào)進行選擇性調(diào)整，最終獲得“完美和聲”。Zong等[5]首先提出和聲搜索算法，該算法結(jié)構(gòu)簡單、需要調(diào)整的參數(shù)少、求解速度快、魯棒性強、全局搜索能力強且通用性高，在解決組合優(yōu)化問題上具有優(yōu)勢。

算法將樂器i(i=1,2,…,n)類比為目標方案中的第i個變量，產(chǎn)生的和聲Hj(j=1,2,…,n)視為優(yōu)化問題的第j個解向量，對和聲的評價即為目標函數(shù)的函數(shù)值。算法首先產(chǎn)生HMS(harmony memory size，和聲記憶庫大小)個解，將其放入和聲記憶庫(harmony memory，HM)，類比樂師的初始記憶，作為目標方案的初始解。之后隨機產(chǎn)生(0,1)的參數(shù)rand1和rand2，并引入和聲記憶庫取值概率(harmony memory considering rate, HMCR)和微調(diào)概率(pitch adjusting rate，PAR)。若rand1

有別于其他啟發(fā)式算法，和聲搜索算法的優(yōu)勢在于其包含記憶庫計算、局部擾動與隨機選擇的即興創(chuàng)作過程，在優(yōu)化算法集約化與多樣化的平衡中發(fā)揮了重要作用。

和聲搜索算法的特征如下：①在所有可能存在的向量中生成新的向量。②針對向量中的每個決策變量進行單獨考慮。③不需要對變量進行初始賦值。④算法中無進制轉(zhuǎn)換，計算速度較快。

和聲搜索算法流程如圖1所示。

圖1 和聲搜索算法流程

2 線路規(guī)劃的數(shù)學(xué)建模與計算

城市公交線路具有停靠節(jié)點多、總里程短等特點。在二維坐標系中放置坐標，模擬公交節(jié)點，利用Matlab語言，分別以服務(wù)總?cè)藬?shù)M最大、總行程時間T最小為目標函數(shù)，采用Matlab 2019a編寫和聲搜索算法程序并進行計算。和聲搜索算法對初始解的依賴性較大，且本試驗算例的計算量較小，為避免過早陷入局部最優(yōu)，因此和聲記憶庫及其取值概率較小，設(shè)置參數(shù)HMS為2，HMCR為0.3，PAR為0.1，bw為0.05，N為100。

坐標系節(jié)點設(shè)置如圖2所示，其中點1、4、8、11為固定節(jié)點，點2、3、5、6、7、9、10為可以選擇經(jīng)過的節(jié)點。點1和點11為確定的起點和終點。

圖2 坐標系節(jié)點設(shè)置

2.1 服務(wù)人數(shù)

公交線路規(guī)劃應(yīng)將服務(wù)更多居民作為重要目標之一。當前研究成果中通常將公交站點服務(wù)人數(shù)作為重要計算指標[3]，本試驗對規(guī)劃線路可能經(jīng)過的節(jié)點進行居住人數(shù)賦值，路段服務(wù)人數(shù)計算見式(1)。

(1)

式中，Mi為路段服務(wù)人數(shù)，人；Pi為路段上各節(jié)點服務(wù)人數(shù)，人/km；Li為路段長度，km；i為節(jié)點。

線路服務(wù)人數(shù)的目標函數(shù)見式(2)。

(2)

式中，M為線路總服務(wù)人數(shù)，人。

節(jié)點坐標及站點服務(wù)人數(shù)如表1所示。

表1 節(jié)點坐標及站點服務(wù)人數(shù)

以每兩個固定節(jié)點間路段的服務(wù)人數(shù)作為變量，輸入坐標及節(jié)點服務(wù)人數(shù)矩陣，經(jīng)過計算篩選，得出符合條件的最優(yōu)路徑為1-3-4-5-8-10-11，最大服務(wù)人數(shù)為4 582人。服務(wù)人數(shù)最大路徑(HS)如圖3所示，服務(wù)人數(shù)適應(yīng)度曲線(HS)如圖4所示。

圖3 服務(wù)人數(shù)最大路徑(HS)

圖4 服務(wù)人數(shù)適應(yīng)度曲線(HS)

2.2 行程時間

模型中的行程時間由換乘時間和行駛時間組成，假設(shè)換乘時間為定量，與上下客人數(shù)無關(guān)。行駛時間為行程長度與平均車速之比。行程時間的目標函數(shù)為

(3)

式中，T為行程時間，min；D為公交線路行程長度，km；d(i-1,i)為從第i-1個節(jié)點到第i個節(jié)點的距離，m；n為最后一個經(jīng)過的節(jié)點；v0為城市公交平均車速，km/h，取35 km/h；t0為平均?？繐Q乘時間，min，取3 min。

公交線路規(guī)劃問題屬于多目標決策問題，本試驗中的不同目標之間具有相對獨立性。根據(jù)《城市綜合交通體系規(guī)劃標準》(GB/T 51328—2018)[7]，公共交通線路非直線系數(shù)不得大于1.4，即目標函數(shù)的約束條件為：D≤1.4×d(0,n)。

不同目標路徑結(jié)果如表2所示。

表2 不同目標路徑結(jié)果

以圖2場景中線路不固定的3個路段分別作為3個變量(樂器)，通過對可選節(jié)點進行組合，并對不同組合結(jié)果下的路段長度對比選擇，計算得到符合條件的行程最短路徑為1-3-4-7-8-9-11，最短行程時間為39.414 7 min?？傂谐虝r間最短路徑如圖5所示，行程長度適應(yīng)度進化曲線(HS)如圖6所示。

圖5 總行程時間最短路徑

圖6 行程長度適應(yīng)度進化曲線(HS)

2.3 遺傳算法對比

本試驗采用遺傳算法(GA)進行算法效果對比，在相同節(jié)點場景下，以相同大小的初始解集進行計算，遺傳算法的參數(shù)設(shè)置如下：種群數(shù)Popsize為2，復(fù)制概率為0.3，交叉概率PC為0.4，變異概率PM為0.3，N為100。用Matlab進行編程，并繪制兩種目標函數(shù)情況下的適應(yīng)度曲線，服務(wù)人數(shù)適應(yīng)度進化曲線(GA)如圖7所示，行程長度適應(yīng)度進化曲線(GA)如圖8所示。

本試驗場景較為簡單，兩種算法都能夠在多次迭代后得到最優(yōu)解，因此本文以迭代次數(shù)作為指標對比兩種算法優(yōu)劣。對比圖4與圖7，在以最大服務(wù)人數(shù)為目標函數(shù)時，HS約25次迭代后收斂，GA約80次迭代后收斂；對比圖6和圖8，在以最短行程時間為目標函數(shù)時，HS約35次迭代后收斂，GA約75次迭代后收斂。相較于遺傳算法，和聲搜索算法采用十進制編碼，原理簡單，容易實現(xiàn)。

圖7 服務(wù)人數(shù)適應(yīng)度進化曲線(GA)

圖8 行程長度適應(yīng)度進化曲線(GA)

3 總結(jié)

本文以假設(shè)條件下的最短行程時間與最大服務(wù)人數(shù)為約束條件，基于和聲搜索算法提出公交線路規(guī)劃方法，結(jié)合算例，對約束模型下的起訖點及部分節(jié)點固定的公交線路進行計算篩選，采用遺傳算法對同一場景編程計算作為對照。對比試驗結(jié)果表明，和聲搜索算法在收斂速度上明顯優(yōu)于遺傳算法，相較于遺傳算法的二進制編碼，和聲搜索的十進制編碼方式更適合進行快速計算。和聲搜索算法作為最新的智能優(yōu)化算法，在固定節(jié)點公交線路的規(guī)劃問題上，具有可參考性，類似的規(guī)劃方法可用于解決班車、校車和定制公交等路線規(guī)劃問題。

相較于其他常用的最優(yōu)化算法，和聲搜索算法的參數(shù)設(shè)置較為簡單，一般依靠經(jīng)驗確定，在計算量較小的前提下，嘗試不同參數(shù)可在一定程度上避免陷入局部最優(yōu)，但在較為復(fù)雜的問題上缺乏理論指導(dǎo)，因此，在參數(shù)的選擇、不同選參條件下的結(jié)果對比以及通過融合其他智能優(yōu)化算法的思想進行算法改進等方面值得深入研究。