考慮用戶偏好的啟發式動態共乘匹配算法

摘 要： 針對現有算法很少考慮用戶之間的共乘偏好需求，提出了一種考慮用戶偏好的啟發式動態共乘匹配算法。構建一個滿足用戶偏好需求的動態共乘匹配模型，旨在最大化系統匹配率和最小化車輛的繞行距離。算法首先根據出行請求的時間約束、車輛與用戶的出行軌跡以及用戶的興趣偏好，過濾不滿足用戶偏好需求的車輛；其次，構建一個臨時匹配圖，設置邊的權值為出行請求插入到車輛的當前行駛路線中的最小繞行距離；最后采用貪婪方式實現用戶與車輛之間的匹配，并采用節點插入方式，將出行請求的出發地點和到達地點插入到車輛的當前行駛路線中。仿真結果表明，提出的啟發式動態共乘匹配算法使車輛增加的平均繞行距離和運行時間低于現有算法，系統匹配率高于現有算法；用戶的出行時間需求、興趣偏好、信譽度等共乘需求對系統匹配率有顯著影響。

關鍵詞： 城市交通； 用戶偏好； 動態共乘； 匹配算法

中圖分類號： U492.4"" 文獻標志碼： A

文章編號： 1001-3695（2022）01-013-0075-05

doi：10.19734/j.issn.1001-3695.2021.06.0252

Heuristic dynamic ridesharing matching algorithm considering user preferences

Liu Wenbin， Yang Bo， Zhong Minjuan

（College of Information Technology amp; Management， Hunan University of Finance amp; Economics， Changsha 410205， China）

Abstract： This paper designed a heuristic dynamic ridesharing matching algorithm considering user preference to overcome defects that the existing algorithms seldom considered the demand of ridesharing preference among users in dynamic ridesharing system.It established a dynamic ridesharing matching model to satisfy the user’s preference demands，which was to address the problem of maximize the system matching rate and minimize the vehicle detour distance.At first，the proposed algorithm filtered the vehicles that did not meet the user’s preferences according to the time constraints of travel requests，the travel trajectories of vehicles and users，and the user’s interests and preferences.And then，it constructed a temporary matching graph，and set the weight of the edge as the minimum vehicle detour distance when inserted a travel request into the current driving route of a vehicle.Finally，the proposed algorithm used a greedy method to realize the matching between users and vehicles，and adopted the nodes insertion method to insert the origin and destination of a travel request into the current driving route of a vehicle.The simulation results show that the average vehicle detour distance and runtime of proposed algorithm are lower than the existing algorithms，and the system matching rate is higher than the existing algorithms.The user’s ridesharing preference requirements such as user’s travel time demand，interest preference，reputation，and so on，have a significant impact on the system matching rate.

Key words： urban traffic； user preference； dynamic ridesharing； matching algorithm

0 引言

共乘的本質是共享汽車資源的使用權，利用移動社交網絡安排出行路線大致相似的多個乘客搭乘同一車輛。與傳統拼車模式相比，動態共乘需要根據乘客出行請求和車輛位置的實時變化，動態地分配車輛給乘客。然而，乘客的出行請求是隨機出現的，車輛位置是實時變化的，難以預測與捕捉，這給乘客與車輛之間的動態匹配帶來了新的挑戰。此外，當越來越多的乘客選擇共乘時，也向系統提出了一些個性化偏好需求：有些乘客選擇熟悉的乘客與之共乘，有些乘客選擇興趣相似的乘客與之共乘，還有些乘客對出行時間有嚴格的需求等。因此，考慮用戶偏好的動態共乘匹配問題已成為交通信息領域的研究熱點［1，2］。

目前，國內外學者針對用戶提出的各種偏好需求，對動態共乘匹配問題展開了研究。Yousf等人［3］根據共乘繞行距離、支付費用、用戶信任度、共同興趣等偏好需求，構建了動態共乘匹配模型。Thaithatkul等人［4］采用共乘效益函數融合共乘費用與偏好需求，利用婚姻穩定匹配算法實現用戶與車輛的一一匹配。張薇等人［5］根據共乘費用、行程時間和舒適度對共乘決策的影響進行了模擬與分析。王晞諾等人［6］通過計算機仿真，探索了用戶的時間需求和信任水平對動態共乘匹配性能的影響。Aiko等人［7］針對繞行距離、時空約束、車輛容量等偏好需求，采用分支限界算法實現了用戶與車輛的一一匹配。Z·ak等人［8］根據乘客的偏好需求構建了一個基于多屬性決策的動態共乘匹配模型，并采用多屬性遺傳算法獲取帕累托最優解。Zhang等人［9］根據用戶的偏好需求，設計具有優先次序的偏好列表，并采用穩定匹配算法將車輛分配給用戶。Fu等人［10］證明了在滿足用戶需求的條件下，最大化系統匹配率的動態共乘匹配問題是一個NP-hard問題，并提出了一種啟發式動態共乘匹配算法。

