多種開行模式下定制公交線網(wǎng)規(guī)劃方法

趙茂林，陳明明

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

0 引言

定制公交作為多樣化公共交通的重要組成部分，主要是通過集合個體出行需求，為出行起訖點、出行時間、服務水平相似的人群提供量身定制的公共交通服務方式[1]. 現(xiàn)有運營的定制公交多為早晚高峰通勤線路，線網(wǎng)模式單一，很難滿足普通乘客的出行需求. 合理規(guī)劃定制公交線網(wǎng)，有利于定制公交融入到城市公共交通系統(tǒng)中，對多元化公共交通進行有效補充，進而提高公交的吸引力，促進私人交通方式向公共交通方式轉(zhuǎn)移.

目前國外對定制公交的研究主要集中于和定制公交相類似的電話叫車、靈活交通運輸服務等方式，在定制公交線網(wǎng)規(guī)劃方面研究較少. Perugia A等[2]建立了以運行成本及旅客總額外時間最小的定制公交線網(wǎng)規(guī)劃模型，采用禁忌搜索算法求解得到站點位置和行車路徑. Corinne Mulley等[3]提出了靈活交通運輸服務(FTS)在交通需求較低的地區(qū)越來越多的被用作公共交通系統(tǒng)的一部分，靈活的線路選擇和提高服務水平將鼓勵更多的人選擇這種服務.

自2013年9月北京開通第1條定制公交線路后，國內(nèi)學者逐漸將研究重點放到了定制公交線網(wǎng)規(guī)劃上來，且研究多集中于多出發(fā)地到單目的地[4]、多出發(fā)地到多目的地等[5]單一開行模式的線網(wǎng)規(guī)劃問題. 此外，何民等[6]針對響應式定制公交線路設計問題，考慮可靠性和舒適性建立了模型，采用LINGO軟件求解了小規(guī)模算例，生成了多出發(fā)地到單目的地的線路. 胡郁蔥等[7]參考車輛徑路問題，構(gòu)建了多起終點、多車型和乘客混載的定制公交線路規(guī)劃模型，利用遺傳算法改進編碼規(guī)則求解. 陶浪等[8]建立了最小化乘客出行時間、最小化車輛油耗的定制公交路線多目標優(yōu)化模型，設計了改進的NSGA-II算法快速得到優(yōu)化路徑.

綜上，國內(nèi)外研究規(guī)劃的定制公交線網(wǎng)模式大多比較單一，忽略了乘客出行需求的差異性，容易造成因預約人數(shù)不足而取消已規(guī)劃線路的現(xiàn)象，企業(yè)也較難盈利. 本文擬考慮乘客出行需求的差異性，設計以線網(wǎng)覆蓋率、運營利潤和乘客總繞行距離最優(yōu)的定制公交線網(wǎng)規(guī)劃模型及算法，規(guī)劃多種開行模式下的定制公交線網(wǎng).

1 問題描述

定制公交線網(wǎng)開行模式根據(jù)乘客出行需求情況一般可分為4類：單出發(fā)地到單目的地(以下稱單-單)、多出發(fā)地到單目的地(多-單)、單出發(fā)地到多目的地(單-多)和多出發(fā)地到多目的地(多-多). 目前學者大多針對單一開行模式的需求情況進行研究. 然而，現(xiàn)實中乘客出行需求時空分布差異較大，每個合乘站點可能聚集了不同目的地以及不同出發(fā)時刻的乘客出行需求，即出行需求的差異性. 以圖1規(guī)劃的定制公交線網(wǎng)為例，站點1～4為上車站點，每個站點有不同的乘客期望出發(fā)時刻，站點5～7為下車站點. 規(guī)劃出的定制公交線網(wǎng)根據(jù)不同的乘客出行需求特征包含了多種開行模式的線路.

圖1 多種開行模式下的定制公交線網(wǎng)示意圖

