喬翔宇， 戴榮健， 高 劍， 丁 川

(1.交通運(yùn)輸部公路科學(xué)研究所，智能交通技術(shù)交通運(yùn)輸行業(yè)重點(diǎn)實(shí)驗(yàn)室， 北京 100088;2.北京航空航天大學(xué)，交通科學(xué)與工程學(xué)院， 北京 100191)

0 引言

智能化、網(wǎng)聯(lián)化、協(xié)同化和共享化是智能交通發(fā)展的重要趨勢(shì)，自動(dòng)駕駛技術(shù)從實(shí)驗(yàn)室走向?qū)嶋H應(yīng)用的步伐正在加快. 根據(jù)各大車企的研發(fā)計(jì)劃，2020年全球?qū)⒂瓉?lái)自動(dòng)駕駛汽車的爆發(fā)期[1]，自動(dòng)駕駛汽車的全面普及將給人們的日常生產(chǎn)生活帶來(lái)根本性的轉(zhuǎn)變. 共享出行模式和網(wǎng)聯(lián)車的出現(xiàn)促進(jìn)了對(duì)車輛集群出行的研究. Fagnant等[2]通過(guò)交通仿真發(fā)現(xiàn)每輛共享模式下的自動(dòng)駕駛車輛可替代11輛傳統(tǒng)汽車出行，但增加了10%的出行距離，Chen等[3]報(bào)告了每一輛共享自動(dòng)駕駛車輛可替代3.7輛私人車輛，其中包括具有與私人車輛每英里成本相當(dāng)?shù)碾妱?dòng)共享自動(dòng)駕駛車輛. 而當(dāng)模擬擴(kuò)展到低市場(chǎng)滲透率情景時(shí)每輛車能取代9輛傳統(tǒng)車輛[4]. 麻省理工學(xué)院 Senseable City Lab主任Carlo Ratti主導(dǎo)的一項(xiàng)新研究[5]表明，如果人類司機(jī)被自動(dòng)駕駛?cè)〈?，城市中的出租車?shù)量將減少一半. 這項(xiàng)研究指出，如果自動(dòng)駕駛汽車由算法調(diào)度，那么只需一半的車輛便能完成相同的旅客運(yùn)輸量. 因此，對(duì)基于共享模式的網(wǎng)聯(lián)自動(dòng)駕駛車輛的出行研究具有重要的現(xiàn)實(shí)意義.

對(duì)于傳統(tǒng)駕駛共享出行， Kumar 等[6-7]等通過(guò)建立離散整數(shù)規(guī)劃模型來(lái)解決車輛共享站的位置問(wèn)題. Kornhauser[8]探究了預(yù)約共享模式對(duì)于新澤西州人出行體驗(yàn)的動(dòng)態(tài)影響. Cepolina等[9]著重研究了傳統(tǒng)共享汽車的車輛規(guī)模問(wèn)題并探討各站點(diǎn)間的車輛分配. Mahmoudi等[10]使用基于狀態(tài)- 空間- 時(shí)間網(wǎng)絡(luò)表示的動(dòng)態(tài)編程方法，研究了具有時(shí)間窗的拾取和遞送服務(wù)的車輛路徑問(wèn)題. Fan等[11-12]提出以系統(tǒng)收益最大為目標(biāo)的車輛動(dòng)態(tài)分配模型. 模型假設(shè)共享汽車的車輛數(shù)、站點(diǎn)數(shù)量、位置以及用戶需求是提前已知的，并采用基于模特卡洛的隨機(jī)優(yōu)化方法對(duì)這類問(wèn)題進(jìn)行求解. 對(duì)于自動(dòng)駕駛共享出行，F(xiàn)ord[13]研究了共享自動(dòng)出租車的最佳定位問(wèn)題，可根據(jù)更多潛在需求選取更有利的位置并重新定位，從而幫助車輛收益最大. Levin[14]研究了擁堵場(chǎng)景下的共享自動(dòng)車輛的最短路徑規(guī)劃問(wèn)題，通過(guò)建立擁塞感知模型，對(duì)系統(tǒng)最優(yōu)流量進(jìn)行了分配，以降低路網(wǎng)擁堵. 然而，此模型未考慮用戶個(gè)人出行時(shí)間需求. Ma等[15]研究了無(wú)人駕駛分時(shí)租賃系統(tǒng)，該系統(tǒng)考慮了單層和多層時(shí)間模型，可根據(jù)不同用戶需求派送無(wú)人車按用戶需求準(zhǔn)時(shí)接送乘客. Fassi等[16]提出一種評(píng)估分時(shí)租賃系統(tǒng)運(yùn)營(yíng)效率的方法，期望通過(guò)最少的車輛最大限度地滿足用戶的需求，然而該方法忽略了異地還車的運(yùn)營(yíng)模式，存在一定的局限性. Wang等[17]提出了一種基于排隊(duì)論的共享全自動(dòng)車輛動(dòng)態(tài)車隊(duì)管理算法，并給予模擬環(huán)境進(jìn)行了算法演示.

