王 寧，曹為政，儲曉雷

(1.蘭州交通大學 機電技術研究所，甘肅 蘭州 730070; 2.黑龍江科技大學 計算機與信息工程學院，黑龍江 哈爾濱 150000；3.黑龍江工程學院 測繪工程學院，黑龍江 哈爾濱 150050)

接運公交線路是指專門為城市軌道交通集散客流的常規(guī)公交線路，接運公交線路的布設是為了與城市軌道交通相互銜接，各自發(fā)揮優(yōu)勢，因此，接運公交的合理設計是提高城市公共交通服務水平的根本環(huán)節(jié)。接運公交設計問題(Feeder bus network design problem，F(xiàn)BNDP)[1]就是確定接運站點、線路經(jīng)由、開車頻率三部分內容組成的城市常規(guī)公交接運線路方案。本文主要針對“線路經(jīng)由”這一部分進行研究，即接運公交線路的優(yōu)化設計問題。針對接運線路優(yōu)化設計問題，現(xiàn)有研究主要以運營成本、出行成本和社會成本最小為目標，建立線路設計模型[2-4]，很少分析接運公交線路設計和客流集散情況的聯(lián)系，因此，本文以單位時間里程集散客流量最大為優(yōu)化目標，設計了軌道交通接運公交線路優(yōu)化設計模型。針對既有模型求解多以啟發(fā)式算法為主[5-8]，其中遺傳算法的應用最為廣泛，但遺傳算法自身存在斂速度慢、易陷入局部最優(yōu)解等問題。因此，本文提出采取元胞遺傳算法(CGA)對模型求解，采用三組不同參數(shù)策略，通過仿真對遺傳算法和元胞遺傳算法進行比較，驗證元胞遺傳算法在接運公交線路優(yōu)化設計問題中的可行性。

1 問題描述及模型構建

1.1 問題描述

以圖1為例對問題進行闡述，如圖1所示軌道交通線路附近區(qū)域存在一系列的客流聚集點，這些客流聚集點多數(shù)是常規(guī)公交車站、居住小區(qū)、商業(yè)大樓、農貿市場等場所，具有較高的客流量[9]。由于軌道交通和常規(guī)公交的功能定位不同，所以單一的軌道交通和單一的常規(guī)公交都無法滿足客流需求。因此，合理地設計接運公交路線可以在一定程度上盡可能多地滿足客流需求。因此，本文針對軌道交通附近的客流需求點，研究如何布設接運線路可以在保證乘客出行時間較短的情況下，同時保證單位里程內更多的將客流運送至其需求點。

1.2 模型假設

本文研究如何布設接運線路連接公交站點和軌道交通站點，為實現(xiàn)上述研究提出以下假設：

1)假設軌道交通間接吸引的客流量及客流分布已知，均為固定值，不受接運公交線網(wǎng)優(yōu)劣的影響。

2)假設出行者選擇出行方式時既包含軌道交通也包含常規(guī)公交，出行者以換乘次數(shù)最小作為選擇出行路徑的首要標準，假定出行者可接受的最大換乘次數(shù)為2次。

3)假設所有接運線路的公交運營車輛為統(tǒng)一類型。

4)假設接運公交線路上運營車輛速度、發(fā)車頻率恒定且已知。

5)假設乘客等車時間為發(fā)車間隔時間的一半。

6)假設沒有開通接運線路的情況下任意站點間也可以相互到達，假定到達所需時間為開通接運線路時間的二倍。

圖1 接運公交線路示意圖

1.3 模型建立

1.3.1 目標函數(shù)

基于以上假設，綜合考慮線網(wǎng)的接運效率(滿足客流需求)、出行者的出行成本以及接運線路的性能，建立布設接運線路的優(yōu)化模型。確定目標函數(shù)輸入為客流量OD矩陣，確定目標函數(shù)最終的輸出是以實現(xiàn)最大的客流運轉量、最小的接運時間、最短接運線路長度為目的[9-13]，計算式為

式中：Q為公交站點和軌道交通站點間市民出行客流矩陣；G為接運公交線網(wǎng)總客運周轉量；L為接運公交線網(wǎng)內的線路總長度；T為接運公交線網(wǎng)接運客流所花費的時間總和；T1為出行者乘坐接運線路運營車輛的在車時間；T2為出行者乘坐接運線路運營車輛的候車時間；I為公交接運站點(客流需求站點)；i∈I為第i個接運公交站點；J為軌道交通站點；j∈J為第j個軌道交通站點；q(i，j)為在接運公交站點i站上車經(jīng)接運公交到達軌道交通j站下車的接運需求量；q(j，i)為在軌道交通站點j站上車經(jīng)接運公交到達接運公交站點i站下車的接運需求量；lij為接運公交站點i到軌道交通站點j的線路長度；xij為決策變量，當站點i到站點j設有接運線路時為1，當站點i到站點j未有接運線路時為2；v為接運公交線路運營車輛的行駛速度;f為接運公交線路運營車輛的發(fā)車間隔。