已有研究主要實現用戶與車輛的一一匹配，因而也只考慮了用戶對車輛的偏好需求。然而，共乘是一次多人同時參與的出行活動，不僅需要考慮用戶對車輛的偏好需求，而且需要考慮車輛上用戶之間的偏好需求。此外，車輛的行程路線因乘客的變化而實時改變，現有研究側重于用戶與車輛的匹配，忽視了車輛行程路線及車上乘客的變化對系統性能的影響。為了彌補現有研究的不足，設計了一種考慮用戶偏好的啟發式動態共乘匹配算法。算法首先根據用戶的偏好需求，篩選出滿足用戶偏好需求的車輛，減少系統的匹配時間；然后構建一個臨時匹配圖，設置邊的權值為出行請求插入到車輛的當前行駛路線中的最小繞行距離；最后采用貪婪方式實現用戶與車輛之間的匹配，在每次匹配過程中，采用節點插入方式，將出行請求的出發地點和到達地點插入到車輛的當前行駛路線中。與現有研究相比，提出的啟發式算法不僅考慮了用戶對車輛的偏好需求，還考慮了車上原有用戶的偏好需求，能有效地提高動態共乘系統的性能。

3 仿真實驗

為了評價算法的性能，將本文提出的啟發式動態共乘匹配算法（簡記為HDRM算法）與文獻［10］提出的動態共乘匹配算法（簡記為DARQ算法）進行比較。DARQ算法首先采用橢圓剪枝技術篩選候選車輛；然后采用Jaccard系數計算用戶之間的興趣相似度，并以此獲取社會舒適度的最大值；最后采用貪婪方式，以最大化用戶的社會舒適度為優化目標，將出行請求分配給共乘服務提供者。

3.1 參數設置

根據美國紐約市的出租車出行記錄集（TLC trip record data，https：//www1.nyc.gov/site/tlc/about/ tlc-trip-record-data.page），提取264 346個節點和366 923 條路段構建城市交通路網；設出租車以40 km/h在道路上勻速行駛，最大載客容量為4（駕駛員除外）。從2016年1月的1 445 285的出行記錄中，提取17：00～19：30的100 000條出行記錄作為仿真實驗數據。每條記錄包括出發時間和到達時間、出發地點和到達地點的緯度與經度、行駛距離等信息。由于數據記錄中沒有出行時間約束，隨機設置出行請求的最早出發時間在5～10 min，最遲到達時間在30～60 min，并服從高斯分布。此外，數據集中也沒有用戶的偏好信息，所以用戶（包括駕駛員）的各種興趣偏好隨機設為0或1，也隨機設置信譽度，取值為［0，1］。

仿真實驗的評價指標是平均繞行距離、系統匹配率和算法的運行時間。平均繞行距離是指車輛增加的繞行距離之和除以車輛數。系統匹配率是指匹配成功的用戶數與用戶總數之比。在每次仿真中，將100 000條出行記錄隨機劃分為車輛集（占20%）和出行請求集（占80%）。實驗結果為50次仿真實驗的平均值。

3.2 實驗結果與分析

1）出行請求數量的影響

圖2顯示當車輛數為20 000、出行軌跡相似度閾值θ=0.7、偏好相似性閾值δ=0.6、信譽度閾值γ=0.9時，出行請求數量變化時的實驗結果。

從圖2（a）的顯示結果可以看出，車輛增加的平均繞行距離隨出行請求數量的增加而增加，這是因為當出行請求數量增加時，更多的用戶選擇共乘，因而每輛車因用戶數量的增加而逐漸增加了它的繞行距離。當出行請求數量增加到|R|=70000后，發現HDRM算法得到的車輛平均繞行距離稍有下降，因為用戶共乘數量增加到一定程度，很多用戶會選擇出行路線更加相似的用戶共乘，從而導致平均繞行距離有下降的趨勢。DARQ算法首先考慮最大化用戶的社會舒適度，其次才考慮最小化車輛增加的繞行距離，而HDRM算法是在滿足用戶偏好需求的情況下，最小化車輛增加的繞行距離。因此，HDRM算法得到的平均繞行距離低于DARQ算法。

