基于混合車型的靈活型接駁公交路徑協(xié)同優(yōu)化研究

邵文，賈順平，曹文娟

(北京交通大學交通運輸學院，北京 100044)

目前，我國城市公共交通系統(tǒng)以軌道交通為骨干，常規(guī)公交為主體，由于二者“定點”與“定線”的特性，乘客出行需要一定距離的繞行，無法滿足非高峰時段居民出行需求。相比固定線路公交，靈活型接駁公交作為介于常規(guī)公交與出租車之間的新興公交服務模式，具有更優(yōu)的機動性、便捷性和舒適性，可提高居民出行直達性，是完善城市交通資源優(yōu)化配置的有效方法。該系統(tǒng)多適用于城市邊緣地帶、高科技園區(qū)、新型居民區(qū)等客流密度中等偏低的地區(qū)，是聯(lián)系周邊交通小區(qū)與主線公交的紐帶，其調(diào)度方案和?？空疚恢每筛鶕?jù)乘客需求調(diào)整，能有效滿足低出行密度區(qū)域多樣化、個性化的居民出行需求。

國外關(guān)于靈活型接駁公交系統(tǒng)的研究要早于國內(nèi)，有較為充分的理論成果并得以應用。Cole[1]提出的7種交通運營模式之一的Dial-a-Bus系統(tǒng)作為靈活型接駁公交系統(tǒng)的雛形，旨在解決低密度人口區(qū)域居民出行難的問題。Flussberg[2]提出了根據(jù)乘客出行需求在特定區(qū)域提供靈活型接駁服務的Merrill-Go-Round系統(tǒng)，并進行了實例應用研究。現(xiàn)有的針對靈活型接駁公交線路調(diào)度優(yōu)化的研究多是關(guān)于可變線路式的服務系統(tǒng)(mobility allowance shuttle transit，MAST)，即車輛圍繞一條由若干站點組成的基準線路運行，車輛可在兩固定站點間允許的松弛時間內(nèi)一定程度地偏離基準線路。針對MAST系統(tǒng)的線路設計、車輛調(diào)度等優(yōu)化問題，Malucelli等[3]建立了離線優(yōu)化模型，Quadrifoglio等[4-5]建立了混合整數(shù)規(guī)劃模型，并提出插入式啟發(fā)算法求解[6-7]，但均未充分考慮接駁公交與主線公交時刻表的協(xié)同優(yōu)化。國內(nèi)學者對于該系統(tǒng)的研究起步較晚，但也取得了一些研究成果。熊杰等[8]綜合考慮路徑出行時間和圈點線路約束，以路徑需求潛力最大化為優(yōu)化目標，建立地鐵接駁線路的路徑優(yōu)化模型，并提出基于路段交叉變異的遺傳算法求解模型。潘述亮等[9]兼顧出行者和運營者雙方利益，就接駁系統(tǒng)線路規(guī)劃和車輛協(xié)同問題，建立路徑優(yōu)化和協(xié)調(diào)調(diào)度整數(shù)規(guī)劃模型，并設計了一種基于新型重模型的啟發(fā)式算法進行求解。劉心雨等[10]研究了保障乘客在期望時間及可接受延誤時間范圍內(nèi)到達換乘中心的前提下，基于乘客不同出行目的的接駁公交線路調(diào)度優(yōu)化方案。目前，國內(nèi)外關(guān)于靈活型接駁公交服務系統(tǒng)的研究多側(cè)重于減少系統(tǒng)出行成本，而忽略了公交服務滿意度這一關(guān)鍵因素。將公交服務滿意度納入系統(tǒng)優(yōu)化目標將有助于提高公交服務水平，增強客流吸引力[11]。

本文考慮乘客滿意度這一影響因素，將其轉(zhuǎn)化為接駁公交與主線公交時刻表的協(xié)同優(yōu)化，兼顧混合車型對靈活型公交接駁系統(tǒng)運營成本的影響，針對靈活型接駁公交的路徑優(yōu)化及協(xié)同調(diào)度問題展開研究。以單個換乘站點為研究對象，同一個固定換乘點作為接駁公交的起訖點，依據(jù)乘客預約出行需求和各需求點車輛到達時間動態(tài)優(yōu)化接駁車輛的運行線路和調(diào)度方案，最終生成多條車輛行駛路徑，即在給定預約需求和車隊規(guī)模的前提下，以最大化乘客滿意度和最小化企業(yè)運營成本為優(yōu)化目標，建立基于混合車型的靈活型接駁公交路徑協(xié)同優(yōu)化模型，并使用遺傳算法對該模型進行求解。

