自動(dòng)駕駛汽車(chē)乘客選擇模型研究

程 振,楊 陽(yáng),范德超

(1.中交公路規(guī)劃設(shè)計(jì)院有限公司,北京 100744; 2.北京市市政工程設(shè)計(jì)研究總院有限公司,北京 100082)

0 引言

近年來(lái),許多國(guó)家都在建設(shè)各具特色的智能交通系統(tǒng)(ITS)[1],而智能車(chē)輛系統(tǒng)是智能交通系統(tǒng)的重要組成部分.同時(shí),自主駕駛技術(shù)、環(huán)境感知技術(shù)、車(chē)聯(lián)網(wǎng)技術(shù)的發(fā)展推動(dòng)了智能車(chē)輛系統(tǒng)長(zhǎng)足發(fā)展.盡管等級(jí)5的共享自動(dòng)駕駛汽車(chē)(SAVs)不太可能在不久的將來(lái)出現(xiàn)[2],但預(yù)計(jì)到2030年,美國(guó)95%的車(chē)?yán)锍虒⒂勺詣?dòng)駕駛汽車(chē)、電動(dòng)汽車(chē)、共享汽車(chē)來(lái)完成[3].自動(dòng)駕駛汽車(chē)受歡迎的原因是自動(dòng)駕駛汽車(chē)(AVs)的駕駛行為穩(wěn)定和其具有面向車(chē)聯(lián)網(wǎng)的可擴(kuò)展性,這為實(shí)時(shí)匹配出行需求和動(dòng)態(tài)路徑規(guī)劃給出了有效的技術(shù)支持,而基于出行需求和動(dòng)態(tài)規(guī)劃的自動(dòng)駕駛汽車(chē),其有著明顯的合乘化和共享化應(yīng)用趨勢(shì)[4],因此共享自動(dòng)駕駛汽車(chē)(SAVs)和合乘無(wú)人駕駛汽車(chē)(RAVs)是未來(lái)的發(fā)展趨勢(shì).共享自動(dòng)駕駛汽車(chē)可提供廉價(jià)的出行服務(wù),并且自動(dòng)駕駛技術(shù)可促進(jìn)動(dòng)態(tài)合乘出行(DRS)的發(fā)展[5].為了實(shí)現(xiàn)SAVs和RAVs,Michael W.Levin提出了1個(gè)共享自動(dòng)駕駛汽車(chē)建模的通用框架,此框架基于動(dòng)態(tài)網(wǎng)絡(luò)加載和動(dòng)態(tài)共乘應(yīng)用,旨在實(shí)現(xiàn)共享自動(dòng)駕駛和合乘無(wú)人駕駛[2].另1種實(shí)踐是Michael W.Levin為擁擠感知系統(tǒng)中的共享自動(dòng)駕駛汽車(chē)提出了最優(yōu)路徑選擇.然而,這些模型沒(méi)有考慮自動(dòng)駕駛汽車(chē)的具體應(yīng)用,例如,如何選擇乘客,乘客如何通過(guò)自動(dòng)駕駛汽車(chē)安全、及時(shí)、方便地出行.因此本文研究了自動(dòng)駕駛汽車(chē)共享系統(tǒng)(AVRS).同時(shí)為了解決司乘匹配的問(wèn)題,本文提出了合乘車(chē)輛乘客選擇模型(carpool passenger selected model,CPSM).

合乘問(wèn)題實(shí)質(zhì)是拼車(chē)出行問(wèn)題,該問(wèn)題最早由Psaraftis[6]提出,Psaraftis開(kāi)發(fā)了O(N2)啟發(fā)式來(lái)解決這個(gè)問(wèn)題,由于城市化快速進(jìn)展帶來(lái)的大量交通需求,拼車(chē)出行近年再次成為熱點(diǎn),具有代表性的文獻(xiàn)如下:Mehdi Nourinejad[7]提出了可通過(guò)分散(基于動(dòng)態(tài)分配的多智能體)優(yōu)化算法求解的動(dòng)態(tài)合乘模型,該模型與集中式(二進(jìn)制整數(shù)規(guī)劃)優(yōu)化算法相比具有較低的計(jì)算復(fù)雜度.Stéphane Galland等[8]提出了應(yīng)用多智能體技術(shù)仿真合乘行為模型,并開(kāi)發(fā)了模擬乘客在合乘中過(guò)程中行為相關(guān)應(yīng)用.邵增珍[9]提出了運(yùn)用兩階段聚類(lèi)啟發(fā)式算法求解多車(chē)輛合乘匹配問(wèn)題,該算法提高了乘客和車(chē)輛匹配的成功率.Lauri Hame[10]提出了1種自適應(yīng)插入算法,該算法提出了單車(chē)合乘問(wèn)題的生成時(shí)間約束最優(yōu)解.目前大多數(shù)合乘乘客匹配均沒(méi)有解決匹配后的系統(tǒng)效率問(wèn)題,僅僅考慮了合乘安全、準(zhǔn)時(shí)的基本要求,并無(wú)法滿足乘客對(duì)合乘提出的便捷要求.現(xiàn)有有關(guān)汽車(chē)合乘的研究大多集中在非自動(dòng)駕駛汽車(chē)的合乘上,該合乘模式應(yīng)用于自動(dòng)駕駛汽車(chē)和對(duì)應(yīng)優(yōu)化算法的適應(yīng)性還有待考證.

