考慮乘客信任程度的營運(yùn)車輛合乘線路規(guī)劃

作者簡介：王志建（1982－），男，河北石家莊人，教授，碩導(dǎo)，博士，主要研究方向?yàn)橹悄芙煌ā⒏?dòng)車技術(shù)（wzjian0722@163.com）；郭健（1999－），男，山東聊城人，碩士研究生，主要研究方向?yàn)橹悄芙煌ā⒏?dòng)車技術(shù)；張強(qiáng)（1982－），男，山西大同人，高級工程師，主要研究方向?yàn)橹腔劢煌?

摘 要：車輛合乘是解決交通擁堵的有效方法，然而乘客對車輛合乘行為缺乏信任是影響合乘發(fā)展的難題。針對這一問題，通過引入信任度權(quán)重和用戶偏好來衡量合乘的信任水平，以車輛的總行駛距離最短以及總信任度值最高為目標(biāo)函數(shù)，同時(shí)考慮了車輛搭載容量約束、車輛行駛距離約束、乘客需求響應(yīng)約束以及車輛站點(diǎn)服務(wù)約束，構(gòu)建了考慮乘客信任程度的合乘模型，然后針對該模型采用改進(jìn)的遺傳算法進(jìn)行求解。最后采用北京市新發(fā)地周邊地區(qū)的營運(yùn)車輛數(shù)據(jù)進(jìn)行算法驗(yàn)證。結(jié)果表明，該模型能夠在有效減少車輛總行駛距離的同時(shí)保障較高的乘客合乘信任水平，相較于僅考慮距離優(yōu)化的模型，距離成本增加了14.8%，信任水平提升了3.3倍。通過對優(yōu)化結(jié)果的對比分析，驗(yàn)證了模型和算法的有效性。

關(guān)鍵詞：智能交通；合乘線路；社交信任；遺傳算法；線路規(guī)劃

中圖分類號：U492.4 文獻(xiàn)標(biāo)志碼：A 文章編號：1001－3695（2023）04－006－0996－04doi： 10.19734/j.issn.1001－3695.2022.09.0460

Abstract：Ride-sharing is an effective way to solve traffic congestion. However， passengers’ lack of trust in ride-sharing behavior is a problem that affects the development of ride-sharing. To solve this problem， by introducing trust weight and user preferences to measure the trust level， taking the shortest total driving distance of the vehicle and the highest total trust value as the objective function， and considering the vehicle loading capacity constraints， vehicle travel distance constraints， passenger demand response constraints and vehicle station service constraints， this paper constructed a ride-sharing model considering passenger trust degree， and used an improved genetic algorithm to solve the model. Finally， this paper used the data of opera-ting vehicles in the surrounding areas of Beijing Xinfa to verify the algorithm. The results show that the model can effectively reduce the total vehicle distance while ensuring a high level of passenger ride-sharing trust. The distance cost is 14.8% less than the models only considering distance optimization， and the trust level is 3.3 times higher. This paper verifies the effectiveness of the model and the algorithm through the comparative analysis of the optimization results.

Key words：intelligent transportation; ride-sharing route; social trust; genetic algorithm; route planning

0 引言

目前城市交通存在的車輛行駛效率低、交通擁堵日益嚴(yán)重的現(xiàn)象，對人們的出行造成了極大的不便。有效的車輛合乘模式可以提高座位利用率，緩解城市交通壓力［1］。然而缺乏安全感是造成我國合乘發(fā)展緩慢的原因之一，缺乏安全感主要是由于缺乏對合乘人的信任，導(dǎo)致乘客對合乘的信任程度較低［2］。因此考慮乘客信任的合乘模式對于合乘的發(fā)展具有重要意義。

