可變線路公交車輛調(diào)度算法優(yōu)化研究*

邵孜科 張 泉 王樹盛 張小輝 李文權(quán)

(1.江蘇省城市規(guī)劃設(shè)計研究院 南京 210036；2.江蘇省城市交通規(guī)劃研究中心 南京 210036；3.江蘇省住房和城鄉(xiāng)建設(shè)廳 南京 210036；4.東南大學(xué)交通學(xué)院 南京211189)

0 引 言

近年來，隨著城鎮(zhèn)化的進一步推進，交通出行不僅在數(shù)量上大規(guī)模增長，而且呈現(xiàn)出多樣化的趨勢。常規(guī)公交雖然能夠滿足基本的出行需求，但是無法更好地服務(wù)多樣化的出行需求，增長的交通需求與落后的交通供給之間的矛盾日益突顯。因此，如何豐富現(xiàn)有的公共交通運行模式，從廣度與深度上提升公交服務(wù)的質(zhì)量，是我國現(xiàn)階段新型城鎮(zhèn)化建設(shè)時期一個亟待解決的問題。

提高公交服務(wù)質(zhì)量的方式有2種，一種是進一步提高常規(guī)公交的服務(wù)質(zhì)量，另一種是探索新型公交運行模式，前者的研究成果相對較多[1-2]，后者的研究成果相對較少?？勺兙€路公交就是一種融合了常規(guī)公交與需求響應(yīng)公交特點的新型公交運行模式，在提供固定站點間出行的同時，還能夠滿足乘客的個性化出行需求[3]。對可變線路公交等需求響應(yīng)式公交的調(diào)度研究是當(dāng)下的一個熱點問題。Cordeau[4]和Liu等[5]針對DAR問題分別建立了數(shù)學(xué)模型，并采用分枝切割算法對模型進行求解。Cremers等[6]研究了提前1 d預(yù)約的Paratransit規(guī)劃問題，并建立了一個非標(biāo)準的兩階段整數(shù)追索模型。Paquette等[7]綜合考慮成本與服務(wù)質(zhì)量，建立了多準則的成本函數(shù)，并設(shè)計了禁忌搜索算法求解該模型。Quadrifoglio等[8]提出了一種簡單插入算法，以效用變化最小的為目標(biāo)，將乘客逐次插入到每個班次中，并將其應(yīng)用到了可變線路公交的仿真模擬[9-10]。林葉倩等[11]考慮了乘客的出行成本和企業(yè)的運營成本，建立了可變線路公交調(diào)度目標(biāo)函數(shù)，采用遺傳算法求解模型。邱豐等[3]建立了同時處理靜態(tài)需求和動態(tài)需求的2階段調(diào)度模型，針對2個模型分別設(shè)計了模擬退火算法和插入算法求解模型，同時對可變線路公交的其他方面進行了詳細的研究[12-16]。潘述亮等[17-18]分別對靈活型公交的服務(wù)區(qū)域和車輛路徑建立了模型，并提出了基于重力模型的啟發(fā)式求解算法。盧小林等[19]研究了復(fù)雜路網(wǎng)下的可變線路公交車輛路徑規(guī)劃問題。

現(xiàn)階段針對可變線路公交調(diào)度算法的研究主要分為2類，一類是設(shè)計簡單的啟發(fā)式算法，主要特點是算法簡單易于實際應(yīng)用，但其僅從局部最優(yōu)出發(fā)，無法保證總體求解質(zhì)量；另一類是基于智能算法的啟發(fā)式算法，比如：遺傳算法、禁忌搜索算法等，主要特點是綜合考慮全局的最優(yōu)性，但算法相對復(fù)雜且求解時間較長，難以實際應(yīng)用。本文針對第一類簡單插入算法，從減少乘客平均出行時間和降低系統(tǒng)拒絕率2個角度出發(fā)，分別提出了相應(yīng)的優(yōu)化算法，從而提高出行者的總體出行質(zhì)量。

1 可變線路公交車輛調(diào)度模型

可變線路公交是一種在固定站點(首末站和控制站)擁有嚴格的時間約束，在固定站點間車輛沒有固定運行路線的公交運行方式，見圖1。

圖1 可變線路公交服務(wù)Fig.1 Flex-route buses

根據(jù)乘客起訖點位置的特征，可變線路公交服務(wù)4類乘客：第1類是固定站上車，固定站下車的乘客；第2類是固定站外上車，固定站外下車的乘客；第3類是固定站上車，固定站外下車的乘客；第4類是固定站外上車，固定站下車的乘客。