本文的研究目的是建立1個(gè)自動(dòng)駕駛合乘系統(tǒng)框架,該系統(tǒng)以自動(dòng)駕駛車(chē)輛為基本元素,由控制中心對(duì)車(chē)輛進(jìn)行控制,與ITS系統(tǒng)進(jìn)行信息交互獲取實(shí)時(shí)路況信息,為乘客提供合乘服務(wù).本文提出了應(yīng)用于單個(gè)無(wú)人駕駛汽車(chē)的乘客合乘選擇模型,通過(guò)模型選出時(shí)間窗相互兼容的并且通過(guò)驗(yàn)證的乘客,組成乘客集合,相比其他乘客集合具有更短的合乘行程時(shí)間,為求解該模型,本文提出了1種啟發(fā)式算法.

在本文的其余部分,描述了自動(dòng)駕駛汽車(chē)合乘系統(tǒng)(AVCS)、討論了單車(chē)乘客選擇模型(CPSM)、介紹了1種啟發(fā)式算法,并顯示了數(shù)值實(shí)驗(yàn)和結(jié)果.

1 自動(dòng)駕駛汽車(chē)合乘系統(tǒng)(AVCS)

自動(dòng)駕駛合乘系統(tǒng)是以自動(dòng)駕駛汽車(chē)為主要運(yùn)載工具和決策主體、控制中心提供宏觀和中觀交通信息并適度干預(yù)自動(dòng)駕駛汽車(chē)決策,來(lái)為乘客提供合乘服務(wù)的系統(tǒng).自動(dòng)駕駛汽車(chē)合乘系統(tǒng)共有3個(gè)控制層級(jí),分別為系統(tǒng)總控制中心、區(qū)域控制中心、自動(dòng)駕駛汽車(chē)控制系統(tǒng).圖1展示了自動(dòng)駕駛合乘系統(tǒng)涉及的主要對(duì)象及他們之間的聯(lián)系.總控制中心的作用是與智能交通系統(tǒng)通信、獲取各個(gè)區(qū)域的宏觀交通信息、采集分析區(qū)域控制中心提供的信息,向智能交通系統(tǒng)提供自動(dòng)駕駛合乘系統(tǒng)的匯總信息、處理跨區(qū)域業(yè)務(wù)(比如跨區(qū)域路線規(guī)劃、跨區(qū)域車(chē)輛調(diào)度等).區(qū)域控制中心的作用是直接與自動(dòng)駕駛汽車(chē)控制系統(tǒng)通信提供所需的交通信息、采集自動(dòng)駕駛汽車(chē)獲取的信息、區(qū)域內(nèi)車(chē)輛調(diào)度、與智能交通系統(tǒng)通信獲取本區(qū)域的交通信息.區(qū)域的劃分是根據(jù)系統(tǒng)覆蓋區(qū)域的居民出行需求的特征劃分的,出行需求特征通過(guò)人均出行次數(shù)來(lái)體現(xiàn)[11].自動(dòng)駕駛汽車(chē)是首先與乘客直接通信并提供實(shí)際出行服務(wù)的智能個(gè)體,是該系統(tǒng)的基本的單元,是系統(tǒng)的重要輸入接口之一.通過(guò)自動(dòng)駕駛汽車(chē),系統(tǒng)可獲取乘客出行信息、實(shí)時(shí)的地理信息、實(shí)時(shí)交通分布等外部信息.同時(shí)自動(dòng)駕駛汽車(chē)也是重要的輸出接口之一,自動(dòng)駕駛汽車(chē)執(zhí)行來(lái)自控制中心的指派命令,為乘客輸出實(shí)際的出行服務(wù)和信息.

