基于隨機森林與變鄰域下降的車輛合乘求解

郭羽含，胡德甲

遼寧工程技術大學 軟件學院，遼寧 葫蘆島 125105

1 引言

隨著經濟快速發展，人們生活水平日益提高，城市中私家車數量大量增加。隨之帶來的環境污染、交通堵塞以及私家車花費問題日漸嚴重[1]，引領網約車、拼車系統等車輛合乘模式的逐漸興起[2]。生活中上下班拼車、回家拼車以及旅游拼車越來越普遍。車輛合乘是指有車人員和無車人員之間或有車人員與有車人員之間的一種合作形式，費用由合乘組成員共同分擔。隨著私家車數量的持續上升，無車人越來越少，長期車輛合乘應運而生。長期車輛合乘主要是根據大中型城市上班族上下班時間接近、上班地點集中以及居住較分散的現狀以及解決上下班時間交通壓力過大的問題提出的上下班模式，是指具有合乘意愿且乘車路線相近的人們分成同一小組乘坐同一輛車，合乘費用分攤的模式。這種合乘關系是長期合作的關系，可以降低臨時或短期合乘的安全隱患，并減少臨時或短期合乘進行多次匹配所帶來的資源浪費。

合乘問題的研究對于物流優化以及城市交通規劃具有重大意義。國內外學者對合乘路徑規劃、車輛調度以及模型算法等領域研究較多。例如Dakroub等[3]針對小規模車輛合乘問題提出一種改進的遺傳算法高效求解合乘方案；Filcek 等[4]研究考慮司機與乘客之間不同標準多目標合乘優化問題，通過加權函數聚合所有目標，應用貪婪算法為全部合乘組生成最佳行駛路線；宋超超等[5]提出基于吸引粒子群算法解決多車輛合乘問題；邵增珍等[6]提出的兩階段聚類啟發式優化算法解決多車輛合乘問題，第一階段通過提出匹配度概念將多車輛合乘問題轉化為單車輛匹配問題，第二階段基于“先驗聚類”插入思想提高算法效率。對客戶屬性以及滿意度研究較少，現在比較熱門的出行安全事件引起人們重視[2]。何勝學等[7]通過建立考慮性別偏好影響的通勤合乘匹配模型，利用同性同組占優原則進行合乘匹配，分別處理了同性合乘、異性合乘、特別組合三種性別合乘模型，一定程度上提升了用戶滿意度但僅僅考慮了性別單個屬性。過去的研究主要是針對小規模車輛合乘問題的研究[8-10]，He 等[11]通過建立考慮性別偏好影響的通勤合乘匹配模型，利用同性同組占優原則進行合乘匹配，分別建立了同性合乘、異性合乘、特別組合三種性別合乘模型，一定程度上提高了安全系數和提升了用戶滿意度，但該方法僅考慮了合乘人員性別單個屬性，具有一定的局限性。盧佐安等[12]通過考慮客戶滿意度的因素，建立客戶滿意度最大和運輸成本最小雙目標函數優化模型，較好的平衡了客戶滿意度和運輸成本，但過多考慮時間屬性，并沒有對其他因素進行較為全面的考慮。進一步，張玉青[13]提出通過KANO模型對用戶需求進行績效指標分類，根據分類結果，將不同用戶需求進行區別處理，該方法通過了解不同層次用戶需求，識別影響客戶滿意的至關重要的因素，利用KANO模型對屬性進行分類，以車輛合乘用戶進行檢驗，得到了較高的客戶滿意度。王銀虎[14]建立出租車服務水平最高為優化目標，將合乘出租車動態調度拆解成一系列靜態時間點保證出租車司機在一定時間內使得資源以及收入達到最優，進而提出“上下”雙層算法進行優化，上層算法進行調參，下層算法基于上層算法得到參數對模型進行求解。可見，在合乘問題中，為了提高乘客在某一方面的滿意度，側重考慮某一乘客屬性以及乘客滿意度因素，得到的結果均有所提高。對于大規模車輛合乘問題求解不適用，存在求解時間長，得不到較優解以及用戶屬性考慮片面達不到用戶滿意的問題。

