鄧連波，何 淵，曾俊豪，周文梁

中南大學交通運輸工程學院，湖南長沙 410075

在城市公共交通系統(tǒng)中，城市軌道交通與常規(guī)公交之間的有效銜接，對于充分發(fā)揮公共交通的網(wǎng)絡化優(yōu)勢具有重要意義．為此，在進行公交線網(wǎng)設(shè)計時，需要充分考慮軌道交通線路的走向和站點分布，由此形成公交接駁線網(wǎng)問題(feeder-bus network-design problem, FBNDP)，即針對存在的一個軌道交通系統(tǒng)，設(shè)計對應的公交接駁線路網(wǎng)絡，使之形成一個整體的接駁換乘系統(tǒng)．FBNDP通過接駁車站、線路經(jīng)由及開行頻率[1]確定城市公交接駁線路方案．

KUAH等[1]提出，由于FBNDP包含旅行商問題且目標函數(shù)具有非線性，是一個典型的多項式復雜程度的非確定性問題，即NP難(non-deterministic polynomial hard, NP-hard)問題，適于采用啟發(fā)式算法求解．BYRNE等[2]對KUAH等[1]建立的公交站點和軌道車站間“多對一”的規(guī)劃模型進行求解，并提出FBNDP．LENSTRA等[3]驗證了遺傳算法對于求解類似于FBNDP這種包含多個變量和多個約束的NP難問題，具有較高的適應度和匹配性．KUAN等[4]也通過遺傳算法得到FBNDP較好的解形式．鄧連波等[5]考慮公交站點與軌道車站“多對多”情形，建立基于換乘網(wǎng)絡的接駁線網(wǎng)優(yōu)化模型．近年來，針對公交接駁線網(wǎng)優(yōu)化問題，許多學者采用遺傳算法進行求解．LI等[6]提供可以降低乘客到達接駁公交成本的接駁公交調(diào)度模型，并利用遺傳算法求解大型線網(wǎng)．SUN等[7]以搜尋基于總出行時間最小化的接駁公交路徑和時刻表為目標，構(gòu)建針對個人需求的定制公交優(yōu)化模型．ANASTASIOS等[8]采用遺傳算法求解需求響應的接駁公交最后一公里問題．TAPLIN等[9]構(gòu)建基于最短步行距離到達接駁公交車站的模型，并通過遺傳算法搜尋最大需求公交站點．針對FBNDP，研究多將公交站點與軌道車站之間的關(guān)系模式分為“多對一”和“多對多”的情形討論，但公交站點仍限制在僅允許被單一線路服務．

對于與FBNDP問題類似的開放式車輛路徑問題，如何構(gòu)造滿足需求可拆分的解是解決此類問題的關(guān)鍵．研究已提出一些求解方法[10]，如列生成算法[11]、禁忌搜索算法[12-14]等．

本研究受需求可拆分條件下車輛路徑問題的啟發(fā)，針對經(jīng)典FBNDP中每一個公交站點只被單一接駁線路服務的限制問題，將其擴充至每個公交站點可以被多條公交接駁線路服務，即公交站點和公交接駁線路間具有“多對多”的關(guān)系，使之更符合實際客流分布規(guī)律．由此形成需求可拆分的公交接駁線網(wǎng)優(yōu)化問題(feeder-bus network-design problem with split delivery, FBNDP-SD)．通過分析換乘網(wǎng)絡總費用，建立需求可拆分情形下的公交接駁線網(wǎng)優(yōu)化模型，針對此問題設(shè)計改進遺傳算法，并分析討論不同公交站點客流需求強度下的優(yōu)化結(jié)果．

1 公交接駁線網(wǎng)描述

經(jīng)典FBNDP滿足以下假設(shè)：① 每一個公交站點只由一條公交接駁線路服務；② 每一條公交接駁線路只連接到一個軌道接駁車站；③ 所有公交接駁線路的速度和能力統(tǒng)一；④ 每一公交接駁線路在其上的每一公交站點停靠．

