路網(wǎng)不發(fā)達地區(qū)混合式靈活型公交路徑優(yōu)化研究

孫超

(蘭州交通大學 交通運輸學院，甘肅 蘭州 730070)

發(fā)展公共交通是解決人們出行問題的重要手段。現(xiàn)階段，在路網(wǎng)發(fā)達的城市地區(qū)，公交線網(wǎng)密度高，大容量的常規(guī)公交能為人們出行提供便捷的服務(wù)。但是，在路網(wǎng)不發(fā)達的地區(qū)，出行距離往往更長，客流更加分散，大體積的常規(guī)公交可達性不高，無法滿足出行需求。自Daganzo[1]首次提出“靈活公交”以來，國外學者對其做了系統(tǒng)的研究，其作為一種新興的公交運行模式，能夠有效解決“最后一公里”的問題。Malucelli[2]對靈活公交靜態(tài)調(diào)度問題進行研究，并提出以系統(tǒng)總效益最大為目標的整數(shù)規(guī)劃模型。Myungseob[3-4]證明在需求密度低或道路無法容納相對較大的固定路線公共汽車的地區(qū)，在門口為乘客服務(wù)的靈活線公共汽車系統(tǒng)可能比固定路線公共汽車系統(tǒng)更可取，同時對于出行不便的固定線路的需求，靈活公交也是優(yōu)選。通過有效地整合傳統(tǒng)和靈活的服務(wù)，使服務(wù)類型與各地區(qū)相匹配，可以大大降低服務(wù)的總成本。Velaga[5]指出目前靈活公交運營規(guī)模小，與其他交通方式銜接不足。盧小林[6]針對靈活型接駁公交，提出一種“固定+靈活”的混合接駁模式，采用基于重力模型的啟發(fā)式算法進行求解，證明這種混合系統(tǒng)能有效減少車輛行駛距離和運行時間。邱豐等[7]針對可變線路式公交建立了兩階段車輛調(diào)度模型，采用模擬退火算法求解驗證了模型的有效性。鄭漢[8]等對居民出行特征用K均值方法進行分析，將乘客出行問題簡化為物流配送問題，以車輛數(shù)最少和運行距離最短為目標建立模型，求解驗證了模型的有效性。胡郁蔥[9]對不同需求的乘客進行聚類，得到乘客上下車站點，建立多車型、多起點的定制公交線路規(guī)劃模型，采用遺傳算求解。Guo[10]針對多車定制公交路線規(guī)劃問題建立了混合整數(shù)規(guī)劃模型，采用遺傳算法求解，驗證了模型的有效性。靳文舟[11]采用K均值聚類算法對需求響應(yīng)公交臨時?？空具M行規(guī)劃，提出精英選擇遺傳算法進行最優(yōu)路徑求解。

現(xiàn)有研究多對城市或城郊等路網(wǎng)相對發(fā)達地區(qū)的靈活公交進行優(yōu)化，采用的優(yōu)化模式為多車型單一線路型或是單車型混合線路。考慮到路網(wǎng)不發(fā)達使得大型車可達性低的情況，本文提出一種混合式靈活型公交服務(wù)。在已知路網(wǎng)和乘客需求的條件下，針對不同位置的乘客需求，采用多車型多線路的混合運行模式，建立混合式需求響應(yīng)公交路徑規(guī)劃模型，利用改進的粒子群-遺傳混合算法分階段進行求解，通過優(yōu)化調(diào)整，實現(xiàn)大小車協(xié)同運行，為乘客提供更加便捷的服務(wù)。

1 問題描述及建模

1.1 問題描述