合乘問題近年來吸引了國內(nèi)外眾多學(xué)者的研究。在求解合乘問題的算法研究中，Chou等人［3］提出了一種基于隨機(jī)集的粒子群優(yōu)化算法，并引入了隨機(jī)編碼來增強(qiáng)傳統(tǒng)粒子，提高了合乘匹配率。Hou等人［4］考慮了一個(gè)以整個(gè)合乘系統(tǒng)負(fù)載率最大化為目標(biāo)的合乘匹配與路徑問題，采用大型鄰域搜索算法提高求解效率，該算法可以最優(yōu)地解決小規(guī)模實(shí)例，并快速為大規(guī)模實(shí)例返回滿意的方案。Huang等人［5］設(shè)計(jì)了一個(gè)合乘系統(tǒng)，提出了基于遺傳算法的合乘路線和匹配算法，實(shí)驗(yàn)證明該算法比爬坡算法能獲得更好的優(yōu)化結(jié)果。Lin等人［6］提出了一種基于集合的模擬二元和多目標(biāo)拼車匹配算法，結(jié)果表明該算法能有效地求解多目標(biāo)優(yōu)化合乘問題。楊志家等人［7］提出了一種兩階段分布式估計(jì)算法的合乘優(yōu)化模型，有效減少了交通擁堵和公共交通的壓力。

在合乘模型問題的研究中，劉文彬等人［8］提出一種考慮用戶偏好的啟發(fā)式動(dòng)態(tài)共乘匹配算法來求解滿足用戶偏好需求的動(dòng)態(tài)共乘匹配模型，最終結(jié)果表明用戶的興趣偏好等共乘需求對系統(tǒng)匹配率有顯著影響。He等人［9］以滿意度最大和價(jià)格最低為目標(biāo)建立了車輛合乘費(fèi)用的優(yōu)化模型來滿足乘客和司機(jī)的需求。張薇等人［10］基于前景理論構(gòu)建了車輛合乘模式?jīng)Q策模型，分析了行程時(shí)間、費(fèi)用、舒適度對乘客合乘心理決策的影響。Chaya等人［11］使用深度學(xué)習(xí)根據(jù)收集的數(shù)據(jù)對用戶滿意度進(jìn)行建模，提出了一種面向滿意度的分配方法，結(jié)果表明，一個(gè)豐富的用戶滿意度模型對于合乘非常重要。

現(xiàn)有研究在建立車輛合乘模型時(shí)，多數(shù)僅考慮了距離、時(shí)間興趣或費(fèi)用等因素的影響，而鮮有從乘客的信任角度出發(fā)研究合乘問題。針對以上問題，本文考慮了乘客合乘的信任問題，以車輛的總行駛距離最短以及總信任度值最高為目標(biāo)函數(shù)，通過引入信任度權(quán)重和用戶偏好來衡量合乘的信任水平，構(gòu)建了車輛合乘線路規(guī)劃模型，并采用改進(jìn)遺傳算法進(jìn)行求解。研究成果有助于提高乘客合乘的積極性。

1 問題描述與模型假設(shè)

1.1 問題描述

合乘車輛線路優(yōu)化問題來自于車輛路徑問題（VRP），本文假設(shè)每位乘客都合乘去往相同的目的地，車輛合乘問題的目標(biāo)是求出一種合乘方案，將乘客分到合乘小組中，并由車輛完成接送任務(wù)，算法計(jì)算出的方案需要兼顧信任優(yōu)化以及距離成本優(yōu)化，合乘過程中的乘客分配和車輛接送情況如圖1所示。

1.2 相關(guān)術(shù)語概念

在合乘過程中，研究要素主要包括車輛、路網(wǎng)、乘客。各研究要素的解釋如下：

a）車輛：在合乘過程中，車輛用k表示，在路網(wǎng)中的車輛集合用K表示，車輛的起始位置各不相同，每輛車有各自的行駛路線。

b）路網(wǎng)：在合乘過程中，用站點(diǎn)以及站點(diǎn)之間的有向線段組成路網(wǎng)，站點(diǎn)的集合用R表示，出發(fā)站點(diǎn)集合用O表示，終點(diǎn)站點(diǎn)用D表示。

