基于區域協同的公交發車時刻表模型

（西南交通大學 a.交通運輸學院; b.物流學院， 成都 610031）

摘 要：

為提高城市公共交通系統的效率，對基于區域協同的公交發車時刻表問題進行了研究。綜合考慮公交內部線路間的換乘銜接，以乘客在區域內的總換乘時間最小為優化目標，建立區域協同發車時刻表模型，針對模型特點，提出了求解該問題的改進遺傳算法。在選擇適當參數的基礎上，通過算例驗證了該模型及算法的合理性和有效性。

關鍵詞：公交發車時刻表；區域協同；改進遺傳算法

中圖分類號：TP301.6文獻標志碼：A

文章編號：1001-3695(2009)04-1282-04

Model of bus dispatching timetable based on regional collaboration

HE Dia， YAN Yu-songa， HU Zuo-ana， QIU Zhong-quanb

(a.School of Traffic Transport， b.School of Logistics， Southwest Jiaotong University， Chengdu 610031， China)

Abstract:

Based on regional collaboration， this paper studied the timetable problem of regional bus dispatching so as to incarnating efficiency of city public transportation system. Studied the model of bus dispatching timetable based on the regional collaboration， considering the transfer between lines， which enabled the transfer of passengers from one route to another with mini-mum waiting time in the region. And according to characteristic of the model， used an improved genetic algorithm to solve the problem in polynomial time. By selecting appropriate parameters， illustrated the reasonable and efficient of the model and algorithm through a case study.

Key words：bus dispatching timetable； regional collaboration； improved genetic algorithm

0 引言

 編制運營組織計劃是運營調度的基礎，而公交運營組織計劃的核心是編制運營時刻表；同時公交時刻表是服務可靠性的關鍵因素，也是運營者與用戶之間的橋梁。因此，應關注時刻表的構建，從而為變動的乘客需求提供可靠的公交服務。

區域調度中的公交時刻表的編制與單線調度相比，一個重要的不同之處，就是調度中心在確定各條線路的發車頻率或間隔之后，還要盡可能地考慮乘客在區域內換乘的方便性，從而編制出能夠最大限度地減少乘客在不同線路交叉點處換乘等待時間的公交時刻表。這方面的研究文獻相對較少。Daganzo[1]提出僅包含輸入輸出線相交的一個節點的網絡協調問題。Voss[2]把最小化乘客在換乘點等待時間的問題表示為Lawler和Hillier等描述的二次分配問題。Desilet等人[3]從可能的開始時間集中為每一條線路選擇開始時間，目標函數是最小化從線路間換乘的總費用，罰函數考慮到達時間的隨意性，可以用不同的方法計算。Ceder[4]指出，事實上調度員嘗試建立滿足必要的頻率、單公交鏈有效的出行安排、確定到達同步三大條件的發車時刻表，并建立了在換乘點車輛兩輛同時到達的次數最多發車時刻表。周雪梅等人[5]對Ceder的模型進行了深化。Fabian 等人[6]采用遺傳算法隨機地安排公交的到達。

總的看來，國內外對基于區域協同的公交時刻表的研究還比較少，沒有從公交調度員實際操作的角度看待問題。相對成熟的理論是Ceder進行的研究，但在其研究中，沒有考慮站點的權重，要求車輛必須同步到達，其建立的啟發式方法不易移植。周雪梅等人雖然在Ceder的基礎上進行了深化，但其僅僅考慮兩條線路之間的換乘，沒有對模型的求解方法進行說明。Fabian 等人建立的模型比較詳盡，但參數難以獲得，不具備實用性。

本文綜合考慮公交內部線路間的換乘銜接問題，對協調的內涵進行了闡述，分析了區域協同發車時刻表的任務；建立了區域協同發車時刻表的模型，使乘客在區域的換乘時間最小。由于涉及大量的變量，該模型的求解問題相當復雜，問題的組合特性也使得計算困難，用傳統算法很難求解。為此提出了求解該問題的改進遺傳算法(IGA)；通過案例進行了求解，并與基本遺傳算法(SGA)和嫁接共生遺傳算法(GSGA) [7]的計算結果進行了分析比較。