針對長期車輛合乘問題（Long-Term Car Pooling Problem，LTCPP），為了最大化用戶對合乘結果的滿意度，需要考慮多個優化目標。本文首先構建了帶有車容量和時間窗約束的多目標優化模型，在將其轉化單目標優化時，權重因子的選擇對優化結果起著至關重要的作用。人為設定權重因子主觀性太強，達不到絕大多數用戶的滿意。因此，本文使用機器學習中決策樹集成算法Bagging模型中的隨機森林算法對歷史合乘數據及用戶滿意度進行分析，并得到各個指標對用戶滿意度的重要性影響，作為對應優化目標的權重。然后，提出了一種求解LTCPP的變鄰域下降（Variable Neighborhood Descent，VND）算法。實驗結果表明，結合隨機森林算法和VND算法能夠高效地為LTCPP提供高質量的解決方案。

2 問題定義和數學模型

對LTCPP問題進行了簡單定義，介紹了數學模型。

2.1 問題定義

LTCPP就是指假設每個參與者都擁有一輛私家車，并且他們的目的地相同或相近，出行時間接近。合乘前概況圖如圖1 所示。每位參與者都有各自的最早出發時間、期望出發時間、最晚到達時間、期望到達時間、年齡、性別、最長駕駛時間以及最大載客量。每位參與者也有獨乘和合乘兩種方式，在滿足每位參與者時間窗和車容量的前提下，將所有用戶分成若干個合乘組（一個合乘組形成后如圖2 所示），每個小組中的合乘者按照輪流駕駛的原則利用算法最小化所有小組出行花費的總和。

圖1 合乘前用戶出行示意圖

圖2 合乘后用戶出行示意圖

2.2 數學模型

2.2.1常量定義

C：參與合乘的用戶集合；

0：目的地；

E：邊集合，

K：合乘組集合；

Xi：用戶i性別，用0、1表示；

Ai：用戶i年齡；

Ti：用戶i所能接受的最長駕駛時間；

Ri：用戶i的車容量；

edti：用戶i的最早出發時間；

qdti：用戶i期望出發時間；

lati：用戶i最晚到達時間；

qati：用戶i期望到達時間；

(xi,xj)：用戶i的地理坐標；

dij：用戶i、j間的距離；

tij：用戶i前往用戶j所需的駕駛時間；

ρ：懲罰系數。

2.2.2變量定義

yik變量表示用戶i是否在合乘組k中，0表示用戶i不在合乘組k中，1表示在。

φi變量表示用戶i出行方式，0 表示用戶i與其他用戶合乘，1表示用戶i單獨出行。

ti變量表示用戶i當司機時的實際駕駛時間。

Agek變量表示合乘組k內成員年齡Ai的平均值。

Xbk變量表示合乘組k的性別懲罰值，同性懲罰值為0，否則為1。

2.2.3目標函數及約束

LTCPP 以最小化所有用戶出行花費最小為優化目標，即最小化所有合乘組出行花費之和。設k為一個合乘組用戶的集合，用戶h(h∈k)為某日合乘組k的司機，用戶h在滿足|k|≤Rh以及用戶i(i∈k)的時間窗的約束下從h出發依次走遍用戶i(i∈k?i≠h)最終到達目的地0即為可行路徑，從所有可行路徑中選擇最優路徑。將所有用戶h(h∈k)的最優路徑長度累加后除以合乘組k的成員數量|k|，即為合乘組k的平均每日出行花費。

此外，為了增加用戶滿意度，還需要最小化用戶實際出發/到達時間與期望的實際出發/到達時間的差距、合乘所產生的額外駕駛時間、用戶年齡與組內平均年齡差值、用戶性別與組內平均性別值差值以及單獨出行用戶數。將多個優化目標的加權和作為目標函數，并通過引入懲罰值來減少單獨出行的用戶數量。目標函數如公式（1）所示，其中，α、β、γ、δ、ε分別為所有合乘組平均每天行駛里程之和、所有用戶實際出發到達時間與期望出發到達時間差值之和、所有用戶擔任司機時實際駕駛時間與單獨出行時間差值之和、所有用戶年齡與組內平均年齡差值之和、所有用戶性別與組內平均性別值差值之和的權重因子。

s.t.

約束（2）確保滿足車容量約束，即合乘小組人數小于等于用戶車容量；約束（3）確保用戶h在合乘小組k中做司機的駕駛時間不超過其最大駕駛時間；約束（4）和（5）確保滿足用戶出發時間約束，即用戶h在合乘小組k中做司機時，確保用戶i的出發時間大于等于其最早出發時間；約束（6）和（7）確保滿足用戶到達時間約束，即用戶h在合乘小組k中做司機時，確保用戶i的到達時間小于等于其最晚到達時間；約束（8）～（10）確保若用戶i（或j）在司機h的行駛路徑中，則用戶i（或j）必須在合乘組k中；約束（11）確保用戶的出行方式一致性；約束（12）～（14）為二進制約束；約束（15）～（17）為非負約束。