對(duì)于傳統(tǒng)駕駛共享出行，以往研究集中于車輛共享站的選址、預(yù)約調(diào)度以及物流車輛最優(yōu)調(diào)度問(wèn)題. 對(duì)于自動(dòng)駕駛共享出行中的自動(dòng)出租車的最佳定位問(wèn)題、最短路徑問(wèn)題以及如何建立無(wú)人駕駛分時(shí)租賃系統(tǒng)是學(xué)界的研究熱點(diǎn). 總體而言，已有的研究多以靜態(tài)需求出行為主，多考慮車輛提前預(yù)約，對(duì)自動(dòng)駕駛和共享模式的單獨(dú)對(duì)象研究較多，缺少聯(lián)合研究. 在網(wǎng)聯(lián)自動(dòng)駕駛環(huán)境下，本研究綜合考慮用戶出行等待時(shí)間以及能耗出行成本，對(duì)共享自動(dòng)駕駛車輛規(guī)模及行駛路徑進(jìn)行建模與優(yōu)化，具有理論與現(xiàn)實(shí)意義.

1 模型假設(shè)

為了更直觀的觀察共享汽車的服務(wù)過(guò)程，本研究搭建了汽車共享網(wǎng)絡(luò)，如圖1所示. 在一定區(qū)域內(nèi)，現(xiàn)假設(shè)用戶出行需求已知，需求編號(hào)為i，其中i∈I. 出行需求的起訖點(diǎn)作為網(wǎng)絡(luò)中的節(jié)點(diǎn)，需求i的出發(fā)節(jié)點(diǎn)為i-，到達(dá)節(jié)點(diǎn)為i+，且i-∈I-，i+∈I+，同時(shí)設(shè)置了一個(gè)虛擬出發(fā)節(jié)點(diǎn)o和一個(gè)虛擬回收節(jié)點(diǎn)d，網(wǎng)絡(luò)中所有節(jié)點(diǎn)集合為N={I+,I-,o,d}. 節(jié)點(diǎn)之間的連接表示共享汽車的服務(wù)路徑，參考Ma等[15]的研究，根據(jù)路徑功能的不同可將車輛的行駛路徑分為5類：分配路徑，服務(wù)路徑，重新定位路徑，回收路徑和虛擬路徑，因此網(wǎng)絡(luò)中路徑的集合為式(1)：

A={(i-,i+)}i∈I∪{(i+,j-)}i,j∈I∪
{(o,i-)}i∈I∪{(i+,d)}j∈I∪{(o,d)}

(1)