在圖2（b）中，當出行請求數量與車輛數量相同時，即|R|=20 000時，盡管在理論上車輛與用戶可以進行一一匹配，但受到用戶偏好和信譽度的影響，匹配率并沒有達到100%。隨著出行請求數量的逐漸增加，系統匹配率卻逐漸降低，這是因為受車輛數量的影響，用戶需要選擇其他用戶與之共乘，而用戶之間的各種偏好需求嚴重影響了系統的匹配率。但當出行請求數量增加到|R|=50 000后，系統匹配率卻逐漸提高，這是因為隨著出行請求數量的增加，部分用戶的偏好和出行路線也逐漸相似，因而系統匹配率也逐漸提高。另一方面，DARQ算法追求的是最大化用戶的社會舒適度，而HDRM算法只需考慮是否滿足用戶的偏好需求，因而HDRM算法的系統匹配率略高于DARQ算法。

圖2（c）顯示了兩種算法的運行時間，算法的運行時間隨出行請求數量的增加而增加。從結果可以看出，HDRM算法的運行時間低于DARQ算法。其中一個主要的原因是，將出行請求插入到車輛的當前行駛路線中，DARQ算法采用hopping方式，其時間復雜度為O（k2）（k為車輛中已安排的出行請求數量），而HDRM算法采用節點插入方式［12］，其時間復雜度為O（k）；另一個主要的原因是，DARQ算法在每次將出行請求插入到車輛中時，都需要將每個出行請求與所有候選車輛進行匹配，而HDRM算法只需根據構建的臨時匹配圖，從中選擇權值最小的邊，即可得到出行請求與候選車輛的匹配。

2）出行時間需求的影響

設出行時間需求為最遲到達時間減去最早出行時間，圖3顯示當車輛數為20 000、出行請求數量為80 000、出行軌跡相似度閾值θ=0.7、偏好相似性閾值δ=0.6、信譽度閾值γ=0.9時，出行時間約束在15～60 min變化時的實驗結果。

圖3（a）和（b）的結果表明，車輛增加的平均繞行距離和系統匹配率隨出行時間需求的增加而增加。出行時間需求越嚴格，系統匹配率越低，這是因為將出行請求插入到車輛中，不僅要滿足出行請求的時間需求，而且也要滿足車上已安排的用戶的出行時間需求，因而匹配也越嚴格。但隨著出行時間需求的增加，即逐漸放松時間需求的約束，越來越多的出行請求能滿足彼此之間的時間需求，因而系統匹配率逐漸提高。與此同時，車輛因安排用戶數量的增加，其繞行距離也逐漸增加。然而，當出行時間需求變化到50 min后，用戶因有足夠多的時間滯留在車輛上，可以不受時間限制而與任何用戶共乘，因此系統匹配率和平均繞行距離的增幅不是很明顯。在圖3（c）中，算法的運行時間也受出行時間需求的影響。當出行時間需求越少時，兩種算法分別采用了剪枝或過濾技術，篩出不滿足用戶偏好需求的候選車輛，因而與每個出行請求相匹配的候選車輛較少，在實際匹配過程中，算法所需的時間也低；但隨著出行時間需求的增加，與每個出行請求相匹配的候選車輛逐漸增加，算法的運行時間也增加。從整體上看，HDRM算法的系統匹配率略高于DARQ算法，平均繞行距離和運行時間低于DARQ算法。

3）偏好需求的影響

固定車輛數為20 000、出行請求數量為80 000、出行時間需求為40 min，圖4分別列出了出行軌跡、興趣偏好和信譽度需求值在0.5～0.9變化時，HDRM算法對系統匹配率的影響。顯然，隨著出行軌跡、興趣偏好和信譽度的需求值增加，用戶對與之共乘的用戶進行更加嚴格匹配，因而很多用戶因難以滿足其需求而無法與其他共乘用戶進行匹配，導致了較低的系統匹配率。相對而言，信譽度對系統匹配率的影響較大，興趣偏好次之，出行軌跡的影響較小。實驗結果表明，當用戶選擇共乘時，用戶的信譽度、各種偏好需求對用戶的出行決策有很大的影響。

4 結束語

