臨界—遺傳算法在公交調度中的應用

韋尚成

摘 要：隨著我國交通問題日益不平衡，為了緩解交通壓力，研究公交車調度問題很有必要。針對公交車輛調度的現狀，通過分析乘客出行的舒適度以及公交車的滿載情況定義了乘車感知波動價格。結合實際建立了乘客最小乘車費用以及公交公司最小總耗費為目標的一個綜合優化模型；并引入擁堵彈性因子，分析了它對發車間隔的影響。同時針對傳統遺傳法的局限性以及收斂速度慢等缺陷，通過個體的相似度與父輩相似度的臨界值相比較，動態調整變異時間和控制變異概率的方式對遺傳算法進行改進。最后應用臨界—遺傳算法（C-GA）和簡單—遺傳算法（S-GA）分別對上述優化模型進行求解，通過實例證明了該算法在收斂速度和結果都優于簡單遺傳算法。

關鍵詞：城市交通；調度優化；感知波動價格；臨界—遺傳算法；公交車；博弈

中圖分類號：F570 文獻標識碼：A

Abstract： With traffic's problems is increasingly unbalanced in China， it is necessary to study on bus scheduling problem（BSP）for solving traffic pressure. According to the present situation in the scheduling of bus， considering the comfort' degree of passengers and condition of bus's guests are analyzed to identify the perceived fluctuation-price combined with the actual， an integrated optimizing model is established based on minimize trip cost of passengers and the minimize total cost of bus company and congestion flexibility factors are introduced to analysis it influence on the bus departure time interval； putting a way of dynamic adjust variation's time-based critical value and control variation's probability are improved in the paper to overcome limitation and slow convergence speed of traditional genetic algorithm at the same time and then adopting criticality-genetic algorithm（C-GA）and simple-genetic algorithm（S-GA）to solve BSP model， experiments shows that C-GA is better than S-GA in the speed of convergence and results.

Key words： urban traffic； scheduling and optimization； perceived fluctuation-price； criticality-genetic algorithm； bus； game

0 引 言

隨著我國社會經濟的快速發展，我國機動車保有量逐年增加，交通問題日益嚴重，用有限的道路面積承擔盡可能多的出行是解決城市交通問題的有效途徑，為此如何有效地調度公交車運行是其很重要的環節。大量國內外的學者從不同的角度對公交調度進行了研究，1993年，Malacly Carev[1]對公交車的非準點到站的分布以及不同發車間隔下乘客的到達分布進行研究，然而現在公交車發車往往限制于單位時段內固定發車頻率。1998年，Paolo Delle Site等[2]研究了客運走廊上的公交調度優化模型。2011年，王超、徐猛[3]在Ceder[4]4種確定發車時間間隔的基礎上，考慮了道路擁堵情況下對公交車發車間隔做了研究等。也有學者根據算法的不同對公交模型優化做了相關研究，2004年，童剛[5]以乘客和公交公司總效益最大為調度目標，建立了公交運營參數模型，通過遺傳算法進行了求解，但是公交作為公益性設施，在運營中不應該是簡單加權。2009年，鄭小花、陳淑燕等[6]采用模擬退火算法，以乘客候車時間最小為優化目標的調度模型，而公交在運營中企業效應應該著重表現。2014年，崔明月、黃榮杰等[7]通過量子遺傳算法對公交車輛調度進行了優化。2015年，馬雁、王非等[8]通過改進遺傳算法對公交車調度模型進行了優化。

公交車的調度問題是APTS中最重要的一環，其主要功能是實現公交車輛的自動調度與指揮[9]；實際出行過程中，乘客上下車的時間消耗也占據著很大的比例，尤其對于短途行駛的乘客。本文通過定義乘客出行感知波動函數，以公交公司總利益最大化、乘客等待時間最小化為優化目標，從實際出發，建立了相應的公交車調度優化模型，通過改進遺傳算法進行求解；同時引入擁堵彈性因子，研究了路段處于擁堵狀態下的公交車調度，通過實例說明擁堵彈性因子對發車間隔產生了很大的影響，以及算法的優效性。

1 公交調度優化數學模型的建立