自動(dòng)駕駛合乘系統(tǒng)的合乘流程如圖2所示,第1位乘客向合乘系統(tǒng)發(fā)出合乘需求,合乘系統(tǒng)首先判斷該乘客的身份,如果乘客信息沒(méi)有記錄在系統(tǒng)數(shù)據(jù)庫(kù)中,系統(tǒng)會(huì)要求乘客先上報(bào)基本信息,基本信息主要包括:確定乘客身份的信息和聯(lián)系方式,如:姓名、年齡、當(dāng)前肖像、電話、或社交軟件賬號(hào)等.當(dāng)乘客具有完整基本信息之后,系統(tǒng)客戶端在獲取乘客當(dāng)前位置信息的同時(shí)會(huì)要求乘客為系統(tǒng)提供行程的終點(diǎn)信息、出發(fā)和到達(dá)時(shí)間、出發(fā)和到達(dá)時(shí)間的可接受間隙,之后根據(jù)時(shí)間順序乘客依次完成上述操作.然后,系統(tǒng)客戶端與最近的自動(dòng)駕駛汽車(chē)通信發(fā)送合乘需求信息,自動(dòng)駕駛汽車(chē)會(huì)使用單車(chē)乘客選擇模型會(huì)判斷該乘客是否適合乘坐該自動(dòng)駕駛汽車(chē),當(dāng)不適合乘坐時(shí),該自動(dòng)駕駛汽車(chē)會(huì)將乘客的信息同時(shí)發(fā)送給乘客所在位置附近的另外1輛自動(dòng)駕駛汽車(chē),如果仍不適合乘坐,第2輛自動(dòng)駕駛汽車(chē)會(huì)將乘客信息傳送到控制中心,由控制中心調(diào)度合適的自動(dòng)駕駛汽車(chē).自動(dòng)駕駛汽車(chē)會(huì)判斷人數(shù)是否滿座,如果滿座或者無(wú)法滿足乘客的時(shí)間需求時(shí),自動(dòng)駕駛汽車(chē)就不再接受新的合乘需求,自動(dòng)駕駛汽車(chē)會(huì)根據(jù)合乘的乘客需求綜合控制中心提供的路網(wǎng)信息規(guī)劃行駛路徑,當(dāng)自動(dòng)駕駛車(chē)輛按照規(guī)劃路徑行駛至最后1個(gè)乘客的終點(diǎn)時(shí),自動(dòng)駕駛合乘系統(tǒng)就完成了1次合乘任務(wù)即自動(dòng)駕駛汽車(chē)的1次合乘任務(wù).

圖2 自動(dòng)駕駛汽車(chē)合乘系統(tǒng)運(yùn)行流程

2 單車(chē)乘客選擇模型(CPSM)

單車(chē)乘客選擇模型是基于自動(dòng)駕駛汽車(chē)的重要模型,當(dāng)呼叫該車(chē)輛的人數(shù)多于車(chē)輛的核載乘客數(shù)時(shí),該模型對(duì)同時(shí)呼叫該自動(dòng)駕駛車(chē)輛的乘客進(jìn)行選擇,選出達(dá)到核載乘客數(shù)的乘客,這些乘客與其他模型選出的乘客相比,搭乘該自動(dòng)駕駛汽車(chē)的總行程時(shí)間最少.這一過(guò)程涉及乘客對(duì)合乘服務(wù)的需求,自動(dòng)駕駛汽車(chē)提供服務(wù)的品質(zhì),道路交通系統(tǒng)交通運(yùn)行的現(xiàn)狀,因此乘客、車(chē)輛和路網(wǎng)是該模型需要分析的3個(gè)要素.乘客主要屬性有:基本社會(huì)屬性,時(shí)間屬性,位置屬性.基本社會(huì)屬性包括:用戶的賬戶,預(yù)留電話,性別,肖像,社會(huì)信譽(yù)等,其中肖像、預(yù)留電話、用戶賬戶,性別等是自動(dòng)駕駛汽車(chē)識(shí)別客戶的依據(jù),社會(huì)信譽(yù)等屬性是判斷用戶是否具有合乘資額的屬性,如果社會(huì)信譽(yù)值較低,用戶將無(wú)法使用自動(dòng)駕駛合乘系統(tǒng).社會(huì)信譽(yù)值包含2部分信譽(yù)值:基礎(chǔ)信譽(yù)值和浮動(dòng)信譽(yù)值.基礎(chǔ)信譽(yù)值由犯罪記錄、銀行個(gè)人信用記錄、社會(huì)糾紛記錄等影響,當(dāng)有以上不良記錄時(shí),基礎(chǔ)信譽(yù)值為0.浮動(dòng)信譽(yù)值由2方面因素影響:付款記錄和同伴評(píng)價(jià),付款記錄指乘客有無(wú)惡意拖欠乘車(chē)費(fèi)用的記錄,同伴評(píng)價(jià)指的是用戶在之前使用合乘系統(tǒng)時(shí),其他與該用戶使用過(guò)同1輛合乘車(chē)的用戶對(duì)該用戶的累計(jì)評(píng)價(jià).設(shè)社會(huì)信譽(yù)值為Sc,基礎(chǔ)信譽(yù)值為Bc,浮動(dòng)信譽(yù)值為Cc,未付款記錄數(shù)為Pr,已有乘車(chē)次數(shù)為Pn,同伴不良評(píng)價(jià)數(shù)為Bp,Sc0為系統(tǒng)設(shè)置的最低社會(huì)信譽(yù)值,社會(huì)信譽(yù)值得計(jì)算方法見(jiàn)式(1)～(3):

