基于遺傳算法的智能公交調度系統的研究

李清逸 李文娟 謝 鵬 劉向東 閆利霞

（蘇州城市學院，江蘇 蘇州 215000）

隨著我國國力的不斷增強，國民經濟飛速發展，城市化建設也得到不斷推進，城市人口逐漸上升，公共交通和私家車成為城市居民的出行主要工具，私家車數量的增加造成了較為嚴重的空氣污染和交通擁堵，不斷增長的城市人口為公共交通帶來了巨大壓力?？茖W規劃交通，合理調度資源，建設現代化的城市智能交通調度系統迫在眉睫。

智能公交調度系統在實際公共交通中的應用增多，許多學者針對出現的問題和不足采用不同的算法進行研究和改善。其中遺傳算法、啟發式算法、BP神經網絡和其他智能優化算法對智能公交的調度優化方面有較大幫助。與其他優化算法相比，遺傳算法的搜索從群體出發，在解決多輛公交調度的優化問題方面有較大優勢。

1 智能公交調度系統現狀

2021年智能公交領域進入發展冷卻期，全國城市公交客流量大幅下降，但智能公交調度仍是城市公交發展的主要方向。隨著智能公交調度系統的不斷發展，一線城市與非一線城市的差距逐漸擴大。一線城市的發展趨于飽和，非一線城市的智能化基礎設施完善程度有待提高、信息化基礎較為薄弱、城市信息化設備老舊等因素為智能公交調度系統的發展帶來巨大挑戰。

在政策支持、技術進步、城市化進程和機動車保有量持續攀升等多重因素推動下，我國智能交通行業規模將穩步上升。綜合政策規劃和交通運輸行業細分市場的發展狀況，預計到2026年我國智能交通行業市場規模將突破4 000億元，年均復合增長率在16%左右，智能公交系統的整體發展趨勢穩步上升。2021～2026年中國智能交通行業市場規模預測如圖1所示。

圖1 2021～2026年中國智能交通行業市場規模預測

2 公交調度模型

公交調度指根據線路實時客流量情況，確定線路中各時間段發車次數及發車間隔，制成發車時間表，借此指揮城市公交的運營。

2.1 公交調度

公交調度分為動態調度和靜態調度。動態調度指調度員在公交發車后，根據道路交通情況、車輛運行情況以及突發事件等其他實時信息，對公交的行車間隔等運營信息進行調整，保證公交車運行通暢，維持正常設定的服務水平。在動態調度中遺傳算法應用較多，遺傳算法能夠較好地解決陷入局部最優解的問題。靜態調度主要是確定線路上的車輛配比和發車計劃，在滿足客流需求的條件下，使城市公交的運營變得科學高效。靜態調度是公交調度的基礎，文章主要從靜態調度入手，研究基于遺傳算法的公交調度系統。

2.2 公交調度優化問題分析

調度的目的是合理規劃資源分配，制定科學高效的行車計劃，在運能供應充足和滿足客流需求的條件下，提高行車速度和公里數，節約公司成本，公交調度的核心問題是保證乘客和公交公司的利益最大化。乘客利益方面，候車時間長短是乘客滿意度的重要因素，如果要縮短乘客候車時長，需要增加運營的公交車數量，提高公交車到站頻率。對公交公司而言，增加公交車運行數量，不符合經濟利益，也為城市道路容量帶來壓力。公交公司利益方面，公交公司的收入要承擔公交車的日常維護、折損、燃油和人員工資等問題。乘客利益與公交公司利益成對立狀態，找出調度優化的平衡點是問題的關鍵。

2.3 模型建立

建立的目標函數包括乘客利益最大化，即乘客的平均等車時間最短；公交公司利益最大化，公司的發車次數最少。

目標函數如下：

式中：C1——乘客候車成本；σ1——乘客單位時間內的候車成本（元/min）；a——站點；b——車輛數；C2——公司運營成本；σ2——一輛公交單位時間內的運營成本（元/min）；ρ——a站的到站率；Tb，a——第b輛車到達a站的時間；tb，a——第b輛車離開a站的時間。

為了使目標函數滿足乘客利益和公司利益的平衡，達到雙目標優化的效果，需要分別對乘客候車成本和公交公司運營成本進行加權整合，加權系數分別為α、β，約束條件為最大發車間隔時間，文章選取為10 min，最小發車間隔時間為1 min，則目標函數為（其中min為函數的最小值，即目標函數C的結果為最小成本）：

