陳　丹，徐文遠(yuǎn)

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

?

·信息科學(xué)·

基于遺傳算法的軌道交通與常規(guī)公交線路優(yōu)化方案

陳丹1，2，徐文遠(yuǎn)1

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

為全面提高公共交通的整體效益,充分發(fā)揮軌道交通在公共交通中的骨干作用,需要對軌道交通影響范圍內(nèi)的常規(guī)公交線網(wǎng)進行優(yōu)化調(diào)整。文中結(jié)合城市軌道交通與常規(guī)公交相互協(xié)調(diào)的交通特點,提出基于“遺傳算法”的常規(guī)公交線網(wǎng)優(yōu)化模型。并結(jié)合實例，對哈爾濱市地鐵1號線的常規(guī)公交線網(wǎng)進行調(diào)整，選出最佳方案。

軌道交通;常規(guī)公交;遺傳算法;線路調(diào)整

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

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

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

1　基于軌道交通的常規(guī)公交調(diào)整

1.1調(diào)整目標(biāo)

調(diào)整目標(biāo)[7]如下:

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

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

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

1.2研究思路

根據(jù)優(yōu)化目標(biāo),以路網(wǎng)和出行相關(guān)數(shù)據(jù)為基礎(chǔ),確定目標(biāo)函數(shù)及約束條件。建立初始路網(wǎng)和理想模型,用遺傳算法在值域內(nèi)進行若干次迭算,當(dāng)滿足終止條件時停止跌算,得到理想解,得出線路優(yōu)化方案。

1.3模型的建立

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

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

(1)

其中,fij為小區(qū)i,j間的公交客流量,Tij(X)為當(dāng)前公交網(wǎng)絡(luò)條件下小區(qū)i,j間的公交出行時間。

(2)

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

常規(guī)公交的平均候車時間Tw為

(3)

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

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

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

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

非直線系數(shù)的公式為

(5)

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

建立線網(wǎng)優(yōu)化模型為

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

(6)

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

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

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

2　遺傳算法應(yīng)用

2.1遺傳編碼

模型的解空間由若干個公交網(wǎng)絡(luò)構(gòu)成,每個公交網(wǎng)絡(luò)都包含若干條公交線路,每條公交線路又連接若干個公交起訖站點。

假設(shè)某公交網(wǎng)路包含10個交通小區(qū),每個交通小區(qū)分別用阿拉伯?dāng)?shù)字2～11表示,其中2、3、6、8、11號小區(qū)需設(shè)起訖站點,其余為中轉(zhuǎn)站點,則路網(wǎng)公交線路情況可用下式表示:

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

(7)

其中,D是公交網(wǎng)絡(luò),hi_j是小區(qū)i,j間的公交線路。

所有公交線路均包含在該網(wǎng)絡(luò)中,但并非所有起訖點配對方式間都有公交線路連接。采用二進制編碼方式,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)的線路集構(gòu)成了問題的可行解集。計算時采用k-最短路法[11]，在約束式(4)的基礎(chǔ)上得出全部第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最短路。此時路網(wǎng)中并未包含軌道交通線路,因此,還需在路網(wǎng)中添加軌道交通線路。設(shè)研究路網(wǎng)中僅存在一條軌道交通線路,其值固定為1，放在編碼的末位。最終編碼為

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

(13)

2.2變化算子

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

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

(14)

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

(15)

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

(16)

(17)

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

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

這樣就得到滿足非直線系數(shù)和線長約束的子代解,對于不在公交線網(wǎng)內(nèi)的站點,視為不可行解而淘汰。

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

(18)

其中，

(19)

(20)

(21)

其中，

(22)

2.3適應(yīng)度函數(shù)

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

(23)

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

Rk=CTk+Pk。

(24)

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

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

2.4選擇算子

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

3　實例分析

哈爾濱市地鐵1號線南起哈南站，北至哈東站,途經(jīng)18個站點,全長27.3km。最高運行速度為80km/h,平均速度為30.17km/h。額定載客容量和日均載客量分別為1 470人和14.65萬人次。根據(jù)《城市道路交通規(guī)劃設(shè)計規(guī)范》，地鐵線路的直接吸引范圍[15]為軌道線路兩側(cè)500m帶狀范圍。本例選取西大橋站—博物館站—煙廠站路段進行研究。路網(wǎng)如圖2所示，路網(wǎng)中數(shù)字為公交車行駛時間(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　算例路網(wǎng)圖Fig.2　Network map of example road

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

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

(25)

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

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

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

表2　小區(qū)現(xiàn)狀配對情況表

續(xù)表2

配對模式可能的備選線路直線距離/km路線長度/km非直線系數(shù)第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　公交線路優(yōu)化方案

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

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

線路重復(fù)系數(shù)[17]α應(yīng)該越小越好,計算公式如下

(26)

其中,G總為軌道交通線路、線網(wǎng)的總長度，Li為地鐵影響范圍內(nèi)的常規(guī)公交線路i與地鐵線路相平行的距離，i為第i條與地鐵平行的線路，N為研究范圍內(nèi)與地鐵平行的線路總數(shù)。

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

4　結(jié)　語

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

[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]王煒.實用公交線網(wǎng)規(guī)劃方法研究[J].東南大學(xué)學(xué)報(自然科學(xué)版),1990,20(4):81-88.

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

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

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

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

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

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

[11] 鄭建斌,楊小曼,劉輝,等.遺傳小波神經(jīng)網(wǎng)絡(luò)用于極譜信號的流噪[J].西北大學(xué)學(xué)報(自然科學(xué)版), 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] 敖友云,遲洪欽.基于(μ+λ)選擇策略的多目標(biāo)優(yōu)化分段遺傳算法[J].計算機工程與科學(xué)，2006,28(9):91-93.

[15] 吳休鵬.武漢市軌道交通二號線接運公交線網(wǎng)優(yōu)化研究[D].武漢:武漢理工大學(xué),2011.

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

[17] 王衛(wèi)平.常規(guī)公交與城市軌道交通銜接理論方法與評價研究[D].廣州:華南理工大學(xué),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)

陳丹，男，四川資陽人，從事交通運輸、計算機應(yīng)用技術(shù)研究。

U491

A

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