滿足假設(shè)①和②時，公交站點和公交線路間是多對一情形，與實際接駁線網(wǎng)存在較大差別．為此，取消假設(shè)①，即允許每一個公交站點被多條公交接駁線路服務，將該問題拓展至需求在多條線路間具有可拆分性的情形，形成FBNDP-SD．

FBNDP-SD接駁線網(wǎng)相關(guān)的基礎(chǔ)網(wǎng)絡包括I個常規(guī)公交站點和J個軌道交通車站，記公交站點集合為B={1,2,…,I}， 軌道車站集合為T={I+1,I+2,…,I+J}， 網(wǎng)絡節(jié)點集合N=B∪T． 記任意節(jié)點i、j間的距離為Lij，i,j∈N．

2 FBNDP-SD的優(yōu)化建模

2.1 FBNDP-SD的構(gòu)成約束

定義Xihk及Yijk表示站點間、站點和線路間關(guān)系：

i=1,2,…,I+J;h=1,2,…,I+J;k=1,2,…,K.

i=1,2,…,I;j=I+1,…,I+J;k=1,2,…,K.

FBNDP-SD線網(wǎng)需要滿足以下網(wǎng)絡結(jié)構(gòu)約束：

(1)

(2)

(3)

(4)

(5)

(6)

i=1,2,…,I;k=1,2,…,K

(7)

j=I+1,I+2,…,I+J;k=1,2,…,K

(8)

d=I+1,I+2,…,I+J

(9)

(10)

(11)

上述網(wǎng)絡結(jié)構(gòu)約束中，式(1)保證FBNDP-SD線網(wǎng)的連通性，即公交站點集合須通過接駁線路，或通過其他公交站點接續(xù)至軌道交通車站．其中，H為所有接駁軌道交通車站和部分公交站點的集合，H為N的子集．

式(2)至式(4)保證每條接駁線路的完整性，式(2)表示每條公交接駁線路僅連接1個軌道交通車站；式(3)表明接駁線路均終止于軌道交通車站；式(4)限定接駁線路至少應包含1個公交站點和1個軌道交通車站．

式(5)至式(8)為接駁線網(wǎng)中線路與車站的關(guān)系約束，式(5)表示需求可拆分情形下，每一公交站點至少有1條接駁線路經(jīng)由；式(6)至式(7)表示同一線路上單個站點僅?？?次，且該線路必須是一個無環(huán)的簡單路；式(8)是接駁線路k與站點i、j間的關(guān)系變量Yijk約束．

2.2 公交接駁線網(wǎng)優(yōu)化模型

包含乘客廣義出行費用和運營者運營成本的系統(tǒng)費用最小化優(yōu)化目標函數(shù)為

(12)

其中，Zk為公交接駁線路k相關(guān)的系統(tǒng)費用，即

(13)

(14)

客流Pid選擇線路k的客流量與換乘網(wǎng)絡路徑費用有關(guān)．以Logit分配作為客流選擇函數(shù)，則該OD客流在線路k上的分配客流量為

(15)

基于需求可拆分的公交接駁線網(wǎng)優(yōu)化模型由目標函數(shù)(12)和約束條件(1)至(11)、客流選擇函數(shù)(15)以及關(guān)聯(lián)函數(shù)(13)和(14)組成．與FBNDP優(yōu)化模型相比，除網(wǎng)絡結(jié)構(gòu)約束變化外，還增加了線路間客流選擇函數(shù)(15)．

(16)

其中，Pk和Lk為第k條接駁線路的總客流需求和線路長度．相應的線路費用為

(17)

3 模型求解

FBNDP具有多個變量及約束條件，求解方法多采用啟發(fā)式算法[1]，F(xiàn)BNDP-SD較FBNDP更難求解，本研究采用遺傳算法[15]進行求解．由于FBNDP-SD問題構(gòu)解較為困難，在初始種群個體生成和交叉操作生成子代個體過程中，均是先生成FBNDP線網(wǎng)，再以此為基礎(chǔ)生成FBNDP-SD線網(wǎng)．