1 研究問題描述

本文所研究的靈活型接駁公交可定義為依托于互聯(lián)網(wǎng)平臺，運營方根據(jù)乘客預約的出行申請設計車輛行駛線路，完成招募乘客、預訂座位、在線支付等一系列公交服務[12]。

為研究車輛路徑優(yōu)化問題，現(xiàn)進行詳細描述：在服務區(qū)域內(nèi)有1個固定換乘站點和n個需求點，換乘點內(nèi)有mp輛不同類型容量為Qp的接駁車輛供其調(diào)配，輸出結(jié)果為多條車輛行駛的有向路徑。以車輛把乘客從需求點送達換乘站的過程為例，車輛一次接駁服務可定義為：車輛從換乘站點出發(fā)，基于乘客預約的確定性需求依次對需求響應站點服務后，最終返回原換乘站點，即完成“多對一”條件下的接駁車輛路徑優(yōu)化和調(diào)度方案設計。如圖1所示，圖中有3條接駁線路，線路1采用車型a服務，線路2和線路3均采用車型b服務。

圖1 基于混合車型的接駁車輛行駛路線示意圖Fig.1 Schematic of the flexible shuttle transit routing based on various vehicle types

2 靈活型接駁公交路徑協(xié)同優(yōu)化模型

2.1 模型假設

定義編號0為換乘站，編號1,2,3,…,n為乘客需求點。在建模過程中，進行如下假設：

(1)服務區(qū)域內(nèi)有1個換乘站點和n個需求響應站點，各站點位置已知；

(2)接駁車輛保持一定的速度在各站點間勻速行駛，忽略特殊交通狀況和乘客上下車對車速的影響，不考慮延時和等待；

(3)換乘站點和各需求點間均互相通達，每兩個站點間的行程時間固定且已知；

(4)換乘站所能提供接駁服務的車隊規(guī)模已知；

(5)服務區(qū)域內(nèi)不存在拒絕服務乘客的情況，所有有預約申請的乘客均被服務；

(6)乘客提交預約申請時，明確出行需求，包括需求點位置、出發(fā)時刻、期望和可容忍服務時間窗，只能將換乘點和需求點作為出行起訖點，起訖點不能均是需求點；

(7)接駁公交系統(tǒng)只服務于有預約申請的乘客，所有申請均在車輛出發(fā)前完成，行駛過程中不存在乘客需求變動的情況。

2.2 模型構(gòu)建

模型中的主要參數(shù)和決策變量的含義如表1所示。

表1 模型參數(shù)

2.2.1 目標函數(shù)

靈活型接駁公交屬于城市公共交通的類別，其運營一般需要兼顧乘客和企業(yè)雙方利益，在保證乘客滿意度水平的同時降低企業(yè)運營成本?；诖?，本文將以企業(yè)運營成本最小和乘客滿意度最大兩部分作為目標函數(shù)建立模型。

(1)最小化企業(yè)運營成本

參考已有研究，公交企業(yè)運營成本主要包括車輛損耗成本和車輛油耗成本[13]。車輛損耗成本為每次啟動車輛時所產(chǎn)生的折舊損耗費用，與發(fā)車次數(shù)相關(guān)；車輛油耗成本與車輛類型和行駛里程有關(guān)，不同類型車輛的油耗成本與行駛里程成正比例關(guān)系。

所以公交企業(yè)運營成本可表示為：

(1)

(2)最大化乘客滿意度

(2)

圖2 軟時間窗約束下乘客滿意度函數(shù)圖Fig.2 Passenger satisfaction function with soft time window constraints

(3)

圖3 硬時間窗約束下乘客滿意度函數(shù)圖Fig.3 Passenger satisfaction function with hard time window constraints

因此，乘客滿意度函數(shù)可整理如公式4所示，乘客滿意度最大的目標函數(shù)如公式5所示。

(4)

maxZ2=fsat。

(5)

2.2.2 模型綜合表述

s.t.

(6)

(7)

(8)

(9)

,?k∈D，

(10)

(11)

(12)

(13)

(14)

(15)