具體問題描述如下：根據(jù)已知的若干乘客出行需求，每個出行需求包含了上車站點、下車站點、出發(fā)時刻、到達時刻、需求聚集人數(shù). 每輛定制公交根據(jù)不同的乘客出行需求，從乘客上車站點出發(fā)，經(jīng)過若干合乘站點，將乘客送至下車站點，滿足上座率、站點數(shù)量限制、出發(fā)時間窗等約束. 以線網(wǎng)覆蓋率、運營企業(yè)利潤最大和乘客總繞行距離最小為優(yōu)化目標，研究多種開行模式下的定制公交線網(wǎng)規(guī)劃問題.

2 模型構(gòu)建

2.1 參數(shù)設置

2.2 模型假設

為了簡化問題，做出如下假設：

1)每種類型可供選擇的公交車輛數(shù)量充足；

2)單條線路中不存在既是上車站點又是下車站點的站點；

3)定制公交票價取決于乘客出行距離長短；

4)道路通行狀況良好，車輛勻速行駛，不考慮交通延誤和站點停靠時間.

2.3 目標函數(shù)

1)運營企業(yè)利潤最大，定制公交不同于常規(guī)公交，沒有政府的財政補貼，自負盈虧. 為了定制公交的可持續(xù)發(fā)展，規(guī)劃線網(wǎng)應盡量使運營企業(yè)利潤達到最大.

(1)

式中，第1部分為運營收入；第2部分為運營成本.

2)線網(wǎng)覆蓋率最大，由于乘客出行需求的離散性，定制公交線網(wǎng)不可能服務所有的乘客出行需求，但應盡可能多的服務乘客.

(2)

3) 乘客總繞行距離最小，為了提高乘客的覆蓋范圍、增加企業(yè)的收入，在上座率不足時，車輛勢必會繞行搭載乘客. 為了提高線路的便捷性，同時也為了控制運營成本，線網(wǎng)規(guī)劃應盡可能使乘客總繞行距離最小.

(3)

2.4 約束條件

1)線路站點數(shù)量限制，線路站點數(shù)量過多會喪失定制公交的優(yōu)越性，應對其進行限制,見式(4)：

(4)

2)時間窗約束，車輛到達乘客出發(fā)站點的時刻要在乘客出發(fā)時間窗內(nèi)；到達乘客目的地的時刻不晚于乘客期望到達時刻，否則定制公交將不響應乘客的出行需求. 乘客可接受的出發(fā)時間窗閾值為θ.

(5)

(6)

3) 上座率及車輛容量限制，考慮企業(yè)的運營成本，線路開通要滿足最小上座率約束，同時要保證上車乘客總數(shù)不超過車輛容量，未上車的乘客由下一輛定制公交服務.

(7)

4) 上下車站點要求，定制公交服務某一個需求，需確保先后經(jīng)過上車站點和下車站點.

(8)

5)變量取值約束，對任意車型為g的第k輛車，當服務的需求確定后，所經(jīng)過的站點也隨之確定.

(9)

式中，表示服務的出行需求a與站點i的變量取值關系.

(10)

3 算法設計

定制公交線網(wǎng)規(guī)劃問題是典型的NP-hard問題，其實質(zhì)是求解乘客出行需求的最優(yōu)組合. 相較于其他智能算法，蟻群算法在路徑尋優(yōu)上有明顯的優(yōu)勢，更加符合本文模型的求解特征，本文采用蟻群算法求解.

3.1 模型解的結(jié)構(gòu)分析

3.2 算法步驟

算法的基本思想是讓螞蟻搜索出所有能合乘的出行需求，根據(jù)合乘需求的OD信息規(guī)劃相應的線路，經(jīng)過多次迭代得到最優(yōu)解. 具體步驟如下：

步驟1讀取算法所需基本信息，初始化算法參數(shù). 輸入需求集合Needs、合乘站點集合U和站點距離矩陣D，車型矩陣B. 總體信息素濃度allpheromone=0，迭代次數(shù)為M，蟻群總數(shù)G，當前迭代次數(shù)iter=1.

步驟2當前蟻群序號ag=1.

步驟3當前蟻群ag中的螞蟻數(shù)量as=1.