3 隨機森林與變鄰域下降

介紹了使用隨機森林算法計算特征重要性的方法，以及求解LTCPP的VND算法。

3.1 隨機森林算法

LTCPP問題屬于多目標優化問題，在將其轉化單目標優化時，權重因子的選擇對優化結果起著至關重要的作用。但現今權重因子的選擇大多憑經驗人為設定，主觀性太強，袁麗莎等[15]提出了一種結合深度神經網絡和隨機森林的手掌靜脈分類新方法，自動提取手掌靜脈特征并進行分類識別，避免了人工選擇特征提取算法的局限性。為了避免人為設定權重因子的主觀性，本文通過隨機森林算法根據歷史合乘組信息以及用戶滿意度，計算出各個特征對用戶滿意度的重要性影響，即采用特征重要性作為對應優化目標的權重因子。

3.1.1決策樹的構造

特征和類別：

特征1(difD) 用戶與合乘組重心的距離；

特征2(difI) 用戶實際出發/到達時間與期望時間的時間差；

特征3(difT) 用戶合乘產生的額外駕駛時間；

特征4(difA) 用戶與合乘組平均年齡的差值；

特征5(sexD) 用戶所在合乘組的性別分布。

這5個特征對應于目標函數中的5個優化目標。

類別用戶對合乘組的滿意度評分，取值為1～10，共10個類別。

收集到歷史合乘組信息后，需要對每個用戶對應的特征值進行計算，得到的特征值及類別將用于后續決策樹模型的訓練，如表1為樣本集示例。

表1 樣本示例

特征值計算過程如下所示。

用(xk,yk)表示合乘組k的重心，則：

用戶i到合乘組k重心的距離difDi：

用戶i實際出發時間與期望出發時間差difDi：

用戶i實際到達時間與期望到達時間差difFi

用戶i實際的與理想的出發到達時間差difIi

用戶i參與合乘產生的額外駕駛時間：

用Agek表示合乘組k組內平均年齡，則：

用戶i與合乘組k平均年齡的差值difAi：

用戶i所在合乘組的性別累加sexSi：

用戶i所在合乘組的成員數量MNi：

用戶i所在合乘組的性別分布sexDi，組內成員全為同性sexDi取值為1，否則為0：

構造決策樹，就需要根據樣本數據集的數據特征對數據集進行劃分，直到針對所有特征都劃分過，或劃分的數據子集的所有數據的類別標簽相同。劃分數據集的原則就是將無序的數據變得更加有序，也就是使數據集的熵值變得更小，而節點特征的選取都可以使數據集的熵值減小，從根節點到子節點選取的依據全都是選擇使熵值變化最大的特征，即選取信息增益最大的特征。

構造決策樹過程如下。

（1）收集數據：收集歷史合乘組信息以及用戶的滿意度評分。

（2）數據預處理：根據合乘組信息計算對應的特征值，得到樣本數據集。決策樹構造算法只適用于標稱型數據，因此，還需要對連續型變量進行離散化處理。

（3）構造模型：構造決策樹模型。

（4）訓練和測試模型：將數據分成訓練集和測試集對決策樹模型進行訓練和測試。

（5）使用模型：將完整的決策樹算法投入接下來的隨機森林。

3.1.2隨機森林

隨機森林是包含多個決策樹的模型，其輸出的類別是由單個樹輸出的類別的眾數而定，因此它要比單個決策樹模型具有更高的分類準確性。此外，隨機森林模型具有能夠輸出特征重要性的特點，本文根據這一特點來確定各優化目標的權重，計算過程如下：

（1）從原始歷史合乘數據集中使用Bootstraping 方法隨機抽取n個訓練樣本，共進行k輪抽取，得到k個訓練集。k個訓練集之間相互獨立，數據點可以有重復。

（2）對于k個訓練集分別訓練出k個決策樹模型。

（3）對于單個決策樹模型，每次劃分是根據信息增益選擇最好的特征進行劃分，直到該節點的所有訓練樣本數據都屬于同一類。

（4）將生成的多棵決策樹組成隨機森林，按多棵樹分類器投票決定最終分類結果。