對初始種群個體生成操作，首先通過選取公交站點不斷擴充公交線網(wǎng)，形成不包含重復點的初始個體，再插入重復點形成FBNDP-SD個體，構(gòu)成初始接駁線網(wǎng)種群，并根據(jù)客流選擇規(guī)律在接駁線路間分配客流量和公交線路開行頻率．對于交叉操作，針對父代雙親個體，剔除重復站點形成FBNDP個體，采用與文獻[5]類似方法雙親單子生成2個FBNDP子代個體，并將剔除的重復站點按照一定插入策略隨機插入FBNDP子代個體，完成FBNDP-SD子代個體的構(gòu)造．具體算法流程見圖1．

3.1 編碼方案和適應度

公交接駁線網(wǎng)問題一般采用自然數(shù)編碼，即采用公交車站與軌道交通車站編號表示，使站點與基因片段對應．如當B={1,2,3,4,5,6,7}，T={8,9,10}時， 某一接駁線網(wǎng)表示為1 2 3 8 4 5 9 6 7 10，該接駁線網(wǎng)由3條接駁線路組成，對應上述3個字串1 2 3 8、4 5 9及6 7 10．

以最小化目標函數(shù)的倒數(shù)為基礎(chǔ)，考慮約束條件(11)并引入罰因子λ, 構(gòu)造個體Ω的適應度函數(shù)為

圖1 算法流程圖Fig.1 Framework of the proposed algorithm

3.2 初始種群生成

隨機選擇軌道車站，按照一定概率選擇未在線網(wǎng)中的公交車站，將其加入該接駁車站所屬的某條線路，或由該軌道車站和公交站點組成新的直連接駁線路．對于軌道車站j和公交車站i構(gòu)成的直連接駁線路，可依據(jù)式(13)和式(16)，獲得線路的最優(yōu)系統(tǒng)成本DCij為

(18)

FBNDP初始線網(wǎng)構(gòu)建完畢后，對每一公交站點嘗試作為重復點，構(gòu)造包含重復點的FBNDP-SD初始線網(wǎng)．

算法1初始FBNDP-SD線網(wǎng)生成算法，其步驟為

1) 置集合B′=B為構(gòu)建當前接駁線路的可選擇公交站集，Ω為此時的接駁線網(wǎng)，且線路編號k=1．

2) 若B′=φ， 轉(zhuǎn)5)．否則，從T中選取1個軌道車站j， 選擇方法為等概率隨機選?。?/p>

5) 對于已構(gòu)造的FBNDP初始線網(wǎng)，采取重復點添加策略構(gòu)造FBNDP-SD初始線網(wǎng)：對于每個公交站點i， 分別找到距離其最近，且不包含其本身的線路加入(以點到點之間的距離作為衡量)，使i點同屬于不同線路，將線網(wǎng)轉(zhuǎn)換為需求可拆分情形并記錄重復點i′集合．

對每一FBNDP-SD線網(wǎng)，重復點在各條線路的流量分配算法見算法2．

算法2線路客流分配及頻率確定算法，其步驟為

1) 已知包含重復點的初始解，其中的重復點i′為需要進行客流需求拆分的點．

采用算法1，每次構(gòu)造1個個體，直至達到初始種群規(guī)模n為止．

3.3 遺傳算子設(shè)計

3.3.1 選擇復制

采用2種機制增強算法搜索能力：① 競爭機制．復制n個個體的種群以產(chǎn)生2n個個體的種群，兩兩比較隨機分成n對后的個體適應度，保留較優(yōu)的種群規(guī)模個體；② 入侵機制．采用初始種群生成算法產(chǎn)生n個個體并找到其中適應度最高的ρn個個體，用于替代上述個體中適應度最低的ρn個個體，其中，ρ∈(0,1)為入侵比例，可以提前設(shè)定為常數(shù)或采用動態(tài)控制策略．

3.3.2 交叉操作

對選中的父代個體，采用雙親雙子的交叉操作，其步驟為

