陳垚，柏赟*，張安英，毛保華，陳紹寬

(1.北京交通大學(xué)，綜合交通運(yùn)輸大數(shù)據(jù)行業(yè)重點(diǎn)實(shí)驗(yàn)室，北京 100044；2.廣東省交通運(yùn)輸規(guī)劃研究中心，廣州 510101)

0 引言

隨著城市交通快速發(fā)展和科技水平高速提升，自動(dòng)駕駛汽車[1]與共享出行[2]得到了國(guó)內(nèi)外學(xué)者的眾多關(guān)注。共享自動(dòng)駕駛汽車(Shared Autonomous Vehicles，SAV)是兩者相結(jié)合的產(chǎn)物。共享自動(dòng)駕駛汽車可為出行者提供便捷的需求響應(yīng)式服務(wù)，被視為未來(lái)城市交通系統(tǒng)的重要組成部分[3]。

在SAV運(yùn)營(yíng)過(guò)程中，系統(tǒng)通常需要進(jìn)行兩方面車輛調(diào)度，訂單分配(Vehicle-trip Assignment)與空車移位(Empty Vehicle Relocation)[4]。一方面，在乘客發(fā)送訂單后，訂單分配需要決策系統(tǒng)是否服務(wù)該訂單，若訂單被接受，系統(tǒng)還需為其指派車輛。另一方面，由于乘客出行需求存在一定的方向性，在運(yùn)營(yíng)過(guò)程中部分區(qū)域可能出現(xiàn)空車堆積，而另外區(qū)域出現(xiàn)車輛短缺。因此，系統(tǒng)有必要進(jìn)行空車移位，盡可能保證在需求位置處存在車輛供給，以提升車輛利用率。

乘客出行需求特征是SAV 車輛調(diào)度的主要依據(jù)[5]。車輛調(diào)度需適應(yīng)乘客出行需求的時(shí)空分布。然而，車輛調(diào)度決策需要實(shí)時(shí)動(dòng)態(tài)進(jìn)行，由于未來(lái)時(shí)段的出行需求難以提前掌握，給車輛動(dòng)態(tài)調(diào)度決策帶來(lái)一定的難度。因此，基于歷史出行需求規(guī)律制定科學(xué)合理的動(dòng)態(tài)調(diào)度策略，對(duì)提高系統(tǒng)收益與提升乘客服務(wù)水平都至關(guān)重要。

國(guó)內(nèi)外學(xué)者主要從社會(huì)影響[6]、乘客行為[7]、設(shè)施規(guī)劃[8]和車隊(duì)運(yùn)營(yíng)[4]等角度進(jìn)行SAV 的相關(guān)研究。在車輛動(dòng)態(tài)調(diào)度領(lǐng)域，部分學(xué)者基于仿真方法測(cè)試了不同啟發(fā)式策略的運(yùn)行效果。HYLAND等[9]利用Agent 仿真對(duì)比了6 種訂單分配策略。HORL等[10]利用MATSim仿真平臺(tái)分別評(píng)估了2種訂單分配與2 種空車移位策略的效果。部分學(xué)者也對(duì)車輛動(dòng)態(tài)調(diào)度優(yōu)化展開(kāi)研究。MAO等[11]利用深度強(qiáng)化學(xué)習(xí)提出了無(wú)模型下的空車移位策略。KANG 等[12]基于馬爾科夫決策建立了等待乘客無(wú)流失下的車輛調(diào)度模型，從理論角度分析了SAV系統(tǒng)的最大可服務(wù)乘客數(shù)量。AL-KANJ 等[13]利用近似動(dòng)態(tài)規(guī)劃與值函數(shù)逼近建立共享自動(dòng)駕駛電動(dòng)汽車的動(dòng)態(tài)調(diào)度方法，其調(diào)度策略涉及不同電量車輛的選派、空車移位與充電決策。然而，既有文獻(xiàn)較少同時(shí)考慮訂單分配與空車移位，尤其在訂單分配時(shí)，較少考慮乘客等待時(shí)間限制。如何在乘客發(fā)送訂單后，及時(shí)合理調(diào)度周邊車輛還有待進(jìn)一步探索。

鑒于此，本文綜合訂單分配與空車移位兩方面決策，詳細(xì)考慮乘客等待時(shí)間限制下的訂單分配，研究SAV 系統(tǒng)的車輛動(dòng)態(tài)調(diào)度問(wèn)題。為便于問(wèn)題建模，提出時(shí)空網(wǎng)絡(luò)刻畫(huà)車輛動(dòng)態(tài)調(diào)度問(wèn)題；并以時(shí)空節(jié)點(diǎn)流量為狀態(tài)，以時(shí)空弧流量為決策變量，構(gòu)造馬爾科夫決策模型；采用滾動(dòng)時(shí)域優(yōu)化思想建立隨機(jī)規(guī)劃方法求解各時(shí)刻的動(dòng)態(tài)決策結(jié)果；通過(guò)Sioux Falls網(wǎng)絡(luò)驗(yàn)證方法的有效性。