1.1 模型假設(shè)

可變線路公交的實際運行是一個復(fù)雜的過程，受諸多因素影響，為了建立調(diào)度模型，本文做如下假設(shè)。

1)可變線路公交更多的是服務(wù)特殊群體，所以本文認為可變線路公交是一種預(yù)約型公交，即在進行調(diào)度安排前，已經(jīng)獲取了所有乘客的出行信息。

2)在實際運行中，乘客的出行分布具有很強的時空特征，但本文更注重方法論的介紹，所以，假設(shè)服務(wù)區(qū)域內(nèi)的乘客出行分布在時間和空間上都服從均勻分布。

3)可變線路公交的調(diào)度與路網(wǎng)條件息息相關(guān)，為了簡化模型以及便于說明設(shè)計思路，忽略路網(wǎng)對調(diào)度的影響。Quadrifoglio等[20]已經(jīng)證明“對角”路徑能夠反映車輛真實的運行情況。本文假設(shè)車輛按“對角”路徑運行，即公交車輛只能沿水平或垂直方向運行。

4)可變線路公交常用于低出行密度區(qū)域，乘客出行總量小[13,21]，所以為了簡化模型不考慮車輛的容量約束。

1.2 模型建立

可變線路公交的車輛調(diào)度是在確定可變線路公交的行車計劃之后，根據(jù)乘客的預(yù)約信息，解決“每個班次服務(wù)哪些乘客，怎么服務(wù)” 的問題。和常規(guī)公交一樣，可變線路公交也能從運營者和乘客角度出發(fā)建立雙層規(guī)劃模型，運營者希望在固定投入下能夠服務(wù)更多的乘客，乘客則希望出行的時間越短越好。

(1)

(2)

(3)

(4)

(5)

(6)

式(1)為上層目標(biāo)函數(shù)，上層目標(biāo)是可變線路公交系統(tǒng)服務(wù)乘客數(shù)量最多。式(2)為下層目標(biāo)函數(shù)，下層目標(biāo)是服務(wù)質(zhì)量最高，即乘客的平均出行時間最小，乘客的平均出行時間由2部分組成，一部分是所有被服務(wù)乘客在公交車上的平均行程時間，另一部分是所有被服務(wù)乘客實際上車時間與預(yù)約上車時間的平均偏差時間。式(3)為車輛的固定站到站時間約束，保證車輛必須在要求到站時間前進站。式(4)和式(5)為當(dāng)站點j和站點u在班次k上時，車輛到達站點j的時間等于車輛離開站點u的時間加上2個站點之間的車輛行駛時間。式(6)為每個乘客至多被服務(wù)1次，拒絕的乘客得不到服務(wù)。

可變線路公交的調(diào)度問題是典型的NP-Hard問題，當(dāng)數(shù)據(jù)達到一定規(guī)模時，只能通過啟發(fā)式算法進行求解。插入算法是解決可變線路公交調(diào)度問題的常用簡單算法，每次只安排1個乘客，按照一定的規(guī)則，每次將乘客安排在“最合適”的位置上，其操作簡單，時間效率高。

算法的質(zhì)量由算法效率和算法精度綜合評判，設(shè)計簡單的算法一般更注重算法效率，所以在算法精度方面有較大的優(yōu)化空間。本文將采用拒絕乘客重新安排的思路提高目前基于簡單插入的調(diào)度算法的精度，分別以模型的上下層目標(biāo)(增加服務(wù)乘客人數(shù)和減少乘客平均出行時間)為算法的“進化”方向，對算法進行優(yōu)化研究，提高算法精度。

2 可變線路公交車輛調(diào)度算法優(yōu)化

在介紹算法之前，先介紹“區(qū)間段”和“松弛時間”2個概念。

區(qū)間段即可變線路公交每個固定站都有固定的進出站時刻，所以相鄰兩固定站之間的車輛路徑是相互獨立的，也就說，班次按照固定站可以細分成若干段，將其稱之為“區(qū)間段”。

松弛時間即車輛能夠偏離現(xiàn)有路線，額外服務(wù)新乘客的時間，數(shù)值上等于固定站規(guī)定的進站時刻減去現(xiàn)狀態(tài)下實際的進站時刻。

2.1 基于簡單插入的調(diào)度算法

基于簡單插入的調(diào)度算法是最簡單的可變線路公交調(diào)度算法，其具體步驟如下。

