考慮乘客偏好的共享車輛動態(tài)共乘算法研究

崔洪軍，梁園園，朱敏清，楊依哲

(1.河北工業(yè)大學土木與交通學院，天津 300131；2.河北工業(yè)大學建筑與藝術設計學院，天津 300131)

隨著城市現(xiàn)代化進程的不斷加快，交通阻塞已成為困擾人們出行的頭等難題。共乘出行[1]作為一種最簡便快捷的道路擁堵解決方案，成為一個重要的研究方向。共乘出行的核心是車輛與乘客間的出行需求匹配，在動態(tài)共乘匹配場景中，大規(guī)模的實時匹配是非常耗時的。

中外學者都熱衷于車輛的供需匹配研究。譚衛(wèi)民等[2]提出了一個考慮最大權重的共乘匹配模型，基于不動匹配對和最晚出發(fā)時刻進行評估，最大化提高車輛與乘客的匹配成功率。張璽君等[3]設計了一種改進遺傳算法的車輛共乘線路規(guī)劃模型，以滿足最高搭載率與最短距離的要求。Alonso-Mora等[4]提出了一種大容量實時動態(tài)共乘模型并采用貪心算法進行求解，有效解決大規(guī)模動態(tài)共乘問題。王利龍[5]提出了一種基于Filter and Refinede動態(tài)共乘匹配框架，較好地解決了車輛匹配過程中的實時性問題。Xu等[6]提出來了一種新型的動態(tài)規(guī)劃算法(dynamic programming algorithm，DPA)來加速插入操作，通過固定目標終點的插入位置，尋找使繞行時間最小的起點插入。穆東等[7]指出，傳統(tǒng)的模擬退火算法雖能找到近似于全局最優(yōu)的解，但需要經過大量的迭代次數來求解問題，為了克服這個缺點，需要使用基于馬爾可夫鏈的并行模擬退火算法處理車輛路徑規(guī)劃的問題。Mohammed等[8]使用蟻群系統(tǒng)算法來克服蟻群算法不能較好的平衡收斂能力和探索能力的缺點，該算法通過平衡這種能力的關系來使得算法較快找到較優(yōu)解的同時也不容易陷入局部最優(yōu)。

但現(xiàn)有的研究主要存在兩方面的問題：首先，表現(xiàn)在服務質量參差不齊?？紤]到乘客共乘意愿、時間窗限制因素等不同，陳爽[9]建立了滿足乘客個性化服務需求的路徑優(yōu)化模型，結果表明增加乘客共乘意愿比例，車隊規(guī)模和繞行偏差距離可以提高共乘的效果；Lin等[10]設計了一種基于集合的模擬二進制多目標拼車匹配算法模型，在乘客和司機拼車產生繞行距離最小的基礎上，最大化提高司機與乘客的匹配成功率。其次，表現(xiàn)在沒有兼顧乘客的共乘意愿需求。研究表明，信任是阻礙人們接受共乘的重要障礙。劉文彬等[11]通過啟發(fā)式算法構建了偏好需求下的共乘匹配模型，結果表明乘客的信任程度、個體偏好以及出行時間需求都對匹配成功率有很大影響。Gargiulo等[12]建立了多對多的共乘模型，研究表明如果信任程度、便利程度和優(yōu)惠政策激勵這3個核心問題得到解決，乘客共乘意愿會增大。

與現(xiàn)有的研究相比，本共乘策略首先考慮到大規(guī)模拼車出行環(huán)境下的動態(tài)實時性和高效性要求，通過乘客查找模塊和車輛篩選模塊，篩選掉了絕大數不能與當前乘客共乘的車輛，減少了車輛供需匹配過程中的計算量，并滿足了車輛匹配過程中的實時性要求。然后在最優(yōu)路徑匹配模塊中，考慮到乘客偏好需求，以繞行偏差容忍度最小的路線作為最優(yōu)的行駛路線，并在進一步的基礎上，考慮到乘客共乘意愿差異，在滿足不同乘客共乘意愿需求的基礎上，采用插入算法來為車輛和乘客規(guī)劃出最優(yōu)的行駛路徑，從而提高動態(tài)共享車輛的服務質量，滿足乘客的個性化服務需求。