1 問(wèn)題描述與刻畫(huà)

1.1 SAV動(dòng)態(tài)調(diào)度問(wèn)題

SAV系統(tǒng)主要由SAV車隊(duì)、中央控制端與乘客3 部分組成。SAV 車隊(duì)規(guī)模固定且不提供合乘服務(wù)。SAV 交通網(wǎng)絡(luò)刻畫(huà)為一系列空間位置點(diǎn)及連接路段。各位置點(diǎn)可視為鄰近區(qū)域的聚類中心，以降低問(wèn)題復(fù)雜程度。位置點(diǎn)表示為s、i或j，其集合表示為S。由于AV 車輛具有專用道路，兩位置點(diǎn)間的行駛時(shí)間固定，位置i和j之間的行駛時(shí)間表示為lij。研究時(shí)段T離散為一系列等間隔的時(shí)刻，各時(shí)刻用t或k表示。

在研究時(shí)段內(nèi)，乘客通過(guò)手機(jī)App等向系統(tǒng)發(fā)送出行訂單。假設(shè)乘客發(fā)送的都是即時(shí)出發(fā)訂單，無(wú)提前預(yù)約訂單。出行信息包括當(dāng)前出發(fā)時(shí)刻t，出行起點(diǎn)i及終點(diǎn)j，表示為(i,j,t)。乘客可等待時(shí)長(zhǎng)固定為w，則乘客出發(fā)時(shí)間窗范圍為[t,t+w]。中央控制端實(shí)時(shí)接收乘客訂單，掌握所有SAV的位置與載客狀態(tài)，并將訂單分配給車輛。系統(tǒng)采取延遲集中分單策略(Batching Matching)，在時(shí)刻t集中分配時(shí)間段t-1 到t之間的訂單。每個(gè)訂單可以分配給3類車輛：在訂單出行起點(diǎn)的空閑車輛，該類車輛可直接將乘客運(yùn)送至目的地；在訂單出行起點(diǎn)附近的空閑車輛，該類車輛需先前往訂單起點(diǎn)接駕再運(yùn)送乘客；處于載客狀態(tài)但即將結(jié)束服務(wù)的車輛。該類車輛的上一訂單終點(diǎn)位置需與當(dāng)前訂單起點(diǎn)位置相同或附近(也稱為連續(xù)派單)。定義Si(l)表示距離位置i行程時(shí)間不超過(guò)l的位置點(diǎn)集合，即。因此，在乘客出發(fā)時(shí)間窗k∈[t,t+w]內(nèi)，位置處于s∈Si(t+w-k)(即lsi≤t+w-k)的空閑車輛均可在t+w時(shí)刻之前到達(dá)位置點(diǎn)i。因此，對(duì)于訂單(i,j,t)，在時(shí)刻k∈[t,t+w]空閑且位置處于s∈Si(t+w-k)的車輛均可被指派給該訂單。SAV 系統(tǒng)通過(guò)完成乘客訂單獲取收益。用Psij表示車輛由位置s前往位置i將乘客運(yùn)輸至j的載客收益，主要包括載客收入減去s到i的接駕途中與i到j(luò)的運(yùn)送途中的油耗等成本。

除訂單分配外，系統(tǒng)還需要在各時(shí)刻上進(jìn)行空車移位決策。系統(tǒng)決定是否將當(dāng)前處于位置s的空車移動(dòng)到另一位置j，以匹配乘客需求的空間分布。空車移位成本用Csj表示，主要包括s到j(luò)移車途中的油耗等成本。

綜上，SAV動(dòng)態(tài)調(diào)度問(wèn)題可總結(jié)為中央控制端在運(yùn)營(yíng)時(shí)段內(nèi)各個(gè)時(shí)刻根據(jù)乘客訂單信息進(jìn)行訂單分配與空車移位，其目標(biāo)為時(shí)間段內(nèi)總收益最大化。

1.2 時(shí)空網(wǎng)絡(luò)

為刻畫(huà)SAV車輛調(diào)度問(wèn)題，建立時(shí)空網(wǎng)絡(luò)。時(shí)空節(jié)點(diǎn)n為二元數(shù)組(i,t)，表征時(shí)間與空間信息。時(shí)空弧e連接兩個(gè)時(shí)空節(jié)點(diǎn)，其起終點(diǎn)表示為和，表示車輛運(yùn)行。在任意時(shí)刻下，空閑車輛有3個(gè)選項(xiàng)：接受訂單任務(wù)前往接送乘客，接受移位任務(wù)空駛移至其他位置以及原位置空車等待。因此，時(shí)空弧分為3 類：服務(wù)弧ESER、移位弧EREL與空閑弧EWAT。