1 問題描述

協同是一個在學術范圍和應用中都使用十分廣泛的概念，但卻沒有一個明確的定義。公交車輛區域調度中，將線路的調度視為子系統，包含一定范圍內所有線路的區域調度視為總系統，則區域調度是由多個子系統集成為一個具有特定目標的總系統，多個子系統之間既相互聯系又相互作用，這種作用有可能是相互牽制約束的，也可能相互依存推動。將子系統之間的這種關系稱為系統集成的協調程度，若設F為集成前各子系統的成效總和，W為系統集成后的總成效，則就可用協調度來定量分級表示系統之間的關系，如表1所示。



當子系統集成后所獲得的總成效W超過原來的各成效總和時（W>F），稱系統是協同的，說明子系統之間能夠互相激勵、互相推動，從而獲得了更多的成效。

區域協同發車時刻表的任務是通過各種手段、方法，合理調整區域內公交線路的發車時刻表，使區域內公交線路的發車時刻在保證自身合理、與外部環境相適應的基礎上，彼此之間最大程度地消除矛盾，達到協同工作，實現主要換乘點盡可能同步到達，減少乘客在換乘站點的等待時間，最終目的是提高城市公交調度系統的整體功效水平。其關鍵是在最大限度地縮短乘客換乘等待時間的前提下，確定協同換乘線路的發車時刻表，通過優化線路的發車時刻和駐站時間的組合，實現區域內線路之間的協同調度，以達到換乘等待時間最少的目的，提高換乘效率。

2 模型的建立

考慮分析問題須由簡到繁，在此對問題進行了簡化，建立以下假設：

a)換乘客流量建立在APTS（advanced public transportation systems）的基礎上，是已知的，各換乘點乘客的到達服從均勻分布，并設乘客的到達率為常數，客流模型能反映規劃周期內的客流量。

b)不考慮道路交通運行條件的影響。

c)在APTS條件下，常規公交線路的初始發車時間已知，線路上各站之間行駛的行程時間已知。

d)調度針對特定的規劃周期T＝60 min。

e)由于有些運輸公司規定不能輕易調整行車間隔，只需考慮各線路第一輛車的發車時間之間的配合結合，況且發車間隔的頻繁更換也不利于時刻表的執行。為了簡化問題，假定在規劃周期內，各線路的發車間隔為定值。

f)以min作為最小的時間單位。

g)各公交車嚴格按照時刻表運行，按調度時刻表準時到站和出站，并且排除中途調頭的情況。

根據上面的分析，建立模型如下：

 min∑Mi=1∑Mj=1∑Nn=1∑Fip=1∑Fjq=1Cijn[(Xqj+Tqjn+Sj)-(Xpi+Tpin+Si)]（1）

 s.t.-Hmin/2≤Si≤Hmin i/2（2）

-Hmin j/2≤Sj≤Hmin j/2（3）

0≤(Xqj+Tqin+Sj)-(Xpi+Tpin+Si)≤H（4）

[60/Hmax i]≤Fi≤[60/Hmin i+1]（5）

[60/Hmax j]≤Fj≤[60/Hmin j+1]（6）

Si、Sj為整數（7）

式（1）為目標函數，其目標是協同調度區域內公交線路之間的乘客換乘總等待時間最小；約束式（2）（3）確保時間改變發生在可能的時間改變區間內；約束式（4）保證公交線路j上的公交車q到達換乘站點n的時間比公交線路i上公交車p早；約束式（5）（6）保證在規劃周期T內時刻表中公交線路i、j上發車次數在可行范圍內；約束式（7）保證各線路發車時間的改變值為整數。

模型中的相關變量如下：

