考慮車(chē)輛隨機(jī)到站時(shí)間的動(dòng)態(tài)需求響應(yīng)型接駁公交線路優(yōu)化

孫倩，胡大偉*，錢(qián)一之，江捷，高天洋，姜瑞森

(1.長(zhǎng)安大學(xué)，運(yùn)輸工程學(xué)院，西安 710064；2.新澤西理工學(xué)院，土木與環(huán)境工程系，紐瓦克 NJ07102，美國(guó)；3.深圳市城市交通規(guī)劃設(shè)計(jì)研究中心股份有限公司，城市交通規(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)化問(wèn)題受到廣泛關(guān)注，Montenegro 等[1]以乘客滿意度最大為目標(biāo)建立DRFT線路優(yōu)化模型，并采用一種大鄰域搜索算法求解。安久煜等[2]以車(chē)輛行駛時(shí)間最小化為目標(biāo)，根據(jù)預(yù)約需求規(guī)劃DRFT 線路。Costa等[3]研究了動(dòng)態(tài)DRFT(D-DRFT)線路優(yōu)化問(wèn)題，以乘客出行時(shí)間最小化為目標(biāo)搜索最優(yōu)車(chē)輛分配。王正武等[4]以系統(tǒng)總成本最小化為目標(biāo)，研究了考慮多車(chē)場(chǎng)、多車(chē)型的D-DRFT 線路優(yōu)化問(wèn)題，并采用遺傳算法求解問(wèn)題。以往研究普遍假設(shè)車(chē)輛的行駛時(shí)間以及車(chē)輛到達(dá)站點(diǎn)的時(shí)間是確定的，但在實(shí)際中，公交車(chē)輛服務(wù)于較為開(kāi)放的城市道路網(wǎng)絡(luò)，受到各種隨機(jī)因素(如交通擁堵、交通事故、天氣狀況等)的影響，車(chē)輛的行駛時(shí)間及車(chē)輛到站時(shí)間通常具有隨機(jī)性，表現(xiàn)為服從一定的概率分布。

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

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

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

1.1 問(wèn)題描述

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

圖1 動(dòng)態(tài)需求響應(yīng)型接駁公交線路優(yōu)化問(wèn)題示意圖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)車(chē)輛到達(dá)網(wǎng)絡(luò)節(jié)點(diǎn)的時(shí)間服從已知概率分布。

(4)所有乘客均會(huì)準(zhǔn)時(shí)到達(dá)需求點(diǎn)，且在需求點(diǎn)上車(chē)，在樞紐點(diǎn)下車(chē)。

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

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

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

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

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

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

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

表2 動(dòng)態(tài)規(guī)劃階段符號(hào)說(shuō)明Table 2 Notation for dynamic stage

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

1.4 車(chē)輛隨機(jī)到站時(shí)間分布

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

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

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

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

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

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

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

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

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

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

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

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

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

3 算例實(shí)驗(yàn)與結(jié)果分析

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

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

3.1 模型測(cè)試分析

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

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

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

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

3.2 算法測(cè)試分析

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

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

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

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

3.3 基于西安市的算例

3.3.1 算例描述

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

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

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

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

3.3.2 結(jié)果分析

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

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

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

3.3.3 考慮車(chē)輛隨機(jī)到站時(shí)間的必要性分析

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

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

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

4 結(jié)論

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

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

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