(1)服務(wù)弧表征服務(wù)乘客出行下的車輛位置變化。對(duì)于每個(gè)訂單(i,j,t)，生成服務(wù)弧子集。由于系統(tǒng)可指派時(shí)刻k∈[t,t+w]空閑且位置處于的車輛服務(wù)于訂單(i,j,t)，對(duì)任意的，生成服務(wù)弧連接節(jié)點(diǎn)(s,k)與節(jié)點(diǎn)(j,t′)，其中，。該服務(wù)弧表示車輛在時(shí)刻k由位置s前往位置i接駕，再將乘客送往位置j。該服務(wù)弧的收益，服務(wù)弧的乘客等待時(shí)間。

(2)移位弧表征空車移位下的車輛位置變化。對(duì)任意的i∈S，j∈S和t∈T，生成移位弧e∈EREL連接節(jié)點(diǎn)(i,t)和節(jié)點(diǎn)(j,t+lij)，表示空閑車輛在時(shí)刻t由位置i移至位置j。該移位弧的收益。

(3)等待弧表征空車在原地等待指派。對(duì)任意i∈S和t∈T，生成等待弧e∈EWAT連接起點(diǎn)(i,t)和節(jié)點(diǎn)(i,t+1)。該等待弧表示車輛在時(shí)刻t位置i空閑?？臻e弧的收益為0。

車輛調(diào)度時(shí)空網(wǎng)絡(luò)示例如圖1所示。

圖1 車輛調(diào)度時(shí)空網(wǎng)絡(luò)Fig.1 Time-space network for SAV fleet management

圖1 中，在當(dāng)前時(shí)刻t，對(duì)于訂單(i,j,t)，服務(wù)弧e1表征當(dāng)前處于位置i的空閑車輛用于服務(wù)該訂單；服務(wù)弧e2表征當(dāng)前處于相鄰位置s的空閑車輛用于服務(wù)該訂單(需先前往位置i接駕)；服務(wù)弧e3和e4表征將在時(shí)刻t+1和t+2 空閑且處于位置i的車輛用于服務(wù)該訂單；服務(wù)弧e5表征將在時(shí)刻t+1 空閑且處于位置s的車輛用于服務(wù)該訂單(先前往位置i接駕)。該5 個(gè)服務(wù)弧均屬于。此

為刻畫(huà)車輛動(dòng)態(tài)調(diào)度問(wèn)題，定義Nt表示時(shí)刻t對(duì)應(yīng)的時(shí)空節(jié)點(diǎn)集合。定義Et為時(shí)刻t對(duì)應(yīng)的時(shí)空弧集合，包括時(shí)刻t的訂單對(duì)應(yīng)的服務(wù)弧以及在時(shí)刻t出發(fā)的移位弧和等待弧。由于未來(lái)時(shí)刻的空閑車輛可用于連續(xù)派單，Et不僅包括所有Nt內(nèi)節(jié)點(diǎn)出發(fā)的時(shí)空弧，也可能包括未來(lái)時(shí)刻對(duì)應(yīng)時(shí)空節(jié)點(diǎn)出發(fā)的服務(wù)弧。外，當(dāng)前處于位置i的空閑車輛可被空駛調(diào)度至位置s與j，表示為移位弧e6與e7；也可原地空閑等待，表示為等待弧e8。對(duì)于任意時(shí)空節(jié)點(diǎn)n，由該

2 模型構(gòu)建

將每時(shí)刻視為一個(gè)階段，車輛動(dòng)態(tài)調(diào)度問(wèn)題本質(zhì)上是一個(gè)多階段隨機(jī)優(yōu)化問(wèn)題?？刹捎民R爾科夫決策框架對(duì)問(wèn)題進(jìn)行建模[14]。模型框架主要包括5 部分要素：狀態(tài)變量、外界信息、決策變量、狀態(tài)轉(zhuǎn)移方程與目標(biāo)函數(shù)。

(1)狀態(tài)變量

