王 寧，曹為政，儲(chǔ)曉雷

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

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

1 問(wèn)題描述及模型構(gòu)建

1.1 問(wèn)題描述

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

1.2 模型假設(shè)

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

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

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

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

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

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

6)假設(shè)沒(méi)有開(kāi)通接運(yùn)線路的情況下任意站點(diǎn)間也可以相互到達(dá)，假定到達(dá)所需時(shí)間為開(kāi)通接運(yùn)線路時(shí)間的二倍。

圖1 接運(yùn)公交線路示意圖

1.3 模型建立

1.3.1 目標(biāo)函數(shù)

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

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

1.3.2 約束條件

1)線路長(zhǎng)度

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

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

2)非直系數(shù)

η=d/l≤1.4.

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

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

3)站點(diǎn)通行能力約束

C中≤60n/tp，

C首末≤60nα/tpk.

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

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

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

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

2.1 元胞遺傳算法

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

2.2 染色體編碼

本文采用一個(gè)十進(jìn)制整數(shù)串來(lái)表示接運(yùn)公交網(wǎng)絡(luò)，各個(gè)整數(shù)串內(nèi)又包含幾個(gè)子串。用單個(gè)子串來(lái)表示一條接運(yùn)公交線路，子串上的數(shù)字表示接運(yùn)公交車站的序列，并以軌道交通站點(diǎn)為開(kāi)始和結(jié)束。接運(yùn)站點(diǎn)的編號(hào)定位其十進(jìn)制編碼的位數(shù)，軌道交通車站的編號(hào)從最大的接運(yùn)公交車站編號(hào)后一位開(kāi)始。如:

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

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

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

2.3 遺傳操作

2.3.1 評(píng)價(jià)函數(shù)

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

2.3.2 交叉和變異

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

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

2.4 元胞遺傳算法流程

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

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

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

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

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

Step5：判斷是否滿足終止條件，若不滿足轉(zhuǎn)至Step3，如果滿足，退出迭代得到計(jì)算結(jié)果。

3 算例仿真

3.1 算例說(shuō)明

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

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

表1 站點(diǎn)高峰時(shí)段接運(yùn)需求O-D矩陣

3.2 算例結(jié)果與分析

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

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

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

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

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

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

4 結(jié) 語(yǔ)

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