鄧連波,何 淵,曾俊豪,周文梁
中南大學(xué)交通運(yùn)輸工程學(xué)院,湖南長(zhǎng)沙 410075
在城市公共交通系統(tǒng)中,城市軌道交通與常規(guī)公交之間的有效銜接,對(duì)于充分發(fā)揮公共交通的網(wǎng)絡(luò)化優(yōu)勢(shì)具有重要意義.為此,在進(jìn)行公交線網(wǎng)設(shè)計(jì)時(shí),需要充分考慮軌道交通線路的走向和站點(diǎn)分布,由此形成公交接駁線網(wǎng)問(wèn)題(feeder-bus network-design problem, FBNDP),即針對(duì)存在的一個(gè)軌道交通系統(tǒng),設(shè)計(jì)對(duì)應(yīng)的公交接駁線路網(wǎng)絡(luò),使之形成一個(gè)整體的接駁換乘系統(tǒng).FBNDP通過(guò)接駁車站、線路經(jīng)由及開(kāi)行頻率[1]確定城市公交接駁線路方案.
KUAH等[1]提出,由于FBNDP包含旅行商問(wèn)題且目標(biāo)函數(shù)具有非線性,是一個(gè)典型的多項(xiàng)式復(fù)雜程度的非確定性問(wèn)題,即NP難(non-deterministic polynomial hard, NP-hard)問(wèn)題,適于采用啟發(fā)式算法求解.BYRNE等[2]對(duì)KUAH等[1]建立的公交站點(diǎn)和軌道車站間“多對(duì)一”的規(guī)劃模型進(jìn)行求解,并提出FBNDP.LENSTRA等[3]驗(yàn)證了遺傳算法對(duì)于求解類似于FBNDP這種包含多個(gè)變量和多個(gè)約束的NP難問(wèn)題,具有較高的適應(yīng)度和匹配性.KUAN等[4]也通過(guò)遺傳算法得到FBNDP較好的解形式.鄧連波等[5]考慮公交站點(diǎn)與軌道車站“多對(duì)多”情形,建立基于換乘網(wǎng)絡(luò)的接駁線網(wǎng)優(yōu)化模型.近年來(lái),針對(duì)公交接駁線網(wǎng)優(yōu)化問(wèn)題,許多學(xué)者采用遺傳算法進(jìn)行求解.LI等[6]提供可以降低乘客到達(dá)接駁公交成本的接駁公交調(diào)度模型,并利用遺傳算法求解大型線網(wǎng).SUN等[7]以搜尋基于總出行時(shí)間最小化的接駁公交路徑和時(shí)刻表為目標(biāo),構(gòu)建針對(duì)個(gè)人需求的定制公交優(yōu)化模型.ANASTASIOS等[8]采用遺傳算法求解需求響應(yīng)的接駁公交最后一公里問(wèn)題.TAPLIN等[9]構(gòu)建基于最短步行距離到達(dá)接駁公交車站的模型,并通過(guò)遺傳算法搜尋最大需求公交站點(diǎn).針對(duì)FBNDP,研究多將公交站點(diǎn)與軌道車站之間的關(guān)系模式分為“多對(duì)一”和“多對(duì)多”的情形討論,但公交站點(diǎn)仍限制在僅允許被單一線路服務(wù).
對(duì)于與FBNDP問(wèn)題類似的開(kāi)放式車輛路徑問(wèn)題,如何構(gòu)造滿足需求可拆分的解是解決此類問(wèn)題的關(guān)鍵.研究已提出一些求解方法[10],如列生成算法[11]、禁忌搜索算法[12-14]等.
本研究受需求可拆分條件下車輛路徑問(wèn)題的啟發(fā),針對(duì)經(jīng)典FBNDP中每一個(gè)公交站點(diǎn)只被單一接駁線路服務(wù)的限制問(wèn)題,將其擴(kuò)充至每個(gè)公交站點(diǎn)可以被多條公交接駁線路服務(wù),即公交站點(diǎn)和公交接駁線路間具有“多對(duì)多”的關(guān)系,使之更符合實(shí)際客流分布規(guī)律.由此形成需求可拆分的公交接駁線網(wǎng)優(yōu)化問(wèn)題(feeder-bus network-design problem with split delivery, FBNDP-SD).通過(guò)分析換乘網(wǎng)絡(luò)總費(fèi)用,建立需求可拆分情形下的公交接駁線網(wǎng)優(yōu)化模型,針對(duì)此問(wèn)題設(shè)計(jì)改進(jìn)遺傳算法,并分析討論不同公交站點(diǎn)客流需求強(qiáng)度下的優(yōu)化結(jié)果.
經(jīng)典FBNDP滿足以下假設(shè):① 每一個(gè)公交站點(diǎn)只由一條公交接駁線路服務(wù);② 每一條公交接駁線路只連接到一個(gè)軌道接駁車站;③ 所有公交接駁線路的速度和能力統(tǒng)一;④ 每一公交接駁線路在其上的每一公交站點(diǎn)停靠.
滿足假設(shè)①和②時(shí),公交站點(diǎn)和公交線路間是多對(duì)一情形,與實(shí)際接駁線網(wǎng)存在較大差別.為此,取消假設(shè)①,即允許每一個(gè)公交站點(diǎn)被多條公交接駁線路服務(wù),將該問(wèn)題拓展至需求在多條線路間具有可拆分性的情形,形成FBNDP-SD.
FBNDP-SD接駁線網(wǎng)相關(guān)的基礎(chǔ)網(wǎng)絡(luò)包括I個(gè)常規(guī)公交站點(diǎn)和J個(gè)軌道交通車站,記公交站點(diǎn)集合為B={1,2,…,I}, 軌道車站集合為T(mén)={I+1,I+2,…,I+J}, 網(wǎng)絡(luò)節(jié)點(diǎn)集合N=B∪T. 記任意節(jié)點(diǎn)i、j間的距離為L(zhǎng)ij,i,j∈N.
定義Xihk及Yijk表示站點(diǎn)間、站點(diǎn)和線路間關(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)絡(luò)結(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)絡(luò)結(jié)構(gòu)約束中,式(1)保證FBNDP-SD線網(wǎng)的連通性,即公交站點(diǎn)集合須通過(guò)接駁線路,或通過(guò)其他公交站點(diǎn)接續(xù)至軌道交通車站.其中,H為所有接駁軌道交通車站和部分公交站點(diǎn)的集合,H為N的子集.
式(2)至式(4)保證每條接駁線路的完整性,式(2)表示每條公交接駁線路僅連接1個(gè)軌道交通車站;式(3)表明接駁線路均終止于軌道交通車站;式(4)限定接駁線路至少應(yīng)包含1個(gè)公交站點(diǎn)和1個(gè)軌道交通車站.
式(5)至式(8)為接駁線網(wǎng)中線路與車站的關(guān)系約束,式(5)表示需求可拆分情形下,每一公交站點(diǎn)至少有1條接駁線路經(jīng)由;式(6)至式(7)表示同一線路上單個(gè)站點(diǎn)僅???次,且該線路必須是一個(gè)無(wú)環(huán)的簡(jiǎn)單路;式(8)是接駁線路k與站點(diǎn)i、j間的關(guān)系變量Yijk約束.
包含乘客廣義出行費(fèi)用和運(yùn)營(yíng)者運(yùn)營(yíng)成本的系統(tǒng)費(fèi)用最小化優(yōu)化目標(biāo)函數(shù)為
(12)
其中,Zk為公交接駁線路k相關(guān)的系統(tǒng)費(fèi)用,即
(13)
(14)
客流Pid選擇線路k的客流量與換乘網(wǎng)絡(luò)路徑費(fèi)用有關(guān).以Logit分配作為客流選擇函數(shù),則該OD客流在線路k上的分配客流量為
(15)
基于需求可拆分的公交接駁線網(wǎng)優(yōu)化模型由目標(biāo)函數(shù)(12)和約束條件(1)至(11)、客流選擇函數(shù)(15)以及關(guān)聯(lián)函數(shù)(13)和(14)組成.與FBNDP優(yōu)化模型相比,除網(wǎng)絡(luò)結(jié)構(gòu)約束變化外,還增加了線路間客流選擇函數(shù)(15).
(16)
其中,Pk和Lk為第k條接駁線路的總客流需求和線路長(zhǎng)度.相應(yīng)的線路費(fèi)用為
(17)
FBNDP具有多個(gè)變量及約束條件,求解方法多采用啟發(fā)式算法[1],F(xiàn)BNDP-SD較FBNDP更難求解,本研究采用遺傳算法[15]進(jìn)行求解.由于FBNDP-SD問(wèn)題構(gòu)解較為困難,在初始種群個(gè)體生成和交叉操作生成子代個(gè)體過(guò)程中,均是先生成FBNDP線網(wǎng),再以此為基礎(chǔ)生成FBNDP-SD線網(wǎng).
對(duì)初始種群個(gè)體生成操作,首先通過(guò)選取公交站點(diǎn)不斷擴(kuò)充公交線網(wǎng),形成不包含重復(fù)點(diǎn)的初始個(gè)體,再插入重復(fù)點(diǎn)形成FBNDP-SD個(gè)體,構(gòu)成初始接駁線網(wǎng)種群,并根據(jù)客流選擇規(guī)律在接駁線路間分配客流量和公交線路開(kāi)行頻率.對(duì)于交叉操作,針對(duì)父代雙親個(gè)體,剔除重復(fù)站點(diǎn)形成FBNDP個(gè)體,采用與文獻(xiàn)[5]類似方法雙親單子生成2個(gè)FBNDP子代個(gè)體,并將剔除的重復(fù)站點(diǎn)按照一定插入策略隨機(jī)插入FBNDP子代個(gè)體,完成FBNDP-SD子代個(gè)體的構(gòu)造.具體算法流程見(jiàn)圖1.
公交接駁線網(wǎng)問(wèn)題一般采用自然數(shù)編碼,即采用公交車站與軌道交通車站編號(hào)表示,使站點(diǎn)與基因片段對(duì)應(yīng).如當(dāng)B={1,2,3,4,5,6,7},T={8,9,10}時(shí), 某一接駁線網(wǎng)表示為1 2 3 8 4 5 9 6 7 10,該接駁線網(wǎng)由3條接駁線路組成,對(duì)應(yīng)上述3個(gè)字串1 2 3 8、4 5 9及6 7 10.
以最小化目標(biāo)函數(shù)的倒數(shù)為基礎(chǔ),考慮約束條件(11)并引入罰因子λ, 構(gòu)造個(gè)體Ω的適應(yīng)度函數(shù)為
圖1 算法流程圖Fig.1 Framework of the proposed algorithm
隨機(jī)選擇軌道車站,按照一定概率選擇未在線網(wǎng)中的公交車站,將其加入該接駁車站所屬的某條線路,或由該軌道車站和公交站點(diǎn)組成新的直連接駁線路.對(duì)于軌道車站j和公交車站i構(gòu)成的直連接駁線路,可依據(jù)式(13)和式(16),獲得線路的最優(yōu)系統(tǒng)成本DCij為
(18)
FBNDP初始線網(wǎng)構(gòu)建完畢后,對(duì)每一公交站點(diǎn)嘗試作為重復(fù)點(diǎn),構(gòu)造包含重復(fù)點(diǎn)的FBNDP-SD初始線網(wǎng).
算法1初始FBNDP-SD線網(wǎng)生成算法,其步驟為
1) 置集合B′=B為構(gòu)建當(dāng)前接駁線路的可選擇公交站集,Ω為此時(shí)的接駁線網(wǎng),且線路編號(hào)k=1.
2) 若B′=φ, 轉(zhuǎn)5).否則,從T中選取1個(gè)軌道車站j, 選擇方法為等概率隨機(jī)選?。?/p>
5) 對(duì)于已構(gòu)造的FBNDP初始線網(wǎng),采取重復(fù)點(diǎn)添加策略構(gòu)造FBNDP-SD初始線網(wǎng):對(duì)于每個(gè)公交站點(diǎn)i, 分別找到距離其最近,且不包含其本身的線路加入(以點(diǎn)到點(diǎn)之間的距離作為衡量),使i點(diǎn)同屬于不同線路,將線網(wǎng)轉(zhuǎn)換為需求可拆分情形并記錄重復(fù)點(diǎn)i′集合.
對(duì)每一FBNDP-SD線網(wǎng),重復(fù)點(diǎn)在各條線路的流量分配算法見(jiàn)算法2.
算法2線路客流分配及頻率確定算法,其步驟為
1) 已知包含重復(fù)點(diǎn)的初始解,其中的重復(fù)點(diǎn)i′為需要進(jìn)行客流需求拆分的點(diǎn).
采用算法1,每次構(gòu)造1個(gè)個(gè)體,直至達(dá)到初始種群規(guī)模n為止.
3.3.1 選擇復(fù)制
采用2種機(jī)制增強(qiáng)算法搜索能力:① 競(jìng)爭(zhēng)機(jī)制.復(fù)制n個(gè)個(gè)體的種群以產(chǎn)生2n個(gè)個(gè)體的種群,兩兩比較隨機(jī)分成n對(duì)后的個(gè)體適應(yīng)度,保留較優(yōu)的種群規(guī)模個(gè)體;② 入侵機(jī)制.采用初始種群生成算法產(chǎn)生n個(gè)個(gè)體并找到其中適應(yīng)度最高的ρn個(gè)個(gè)體,用于替代上述個(gè)體中適應(yīng)度最低的ρn個(gè)個(gè)體,其中,ρ∈(0,1)為入侵比例,可以提前設(shè)定為常數(shù)或采用動(dòng)態(tài)控制策略.
3.3.2 交叉操作
對(duì)選中的父代個(gè)體,采用雙親雙子的交叉操作,其步驟為
1) 剔除雙親的重復(fù)點(diǎn),形成FBNDP個(gè)體.具體對(duì)于每個(gè)重復(fù)點(diǎn),比較其在各線路上的客流量,保留客流量最大的重復(fù)點(diǎn)并剔除該點(diǎn)在其他線路中的重復(fù)點(diǎn).
2) 對(duì)已剔除重復(fù)點(diǎn)的FBNDP父代雙親個(gè)體,分別以某一父代個(gè)體為基礎(chǔ),采用文獻(xiàn)[2]的雙親單子交叉操作,對(duì)于FBNDP父代個(gè)體Ωl1及Ωl2, 以Ωl1為基礎(chǔ),以Ωl1的首個(gè)基因位對(duì)應(yīng)的公交站為起點(diǎn),按順序比較其在兩個(gè)父代中下一個(gè)站點(diǎn)與該線路接駁軌道車站間的線路費(fèi)用,保留較好點(diǎn)作為新生子代的基因,并以之為起點(diǎn)繼續(xù)比較.在Ωl1和Ωl2中去除該基因,構(gòu)造當(dāng)前線路的結(jié)束條件為選取基因?qū)?yīng)軌道車站.對(duì)所有公交站點(diǎn)重復(fù)此過(guò)程,形成子代.
3) 將兩個(gè)父代個(gè)體的重復(fù)點(diǎn)按概率插入兩個(gè)FBNDP子代個(gè)體,形成FBNDP-SD子代個(gè)體.將父代個(gè)體中的重復(fù)點(diǎn)作為集合,將集合中的每個(gè)重復(fù)點(diǎn)隨機(jī)插入其中一個(gè)子代個(gè)體(為保證插入重復(fù)點(diǎn)的科學(xué)性和效率性,插入位置為該點(diǎn)所在線路外的線路上,最靠近該點(diǎn)的5個(gè)公交點(diǎn)的位置).對(duì)重復(fù)點(diǎn)的各個(gè)備選插入位置,通過(guò)調(diào)用算法2計(jì)算各線路的客流量及頻率,并優(yōu)化備選重復(fù)點(diǎn)所在線路的徑路經(jīng)由,接受使線網(wǎng)費(fèi)用下降程度最大的插入方案.
3.3.3 變異操作
為增強(qiáng)全局尋找最優(yōu)解能力,以變異概率Pm隨機(jī)選取基因點(diǎn),并依據(jù)概率p接受較差變異解.若選中公交站點(diǎn),將其隨機(jī)插入到其他公交站點(diǎn)對(duì)應(yīng)的基因位;若選中軌道接駁車站,則隨機(jī)選擇另一軌道接駁車站替代.對(duì)變異解需考慮其變異質(zhì)量,即接受概率為[16]
1)徑路經(jīng)由優(yōu)化策略.對(duì)交叉操作中的子代個(gè)體,其每一條接駁線路均需優(yōu)化其徑路經(jīng)由.單條接駁線路的徑路經(jīng)優(yōu)化后均可視為一個(gè)具有固定終點(diǎn)的車輛路徑問(wèn)題.采取在線路內(nèi)部隨機(jī)挑選2個(gè)公交站點(diǎn)i和j進(jìn)行單點(diǎn)交換的方法逐步優(yōu)化線路徑路.
2) 精英保存策略.每次產(chǎn)生新一輪滿足種群規(guī)模的子代后,將本輪最優(yōu)解與歷史最好解比較并保留二者中較優(yōu)解.
算法終止于達(dá)到最大進(jìn)化代數(shù)Tmax或目標(biāo)函數(shù)值在T′代內(nèi)收斂.
采用文獻(xiàn)[5]構(gòu)造的通用算例網(wǎng)絡(luò),包含80個(gè)公交站點(diǎn)和4個(gè)軌道車站.遺傳算法中設(shè)置種群規(guī)模為100,交叉概率為0.8,變異概率為0.08,最優(yōu)個(gè)體保持代數(shù)為120,最大進(jìn)化代數(shù)為1 500.采用C#語(yǔ)言編程,并分析不同客流需求強(qiáng)度下的優(yōu)化結(jié)果.模型參數(shù)見(jiàn)表1.
表1 模型參數(shù)
考慮每個(gè)公交站點(diǎn)與各軌道車站均有客流需求且客流分布均等.單位時(shí)段內(nèi)公交站的客流需求強(qiáng)度為200人.最優(yōu)接駁線網(wǎng)如圖1.其中,接駁線路數(shù)22條,平均長(zhǎng)度1.70 km.線路每小時(shí)開(kāi)行頻率為13.54.接駁線網(wǎng)方案存在1個(gè)重復(fù)點(diǎn),為40號(hào)站點(diǎn).系統(tǒng)總費(fèi)用為53 273元.旅客乘坐公交時(shí)間與旅客乘坐列車時(shí)間比值為1.20∶0.81,旅客繞行比為1.25.
FBNDP-SD最優(yōu)線網(wǎng)與文獻(xiàn)[5]中FBNDP結(jié)果的對(duì)比見(jiàn)表2,系統(tǒng)總費(fèi)用的降低了0.03%.可見(jiàn),在相同線網(wǎng)規(guī)模及軌道車站客流分布等條件下,允許需求可拆分情形時(shí),接駁線網(wǎng)方案更為優(yōu)化合理,線路長(zhǎng)度略有減少,但開(kāi)行頻率維持不變.由于問(wèn)題的復(fù)雜性大大增加,使得運(yùn)算時(shí)間顯著增加.
表2 需求拆分與否條件下的最優(yōu)接駁線網(wǎng)對(duì)比
上述算例中每個(gè)公交站點(diǎn)客流需求強(qiáng)度在接駁線網(wǎng)中的地位一致,且公交站點(diǎn)客流需求在軌道交通站點(diǎn)之間均勻分布,接駁線路交叉關(guān)系并不明顯.為對(duì)比不同客流需求下的線網(wǎng)結(jié)果,對(duì)公交站點(diǎn)采取在50~400人按50的倍數(shù)隨機(jī)設(shè)置單位時(shí)段客流需求,并且每個(gè)公交站點(diǎn)與軌道交通站點(diǎn)間的客流呈線路兩頭大中間小的不均勻分布,與4個(gè)軌道交通車站間客流比例分別為40%、10%、10%及40%,考察FBNDP-SD線網(wǎng)的變化規(guī)律.
求得的最優(yōu)接駁線網(wǎng)如圖2與圖3(站點(diǎn)編號(hào)右下角標(biāo)表示客流需求).其中,接駁線路24條,平均長(zhǎng)度為1.74 km.線路每小時(shí)開(kāi)行頻率為13.96.系統(tǒng)總費(fèi)用為60 980 元.接駁線網(wǎng)方案存在8個(gè)重復(fù)點(diǎn),分別是26、19、20和79號(hào)站點(diǎn),其中,19號(hào)公交站點(diǎn)重復(fù)5次,這些站點(diǎn)的客流需求均為200 人或300 人.
圖2 固定客流強(qiáng)度下的最優(yōu)接駁線網(wǎng)Fig.2 Best result under constant flow volume
圖3 站點(diǎn)客流需求差異的最優(yōu)接駁線網(wǎng)Fig.3 Best result under varying flow volume
與固定客流強(qiáng)度下的優(yōu)化結(jié)果相比,重復(fù)點(diǎn)的數(shù)量隨整體網(wǎng)絡(luò)客流強(qiáng)度的增大由1個(gè)增加到8個(gè),重復(fù)站點(diǎn)設(shè)置更傾向于客流較多的站點(diǎn).
在相同線網(wǎng)條件下,需求可拆分情況下FBNDP-SD最優(yōu)線網(wǎng)與不考慮需求可拆分條件的FBNDP最優(yōu)線網(wǎng)各項(xiàng)指標(biāo)對(duì)比見(jiàn)表3.其中,表3第2行表示不考慮需求可拆分條件的公交接駁最優(yōu)線網(wǎng)結(jié)果.通過(guò)表3可知,系統(tǒng)總費(fèi)用降低比率達(dá)到0.61%,與固定客流強(qiáng)度下的優(yōu)化結(jié)果(0.03%) 對(duì)比, 費(fèi)用降低效果更為明顯,且線路平
表3 需求拆分與否條件下的最優(yōu)接駁線網(wǎng)各項(xiàng)指標(biāo)對(duì)比
均長(zhǎng)度減少,開(kāi)行頻率略有上升.考慮需求可拆分情形可降低線路的平均長(zhǎng)度,為乘客提供更多的線路選擇,說(shuō)明在客流需求量大的情況下,允許需求拆分、多條線路共同為某些需求量大的站點(diǎn)提供服務(wù), 對(duì)降低網(wǎng)絡(luò)費(fèi)用、 優(yōu)化線網(wǎng)結(jié)構(gòu)更具實(shí)際意義.
本研究針對(duì)經(jīng)典FBNDP,進(jìn)一步放寬假設(shè)條件,允許需求在線路間拆分,使公交站點(diǎn)可以為多條公交接駁線路服務(wù),建立基于換乘網(wǎng)絡(luò)且滿足需求可拆分的公交接駁線網(wǎng)優(yōu)化模型.根據(jù)模型特點(diǎn)設(shè)計(jì)了基于遺傳算法的求解方法.模型和算法綜合考慮需求可拆分條件下的網(wǎng)絡(luò)結(jié)構(gòu)和客流選擇行為等約束條件;在優(yōu)化算法中,以FBNDP的解為基礎(chǔ),融入重復(fù)點(diǎn)的生成和插入策略,實(shí)現(xiàn)FBNDP解和FBNDP-SD解的相互轉(zhuǎn)換,有效解決了FBNDP-SD構(gòu)解困難的問(wèn)題.優(yōu)化結(jié)果表明,在考慮公交需求可拆分的情形下,F(xiàn)BNDP-SD線網(wǎng)能夠?yàn)楣徽军c(diǎn)提供多條接駁線路進(jìn)行選擇,從而有效分流乘客,降低線路成本,優(yōu)化線網(wǎng)結(jié)構(gòu).對(duì)于線網(wǎng)客流強(qiáng)度較高的情況或者具有較大客流量的站點(diǎn),考慮公交需求可拆分更具實(shí)際意義.