由于車輛在載客狀態(tài)下不能接受乘客訂單與空車移位，車輛狀態(tài)定義為車輛最早處于空閑狀態(tài)的時(shí)刻與位置。在當(dāng)前時(shí)刻t，若車輛處于空閑狀態(tài)，則狀態(tài)變量刻畫(huà)此時(shí)的車輛位置。若車輛在時(shí)刻t處于載客狀態(tài)，狀態(tài)變量不刻畫(huà)其當(dāng)前時(shí)刻位置，而刻畫(huà)其載客結(jié)束后的時(shí)刻與位置?；跁r(shí)空網(wǎng)絡(luò)，可用時(shí)空節(jié)點(diǎn)n=(s,k)的車輛流量表征狀態(tài)變量。表示根據(jù)時(shí)刻t信息，最早在時(shí)刻k空閑且處于位置s的車輛數(shù)。

(2)外界信息

在SAV系統(tǒng)中，中央控制端在各個(gè)時(shí)刻更新乘客的訂單信息。在時(shí)刻t，訂單信息表示為訂單(i,j,t)的需求數(shù)。

(3)決策變量

在時(shí)刻t，系統(tǒng)需為當(dāng)前訂單指派車輛并對(duì)當(dāng)前空閑車輛進(jìn)行空車調(diào)度?；跁r(shí)空網(wǎng)絡(luò)，車輛調(diào)度行為可用集合Et內(nèi)的時(shí)空弧表征。弧流量表示在時(shí)刻t按調(diào)度行為e∈Et執(zhí)行的車輛數(shù)。

式(1)表示對(duì)于當(dāng)前訂單(i,j,t)，調(diào)度行為必須不超過(guò)訂單的需求數(shù)。約束取小于意味著該訂單中的部分需求被拒絕，未被派車的乘客將離開(kāi)系統(tǒng)。值得注意的是，針對(duì)當(dāng)前訂單，可指派未來(lái)時(shí)刻的空閑車輛。式(2)為當(dāng)前時(shí)刻的流平衡約束。在當(dāng)前時(shí)刻節(jié)點(diǎn)n∈Nt的空閑車輛必須被全部調(diào)度(執(zhí)行訂單、空車移位或空車等待)以進(jìn)入下一時(shí)刻。式(3)為未來(lái)時(shí)刻的流量限制約束。未來(lái)時(shí)刻的空閑車輛可用于連續(xù)派單。在未來(lái)時(shí)刻k(k ＞t)的節(jié)點(diǎn)n∈Nk，必須有足夠的車輛數(shù)才可執(zhí)行連續(xù)派單。

(4)狀態(tài)轉(zhuǎn)移方程

狀態(tài)轉(zhuǎn)移方程刻畫(huà)系統(tǒng)從時(shí)刻t至t+1 的狀態(tài)變化。由于車輛的行駛時(shí)間固定，可根據(jù)時(shí)刻t的狀態(tài)與決策行為對(duì)時(shí)刻t+1的系統(tǒng)狀態(tài)進(jìn)行估計(jì)。

式(4)表示時(shí)刻t+1狀態(tài)中，在時(shí)空節(jié)點(diǎn)n的空閑車輛數(shù)等于在時(shí)刻t已知空閑的車輛數(shù)加上決策后新增的空閑車輛數(shù)，以及減去決策后減少的空閑車輛數(shù)。

(5)目標(biāo)函數(shù)

車輛動(dòng)態(tài)調(diào)度的主要目標(biāo)是最大化系統(tǒng)凈收益。時(shí)刻t決策所產(chǎn)生的收益包括完成乘客訂單服務(wù)的收益減去空車移位的成本，即

在研究時(shí)間段內(nèi)，問(wèn)題目標(biāo)是使凈收益總和的期望最大化，即

車輛動(dòng)態(tài)調(diào)度問(wèn)題既需要考慮當(dāng)前時(shí)刻收益，也需要平衡調(diào)度方案對(duì)未來(lái)運(yùn)營(yíng)的影響。根據(jù)Bellman 最優(yōu)原理，時(shí)刻t的決策需使當(dāng)前時(shí)刻收益與未來(lái)收益期望值之和最大化。該問(wèn)題遞推表達(dá)式為

值得注意的是，對(duì)于一個(gè)訂單而言，當(dāng)既可指派給當(dāng)前空閑車輛，也可連續(xù)派單給未來(lái)空閑車輛時(shí)，應(yīng)優(yōu)先指派當(dāng)前空閑車輛。從乘客角度，可減少乘客的等待時(shí)間；從運(yùn)營(yíng)角度，有利于當(dāng)前空閑車輛的使用，提高車輛的利用率。因此，系統(tǒng)決策可在凈收益最大化基礎(chǔ)上增加第2目標(biāo)，即最小化乘客等待時(shí)間。

式中：ε為一個(gè)很小的權(quán)重系數(shù)，用于平衡首要目標(biāo)與次要目標(biāo)[15]。

3 基于滾動(dòng)時(shí)域的隨機(jī)規(guī)劃方法