各類路徑的功能如下：①分配路徑(o,i-)：每輛進(jìn)行服務(wù)的網(wǎng)聯(lián)自動(dòng)駕駛車輛都要通過(guò)此路徑到達(dá)所服務(wù)的第一個(gè)需求所在出發(fā)點(diǎn)；②服務(wù)路徑(i-,i+)：網(wǎng)聯(lián)自動(dòng)駕駛車輛通過(guò)此路徑服務(wù)每個(gè)需求；③重新定位路徑(i+,j-)：參與服務(wù)的網(wǎng)聯(lián)自動(dòng)駕駛車輛在服務(wù)完上一次出行需求后通過(guò)此路徑到達(dá)下一個(gè)需求的出發(fā)點(diǎn)；④回收路徑(i+,d)：參與服務(wù)的網(wǎng)聯(lián)自動(dòng)駕駛車輛在服務(wù)完所有需求后通過(guò)此路徑回到虛擬回收節(jié)點(diǎn)；⑤虛擬路徑(o,d)：不參與服務(wù)的網(wǎng)聯(lián)自動(dòng)駕駛車輛都將通過(guò)此路徑從虛擬出發(fā)節(jié)點(diǎn)到達(dá)虛擬回收節(jié)點(diǎn).

假設(shè)有3個(gè)出行需求1-→1+，2-→2+，3-→3+，在個(gè)體最優(yōu)的情況下，將派3輛車分別服務(wù)3個(gè)用戶，用戶不用等待，出行體驗(yàn)最佳. 為達(dá)到系統(tǒng)出行最優(yōu)的條件，可先分配一輛車服務(wù)需求1的用戶，服務(wù)完成后重新定位從而服務(wù)需求2用戶，此時(shí)需求2的用戶可能需要在可接受的范圍內(nèi)等待一段時(shí)間，此情景下系統(tǒng)所需服務(wù)車輛規(guī)模減少，降低了交通出行能耗.

圖1 汽車共享網(wǎng)絡(luò)

服務(wù)車輛通過(guò)分配路徑到達(dá)用戶出發(fā)點(diǎn)，使用服務(wù)路徑完成出行需求的服務(wù)，并在之后經(jīng)過(guò)重新定位路徑到達(dá)下一個(gè)用戶出發(fā)點(diǎn)服務(wù)下一個(gè)出行需求，最終通過(guò)回收路徑到達(dá)虛擬回收點(diǎn)d，而未服務(wù)車輛將直接通過(guò)虛擬路徑到達(dá)虛擬回收點(diǎn)d. 本研究出行場(chǎng)景的基本假設(shè)包括：

1)用戶通過(guò)出行需求預(yù)定系統(tǒng)提前預(yù)定出行需求，即所有出行需求是已知的；

2)所有車輛均為自動(dòng)駕駛，不考慮自動(dòng)駕駛與非自動(dòng)駕駛車輛混合行駛；

3)不考慮拼車服務(wù)，即每輛車1次只服務(wù)1個(gè)用戶；

4)所有車輛必須從虛擬出發(fā)點(diǎn)o點(diǎn)出發(fā)，到達(dá)虛擬回收點(diǎn)d點(diǎn).

在共享出行模式下，隨著服務(wù)車輛數(shù)量的增大，用戶出行等待時(shí)間將減小，但同時(shí)出行運(yùn)營(yíng)費(fèi)用會(huì)不斷增加，此研究將考慮車輛服務(wù)成本與出行等待成本之間的內(nèi)在關(guān)聯(lián)，尋求一個(gè)均衡點(diǎn)(如圖2所示)，確定能滿足出行需求的最優(yōu)車輛數(shù)和車輛最優(yōu)路徑，使系統(tǒng)總成本最低. 為了解決此問(wèn)題，將通過(guò)建立模型達(dá)到以下2個(gè)方面的目標(biāo)：考慮運(yùn)營(yíng)成本與用戶等待之間的內(nèi)在關(guān)聯(lián)，確定給定出行需求情況下車輛規(guī)模與服務(wù)路徑；對(duì)比系統(tǒng)最優(yōu)與個(gè)體最優(yōu)的出行油耗成本與運(yùn)營(yíng)成本.

圖2 共享車輛規(guī)模與出行成本關(guān)系

2 模型建立

構(gòu)建的汽車共享網(wǎng)絡(luò)表示了共享車輛所有可能的服務(wù)路徑空間. 為了構(gòu)建汽車服務(wù)路徑的優(yōu)化模型，需要設(shè)定網(wǎng)絡(luò)中路徑的屬性，主要包括路徑的收益、路徑的成本、路徑的容量以及路徑的行程時(shí)間. 除此之外，車輛在重新定位服務(wù)下一個(gè)路徑時(shí)，可能會(huì)造成一定延誤，因此對(duì)于重新定位路徑，還需要確定用戶的等待時(shí)間.