混合式靈活公交系統(tǒng)結(jié)合大型車運量大與小型車可達性高的特點，為乘客提供一種個性化的出行需求(見圖1)。大車運行模式為區(qū)域線路公交服務(wù)[12]，即在固定的首末站間為乘客提供定制公交服務(wù)；小車運行模式為需求響應(yīng)式接駁服務(wù)[13]，小車可將乘客需求接駁到大車站點，也可按需求響應(yīng)模式直接將乘客送往目的地。已知目的地、路網(wǎng)和需求點，每個需求點有若干乘客，首先對乘客需求進行分配，利用聚類算法規(guī)劃大型車?？空军c，在原有需求站點中剔除停靠站附近的需求點，這部分乘客自行前往大車?？空镜却宪嚕粚τ陔x主路較遠的離散需求點，小型車將其收集接駁到大車?？空净蛑苯咏铀偷侥繕苏军c。

圖1 混合式靈活公交服務(wù)系統(tǒng)模式

1.2 模型建立

1.2.1 模型假設(shè)

為使問題便于求解且符合實際需求，提出如下假設(shè)：① 每輛車都從固定車場出發(fā)，前往固定的目的地；②同一乘客需求點每輛車僅服務(wù)一次；③公交車總數(shù)、車輛行駛速度、載客量已知；④每個需求點最多只換乘一次。

1.2.2 模型表述

混合式靈活公交系統(tǒng)模型以總線路行程時間和乘客的等待時間最小為目標，以載客人數(shù)、線路最大長度等為約束，模型參數(shù)見表1。

表1 模型參數(shù)

(1)目標函數(shù)。

大型車的線路行程時間見式(1)；小型車的行程時間見式(2)；乘客的等待時間包括乘客在站點的等待時間和換乘時間，見式(3)。綜上，優(yōu)化目標函數(shù)為三部分之和，見式(4)。

(1)

(2)

(3)

Z=Z1+Z2+Z3

(4)

(2)約束條件。

式(5)表示對于每一個需求點，至少有1輛車服務(wù)；式(6)表示對于每個需求點，最多有C輛車服務(wù)；式(7)表示任意一個乘客需求r最多接駁一個大車停靠站點；式(8)、式(9)表示避免在車輛路徑中出現(xiàn)回路；式(10)表示小車線路應(yīng)滿足最大長度；式(11)表示任何一個需求只能被一輛車服務(wù)；式(12)為車輛載客量約束。

(6)

(7)

Uik-Ujk+|H|·yijk≤|H|-1,?i,j∈H∪H0;k∈K

(8)

Umk-Unk+|H|·Ymnk≤|H|-1,?m,n∈H0;k∈K0

(9)

(10)

(11)

(12)

2 模型求解

2.1 停靠站點規(guī)劃

現(xiàn)有?？空镜倪x擇通常采用K均值算法實現(xiàn)，但該算法在規(guī)劃停靠站點時，需要已知?？空镜臄?shù)量，而需求響應(yīng)公交?？空镜奈恢眠x擇往往隨著需求點的變化而變化，即?？空镜臄?shù)量是未知的。為了解決這個問題，采用一種基于GSA算法的K均值聚類算法[14]規(guī)劃停靠站位置，該算法可根據(jù)出行需求站點數(shù)求出最優(yōu)的?？空军c數(shù)。本文對原有算法進行改進，即在原算法的基礎(chǔ)上加入聚類中心修正[15]步驟，將生成的聚類中心修正到與其最近的道路上，得到臨時?？空军c。修正算法具體步驟如下：

Step1:利用GSA算法改進的K均值聚類算法求出初始的聚類中心集合；

Step2:令n=1，輸入已生成的聚類中心集合U，聚類中心數(shù)量r，備選站點集合S；

當聚類中心位于路網(wǎng)內(nèi)部時，選擇附近路網(wǎng)節(jié)點為備選站點，如圖 2a所示，若O為聚類中心，則A、B、C、D為備選站點；如圖 2b所示，則A、B為備選站點。

(a)

Step3:當nr，轉(zhuǎn)至Step7；

Step4:判斷S中是否存在站點與抽取的聚類中心坐標重合，重合則n=n+1，返回Step3，否則篩選u所在路網(wǎng)附近可能構(gòu)成聚類中心的備選站點S，轉(zhuǎn)Step5；