由于系統(tǒng)未來(lái)訂單信息的隨機(jī)性，式(7)中期望值難以通過(guò)數(shù)學(xué)表達(dá)式精確刻畫(huà)?；跐L動(dòng)時(shí)域優(yōu)化思想[14]，本文滾動(dòng)建立前視(Lookahead)時(shí)間窗，利用歷史樣本數(shù)據(jù)作為未來(lái)訂單信息的估計(jì)，建立隨機(jī)規(guī)劃模型，以輔助當(dāng)前時(shí)刻決策。

假設(shè)時(shí)間窗長(zhǎng)度設(shè)h，時(shí)刻t的前視時(shí)間窗為。為考慮未來(lái)訂單信息，根據(jù)歷史數(shù)據(jù)生成樣本集Ω。每個(gè)樣本ω∈Ω提供未來(lái)時(shí)刻t′∈Ht的乘客訂單需求作為輸入。滾動(dòng)時(shí)域框架下，系統(tǒng)在時(shí)刻t對(duì)整個(gè)時(shí)間窗內(nèi)的車輛調(diào)度決策進(jìn)行優(yōu)化。既確定當(dāng)前時(shí)刻t所對(duì)應(yīng)的時(shí)空弧e∈Et的流量，也確定未來(lái)時(shí)刻t′∈Ht對(duì)應(yīng)的時(shí)空弧e∈Et′的流量。決策變量為，后者表示在時(shí)間t根據(jù)樣本ω決策下的時(shí)空弧e∈Et′的流量。只有e∈Et的決策結(jié)果被執(zhí)行，e∈Et′的決策結(jié)果不被采用。

基于滾動(dòng)時(shí)域優(yōu)化，建立時(shí)刻t的隨機(jī)規(guī)劃模型為

目標(biāo)函數(shù)式(9)既包括最大化當(dāng)前收益，也包括在各樣本訂單信息下未來(lái)時(shí)刻的平均收益，第2項(xiàng)可理解為式(7)中未來(lái)收益期望值的近似，為提升車輛調(diào)度決策效果，增加了第2目標(biāo)最小化乘客等待時(shí)間。式(10)表示當(dāng)前訂單(i,j,t)的派單調(diào)度不超過(guò)訂單的需求數(shù)。式(11)表示對(duì)于樣本ω∈Ω，時(shí)間窗內(nèi)訂單(i,j,t′)的派單調(diào)度不超過(guò)訂單的需求數(shù)。式(12)為當(dāng)前時(shí)刻t的車輛流平衡約束。式(13)為時(shí)間窗內(nèi)未來(lái)時(shí)刻t′∈Ht的車輛流平衡約束，其中，等式左邊為從時(shí)空節(jié)點(diǎn)n出發(fā)的車輛數(shù)；等式右邊第1項(xiàng)為時(shí)刻t已知在時(shí)空節(jié)點(diǎn)n的車輛數(shù)，等式右邊第2 和第3項(xiàng)為到達(dá)時(shí)空節(jié)點(diǎn)n的車輛數(shù)。式(14)為時(shí)間窗后未來(lái)時(shí)刻的車輛流量限制約束。式(15)表示決策變量為整數(shù)。由于的決策結(jié)果不被采用，可采用連續(xù)變量以加快模型求解速度。該隨機(jī)規(guī)劃模型為混合整數(shù)線性規(guī)劃模型，可用CPLEX等商業(yè)求解器直接求解。模型規(guī)模受時(shí)間窗長(zhǎng)度與樣本數(shù)量決定。

利用隨機(jī)規(guī)劃模型求解得到調(diào)度行為e∈Et的結(jié)果后，通過(guò)狀態(tài)轉(zhuǎn)移方程更新系統(tǒng)狀態(tài)，即可進(jìn)入下一時(shí)刻，并以此往復(fù)。

4 算例分析

4.1 基礎(chǔ)數(shù)據(jù)

本文以Sioux Falls標(biāo)準(zhǔn)網(wǎng)絡(luò)[16]為例驗(yàn)證所建立的模型與方法。網(wǎng)絡(luò)包括24 個(gè)位置點(diǎn)和76 條弧段。位置點(diǎn)間行駛時(shí)間采用自由流時(shí)間。算例以3 h 為研究時(shí)段，以1 min 為時(shí)間間隔。在初始時(shí)刻，各位置點(diǎn)均有8輛空閑車輛。時(shí)段內(nèi)兩點(diǎn)間訂單平均需求設(shè)為路網(wǎng)OD 出行量的1/100。時(shí)段內(nèi)訂單總需求約為3600。網(wǎng)絡(luò)如圖2所示。

圖2 Sioux Falls網(wǎng)絡(luò)[16]Fig.2 Sioux Falls network