1 動態(tài)共乘模型建立

1.1 模型假設

模型中的關鍵性假設主要包括：①車輛初始狀態(tài)為空載；②車輛的類型都相同，最大載客量為3；③乘客的時間窗參數都相等；④車輛與乘客的直線距離超過100 m時，方可共乘；⑤意愿共乘的乘客隨機產生；⑥車輛以恒定速度運行，且乘客上下車時間忽略不計；⑦在動態(tài)共乘中，考慮到個體偏好不同，將繞行偏差容忍度的最大值設置為0.5。

1.2 動態(tài)共乘模型

1.2.1 網絡結構

令G={V,E}表示有向圖，其中V為所有節(jié)點的集合，E為所有路段間集合，tij為車輛從節(jié)點i到j所消耗的時間，dij為節(jié)點i到j之間的距離，i和j為路網的節(jié)點且i,j∈V。

1.2.2 乘客

給定任意一個乘客集合O都由5個因素{si,di,ei,fi,qi}構成，其中，si為乘客的出發(fā)點位置；di為乘客的目的地位置；ei為乘客出發(fā)點的時間窗，即ei=(stsi,stei),其中，stsi為車輛到達乘客出發(fā)點的時間，stei為車輛到達乘客出發(fā)點時間的寬度值，fi為乘客目的地的時間窗，即fi=(dtsi,dtei)，其中，dtsi為乘客要求車輛到達目的地的時間，dtei為乘客要求車輛到達目的地的時間寬度值；qi為乘客所需空余座位數量。

1.2.3 車輛

1.2.4 共乘出行過程

一次完整的乘客共乘出行時間節(jié)點信息如圖1所示。

1.2.5 共乘出行的約束條件

1)時間約束

Tdeparture+Tmin≤tls

(1)

式(1)保證車輛必須在乘客的最晚出發(fā)時間之前到達乘客出發(fā)位置。

tes≤Tdeparture+Tmin

(2)

式(2)保證車輛必須在乘客的最早出發(fā)時間之后到達乘客出發(fā)位置。

OA和DA分別為乘客A的出發(fā)點和目的地；Pk和PA分別為車輛的出發(fā)點位置和?？奎c位置；Tdeparture為車輛當前的出發(fā)時間；TW為乘客出發(fā)時間和下車時間前后的寬度值；tes為乘客的最早出發(fā)時間；tls為乘客的最晚出發(fā)時間；tla為乘客的最晚到達時間；Tmax為車輛到乘客A出發(fā)位置所用的最大時間；Tmin為車輛到乘客A出發(fā)位置所用的最小時間；TTravel為從乘客A出發(fā)位置到目的地位置所用的時間；Rreturn為車輛最晚到達停靠點PA處的時間圖1 乘客共乘出行的時間節(jié)點信息圖Fig.1 Information diagram of time nodes for passenger shared travel

Tdeparture+Tmin≤Tdeparture+Tmin+Ttravel

(3)

式(3)保證車輛將乘客送到目的地的時間不小于車輛到達乘客出發(fā)點的時間。

Tdeparture+Tmax+Ttravel≤tla

(4)

式(4)保證車輛將乘客送到目的地的時間必須在乘客最晚到達時間之前。

2)容量約束

0≤maxQ≤a

(5)

式(5)保證在車輛運送過程中，車輛的載客量Q小于等于最大載客容量a。

3)距離約束

繞行偏差容忍度σ為在整條路線上，由于插入新請求后產生的繞行距離與原始行程距離的比值。如在給定交通網絡中G={V,E}，車輛的當前行駛路線S和插入新請求r后的路線S1，在滿足時間、容量約束以及距離約束條件下求得的偏差容忍度可表示為

