優(yōu)化公交車調(diào)度的多目標遺傳算法模型

張思維，魏昕怡，邱桃榮

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

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

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

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

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

1 基于多目標遺傳算法的公交車調(diào)度優(yōu)化模型

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

1.2.1 術(shù)語的定義

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

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

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

(1)驗證數(shù)據(jù)集

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

(2)驗證方法

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

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

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

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

(3)驗證的結(jié)果與分析

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

time quantum/h

1.2 基于多目標遺傳算法的公交調(diào)度優(yōu)化模型

1.2.3 模型假設(shè)

為了給模型創(chuàng)造一個穩(wěn)定的環(huán)境，保證建模的方便和數(shù)據(jù)的正確性，本文對實際情況作出以下假設(shè)：

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

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

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

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

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

(6)假設(shè)在一個發(fā)車時間間隔內(nèi)，客流量服從正態(tài)分布。

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

1.2.4 多目標優(yōu)化模型的構(gòu)建

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

(1)乘客出行成本

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

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

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

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

C=(n1c1+n1c1+…)L

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

(3)模型整合

本文分別以乘客出行成本最小和公共交通的運行成本最小為目標，構(gòu)建公交調(diào)度優(yōu)化模型，模型如下所示。

minC=(n1c1+n1c1+…)L

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

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

1.2.5 多目標遺傳算法模型的構(gòu)建

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

(1)編碼方式

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

(2)初始化種群

根據(jù)高峰期和平峰期的定義可知，平高峰期是一個時間段，因此基于“高平峰”優(yōu)化的染色體里的基因?qū)τ凇案咂椒濉笔沁B續(xù)的。根據(jù)本文之前定義的高平峰計算方法，一條染色體開始應(yīng)該是連續(xù)的平(或高)峰期，再是連續(xù)的過渡時期，最后是連續(xù)的高(或平)峰期。

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

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

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

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

(4)算法的設(shè)計

算法流程圖下圖2所示。

圖2 算法流程圖

3 實驗結(jié)果與分析

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

表1 擬合參數(shù)表

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

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

Time senes/min

4 模型分析與討論

4.1 “平高峰”優(yōu)化前后實驗結(jié)果對比分析

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

表2 優(yōu)化前后的成本對比結(jié)果表

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

4.2 “平高峰”優(yōu)化前后乘載率對比分析

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

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

圖4 優(yōu)化前后的乘載率對比結(jié)果圖

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

5 結(jié)語

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