在研究時(shí)段內(nèi)，兩點(diǎn)間雙方向的總需求呈對(duì)稱分布。為模擬實(shí)際需求在早晚高峰時(shí)段的空間不對(duì)稱性，在各小時(shí)內(nèi)兩點(diǎn)間雙方向需求呈非對(duì)稱分布。在第1 小時(shí)，主方向?yàn)镾1～S12 去往S13～S24；在第3 小時(shí)，主方向?yàn)镾13～S24 回到S1～S12。因此，第1小時(shí)起點(diǎn)在S1～S12和終點(diǎn)在S13～S24的訂單數(shù)多于起點(diǎn)在S13～S24 和終點(diǎn)在S1～S12 的訂單；在第2小時(shí)，雙方向之間出行訂單數(shù)量相同；在第3小時(shí)，起點(diǎn)在S1～S12和終點(diǎn)在S13～S24的訂單數(shù)少于起點(diǎn)在S13～S24 和終點(diǎn)在S1～S12 的訂單。兩點(diǎn)間分小時(shí)出行需求比例如表1所示。

表1 兩地點(diǎn)間分小時(shí)需求比例Table 1 Percentage of trip demand of three hours for each OD pair

為模擬訂單需求的隨機(jī)性，假設(shè)各時(shí)刻兩點(diǎn)間的訂單需求服從泊松分布，生成20 組數(shù)據(jù)樣本。其中，10組為測(cè)試樣本，作為當(dāng)前訂單信息的輸入，用于測(cè)試算法效果；另外10組為歷史樣本，作為滾動(dòng)時(shí)域優(yōu)化的輸入。訂單服務(wù)價(jià)格為2.5元·min-1，空車移位成本為1 元·min-1，乘客可等待時(shí)間設(shè)為4 min。

4.2 滾動(dòng)時(shí)域方法測(cè)試

為測(cè)試滾動(dòng)時(shí)域方法效果，分析有和無(wú)滾動(dòng)時(shí)域優(yōu)化情形下的系統(tǒng)凈收益。首先，不采用滾動(dòng)時(shí)域優(yōu)化，時(shí)間窗長(zhǎng)度設(shè)為0(只考慮當(dāng)前訂單信息)，進(jìn)行車輛調(diào)度決策；然后，采用滾動(dòng)時(shí)域優(yōu)化，對(duì)比車輛調(diào)度結(jié)果下的系統(tǒng)凈收益。時(shí)間窗長(zhǎng)度與樣本集規(guī)模是影響滾動(dòng)時(shí)域方法的關(guān)鍵，因此，設(shè)置不同的時(shí)間窗長(zhǎng)度與樣本集規(guī)模。針對(duì)10組測(cè)試樣本，以采用滾動(dòng)時(shí)域優(yōu)化后SAV系統(tǒng)收益的提升比例為優(yōu)化率，其結(jié)果如圖3所示。這里隨機(jī)規(guī)劃模型均設(shè)置最小化乘客等待時(shí)間為第2目標(biāo)。

圖3 滾動(dòng)時(shí)域方法優(yōu)化率Fig.3 Optimization results of rolling horizon method

如圖3所示，相較于無(wú)滾動(dòng)時(shí)域優(yōu)化，采用滾動(dòng)時(shí)域優(yōu)化方法后，優(yōu)化率均為正值。意味著系統(tǒng)凈收益均有所提高，滾動(dòng)時(shí)域優(yōu)化方法可提升車輛調(diào)度決策效果。在給定樣本規(guī)模下，時(shí)間窗長(zhǎng)度越長(zhǎng)，優(yōu)化率呈上升趨勢(shì)。這是因?yàn)殡S機(jī)規(guī)劃模型可以考慮未來(lái)更長(zhǎng)時(shí)間的影響。但隨著時(shí)間窗長(zhǎng)度的延長(zhǎng)，優(yōu)化率的上升有所減緩。另外，在樣本規(guī)模較大時(shí)，延長(zhǎng)時(shí)間窗長(zhǎng)度可更加明顯地提升優(yōu)化率。在樣本規(guī)模較小時(shí)，例如，只采用1 個(gè)樣本，延長(zhǎng)時(shí)間窗長(zhǎng)度并未明顯提高優(yōu)化率。因此，滾動(dòng)時(shí)域優(yōu)化方法需要使用一定的樣本量以保證優(yōu)化效果。