σ={D(S1)-D(S)}/D(S)，σ≤0.5

(6)

式(6)中：D(S)為車輛在當前行駛路線S上的總行駛距離；D(S1)為插入新請求r后車輛在S1路線上的總行駛距離；D(S1)-D(S)表示在插入新請求r后產生的繞行距離。

2 算法框架構建

路徑規(guī)劃算法分為3個模塊，分別為乘客查找模塊、車輛篩選模塊和最優(yōu)路徑匹配模塊。系統(tǒng)根據乘客的共乘意愿請求，為乘客查找匹配滿足要求的車輛，與此同時根據乘客的時間和距離要求篩選掉不滿足要求的車輛。最后在眾多滿足要求的車輛中，挑選出距離偏差容忍度最少的車輛以及其對應的共乘行駛路徑，作為最優(yōu)篩選結果反饋給乘客。

2.1 乘客查找模塊

乘客查找模塊的目的是根據乘客共乘意愿的請求，挑選出合適的車輛。系統(tǒng)運行開始的時間為Tcur，固定匹配間隔時間為定值I，每經過I時間段，系統(tǒng)就會調度一次。

Tcur=nI，n=1，2，…，i

(7)

式(7)中：n為調度的次數。

乘客查找模塊分為搜索、等待兩個過程。

2.1.1 搜索

首先系統(tǒng)會設定一個區(qū)域，這個區(qū)域主要用于限制乘客和車輛的搜索范圍，還可用于定義車輛的平均速度。初始化乘客和車輛的數據，把乘客數據(來自歷史行程數據)載入存儲器中，所有的車輛一開始就進入系統(tǒng)，乘客按照歷史行程數據中出發(fā)的時間先后順序依次進入系統(tǒng)。系統(tǒng)每隔I分鐘刷新一次，刷新時需檢測前一階段出行需求的匹配結果，將匹配成功的出行需求信息及車輛路徑信息保存到已匹配區(qū)域。到達匹配時間節(jié)點后，系統(tǒng)會同時安排盡可能多的乘客與司機配對。路徑規(guī)劃策略會優(yōu)先考慮愿意共乘的乘客，對于沒有共乘意愿的乘客，系統(tǒng)會根據最短路徑原理給該乘客匹配最近的空車車輛，一旦接上乘客，在將該乘客送到目的地之前不能接送其他乘客。乘客不止把請求發(fā)送給一個車輛，乘客會優(yōu)先考慮距離比較近的車輛，無可用請求的時候，才會擴展搜索鄰近的區(qū)域。

2.1.2 等待

乘客的等待部分是指乘客向車輛發(fā)送請求后，乘客會按照時間順序在規(guī)定的時間窗內進行搜索，如果在規(guī)定的時間窗內，檢索不到成功的匹配時，該乘客的出行需求信息就會被移除，如存在時間窗未過期且未匹配成功的出行需求，將該出行需求轉移到等待區(qū)，與最新產生的出行需求一起等待系統(tǒng)匹配。理想的情況是能夠找到等同于座位數量的乘客進行共乘。當多個乘客的可行條件不能同時滿足時，系統(tǒng)會逐步減少乘客數量繼續(xù)進行匹配，如果與任何乘客的匹配條件都無法滿足，那么車輛會繼續(xù)在起點等待下一次匹配。乘客查找模塊的流程如圖2所示。

圖2 乘客查找模塊的系統(tǒng)結構圖Fig.2 System structure diagram of passenger search module

2.2 車輛篩選模塊

