基于遺傳算法的軌道交通與常規公交線路優化方案

陳　丹，徐文遠

(1.東北林業大學 土木工程學院, 黑龍江 哈爾濱　150040； 2.北京市市政工程設計研究總院有限公司， 北京　100082)

?

·信息科學·

基于遺傳算法的軌道交通與常規公交線路優化方案

陳丹1，2，徐文遠1

(1.東北林業大學 土木工程學院, 黑龍江 哈爾濱150040； 2.北京市市政工程設計研究總院有限公司， 北京100082)

為全面提高公共交通的整體效益,充分發揮軌道交通在公共交通中的骨干作用,需要對軌道交通影響范圍內的常規公交線網進行優化調整。文中結合城市軌道交通與常規公交相互協調的交通特點,提出基于“遺傳算法”的常規公交線網優化模型。并結合實例，對哈爾濱市地鐵1號線的常規公交線網進行調整，選出最佳方案。

軌道交通;常規公交;遺傳算法;線路調整

隨著軌道交通的興建,出現了常規公交與軌道交通之間惡性競爭、資源浪費等現象,而軌道交通建成后很難再調整,因此開展基于軌道交通的現有公交線路優化工作已迫在眉睫。

國外在二十世紀七十年代初就開始了各種交通方式間銜接問題的研究,Lampkin等人[1]用乘客舒適度和出行時間作為主要指標,建立交通線網優化模型。基于出行分配、路徑規劃、行車間隔,Cedar和Wilson提出了線網設計的三階段法,Martins等人研究啟發式算法在線網優化中的應用[2]。Kuah等人考慮接駁公交社會效益和系統效益,建立了系統收益分析模型[3]。國內相關研究較晚,王煒教授等人以換乘客流最小和運量最大為目標,提出“逐條布設、優化成網”的方法[4]。蔣冰蕾等人建立了以換乘站點周轉量極大值和換乘線接運效率極大值為目標的目標優化搜索算法[5]。韓傳峰,胡志偉等人基于平均換乘次數,通過數學模型來研究線網拓撲結構,并對系統系性能進行評價[6]。這類算法大都通過建立評價指標或者迭代運算實現。綜合評價等證優類方法存在針對性不足,效率低下,優化結果不理想等特點;而一般的迭代運算方法非常容易陷入局部最優的陷阱，從而出現“死循環”現象,使迭代無法進行,導致優化方案不夠理想。遺傳算法屬于進化算法，用該方法求出優化問題的最優解能很好避免傳統算法的缺點,具有明顯的優越性。

常規遺傳算法在迭代過程中,交叉和變異概率常取一個固定值，這是運算性能下降的重要因素。遺傳運算初期稍大的交叉概率能提高搜索效率,后期其值較小能減少理想基因的損壞;而變異概率則是個體性能越好，其值越小。本文給出了交叉變異概率的自適應公式,在運算過程中采用自適應交叉和變異概率值,對改進傳統遺傳算法性能和提高優化求解效能具有重要意義。

1　基于軌道交通的常規公交調整

1.1調整目標

調整目標[7]如下:

1)優化公交線網布局,增加軌道交通客流量，縮短成本回收期;

2)加強公交子系統間的合作,提高系統出行效率,提升系統運營效益;

3)降低各交通出行方式間的不良競爭,減少資源浪費。

1.2研究思路

根據優化目標,以路網和出行相關數據為基礎,確定目標函數及約束條件。建立初始路網和理想模型,用遺傳算法在值域內進行若干次迭算,當滿足終止條件時停止跌算,得到理想解,得出線路優化方案。

1.3模型的建立

1.3.1目標函數本文以乘客公交出行總時間為目標函數，其最小值即為最優線路方案。軌道交通線路確定后就不能再輕易改變,在計算時將其算作一條固定的線路。

以線路各OD點間的搭配方式為元素構成集合,由集合構成搭配矩陣X,用r表示搭配方式、s表示搭配方式間的第s最短路,r，s分別構成矩陣的行和列。xrs=1表示搭配方式r的第s最短路上存在公交線路,xrs=0表示搭配方式r的第s最短路上不存在公交線路。出行者總出行時間[8]T為

(1)

其中,fij為小區i,j間的公交客流量,Tij(X)為當前公交網絡條件下小區i,j間的公交出行時間。

(2)

其中,lij為小區i,j之間公交線路距離,Tr為步行時間,Tw為候車時間,n為換乘次數,Th為一次換乘時間,v為公交或軌道交通行駛速度(一般采用平均速度)。

常規公交的平均候車時間Tw為

(3)

其中,L為公交線路總長度,n為公交車輛數。

當路網中公交中間站點的運輸服務能力不能滿足公共交通出行客流需求時,應設起訖站點(OD點)。起訖站點客流運輸能力與高峰小時滿載率、高峰小時發車間隔等多個因素有關,其計算公式為