對于特定的公交路線，影響公交調度模式和相關方案選擇的因素主要表現在乘客和公交公司的利益之間的博弈，公交公司總希望發車間隔盡量的大，以此來減少班次數，保持其可變成本盡量低，而乘客卻是希望獲得較小的發車間隔以至于達到出行方便。二者博弈的結果就是要求調度方案盡可能地在二者之間尋找納什均衡點。本文以此為目的，建立了如下的數學優化模型。

為了簡化模型，現提出如下假設：（1）在某一個時間段內，車輛只能沿著規定的路線行駛；（2）公交車不準等客；（3）每輛公交車發車頻率不受到乘客多少的影響并且相等；（4）所有到站乘客只能通過選擇公交車作為其出行方式；（5）有足夠的公交車供調度使用；（6）站點均勻分布；（7）在不考慮公交專用道下，相鄰站點公交車行駛的過程中，行駛時間只與路段是否擁擠有關；（8）只考慮單向行駛。

符號、變量、常量的說明如下：

車站集：I=1，2，3，…，N同時表示共有N個車站（注：文中i-1僅表示i的前一站，無任何數值比較）；

車輛集：J=1，2，3，…，K同時表示可供調度的公交車共有K輛（注：文中j-1僅表示j的前一輛車，沒有任何數值比較）；

t■■表示第j輛公交車到達第i站的時刻經適當轉化后用于比較的實數；

s■■表示第j輛公交車從第i站的發車時刻經適當轉化后用于比較的實數；

π■表單位乘客候車費用（元/人）；

π■表單位乘客坐車費用（元/人）；

λ■表示乘客在第i站的下車率（%）；

ρ■表示乘客到達第i站的到達率（%）；

T■■表示第j輛公交車在第i站最大停車時間（min）；

T■■表示第j輛公交車在第i站最小停車時間（min）；

H■表示最大車頭時距；

x■為第j輛公交車從i站出發時的載客量（人）；

B為公交車定員（人）。

建立優化模型如下：

記∏■為乘客候車費用，則：

∏■？芪π■·■■t■-s■ρ■·t■-s■ （1）

其中：t■-s■表示乘客候車時間。

記∏■為乘客車內費用，其時間消耗主要由三部分組成，第一部分為所有乘客在公交車行駛時的耗時t■，第二部分為所有乘客上車的時間消耗t■，第三部分為所有乘客下車階段的時間消耗t■。

t■=■x■·t■-s■ （2）

t■=■■■■·ρ■·s■-s■ （3）

t■=■■■·λ■·x■ （4）

其中：■表示單位乘客平均上車時間（min/人）；■表示單位乘客平均下車時間（min/人）；t■-s■表示列車運行時間；s■-s■表示前后兩車的車頭時距。

定義乘車感知波動價格δ■，即乘客出行中若乘車過度擁擠或者未能達到公交公司規定的滿載率所承擔的額外費用，據研究統計得δ■與乘客人數x■之間函數關系如下：

δ■x■=■ （5）

式中：ζ為公交公司規定乘客數未能達到平均滿載率時的懲罰系數，ζ>1，ω為滿載率，即如若當次乘客數量未達及公交公司規定最小乘客數ω·B時，則會收取額外的費用ζ-1·π■；θ為乘客波動系數，θ<1，當x■=B即此時乘客數為公交車車型定員時δ■=π■；當x■>B時，由于擁擠則會受到懲罰，多支付η-1π■；通過數據驗證，可得下式：

η=maxx■/B； i∈I， j∈J （6）

則乘客下車階段產生的廣義費用：

∏■=π■·x■·1-ρ■·t■+t■+δ■x■·t■ （7）

則乘客出行的廣義費用∏■表示為：

∏■=∏■+∏■+∏■ （8）

記∏■為公交公司可變費用，則：

∏■=■■∏·t■-s■ （9）

其中：∏表示公交車可變運營費用（元）。

由以上分析可建立以公交車每時段發車時間間隔為內生變量的數學優化模型：

minα∏■+1-α∏■

s.t.■ ？坌i，j （10）

其中：α乘客出行廣義費用所占的權重系數；s■-t■表示為第j車在第i站停車的時間。