車輛在以上5種路徑中行駛時(shí)會(huì)產(chǎn)生不同的運(yùn)營(yíng)成本費(fèi)用. 每輛進(jìn)行服務(wù)的網(wǎng)聯(lián)自動(dòng)駕駛車輛在分配和回收時(shí)都會(huì)產(chǎn)生固定的運(yùn)營(yíng)費(fèi)用R，包括車輛固定油費(fèi)以及維護(hù)費(fèi)用. 在服務(wù)出行需求和重新定位過(guò)程只會(huì)產(chǎn)生耗油費(fèi)用，通過(guò)虛擬路徑從虛擬出發(fā)節(jié)點(diǎn)直接到達(dá)虛擬回收節(jié)點(diǎn)的未參與服務(wù)的車輛將不產(chǎn)生任何運(yùn)行費(fèi)用. 車輛在行駛過(guò)程中產(chǎn)生的耗油費(fèi)用是跟路徑的行駛距離Dij有關(guān)的，假設(shè)單位距離的耗油費(fèi)用為δ. 同時(shí)，車輛服務(wù)出行需求會(huì)獲取一定的收益，因此車輛只有在使用服務(wù)路徑時(shí)才會(huì)產(chǎn)生收益，該收益與路徑的行駛距離有關(guān)，單位行駛距離的收益為λ，則路徑的收益可由式(2)表示. 相對(duì)于運(yùn)營(yíng)成本費(fèi)用來(lái)說(shuō)，收益應(yīng)該為負(fù)數(shù)，若計(jì)算出運(yùn)營(yíng)成本費(fèi)用為負(fù)值，則表示為運(yùn)營(yíng)收益. 因此，網(wǎng)聯(lián)自動(dòng)駕駛車輛在5種運(yùn)行路徑中產(chǎn)生的運(yùn)營(yíng)成本費(fèi)用cij如式(3)所示.

eij=Dijλ(i,j)∈{(i-,i+)}i∈I

(2)

(3)

為了確定服務(wù)已知需求所需的車輛數(shù)量，本研究建立了虛擬路徑，除虛擬路徑以外，每條路徑的最大車容量都為1輛，表示出行需求只需被服務(wù)1次，而虛擬路徑的最大車容量為車隊(duì)總數(shù)T. 為了滿足所有出行需求，車隊(duì)總數(shù)T可設(shè)置為一個(gè)相對(duì)較大的數(shù)字. 則路徑的最大車容量mij，如式(4)：

(4)

本研究不僅考慮運(yùn)營(yíng)者角度考慮車輛的運(yùn)行成本費(fèi)用，也從出行者角度考慮用戶的出行等待時(shí)間. 假設(shè)車輛在重新定位時(shí)的行駛速度為v(i+,j-)，則車輛在重新定位路徑中行駛的時(shí)間ti+j-為：

(5)

(6)

(7)

xij≤mij, ?(i,j)∈A

(8)

xij≥0,?(i,j)∈A

(9)

(10)

(11)

(12)

式中xij為模型中的決策變量，表示路徑(i,j)上行駛的車輛數(shù). 模型的目標(biāo)函數(shù)為系統(tǒng)總成本最低，即運(yùn)營(yíng)總成本和用戶等待總時(shí)間之和的最小值. 為統(tǒng)一量化成本標(biāo)準(zhǔn)，用戶等待總時(shí)間乘以人均小時(shí)工資α可將其單位轉(zhuǎn)換為元. 此參數(shù)是由地區(qū)GDP、人口、經(jīng)濟(jì)發(fā)展情況等因素決定的. 式(8)表示每條路徑上的最大車流量，式(9)表示每條路徑上的車輛數(shù)為正. 除虛擬路徑以外，所有路徑都最多被一輛網(wǎng)聯(lián)自動(dòng)駕駛車輛占有. 式(10)和(11)表示從o點(diǎn)出發(fā)的車輛總數(shù)和最終到達(dá)d點(diǎn)的車輛總數(shù)都為車隊(duì)總規(guī)模，也就是說(shuō)所有不參與服務(wù)的車輛都將通過(guò)虛擬路徑到達(dá)d點(diǎn). 式(12)是流量平衡約束，即進(jìn)入某節(jié)點(diǎn)的所有車輛等于離開該節(jié)點(diǎn)的所有車輛.

