孫倩，胡大偉*，錢一之，江捷，高天洋，姜瑞森

(1.長安大學(xué)，運輸工程學(xué)院，西安 710064；2.新澤西理工學(xué)院，土木與環(huán)境工程系，紐瓦克 NJ07102，美國；3.深圳市城市交通規(guī)劃設(shè)計研究中心股份有限公司，城市交通規(guī)劃研究院，廣東深圳 518063）

0 引言

需求響應(yīng)型接駁公交(Demand-responsive Feeder Transit,DRFT)是“互聯(lián)網(wǎng)+交通”背景下，積極響應(yīng)“提升城市公交服務(wù)品質(zhì)，完善多樣化公交服務(wù)網(wǎng)絡(luò)”發(fā)展主題的典型代表。其線路優(yōu)化問題受到廣泛關(guān)注，Montenegro 等[1]以乘客滿意度最大為目標(biāo)建立DRFT線路優(yōu)化模型，并采用一種大鄰域搜索算法求解。安久煜等[2]以車輛行駛時間最小化為目標(biāo)，根據(jù)預(yù)約需求規(guī)劃DRFT 線路。Costa等[3]研究了動態(tài)DRFT(D-DRFT)線路優(yōu)化問題，以乘客出行時間最小化為目標(biāo)搜索最優(yōu)車輛分配。王正武等[4]以系統(tǒng)總成本最小化為目標(biāo)，研究了考慮多車場、多車型的D-DRFT 線路優(yōu)化問題，并采用遺傳算法求解問題。以往研究普遍假設(shè)車輛的行駛時間以及車輛到達(dá)站點的時間是確定的，但在實際中，公交車輛服務(wù)于較為開放的城市道路網(wǎng)絡(luò)，受到各種隨機因素(如交通擁堵、交通事故、天氣狀況等)的影響，車輛的行駛時間及車輛到站時間通常具有隨機性，表現(xiàn)為服從一定的概率分布。

出于這種研究需求，學(xué)者們開始研究考慮車輛隨機到站時間的公交線路優(yōu)化問題，Chen等[5]在優(yōu)化常規(guī)公交服務(wù)時考慮服從正態(tài)分布的車輛隨機到站時間(Stochastic Arrival Time,SAT)，研究表明，采用確定性的車輛到站時間會嚴(yán)重低估系統(tǒng)總成本。Jiang 等[6]研究了行駛時間不確定的電動公交調(diào)度問題，并采用分支定價算法求解問題。已有考慮車輛隨機到站時間的公交線路優(yōu)化研究中，多是針對固定線路的常規(guī)公交展開的，而針對動態(tài)DRFT的研究還存在不足。

綜上，本文研究考慮車輛隨機到站時間的動態(tài)DRFT(SAT-D-DRFT)線路優(yōu)化問題，以最小化包含運營商成本、乘客乘車時間成本和乘客等待時間成本組成的系統(tǒng)總成本為目標(biāo)建立模型，尋求考慮車輛在行駛途中接收乘客實時需求，同時考慮服從一定分布的車輛隨機到站時間情形下的最優(yōu)公交線路方案，并提出一種遺傳算法和鄰域搜索相結(jié)合的啟發(fā)式算法求解該模型，通過算例測試了本文提出模型和算法的優(yōu)勢。

1 SAT-D-DRFT線路優(yōu)化問題描述與建模

1.1 問題描述

本文研究問題如圖1所示，在考慮車輛隨機到站時間的情形下，根據(jù)初始預(yù)約需求(包含上車點、上車時間窗、乘客人數(shù)等信息)合理規(guī)劃公交初始線路，當(dāng)車輛按照計劃服務(wù)初始預(yù)約需求時，系統(tǒng)每隔一段時間統(tǒng)計一次接收到的實時需求，并結(jié)合實時需求信息對公交線路進行重新優(yōu)化，使得由乘客時間成本與運營商成本組成的系統(tǒng)總成本最小。

圖1 動態(tài)需求響應(yīng)型接駁公交線路優(yōu)化問題示意圖Fig.1 Diagram of dynamic bus routing optimization problem for demand-responsive feeder transit

1.2 數(shù)學(xué)模型假設(shè)

建模假設(shè)如下：

(1)需求響應(yīng)型接駁公交服務(wù)區(qū)域已知。

(2)所有乘客需求均需要被滿足。

(3)車輛到達(dá)網(wǎng)絡(luò)節(jié)點的時間服從已知概率分布。

(4)所有乘客均會準(zhǔn)時到達(dá)需求點，且在需求點上車，在樞紐點下車。

1.3 數(shù)學(xué)模型建立

本文研究的SAT-D-DRFT 服務(wù)網(wǎng)絡(luò)定義在圖G=(V,A) 上，其中，V為所有節(jié)點集合，A為弧集，A={(i,j):i,j∈V}。公交線路優(yōu)化過程分為發(fā)車前基于初始預(yù)約需求的初始線路優(yōu)化和發(fā)車后基于實時需求的動態(tài)優(yōu)化調(diào)整。

1.3.1 初始規(guī)劃階段(基于初始預(yù)約需求)

表1 初始規(guī)劃階段符號說明Table 1 Notation for initial static stage

式(1)為目標(biāo)函數(shù)，最小化了系統(tǒng)總成本，包含3 個部分：式(2)為運營商成本Z1，包含車輛使用固定成本和運營成本；式(3)為乘客乘車時間成本Z2，即乘客人數(shù)qi，車內(nèi)乘客單位時間成本λ3與乘客等待時間成本Z3，當(dāng)車輛晚于時間窗上限li到達(dá)時，i點乘客的等待時間成本為等待時間，車外乘客單位時間成本λ4與乘客數(shù)qi的乘積。式(5)～式(14)為約束條件：式(5)表示每個需求點有且只有一輛車訪問；式(6)為車輛進出需求點流量守恒；式(7)為派遣車輛進出樞紐點流量守恒；式(8)為車容量約束；式(9)和式(10)表示節(jié)點間的客流遞推關(guān)系，同時，式(9)消除了線路子循環(huán)；式(11)計算車輛在節(jié)點開始服務(wù)時間；式(12)計算車輛離開節(jié)點時間；式(13)為車輛在各節(jié)點時間的變化關(guān)系；式(14)表示在給定的置信水平ζ下，每條線路的最長行駛時間不大于Tmax。

1.3.2 動態(tài)調(diào)整階段(基于實時需求)

動態(tài)調(diào)整階段建模使用符號如表2所示。

表2 動態(tài)規(guī)劃階段符號說明Table 2 Notation for dynamic stage

動態(tài)調(diào)整階段與初始規(guī)劃階段的一個重要區(qū)別在于初始規(guī)劃階段的需求點僅為初始預(yù)約需求點N0+，而動態(tài)調(diào)整階段中的需求點包含兩個部分，以第r次實時需求為例，需求點包含接收到的實時需求點和未被服務(wù)的需求點。式(15)為第r次統(tǒng)計實時需求后調(diào)整線路的目標(biāo)函數(shù)，最小化系統(tǒng)總成本，包含3個部分：式(16)為運營商成本，包括派遣額外車輛的固定成本和車輛的運營成本兩個部分；式(17)為乘客乘車時間成本，包含未被服務(wù)乘客的乘車時間成本和車內(nèi)乘客后續(xù)的乘車時間成本兩個部分；式(18)為乘客等待時間成本。式(19)～式(28)為動態(tài)規(guī)劃階段的約束條件，含義可參見式(5)～式(14)。

1.4 車輛隨機到站時間分布

參考Lanza 等[7]研究，考慮到伽馬分布具有全正值、“偏態(tài)”、“長尾”等性質(zhì)，本文假設(shè)車輛的到站時間服從伽馬分布，即～gamma(αjk,θjk)，參數(shù)αjk為形狀參數(shù)，θjk為尺度參數(shù)，給出的概率密度函數(shù)f()為

本文假設(shè)以下信息均是已知的：各站點間的車輛行駛時間均值E[ti-1,i]，車輛從車場發(fā)車的時間，車輛在各站點的時間窗約束以及車輛在各站點的服務(wù)時間sik，則可由式(32)計算得到。由式(30)和式(31)可知，若已知，θjk值越大，越大，則車輛到站時間的不確定性越大。

2 遺傳-鄰域搜索啟發(fā)式算法

本文研究的SAT-D-DRFT 線路優(yōu)化問題是一個NP 難問題，因此，提出一種遺傳-鄰域搜索啟發(fā)式算法(Hybrid Genetic Algorithm and Local Search,HGA-LS)求解該問題。該算法融合了遺傳算法的全局搜索優(yōu)勢和鄰域搜索的局部搜索能力，可以有效提高收斂速度。

2.1 初始線路規(guī)劃階段

初始線路規(guī)劃的算法偽代碼如表3所示。表4顯示了考慮車輛隨機到站時間情形下解的適應(yīng)度函數(shù)評估過程。

表3 遺傳-鄰域搜索啟發(fā)式算法偽代碼Table 3 Pseudocode of hybrid genetic algorithm and local search(HGA-LS)

表4 考慮車輛隨機到站時間情形下解的適應(yīng)度函數(shù)評估偽代碼Table 4 Pseudocode of fitness evaluation considering stochastic bus arrival time

2.2 線路動態(tài)優(yōu)化調(diào)整階段

在統(tǒng)計實時需求后，要立即采取措施對線路進行重新優(yōu)化調(diào)整，因此，需要確定當(dāng)前乘客需求點以及車輛使用等情況。這部分過程的偽代碼如表5所示。

表5 車輛狀態(tài)確定偽代碼Table 5 Pseudocode of bus status

確定初始派遣車輛的實時狀態(tài)后，安排車輛為更新后的需求點集合服務(wù)，如果已派遣車輛無法為所有需求點服務(wù)，則需要派遣新的車輛。算法過程如表6所示。

表6 動態(tài)優(yōu)化調(diào)整階段偽代碼Table 6 Pseudocode of dynamic stage

3 算例實驗與結(jié)果分析

首先，采用改編Solomon 提出的經(jīng)典VRPTW算例[8]和2021年吳典文等提出的算例[9]測試本文模型和算法的有效性和先進性。再基于西安市地鐵3號線延平門站生成算例對模型的適用性進行仿真研究。算法編程采用MATLAB R2018b 及LINGO(18.0 version)求解器在內(nèi)存8 G，CPU 3.0 GHz 的PC 機上運行。算法參數(shù)取值與對應(yīng)算例規(guī)模相關(guān)，經(jīng)多次反復(fù)測試，不同算例的算法參數(shù)取值如表7所示。

表7 HGA-LS參數(shù)取值Table 7 Parameter value of HGA-LS

3.1 模型測試分析

為了測試本文模型和算法的有效性，改編Solomon的R101算例生成本文測試算例，分別選取5～50 個需求生成不同規(guī)模的算例，將LINGO 求解器與HGA-LS求得的結(jié)果進行比較，如表8所示，其中，LINGO求解器的運算時間上限設(shè)定為10800 s，HGA-LS 算法結(jié)果是進行10 次重復(fù)實驗得到的最優(yōu)值，平均值及平均運算時間。

表8 LINGO與HGA-LS求解結(jié)果對比Table 8 Results of LINGO and HGA-LS

表8顯示了本文提出模型的準(zhǔn)確性。計算結(jié)果顯示：當(dāng)算例規(guī)模增加到15個需求點時，LINGO求解器在規(guī)定的時間內(nèi)(10800 s)無法找到可行解，運算時間的比較表明啟發(fā)式算法在求解復(fù)雜模型時更有優(yōu)勢。算例R101-15 的目標(biāo)函數(shù)迭代圖如圖2所示。

圖2 算例R101-15的目標(biāo)函數(shù)迭代圖Fig.2 Iteration figure of objective function for R101-15

3.2 算法測試分析

為了測試本文提出算法的先進性，采用HGALS 算法對吳典文等[9]提出的僅基于預(yù)約需求的DRFT 線路優(yōu)化問題算例進行求解，結(jié)果如表9所示。表中展示了采用HGA-LS 算法進行10 次重復(fù)實驗得到的系統(tǒng)總成本最優(yōu)值和平均值、HGA-LS平均運算時間、最優(yōu)解所對應(yīng)的線路。

表9 模擬退火算法與HGA-LS算法求解結(jié)果對比Table 9 Results of simulated annealing and HGA-LS

如表9所示，相比文獻中的模擬退火算法，本文提出的HGA-LS 算法可以規(guī)劃出使系統(tǒng)總成本更小(減少了6.8%)的公交線路，表明HGA-LS算法的先進性。算法的求解穩(wěn)定性和運算時間均在可接受范圍內(nèi)，表明了HGA-LS 算法能夠有效求解DRFT 線路優(yōu)化問題，一定程度上說明將全局搜索算法和鄰域搜索策略合理的融合可以提高算法求解性能。本算例的目標(biāo)函數(shù)迭代圖如圖3所示。

圖3 DRFT算例的目標(biāo)函數(shù)迭代圖Fig.3 Iteration figure of objective function for DRFT

3.3 基于西安市的算例

3.3.1 算例描述

算例選取西安市地鐵3 號線延平門地鐵站為樞紐站點，動態(tài)DRFT的服務(wù)區(qū)域如圖4所示，乘客需求點使用數(shù)字1～40 標(biāo)記，乘客出行時空需求如表10所示，各節(jié)點間的距離采用歐幾里得距離。參數(shù)的取值來源于西安公交公司的實際調(diào)研及相關(guān)文獻[10]，Q=10人，λ1=60元·輛-1，λ2=5.76元·km-1，λ3=38 元·h，λ4=58 元·h-1，Tmax=20 min。

圖4 西安市延平門地鐵站及乘客需求點位置示意圖Fig.4 Locations of Yanpingmen station and passenger demand

表10中乘客需求分為初始預(yù)約需求和實時需求兩個部分，車輛9:00從樞紐站發(fā)車對初始預(yù)約需求(共30 組)進行服務(wù)，每間隔4 min 對實時需求進行一次統(tǒng)計，9:04 第1 次統(tǒng)計收到站點10，27，33，36和40的5組乘客提交的實時需求，9:08第2次統(tǒng)計收到站點6，11，22，28和31的5組乘客提交的實時需求，即需要在9:04 和9:08 時動態(tài)調(diào)整DRFT線路。

表10 乘客需求時空信息Table 10 Temporal and spatial information of passenger requests

3.3.2 結(jié)果分析

表11和表12為公交線路優(yōu)化結(jié)果。結(jié)果表明，本文設(shè)計的HGA-LS算法既可以根據(jù)初始預(yù)約需求規(guī)劃出合理的初始線路，又可以在實時需求出現(xiàn)后快速的動態(tài)調(diào)整優(yōu)化路徑，顯示出HGALS針對SAT-D-DRFT線路優(yōu)化問題的有效性。

表11 基于初始預(yù)約需求的規(guī)劃結(jié)果Table 11 Results based on reservation requests

表12 基于實時需求調(diào)整的優(yōu)化結(jié)果Table 12 Results of adjustment based on real-time requests

3.3.3 考慮車輛隨機到站時間的必要性分析

分別對考慮確定的和考慮隨機的車輛到站時間結(jié)果進行分析，采用車輛到站時間的均值作為車輛確定的到站時間，結(jié)果如表13所示。

表13 考慮車輛確定到站時間和考慮車輛隨機到站時間的結(jié)果對比Table 13 Results of considering deterministic and stochastic bus arrival time

相比于確定的車輛到站時間，將車輛到站時間的隨機性考慮其中，結(jié)果增加了1 輛車，運營商成本略有增加(6.9%)；車輛數(shù)增加使每輛車服務(wù)的站點數(shù)減少，乘客的乘車時間減少(乘車時間成本減少10%)，乘客的等待時間成本顯著減少(47.6%)，系統(tǒng)總成本減少5.8%。結(jié)果說明，考慮車輛隨機到站時間可以有效減少乘客時間成本和系統(tǒng)總成本，進一步提高了乘客公交出行滿意度，持續(xù)提高出行者選擇公交出行的吸引力。

4 結(jié)論

本文得到的主要結(jié)論如下：

(1)針對考慮車輛隨機到站時間的動態(tài)需求響應(yīng)型接駁公交(SAT-D-DRFT)線路優(yōu)化問題設(shè)計了HGA-LS算法，與模擬退火算法相比，HGA-LS算法得到了使系統(tǒng)總成本下降6.8%的公交線路方案，驗證了HGA-LS算法的有效性和先進性，一定程度上說明將全局搜索算法和鄰域搜索策略合理融合可以提高算法的求解性能。

(2)與傳統(tǒng)考慮確定的車輛到站時間相比，考慮車輛隨機到站時間在一定程度上可以減少10%的乘客時間成本和5.8%的系統(tǒng)總成本，其中乘客等待時間成本顯著減少了47.6%。