a)運輸網絡變量

M：區域網絡中公交線路的數量；

N：區域網絡中公交換乘點的數量；

i，j：公交線路，1≤i，j≤M；

n：換乘點，1≤n≤N；

b)決策變量

Si：公交線路i上公交車的發車時間改變值，1≤i≤M，Si為整數變量；

Sj：公交線路j上公交車的發車時間改變值，1≤j≤M，Sj為整數變量；

c)狀態變量

Fi，Fj：規劃周期T內時刻表中公交線路 i，j各自的發車次數 ，1≤i，j≤M；

Cijn：在換乘點n從換乘線路 i到線路j的平均乘客數量，1≤n≤N，1≤i，j≤M；

Xpi：公交線路i上第p輛公交車的發車時間，Hi是公交線路i上相鄰兩輛公交車的發車間隔，Xpi=X1i+(p-1)Hi(p=1，2，…，Fi; j=1，2，…，M)；

Xqj：公交線路j上第q輛公交車的發車時間， Hj是公交線路j上相鄰兩輛公交車的發車間隔， Xqj=X1j+(q-1)Hj(q=1，2，…，FJ，J=1，2，…，M)；

Tpin：公交線路i上第p輛公交車從始發站到換乘點n的運行時間；

Tqjn：公交線路j上第q輛公交車從始發站到換乘點n的運行時間；

Hmax i、Hmax j：公交線路i、j上相鄰兩輛公交車的最大時間間隔；

Hmin i、Hmin j：公交線路i、j上相鄰兩輛公交車的最小時間間隔；

H=min(Hi，Hj) Hi≥Hjmax(Hi，Hj) Hi＜Hj

由于時刻表問題的復雜性和組合性，即使對簡單的公交網絡，發車時刻表也是復雜的組合優化問題。從算法的角度看，在上述建立的整數規劃模型中，整數變量的數目決定它的復雜性，雖然涉及多條公交線路、換乘站點和公交車輛，由于發車間隔是確定的，實際上需要確定各條線路上第一輛車的發車時間，這里整數變量的數目為M。令H＝max(Hmax i)，1≤i≤M，則在最差的情況下可能的時刻表改變的組合變量數目為HM，這個數量是相當龐大的。

3 改進的遺傳算法求解

整數規劃問題的本質是確定滿足約束的某些項的排列，雖然用枚舉法逐個比較總可以得出最優解，但不具備時間有效性。解決大規模整數規劃問題，基于種群的智能優化算法具有明顯的優勢，它們同時從多個點出發，利用迭代過程中獲得的信息自行組織搜索，其分布式并行模式大大提高了整個算法的運行效率、魯棒性和快速反應能力。

作為一種基于種群的智能優化算法的遺傳算法 [8，9]，提供了一種求解復雜系統優化問題的模式，它不依賴于問題的具體領域，對問題的求解種類有很強的魯棒性。同時，與傳統的優化算法如梯度法、動態規劃法、分支定界法等相比，除了具有良好的并行性外，遺傳算法還具有如下優點：全局優化性能和穩健性好，有利于搜索到全局最優解；不需要其他推導和附屬信息，對問題和時間的依賴性小；搜索效率往往優于其他算法；利用概率轉移規則，而不是確定規則，采用的概率搜索技術是一種不確定性搜索方法，不受搜索空間是否連續或可微的限制，不同于傳統的確定性的搜索方法，更有利于得到最優解。

基于上述特點，遺傳算法非常適合求解復雜的離散型優化問題。然而，遺傳算法在解決復雜調度問題時存在兩個局限性，即進化速度緩慢和存在過早收斂現象。尤其是當采取措施加快進化速度時，早熟現象就越嚴重，以致在解決復雜調度問題時得不到理想的結果。針對這些問題，本文在GSGA的基礎上采用新自適應方式[10]的交叉和變異，提出改進的遺傳算法IGA，其中的主要改進如下：