3 算例驗(yàn)證

使用圖3所示的8×8的網(wǎng)格型路網(wǎng)，網(wǎng)格代表實(shí)際道路路段，網(wǎng)絡(luò)中單元格代表實(shí)際距離5 km，出行需求將在網(wǎng)格交叉點(diǎn)處產(chǎn)生，例如在路網(wǎng)中隨機(jī)生成3個(gè)需求的出行路徑如圖3所示. 出行需求信息包括起點(diǎn)和終點(diǎn)位置坐標(biāo)，出發(fā)時(shí)間和到達(dá)時(shí)間，如表1所示. 假設(shè)車輛在路網(wǎng)中兩點(diǎn)之間總是選擇最短路徑出行，那么可得到路徑的行駛距離如式(13)所示，其中O_x為需求起點(diǎn)橫坐標(biāo)，O_y為需求起點(diǎn)縱坐標(biāo)，D_x為需求終點(diǎn)橫坐標(biāo)，D_y為需求終點(diǎn)縱坐標(biāo). 同時(shí)假設(shè)車輛在路網(wǎng)中具有相同的行駛速度v為60 km/h，則路徑的行駛時(shí)間可通過(guò)式(14)得到. 由于未考慮網(wǎng)格型路網(wǎng)中各路徑的交通阻抗，因此車輛在所有路徑上的出行時(shí)間都只與行駛速度有關(guān)，且任意兩點(diǎn)間非繞路出行時(shí)間都是相同的. 在該網(wǎng)格型路網(wǎng)中車輛路徑主要關(guān)注于車輛接送服務(wù)順序.

dij=5×(|D_x-O_x|+|D_y-O_y|)(km)

(13)

tij=dij/v=5×(|D_x-O_x|+|D_y-O_y|)(min)

(14)

圖3 網(wǎng)格型路網(wǎng)

為驗(yàn)證模型的有效性和魯棒性，本研究基于優(yōu)化工具Gurobi對(duì)模型進(jìn)行求解，模擬隨機(jī)需求下路徑規(guī)劃，確定合理的網(wǎng)聯(lián)自動(dòng)駕駛車輛規(guī)模，并與個(gè)體出行路徑最短情況下的能耗進(jìn)行對(duì)比. 基于隨機(jī)數(shù)生成器，在如圖3所示交通網(wǎng)絡(luò)中隨機(jī)生成10個(gè)出行需求，如表1所示.

由于地區(qū)間GDP、人口數(shù)量和經(jīng)濟(jì)發(fā)展情況具有顯著的差異，因此人均小時(shí)工資也不同，本研究選取北京市為例. 據(jù)公布的數(shù)據(jù)顯示，北京市最低小時(shí)工資為24元/h[18]，本研究將根據(jù)此數(shù)據(jù)確定α的值. 根據(jù)我國(guó)油價(jià)標(biāo)準(zhǔn)，本研究將假定單位距離的油耗費(fèi)用δ的值為0.56元/km. 服務(wù)路徑的單位收益λ的取值假定為13元/km，車輛分配和回收時(shí)的固定費(fèi)用R的取值假定為13元/輛，并假設(shè)原始車隊(duì)規(guī)模T為15輛. 基于以上參數(shù)選取假設(shè)，對(duì)表1所示的出行需求案例進(jìn)行求解，得出此場(chǎng)景下的最優(yōu)車輛規(guī)模以及路徑規(guī)劃. 最終模型最優(yōu)解為：參與此次出行服務(wù)總共需要共4輛車，每輛車的行駛路徑見表2以及圖4.

表1 出行需求信息

表2 車輛服務(wù)路徑