（5）計算特征重要性。

特征重要性即特征對分類結果的影響比重。特征重要性通常用Gini 指數或者袋外數據錯誤率作為評價指標來衡量。

本文以Gini指數作為衡量標準來計算特征重要性，下面是具體計算過程：

Gini指數又稱基尼不純度，表示樣本集合中一個隨機選中的樣本在子集中被分錯的概率。Gini 指數為這個樣本被選中的概率乘以它被分錯的概率。當一個節點中所有樣本都屬于同一個類別時，Gini指數為零。節點m的基尼指數為：

式中，K為類別個數，pmk表示節點m中隨機選中一個樣本屬于k類別的概率。

特征j在節點i的重要性為選擇特征j對節點m進行一次劃分后Gini 指數差值，劃分后產生新的節點l、r，那么：

集合M表示決策樹i中特征j出現的節點集合，那么特征j在這棵樹上的重要性：

假設隨機森林中有n棵樹，那么特征j的全局重要性為通過特征j在單顆樹中的重要性的累加：

最后，將所有求得的特征重要性做歸一化處理：

3.2 變鄰域下降算法

變鄰域下降（VND）算法是順序地在多個鄰域內搜索的啟發式算法，它的成功在于不同的鄰域結構通常具有不同的局部最小值，因此VND 比一般的局部搜索算法更有可能搜索到全局最優解。VND以隨機或結構化的初始解開始，然后在當前解的當前鄰域內進行探索，如果找到更好的解，則以新的解決方案作為當前解，返回第一個鄰域重復搜索過程，否則進入下一個鄰域探索。當探索完所有鄰域，無法找到比當前解更好的解決方案時，算法停止。算法1展示了VND的偽代碼。

算法1 變鄰域下降算法（VND）

1.構造初始解s

2.定義鄰域結構{N1,N2,…,Nkmax}

3.Fortokmaxby 1

（1）找到s的最佳鄰居解

（2）If//當前解獲得改進

（3）End If

4.End For

5.Returns

基于該算法框架，本文將其用于求解LTCPP，3.2.1小節介紹了初始解的構造方法，3.2.2小節介紹了4種鄰域結構，3.3.3 小節介紹了LTCPP 完整解決方案的求解方法。

3.2.1初始解的構造

相比于隨機生成的初始解，一個設計良好的初始解可以縮短搜索到最優解的時間。因此，本文提出如下方法來產生初始解決方案。

該方法的主要思路是按照用戶的地理分布，每次從用戶集合中選擇相距最遠的兩個用戶分別建立合乘小組，然后將與他們臨近的用戶分配到各自所在的合乘小組中，直至所有用戶都被分配到合乘組為止。初始解構造方法的偽代碼如算法2所示。

算法2 初始解構造方法

1.對所有用戶按照其坐標x+y的值進行排序，排序后的用戶存儲在集合U中

2.pools←{} //合乘小組集合

3.WhileU.size()!=0 do

（1）IfU.size()==1

U.remove(d1)；

pools.add(pool)；

break；

（2）End If

（3）選擇U中排列在第一位的用戶d1←U.get(0)建立一個合乘小組pool1，并將其從集合U中移除

（4）使Cpool1←Rd1-1 表示d1所在合乘組小組還可容納用戶數量

（5）While（Cpool1!=0）&&（U.size()!=0）do

從集合U選擇離d1最近的用戶i加入pool1，并將其從U中移除；

（6）End While

（7）pools.add(pool1)

（8）IfU.size()==0

break

（9）End If

（10）選擇U中排列最后一位的用戶d2←U.get(U.size()-1)建立一個合乘小組pool2，并將其從集合U中移除

（11）使Cpool2←Rd2-1 表示d2所在合乘組小組還可容納用戶數量

（12）While(Cpool2!=0)&&(U.size()!=0) do

從集合U選擇離d2最近的用戶j加入pool2，并將其從U中移除；

（13）End While

（14）pools.add(pool2)

4.End While

5.Returnpools

3.2.2鄰域設計

鄰域N(s)可以定義為鄰居解s′是通過對當前解s應用某種變化得的}，本文設計了4種鄰域結構，分別與分割、2-opt、移動、合并操作相關聯。這4 種鄰域會被順序地進行搜索。

（1）分割鄰域N1