Step5:抽取S中站點si判斷是否與已修正的站點坐標重合，若重合，繼續(xù)抽取，否則替換u，計算當前備選站介入下的粒子適應(yīng)度值并排序；

Step6:選出適應(yīng)度值最小的粒子，對其用K均值算法求聚類；

Step7:n=n+1，返回Step2；

Step8:算法結(jié)束，得到修正的臨時?？空炯稀?/p>

2.2 混合式需求響應(yīng)公交路徑規(guī)劃

本文所建立的模型為混合整數(shù)規(guī)劃模型，是一類NP-hard問題[16]，嘗試采用啟發(fā)式算法進行求解。對于混合式需求響應(yīng)公交路徑規(guī)劃模型，分兩個階段對大車路徑和小車路徑分別求解。

2.2.1 基本步驟

第一階段大車路徑的求解問題可看作多車場跨區(qū)域聯(lián)合配送的半開放式車輛路徑問題(half-open vehicle routing problem，HOVRP)[17]，采用改進的粒子群-遺傳混合算法求解，得到區(qū)域線路公交服務(wù)模式的大車運行線路，以及各站點的到站時間。具體步驟如圖3所示。

第二階段的小車求解問題采用基于引力模型的PSO-GA混合算法求解，具體步驟如圖4所示。

圖3 PSO-GA混合算法步驟

圖4 基于引力模型的PSO-GA混合算法步驟

2.2.2 關(guān)鍵環(huán)節(jié)

(1)編碼和解碼。①編碼方式為整數(shù)編碼，一階段個體長度為：Nr+Nmax-1(Nr為需求點數(shù)量，Nmax為最大車輛數(shù))；二階段個體為整合了滿足所有需求時，每輛車初始路徑以及起終點而形成的個體，根據(jù)初始路徑生成二階段換乘方案，換乘為1，否則為0，初始路徑采用引力模型[18]生成。②解碼時以大于需求點數(shù)位置為節(jié)點，將其替換為0，假設(shè)需求點有5個，最大車輛數(shù)為2，編碼方案為0→1→3→6→2→4→5，解碼為0→1→3→0→2→4→5，表示：

車輛1路徑為：出發(fā)點→1→3→目的地；車輛2路徑為：出發(fā)點2→4→5→目的地。

(2)引力模型生成初始路徑。任意兩點之間的吸引力用式(13)計算，式中，Di為i需求點的乘客人數(shù)；tij為需求點i到j(luò)的旅行時間。

(13)

引力模型求解車輛初始路徑的具體步驟如下：

Step1:計算各個需求點以及與始終點之間的引力模型；

Step2:從終點出發(fā),選擇與該點吸引力最大的需求點，以該需求點為新起點，繼續(xù)選擇，計算當前已在車的需求；

Step3:如果乘客需求量超過其載客量，轉(zhuǎn)入Step4，否則，轉(zhuǎn)Step5；

Step4:選擇插入換乘點，令當前在車需求為0；

Step5:計算當前選擇路徑長度，若長度超過小車最大長度限制，則已得到一條車輛路徑，轉(zhuǎn)step6;

Step6:若所有需求點均已滿足，結(jié)束，否則返回Step2；

Step7:結(jié)束。

(3)二階段換乘點插入：計算到達當前換乘位置的時刻，遍歷所有臨時?？空军c，選擇等待時間最少的?？空静迦搿?/p>

(4)適應(yīng)度均為目標函數(shù)值，交叉采用兩點交叉，變異采用單點變異。

(5)局部搜索操作：采用大鄰域搜索策略(LNS)[20]的destroy和repair操作，如對一個個體0→1→3→6→2→4→5，利用destroy操作隨機破壞，生成0→1→6→2→5，然后利用repair操作進行修復(fù)，隨機插入破壞的點，選擇生成的最好的個體，如0→1→6→2→3→4→5。

3 案例分析