2 公交調度優化模型的求解

遺傳算法（GA）于J.Holland教授等人啟發提出的[10]，是一種優秀的全局搜索算法，但遺傳算法局部搜索能力很差，很容易出現早熟現象，對新的基因結構的產生具有局限性，從而導致遺傳算法的收斂效果并不理想；交叉和變異算子是遺傳算法中最重要的操作算子，交叉操作對于保證遺傳算法尋優過程收斂到全局最優，以及提高尋優過程的收斂速度，都起著重要的作用；而變異操作則使種群保持一定的多樣性[11]。本文通過臨界值動態控制交叉順序及調整變異概率，對傳統的遺傳算法做了改進，通過對公交調度模型的求解，驗證了算法的更優性。

2.1 約束條件的處理

為了使算法具有自適應能力，現在采用懲罰策略對約束條件進行處理，假定μ■， μ■， μ■為式（11）中各約束條件的邊際效用（罰函數作用強度的系數），則：

minLΔ■，s■，μ■，μ■，μ■？芪min∏■+∏■+μ■·■max0，s■-t■-T■■+μ■·■max0，T■■-s■-t■+μ■·■max0，s■-s■-H■（11）

2.2 染色體的編碼

根據本文模型特點，采用二進制編碼；根據統計，假設取發車間隔的值域為Δt|Δt=2，3，4，…，15，即：Δt■=2，Δt■=15；Δt由于Δt是滿足2≤Δt≤15的14個整數，而且2■<14<2■，故而Δt的二進制串長度至少需要4位，如表1：染色體的長度取決于時間段的數目，如果全天共分成n個時段，則染色體的長度為4n。

2.3 初始化

隨機確定L個染色體為初始種群，并根據Δt的約束范圍2，15，選擇初始種群的時候剔除無效的染色體；記種群集：■

=α■，α■，…，α■，…，α■，…，α■。

2.4 參數選擇

遺傳算法中，需確定相應的交叉概率p■以及初始變異概率p■。

2.5 適值計算

適應度的作用在于評價個體的優劣程度，適應度越大，個體則就越好，同時個體則有更多的機率遺傳繁殖到下一代，反之則反。故而遺傳算法要求適值非負，通過式（12）將最小的目標根據適值非負原則將其轉化為求解目標最大值的形式。

f■=■ （12）

式中：z■為一較大的特定輸入值；z■為個體f■對應的可行解。

計算中發現：易證明fx=e■ω·B≤x≤B為凸函數。當x■→B時，波動率呈現指數級增長。從而導致的波動率差異過大，同時考慮到線性函數增長的平穩性以及大大降低求解難度，現將此凸費用函數用分段，線性規劃近似，取ω·B，B的中點作為段點：則處理后的凸費用如圖1所示：

以各段線性函數的梯度作為權重，則式（5）轉化為：

δ■x■=■ （13）

將δ■x■代入式（7）中即可。

2.6 遺傳產生后代操作

（1）復制

本文采用輪盤賭選擇，即個體適值越大，則被選中的概率就越高，那么該個體被復制至下一代的機率也就越大，反之則反，個體被選擇的概率由式（14）計算：

P■f■=gf■/∑gf■ （14）

其中：P■f■為選擇概率；gf■為個體f■的適值。

（2）交叉操作

交叉就是通過交配原則產生一組新的染色體（解）的過程。變異算子在遺傳算法中的主要作用就是使得種群保持一定的多樣性。本文通過采用父輩臨界值來控制變異時間，操作為首先劃分出優良種群，進行多父輩POX交叉[12]，并且從中選擇最優的兩個父個體，但是不同于以往的是這兩個父個體不直接放入子代種群，而是將這兩父個體的相似度與父輩相似度的臨界值作比較。

定義0-1變量：

θα，k=S■■-S■■=■ （15）

其中：S■■和S■■為兩個體對應染色體α■和α■中的第k個基因，若k為相同的等位基因，則θα，k為1，否則為0。

于是父個體相似度C■：

C■？芾■■θα，xdx （16）

父輩相似度的臨界值S■：

S■=■ （17）

其中：d■和d■分別表示染色體α■和α■上的第k個基因；L為種群大小。