分割鄰域N1(s)是通過對當前解s應用分割操作得到的解的集合。對當前解s中所有合乘組（合乘組成員數量為1 的除外）應用一次分割操作來獲得當前解s的一個鄰居解。分割操作即將一個合乘組分割為兩個新的合乘組，分割時需要考慮所有的可能情況。例如合乘組成員數量為4，則有1、3和2、2兩種分割方式，數字表示分割后新的合乘組成員數量。新的合乘組成員組成也是通過枚舉所有可能的組合找到能使得目標函數降低的分割方式。一旦合乘組找到使得目標函數降低的分割方式，則確認該分割操作，換下一個合乘組應用分割操作。如圖3展示了1、3分割的一個例子。

圖3 分割操作

（2）2-opt鄰域N2

2-opt鄰域N2(s)是通過對當前解s應用兩兩交換操作得到的解的集合。通過將當前解s中的所有合乘組與其他合乘組進行成員兩兩交換來獲得當前解s的鄰居解，該交換操作嘗試合乘組中的所有用戶，一旦交換后使得目標函數降低，則確認該交換，換下一個合乘組應用交換操作。在圖4 中，通過將合乘小組（1）、（2）中的成員進行互換得到新的合乘小組。新的合乘組用戶與合乘組重心的距離更近。

圖4 2-opt操作

（3）移動鄰域N3

移動鄰域N3(s)是通過對當前解s應用移動操作得到的解的集合。通過將當前解s中所有的合乘小組的成員移動到其他的合乘小組來獲得當前解s的鄰居解。移動后的合乘小組仍需滿足車容量約束。嘗試移動合乘組中的每一個用戶至其他合乘組，直到移動后使得目標函數降低，則確認該移動，換下一個合乘組進行移動。在圖5 中，合乘小組（2）中距離其他成員較遠的成員被移動到合乘組（1）中。

圖5 移動操作

（4）合并鄰域N4

合并鄰域N4(s)是通過對當前解s應用合并操作得到的解的集合。通過將當前解s中組員數量未達到車容量的合乘小組進行兩兩合并來獲得當前解s的鄰居解。合并后的合乘小組需滿足車容量約束。嘗試將合乘組與其他每一個未達到車容量的合乘組進行合并，一旦合并后使得目標函數降低，則確認該合并操作，換下一個合乘組進行合并。在圖6中，相距很近的合乘小組（1）、（2）被合并為一個合乘小組。

圖6 合并操作

3.2.3完整解的求解方法

將LTCPP 的解表示為兩層結構。第一層表示用戶的分組情況，第二層表示用戶擔任司機時的具體路由信息。該信息與每個用戶i∈C相關聯，具體包括：用戶i擔任司機的行駛路徑Pi、接載合乘組成員的時間表Ci、行駛里程數disi、行駛時間timi、到達目的地時間arvi以及用戶是與其他用戶合乘還是單獨出行φi。解的結構如圖7所示。

圖7 一個解決方案的表述

通過VND 算法可以得到用戶的分組情況，即得到了解的第一層信息。因此，接下來介紹如何根據分組信息得到LTCPP完整解決方案。

該問題是賦權哈密頓回路最小化問題，即給定n個點以及點與點間的距離，找到一條回路由指定的起點前往指定的終點，經過圖中所有點且只經過一次，要求整個回路的總距離最短。這一問題可以通過枚舉法進行求解，其計算量為(n-2)!。這種精確算法對于大多數問題是不可行的，但在本文中，一個合乘小組的成員數量通常不大于5，因此該問題規模非常小，完全可以使用枚舉法來獲得最優的哈密頓回路。圖8（a）給出了一個計算實例，其中U1、U2、U3、U4 為同一合乘小組，通過對除起點和終點外的其他點的順序進行全排列，可以得到U1 作為司機時所有可能的行駛路徑如圖8（b）所示。路徑1的距離：（6+2+3.5+21）=32.2，類似地，可以得到路徑2、3、4、5、6 的距離分別為：35.5、34、37.5、34.5、35。因此路徑1 為U1 的最佳行駛距離，即R1={U1,U2,U3,U4}，其他第二層解信息可以基于該變量得到。

圖8 哈密頓回路示例

在計算最短哈密頓回路時，進行時間窗檢查，對于不滿足時間窗約束的合乘組，通過將其不斷地劃分為更小的合乘組直到所有的合乘組都滿足時間窗約束。

4 實驗與分析

本章將仿真實驗，以驗證算法的有效性及效率，并對實驗結果進行分析。