圖4 車輛行駛路線

第1輛車將從虛擬出發(fā)點(diǎn)o出發(fā)，首先服務(wù)需求0，在服務(wù)完需求0后，會(huì)在晚于需求2預(yù)定出發(fā)時(shí)間17 min時(shí)到達(dá)需求2的出發(fā)點(diǎn)，服務(wù)完成后最終回到虛擬回收點(diǎn)d；第2輛車將從虛擬出發(fā)點(diǎn)o出發(fā)，首先服務(wù)需求1，在服務(wù)完需求1后，會(huì)提前5 min到達(dá)需求9的出發(fā)點(diǎn)，在服務(wù)完需求9后會(huì)在晚于需求5預(yù)定出發(fā)時(shí)間20 min時(shí)到達(dá)需求5的出發(fā)點(diǎn)，在服務(wù)完需求5后會(huì)在晚于需求4預(yù)定出發(fā)時(shí)間8 min時(shí)到達(dá)需求4的出發(fā)點(diǎn)，服務(wù)完成后最終回到虛擬回收點(diǎn)d；第3輛車將從虛擬出發(fā)點(diǎn)o出發(fā)，首先服務(wù)需求6，在服務(wù)完需求6后將在晚于需求3預(yù)定出行時(shí)間晚12 min到達(dá)3的出發(fā)點(diǎn)，在服務(wù)完需求3后會(huì)在晚于需求8預(yù)定出發(fā)時(shí)間9 min時(shí)到達(dá)需求8的出發(fā)點(diǎn)，服務(wù)完成后最終回到虛擬回收點(diǎn)d；第4輛車只服務(wù)于需求7. 可看出，用戶2、5、4和3分別需要等待17 min、20 min、8 min和12 min，其他用戶會(huì)按照預(yù)訂時(shí)間準(zhǔn)時(shí)出發(fā)，車輛到達(dá)時(shí)間都在用戶可接受范圍內(nèi). 在此場(chǎng)景下，計(jì)算得出所有車輛出行的總能耗量為66l，而系統(tǒng)出行收益為2 490.6元.

表3 系統(tǒng)與個(gè)體最優(yōu)結(jié)果對(duì)比

本研究同時(shí)計(jì)算了個(gè)體最優(yōu)情景下的服務(wù)車輛規(guī)模、總交通能耗量和出行總成本，對(duì)比結(jié)果如表3所示. 相對(duì)于個(gè)體最優(yōu)條件而言，系統(tǒng)最優(yōu)條件下服務(wù)車輛數(shù)減少了6輛，車輛出行總能耗量減少了47l，而總收益增加了411.6元. 由此可見，本研究提出的共享模式下網(wǎng)聯(lián)自動(dòng)駕駛車輛動(dòng)態(tài)路徑規(guī)劃模型能大幅度減少車輛出行規(guī)模，提高自動(dòng)駕駛車輛的使用率，降低車輛出行時(shí)的能耗量以及出行總成本，在節(jié)能減排方面作用顯著.

4 結(jié)論

本文基于共享模式和自動(dòng)駕駛共同發(fā)展的時(shí)代背景，提出了基于共享模式的網(wǎng)聯(lián)自動(dòng)駕駛車輛動(dòng)態(tài)路徑規(guī)劃方法. 在隨機(jī)生成的出行需求下，考慮車輛服務(wù)成本與出行等待成本之間的內(nèi)在關(guān)聯(lián)，利用優(yōu)化工具Gurobi確定能滿足出行需求的車輛數(shù)和最優(yōu)的車輛服務(wù)路徑. 通過(guò)需求案例分析，與個(gè)體最優(yōu)情況下的系統(tǒng)成本及能耗進(jìn)行對(duì)比，驗(yàn)證模型的魯棒性和有效性. 研究結(jié)果表明，模型求解出的出行路徑能在用戶等待時(shí)間可接受范圍內(nèi)大幅度減少車隊(duì)出行規(guī)模，降低系統(tǒng)總體出行能耗，具有節(jié)能減排綠色發(fā)展的可持續(xù)性意義.