(4)其中,C′為起訖站點運輸能力,R為公交車輛額定載客數,r為高峰小時滿載率,t為高峰小時發車間隔,

1.3.2約束條件根據《城市道路交通規劃設計規范》GB 50220-1995，確定線路非直線系數和線長為公交線路優化模型的約束條件[9]。

非直線系數的公式為

(5)

其中,aws為搭配w間第s最短路非直線系數,lws為搭配w間第s最短路的長度,dws為搭配w的直線距離。

建立線網優化模型為

s.t. 8 km≤lws≤12 km，aws≤1.4。

(6)

其中,lws為公交線路長度,aws為非直線系數。

1.3.3遺傳算法概述遺傳算法屬于全局性概率搜索算法[10]。首先需確定初始解,然后不斷迭代逐步優化當前解,直到得出理想解時停止運算。迭代運算是遺傳算法的重要環節,其采用了自然選擇和有性繁殖的原理,在繼承父代優良基因的基礎上,生成性能更好的子代解。運算方式如下:

圖1　遺傳算法示意圖Fig.1　Sketch Map of genetic algorithm

2　遺傳算法應用

2.1遺傳編碼

模型的解空間由若干個公交網絡構成,每個公交網絡都包含若干條公交線路,每條公交線路又連接若干個公交起訖站點。

假設某公交網路包含10個交通小區,每個交通小區分別用阿拉伯數字2～11表示,其中2、3、6、8、11號小區需設起訖站點,其余為中轉站點,則路網公交線路情況可用下式表示:

D=(h2_3,h2_6,h2_8,h2_11,h3_6,h3_8,h3_11,h6_8,h6_11,h8_11)。

(7)

其中,D是公交網絡,hi_j是小區i,j間的公交線路。

所有公交線路均包含在該網絡中,但并非所有起訖點配對方式間都有公交線路連接。采用二進制編碼方式,1表示兩起訖點間有公交線路連接,0表示兩起訖點間無公交線路連接。采用式(7)的配對順序，則

D=(1,0,0,1,1,0,0,0,1,0)。

(8)

式(8)表明,具有公交線路相連的起訖站為:2站與3站、2站與11站、3站與6站和6站與11站。可行線路必須滿足式(6),由式(5)和(6)得:

lmin≤lij≤min(1.4dij,lmax)。

(9)

其中,lmin和lmax分別為線路最小和最大長度,lij為站點i,j間線路長度,dij為站點i,j間直線距離。

滿足式(9)的線路集構成了問題的可行解集。計算時采用k-最短路法[11]，在約束式(4)的基礎上得出全部第k-最短路的解集為

H(2_11,1)=(1,3,5,7,9,10),

(10)

H(2_11,3)=(1,2,4,5,6,8,9,10)。

(11)

H(2_11,1)表示2站與11站間的第一最短路徑,H(2_11,3)表示2站與11站間的第三最短路徑。求出滿足條件的所有最短路:

D=(0,2,0,3,0,0,0,0,0,0)。

(12)

表明所有站點中僅2站與6站、2站與11站間存在公交線路，同時也表示2站與6站間的公交線路是第2最短路,2站與11站間的公交線路是第3最短路。此時路網中并未包含軌道交通線路,因此,還需在路網中添加軌道交通線路。設研究路網中僅存在一條軌道交通線路,其值固定為1，放在編碼的末位。最終編碼為

D=(0,2,0,3,0,0,0,0,0,0,1)。

(13)

2.2變化算子

上一代解集中好的起訖點配對方式和優良的公交線路均通過交叉運算遺傳給了下一代解集。在進行交叉運算時,采用單點式交叉運算,對于如下的父本

D1=(1,0,0,2,|0,0,4,0,3,1),

(14)

D2=(0,2,1,0,|0,3,0,1,0,1)。

(15)

交叉點的確定采用隨機方式,假設在第4,5位編碼之間設置交叉點。交叉后生成新個體為

(16)

(17)

這樣父體的部分起訖點配對方式及公交線路就遺傳給了子代,而軌道交通部分則未發生變化。

變異運算,采用隨機變化的方式，即在低概率下,隨機選取子代中一種配對方式,并隨機賦值。軌道交通,不進行變異運算。

這樣就得到滿足非直線系數和線長約束的子代解,對于不在公交線網內的站點,視為不可行解而淘汰。

交叉和變異概率對迭代結果的影響十分嚴重，交叉概率pc的取值范圍一般為0.40～0.99，變異概率pm的取值范圍為0.001～0.1。前部分運算希望交叉概率稍微偏大,這樣能夠使算法的搜索功能提高;在后部分運算時，使其值偏小能夠減少對理想基因的損壞,使收斂速度提高。對于適應性高、性能優良的個體，希望其變異概率越小越好,對于適應度低、不好的個體，則希望其有較大的變異。用自適應法對二者取值，