1.3.2 約束條件

1)線路長度

lmin≤l≤lmax=Vb×Tmax/60.

式中：l為常規(guī)公交線路長度，m；Vb為常規(guī)公交的平均行駛速度，km/h；Tmax為城市95%出行者的單程出行時間，min。

2)非直系數(shù)

η=d/l≤1.4.

式中：η為公交線路非直線系數(shù)；d為公交線路首末站點之間的空間直線距離；l為線路的效率。

《城市道路交通規(guī)劃設計規(guī)范》(GB50220-95)中規(guī)定公交線路非直線系數(shù)不大于1.4。

3)站點通行能力約束

C中≤60n/tp，

C首末≤60nα/tpk.

式中：C中，C首末分別為中間站、首末站的通行能力，人/h；n為高峰小時每輛公交在中間站點的平均載客人數(shù)，人；tp為高峰小時公交車到達站點的時間間隔，min；α為高峰小時公交車滿載率，%；k為線路最大斷面流量與起訖站點前后斷面流量比值。

綜上所述，優(yōu)化模型為

2 基于元胞遺傳算法的模型求解過程

本文規(guī)劃模型變量個數(shù)是變化的，對于此類模型無法用確定性解析法求解。本文意在對軌道交通沿線的公交線路進行調整，在對算法進行分析的基礎上進行全局優(yōu)化，是一種適合種群規(guī)模不大求解的算法，遺傳算法具備這種特性。但由于遺傳算法還具有容易出現(xiàn)早熟現(xiàn)象、局部搜索能力不足等特征，導致遺傳算法在后期的收斂速度慢，甚至無法收斂到最優(yōu)解。元胞遺傳算法不僅在一定程度上改進了效率低、容易過早收斂的缺點，而且在解決實際組合優(yōu)化問題中表現(xiàn)出高效的性能及較高的貼合性，因此，本文選用元胞遺傳算法。

2.1 元胞遺傳算法

元胞遺傳算法( Celluar Genetic Algorithms，CGA)是將元胞自動機理論及遺傳算法理論相互結合而產生的進化算法，與經(jīng)典遺傳算法不同，主要體現(xiàn)在種群中個體分布是否有序[14]。經(jīng)典遺傳算法中種群個體分布是無序的，而元胞遺傳算法中種群個體分布是規(guī)則有序的。如圖2所示，元胞遺傳算法種群中的個體分布在一個環(huán)形聯(lián)通的網(wǎng)絡拓撲中，個體與它的周圍個體形成了一個小生境，中心個體僅限于與它的鄰居進行選擇、交叉、變異，使得優(yōu)良的個體得以在種群中緩慢擴散[15]。

2.2 染色體編碼

本文采用一個十進制整數(shù)串來表示接運公交網(wǎng)絡，各個整數(shù)串內又包含幾個子串。用單個子串來表示一條接運公交線路，子串上的數(shù)字表示接運公交車站的序列，并以軌道交通站點為開始和結束。接運站點的編號定位其十進制編碼的位數(shù)，軌道交通車站的編號從最大的接運公交車站編號后一位開始。如:

Route1(7 2 5 8 13)，Route2(5 6 9 14)，Route3(4 11 14).

它所代表的接運公交線網(wǎng)染色體為:(7 2 5 8 13 5 6 9 14 4 11 14).

該染色體的具體含義為該接運公交線網(wǎng)由Route1、Route2和Route3 3條線路組成，其中編號為13、14代表軌道交通站點，分別為這3條線路的終點。這種表示法是唯一的，一個染色體僅能標識一個解向量。由于字符串中的每個軌道交通車站都表示一條線路的終點。

2.3 遺傳操作

2.3.1 評價函數(shù)

建立軌道交通接運線路優(yōu)化模型是為了生成接運線路連接接運站點和軌道交通站點，以實現(xiàn)最大的客流運轉量、最小的接運時間、最短的接運線路長度為目的，因此，評價函數(shù)為之前建立的目標函數(shù)。

2.3.2 交叉和變異

元胞遺傳算法區(qū)別于經(jīng)典遺傳算法最為關鍵的步驟是其交叉和變異過程。這里采用馮·諾依曼型鄰居結構，每個個體包含4個鄰居，每次交叉過程從鄰居中隨機選取一個作為交叉父本，進行交叉操作生成子代個體。pc為交叉操作的概率，每次種群中平均有pc*pop-size個染色體進行交叉操作。

為保持種群的多樣性，定義Pm為遺傳系統(tǒng)中的變異概率，這個概率表明每次進化均有Pm·pop-size個染色體用來進行變異操作。由i=1到i=pop-size，重復下列過程：從區(qū)間[0，1]產生隨機數(shù)r，若r≤Pm，則重新生成第i個染色體，并檢驗其可行性，若可行，則用新的染色體代替原來的染色體。