車輛篩選模塊基本思想是根據乘客的出發(fā)時間篩選和歐式距離篩選，過濾掉絕大部分不可能與當前行程共乘的車輛，將符合要求的車輛歸為一個團體。首先輸入乘客和車輛的數據，計算乘客的出發(fā)時間窗(tes-tls)，判斷車輛的出發(fā)時間Tdeparture是否小于乘客最晚出發(fā)時間tls，將不符合要求的車輛從系統(tǒng)中刪去，將篩選后的車輛團體儲存到K1中，計算滿足乘客出發(fā)時間要求的最遠距離Dmax(j)；由乘客的出發(fā)點位置Cposition和車輛的出發(fā)點位置Vposition(K1)，計算出車輛到乘客出發(fā)點最短距離Dmin(j)，比較Dmax(j)和Dmin(j)大小，刪除K1中Dmax(j)

圖3 車輛篩選模塊流程圖Fig.3 Flow chart of vehicle screening module

2.3 最優(yōu)路徑匹配模塊

最優(yōu)路徑匹配模塊是指將乘客新請求的起點和終點分別插入到當前車輛的行程規(guī)劃中，利用約束條件和乘客的異質性偏差特性進行篩選，從而選擇最優(yōu)的車輛進行匹配。一般情況下，在行程中匹配新的乘客可能會改變原來的行駛路線。當有新的乘客加入當前行駛路線時，由于其起點、終點位置的分布以及時間限制的影響，原來共乘路線上接送的先后順序會被再次打亂。系統(tǒng)會先將滿足約束條件的所有請求的乘客起點插入到當前行程鏈中，并計算新共乘線路中乘客的繞行距離，對比新插入請求前后繞行距離，選擇繞行偏差容忍度最小的路線作為最優(yōu)路線。

舉例詳細說明路徑插入算法，插入乘客新請求的示例如圖4所示。

圖4 插入乘客新請求的示例圖Fig.4 An example diagram of inserting a new passenger request

圖4中，假設實線表示車輛K原始行程路線{K,OA,OB,DB,DA,P1}，實線的兩端為車輛的起始點和停車站(當把最后一位乘客送到目的地后，車輛會返回到離自己最近的停車場，P1、P2和P3都是指停車場，假設最近的停車場是P1)，新請求的起點和終點分別表示為OC和DC。當將新請求的起點和終點插入到現(xiàn)有路徑時，需要檢查每個車輛和新請求所有可能的拼車路線，并從中篩選出滿足所有拼車要求并且繞路偏差容忍度最小的路徑，因此采用了插入算法。插入算法的具體步驟如下。

步驟1讀取新請求和原始路線數據。在匹配過程中，從所有車輛路徑中尋找可能的插入點，將新請求的起點插入到所有可能的位置路線中，計算新請求的起點插入到每個位置后的距離偏差，將加入后產生的距離偏差最小的位置作為插入點。

步驟2檢驗插入乘客起點后，乘客和車輛的共乘條件是否依舊滿足：①檢驗上車時間約束。若不滿足，則終止本次插入操作；②檢驗車輛容量約束是否滿足，不滿足車輛容量約束，終止本次插入操作。

步驟3系統(tǒng)更新匹配成功車輛的行駛路線。同理，將新請求的終點插入到所有可能的位置路線中，計算新請求的終點插入到每個位置后的距離偏差，將加入后產生的距離偏差最小的位置作為插入點。

步驟4檢驗插入乘客終點后，乘客和車輛的共乘條件是否依舊滿足：①檢驗上車和下車時間約束是否滿足。若不滿足，則終止本次插入操作；②檢驗車輛容量約束是否滿足，不滿足車輛容量約束，則終止本次插入操作；對于一對乘客起終點的插入順序，遵循先插入乘客起點，后插入乘客終點的原則，且路徑上的終點必須在起點后。

步驟5將滿足約束條件的全部路線作為候選路線，檢驗插入乘客的終點后，繞行距離偏差容忍度是否小于等于0.5，如不滿足，則終止本次插入操作，若滿足則將新請求的路線作為最優(yōu)路線。

3 算法仿真及結果分析

