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

周 楊，王景升

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

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

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

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

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

1 和聲搜索算法

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

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

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

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

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

圖1 和聲搜索算法流程

2 線路規劃的數學建模與計算

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

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

圖2 坐標系節點設置

2.1 服務人數

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

(1)

式中，Mi為路段服務人數，人；Pi為路段上各節點服務人數，人/km；Li為路段長度，km；i為節點。

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

(2)

式中，M為線路總服務人數，人。

節點坐標及站點服務人數如表1所示。

表1 節點坐標及站點服務人數

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

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

圖4 服務人數適應度曲線(HS)

2.2 行程時間

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

(3)

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

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

不同目標路徑結果如表2所示。

表2 不同目標路徑結果

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

圖5 總行程時間最短路徑

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

2.3 遺傳算法對比

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

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

圖7 服務人數適應度進化曲線(GA)

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

3 總結

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

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