4.1 實驗環境

本文所提出的算法均由Java 語言實現。實驗所用的計算機配置為2.7 GHz Intel Core i5CPU，8 GB 內存，操作系統為OS High Sierra 10.13.6。

4.2 實驗數據

由于LTCPP 沒有基準數據集，因此，本文采用如下方法生成測試實例。以坐標原點（0，0）表示目的地，用戶地理坐標x、y取值范圍為[?60，60]，用戶以3種分布方式：集中(C)、隨機(R)、混合(RC)分布在原點周圍，用戶數量分別設置為 100、200、400、600、800、1 000、1 500、2 000。所有測試實例均由程序生成。

4.3 實驗結果

用戶數量（Size）、訓練集比例（Training set）以及測試集比例（Test set）對隨機森林得分（Score）的影響如表2所示，由于隨機森林隨機提取測試集，即使相同的用戶數據、訓練集比例以及測試集比例也會得到不同的實驗結果，每次相同數據進行50 次實驗取平均值得到表中數據，從表中數據可知，訓練集比例以及測試集比例對所構造的森林得分無較大影響，訓練集比例取值為0.6時，森林得分較好；測試集比例不能過小，以免影響測試森林得分，無法公正評估森林準確性。隨著用戶數量的增加，得到的森林越加準確，到最后35 000個數據時，森林得分趨于穩定，所以本文中取35 000 個用戶歷史數據，訓練集比例為0.6，測試集比例為0.4進行實驗。

表2 用戶數量、訓練集測試集結果分析表

選取35 000個用戶歷史數據，測試集比例為0.6，訓練集比例為0.4，進行100 次實驗，因為隨機森林測試集選取的隨機性，每次得到的各項權重因子并不完全相同，取森林得分測試結果高于0.975的實驗，進行平均處理得到各項權重因子。部分實驗結果如表3所示。

通過隨機森林模型對歷史分組數據進行學習，得到各個特征對用戶滿意度的影響權重。其中，特征difD的重要性為0.71，特征difI的重要性為0.14，特征difT的重要性為0.03，特征difA的重要性為0.04，特征sexD的重要性為0.07。特征重要性將作為下一階段采用VND 算法求解LTCPP 時目標函數中各優化目標的權重，即α=0.71，β=0.14，γ=0.03，δ=0.04，ε=0.07。將與文獻[16]中的聚類蟻群算法（Clustering Ant Colony algorithm，CAC）進行對比，該文獻中的各優化目標的權重均由人為設定。實驗結果如表4所示，其中，Size表示用戶數量，Rcar表示合乘后平均每天的出行車輛減少率，該值可以計算為：Rdis表示為合乘后平均每天用戶行駛里程減少率，Din表示平均用戶與合乘組的距離，Ain表示平均用戶與合乘組平均年齡的差值，Rs表示合乘組全為同性成員的比率，Tg表示平均每位用戶每天的實際出發到達時間與理想的時間差，Te表示合乘后平均每位用戶每天的額外駕駛時間，Tc表示算法求解時間，表示CAC算法在5個節點集群上計算時間，表示CAC算法在10個節點集群上計算時間。

表3 權重因子實驗結果

表4 實驗結果

4.4 結果分析

4.4.1有效性分析

為了驗證通過VND 算法得到的合乘方案的有效性，從指標Rcar、Rdis、Din、Ain、Rs、Tg、Te進行驗證。從表1可以看出，用戶參與合乘后平均每天可以減少Rcar=72%的出行車輛，每天總行駛里程減少Rdis=67%。用戶離合乘組重心的平均距離Din=2.4 km，這說明一個合乘組中的成員通常分布在以2.4 km 為半徑的圓形范圍內。用戶與合乘組內平均年齡的差值約為Ain=5歲。合乘組成員性別均相同的概率Rs=26%。用戶每天的實際出發到達時間與理想的時間差Tg=7 min。合乘后平均每位用戶每天的額外駕駛時間Te=7 min。

表5展示了通過VND獲得的合乘方案相較于CAC的改進百分比，值為正表示得到改進，反之，則表示未得到改進。從總體上來看，通過VND獲得的合乘方案，比CAC獲得的合乘方案在各個指標下均有一定程度的改進。其中，Din平均改進17%，這說明VND 得到的合乘方案，合乘組內成員間距離更近。Rs平均改進31%，這說明VND 得到的合乘方案，合乘組內成員性別多為同性。Te平均改進28%，這與Din相一致，合乘組內成員距離越近，則用戶的額外駕駛時間越短。