(1)

(2)

Sc=Bc-CcSc≥Sc0

(3)

時(shí)間屬性包括出發(fā)時(shí)間窗和到達(dá)時(shí)間窗,時(shí)間窗指某乘客可接受的最早時(shí)刻到最晚時(shí)刻的時(shí)刻集合,車(chē)輛從起點(diǎn)出發(fā)和到達(dá)目的地必須在出發(fā)時(shí)間窗和到達(dá)時(shí)間窗內(nèi),同時(shí)時(shí)間窗需要包含乘客上下車(chē)的時(shí)間.設(shè)乘客i的最早出發(fā)時(shí)間為見(jiàn)式(4)(5),最晚出發(fā)時(shí)間為見(jiàn)式(4)(5),乘客的最早到達(dá)時(shí)間為見(jiàn)式(4)(5),最晚到達(dá)時(shí)間為見(jiàn)式(4)(5).

位置屬性包括起點(diǎn)位置,終點(diǎn)位置,起點(diǎn)位置指乘客發(fā)出合乘需求時(shí)所在的位置,終點(diǎn)位置為乘客設(shè)定的最終目的地所在的位置.

車(chē)輛主要有位置屬性、路徑屬性、時(shí)間屬性、乘載屬性.位置屬性主要包括:車(chē)輛出發(fā)位置、車(chē)輛經(jīng)停位置、車(chē)輛到達(dá)位置.起始位置指車(chē)輛在接收到呼叫時(shí)所在的位置,此時(shí)在車(chē)上無(wú)乘客;車(chē)輛經(jīng)停位置指乘客上下車(chē)時(shí)車(chē)輛?？康奈恢?車(chē)輛經(jīng)停位置和一部分乘客的起點(diǎn)位置和終點(diǎn)位置相同;車(chē)輛到達(dá)位置指車(chē)輛的最終到達(dá)的目的地,該位置和一部分乘客的終點(diǎn)位置相同,此時(shí)在車(chē)上無(wú)乘客.路徑屬性包括:路段信息和節(jié)點(diǎn)信息,節(jié)點(diǎn)信息可分為兩類(lèi):路網(wǎng)節(jié)點(diǎn)和?？抗?jié)點(diǎn).路段信息指路徑經(jīng)過(guò)路段的信息,路段信息包括:路段名稱(chēng)或編號(hào)、路段長(zhǎng)度、路段限制速度、路段實(shí)際通行能力、路段交通量、路段行程時(shí)間.路網(wǎng)節(jié)點(diǎn)指路徑經(jīng)過(guò)的路網(wǎng)中的交叉口等道路網(wǎng)中的固有節(jié)點(diǎn),停靠節(jié)點(diǎn)指路徑中車(chē)輛停車(chē)安排乘客上下車(chē)產(chǎn)生的節(jié)點(diǎn),?？抗?jié)點(diǎn)中包含任務(wù)起點(diǎn)和任務(wù)終點(diǎn),任務(wù)起點(diǎn)指車(chē)輛收到乘客呼叫所在的位置,任務(wù)終點(diǎn)指整個(gè)行程的終點(diǎn)即合乘任務(wù)中最后1名乘客下車(chē)的位置.時(shí)間屬性包括車(chē)輛到達(dá)出發(fā)地時(shí)間,車(chē)輛到達(dá)目的地時(shí)間,車(chē)輛到達(dá)出發(fā)點(diǎn)時(shí)間是1個(gè)點(diǎn)時(shí)間集合,它指車(chē)輛到達(dá)乘客發(fā)出呼叫的地點(diǎn)的所有點(diǎn)時(shí)間,車(chē)輛到達(dá)目的地時(shí)間指車(chē)輛到達(dá)乘客目的地的所有點(diǎn)時(shí)間.設(shè)車(chē)輛到達(dá)第i名乘客的出發(fā)地時(shí)間為tio,車(chē)輛到達(dá)第i名乘客的目的地時(shí)間為tid.車(chē)輛時(shí)間屬性與乘客時(shí)間屬性的關(guān)系見(jiàn)式(4)(5):