1) 剔除雙親的重復點，形成FBNDP個體．具體對于每個重復點，比較其在各線路上的客流量，保留客流量最大的重復點并剔除該點在其他線路中的重復點．

2) 對已剔除重復點的FBNDP父代雙親個體，分別以某一父代個體為基礎(chǔ)，采用文獻[2]的雙親單子交叉操作，對于FBNDP父代個體Ωl1及Ωl2， 以Ωl1為基礎(chǔ)，以Ωl1的首個基因位對應的公交站為起點，按順序比較其在兩個父代中下一個站點與該線路接駁軌道車站間的線路費用，保留較好點作為新生子代的基因，并以之為起點繼續(xù)比較．在Ωl1和Ωl2中去除該基因，構(gòu)造當前線路的結(jié)束條件為選取基因?qū)壍儡囌荆畬λ泄徽军c重復此過程，形成子代．

3) 將兩個父代個體的重復點按概率插入兩個FBNDP子代個體，形成FBNDP-SD子代個體．將父代個體中的重復點作為集合，將集合中的每個重復點隨機插入其中一個子代個體(為保證插入重復點的科學性和效率性，插入位置為該點所在線路外的線路上，最靠近該點的5個公交點的位置)．對重復點的各個備選插入位置，通過調(diào)用算法2計算各線路的客流量及頻率，并優(yōu)化備選重復點所在線路的徑路經(jīng)由，接受使線網(wǎng)費用下降程度最大的插入方案．

3.3.3 變異操作

為增強全局尋找最優(yōu)解能力，以變異概率Pm隨機選取基因點，并依據(jù)概率p接受較差變異解．若選中公交站點，將其隨機插入到其他公交站點對應的基因位；若選中軌道接駁車站，則隨機選擇另一軌道接駁車站替代．對變異解需考慮其變異質(zhì)量，即接受概率為[16]

3.4 輔助優(yōu)化策略

1)徑路經(jīng)由優(yōu)化策略．對交叉操作中的子代個體，其每一條接駁線路均需優(yōu)化其徑路經(jīng)由．單條接駁線路的徑路經(jīng)優(yōu)化后均可視為一個具有固定終點的車輛路徑問題．采取在線路內(nèi)部隨機挑選2個公交站點i和j進行單點交換的方法逐步優(yōu)化線路徑路．

2) 精英保存策略．每次產(chǎn)生新一輪滿足種群規(guī)模的子代后，將本輪最優(yōu)解與歷史最好解比較并保留二者中較優(yōu)解．

3.5 終止條件

算法終止于達到最大進化代數(shù)Tmax或目標函數(shù)值在T′代內(nèi)收斂．

4 算例分析

采用文獻[5]構(gòu)造的通用算例網(wǎng)絡，包含80個公交站點和4個軌道車站．遺傳算法中設(shè)置種群規(guī)模為100，交叉概率為0.8，變異概率為0.08，最優(yōu)個體保持代數(shù)為120，最大進化代數(shù)為1 500．采用C#語言編程，并分析不同客流需求強度下的優(yōu)化結(jié)果．模型參數(shù)見表1．

表1 模型參數(shù)

4.1 固定客流強度下的優(yōu)化結(jié)果

考慮每個公交站點與各軌道車站均有客流需求且客流分布均等．單位時段內(nèi)公交站的客流需求強度為200人．最優(yōu)接駁線網(wǎng)如圖1．其中，接駁線路數(shù)22條，平均長度1.70 km．線路每小時開行頻率為13.54．接駁線網(wǎng)方案存在1個重復點，為40號站點．系統(tǒng)總費用為53 273元．旅客乘坐公交時間與旅客乘坐列車時間比值為1.20∶0.81，旅客繞行比為1.25．

FBNDP-SD最優(yōu)線網(wǎng)與文獻[5]中FBNDP結(jié)果的對比見表2，系統(tǒng)總費用的降低了0.03%．可見，在相同線網(wǎng)規(guī)模及軌道車站客流分布等條件下，允許需求可拆分情形時，接駁線網(wǎng)方案更為優(yōu)化合理，線路長度略有減少，但開行頻率維持不變．由于問題的復雜性大大增加，使得運算時間顯著增加．