表5 與CAC對比結果

4.4.2效率分析

圖9 展示了算法運行時間隨用戶數量的增長趨勢。其中CAC為文獻[16]中所提出的算法，DCAC是其在 Spark 上實現的分布式版本，DCAC（5 nodes）表示DCAC 在5 個節點集群上的運行時間，類似地，DCAC（10 nodes）表示集群節點個數為10。

圖9 算法運行時間

從圖中可以看出，兩種算法均隨著用戶數量的增加而增加。但很明顯，VND 算法的運行時間遠低于CAC算法，且VND 算法的增長趨勢要比CAC 算法平緩很多，這說明無論是處理小規模問題還是大規模問題VND 算法都表現出了較優的性能。根據表4 中的實驗結果可以計算得到，VND要比CAC平均節省55%時間。此外，從圖中可以看出，對于用戶數量少于600 的小規模實例，VND 的運行時間低于CAC 和DCAC。但繼續增加用戶數量，集群計算的優勢開始顯現，DCAC 的運行時間要比VND 運行時間短。因此，在計算資源充足的條件，相比較VND，采用DCAC對大規模問題求解具有更高的時間效率。而在單機環境下，VND 要比CAC表現更好。

4.4.3案例分析

為了更好地理解和說明提出的多目標優化模型和求解算法VND 如何為LTCPP 提供好的解決方案，以R-1為例進行案例分析。實例R-1包含100個用戶，用戶地理位置分布如圖10 所示。通過VND 算法獲得的分組結果如圖11所示，其中，具有相同圖案且用虛線連接的同戶被分在同一個合乘組。圖11所展示的分組即為合乘方案第一層信息，接下來再對合乘方案的第二層信息進行分析。

在合乘方案中，U1 單獨出行(φ1=1)，從圖10可以看出，U1 距離其他用戶較遠，若將其與其他用戶分配到同一個合乘組，接載U1 會導致合乘組成員的額外駕駛時間增加，可能會違反用戶的最大駕駛時間約束，或導致目標函數值增加。因此，將用戶額外駕駛時間作為優化目標，可以使得分布過于零散的用戶偏向于單獨出行，旨在提升所有用戶的出行體驗。出于相同的原因，U90、U71、U37 等用戶也將單獨出行。

圖10 R-1地理位置分布

圖11 R-1分組結果

從圖11 可以看出，U38、U75、U94(φ38=φ75=φ94=0)為同一個合乘組，用戶數據如表6 所示。當一個合乘組產生后，VND 算法首先會檢查車容量約束。U38、U75、U94 的車容量均為4，而合乘組成員數量為3，所以沒有違反車容量約束。

表6 用戶數據

然后，為每個用戶計算其擔任司機時的最佳行駛路徑，即求解賦權哈密頓回路最小化問題。按照3.2.3 小節提出的方法，可以得到U38、U75、U94 的最佳行駛路徑。第一天，由U38 擔任司機，最佳行駛路徑為U38-U75-U94，第二天由U75 擔任司機，最佳行駛路徑為U75-U38-U94，第三天由U94 擔任司機，最佳行駛路徑為U94-U38-U75。之后3 人繼續輪流擔任每日的司機。詳細的出發到達時間如圖12所示。

圖12 出發到達時間

在計算用戶最佳行駛路徑，進行時間窗檢查，包括：（1）出發/到達時間窗約束；（2）最大駕駛時間約束。從圖12 可知，U38 每日實際出發時間依次為：6：42、6：48、6：32，其可接受的最早出發時間為6：30，滿足出發時間窗約束。U38 每日實際到達時間依次為：7：25、7：35、7：19，其可接受的最晚到達時間為8：00，滿足到達時間窗約束。U38 與目的地（坐標為（0，0））的距離為，駕駛時間等于43/1=43 min（行駛速度可按照實際情況進行調整）。與U75、U94 合乘后，U38 從自己的位置出發，依次接載U75、U94，再從U94 的位置前往目的地，所花費的時間為47 min，其可接受的最大駕駛時間為63 min，滿足最大駕駛時間約束。同樣的計算和檢驗方法應用于U75 和U94，只要其中有一位用戶沒有滿足時間窗約束的行駛路徑，該合乘組被視為無效合乘組，VND 算法會將該合乘組劃分為兩個小的合乘組，重復該過程，直到所有的合乘組滿足時間窗約束。