c）乘客：乘客的集合用P表示，乘客分布在各個(gè)站點(diǎn)上，每個(gè)站點(diǎn)包含乘客的信息，信息包括的屬性有站點(diǎn)位置、乘客的信任度權(quán)重以及用戶偏好，每位乘客需要被車輛響應(yīng)。

1.3 模型假設(shè)

本文的合乘模型做如下假設(shè)：

a）車輛初始狀態(tài)為空載；

b）參與合乘的乘客的所有信息可提前獲取；

c）車輛發(fā)車起點(diǎn)到首個(gè)站點(diǎn)的距離為0；

d）乘客的終點(diǎn)站點(diǎn)一致；

e）為了乘車的舒適性，車輛最大載客量設(shè)為3。

2 建模方法

2.1 目標(biāo)函數(shù)

模型建立的目的是要兼顧車輛總行駛距離的同時(shí)保障較高的乘客合乘信任水平，因此建立雙目標(biāo)下的數(shù)學(xué)模型。

以車輛總行駛距離為目標(biāo)函數(shù)的數(shù)學(xué)模型如式（1）所示。

3 算法設(shè)計(jì)

針對合乘模型的特點(diǎn)，有明確的優(yōu)化目標(biāo)，需大量并行優(yōu)化計(jì)算，遺傳算法非常適合于車輛合乘模型的求解。因此，本文采用改進(jìn)遺傳算法實(shí)現(xiàn)車輛合乘線路規(guī)劃。

3.1 編碼設(shè)計(jì)

車輛合乘問題是一種基于線路組合順序的規(guī)劃問題，針對本文的合乘問題，采用站點(diǎn)編碼的方式進(jìn)行設(shè)計(jì)，遺傳算法的每條染色體表示一個(gè)合乘方案，每條染色體上的基因表示站點(diǎn)，染色體分割成多個(gè)子片段，每個(gè)子片段代表每輛車的合乘路徑［13］。

3.2 適應(yīng)度評價(jià)與選擇

本文中方案的選擇操作選用總評價(jià)值來描述候選個(gè)體的適應(yīng)度。由于模型的目標(biāo)函數(shù)既要求總行駛距離最小，還要求總信任度值最大，雙目標(biāo)函數(shù)的變化趨勢是相逆的，所以采用總信任度值與總行駛距離之比的形式作為模型的總評價(jià)值Sc，即

其中：Sc為總評價(jià)值；

W為常數(shù)，由于信任度值與行駛距離的比值較小，將該比值乘以一個(gè)常數(shù)，使得目標(biāo)函數(shù)放大到一個(gè)合理的范圍，W取值100。

為了繼承優(yōu)良基因片段的遺傳信息，進(jìn)而增加遺傳算法的全局收斂性以及計(jì)算效率，選擇錦標(biāo)賽選擇算子［14］，生成新一代種群。

3.3 交叉操作

本文采用隨機(jī)片段交叉方法，如圖2所示，具體的交叉過程為：隨機(jī)選取兩條父代個(gè)體P1、P2作為交叉?zhèn)€體，確保交叉片段兩端為不同車輛片段；然后將父代兩片段進(jìn)行片段交叉操作，示例中將P1中站點(diǎn)7、9、2與P2中站點(diǎn)8、4、9進(jìn)行交叉操作；交叉操作完成之后，子代中會(huì)出現(xiàn)重復(fù)站點(diǎn)，將交叉片段外的重復(fù)站點(diǎn)刪除，補(bǔ)充缺失的站點(diǎn)，示例中P1交叉完后站點(diǎn)4、8重復(fù)，刪除站點(diǎn)4、8，補(bǔ)充缺失站點(diǎn)2、7，最終形成子代個(gè)體S1，同理形成子代個(gè)體S2。

3.4 變異操作

