優化公交車調度的多目標遺傳算法模型

張思維，魏昕怡，邱桃榮

(南昌大學a.際鑾書院;b.信息工程學院，江西 南昌 330031)

公交車對社會影響巨大，對城市發展起著最基本的推動作用。公交車的站點布局、線路規劃、車型配備、票價制定、發車頻率和車輛調度反映了一個城市的管理水平，因此對公交調度的理論與應用研究具有相當的現實意義。與此同時，在我國公交優先發展和公交系統快速發展的政策背景下，通過對公交調度理論方法的研究可以有效提高城市公交系統的資源利用率，提高運營效率和服務品質。研究公交調度優化理論不僅是服務企業進行科學決策、提高資源利用率的需要、也是推進國家優先發展公交的戰略。

然而，公交的客流量不僅具有周期性和趨勢性，且易受天氣、突發事件、相鄰站點之間的相互作用等因素的影響，具有較強的隨機性。目前國內外關于公交調度優化的理論研究已有不少的成果。例如，趙靖等[1]考慮需求了起訖點及需求等級對響應型社區公交行車調度進行優化；韓霜等[2]、陳深進等[3]對公交調度的即時性和實時性進行動態調度研究；ZHONG X W等[4]利用基于列生成的退火模擬、特征分析等算法對公交調度進行優化；劉星程等[5]提出一種基于云計算和實時數據的公交車實時調度算法。隨著研究的深入，公交車的均衡滿載率[6]、異質性出行需求[7]、自動駕駛[8]等因素也廣泛被相關學者在公交調度領域進行理論研究。但這些算法的復雜度較高，且多利用居民出行調查數據進行驗證，無法進行大規模實際應用。此前的研究并未考慮到由于人們的工作時間的不同導致公交出行出現的明顯平高峰現象，公交調度的優化模型的魯棒性有待提升。

近年來，遺傳算法作為一種結構較為簡單的算法，憑借其優秀的全局搜索能力、信息并行處理能力、魯棒性等優點[9]，在許多計算機領域有廣泛的應用。彭穎等[10]利用遺傳算法對數據最大熵的概率分布進行計算，進一步拓寬了遺傳算法的運用范圍。姜婧等[11]將改進的遺傳算法運用到排課問題中，提高了算法的運行效率。

隨著公交硬件系統的更新換代，公交一卡通制度不斷升級以及IC卡的使用率不斷提升，使得IC數據的可信度大大提高。針對上述問題和背景，本文融合IC卡及GPS數據，考慮到公交客流量呈現的高峰期與平峰期趨勢，提出一種基于車輛運行成本、乘客出行成本為目標函數的多目標遺傳算法模型對城市公交調度進行優化，并驗證其可靠性。

1 基于多目標遺傳算法的公交車調度優化模型

1.1 公交車線路“高峰”和“平峰”定義

1.2.1 術語的定義

根據生活常識，高峰期和平峰期顯然可以通過對比不同時間內準備乘車人數(包括最后是乘公交車及最后乘坐其他交通工具的人)來定義。考慮到給定時間內準備乘車的人數難以統計得到數據以及最初想乘公交最后乘坐其他交通工具的人占比較小，本文忽略最初想乘公交最后乘坐其他交通工具的人，只考慮乘坐公交車的人，并為了數據收集的方便考慮用每趟公交車的實際載客量相關量來定義。

由于時段發車時間間隔不同，比如高峰期發車時間間隔短，本文使用每趟車的實際載客量?除以該趟車發車到下趟車發車的間隔時間Δt這個量(即平均每小時載客人數φ)來定義平峰期和高峰期。即：

1.2.2 “高峰”和“平峰”定義的合理性驗證

(1)驗證數據集

考慮到公交的運行易受道路基礎設施等外界因素的影響，本文選擇了受外界影響力較小的武漢市某快速公交作為研究對象。公交線路全長20 km，從始發站到終點站共24個站點。站點分布較為均勻，基本上1 km內有一個站點。該公交的運營時間為5:30～23:00。同時該公交型號一致，按照國家相關標準每輛車荷載100人，開車速度不超過25 km/h。同時研究當天的發車時間間隔在15，4.5以及6 min不等。

(2)驗證方法

本文統計出一天相應時間段(即每趟車發車到下趟車發車的時間段)的平均載客人數φi(i表示第i段時間)，為了排除偶然因素的影響，本文根據每段時間游客量得到載客人數的頻率，并畫出相應的頻率分布直方圖。根據該天公交的發車時間以及乘客人數計算出每段時間的平均載客人數φi。