在相同的時(shí)間窗長(zhǎng)度下，隨著樣本規(guī)模的增加，優(yōu)化率總體呈上升趨勢(shì)。這是因?yàn)闃颖驹蕉?，未?lái)收益期望值的近似誤差越小。但優(yōu)化率的上升隨樣本規(guī)模的增加而有所減緩。另外，當(dāng)時(shí)間窗長(zhǎng)度較短時(shí)(例如，時(shí)間窗長(zhǎng)度為6)，增加樣本規(guī)模(例如，樣本規(guī)模從3 增加到10)優(yōu)化率上升不明顯。而當(dāng)時(shí)間窗長(zhǎng)度較長(zhǎng)時(shí)(例如，時(shí)間窗長(zhǎng)度為12)，增加樣本規(guī)?？筛佑行У靥嵘凉L動(dòng)時(shí)域方法。

在計(jì)算時(shí)間方面，當(dāng)不采用滾動(dòng)時(shí)域優(yōu)化時(shí)，每次決策所需時(shí)間約為0.01 s。而采取滾動(dòng)時(shí)域優(yōu)化時(shí)，所需的計(jì)算時(shí)間更長(zhǎng)，如圖4所示。

圖4 滾動(dòng)時(shí)域方法求解時(shí)間Fig.4 Computational time of rolling horizon method

由圖4可知，時(shí)間窗長(zhǎng)度越長(zhǎng)，樣本規(guī)模越大，隨機(jī)規(guī)劃模型所需要的求解時(shí)間也越長(zhǎng)。在時(shí)間窗長(zhǎng)度為12和樣本規(guī)模為3時(shí)，每次決策的求解時(shí)間為0.77 s。當(dāng)時(shí)間窗長(zhǎng)度提升為18 或樣本規(guī)模提升為5時(shí)，決策所需時(shí)間將超過(guò)1 s。

綜合考慮優(yōu)化效果與計(jì)算時(shí)間可以發(fā)現(xiàn)，在保證一定的樣本規(guī)模和時(shí)間窗長(zhǎng)度后，延長(zhǎng)時(shí)間窗長(zhǎng)度比增加樣本規(guī)模效果更好。因此，為控制隨機(jī)規(guī)劃模型的求解時(shí)間，可采用長(zhǎng)時(shí)間窗和中等樣本規(guī)模。

4.3 車輛調(diào)度運(yùn)營(yíng)結(jié)果

以時(shí)間窗長(zhǎng)度為12，樣本規(guī)模為3 為例，采用滾動(dòng)時(shí)域優(yōu)化后的車輛調(diào)度運(yùn)營(yíng)結(jié)果指標(biāo)如表2所示。其中，訂單服務(wù)率為被服務(wù)的訂單占訂單需求的百分比，車輛利用率為車輛處于載客運(yùn)行的時(shí)長(zhǎng)百分比。

表2 車輛調(diào)度運(yùn)營(yíng)結(jié)果Table 2 Operational performance of SAV fleet management

與無(wú)滾動(dòng)時(shí)域優(yōu)化對(duì)比，當(dāng)采取滾動(dòng)時(shí)域優(yōu)化后，運(yùn)營(yíng)收益提高了5.38%，車輛的利用率與訂單的服務(wù)率均有所提升。結(jié)果表明，采用滾動(dòng)時(shí)域優(yōu)化進(jìn)行車輛調(diào)度，既提高了系統(tǒng)的運(yùn)營(yíng)效率，也保證了乘客的出行。從空車移位次數(shù)明顯增加可以看出，系統(tǒng)根據(jù)歷史訂單信息采取了合理的空車移位策略，使得系統(tǒng)運(yùn)營(yíng)效率提升。乘客等待時(shí)間略微上升，主要是因?yàn)橄到y(tǒng)車輛需要服務(wù)更多的訂單，使乘客出現(xiàn)了更多地等待。

為測(cè)試隨機(jī)規(guī)劃模型中第2 目標(biāo)對(duì)系統(tǒng)車輛調(diào)度的影響效果，在目標(biāo)函數(shù)中不考慮最小化乘客等待時(shí)間，僅考慮最大化系統(tǒng)凈收益。其車輛調(diào)度運(yùn)營(yíng)結(jié)果如表3所示。

表3 車輛調(diào)度運(yùn)營(yíng)結(jié)果(不最小化乘客等待時(shí)間)Table 3 Performance of fleet management(without minimizing passenger waiting time)

對(duì)比表2 和表3 可知，將最小化乘客等待時(shí)間設(shè)為第2 目標(biāo)，可有效減少乘客等待時(shí)間。同時(shí)，系統(tǒng)凈收益、訂單服務(wù)率與車輛利用率等指標(biāo)也同步提升。在車輛動(dòng)態(tài)調(diào)度問(wèn)題中，若目標(biāo)函數(shù)只考慮最大化系統(tǒng)凈收益，僅能保證當(dāng)前時(shí)刻凈收益最大，會(huì)忽略車輛調(diào)度結(jié)果對(duì)未來(lái)運(yùn)營(yíng)的影響。因此，進(jìn)一步考慮乘客等待時(shí)間非常必要。