為了使結果更接近真實性，使用出租車的歷史行程數據來模擬共享無人駕駛車輛的數據。采用成都市2017年8月1日7:00—21:00時間段的700輛出租車和2 100位乘客的GPS軌跡數據(https://www.didiglobal.com/science/intelligent-driving)，來模擬現(xiàn)實中14 h的情況。

3.1 不同偏好條件下對共乘結果的影響

為了分析繞行偏差容忍度σ和乘客共乘意愿比例對匹配結果的影響，假定其他參數不變，分析對乘客平均等待時間、總社會效益、匹配成功率的影響。繞行偏差容忍度和乘客共乘意愿比例都分別設置為0%、25%、50%、75%、100%時，分析結果如表1～表3所示。

表1 不同偏好條件下乘客平均等待時間結果對比Table 1 Comparison of the results of the average waiting time of passengers under different preference conditions

表2 不同偏好條件下總社會效益結果對比Table 2 Comparison of the results of total social benefits under different preference conditions

表3 不同偏好條件下匹配成功率結果對比Table 3 Comparison of matching success rate results under different preference conditions

由表1可以看出，在同一共乘意愿比例下，乘客平均等待時間隨著繞行偏差容忍度的增大而減小，這主要是因為同樣時間內，繞行偏差容忍度越大，車輛在接送乘客過程中選擇的靈活性越高，乘客可選擇的車輛就越多，即增加了車輛與乘客的供需匹配的可能性。和常規(guī)情況對比可以看出乘客平均等待時間降低了7.0%。

由表2、表3可以看出，在同一共乘意愿比例下，總社會收益和匹配成功率都是隨著繞行偏差容忍度的增大而增大，但當繞行偏差容忍度和共乘意愿比例增加到一定程度時，由于達到車輛最大容忍量，總社會效益和匹配成功率逐漸趨于平穩(wěn)，其原因在于總社會效益受服務人數的影響，當服務人數逐漸趨于飽和時，匹配成功率也逐漸趨于平緩。和常規(guī)情況對比可以看出總社會收益提高了44.7%，匹配成功率提高了34.2%。

3.2 不同時間窗下速度對共乘效果的影響

考察時間窗長度為10、15、20、25、30 min條件下，固定乘客可接受的繞行偏差容忍度為0.5，乘客全部愿意共乘，假定其他參數不變，分析速度對乘客平均等待時間、總社會效益、匹配成功率的影響，分析結果如圖5～圖7所示。

圖5 不同時間窗下速度對乘客平均等待時間的影響Fig.5 Comparison of speed versus average waiting time of passengers under different time windows

圖6 不同時間窗下速度對總社會效益的影響Fig.6 Comparison of speed versus total social benefits under different time windows

圖7 不同時間窗下速度對匹配成功率的影響Fig.7 Comparison of speed versus matching success rate under different time windows

由圖5～圖7可知，在同一時間窗下，隨著速度的增大，總社會效益、匹配成功率均呈現(xiàn)增大趨勢，乘客平均等待時間逐漸減小，但當車輛速度增大到60 km/h，總社會效益和匹配成功率隨著車輛速度的增大逐漸趨于平緩，這說明服務的人數已經逐漸趨于飽和。在同一速度不同時間窗下，時間窗差值越大，總社會效益、匹配成功率的差值越大，原因在于時間窗越大，可同時服務的人數就越多，車輛的收入也會越多，因此總社會效益和匹配成功率越大。由于同時服務的人數越多，則同一速度下，時間窗越大則乘客的平均等待時間就越大。

4 結論

所提算法運用了乘客查找模塊和車輛篩選模塊濾掉了絕大部分不可能與當前行程共乘的行程，快速的為乘客篩選出滿足乘客要求的車輛。另外，乘客由于個體偏好原因對共乘策略中共享意愿、可接受的路徑偏差范圍有不同的喜好，針對此情況構建的算法框架能夠巧妙解決動態(tài)共享車輛共乘匹配和調度復雜關系，并從平均等待時間、總社會效益、匹配成功率3個角度進行分析，證明了該算法以及團體篩選策略的優(yōu)越性。