如若C■≤S■，那么將這α■和α■放入到子代種群中，否則為了有效地避免近親繁殖，則先對次優的父個體通過一次或者幾次的突變，這樣則即降低了父個體之間的相似度，同時又保留了優良個體，迭代至與最優父個體相似度C■'≤S■為止，此時再將父個體放入子代種群中。

通過上述策略，則能有效地避免新一輪操作中父輩之間進行交叉，又有利于產生新個體，同時有利于搜索到新的解空間。

（3）變異操作

傳統的遺傳算法的變異操作中，事先確定一個固定的突變概率，本文采用動態調整變異概率，記S■為收斂度的臨界值。具體操作步驟如下：

step1：計算染色體適值g■f■，將最優染色體進行保存，記錄其適值gf■。

step2：計算下一代染色體適值g■f■，并且保存最優染色體，記錄其適值gf■。

step3：依Step1，Step2方法以此記錄各后代的染色體適值分別為：gf■，gf■，gf■，…。

step4：If gf■=gf■，則記S■=1；If gf■=gf■=gf■，則S■=2，以此規律If gf■=gf■=gf■=…=gf■，則使S■=n-1；否則S■=0。

step5：定義P■=p■+S■/100為突變概率，可見突變概率隨著S■的變化而改變，從而實現動態改變變異概率。

根據上述提出的動態改變變異概率的特點，變異操作采用自適應變異算子的方法進行設計。

2.7 終止操作

（1）本文采用經典的固定遺傳代數的方法，既設定當算法迭代到M代時即停止，得到各時段發車時間間隔的二進制串，再將其轉化為實數；

（2）將上述得到的二進制串轉化為相應的實數Δt，根據客流量，根據Ceder所提出的模型[13-14]，引入擁堵彈性因子μ■，考慮道路的交通擁堵情況下公交車調度問題。

定義μ■k時段列車的行駛速度與規定最大行駛速度之比；可見0<μ■≤1；

min ■ ， ■ ， Δt （18）

注： x 表示對x做四舍五入的取整運算，當μ■=1，■→∞。

其中：L為全程路長，P■■為k時段所有站點客流量的最大值。

3 實 例

利用上述公交車調度優化方案以及算法設計，以蘭州市1路車下行線路作為研究對象，通過相關統計調查，得到了相應參數值，算法中的主要參數見表1：

根據某一天內（非節假日）公交IC卡數據采集，通過a■■=a■·■對原始統計值的修正。

式中：a■為第j輛公交車到達i站時上下車的乘客的原始值；a■■為第j輛公交車到達i站時上下車的乘客的修正值；p為公交公司的運營人數。

乘客車內以及等車費用由式（19）計算：

π■=π■=G■/365×5/7×8×60 （19）

其中：G■為人均國內生產總值；依照2015年統計，計算可得π■，π■約為0.05元/min。

利用調查參數，依照本文提出的優化模型以及算法，將其在Eclipse集成開發環境上通過java程序語言運行迭代200次。通過計算整合，得到了各時段的發車時間間隔以及發車車次，見表2：

根據表2，可得公交車在不同道路狀況下的折線圖，如圖2所示。

實際中在車輛數足夠多的時候，發車頻率與乘客到達率成正比關系，而交通擁堵也往往發生在客流量大的時段；由圖2可知：在考慮道路擁堵因素時，則會一定程度上降低了發車頻率從而去緩解當前的交通壓力，如果一定程度地增大μ■，則發車頻率則會相應的減少，這與實際情況相符。μ■增加，交通擁堵增加，此時就應適當降低發車頻率，使發車間隔增加，從而有效地控制運營成本。

優效性，現采用同組數據通過與S-GA分別計算目標最優值進行性能比較，結果如圖3所示。

由于相比較S-GA的固定變異率，C-GA卻采用自適應動態調整的變異，這樣能較好地維持種群的可進化性，同時又大大的提高了算法的優效性；由圖3可得C-GA在收斂速度上以及效率上明顯優于S-GA。

現針對公交車優化模型，為了驗證C-GA的可行性以及準確性，采用同數據與S-GA結果進行分析，如圖4。