式(6)、(7)表示接駁車輛行駛過程中各需求點僅有1條行駛路徑；式(8)表示車上乘客數(shù)不超過p車型的額定載客量；式(9)表示調(diào)度過程中所使用的各車型車輛數(shù)不可超出換乘站總配備車輛數(shù)；式(10)表示車輛從換乘站點出發(fā)，最終返回原換乘站完成接駁服務；式(11)表示一次接駁服務行程中，每輛車不得超過最大允許行駛距離；式(12)表示需求點i乘客滿意度函數(shù)的軟時間窗約束；式(13)表示第k輛車返回換乘站的乘客滿意度函數(shù)的硬時間窗約束；式(14)、(15)表示接駁車輛到達需求點i的時間約束。

3 模型求解

本文研究的基于混合車型的靈活型接駁公交路徑協(xié)同優(yōu)化模型帶有乘客滿意度的時間窗約束，屬于典型的帶有時間窗約束的開放式車輛路徑問題(vehicle routing problem，VRP)。車輛路徑問題的求解方法可分為精確算法和啟發(fā)式算法，精確算法包括分支定界法和列生成法等，啟發(fā)式算法包括蟻群算法、模擬退火算法和遺傳算法等。

蟻群算法是一種基于種群的進化算法，具有很強的發(fā)現(xiàn)較好解的能力和魯棒性，易于與多種啟發(fā)式算法結(jié)合，在解決一些小規(guī)模的旅行商問題(travelling salesman problem，TSP)時表現(xiàn)較好，但隨著問題規(guī)模的增大，難以在可接受的循環(huán)次數(shù)內(nèi)找到最優(yōu)解。模擬退火算法能夠以較大概率求得較優(yōu)解，具有較強的魯棒性、全局收斂性以及隱含并行性，通用性強，易于實現(xiàn)，但是該算法缺乏歷史搜索信息，每次能保留一個解，對整個搜索空間的搜索能力不強。遺傳算法提供了一種求解非線性、多模型、多目標等復雜系統(tǒng)優(yōu)化問題的通用框架，具有較強的全局搜索能力和隱含并行搜索特性，按照一定概率的變遷規(guī)則來指導搜索方向，具有較強的自組織和自適應的能力，是一種實用、高效、魯棒性強的優(yōu)化技術(shù)。因此，本文利用遺傳算法求解該路徑優(yōu)化模型。

3.1 染色體編碼及種群初始化

本文采用自然數(shù)編碼策略求解車輛調(diào)度模型，將染色體編碼成長度為n+k+1的個體，1，2，3，…，n為各需求點的編號，n+1～n+k為k輛接駁公交的編號。由于需求點位置在車輛出發(fā)前已確定，對車輛進行編碼，0代表不使用，1代表使用。個體向量的第1個分量代表第1輛車服務的第1個乘客，接著尋找滿足時間窗和車容量約束的乘客加入到當前路徑中，直至不滿足約束條件時停止，最終得到該車輛的行駛路徑。例如，若確定車輛1、4、7投入使用，基于車輛編碼結(jié)果確定乘客編碼，對于乘客1隨機生成1～3的數(shù)字。若輸出數(shù)字2，表示車輛4對乘客1進行服務。

本文采取隨機排列策略生成初始種群，以保證種群多樣性的最大化，將所有乘客的出行需求隨機排列，形成初始個體向量并設置種群規(guī)模。

3.2 適應度函數(shù)

3.2.1 統(tǒng)一求解方向

該模型的優(yōu)化目標包括最小化企業(yè)運營成本和最大化乘客滿意度兩部分，屬于是多目標問題優(yōu)化，由于目標函數(shù)求解方向不同，需要統(tǒng)一求解方向，將乘客滿意度極大值轉(zhuǎn)換為不滿意度極小值進行求解。

minZ3=min(1-fsat)。

(16)

3.2.2 歸一化處理

因企業(yè)運營成本和乘客滿意度量綱不同，且乘客滿意度取值范圍為0～1，需對運營成本進行歸一化處理，處理結(jié)果為：

G*=Gm/Gmax，

(17)

H*=Hm/Hmax，

(18)

其中，G*和H*分別表示未歸一化后的車輛損耗成本和油耗成本，Gm和Hm分別表示個體cm中實際的損耗成本和油耗成本，Gmax和Hmax分別表示當前種群個體中的損耗成本和油耗成本的最大值。

3.2.3 多目標函數(shù)處理