(18)

其中，

(19)

(20)

(21)

其中，

(22)

2.3適應度函數

適應度函數采用式(1)～(6)。確定線路的優先等級為:二次換乘<一次換乘<直達線路。進行客流量分配時,軌道交通作為一條固定不變的線路參與其中。當優先級相同，有多個選擇路線時,按出行效用進行選擇,使用Logit模型[12]計算選取某路線的概率

(23)

其中,Rk為k號出行路徑的交通阻抗,R為出行路徑交通阻抗均值,θ為分配參數,m為出行路徑數量。

Rk=CTk+Pk。

(24)

其中,C為時間價值,Tk為路徑出行時間,Pk為出行票價。

Tk的計算同式(2),由式(2),(23)和(24)得出各OD點間的出行者在各個路徑上的出行時間及出行量。進一步可以得出公交系統出行的總時間[13],也是研究模型的適應度函數值。

2.4選擇算子

選擇運算方法較多,在具體設計時需根據問題實際情況和規模大小綜合確定。確定性選擇運算[14]方式常常應用于路網規模較大的情況。而隨機性選擇運算方式(如輪盤賭法)，則常常應用于路網中線路或站點較少的情況。

3　實例分析

哈爾濱市地鐵1號線南起哈南站，北至哈東站,途經18個站點,全長27.3km。最高運行速度為80km/h,平均速度為30.17km/h。額定載客容量和日均載客量分別為1 470人和14.65萬人次。根據《城市道路交通規劃設計規范》，地鐵線路的直接吸引范圍[15]為軌道線路兩側500m帶狀范圍。本例選取西大橋站—博物館站—煙廠站路段進行研究。路網如圖2所示，路網中數字為公交車行駛時間(min)。其中地鐵1號線線路為圖中虛線部分(F-M-S),公交車和地鐵的平均運行速度分別為15km/h和30km/h。OD需求矩陣如表1所示。

A 和興路; B 文政街; C 文昌街;D 文明街;E 果戈理大街;F 西大橋;G 通達街; H 撫順街; I 龍江街;J 人和街; K 民安街; L 鼎新三道街;M 博物館; N 花園街; O 大成街圖2　算例路網圖Fig.2　Network map of example road

算例中小區A，E，M，P，S處設置起訖站點,由于F-S間存在地鐵線路,故不再將其進行起訖站點配對分析。對各配對方式的線長和非直線系數情況進行檢測,結果見表2。

取公交線路的最大長度、最小長度分別為6km，2km,模式EM不滿足式(4)，而被淘汰。地鐵線路FS，FM段長度分別為4.5km，2.5km,平均速度30km/h,則FM，MS間的行駛時間分別為5min，4min。出行者根據效用選乘地鐵或常規公交,客流分配方式優先等級為:2次換乘<1次換乘<直達線路。當存在多條換乘情況相同的線路時,乘客選中某線路的概率按下式計算，

(25)

其中,ti為i線路的行駛時間，A為同一優先等級下的所有可選線路。

使用Matlab軟件[16]進行編程。忽略乘客公共交通出行的步行時間,換乘平均耗時取3min。假設案例路網中共有公交車20輛，種群的規模初步定為30,初始以0.95的交叉概率進行交叉運算，以0.10的變異概率進行變異運算,隨著迭代進行，根據式(18)～(22)確定其相應值。初始種群采用隨機方式生成,進行選擇運算時,選擇方法采用輪盤賭法,反復迭代20次。程序在相同條件下運行5次,最后取5次結果的平均值如圖3所示，表3為得出的優化方案。

表1　公共交通需求OD矩陣表

表2　小區現狀配對情況表

續表2

配對模式可能的備選線路直線距離/km路線長度/km非直線系數第K最短路MPM-Q-H-P2.12.251.071M-T-P2.12.51.192P-H-M-S2.823.51.241P-T-R-S2.823.51.242P-H-Q-M-N-I-S2.8241.423

表3　公交線路優化方案

圖3　遺傳算法收斂過程Fig.3　Convergence process of genetic algorithm

進行線路方案優化后,路網中乘客出行總時間為469 758min,乘客平均出行耗時19.41min，小于25min,符合《城市道路交通規劃設計規范》中居民單程最大出行時耗的要求。路網中各公交線路的非直線系數均小于1.4,滿足城市公交線路非直線系數不得大于1.4的要求。

線路重復系數[17]α應該越小越好,計算公式如下

(26)

其中,G總為軌道交通線路、線網的總長度，Li為地鐵影響范圍內的常規公交線路i與地鐵線路相平行的距離，i為第i條與地鐵平行的線路，N為研究范圍內與地鐵平行的線路總數。