變異算子即以一種較小的概率去對染色體中的某些值進(jìn)行突變。且變異操作能夠很大程度上避免染色體種群陷入局部最優(yōu)而無法跳出的情況，使用傳統(tǒng)變異算子會(huì)很大可能產(chǎn)生不可行解，采用改進(jìn)變異算子個(gè)體內(nèi)部兩位互換的方法［15］。如圖3所示，具體的變異過程為：在父代P1中隨機(jī)產(chǎn)生兩個(gè)變異點(diǎn)，示例中為站點(diǎn)1、4，將站點(diǎn)1、4的位置互換，形成新的子代個(gè)體，將P1和M1進(jìn)行站點(diǎn)順序排序，進(jìn)行行駛距離約束，然后將排序后的個(gè)體進(jìn)行評價(jià)值比較，評價(jià)值大的個(gè)體保留形成子代個(gè)體S1。

3.5 算法步驟

a）將聚類的所有車輛站點(diǎn)進(jìn)行自然數(shù)編碼；

b）采用randperm函數(shù)隨機(jī)生成初始種群；

c）計(jì)算種群中每個(gè)方案的雙目標(biāo)函數(shù)值；

d）將每個(gè)方案的信任度值與行駛距離的比值作為適應(yīng)度值；

e）判斷是否達(dá)到迭代次數(shù)，是則輸出最優(yōu)解，算法終止；否則跳轉(zhuǎn)步驟f）；

f）進(jìn)行錦標(biāo)賽選擇算子、隨機(jī)片段交叉、兩位互換變異，進(jìn)行行駛距離約束判斷，生成子代種群，計(jì)算子代種群總評價(jià)值，并采用精英保留策略將子代最優(yōu)個(gè)體與父代比較，保留優(yōu)良個(gè)體，跳轉(zhuǎn)步驟e）。

算法的主要流程如圖4所示。

4 實(shí)驗(yàn)分析

本文所用數(shù)據(jù)為北京市2020年6月9日至15日新發(fā)地周邊地區(qū)的營運(yùn)車輛數(shù)據(jù)，對車輛的起始點(diǎn)進(jìn)行K-means聚類，提取出各站點(diǎn)信息，結(jié)果如圖5所示，各站點(diǎn)的信息如表1所示，終點(diǎn)站點(diǎn)為北京南站。對各站點(diǎn)乘車人的用戶偏好ω和信任度權(quán)重θ進(jìn)行假設(shè)，如圖6所示。

采用MATLAB R2017b軟件編程計(jì)算，實(shí)驗(yàn)參數(shù)設(shè)置為：種群規(guī)模為20，最大迭代次數(shù)為50，交叉概率為0.9，變異概率為0.1，經(jīng)過迭代進(jìn)化后，得到最終的車輛合乘線路，結(jié)果如圖7所示。

選取差分進(jìn)化算法（DE）和迭代局部搜索算法（ILS）與本文算法進(jìn)行對比，差分進(jìn)化算法中的參數(shù)根據(jù)文獻(xiàn)［1］設(shè)置，交叉率CR為0.1，縮放因子F為0.7。在相同最大迭代次數(shù)下，輸出結(jié)果得到最優(yōu)車輛合乘線路規(guī)劃的方案以及方案的總行駛距離Ddist、總信任度值Strust和總評價(jià)值Sc，如表2所示。

當(dāng)僅考慮距離優(yōu)化而不考慮信任優(yōu)化時(shí)，與本文同時(shí)考慮距離和信任優(yōu)化的模型相比，在相同的實(shí)驗(yàn)參數(shù)設(shè)置下進(jìn)行求解，實(shí)驗(yàn)結(jié)果如表3所示。

由表2可知，本文算法與ILS和DE算法相比，在總評價(jià)值方面，本文算法求解的總評價(jià)值更高，最優(yōu)合乘線路方案2→7→8→11、1→5→6→11、3→4→11、9→10→11更優(yōu)。在距離成本和信任水平方面，相較于ILS算法，本文算法增加了107 km的距離成本，但是提高了整體的信任水平；相較于DE算法，本文算法在信任水平一樣的基礎(chǔ)上，距離成本節(jié)省了338 km。