a）采用雙種群設計。算法中包括待進化種群和嫁接種群。待進化種群的地位等同于標準遺傳算法中的種群，其第一代染色體均為隨機生成；而嫁接種群則要滿足初始種群染色體的適值較高和內部染色體具有惟一性的雙重條件。嫁接種群中染色體的數目比較小，一般取待進化種群的20%~30%。

b）新自適應方式的交叉和變異。交叉概率Pc和變異概率Pm為固定的值時易產生早熟現象。本文對不同的染色體以不同的概率進行交叉和變異，引入新的自適應算法公式：

Pc=0.9{exp(-0.382)（f ′-favg）/（fmax-favg）} f ′＞favg0.9f≤favg（8）

Pm=0.1{exp(-0.618)(fmax-f)/(fmax-favg)} f＞favg0.1f≤favg（9）

這樣，交叉概率和變異概率隨群體的適應度自動改變。當種群各個體的適應度趨于一致或者趨于局部最優時，使Pc和Pm增加，以跳出局部最優；而當群體適應度比較分散時，使Pc和Pm減少，以有利于優良個體的生存。在進化初期，染色體的適值差別較大，較優染色體與較差染色體交叉概率的差別也較大；隨著進化代數的增加，染色體的交叉概率的差別逐步縮小；到進化的后期，所有染色體的交叉概率逐步收斂于一個固定值。因而保持種群的均衡進化和多樣性，能有效地提高抗早熟能力。

c）算法分階段執行。該算法從執行過程來看分為兩個階段，即嫁接階段和共生階段。嫁接階段的主要功能是實現種群的快速進化；共生階段的主要功能則是進一步提高算法的求解精度。

通過嫁接種群的指導，待進化種群染色體的適應度值得到迅速提高。隨著進化代數的不斷增加，待進化種群染色體的平均適應度值會超過嫁接種群染色體的平均適應度值，此時的嫁接種群已無法起到指導待進化種群進化方向的作用，算法便進入第二階段——共生階段。此時的兩類種群轉變為兩個獨立進化、相互合作的共生種群。種群的重新初始化，可以通過把嫁接種群和待進化種群中的所有染色體平均分配給兩個共生種群來實現。

算法的求解步驟如下：

a)采用隨機方法初始化待進化種群，采用啟發式規則初始化嫁接種群。

b)計算待進化種群和嫁接種群的適應度值，如果待進化種群的平均適應度值較大，轉e)。

c)根據自適應的交叉概率進行種群間交叉，即分別從兩個種群中選擇一個染色體作為母體實施交叉操作。交叉后產生的子代染色體應同時更新嫁接種群和待進化種群。

d)根據自適應的變異概率對待進化種群實施鄰域搜索變異操作，如該子代染色體優于待進化種群中的最差者，則直接取代；否則保持待進化種群不變。判斷是否需要更新嫁接種群，如果需要則進行更新，算法代數加1，轉b)；否則不進行更新，算法代數加1，轉b)。

e)根據自適應的交叉概率和變異概率對待進化種群和嫁接種群分別進行種群內交叉和變異，并進行更新。

f)判斷是否滿足定期交換條件，如果是則分別在待進化種群和嫁接種群中選擇優秀染色體進行交換并實施種群間交叉。

g)算法代數加1，判斷是否滿足中止條件，如果是，算法結束；否則轉e)。

IGA綜合了自適應遺傳算法和嫁接共生遺傳算法的優點，把優秀的染色體放入一個單獨的種群，并保持惟一性。算法中一個種群可以指導另一個種群的進化方向，由于嫁接種群也一直在進化，它不但可以一直起到加速進化的作用，而且還可以防止早熟。同時采用了自適應的交叉概率和變異概率來提高抗早熟的能力和解的精度。

4 算例