3 基于遺傳算法的智能公交調度

靜態公交車調度是多目標優化問題，遺傳算法的搜索從群體出發，經過編碼，選擇，交叉，變異四個過程，能夠快速找出問題的最佳解決方案。

3.1 基于遺傳算法的公交調度模型求解

（1）編碼。由于遺傳算法不能直接處理問題空間的參數，必須通過編碼將需要求解的問題表示成遺傳空間的染色體或者個體[1]。系統采用浮點數編碼中的實數編碼較為簡便，以公交的發車時間為變量，客流量峰值控制發車間隔。根據發車時段劃分生成發車間隔，結合種群大小和一段時間內首末班車的發車時間和截止時間，完成初始種群選取。實數算法的優勢在于種群的個體就是問題的解，不需要使用函數進行轉換，且個體的優良基因段將會繼續遺傳到下一代，使得每一代都有進化。

（2）選擇操作。選擇操作是為了在群體中開展優勝劣汰。采用選擇操作中的輪盤賭選擇法和最佳個體保存法，使適應度值越好的個體被選擇的概率越大。在遺傳中每一代先保留一個最佳個體，且個體中不含重復的基因片段，按照選擇概率劃分區域將個體放入輪盤，然后對隨機算子選中的個體進行配對。

（3）交叉操作。采用單點交叉可以得到更多合理的發車時間表。通過隨機算子決定是否進行交叉操作，進行交叉的頻率受設置的交叉率影響，個體在隨機選擇的位置點上進行交叉，得到兩個新的個體，如果新個體中含重復片段，則重新選擇交叉位點，直至新個體中不含重復的基因片段。

（4）變異操作。采用實數編碼限制了變異基因的變異范圍，不允許新個體中含有重復的基因片段。由隨機算子決定是否進行變異操作，若進行編譯操作，隨機選擇變異染色體的某個基因，將其轉化為二進制編碼后隨機選擇一位二進制位點進行變。如果變異后所選基因的值為0、1或者不在可變異區間內則重新進行變異。

3.2 算法的應用

（1）初始化變量。運算參數設定包括乘客的候車成本為1 元/min；公司運營成本為2 元/min，線路的站點總數為25個，線路的車輛總數為10輛，首班車時間為6:00，末班車的時間為21:00，發車次數為50次，平均運行時間為20 km/h。公交的到站率由每個站點的購票人數和發車間隔求出，將公交的發車時間到截止時間劃分為幾個時段區間，發車次數由預設定給出，具結合實際公交客流量數據樣例。

（2）不同權重下最小成本的計算結果。模型中的權重取值代表利益中乘客利益和公交公司利益的占比大小，目標函數中權重的不同取值代表不同的最小成本，按照參數和蘇州公交公司某條線路單日客流量數據進行計算得到不同權重下的計算結果，在α=0.5，β=0.5時（α+β=1）最小成本明顯低于其他測試值。最小成本隨α占比變化如圖2所示。

圖2 最小成本隨α占比變化

（3）不同交叉率、變異率、迭代次數下平均成本的計算結果。交叉率會對實驗結果產生不同程度的影響，當交叉概率P1=0.7時，種群的平均成本較小，優于其他交叉概率下的測試值。

不同變異率對平均成本的影響較大，當變異概率P2=0.000 5時的平均成本優于其他測試值。

平均成本隨迭代次數的增加而減小，當迭代次數n=400時的平均成本趨于穩定狀態。

平均成本隨交叉概率變化如圖3所示。

圖3 平均成本隨交叉概率變化

平均成本隨變異概率變化如圖4所示。

圖4 平均成本隨變異概率變化

平均成本隨迭代次數變化如圖5所示。

圖5 平均成本隨迭代次數變化

4 結語

隨著時代的快速發展，解決城市交通擁堵的問題迫在眉睫，大力發展城市公交，優化城市公交調度系統能夠有效解決交通擁堵問題，結合遺傳算法、科學規劃交通以及合理調度資源為城市公交的發展帶來更多可能。在未來的實踐中，應結合動態調度分析在各類異常情況下的調度決策問題，聯合實際城市公交現狀找到問題的更優解，形成更加成熟的現代化城市公交調度系統。