由表3可知，在總行駛距離方面，本文模型的總行駛距離為41.67 km，僅考慮距離優(yōu)化模型的總行駛距離為35.5 km，相比之下，本文的距離成本增加了14.8%。在總信任度方面，本文模型的總信任度為3.874，是僅考慮距離優(yōu)化模型的總信任度1.177的3.3倍，信任水平明顯提高。

從合乘時(shí)每一輛車的角度出發(fā)，由圖8可知，本文算法與ILS算法求解的結(jié)果相比，車輛1的出行距離和信任度值的結(jié)果相同；車輛2的出行距離遠(yuǎn)3.55 km，信任度值低1.186；車輛3的出行距離近1.46 km，信任度值高0.862；車輛4的出行距離近2.02 km，信任度值高0.572。綜上所述，本文算法的求解結(jié)果，車輛1效果一樣，車輛3、4的效果更好，而車輛2的效果較差。因?yàn)椴煌丝陀胁煌挠脩羝忙兀玫偷某丝蛯铣说慕蛹{程度低，偏好低的乘客分配到車輛2中，其他車輛的信任水平提高，整個(gè)合乘系統(tǒng)的信任水平也相對提高。

同理，本文算法與DE算法求解的結(jié)果相比，車輛1、2效果一樣；車輛3行駛距離較遠(yuǎn)，但信任水平較高；車輛4信任水平較低，但行駛距離較近。由表2綜合來看，在整個(gè)合乘系統(tǒng)中，本文算法計(jì)算出來的總行駛距離更短，信任水平相同，因此總評價(jià)值更高，合乘方案更優(yōu)。

由圖9可知，合乘下的總行駛距離要小于非合乘時(shí)的總行駛距離，合乘模式比非合乘模式不僅提高了車輛利用率，減少了車輛總行駛距離，同時(shí)提高了乘客合乘時(shí)的信任程度，提高了合乘的舒適性。

5 結(jié)束語

基于傳統(tǒng)的線路規(guī)劃問題，提出了車輛合乘的線路規(guī)劃方案，并在要求總行駛距離短的同時(shí)，考慮了合乘的信任水平，提高合乘時(shí)的舒適度，根據(jù)模型特點(diǎn)，采用改進(jìn)遺傳算法進(jìn)行模型求解，獲得最優(yōu)的合乘線路。在算法對比中，改進(jìn)遺傳算法求得的合乘線路更滿足模型的需求，相較于僅考慮距離優(yōu)化的模型，本文模型雖然增加了少部分的距離成本，但極大地提升了信任水平，在兼顧了車輛總行駛距離的同時(shí)保障了較高的乘客合乘信任水平。

本文實(shí)驗(yàn)分析中路網(wǎng)和站點(diǎn)規(guī)模較小且乘客信任方面的相關(guān)參數(shù)為假設(shè)參數(shù)，未來可以從路網(wǎng)規(guī)模的角度和從乘客真實(shí)信任關(guān)系的角度出發(fā)，結(jié)合現(xiàn)實(shí)進(jìn)一步探究。

參考文獻(xiàn)：

［1］鄭建國，李園園. 基于改進(jìn)差分進(jìn)化算法的出租車合乘問題研究 ［J］. 交通運(yùn)輸系統(tǒng)工程與信息，2018，18（1）： 121－126，157. （Zheng Jianguo，Li Yuanyuan. Research on taxi sharing problem based on improved differential evolution algorithm ［J］. Journal of Transportation Systems Engineering and Information Technology，2018，18（1）： 121－126，157.）

［2］楊慧潔. 關(guān)系在拼車中的作用 ［D］. 武漢： 華中科技大學(xué)，2013. （Yang Huijie. The impact of relationship on carpool ［D］. Wuhan： Huazhong University of Science and Technology，2013.）

［3］Chou S K，Jiau M K，Huang S C. Stochastic set-based particle swarm optimization based on local exploration for solving the carpool service problem［J］. IEEE Trans on Cybernetics，2016，46（8）： 1771－1783.

［4］Hou Liwen，Li Dong，Zhang Dali. Ride-matching and routing optimi-sation： models and a large neighbourhood search heuristic ［J］. Transportation Research Part E： Logistics and Transportation Review，2018，118（10）： 143－162.

［5］Huang S C，Jiau M K，Lin C H. A genetic-algorithm-based approach to solve carpool service problems in cloud computing ［J］. IEEE Trans on Intelligent Transportation Systems，2015，16（1）： 352－364.

［6］Lin Jingjie，Huang S C，Jiau M K. An evolutionary multiobjective carpool algorithm using set-based operator based on simulated binary crossover［J］. IEEE Trans on Cybernetics，2018，49（9）： 3432－3442.

［7］楊志家，王子，汪揚(yáng)，等. 車輛合乘問題的兩階段分布式估計(jì)算法 ［J］. 交通運(yùn)輸系統(tǒng)工程與信息，2016，16（2）： 164－169. （Yang Zhijia，Wang Zi，Wang Yang，et al. Two-stage estimation of distribution algorithm to solve multi-vehicle carpooling problem ［J］. Journal of Transportation Systems Engineering and Information Technology，2016，16（2）： 164－169.）

［8］劉文彬，楊波，鐘敏娟. 考慮用戶偏好的啟發(fā)式動(dòng)態(tài)共乘匹配算法 ［J］. 計(jì)算機(jī)應(yīng)用研究，2022，39（1）： 75－79. （Liu Wenbin，Yang Bo，Zhong Minjuan. Heuristic dynamic ridesharing matching algorithm considering user preferences ［J］. Application Research of Computers，2022，39（1）： 75－79.）

［9］He Feng，Yu Sengbin，He Ruichun，et al. Research on optimization model of taxi-carpooling expenses based on the passengers’persona-lized demand ［C］// Proc of International Conference on Transportation Information and Safety. Piscataway，NJ： IEEE Press，2015： 246－249.

［10］張薇，何瑞春，肖強(qiáng)，等. 考慮乘客心理的出租車合乘決策方法研究 ［J］. 交通運(yùn)輸系統(tǒng)工程與信息，2015，15（2）： 17－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.）

［11］Chaya L，Noam H，Amos A. Human satisfaction as the ultimate goal in ridesharing ［J］. Future Generation Computer Systems，2020，112（2）： 176－184.

［12］Xia Jizhe，Curtin K M，Huang Jiajun，et al. A carpool matching model with both social and route networks ［J］. Computers，Environment and Urban Systems，2019，75（3）： 90－102.

［13］張璽君，張祺瑞，張麗娟，等. 基于改進(jìn)遺傳算法的出租車共乘線路規(guī)劃研究 ［J］. 交通運(yùn)輸系統(tǒng)工程與信息，2019，19（6）： 123－128. （Zhang Xijun，Zhang Qirui，Zhang Lijuan，et al. Taxi sharing route planning based on improved genetic algorithm ［J］. Journal of Transportation Systems Engineering and Information Technology，2019，19（6）： 123－128.）

［14］吳樹新. 基于雙層遺傳算法的城市出租車合乘模型的研究 ［D］. 大連：大連交通大學(xué)，2015. （Wu Shuxin. The research of urban taxi-pooling based on bilevel GA［D］.Dalian：Dalian Jiaotong University，2015.）

［15］李金洋. 基于遺傳算法的網(wǎng)約出租車合乘路徑優(yōu)化模型研究 ［D］. 大連：大連交通大學(xué)，2020. （Li Jinyang. Optimization model of ride-sharing path for taxi online based on genetic algorithm ［D］. Dalian： Dalian Jiaotong University，2020.