算例中地鐵線路長度為7.0km,調整前線路重復距離為16.50km,此時計算線路重復系數為2.36;調整后重復距離為6.0km,此時計算線路重復系數為0.86,大大減少了常規公交與地鐵間的惡性競爭,線路優化方案取得了良好的效果。

4　結　語

本文立足于遺傳算法在優化問題中的優點,以研究范圍內乘客出行時耗最小為線網優化的目標函數,以公交線路長度和非直線系數為約束條件,介紹了遺傳算法在基于軌道交通的現有公交線網優化工作中的應用,彌補了一般迭代算法容易陷入局部最優陷阱或出現“死循環”現象而導致優化方案不盡合理的缺點,得到了較理想的優化方案。結合實際，對哈爾濱市地鐵1號線影響范圍內的現有公交線路進行優化調整,取得了很好的效果。說明運用遺傳算法能科學、合理、便捷地對常規公交線路進行優化調整,對提高公交系統運行效率、降低資源浪費具有重要意義。

[1]LAMPKIN W, SAALMANS P D. The design of routes, service frequencies, and schedules for a municipal bus undertaking: A case study [J]. Operation Researeh Quart,1998,51(3): 41-42.

[2]CEDER A, WILSON N H M. Bus network design[J]. Transportation Research Part B: Methodological, 1986, 20(4): 331-344.

[3]MARTINS C L, PATO M V. Seareh strategies for the feeder bus network design problem[J] European Journal of Operation Researeh, 1998, 106(2): 425-440.

[4]王煒.實用公交線網規劃方法研究[J].東南大學學報(自然科學版),1990,20(4):81-88.

[5]蔣冰蕾，孫愛充.城市快速軌道交通接運公交路線網規劃[J].系統工程理論與實踐,1998(3):130-134.

[6]韓傳峰,胡志偉.城市公交路網性能評估的網絡圖方法[J].系統工程,2003, 21(3):58-61.

[7]吳嬌蓉,汪煜,劉瑩.城市軌道交通各發展階段的運行特征及在公交系統中的作用[J].城市軌道交通研究,2007(6):9-11.

[8]林伯梁,楊富社,李鵬.基于出行費用最小化的公交網絡優化模型[J].中國公路學報,1999,12(1):79-83.

[9]國家質檢總局(GN-GB).GB 50220-1995城市道路交通規劃設計規范[S].北京：人民交通出版社，1995.

[10] 韓瑞鋒.遺傳算法原理與應用實例[M].北京:兵器工業出版社,2010.

[11] 鄭建斌,楊小曼,劉輝,等.遺傳小波神經網絡用于極譜信號的流噪[J].西北大學學報(自然科學版), 2002,32(5):447-450.

[12] KALOUPTSIDIS N, PSARAKI V. Approximations of choice probabilities in mixed logit models [J]. European Journal of Operational Research,2010,200(2):529-535.

[13] NAYEEM M A, RAHMAN M K, RAHMAN M S. Transit network design by genetic algorithm with elitism [J]. Transportation Research Part C: Emerging Technologies, 2014, 46: 30-45.

[14] 敖友云,遲洪欽.基于(μ+λ)選擇策略的多目標優化分段遺傳算法[J].計算機工程與科學，2006,28(9):91-93.

[15] 吳休鵬.武漢市軌道交通二號線接運公交線網優化研究[D].武漢:武漢理工大學,2011.

[16] 虞蕾,趙紅,趙宗濤.一種基于遺傳算法的航跡優化方法[J].西北大學學報(自然科學版),2006,36(2):205-208.

[17] 王衛平.常規公交與城市軌道交通銜接理論方法與評價研究[D].廣州:華南理工大學,2011.

(編輯李靜)

Optimization scheme of rail transportation and conventional bus lines based on genetic algorithm

CHEN Dan1，2, XU Wen-yuan1

(1.School of Civil Engineering, Northeast Forestry University, Harbin 1500140, China；2.Beijing Municipal Engineering Design & Research Institute Co.,Ltd., Beijing 100082, China)

In order to enhance the overall efficiency of public transportation, give full play to the backbone role of rail transit in public transportation, adjust the regular bus network within the scope of the influence of rail transit, in this paper, combined with the characteristics of regular bus and new rail transit, the optimization model is put forward based on the "genetic algorithm". And using genetic algorithm to adjust the regular bus network around the Harbin city metro line, the best scheme is selected.

rail transit; conventional transit; genetic algorithm; circuit conditioning

2015-08-17

黑龍江省交通運輸廳重點科技基金資助項目(2011TZD037)

陳丹，男，四川資陽人，從事交通運輸、計算機應用技術研究。

U491

A

10.16152/j.cnki.xdxbzr.2016-03-011