共乘是一種由多人參與的共享型消費。針對用戶的多種共乘偏好需求，提出了一種考慮用戶偏好的啟發式動態共乘匹配算法，旨在最大化系統匹配率和最小化車輛的繞行距離。首先根據用戶的偏好需求，過濾不滿足用戶偏好需求的車輛。其次，構建一個臨時匹配圖，設置邊的權值為出行請求插入到車輛的當前行駛路線中的最小繞行距離。最后，采用貪婪方式，將出行請求分配給車輛，即在滿足用戶之間的偏好需求下，采用節點插入方式，將出行請求的出發地點和到達地點插入到車輛的當前行駛路線中。與現有算法相比，考慮用戶偏好的啟發式動態共乘匹配算法的優勢在于：a）在考慮用戶偏好需求時，不僅考慮了用戶對車輛的共乘偏好需求，而且也考慮了用戶之間的共乘偏好需求；b）針對車輛行程路線的實時變化，利用節點插入方式，將出行請求的出發地點和到達地點插入到車輛的當前行駛路線中。仿真實驗結果表明，提出的啟發式動態共乘匹配算法在系統匹配率和運行時間上要優于已有算法。然而，設計的算法考慮每個出行請求僅包含一位乘客，如果一個出行請求包含多位乘客，如何考慮他們之間的偏好需求以及與其他乘客和車輛之間的偏好需求，是算法沒有考慮的問題，也將是今后的研究方向。

參考文獻：

［1］Tang Lei，Duan Zongtao，Zhao Yaling.Toward using social media to support ridesharing services：challenges and opportunities［J］.Transportation Planning and Technology，2019，42（4）：355-379.

［2］徐毅，童詠昕，李未.大規模拼車算法研究進展［J］.計算機研究與發展，2020，57（1）：32-52. （Xu Yi，Tong Yongxin，Li Wei.Recent progress in large-scale ridesharing algorithms［J］.Journal of Computer Research and Development，2020，57（1）：32-52.）

［3］Yousf J，Li Juanzi，Chen Lu，et al.Generalized multipath planning model for ride-sharing systems［J］.Frontiers of Computer Science，2014，8（1）：100-118.

［4］Thaithatkul P，Seo T，Kusakabe T，et al.A passengers matching pro-blem in ridesharing systems by considering user preference［J］.Journal of the Eastern Asia Society for Transportation Studies，2015（11）：1416-1432.

［5］張薇，何瑞春，肖強，等.考慮乘客心理的出租車合乘決策方法研究［J］.交通運輸系統工程與信息，2015，15（2）：18-23. （Zhang Wei，He Ruichun，Xiao Qiang，et al.A method of taxi pooling mode decision-making with passenger psychology［J］.Journal of Transportation Systems Engineering and Information Technology，2015，15（2）：17-23.）

［6］王晞諾，侯立文.雙因素約束下動態共乘成功率仿真研究［J］.計算機應用研究，2018，35（5）：1331-1336. （Wang Xinuo，Hou Liwen.Matching modeling amp; simulation of dynamic ridesharing with dual factor constraint［J］.Application Research of Computers，2018，35（5）：1331-1336.）

［7］Aiko S，Thaithatkul P，Asakura Y.Incorporating user preference into optimal vehicle routing problem of integrated sharing transport system［J］.Asian Transport Studies，2018，5（1）：98-116.

［8］Z·ak J，Hojda M，Filcek G.Multiple criteria optimization of the carpoo-ling problem［J］.Transportation Research Procedia，2019，37：139-146.

［9］Zhang Hongmou，Zhao Jinhua.Mobility sharing as a preference mat-ching problem［J］.IEEE Trans on Intelligent Transportation Systems，2019，20（7）：2584-2592.

［10］Fu Xiaoyi，Zhang Ce，Lu Hua，et al.Efficient matching of offers and requests in social-aware ridesharing［J］.GeoInformatica，2019，23：559-589.

［11］Lee J G，Han J，Whang K Y.Trajectory clustering：a partition-and-group framework［C］//Proc of ACM SIGMOD.New York：ACM Press，2007：593-604.

［12］劉文彬，楊波，閻綱，等.動態共乘系統中一種高效的插入操作方法［J］.計算機應用研究，2021，38（8）：2430-2434. （Liu Wenbin，Yang Bo，Yan Gang，et al.A high efficient insertion operation method in dynamic ridesharing system［J］.Application Research of Computers，2021，38（8）：2430-2434.）