步驟4從需求集合Needs中取出第1個當前需求need，用need的上車點s和下車點e構(gòu)造當前路徑Presentpath=[s,e]. 并將站點s從U中刪除.

步驟5根據(jù)站點間信息素濃度將U中的站點重新排序,從站點s開始，從allpheromone中尋找信息素濃度最高的下一個站點，以此類推，遍歷其中的每1個站點.

步驟6從U中取出下一個當前站點Presentstation.

步驟7判斷Presentstation是否能滿足當前路徑的時間窗約束和站點數(shù)量約束，若滿足，則繼續(xù)執(zhí)行，否則，跳轉(zhuǎn)到步驟7.

步驟8在Needs中，找到以當前站點Presentstation為起點或終點的相關聯(lián)的需求，判斷這些需求能否與當前需求need合乘. 若能合乘，則將能合乘需求的上下車站點加入Presentpath中，否則，跳轉(zhuǎn)到步驟6.

步驟9遍歷完所有站點后，將符合要求的合乘需求存儲到Tempfinishneeds中，然后為其分配車輛，并判斷是否滿足最小上座率約束. 若不滿足，則將當前需求need從Needs中刪除. 若滿足，則將搜索結(jié)果存儲到Finalresult中，同時從Needs中刪除Tempfinishneeds中的需求.

步驟10判斷Needs是否為空. 若Needs不為空，則蟻群ag中的螞蟻數(shù)量as=as+1，跳轉(zhuǎn)到Step 4. 若Needs為空，則蟻群搜索結(jié)束.

步驟11根據(jù)Finalresult中的結(jié)果，計算當前方案的總利潤、覆蓋率、總繞行距離. 根據(jù)文獻[5]中的信息素更新策略更新allpheromone，歸一化處理各目標函數(shù).

步驟12ag=ag+1,若ag≤G，返回步驟3. 否則，此次迭代結(jié)束，iter=iter+1.

步驟13若iter≤M，返回步驟2. 否則，算法結(jié)束，輸出最優(yōu)解.

4 算例分析

圖2 站點位置分布圖

以蘭州公交集團的出行需求數(shù)據(jù)為基礎，選取蘭州市安寧區(qū)、七里河區(qū)、城關區(qū)聚集的64個乘客出行需求，共914位乘客為研究對象. 乘客分別在21個合乘站點上下車，合乘站點的具體位置如圖2所示. 站點間的距離利用百度地圖獲取，部分距離矩陣如表1所示. 部分需求矩陣如表2所示. 采用的車型容量分別為20、30、45座，共3種車型. 根據(jù)成本核算及實際運營經(jīng)驗,各車型的單位距離成本分別為7.4、8.6、10.2(元/km). 線路最大站點數(shù)量參考文獻[9]中乘客對站點數(shù)量接受意愿的調(diào)查結(jié)果，Nmax=6，最低上座率rmin=0.75(公交集團要求的最低上座率)，出發(fā)時間窗閾值取15 min ，車輛運行速度v=25 km/h，票價函數(shù)(參考文獻[9]中乘客出行意愿特征分析結(jié)果及蘭州市實際情況)如式(11)所示.

(11)

表1 合乘站點間部分距離矩陣 m

表2 部分出行需求矩陣

結(jié)合專家經(jīng)驗法及路網(wǎng)實際調(diào)查數(shù)據(jù)情況，蟻群算法的相關參數(shù)設置為：蟻群總數(shù)G=10，迭代次數(shù)M=200；揮發(fā)系數(shù)rho=0.1；信息素增量Q=0.1. 采用Matlab編程，規(guī)劃結(jié)果如表3～6所示.

表3 單—單模式線路

表4 單—多模式線路

表5 多—單模式線路

表6 多—多模式線路