圖4顯示：算法得到解在各個高峰階段，發車頻率都較高，發車間隔小，此時主要體現出乘客的利益；而在低峰或者平峰階段，發車頻率小，發車間隔大，又恰好地反映了公交公司的利益；同時C-GA比起S-GA得到的發車頻率在小客流量時間段發車頻率都較小，客流較大時段發車頻率都較大。眾所周知每天8：00～9：00以及17：00～19：00為全天客流量最大的時間段，實際中此時段也往往是人們上下班，學生上放學的時刻，容易造成交通擁堵現象，前文也有相關分析，故C-GA在此情況下得到的發車頻率的降低幅度會更大，在滿足交通量需求的同時更好地均衡了乘客與共交公司的二者利益；由上述分析顯示本文模型符合實際情況，算法有效。

4 結 論

本文從實際情況出發，在考慮乘客上下車的耗時，以乘客舒適度和公交滿載率為基礎，定義了感知波動價格函數來形象反映乘客出行過程中的廣義價格變化，從而建立了以公交公司與乘客總耗費最小的公交調度優化問題；引入了擁堵彈性因子來，通過與正常情況下公交車發車頻率的對比驗證了擁堵彈性因子對公交車發車間隔產生了較大的影響，且能有效控制線路上的公交發車間隔在滿足交通量需求的同時維護了二者利益，切合實際情況，對研究公交的吸引度以及公交調度有一定的意義。同時為了克服遺傳算法的不足之處，設計了C-GA算法進行優化，并通過S-GA作比較通過實例證明C-GA對公交調度優化是可行有效的。由于本文的研究時間以及知識水平有限，論文中存在著很多有待改善的地方，比如客流到達分布以及不確定性未被考慮、過于簡化旅客到達率，為詳細研究、模型的相關參數較多，參數值的標定缺乏理論上的支撐等。后續工作中考慮隨機客流分布研究，其他公交車運行的影響以及上下行等問題做進一步研究，使得模型更加貼近實際情況，為城市公交調度提供重要理論依據。

參考文獻：

[1] Malacly C. Optimizing scheduled times allowing for behavioural response[J]. Transportation Research， 1998，32（5）：329-342.

[2] Paolo D. S， Francesco F. Bus service optimization with fuel saving objective and various financial constrains[J]. Transportation Research， 2001，35（2）：157-176.

[3] 王超，徐猛. 考慮道路交通擁堵的公交發車間隔優化模型[J]. 交通運輸系統工程與信息，2011，11（4）：23-30.

[4] Ceder A. Public transit planning and operation： Theory， modeling and practice[M]. Elsevier， 2007.

[5] 童剛. 遺傳算法在公交調度中的應用研究[J]. 計算機工程，2005，31（13）：29-31.

[6] 鄭小花，陳淑燕，武林芝. 模擬退火算法在公交調度中的應用[J]. 信息化研究，2009，35（9）：45-47.

[7] 崔明月，黃榮杰，劉宏釗，等. 量子遺傳算法在公交車輛調度中的應用[J]. 實驗室研究與探索，2014，33（12）：1-4.

[8] 馬雁，王非，周永年. 改進遺傳算法在公交智能調度中的應用[J]. 科技通報，2015，31（9）：13-15.

[9] 張飛舟，晏磊，范躍祖. 智能交通系統中的公交車輛調度方法研究[J]. 中國公路學報，2003，16（2）：82-85.

[10] 王凌. 車間調度及其遺傳算法[M]. 北京：清華大學出版社，2003：68-76.

[11] 李繼哲，王書振，王東. 基于約束范圍交叉操作的遺傳算法[J]. 北京交通干部管理學報，2004，14（3）：232-261.

[12] 梁旭，黃明，寧濤，等. 現代智能優化混合算法及其應用[M]. 北京：電子工業出版社，2014：54-55.

[13] Ceder A. Bus frequency determination using passenger count data[J]. Transportation Research Part A： General， 1984，18（5）：439-453.

[14] Ceder A， Golany B. Creating bus timetables with maximal synchronization[J]. Transportation Research Part A： Policy and Practice， 2001，35（10）：913-928.