步驟1。根據(jù)乘客起訖點的位置，分別確定乘客起訖點所屬的“區(qū)間段”。假設(shè)構(gòu)成“區(qū)間段”的固定站點的橫坐標(biāo)為X1和X2，新插入乘客的起點或訖點的橫坐標(biāo)為x，那么新插入乘客點所屬的“區(qū)間段”滿足如下關(guān)系。

(x-X1)(x-X2)<0

(7)

步驟2。選擇第一個班次。

步驟3。計算 “區(qū)間段”內(nèi)所有可插入位置消耗的松弛時間，將消耗松弛時間最少的位置確定為“區(qū)間段”內(nèi)的最終插入位置。新乘客在“區(qū)間段”內(nèi)會有多個位置可以插入(見圖2)，這一步的作用是計算乘客插入不同位置所消耗的松弛時間，新乘客將被安排在消耗松弛時間最小的位置。

圖2 乘客插入位置Fig.2 Possible insertion positions for a passenger

步驟4。確定所選班次是否屬于可插入班次備選集合。根據(jù)乘客點最終插入位置消耗的松弛時間，如果消耗的松弛時間小于對應(yīng)的可消耗松弛時間，那么班次進入備選班次集合。

步驟5。如果分析的是最后一個班次，那么跳轉(zhuǎn)步驟6；如果分析的不是最后一個班次，那么選擇下一個班次，并跳轉(zhuǎn)步驟3。

步驟6。確定乘客最終的插入班次。如果乘客對應(yīng)的可插入班次備選集合是一個空集，那么該乘客的出行要求將被系統(tǒng)拒絕；如果備選班次集合不為空集，則分別計算備選集合中每個班次對應(yīng)的乘客平均出行時間，將乘客平均出行時間最小的班次確定為乘客點最終的插入班次。

該算法的優(yōu)點是算法簡單且效率高，缺點是每一次的局部最優(yōu)會使最終的結(jié)果偏離整體最優(yōu)，因為在時間和空間上看似毫不相關(guān)的2個乘客，極有可能相互影響，一個乘客的“最優(yōu)選擇”會導(dǎo)致另一個乘客被系統(tǒng)拒絕。

通過拒絕乘客重新安排的方式，即拒絕-重新插入優(yōu)化操作，可以降低乘客間的潛在影響，提高算法的精度，即當(dāng)出現(xiàn)拒絕乘客的現(xiàn)象時，系統(tǒng)觸發(fā)“拒絕-重新插入”操作?！熬芙^-重新插入”操作通過移動原來已經(jīng)安排好的乘客尋求插入該拒絕乘客的可行性，即重新構(gòu)造被拒絕乘客的備選班次集合。

“拒絕-重新插入”的規(guī)則就是簡單插入算法的“進化”方向，不同側(cè)重點的進化方向會給算法帶來不同的優(yōu)化結(jié)果。本文根據(jù)雙層規(guī)劃模型的上下層目標(biāo)，分別設(shè)置2個進化方向：①在進化時更加注重乘客平均出行時間，即側(cè)重減少乘客平均出行時間；②在進化時更加注重服務(wù)乘客數(shù)量，即側(cè)重進一步降低系統(tǒng)拒絕率。

2.2 側(cè)重減少乘客平均出行時間的優(yōu)化算法

側(cè)重減少乘客平均出行時間的優(yōu)化算法在制定“拒絕-重新插入”規(guī)則時，將乘客的平均出行時間作為算法的進化方向，思路是如果被拒絕乘客能夠重新安排至班次中，那么將乘客安排至引起乘客平均出行時間最小的位置，具體流程如下。

步驟1。選擇第一個班次。

步驟2。確定新插入乘客在該班次中的插入位置。采用簡單插入算法中的方法確定乘客的插入位置，此時，插入乘客后所消耗的松弛時間大于對應(yīng)“區(qū)間段”的可消耗松弛時間。

步驟3。移除乘客。將乘客從班次中移除，計算移除乘客后消耗的松弛時間。

步驟4。如果移除乘客后消耗的松弛時間仍然大于可消耗松弛時間，那么說明移除該乘客是無效的，如果這是最后一個乘客，跳轉(zhuǎn)步驟6，否則，選擇下一個乘客，跳轉(zhuǎn)步驟3；如果移除乘客后消耗的松弛時間小于可消耗松弛時間，那么說明移除該乘客是有效的，跳轉(zhuǎn)步驟5。