已知某公交網絡，如圖1所示，網絡中有四條線路、四個換乘點。本例中假定統一路段上行車時間相同、路段上的數字為路段行車時間、圓圈內的數字為換乘節點編號、線端的羅馬數字為線路編號、各線路在整點始發。線路和節點描述如表2和3所示。



為檢驗上述模型及求解算法的有效性，采用MATLAB 7.1 [11]對上述算例進行了求解。GA是一種隨機搜索算法，收斂性無嚴格的數學證明，要比較各種改進遺傳算法的優劣需采用統計方法，通過實際數據說明。在采用相同目標函數、約束條件、實驗參數(種群數=60，進化代數=100，初始交叉概率=0.5，初始變異概率=0.1)的情況下，在每次計算中固定10個不同初始種群。 IGA、GSGA、SCA三種不同算法的結果如表4和5所示。

由表4和5可知，問題的模型和求解算法有效，具有魯棒性， 改進后的IGA在搜索速度和尋找最優解方面都明顯優于GSGA和SGA，同時在整體的算法運行上也證明了本文提出的新算法快于GSGA和SGA算法。因此有力地證明了該算法在尋優能力上的明顯優勢，以及在提高搜索效率、改進收斂性能上的顯著能力。最后通過圓整法，其最終結果為當S1=4，S2=4，S3=-9，S4=-1時，獲得最優解為2 549 min。

5 結束語

本文建立了區域協同發車時刻表的模型，并通過實例具體展示了改進的遺傳算法，對解決大規模、復雜的區域公交車輛調度問題進行了有益的嘗試。優化結果的分析和比較表明該算法具有較好的效率，是解決公交調度問題的有效方法，同時也表明區域調度下可以更好地進行線路間的換乘銜接，比線路調度模式具有更好的優勢。

未來的研究應繼續將算法應用于更大規模的實際問題，同時提高算法并行計算的效率，改進現有的獲得公交和乘客數據的技術和數據采集、處理技術，使算法中的數據更易獲得。

參考文獻:

[1]DAGANZO C F. On the coordination of inbound and outbound schedules at transportation terminals[C]//Proc of the 11th International Symposium on Transportation and Traffic Theory. Yokohama， Japan:Elsevier， 1990：379-390.

[2]VOSS S. Network design formulation in schedule synchronization[M]. Berlin:Computer-Aided Transit Scheduling， 1992：137-152.

[3]DESILET A， SYNCRO R J. A computer-assisted tool for the synchronization of transfer in public transit networks[M]. Berlin: Computer-Aided Transit Scheduling. 1992：153-166.

[4]CEDER A. Bus timetables with even passenger loads as opposed to even headways[J]. Transportation Research Record: Part B， 2002， 17：26-39.

[5]周雪梅，楊曉光. 基于ITS的公共交通換乘等待時間最短調度問題研究[J]. 中國公路學報， 2004，17(2):82-85.

[6]CEVALLOS F， ZHAO Fang. A genetic algorithm for bus schedule synchronization[C]//Proc of AATT 2006. 2006：737-742.

[7]徐國華，王書振，王東. 嫁接共生遺傳算法及其在作業調度中的應用[J]. 計算機集成制造系統， 2004，10(4):461-464.

[8]DEB K， CHAKROBORTY P. Time scheduling of transit systems with transfer considerations using genetic algorithms[J]. Special Issue on Evolutionary Algorithms for Scheduling， Evolutionary Computation， 1998， 6(1):1-24.

[9]費洪曉，黃勤徑，戴弋，等. 基于SVM與遺傳算法的燃煤鍋爐燃燒多目標優化系統[J]. 計算機應用研究，2008，25(3):811-813.

[10]郭琛，黃明，梁旭. 新自適應方式雙倍體遺傳算法求解作業車間調度問題[J]. 大連交通大學學報， 2008，29(3):78-81.

[11]雷英杰，張善文，李續武，等. MATLAB遺傳算法工具箱及應用[M]. 西安：西安電子科技大學出版社， 2005：146-206.