某區(qū)域內(nèi)已預(yù)約需求點和路網(wǎng)情況如圖5所示,已知需求點數(shù)量為93，乘客人數(shù)為148，車場內(nèi)車輛數(shù)為大車4輛，小車10輛，大車平均速度為60 km/h,小車平均速度為80 km/h，大車載客量為35人，小車載客量為13人。

圖5 路網(wǎng)和需求點(單位：km)

3.1 臨時?？空疽?guī)劃

根據(jù)原始坐標信息，首先對乘客需求進行分配，采用GSA算法改進的K均值聚類算法對乘客需求聚類，生成初始聚類中心，利用修正方法對初始聚類中心修正，生成大車臨時?？空?，將靠近大車臨時?？空?d≤1000 m)的需求點在路網(wǎng)中剔除，整合后的離散需求點共有39個，公交車臨時?？空?1個，如圖6所示，位置坐標和乘客數(shù)量如表2所示。

圖6 聚類生成臨時?？空?單位：km)

表2 臨時?？空咀鴺撕腿藬?shù)

續(xù)表

3.2 車輛路徑規(guī)劃

本文所提出算法為啟發(fā)式算法，結(jié)果不唯一，在Matlab2018a上編程計算20次取最優(yōu)結(jié)果。圖7a、圖7b分別為大小車路徑計算收斂圖。計算結(jié)果如表3所示，當混合靈活式公交系統(tǒng)采用35座大車和13座小車時，投入服務(wù)的大車和小車共7輛，每輛小車均與大車進行了接駁?？傂谐虝r間為463.33 min，乘客等待時間為86.18 min，車輛行駛路徑分別如圖8a、圖8b所示。將計算結(jié)果與單一模式下的靈活型公交計算結(jié)果進行比較，如表4所示，采用混合式靈活型公交運行模式的總行程時間比采用單一模式的總行程時間減少了25.03%，乘客等待時間減少了7.39%，車輛數(shù)減少5輛。

(a)

表3 車輛路徑

表4 不同模式對比

(a)

為進一步驗證模型與算法的有效性，分別采用9座、11座、15座、17座不同載客量的小車，車輛平均速度分別為85 km/h、80 km/h、70 km/h、70 km/h，對混合模式和單一模式分別求解。得出結(jié)果如表6所示，采用9座、11座車時車輛的總行程時間和乘客等待時間混合模式比單一模式分別增加7.57%、6.68%，21.01%、1.30%，車輛數(shù)兩種車型分別減少5輛、6輛；采用15座車時，混合模式比單一模式的行程時間減少6.33%，乘客等待時間減少2.97%，車輛數(shù)減少3輛；采用17座車時總行程時間混合模式比單一模式減少4.00%，乘客等待時間減少11.58%，車輛數(shù)減少3輛?？梢钥闯?，不管采用那種車型混合模式下服務(wù)的車輛數(shù)都明顯少于單一模式，采用15座車、17座車時，混合模式在總行程時間、乘客等待時間、車輛數(shù)方面都要優(yōu)于單一模式；在當前需求下，采用混合模式13座車為最優(yōu)方案。

4 結(jié) 語

針對路網(wǎng)不發(fā)達地區(qū)的混合式靈活公交服務(wù)問題，分階段建立了靈活公交路徑優(yōu)化模型，本文所建立的路徑優(yōu)化模型將混合運行系統(tǒng)分解，每部分建立模型；最終目標為總行程時間、乘客等待時間最少。對模型的求解首先是對乘客需求進行分配，利用基于GSA算法的K均值聚類算法并通過聚類中心修正步驟，在路網(wǎng)中規(guī)劃大車臨時停靠站點，然后采用基于引力模型的PSO-GA混合算法分階段求解最優(yōu)路徑。算例結(jié)果表明，本文所提出的混合式靈活公交系統(tǒng)在路網(wǎng)受限的條件下，能夠有效減少總行程時間和乘客的等待時間，求解算法也能在短時間求出有效、合理的車輛路徑和服務(wù)車輛數(shù)。

表6 不同車型運營里程