2.4 元胞遺傳算法流程

結合2.1—2.3節(jié)所述，本文采用元胞遺傳算法的流程如下：

Step1：初始參數(shù)設定，生成初始種群，采用整數(shù)編碼；

Step2：選擇操作，根據(jù)給定的更新策略和鄰居結構，選取中心個體及其鄰居；

Step3：交叉變異操作，根據(jù)2.3.2條提出的方法，對父代個體進行運算，得到子代個體；

Step4：個體更新，根據(jù)2.3.1條提出的適應度函數(shù)比較子代和父代優(yōu)劣，進行替換；

Step5：判斷是否滿足終止條件，若不滿足轉至Step3，如果滿足，退出迭代得到計算結果。

3 算例仿真

3.1 算例說明

以蘭州市軌道交通一號線的“西關十字”站和“省政府”站周邊接運站點的接運線路布設為實例進行分析。西關什字站和省政府站位于中山路與張掖路的步行街交叉口，地處蘭州市繁華商業(yè)路段，附近商廈林立，土地開發(fā)強度大，城市功能完善，客流集散量很大。為使斷面客流均勻分布，及時疏散需要轉乘的出行者，在“西關十字”和“省政府”兩站周邊設置相應接運線路。

以“西關十字”和“省政府”兩站為輻射中心，選取了12個重要站點作為接運公交站點。各接運站點及其對應的編號為：1白馬浪、2中山橋、3市委、4時代廣場、5通渭路、6武都路十字、7白銀路口、8雙城門、9柏道路、10隴鑫大廈、11航天賓館、12鼓樓巷。為了編碼的連續(xù)性，“西關十字”站編號為13，“省政府”站編號為14。實地調研了12個公交站點及兩個與公交站點重合的軌道交通站點的客流情況，并在蘭州公交四公司、六公司獲取了14個站點間客流高峰時期接運需求矩陣，如表1所示，各站點間的最短距離矩陣見參考文獻[16]。

表1 站點高峰時段接運需求O-D矩陣

3.2 算例結果與分析

使用Matlab編程，分別采用GA和CGA 兩種不同的算法，采用3組種群大小、交叉、變異不同的參數(shù)運行程序。以其中一組為例，參數(shù)設定如下：種群大小α=200、交叉概率Pc=0.1、變異概率Pm=0.01種植代數(shù)Gen=100，得到的算法求解結果收斂曲線如圖3所示。從圖3可以看出，經(jīng)典遺傳算法到80代左右開始收斂，而元胞遺傳算法僅需到30代就達到收斂，此時種群趨于穩(wěn)定，沒有太大變化，元胞遺傳算法且目標函數(shù)值更高于經(jīng)典遺傳算法所得。針對該算例多次遺傳算法和元胞遺傳算法進行多次重復運算，收斂次數(shù)、計算結果相差不大，元胞遺傳算法局優(yōu)于經(jīng)典遺傳算法。

表2為最終計算結果，由表2可知，不同參數(shù)策略對應的優(yōu)化過程不同，采取種群設定為100時，相比于其他策略算法效率較高。通過對不同參數(shù)策略下

圖3 元胞遺傳算法和經(jīng)典遺傳算法的迭代過程

2種算法的比較可知，元胞遺傳算法的收斂速度遠高于經(jīng)典遺傳算法，而且能夠快速收斂至目標函數(shù)的最大解值。

表2 三組不同參數(shù)下兩種算法得到的計算結果

最終得到的優(yōu)化線路結果通過MATLAB兩種算法求得最優(yōu)解相同為(4 3 5 14 1 2 13 12 11 8 13 7 8 13 9 10 6 14)，目標函數(shù)值753.4，其中包含5條接運公交線路(4 3 5 14)、(1 2 13)、(12 11 8 13)、(7 8 13)、(9 10 6 14)。

4 結 語

針對軌道交通與公共交通接運線路的優(yōu)化模型優(yōu)化問題，經(jīng)典遺傳算法具有收斂速度慢且易陷入局部最優(yōu)解的缺點，本文提出使用元胞遺傳算法進行求解。首先研究現(xiàn)有的接運線路優(yōu)化模型，綜合考慮接運效率、乘客出行成本等因素建立接運公交線網(wǎng)的數(shù)學模型。采用3種不同參數(shù)策略分別對比經(jīng)典遺傳算法和元胞遺傳算法的迭代次數(shù)及目標函數(shù)值。對比結果發(fā)現(xiàn)，元胞遺傳算法的收斂速度遠超于經(jīng)典遺傳算法，且求得的目標函數(shù)值穩(wěn)定，表明元胞遺傳算法運用于接運線路的優(yōu)化問題具有可行性。