基于共享模式的網(wǎng)聯(lián)自動駕駛車輛路徑規(guī)劃研究

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

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

0 引言

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

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

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

1 模型假設(shè)

為了更直觀的觀察共享汽車的服務(wù)過程，本研究搭建了汽車共享網(wǎng)絡(luò)，如圖1所示. 在一定區(qū)域內(nèi)，現(xiàn)假設(shè)用戶出行需求已知，需求編號為i，其中i∈I. 出行需求的起訖點作為網(wǎng)絡(luò)中的節(jié)點，需求i的出發(fā)節(jié)點為i-，到達節(jié)點為i+，且i-∈I-，i+∈I+，同時設(shè)置了一個虛擬出發(fā)節(jié)點o和一個虛擬回收節(jié)點d，網(wǎng)絡(luò)中所有節(jié)點集合為N={I+,I-,o,d}. 節(jié)點之間的連接表示共享汽車的服務(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-)：每輛進行服務(wù)的網(wǎng)聯(lián)自動駕駛車輛都要通過此路徑到達所服務(wù)的第一個需求所在出發(fā)點；②服務(wù)路徑(i-,i+)：網(wǎng)聯(lián)自動駕駛車輛通過此路徑服務(wù)每個需求；③重新定位路徑(i+,j-)：參與服務(wù)的網(wǎng)聯(lián)自動駕駛車輛在服務(wù)完上一次出行需求后通過此路徑到達下一個需求的出發(fā)點；④回收路徑(i+,d)：參與服務(wù)的網(wǎng)聯(lián)自動駕駛車輛在服務(wù)完所有需求后通過此路徑回到虛擬回收節(jié)點；⑤虛擬路徑(o,d)：不參與服務(wù)的網(wǎng)聯(lián)自動駕駛車輛都將通過此路徑從虛擬出發(fā)節(jié)點到達虛擬回收節(jié)點.

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

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

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

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

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

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

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

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

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

2 模型建立

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

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

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

(2)

(3)

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

(4)

本研究不僅考慮運營者角度考慮車輛的運行成本費用，也從出行者角度考慮用戶的出行等待時間. 假設(shè)車輛在重新定位時的行駛速度為v(i+,j-)，則車輛在重新定位路徑中行駛的時間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)總成本最低，即運營總成本和用戶等待總時間之和的最小值. 為統(tǒng)一量化成本標(biāo)準(zhǔn)，用戶等待總時間乘以人均小時工資α可將其單位轉(zhuǎn)換為元. 此參數(shù)是由地區(qū)GDP、人口、經(jīng)濟發(fā)展情況等因素決定的. 式(8)表示每條路徑上的最大車流量，式(9)表示每條路徑上的車輛數(shù)為正. 除虛擬路徑以外，所有路徑都最多被一輛網(wǎng)聯(lián)自動駕駛車輛占有. 式(10)和(11)表示從o點出發(fā)的車輛總數(shù)和最終到達d點的車輛總數(shù)都為車隊總規(guī)模，也就是說所有不參與服務(wù)的車輛都將通過虛擬路徑到達d點. 式(12)是流量平衡約束，即進入某節(jié)點的所有車輛等于離開該節(jié)點的所有車輛.

3 算例驗證

使用圖3所示的8×8的網(wǎng)格型路網(wǎng)，網(wǎng)格代表實際道路路段，網(wǎng)絡(luò)中單元格代表實際距離5 km，出行需求將在網(wǎng)格交叉點處產(chǎn)生，例如在路網(wǎng)中隨機生成3個需求的出行路徑如圖3所示. 出行需求信息包括起點和終點位置坐標(biāo)，出發(fā)時間和到達時間，如表1所示. 假設(shè)車輛在路網(wǎng)中兩點之間總是選擇最短路徑出行，那么可得到路徑的行駛距離如式(13)所示，其中O_x為需求起點橫坐標(biāo)，O_y為需求起點縱坐標(biāo)，D_x為需求終點橫坐標(biāo)，D_y為需求終點縱坐標(biāo). 同時假設(shè)車輛在路網(wǎng)中具有相同的行駛速度v為60 km/h，則路徑的行駛時間可通過式(14)得到. 由于未考慮網(wǎng)格型路網(wǎng)中各路徑的交通阻抗，因此車輛在所有路徑上的出行時間都只與行駛速度有關(guān)，且任意兩點間非繞路出行時間都是相同的. 在該網(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ōu)化工具Gurobi對模型進行求解，模擬隨機需求下路徑規(guī)劃，確定合理的網(wǎng)聯(lián)自動駕駛車輛規(guī)模，并與個體出行路徑最短情況下的能耗進行對比. 基于隨機數(shù)生成器，在如圖3所示交通網(wǎng)絡(luò)中隨機生成10個出行需求，如表1所示.

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

表1 出行需求信息

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

圖4 車輛行駛路線

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

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

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

4 結(jié)論

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