通過曲線擬合可以得到一條較好的連續曲線。根據我們擬合出來的曲線，得出平均每小時載客人數的最大值M和最小值m，根據我們定義的系數s，t(0

·若某段時間平均每小時載客人數U≥m+(M-m)×t則視為高峰期。

·若某段時間平均每小時載客人數U≤m+(M-m)×s則視為平峰期。

(3)驗證的結果與分析

根據本文所定義的平高峰模型，繪制出平均載客人數的頻率分布直方圖，如圖1所示。并s=0.25，t=0.75，M=18.54人/min，m=2.88人/min。經過計算可知，高峰期為6:05～9:45，12:00～12:55，17:05～19:00。平峰期為10:00～11:30，14:45～16:30。其余時間段為過渡期。此結論與生活常識是一致的，因此可以認為本文之前指定的對“公交平高峰”定義是合理的。但本文發現φi擬合結果與客運量的結果不一致，在中午出現了小高峰現象。這可能與快速公交在中午的公交調度不合理導致，因此對快速公交的調度進行優化成為不可避免的問題。

time quantum/h

1.2 基于多目標遺傳算法的公交調度優化模型

1.2.3 模型假設

為了給模型創造一個穩定的環境，保證建模的方便和數據的正確性，本文對實際情況作出以下假設：

(1)不考慮惡劣天氣、汽車運行故障、堵車等多方面的外界因素對快速公交運行的影響；

(2)不考慮乘客上下車的時間，乘客均一次性上車。

(3)公交司機嚴格按照發車時刻表發車并準時到達各個站點。

(4)公交車以20km/h的速度行駛，不考慮公交車加速、擁堵或減速駕駛等因素。

(5)不考慮乘客在車內所產生的時間成本，乘客對公交服務的滿意度僅僅以其平均等車時間來衡量。

(6)假設在一個發車時間間隔內，客流量服從正態分布。

(7)所拿到的公交運營數據真實可信，能夠反映乘客的乘車時間、公交運行成本等運營關系。

1.2.4 多目標優化模型的構建

多目標優化是數學規劃的一個分支。研究多于一個的目標函數在給定區域上的最優化。本文從公共交通和乘客出行兩個方面的利益出發，考慮乘客的出行成本和公共交通的運行成本。考慮到不同的乘客由于個人原因會使得出行時間不一致，本文通過計算乘客在站等待時間作為乘客的出行成本；而公共交通的運行成本包括油費、人力勞務費等費用。將本文考慮的因素綜合起來建立以乘客出行成本最小和公共交通的運行成本最小的公交調度優化模型。

(1)乘客出行成本

本文乘客出行成本由乘客在站等待時間量化表示：

式中,T等是乘客出行成本，s是公交車站點編號，n是公交車編號，ts,n表示編號為n的公交車到達站點s的時間，qs是到達s站點總客流。?(t;μ,σ,a,b)是車站s乘客出行需求的概率密度分布，其表達式如下：

式中，φξ是對數正態分布的概率密度函數，Φ?是對數正態分布的累積分布函數，b、a是本文研究時間的始末點，φξ、Φ?表達式如下：

(2)公共交通的運行成本

C=(n1c1+n1c1+…)L

式中，C表示線路所有車輛的運行的總成本，ni(i=1,2,3…)、ci(i=1,2,3…)分別表示從車輛編號和單位公共交通的運營成本，L表示公交路線長度。

(3)模型整合

本文分別以乘客出行成本最小和公共交通的運行成本最小為目標，構建公交調度優化模型，模型如下所示。

minC=(n1c1+n1c1+…)L

s.t.ωmin≤ts,n-ts,n-1≤ωmax

式中，ωmin、ωmax分別為最大發車間隔與最小發車間隔。

1.2.5 多目標遺傳算法模型的構建

多目標優化是在現實各個領域中都普遍存在的問題，每個目標不可能都同時達到最優，必須各有權重。究竟要怎樣分配權重，這已經成為人們研究的熱點問題[12]。同時，根據生物進化論發展起來的遺傳算法也得到了人們的關注。將這兩者結合起來，能夠利用遺傳算法的全局搜索能力，避免傳統的多目標優化方法在尋優過程中陷入局部最優解，可以使解個體保持多樣性。其核心為遺傳三算子，即選擇、交叉和變異。

(1)編碼方式

為了實現考慮公交客流“平高峰”期的公交調度優化，遺傳算法的編碼方式與以往的編碼有所不同。染色體中的每一個基因代表一個最小時間間隔點，本文將其設置為1min，例如，如果研究時段為半小時則基因一共有30個。染色體上的基因為0表示平峰期不發車，基因為1表示在平峰期時段發車，基因為2表示高峰期不發車，基因為3表示在高峰時段發車，基因為4表示在過渡期時段不發車，基因為5表示在過渡期時段發車。

(2)初始化種群

根據高峰期和平峰期的定義可知，平高峰期是一個時間段，因此基于“高平峰”優化的染色體里的基因對于“高平峰”是連續的。根據本文之前定義的高平峰計算方法，一條染色體開始應該是連續的平(或高)峰期，再是連續的過渡時期，最后是連續的高(或平)峰期。

在實際的公共交通運營過程中，本文考慮到公交車長時間不發車情況為小概率事件。一般公交調度的發車間隔不會超過10min，本文除去了連續10個以上基因為“不發車”的染色體。

(3)選擇、交叉、變異操作

選擇操作是根據種群中的個體的適應度函數值所度量的優劣程度決定它在下一代是被淘汰還是被遺傳。在解碼的基礎上計算每個個體的序值和擁擠距離。本文通過序值前后進行選擇，若序值相同則比較個體的擁擠距離。通過相應的選擇方法對每個個體進行選擇，保留滿足條件的個體而淘汰不適應者，適者生存。并對保留下來的個體進行交叉、變異操作。

本文隨機設置了多個交叉點以便對不同染色體中的基因片段進行交換[13]。交換遺傳后，將更優秀的個體與父代個體進行非支配比較并放入下一代新種群中。通過對染色體的破壞和修復，將減小發車數和減少乘客在站等待時間作為變異操作。

(4)算法的設計

算法流程圖下圖2所示。

圖2 算法流程圖

3 實驗結果與分析

由于提出的算法考慮到了“平高峰”，因此本文在設置研究時段時必須同時包含客流高峰期及平峰期。本文取某公交5:30～13:00時間段作為研究對象。為了統計的方便，我們每隔10min將研究時段劃分成小階段進行客流量的統計。本文根據研究時段內的客流特征，對客流的到達概率分布進行正態分布的擬合，擬合結果如下表1所示：

表1 擬合參數表

根據公交車調度情況，根據本文對染色體配置可知發車間隔為1min，即公交車將以1min、2min、3min等1min的倍數進行調度。根據本文對染色體初始化安排設定ωmin=1min，ωmax=10min。設定種群規模為60、迭代次數為100次、交叉概率設為0.8、變異概率設為0.025。

根據以上對數據的分析和參數的設定，我們可以對研究時段的公交調度進行優化計算，生成非支配解集；并對乘客總等待時間的計算結果(取中值進行研究)進行升序排列。得到公交調度時序圖如下圖3所示：

Time senes/min

4 模型分析與討論

4.1 “平高峰”優化前后實驗結果對比分析

本文算法的一大創新點便是將“平高峰”引入到算法多目標遺傳算法模型當中，因此考慮“平高峰”前后優化對比是十分必要的。按照以往的多目標遺傳的經典算法，不考慮“平高峰”時，染色體的基因編碼方式有兩種：基因為0為不發車、基因為1為發車。本文將兩種優化前后的染色體基因序列分別進行測試，得到的結果如下表2所示。

表2 優化前后的成本對比結果表

通過測試我們可以清楚地看到優化前后的目標結果明顯優于優化前。優化后的乘客出行時間比優化前的數據降低了13.75%，同時公共交通的運行成本也降低了1.7%。不管是對于乘客還是對公交公司，優化后的公交調度方案均比優化前的成本要低。這也從結果的角度說明本文的算法的優化能力更加強悍。

4.2 “平高峰”優化前后乘載率對比分析

為了進一步對比分析優化前后的公交調度情況，本文引入了乘載率，即一定時間內反映線路上運行車輛乘客滿載程度的相對值。它是體現城市公交服務質量和水平的重要指標，也是公交營運調度部門編制營運作業計劃以及進行現場調度的依據之一。乘載率被定義為乘客對公交車座位的占有率，即實際乘載人數與公交車輛座位數的比值。

本文對優化前后的乘載率進行計算后得到的結果如下圖4所示。可以觀察到“平高峰”優化前的模型的乘載率起伏較大，甚至有個別時間段的乘載率達到2以上。而優化后的乘載率更趨于平穩，且乘載率幾乎收斂于1。

圖4 優化前后的乘載率對比結果圖

乘載率一定程度上反映了乘客的候車舒適度。由此可見，利用“平高峰”因素優化后的多目標遺傳優化模型不僅減少了公共交通的運行成本和乘客平均等待時間，還大大增加了乘客的候車舒適度。

5 結語

實驗結果表明，本文提出的基于“平高峰”因素的多目標遺傳優化模型相比與傳統的模型能夠更好地對公交調度進行優化。測試結果表明，本文提出的優化模型不僅能夠有效降低公交公司與乘客兩方面的成本，還能提升乘客的候車舒適度。在今后的對公交公司決策優化公交調度具有一定的參考意義。本文將針對以下方面做進一步研究：本文的目標優化模型只考慮到了兩個指標，可以利用兩個以上指標展開討論；進一步優化優化模型和數據處理方法，尋找優化能力更強的算法。