從表3～6可看出，此次規(guī)劃的線網(wǎng)共有20條線路，4種開行模式均有線路運行，其中單-單模式線路有6條，占比30%，該模式線路聚集性高，多為通勤線路，企業(yè)在實際運營時，后期可根據(jù)實際情況，將其作為定制公交固定線路運行. 線網(wǎng)總體覆蓋率為72.54%，平均上座率為0.93,總利潤為1 382.78元，線網(wǎng)總繞行距離為600.86 km，乘客平均繞行距離為0.92 km. 從時間分布上來看，規(guī)劃的線網(wǎng)既有早晚高峰線路，也有平峰線路運行. 規(guī)劃的每條線路都根據(jù)乘客的出行需求設置了時刻表，不會存在因線路預約人數(shù)不足造成規(guī)劃線路取消的現(xiàn)象. 從上述結(jié)果可看出，本次規(guī)劃的定制公交線網(wǎng)開行模式豐富多樣，較好地滿足了差異化的乘客出行需求，體現(xiàn)了定制公交為乘客量身定制的特點.

4.1 車型選擇

車型方面，有12條線路采用了車型1，10條線路采用了車型2，采用車型3的線路只有1條. 這是由于大部分站點積聚的乘客較少，很難滿足大車型的上座率要求，而小車型成本較低，更加經(jīng)濟適用. 從線網(wǎng)規(guī)劃結(jié)果來看，運營公司在配置車輛時，應以小車型為主，盡可能配置更多車型，使線路車型的選擇更加靈活，增強線網(wǎng)對出行需求差異分布的適應能力. 此外，規(guī)劃的定制公交線網(wǎng)中，線路1、線路12和線路19根據(jù)乘客實際聚集情況均采用了2種車型服務乘客，線路6、線路8、線路20服務的車輛數(shù)超過了1輛，更好地滿足了差異化的乘客出行需求.

4.2 時間窗約束靈敏度分析

影響線網(wǎng)規(guī)劃結(jié)果的主要約束條件為線路最大站點數(shù)、最小上座率和時間窗. 考慮乘客體驗和企業(yè)運營成本，線路最大站點數(shù)和最小上座率變化不宜過大，本文不作深入研究. 在Nmax=6和rmin=0.75的基礎上，探討不同出發(fā)時間窗閾值對線網(wǎng)覆蓋率和企業(yè)總利潤的影響，結(jié)果如圖3所示.

圖3 出發(fā)時間窗閾值與總利潤及覆蓋率關系

從圖3可看出，總利潤及線網(wǎng)覆蓋率隨著閾值的增加，總體呈現(xiàn)上升趨勢. 總利潤在閾值為35 min時達到最大，此時規(guī)劃的線網(wǎng)是發(fā)掘聚集性最高的需求，最大程度降低成本. 覆蓋率和總利潤在閾值分別達到20、35 min后均未明顯上升，而是小范圍波動. 這是因為除了出發(fā)時間窗約束，還有最晚到達時刻約束，達到一定閾值后，并不能繼續(xù)增加達到合乘要求的線路數(shù)量. 時間窗閾值越大，意味著線路偏離乘客期望出發(fā)時刻的程度越大，乘客越可能取消出行計劃. 運營企業(yè)應綜合考慮乘客利益和實際情況，選擇合適的出發(fā)時間窗.

5 結(jié)論

1)針對現(xiàn)有定制公交線網(wǎng)模式單一、規(guī)劃線路容易因預約人數(shù)不足而取消等問題，提出考慮乘客出行需求的差異性，規(guī)劃多種開行模式下的定制公交線網(wǎng).

2)建模時將乘客總繞行距離因素納入目標函數(shù)，綜合考慮了企業(yè)和乘客2方面的利益，此外，模型約束條件考慮了乘客出行時間窗，更加適用于實際情況.

3)通過算例的驗證，本文設計的模型及算法規(guī)劃出的定制公交線網(wǎng)可包括單-單、多-多等在內(nèi)的4種開行模式，且同一線路可采用不同車型服務乘客，更加靈活高效，有助于提高線網(wǎng)覆蓋率，節(jié)約成本.

4)線網(wǎng)規(guī)劃時未考慮同一站點同時有上下車乘客的情況，忽略了乘客上下車時間，未考慮與常規(guī)公交的銜接問題等，今后還應深入研究使規(guī)劃線網(wǎng)更符合實際.