步驟5。將移除的乘客作為新乘客，按照簡單插入算法進行安排，如果被移除的新乘客不能重新被可變線路公交服務(wù)，那么移除該乘客仍然是無效的，如果這是最后一個乘客，跳轉(zhuǎn)步驟6，否則，選擇下一個乘客，跳轉(zhuǎn)步驟3；如果被移除的新乘客能夠被重新服務(wù)，那么移除該乘客是有效的，該乘客進入該班次的備選移除乘客集合，如果是最后一個乘客，跳轉(zhuǎn)步驟6，否則，選擇下一個乘客，跳轉(zhuǎn)步驟3。

步驟6。如果備選移除乘客集合是一個空集，說明“拒絕-重新插入”操作沒有效果，該乘客仍然會被拒絕；如果備選移除乘客集合不是空集，那么說明通過乘客間的位置變換，可以服務(wù)原來被拒絕的乘客，該班次可以進入備選班次集合。最終被移除并重新安排的乘客為使乘客平均出行時間最小的乘客。

步驟7。如果分析的是最后一個班次，那么完成重新確定備選班次集合的操作；如果分析的不是最后一個班次，那么選擇下一個班次，并跳轉(zhuǎn)步驟2。

2.3 側(cè)重降低系統(tǒng)拒絕率的優(yōu)化算法

側(cè)重降低系統(tǒng)拒絕率的優(yōu)化算法在制定“拒絕-重新插入”規(guī)則時，將每次最大化的利用松弛時間作為算法的進化方向，思路是如果被拒絕乘客能夠重新安排至班次中，那么將乘客安排至消耗松弛時間最少的位置，與側(cè)重減少乘客平均出行時間的優(yōu)化算法相比，主要變化在步驟5和步驟6。

步驟5的變化。被移除乘客新班次的安排不再按照乘客平均出行時間最小確定，而是將使消耗松弛時間最小的班次確定為被移除乘客的插入班次。

步驟6的變化。最終被移除乘客的選擇也不再按照乘客平均出行時間最小確定，而是將移除乘客后使原班次減少消耗的松弛時間與重新插入該移除乘客后增加消耗的松弛時間之和最小的乘客確定為最終移除的乘客。

3 案例分析與算法比較

由于國內(nèi)尚沒有可變線路公交，所以本文選用美國646路公交線路的基礎(chǔ)數(shù)據(jù)[3]進行算法比較。646路可變線路公交的服務(wù)區(qū)域是一個16×1.6 km2的矩形區(qū)域。除公交首末站外，在服務(wù)區(qū)域的中心位置設(shè)置了一個控制站，即相鄰固定站之間的水平距離為8 km。公交車的發(fā)車間隔為100 min，運行周期為50 min，即相鄰2個控制站之間的運行時間為25 min，車輛的行駛速度為40 km/h。4類出行乘客的比例大概為0.1∶0.1∶0.4∶0.4。另一方面，假設(shè)可變線路公交服務(wù)一個乘客所需要的停留時間均為18 s，在控制站的停留時間為2 min。

公交有從首站到末站和從末站到首站2個運行方向，由于對稱性，在分析時，只選取一個方向作為分析對象。對單方向乘客出行需求為5人/h、10人/h、15人/h和20人/h的4種情況進行分析。仿真試驗?zāi)M可變線路公交的服務(wù)時間為10 h，為了保證結(jié)果的穩(wěn)定性，對每種情形各進行1 000次的仿真模擬，仿真結(jié)果見表1～2。

表1 不同算法下的可變線路公交拒絕率仿真結(jié)果

注：算法1為簡單插入算法；算法2為側(cè)重減少乘客平均出行時間的優(yōu)化算法；算法3為側(cè)重降低系統(tǒng)拒絕率的優(yōu)化算法

乘客出行需求為10人/h時，幾乎所有的乘客都能被公交系統(tǒng)服務(wù)，但偶爾仍會發(fā)生拒絕乘客出行的現(xiàn)象；乘客出行需求為15人/h時，公交系統(tǒng)開始拒絕一定比例的乘客出行要求，但平均拒絕率處于較低的水平。因為整體拒絕率處于較低的水平，所以乘客出行需求為10～15人/h時，交通需求與供給是相互適應(yīng)的。

表2 不同算法下的可變線路公交乘客平均出行時間仿真結(jié)果