4.4 連續(xù)派單影響

為測(cè)試連續(xù)派單對(duì)系統(tǒng)運(yùn)營(yíng)調(diào)度的影響，假設(shè)不采取連續(xù)派單模式。系統(tǒng)只將訂單指派給當(dāng)前空閑車輛，即第1類與第2類車輛，不能指派給當(dāng)前未結(jié)束服務(wù)的車輛。采用滾動(dòng)時(shí)域優(yōu)化方法，車輛調(diào)度運(yùn)營(yíng)結(jié)果如表4所示。

表4 無(wú)連續(xù)派單下的車輛調(diào)度運(yùn)營(yíng)結(jié)果Table 4 Performance of fleet management without continue assignment

由表4 可知，在無(wú)連續(xù)派單情況下，系統(tǒng)收益下降達(dá)7.22%。由于未結(jié)束服務(wù)的車輛不能夠接單，車輛利用率由80.63%降至75.71%，乘客訂單也更難被服務(wù)，訂單服務(wù)率由86.91%降至78.97%。由于乘客均由當(dāng)前空閑車輛服務(wù)，其等待時(shí)間減短至0.68 min。由于車輛可被使用的機(jī)會(huì)下降，空車移位次數(shù)也相應(yīng)減少。

4.5 乘客可等待時(shí)間影響

為測(cè)試乘客可等待時(shí)間對(duì)系統(tǒng)運(yùn)營(yíng)的影響，假設(shè)乘客可等待時(shí)間為0 min或2 min，車輛調(diào)度運(yùn)營(yíng)結(jié)果如表5所示。

表5 不同乘客可等待時(shí)間下的車輛調(diào)度運(yùn)營(yíng)結(jié)果Table 5 Performance of fleet management without maximum waiting time

當(dāng)乘客可等待時(shí)間為0時(shí)，乘客訂單只能分配給處于起點(diǎn)位置的空閑車輛，車輛利用率降為71.21%，訂單服務(wù)率也降為74.35%，系統(tǒng)運(yùn)營(yíng)收益下降了10.4%。由于可服務(wù)的訂單更少，空車移位次數(shù)也更少。當(dāng)乘客可等待時(shí)間為2 min 時(shí)，系統(tǒng)運(yùn)營(yíng)收益和車輛利用率與訂單服務(wù)率相比可等待時(shí)間為0 時(shí)均有所上升?？哲囈莆淮螖?shù)甚至相比乘客可等待時(shí)間為4 min時(shí)更多。這是因?yàn)槌丝涂傻却龝r(shí)間為4 min 時(shí)，系統(tǒng)不需要空車移位也可以保證訂單服務(wù)率。

5 結(jié)論

本文通過(guò)構(gòu)造SAV 車輛調(diào)度時(shí)空網(wǎng)絡(luò)，分別針對(duì)訂單分配與空車移位生成對(duì)應(yīng)的車輛運(yùn)行時(shí)空弧，建立了車輛動(dòng)態(tài)調(diào)度的馬爾科夫決策模型，并針對(duì)模型設(shè)計(jì)了基于滾動(dòng)時(shí)域優(yōu)化的隨機(jī)規(guī)劃方法。

Sioux Falls 網(wǎng)絡(luò)算例結(jié)果表明，采用滾動(dòng)時(shí)域優(yōu)化方法比不采用滾動(dòng)時(shí)域優(yōu)化方法的車輛調(diào)度決策效果更好。時(shí)間窗長(zhǎng)度越長(zhǎng)，樣本規(guī)模越大，滾動(dòng)時(shí)域方法的優(yōu)化效果越顯著；但因計(jì)算時(shí)間限制，應(yīng)優(yōu)先采用長(zhǎng)時(shí)間窗中等規(guī)模樣本。采用滾動(dòng)時(shí)域優(yōu)化方法時(shí)，在最大化系統(tǒng)收益的同時(shí)進(jìn)一步最小化乘客等待時(shí)間，既可提高運(yùn)營(yíng)商收益，也可以降低乘客等待時(shí)間。采用連續(xù)派單方式可明顯提高系統(tǒng)運(yùn)營(yíng)效率，車輛利用率和訂單服務(wù)率均得到大幅提升。乘客可等待時(shí)間對(duì)系統(tǒng)運(yùn)營(yíng)有顯著影響，乘客可等待時(shí)間越長(zhǎng)，系統(tǒng)運(yùn)營(yíng)收益越大，有必要在車輛調(diào)度過(guò)程中考慮乘客可等待時(shí)間。