為將多目標優(yōu)化模型轉(zhuǎn)變?yōu)閱文繕藘?yōu)化問題，可將目標函數(shù)變?yōu)榍笃髽I(yè)運營成本和平均乘客不滿意度之和的最小值。本文依據(jù)運營成本和乘客滿意度對系統(tǒng)的影響程度賦予不同的權(quán)重值，并且取兩者之和的倒數(shù)，構(gòu)造適應度函數(shù)如式(19)所示。個體適應度函數(shù)值越大，表明其適應度越強。

g(cm)=1/[w1G*+w2H*+w3(1-fsat)]。

(20)

3.2.4 遺傳操作

基因選擇采用輪盤賭的方法，將各染色體適應度與所有染色體適應度和的比值作為該染色體的被選概率進行選擇。假設各染色體的被選概率為Pi，Si為染色體i隨機產(chǎn)生一個數(shù)，取值在0～1內(nèi)。若Si

交叉操作采用多點交叉的方式，先隨機確定多個交叉位置，然后交換相應的子串，從而產(chǎn)生新的個體。

變異操作采用單點變異法，即遍歷種群中每個個體的編碼位置，每次產(chǎn)生一個隨機數(shù)τ。若τ小于變異概率，則對該位置進行變異操作；反之，則重新選擇變異位置。

4 案例分析

為驗證上述模型的有效性和可行性，構(gòu)造一個小型網(wǎng)絡進行案例分析，該模型所需的已知條件如表2～4所示。表2中給出了一些常變量的輸入?yún)?shù)，車輛到達換乘站的時間窗約束范圍為主線公交出發(fā)前2 min。表3 列出了服務區(qū)域內(nèi)各需求站點的乘客預約信息。以需求點1的乘客預約信息為例進行解釋，在需求點1共有2名乘客提出預約申請，他們的期望服務時間窗分別為9:03—9:05和9:23—9:25，可容忍服務時間窗分別為9:00—9:10和9:18—9:30。表4列出了服務區(qū)域內(nèi)換乘站與需求點以及各需求點之間的出行時間矩陣，其中編號1～15為需求點，編號0為換乘站，各站點間的平均出行時間為在實際路網(wǎng)中的最短距離與車輛平均行駛速度的比值。

表2 案例中的常變量

表3 各需求點的預約信息統(tǒng)計表

表4 案例網(wǎng)絡的旅行時間矩陣

運用建立的路徑優(yōu)化模型和設計的遺傳算法，通過PYTHON軟件編程對該案例進行求解，同時對比單純使用8座車型和15座車型的輸出結(jié)果進行分析，如表5所示。

表5 接駁公交行駛路線表

表5的結(jié)果表明，算例1使用了4輛車，包括3輛8座車和1輛15座車，算例2使用了5輛8座車，算例3使用了4輛15座車，其中算例1的最優(yōu)適應度值最高為1.086 7。通過對比可發(fā)現(xiàn)，綜合考慮企業(yè)運營成本最低和平均乘客滿意度最高，同樣的出行需求下，混合車型的路徑規(guī)劃結(jié)果更優(yōu)，其供需匹配更為合理。采用混合車型路徑優(yōu)化方案與僅使用單一車型相比，其優(yōu)勢在于：在不超出車容量和線路長度的前提下，乘客出行需求少且距離換乘站遠的需求點宜使用運營成本低的小型接駁車輛，乘客出行需求多且位置分布較集中的需求點宜使用可服務更多乘客的大容量接駁車輛，從而達到系統(tǒng)最優(yōu)的效果。

4 結(jié)論

本文探討了靈活型接駁公交的路徑優(yōu)化問題，重點考慮混合車型聯(lián)合調(diào)度對接駁車輛路徑優(yōu)化的影響，以企業(yè)運營成本最小和乘客滿意度最大為優(yōu)化目標，兼顧路徑規(guī)劃和車輛協(xié)調(diào)調(diào)度，建立了基于混合車型的靈活型接駁公交路徑協(xié)同優(yōu)化模型，同時設計了遺傳算法求解模型。算例結(jié)果表明，該模型適用于采用多車型的靈活型接駁公交系統(tǒng)，能在合理時間內(nèi)求解出車輛調(diào)度方案和最優(yōu)行駛路徑，具有一定的實際運用價值。本文建立的模型適用于小規(guī)模的主線公交換乘點的接駁公交線路設計及調(diào)度方案優(yōu)化，作為一類典型的NP-hard問題，當乘客需求數(shù)較大時，算法的運算效率有待提高，后續(xù)需要進一步設計算法，提高實時在線的計算速度。