接下來從用戶與合乘組的距離、用戶的額外駕駛時間、用戶實際出發/到達時間與期望時間的差值、用戶與合乘組平均年齡的差值以及合乘組用戶性別分布情況來分析該合乘組的優劣。

U38 與合乘組的距離被計算為U38 與合乘組重心的距離，合乘組重心為(8.6,-36.3)，則U38 與合乘組距離為6.8 km，U75 與合乘組的距離為2.3 km，U94 與合乘組的距離為5.5 km，則平均的用戶與合乘組的距離為4.9 km。用戶與合乘組的距離越大，說明合乘組成員間的距離越大，則用戶所在合乘組每天行駛的里程數越多。因此，該值與合乘組每日行駛里程數具有正相關關系。U38 擔任司機時總的駕駛時間為47 min，U75 擔任司機時總的駕駛時間為54 min，U94 擔任司機時總的駕駛時間為55 min，則該合乘組平均每天行駛的里程數為：52 km，該值會作為優化目標納入到目標函數中，以減少合乘組每天行駛的里程數。

U38與目的地（坐標為（0，0））距離為43 km，所需要的駕駛時間為43/1=43 min（行駛速度可按照實際情況進行調整）。與U75、U94 合乘后，U38從自己的位置出發，依次接載U75、U94，再從U94 的位置前往目的地，所花費的時間為47 min。因此，參與合乘后，U38 的額外駕駛時間為4 min。同理，U75 的額外駕駛時間為19 min，U94 的額外駕駛時間為21 min，則平均的用戶的額外駕駛時間為15 min。同樣的，該指標以一定的權重作為優化目標納入到目標函數中，旨在減少用戶額外駕駛時間過長，導致用戶滿意度低。

U38 實際出發/到達時間與其期望的時間（6：35/7：20）的差值約為8 min。U75 實際出發/到達時間與其期望的時間（6：50/7：35）的差值約為8 min。U75實際出發/到達時間與其期望的時間（6：40/7：20）的差值約為9 min。平均的用戶實際出發/到達時間與期望時間的差值為8 min。同樣的，該指標以一定的權重作為優化目標納入到目標函數中，旨在縮小用戶出發/到達時間與其期望實際的差距，增加用戶滿意度，提升用戶體驗。

此外，組內平均年齡為32，U38 與組內平均年齡的差值為0，U75 與組內平均年齡的差值為5，U94 與組內平均年齡的差值也為5，則平均的用戶與合乘組的年齡差為3。該指標同樣以一定的權重作為優化目標納入到目標函數中，旨在減少合乘組內用戶的年齡差。該合乘組的成員全為男性，性別分布合理，在目標函數中為0，若為其他性別分布，則在目標函數具有一定的懲罰值，旨在增加同性別用戶被分在一個合乘組的幾率，這是出于用戶出行安全的考慮。

需要說明的是，該案例中用戶與合乘組的距離和用戶的額外駕駛時間比表4中的對應指標的平均值大，這是由于實例R-1中的用戶屬于隨機分布，相對于集中分布和混合分布，隨機分布的用戶地理位置過于分散，用戶間距離較大，從而導致這兩個值增大。

鑒于篇幅限制，以合乘組(U38、U75、U94)為例進行了分析，其他合乘組分析方法相似。

5 結論

目前，我國城市交通擁堵嚴重，并由此導致一系列問題，嚴重影響了城市居民的生活質量。而車輛合乘可以在現有資源條件下有效減少私家車出行數量，從而緩解交通擁堵問題。針對LTCPP，本文首先構建了基于用戶滿意度的帶有車容量和時間窗約束的多目標優化模型，并通過隨機森林算法確定各優化目標的權重，旨在解決人為設定權重因子主觀性太強的問題。然后，提出了解決LTCPP的VND算法。實驗結果表明，采用VND算法獲得的解決方案，每日私家車出行量可以減少72%，每日行駛的總里程數減少67%，合乘成員通常分布在半徑為2.4 km的圓形范圍內，合乘組成員平均年齡差在5 歲左右，同性被分到同一個的概率在26%，用戶實際出發到達時間與期望的時間差7 min 左右，用戶需額外駕駛時間在7 min左右。從時間效率上來看，VND算法相較于CAC 可以節省55%的時間。因此，結合隨機森林算法和VND算法能為LTCPP高效得提供高質量的解決方案。