表2 需求拆分與否條件下的最優(yōu)接駁線網(wǎng)對比

4.2 站點客流需求差異的優(yōu)化結(jié)果

上述算例中每個公交站點客流需求強度在接駁線網(wǎng)中的地位一致，且公交站點客流需求在軌道交通站點之間均勻分布，接駁線路交叉關(guān)系并不明顯．為對比不同客流需求下的線網(wǎng)結(jié)果，對公交站點采取在50～400人按50的倍數(shù)隨機設(shè)置單位時段客流需求，并且每個公交站點與軌道交通站點間的客流呈線路兩頭大中間小的不均勻分布，與4個軌道交通車站間客流比例分別為40%、10%、10%及40%，考察FBNDP-SD線網(wǎng)的變化規(guī)律．

求得的最優(yōu)接駁線網(wǎng)如圖2與圖3(站點編號右下角標表示客流需求)．其中，接駁線路24條，平均長度為1.74 km．線路每小時開行頻率為13.96．系統(tǒng)總費用為60 980 元．接駁線網(wǎng)方案存在8個重復點，分別是26、19、20和79號站點，其中，19號公交站點重復5次，這些站點的客流需求均為200 人或300 人．

圖2 固定客流強度下的最優(yōu)接駁線網(wǎng)Fig.2 Best result under constant flow volume

圖3 站點客流需求差異的最優(yōu)接駁線網(wǎng)Fig.3 Best result under varying flow volume

與固定客流強度下的優(yōu)化結(jié)果相比，重復點的數(shù)量隨整體網(wǎng)絡客流強度的增大由1個增加到8個，重復站點設(shè)置更傾向于客流較多的站點．

在相同線網(wǎng)條件下，需求可拆分情況下FBNDP-SD最優(yōu)線網(wǎng)與不考慮需求可拆分條件的FBNDP最優(yōu)線網(wǎng)各項指標對比見表3．其中，表3第2行表示不考慮需求可拆分條件的公交接駁最優(yōu)線網(wǎng)結(jié)果．通過表3可知，系統(tǒng)總費用降低比率達到0.61%，與固定客流強度下的優(yōu)化結(jié)果(0.03%) 對比， 費用降低效果更為明顯，且線路平

表3 需求拆分與否條件下的最優(yōu)接駁線網(wǎng)各項指標對比

均長度減少，開行頻率略有上升．考慮需求可拆分情形可降低線路的平均長度，為乘客提供更多的線路選擇，說明在客流需求量大的情況下，允許需求拆分、多條線路共同為某些需求量大的站點提供服務， 對降低網(wǎng)絡費用、 優(yōu)化線網(wǎng)結(jié)構(gòu)更具實際意義．

結(jié) 語

本研究針對經(jīng)典FBNDP，進一步放寬假設(shè)條件，允許需求在線路間拆分，使公交站點可以為多條公交接駁線路服務，建立基于換乘網(wǎng)絡且滿足需求可拆分的公交接駁線網(wǎng)優(yōu)化模型．根據(jù)模型特點設(shè)計了基于遺傳算法的求解方法．模型和算法綜合考慮需求可拆分條件下的網(wǎng)絡結(jié)構(gòu)和客流選擇行為等約束條件；在優(yōu)化算法中，以FBNDP的解為基礎(chǔ)，融入重復點的生成和插入策略，實現(xiàn)FBNDP解和FBNDP-SD解的相互轉(zhuǎn)換，有效解決了FBNDP-SD構(gòu)解困難的問題．優(yōu)化結(jié)果表明，在考慮公交需求可拆分的情形下，F(xiàn)BNDP-SD線網(wǎng)能夠為公交站點提供多條接駁線路進行選擇，從而有效分流乘客，降低線路成本，優(yōu)化線網(wǎng)結(jié)構(gòu)．對于線網(wǎng)客流強度較高的情況或者具有較大客流量的站點，考慮公交需求可拆分更具實際意義．