tile≤tio≤till

(4)

tiae≤tid≤tial

(5)

乘載屬性包括:核載量、實(shí)載量、乘載率.核載量指車(chē)輛滿載可乘載的人數(shù),實(shí)載量指當(dāng)前車(chē)輛實(shí)際乘載的人數(shù),乘載率指實(shí)載量與核載量的比值,乘載率越大說(shuō)明車(chē)量載客的人數(shù)越多,當(dāng)乘載率為1時(shí),車(chē)輛為滿載.設(shè)核載量為m,實(shí)載量為r,乘載率為θ的計(jì)算方法見(jiàn)式(6)[12]:

θ=m/r

(6)

路網(wǎng)主要有:路段屬性和節(jié)點(diǎn)屬性.路段屬性包含的路段信息有路段名稱(chēng)或編號(hào)、路段長(zhǎng)度、相連的節(jié)點(diǎn)編號(hào)、路段實(shí)際通行能力、路段限制車(chē)速,車(chē)輛的路徑屬性的路段乘載信息的具體取值在相同路段與路網(wǎng)的路段屬性的路段信息的具體取值相同,但是路網(wǎng)的路段屬性包含車(chē)輛路徑經(jīng)過(guò)路段的路段信息也包含未經(jīng)過(guò)路段的路段信息.幾何上看,路網(wǎng)的節(jié)點(diǎn)指路網(wǎng)中路段的起終點(diǎn)或路段的交點(diǎn)(如交叉口),節(jié)點(diǎn)屬性包括節(jié)點(diǎn)位置、相鄰路段、進(jìn)口道交通量、信號(hào)周期長(zhǎng)度、綠信比,交叉口飽和度.獲取路網(wǎng)屬性的目的是為了自動(dòng)駕駛汽車(chē)預(yù)測(cè)行程時(shí)間延誤,由于自動(dòng)駕駛汽車(chē)只在開(kāi)始接受呼叫時(shí)進(jìn)行行程時(shí)間預(yù)測(cè),因此,在1次合乘出行服務(wù)中,行程時(shí)間是1個(gè)常量.行程時(shí)間根據(jù)路網(wǎng)的屬性分為路段行程時(shí)間和節(jié)點(diǎn)延誤,路段行程時(shí)間計(jì)算采用應(yīng)用最廣泛的美國(guó)道路局開(kāi)發(fā)的BPR函數(shù)計(jì)算[13]:

(7)

(8)

式中,ta為路段a上的時(shí)間延誤;ta(0)為路段a上的車(chē)輛自由行駛時(shí)間;la為路段a的長(zhǎng)度;vf為自由流速度;qa為路段a上的交通量;ca為路段a上的實(shí)際通行能力;α、β為阻滯參數(shù),根據(jù)由智能交通系統(tǒng)根據(jù)實(shí)際數(shù)據(jù)回歸分析求得.

交叉口延誤計(jì)算采用Webster公式計(jì)算見(jiàn)式(9):

(9)

式中,tu為u交叉口延誤;T為信號(hào)周期長(zhǎng)度;λ為進(jìn)口道有效綠燈時(shí)間與信號(hào)周期長(zhǎng)度之比,即綠信比;Q為進(jìn)口道的交通流量;X為飽和度,即進(jìn)口道交通流量與進(jìn)口道通行能力之比.

對(duì)于單車(chē)乘客選擇模型有如下假設(shè):

1)應(yīng)用單車(chē)乘客選擇模型的自動(dòng)駕駛汽車(chē)是自動(dòng)駕駛合乘系統(tǒng)中的自動(dòng)駕駛汽車(chē),該自動(dòng)駕駛汽車(chē)是1個(gè)完全的智能體;

2)所有備選的乘客均是在同一時(shí)間呼叫該自動(dòng)駕駛汽車(chē)進(jìn)行合乘服務(wù)的乘客;

3)單車(chē)乘客選擇模型只有在車(chē)輛實(shí)載量大于核載量時(shí)才會(huì)啟動(dòng);

4)單車(chē)乘客選擇模型對(duì)于時(shí)間最優(yōu)的選擇只限于車(chē)輛1次合乘任務(wù)、1輛自動(dòng)駕駛汽車(chē);

5)單車(chē)選擇模型中備選的乘客的基本社會(huì)屬性符合要求,社會(huì)信譽(yù)值應(yīng)大于Sc0,Sc0為自動(dòng)駕駛合乘系統(tǒng)的社會(huì)信譽(yù)值下限;

6)單車(chē)選擇模型在完成已有的任務(wù)時(shí)才會(huì)接受下1任務(wù),車(chē)輛中只允許下車(chē)不允許上車(chē);