乘客出行需求為5人/h時，由于完全不存在拒絕乘客出行的情況，所有乘客都能被公交系統(tǒng)服務(wù)，此時，交通供給極可能遠大于需求；乘客出行需求為20人/h時，公交系統(tǒng)開始大規(guī)模拒絕乘客出行要求，拒絕率接近20%，交通需求與供給已經(jīng)處于失衡狀態(tài)。可變線路公交系統(tǒng)不僅需要考慮乘客的服務(wù)質(zhì)量，也需要考慮運營成本，即交通需求與供給宜處于一個平衡的狀態(tài)，故后續(xù)分析主要集中在乘客出行需求為10人/h和15人/h的2種情況。

因為乘客出行需求為10人/h時，系統(tǒng)幾乎服務(wù)所有的乘客，所以3種算法的平均乘客平均出行時間差別不大，分別為51.17，51.51和51.21 min。算法3不會產(chǎn)生拒絕乘客的現(xiàn)象，算法1和算法2偶爾會出現(xiàn)拒絕乘客的現(xiàn)象。當(dāng)出現(xiàn)拒絕現(xiàn)象時，算法1的最大拒絕率為11%，算法2的最大拒絕率為3%，所以與算法1相比，算法2能降低出現(xiàn)極端拒絕率的情況，保證可變線路公交系統(tǒng)服務(wù)質(zhì)量的穩(wěn)定性。

乘客出行需求為15人/h時是一種正常的供需平衡狀態(tài)，可變線路公交系統(tǒng)能夠服務(wù)絕大多數(shù)的乘客以保證服務(wù)質(zhì)量，但也會拒絕一小部分乘客的出行需求以控制運營成本。2種優(yōu)化算法能顯著的服務(wù)更多的乘客，與算法1的平均拒絕率相比，算法2降低了3.03%，算法3降低了3.42%，故算法3比算法2更優(yōu)。3種算法的最大拒絕率分別為18.67%，18%和18%，表明無論哪種算法都無法阻止可變線路公交系統(tǒng)出現(xiàn)極端服務(wù)質(zhì)量的情況。另一方面，3種算法平均拒絕率的方差為14.90，12.64和11.91，說明算法3比其他2種算法更能保證可變線路公交系統(tǒng)服務(wù)質(zhì)量的穩(wěn)定性。

在乘客平均出行時間方面，算法2和算法3的平均值分別比算法1高4.01 min和5.24 min，這是因為可變線路公交服務(wù)的乘客數(shù)量增多，車輛的繞行時間增加，乘客的行程時間也就增加，導(dǎo)致平均出行時間變大。結(jié)合乘客平均出行時間的方差、最小值和最大值，在時間維度上3種算法差別不大，乘客的出行體驗差別不大。

算法選擇是建立在需求與供給相互適應(yīng)的基礎(chǔ)上的，目標(biāo)是在確定供給的情況下，盡可能地提高供給的效率和服務(wù)質(zhì)量。拒絕率代表著服務(wù)效率，拒絕率越低，供給的使用效率就越高。乘客平均出行時間代表著服務(wù)質(zhì)量，乘客平均出行時間越低，服務(wù)質(zhì)量就越高。與其他2種算法相比，側(cè)重降低系統(tǒng)拒絕率的優(yōu)化算法(即算法3)能夠在維持服務(wù)質(zhì)量處于一定水平的基礎(chǔ)上，顯著提高可變線路公交的使用效率。

4 結(jié) 論

本文從運營者和乘客角度出發(fā)，建立了可變線路公交調(diào)度的雙層規(guī)劃模型，上層目標(biāo)是可變線路盡可能地服務(wù)更多的乘客，達到效率最大化，下層目標(biāo)是盡可能地縮短乘客的平均出行時間，提高服務(wù)質(zhì)量。針對簡單插入算法的缺點，從不同的“進化”方向?qū)λ惴ㄟM行優(yōu)化，提出了側(cè)重減少乘客平均出行時間和側(cè)重降低系統(tǒng)拒絕率的2種優(yōu)化算法。

在需求與供給相匹配的情況下，2種優(yōu)化算法的結(jié)果都優(yōu)于簡單插入算法。在乘客出行需求為10人/h時，2種優(yōu)化算法能夠降低出現(xiàn)極端拒絕率的概率，提高算法的穩(wěn)定性；在乘客出行需求為15人/h時，2種優(yōu)化算法能夠降低3%左右的拒絕率，提高算法的精度。

本文研究的算法主要針對的是設(shè)計簡單的啟發(fā)式算法，下一步研究的方向是結(jié)合基于智能算法的啟發(fā)式算法，對2類算法在解的質(zhì)量和算法效率2個方面進行比較分析。