7)乘客的出發(fā)時(shí)間窗和到達(dá)時(shí)間窗都分別相互具有交集;

8)單車(chē)選擇模型中的時(shí)間延誤是1個(gè)常量;

9)單車(chē)選擇模型車(chē)輛?？繒r(shí)間只考慮乘客上下車(chē)時(shí)間.

單車(chē)選擇模型行程總時(shí)間是從車(chē)輛選定好適合這次任務(wù)的乘客開(kāi)始出發(fā)去接第1個(gè)乘客開(kāi)始到最后1名下車(chē)為止的時(shí)間段,包括途徑的路段行程時(shí)間和節(jié)點(diǎn)時(shí)間延誤,節(jié)點(diǎn)延誤中包括交叉口節(jié)點(diǎn)延誤和停靠延誤2種節(jié)點(diǎn)延誤.?？垦诱`為車(chē)輛到達(dá)乘客的出發(fā)點(diǎn)或目的地的停靠時(shí)間,?？繒r(shí)間包括乘客上車(chē)時(shí)間和乘客下車(chē)時(shí)間.任務(wù)起點(diǎn)的和任務(wù)終點(diǎn)的位置不一定恰好路網(wǎng)節(jié)點(diǎn)上,因此任務(wù)的出發(fā)路段的路段行程時(shí)間和結(jié)束路段的路段行程時(shí)間不是所在整個(gè)路段行程時(shí)間,其中出發(fā)路段指任務(wù)起點(diǎn)到路徑經(jīng)過(guò)的第1個(gè)路網(wǎng)節(jié)點(diǎn)的路段,同理,結(jié)束路段指路段經(jīng)過(guò)的最后1個(gè)節(jié)點(diǎn)到任務(wù)終點(diǎn)的距離.設(shè)to為出發(fā)路段行程時(shí)間,t1為車(chē)輛行駛第1路段全路段的行程時(shí)間,l0任務(wù)起點(diǎn)到路徑經(jīng)過(guò)的第1個(gè)路網(wǎng)節(jié)點(diǎn)的距離,l1路徑經(jīng)過(guò)的第1個(gè)路段的路段長(zhǎng)度,出發(fā)路段行車(chē)時(shí)間見(jiàn)式(10):

(10)

式中,設(shè)td為結(jié)束路段行程時(shí)間;te為車(chē)輛行駛最后1個(gè)路段全路段的行程時(shí)間;ld路徑經(jīng)過(guò)的最后1個(gè)路網(wǎng)節(jié)點(diǎn)到任務(wù)終點(diǎn)的距離;le路徑經(jīng)過(guò)的最后1個(gè)路段的路段長(zhǎng)度,結(jié)束路段行車(chē)時(shí)間見(jiàn)式(11):

(11)

式中,設(shè)Tt為1次任務(wù)總的行程時(shí)間國(guó);tiup為乘客i上車(chē)時(shí)間;tidown為乘客i下車(chē)時(shí)間;nr為實(shí)載乘客數(shù);w為路徑經(jīng)過(guò)的路段數(shù),可得總的行程時(shí)間為:

(12)

綜上所述,可得單車(chē)選擇模型目標(biāo)函數(shù)為和約束條件如下:

minTt

(13)

3 啟發(fā)式算法

在自動(dòng)駕駛合乘系統(tǒng)中,自動(dòng)駕駛汽車(chē)要及時(shí)對(duì)乘客的需求做出應(yīng)答,因此求解單車(chē)選擇模型的關(guān)鍵是在較短的時(shí)間內(nèi)找到滿意解,本文提出了多重選擇啟發(fā)式算法求解單車(chē)選擇模型,該算法的含義是:根據(jù)模型的需求分級(jí)求解,需求程度由迫切到一般的順序依次是:安全、準(zhǔn)時(shí)、耗時(shí)短[14],安全指用戶的社會(huì)信譽(yù)值必須高于自動(dòng)駕駛合乘系統(tǒng)的社會(huì)信譽(yù)值的下限,準(zhǔn)時(shí)指乘客的時(shí)間窗應(yīng)該相互包含或有交集,不是相互獨(dú)立沒(méi)有交集的,耗時(shí)短即為模型的目標(biāo)函數(shù),指自動(dòng)駕駛車(chē)完成1次任務(wù)總的行程時(shí)間最短.如圖3所示,算法的流程為:

圖3 啟發(fā)式算法流程

1)判斷呼叫該自動(dòng)駕駛汽車(chē)的乘客數(shù)量;超過(guò)核載量時(shí)進(jìn)入下一步,否則完成乘客選擇,退出單車(chē)選擇模型;

2)設(shè)置社會(huì)信譽(yù)值的下限,判斷所有呼叫乘客的社會(huì)信譽(yù)值,選出高于社會(huì)信譽(yù)值下限的乘客,其他乘客將被告知請(qǐng)選擇其他車(chē)輛.判斷選出乘客數(shù)是否超過(guò)自動(dòng)駕駛汽車(chē)核載量,如果超過(guò)核載量進(jìn)入下一步,否則完成乘客選擇,退出單車(chē)選擇模型;

3)分別排列乘客的出發(fā)時(shí)間窗和到達(dá)時(shí)間窗,將選出出發(fā)時(shí)間窗和到達(dá)時(shí)間窗分別互有交集的乘客,這類(lèi)乘客的數(shù)量記為可共乘乘客數(shù)np,如果np

4)進(jìn)入行程時(shí)間優(yōu)化選擇,完成乘客選擇退出單車(chē)選擇模型.

行程時(shí)間優(yōu)化選擇算法是通過(guò)選擇指數(shù)完成最后一步選擇工作,選擇指數(shù)受方向變量和繞行時(shí)間變量影響.

算法的流程為:

1)根據(jù)待選乘客數(shù)目均分自動(dòng)駕駛汽車(chē)的服務(wù)區(qū)域;

2)劃分待選乘客起點(diǎn)和終點(diǎn)所屬的區(qū)域,對(duì)于在區(qū)域邊緣的點(diǎn)自動(dòng)劃入包含點(diǎn)較多的區(qū)域,否則隨機(jī)劃入1個(gè)區(qū)域;

3)使用BPR函數(shù)和Webster公式結(jié)合Dijkstra算法預(yù)測(cè)每名乘客起點(diǎn)到終點(diǎn)的行程時(shí)間和自動(dòng)駕駛汽車(chē)從當(dāng)前位置行駛到乘客起點(diǎn)的行程時(shí)間;

4)計(jì)算選擇指數(shù);

5)根據(jù)選擇指數(shù)對(duì)乘客進(jìn)行排序,選擇指數(shù)最高的前m名乘客,如果排在第m名的有多名乘客,隨機(jī)選擇其中1位;

6)通知落選的待選乘客選擇其他自動(dòng)駕駛汽車(chē).

算法流程中選擇指數(shù)的計(jì)算將第i名乘客的選擇指數(shù)設(shè)為si,方向變量設(shè)為di,繞行時(shí)間變量設(shè)為pi,可得選擇指數(shù)見(jiàn)式(14)～(18):

si=di-pi

(14)

dio=αi/n

(15)

did=ωi/n

(16)

di=diodid

(17)

pi=tio/ti

(18)

式中,αi為與乘客i起點(diǎn)在同一區(qū)域的乘客數(shù);ωi為與乘客i終點(diǎn)在同一區(qū)域的乘客數(shù);N為待選乘客數(shù);dio為乘客i的起點(diǎn)方向變量;did為乘客i的終點(diǎn)方向變量;tio為車(chē)輛到達(dá)乘客i起點(diǎn)處的預(yù)測(cè)行程時(shí)間;ti為乘客i的起點(diǎn)至終點(diǎn)的預(yù)測(cè)行程時(shí)間.

4 數(shù)值實(shí)驗(yàn)

如圖4所示,本文選取1個(gè)隨機(jī)路網(wǎng),隨機(jī)選取車(chē)輛起始位置、乘客起訖點(diǎn)、乘客數(shù)量、起點(diǎn)乘客出發(fā)時(shí)間窗和到達(dá)時(shí)間窗、路網(wǎng)交通量,設(shè)定車(chē)輛的核載量為4名乘客,分別采用啟發(fā)式算法的單車(chē)乘客選擇模型和隨機(jī)選取乘客的方法選出參與合乘的乘客,其中隨機(jī)選擇乘客指從所有同時(shí)呼叫該車(chē)的用戶中任意選擇4名乘客作為這次合乘的最終乘客.在合乘乘客選出之后,采用Dijkstra算法進(jìn)行合乘的最短路徑規(guī)劃,Dijkstra算法是圖論中計(jì)算最短路問(wèn)題的經(jīng)典算法,該算法可獲得問(wèn)題的最優(yōu)解[15],在獲得合乘的最短路徑后,分別計(jì)算2種方法的總行程時(shí)間Tt和乘載率θ.設(shè)路網(wǎng)交通量為Qt,其中路網(wǎng)交通量Qt與路段交通量qa的關(guān)系見(jiàn)式(19):

(19)

模擬實(shí)驗(yàn)的路網(wǎng)交通量按均勻分布從0 pcu/h逐步遞增至75 000 pcu/h(見(jiàn)圖5),我們發(fā)現(xiàn)隨著路網(wǎng)交通量的增加,合乘總行程時(shí)間也隨之增加,其中使用單車(chē)選擇模型后進(jìn)行合乘出行的合乘總行程時(shí)間的期望值為:34.94 min,標(biāo)準(zhǔn)差為14.35 min;采用隨機(jī)選擇后進(jìn)行合乘出行的合乘總行程時(shí)間的期望值為:43.70 min,標(biāo)準(zhǔn)差為20.85 min,可見(jiàn)采用單車(chē)選擇模型相較隨機(jī)選擇合乘乘客具有更短的行程時(shí)間,受道路中交通量變化影響較小,到達(dá)時(shí)間相對(duì)準(zhǔn)時(shí).

當(dāng)路網(wǎng)交通量為27 000 pcu/h時(shí),采用單車(chē)選擇模型與隨機(jī)選擇乘客后所得合乘行程總時(shí)間最接近,在總時(shí)間基本相同時(shí),可對(duì)兩種模型的承載率進(jìn)行對(duì)比,因此選取路網(wǎng)交通量為27 000 pcu/h進(jìn)行模擬實(shí)驗(yàn)獲取乘載率數(shù)據(jù).經(jīng)過(guò)多次實(shí)驗(yàn)之后可得選用單車(chē)選擇模型后自動(dòng)駕駛汽車(chē)的乘載率期望值為95%,標(biāo)準(zhǔn)差為12.18%;選用隨機(jī)選擇的自動(dòng)駕駛汽車(chē)的乘載率為100%,標(biāo)準(zhǔn)差為0.可見(jiàn)由于單車(chē)選擇模型對(duì)備選乘客的篩查降低了乘客與自動(dòng)駕駛汽車(chē)匹配的成功率,也降低了車(chē)輛的乘載率,但是自動(dòng)駕駛車(chē)的乘載率仍在90%以上,仍具有較高使用效率,同時(shí)隨機(jī)選擇產(chǎn)生的合乘乘客組合,乘客社會(huì)信譽(yù)值是未知的,因此合乘行為存在一定的安全隱患.同時(shí),隨機(jī)選擇也不能保證合乘乘客的時(shí)間窗具有相似性,可能發(fā)生無(wú)法準(zhǔn)時(shí)將乘客送達(dá)至目的地;因此單車(chē)乘客選擇模型相較隨機(jī)選擇合乘乘客的方式具有高效性.

5 結(jié)論

本文提出了1種自動(dòng)駕駛汽車(chē)合乘系統(tǒng)(AVCS)的系統(tǒng)框架和運(yùn)營(yíng)模式,為未來(lái)自動(dòng)駕駛汽車(chē)在交通運(yùn)輸領(lǐng)域的應(yīng)用提供1個(gè)初步可行的方案.基于自動(dòng)駕駛汽車(chē)合乘系統(tǒng)框架,本文提出應(yīng)用于1輛自動(dòng)駕駛合乘汽車(chē)的乘客選擇模型(CPSM),解決了自動(dòng)駕駛汽車(chē)在面對(duì)超過(guò)車(chē)輛核載的乘客需求時(shí)如何選出行程時(shí)間最短的合乘乘客的問(wèn)題,同時(shí)提出了1種啟發(fā)式算法求解單車(chē)乘客選擇模型,通過(guò)數(shù)值實(shí)驗(yàn),證明了算法的可行性和模型的高效性.

對(duì)于未來(lái)自動(dòng)駕駛汽車(chē)合乘的研究,本文提出的自動(dòng)駕駛汽車(chē)合乘模型和單車(chē)選擇模型仍有許多不足之處:自動(dòng)駕駛汽車(chē)合乘系統(tǒng)的框架和運(yùn)營(yíng)模式仍然是基于對(duì)現(xiàn)有合乘系統(tǒng)框架和運(yùn)營(yíng)模式的延伸,其可行性還有待未來(lái)實(shí)踐的檢驗(yàn);單車(chē)選擇模型沒(méi)有考慮在乘載率沒(méi)有達(dá)到100%的情況下繼續(xù)接受乘客合乘需求的情況,同時(shí)對(duì)于往返乘客的需求也排除在外,對(duì)于多個(gè)自動(dòng)駕駛汽車(chē)協(xié)同聯(lián)運(yùn)的情況也考慮較少,對(duì)于宏觀的多輛自動(dòng)駕駛汽車(chē)與多名合乘乘客的高效精準(zhǔn)匹配問(wèn)題也尚未給予回答,可見(jiàn)未來(lái)仍有諸多問(wèn)題有待解決.