考慮匹配可行性的長期合乘問題建模與求解*

郭羽含，胡芳霞

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

1 引言

近年來，我國私家車保有量大幅增長，使出行車輛數(shù)量迅速增加，產生了城市交通擁堵、通行速度減慢、空氣污染和停車困難等問題[1]。公共交通可以有效緩解城市交通擁堵，但其靈活性、舒適度和自由度低于私家車，因此私家車出行仍是迄今為止最受歡迎的通勤方式。然而，私家車占據大量道路通行空間，卻空載率很高，一輛私家車通常只運送1～2 個人。通過車輛合乘可以提高座位利用率并有效減少私家車出行數(shù)量，是一種環(huán)境友好且可持續(xù)的出行方式，對于減少碳排放、停車位需求以及緩解交通壓力具有重要意義。此外，合乘可以減少參與用戶的人均出行成本（比如油費、過路費）以及駕駛交通工具帶來的壓力[2-3]。

車輛合乘（car pooling，CP）又稱共乘或者拼車，是指用戶在出行時，與出行時間和目的地相同或相近的用戶共享車輛，以減少往返于目的地的車輛數(shù)量[3]。實際操作中出現(xiàn)了兩種不同形式的車輛合乘問題。第一種是單次車輛合乘問題（daily car pooling problem，DCPP），即事先知道某一天可用的司機和車輛，問題在于將用戶和司機進行匹配，并確定司機的駕駛路徑，在滿足時間窗和車容量限制的基礎上，最小化服務成本和未分配用戶的懲罰值之和[4-5]。第二種是長期車輛合乘問題（long-term car pooling problem，LTCPP），將參與合乘的用戶分為若干合乘小組，其合乘關系長期保持，每天由組內成員輪流擔任司機，目標是劃分用戶以及確定每組中各成員擔任司機時的駕駛路徑，以最小化每天的行駛總距離，同樣受車容量和時間窗限制[6]。此外，存在兩種車輛合乘問題的變型。在第一個變型中，共享乘車去程的合乘組也將同樣共享返程。在第二個變型中，去程和返程的問題是不同的，需獨立解決。本文研究車輛合乘問題的第二種形式的第一個變型，即長期車輛合乘去程問題。

盡管車輛合乘是減少交通擁堵及其相關誘導效應的有效手段，但相關的研究還處在起步階段。Baldacci等人為組織員工通勤合乘的公司提出了一種基于拉格朗日列生成的精確方法[4]，但Varrentrapp 等人證明了LTCPP 是NP 完全問題[7]，因此精確算法只能處理小規(guī)模問題。對于大規(guī)模問題，無法利用計算機在多項式時間內找出全局最優(yōu)解。因此，為了在可接受的計算時間內獲得較優(yōu)的解決方案，近似算法、啟發(fā)式和元啟發(fā)式算法被設計用于解決車輛合乘問題。例如，Manzini 和Pareschi 提出了一種解決LTCPP 的基于聚類分析的分層方法，用于合乘組的形成以及尋找最優(yōu)的車輛路徑?；谠摲椒ǎ髡哌€介紹一個原創(chuàng)的決策支持系統(tǒng)[8]。Yan等人使用網絡流技術構建一個LTCPP 的模型，并通過拉格朗日松弛算法解決該模型[9]。Hussain 等人設計了一個基于智能體的框架用于求解LTCPP，介紹了溝通、協(xié)商和協(xié)調的概念，并考慮了靈活的活動調度[10]。Filcek等人研究了考慮駕駛員和乘客的不同方面和相互矛盾的偏好的多標準合乘優(yōu)化問題，通過加權函數(shù)聚合所有標準，然后設計了啟發(fā)式規(guī)則匹配合乘組以及應用貪婪算法為所有的合乘組生成最佳的駕駛路線[11]。相近的研究領域，邵增珍等人針對單車輛合乘問題，提出基于匹配度的聚類算法，用于將服務需求分配到具體某一輛車，且實現(xiàn)了車輛及服務需求的雙向優(yōu)選[12]。針對確定性多車輛合乘匹配問題，提出針對服務需求分派的啟發(fā)式聚類算法[13]。此外，已有關于車輛合乘方面的實際應用。Bruck 等人介紹了一家意大利服務公司的實際車輛合乘案例，開發(fā)了一個集成的Web 應用程序，供該公司的員工每天組織合乘人員，使用數(shù)學公式和啟發(fā)式算法尋找可能的合乘方案，結果表明通過合乘可以有效減少CO2排放[14]。Bruglieri 等人[15]介紹了一個實際項目PoliUni-Pool，旨在為大學提供車輛合乘服務。

現(xiàn)有的研究大多只考慮用戶間的地理距離，就近匹配生成合乘組，以最小化所有用戶前往目的地所行駛的路徑距離之和。從社會角度來看，這一目標非常重要，因為它有助于減少污染（排放）和交通擁堵。該目標還與最小化總出行成本相一致，這是用戶選擇合乘的重要考慮因素。但是，以行駛總距離作為單一的優(yōu)化目標，得到的合乘方案往往實際操作中缺乏可行性。因為它忽略了合乘組成員構成、合乘所導致的用戶額外駕駛時間以及用戶的啟程時間和到達時間等。其中，合乘組成員構成是指在一個合乘組中各個成員所具有的各項個體特征的分布和組成情況。經調研發(fā)現(xiàn)，合乘組成員的性別、年齡、社會關系、歷史評價等個體特征是影響用戶參與合乘以及合乘關系長久保持的重要因素。（1）性別：目前，女性出行安全已成為社會關注的焦點，為了降低危險系數(shù)，應盡量使合乘組成員中女性結伴出行，避免出現(xiàn)一名女性單獨與男性合乘。（2）年齡：一般而言，年齡差越小，用戶的觀念和興趣差異越小，溝通和相處越容易，合乘關系更容易長久保持。（3）社會關系：本文只考慮同事關系，優(yōu)先將具有同事關系的用戶分在同一個合乘組，可以降低由陌生人帶來的不確定危險因素。（4）歷史評價：減少匹配到歷史評價較差的用戶，可以有效降低合乘的不穩(wěn)定因素，確保長期的合乘關系。除了需要考慮合乘組成員構成外，合乘所導致的用戶額外駕駛時間以及用戶的啟程到達時間也是影響匹配可行性的重要因素。額外駕駛時間過長、用戶實際啟程到達時間與用戶期望的時間的差距過大會降低用戶合乘的積極性，進而影響合乘關系的長久保持。因此，為了獲得長久穩(wěn)定的合乘關系，考慮匹配可行性是非常必要的。此外，現(xiàn)有的研究在求解大規(guī)模的車輛合乘問題上存在局限性。

針對以上問題，本文基于匹配可行性，構建了帶有車容量和時間窗約束的多目標優(yōu)化模型，并提出了一種有效的分布式聚類蟻群算法（distributed clustering ant colony algorithm，DCAC）用于高效地求解LTCPP。該算法在生成合乘組期間，除了以用戶間地理距離作為分組依據外，還考慮了用戶的性別、年齡、社會關系、歷史評價等個體特征等。此外，該算法應用了Spark編程模型，可以分布式并行地運行在Spark 集群或云計算平臺中，可高效求解大規(guī)模的LTCPP。實驗結果表明DCAC 能為LTCPP 提供高質量的解，并在處理大規(guī)模問題上具有明顯優(yōu)勢。

2 問題定義和數(shù)學模型

2.1 問題定義

在LTCPP中，每位參與合乘的用戶都擁有車輛，且出行時間和目的地相同或相近，問題在于將參與合乘的用戶分為若干個合乘小組，每天輪流由一名用戶駕車依次接載組內其他成員共同前往目的地，其合乘關系長期保持，以最小化所有用戶每日的行駛距離之和，同時受車容量和時間窗限制。LTCPP可以被視為聚類問題和路由問題的組合，即它需要找到相對靠近的合乘組成員，并確定合乘組中每個成員的行駛路線和各成員的接載時間表。圖1 顯示了一個合乘小組每日出行情況。

Fig.1 Example of car pooling圖1 一個合乘組示例

本文使用有向圖G=模擬LTCPP，其中頂點集V=U∪{0}，U表示所有用戶住所的集合，0 表示目的地，有向邊集合E={(i,j)|i∈U,j∈V,i≠j}，頂點間的距離dij作為邊的權值。每個用戶i∈U都有一個可接受的最早啟程時間ei、最晚到達目的地時間ri、理想啟程時間iei、理想到達目的地時間iri、最大駕駛時間Ti、車輛座位數(shù)Qi以及性別gi、年齡ai、公司或單位ci、歷史評分si與之關聯(lián)。

LTCPP 包括劃分用戶形成合乘組及確定合乘組中每個成員的行駛路線和各成員的接載時間表。下面將介紹有效路徑、有效合乘組、有效合乘方案的概念。

例如，合乘小組G=(i1,i2,…,im)，用戶i1作為司機時，駕車依次接載組內成員i2,i3,…,im并到達目的地0，如果滿足車容量和時間窗約束，則P=(i1,i2,…,im,0)為有效路徑。

（1）車容量約束

（2）時間窗約束

時間窗約束包含兩部分內容：①最大駕駛時間約束。路徑P的總行駛時間不能超過。②啟程/到達時間約束。用表示用戶h作為司機時，用戶i的啟程時間（即用戶h接載用戶i的時間）；表示用戶h作為司機時，用戶i的到達目的地時間；tij表示頂點i、j間的行駛時間。則需滿足：

用戶實際啟程時間不早于最早啟程時間：

用戶實際到達時間不晚于最晚到達時間：

相鄰接載用戶的啟程時間之差不小于他們間的行駛時間：

若i1,i2,…,im擔任司機時，均存在有效路徑，則G為有效合乘組。將用戶集合U劃分為各個有效合乘組，即得到一個有效合乘方案。LTCPP 的目標是找到最優(yōu)的合乘方案，以最小化平均每日用戶行駛距離之和。

為了增加匹配可行性以及使合乘關系長久保持，本文除了以降低總行駛距離為目標外，新增以下優(yōu)化目標：

（1）最小化額外駕駛時間。額外駕駛時間是指用戶參與合乘導致的相對于單獨出行所增加的額外駕駛時間。可以被計算為所有用戶額外駕駛時間之和。

（2）最小化實際啟程到達時間與用戶理想時間的差距。該目標可以被計算為所有用戶平均每日實際啟程、到達時間與理想啟程到達時間差之和。

（3）最小化匹配不可行性。匹配不可行性體現(xiàn)在合乘組成員構成，具體考慮的因素有性別、年齡、是否為同事關系。

2.2 數(shù)學模型

2.2.1 集合

U=合乘參與者集合

A=所有有向邊集合

K=所有合乘組集合

2.2.2 參數(shù)

參數(shù)dij、tij、ei、iei、ri、iri、Ti、Qi、gi、ai、ci、si的定義同2.1節(jié)，除此之外，有：

w1=所有用戶平均每日行駛距離之和權重因子

w2=所有用戶平均每日實際啟程到達時間與理想時間差值之和的權重因子

w3=所有用戶擔任司機時的駕駛時間與獨自出行時間差值之和的權重因子

w4=所有合乘組不可行級別之和的權重因子

決策變量：

yik=0-1變量，1表示用戶i在合乘組k中，0表示不在

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

ti=用戶i擔任司機時的駕駛時間

Sk=合乘組k的不可行級別

2.2.3 模型

目標函數(shù)（1）最大限度地降低了用戶每日行駛距離以及匹配的不可行性。它包括（從左到右的順序）平均每日用戶行駛距離之和、所有用戶實際啟程和到達時間與理想狀態(tài)的差距之和、所有用戶參與合乘產生的額外駕駛時間之和以及所有合乘組的不可行級別之和。

2.2.4 約束

（1）合乘組不可行級別約束關系。在計算合乘組的不可行級別時，考慮的因素有性別、年齡、是否同事關系。分別表示從性別、年齡、是否同事關系角度考慮，合乘組k成員組成的不可行級別，值越大，不可行性越高。Sk為這三者之和。具體計算公式如下：

①性別。令mk、fk分別表示合乘k中男性、女性成員數(shù)量，則性別不可行級別可以被計算為當合乘組女性數(shù)量少于男性數(shù)量時，男性數(shù)量與女性數(shù)量的差值。具體計算公式如下：

③同事關系。具體計算公式如下：

合乘組k的不可行級別Sk可以通過的求和得到：

（2）約束（3）確保合乘組人數(shù)滿足車容量約束。

（3）約束（4）確保司機總行駛時間不超過其最大駕駛時間。

（4）約束（5）～（8）確保用戶滿足啟程/到達時間約束。

（5）約束（9）～（11）確保若頂點i（或j）在司機h的駕駛路徑中，則將用戶i（或j）加入合乘組k中。

（6）約束（12）確保用戶或者單獨駕駛前往或者被劃入某一合乘組。

（7）約束（13）～（18）為二進制和非負約束。

3 分布式聚類蟻群算法

LTCPP 是聚類問題和路由問題的組合，其將用戶分為各個合乘組，并為各用戶規(guī)劃最佳行駛路徑以接載組內其他成員共同前往目的地。蟻群算法是一種模仿螞蟻覓食行為的啟發(fā)式算法，最先用于解決旅行商問題（traveling salesman problem，TSP）。與解決TSP 思路類似，讓螞蟻訪問所有的用戶，即完成螞蟻的一次旅行，并在螞蟻旅行訪問用戶期間進行聚類，形成各個合乘組，再通過枚舉法為用戶設計最佳的行駛路徑。當螞蟻完成一次旅行時，便可以得到LTCPP 的一個解。此外，蟻群算法具有并行和分布式的特點，因而可以在Apache Spark分布計算框架進行分布式實現(xiàn)，借助云計算平臺或集群增強其求解效率，使其能更高效地解決大規(guī)模問題。因此，蟻群算法非常適于求解LTCPP，尤其是大規(guī)模的LTCPP。

基于上述思路及作者之前的研究[16]提出了分布式聚類蟻群算法（distributed clustering ant colony algorithm，DCAC）用于求解LTCPP。首先，介紹DCAC的非分布式版本聚類蟻群算法（clustering ant colony algorithm，CAC），算法的主要結構見3.1節(jié)，3.2節(jié)至3.6節(jié)對CAC 每個子過程進行具體闡述，3.7 節(jié)介紹DCAC。

3.1 主要結構

在CAC中，為了指導螞蟻的聚類活動，本文引入了偏好和吸引力的概念。其中，偏好信息用來取代傳統(tǒng)的信息素，偏好和吸引力的詳細定義在3.2 節(jié)。求解過程主要分為兩個步驟：聚類和路由規(guī)劃。聚類是通過螞蟻旅行活動得到分組方案，即定義合乘小組成員；路由規(guī)劃是在得到分組方案后，定義每位用戶擔任司機時的最佳行駛路徑、各合乘成員的啟程到達時間等。

首先，螞蟻隨機選擇一個用戶作為旅行的起點，并建立一個合乘小組。螞蟻之后的行為是基于偏好和吸引力的輪盤賭選擇，它可以訪問一個新用戶，并將其插入到當前的合乘小組，或結束當前的合乘小組，并選擇一個新用戶去開始一個新的合乘小組。當所有的用戶都被螞蟻訪問后，螞蟻的旅行結束。出于降低時間復雜度的考慮，聚類過程中，只檢查車容量約束。然后，根據當前分組方案，進行路由規(guī)劃，在此過程中，進行時間窗約束檢查，對于不滿足時間窗約束的無效合乘組，將其劃分為更小的合乘組直到所有的合乘組都滿足時間窗約束為止。最后，選擇幾個具有最佳適應度的解，應用局部搜索過程進行進一步的優(yōu)化。改進后的解用于更新偏好信息。通過這種機制，聚類經驗總是記憶和更新，以引導未來螞蟻的搜索。CAC的主要結構如算法1描述。

算法1聚類蟻群算法

1.初始化偏好矩陣和吸引力矩陣；

2.While不滿足退出條件do

（1）Fork=1，k≤螞蟻數(shù)量do

聚類：

①選擇新用戶訪問并建立新的合乘小組；

②檢查車容量約束：

If車容量已滿，轉至步驟①；

③基于偏好和吸引力信息以一定的概率選擇接下來的操作：

If 選擇新用戶訪問并加入當前合乘組，然后轉至步驟②；

Else 結束當前合乘小組并轉至步驟①；

Until所有用戶都被遍歷到；

路由規(guī)劃：

④計算每位用戶作為司機時的最佳行駛路徑、行駛時間、各合乘成員的啟程和到達時間。對于在計算過程中發(fā)現(xiàn)的無效合乘組進行劃分，直到所有的合乘組都是有效的；

⑤計算解的適應度；

（2）End for

（3）選擇m個具有最佳適應度的解應用局部搜索；

（4）依據改進后的解結構更新偏好矩陣；

（5）記錄截止目前的最優(yōu)解；

3.End while

4.輸出最優(yōu)解；

其中退出條件設置為：迭代次數(shù)達到最大迭代次數(shù)或者連續(xù)迭代達到一定次數(shù)，最優(yōu)解仍未得到改進，程序終止。

3.2 初始化

CAC 算法的第一步是初始化偏好和吸引力矩陣，本節(jié)將給出偏好和吸引力信息的定義和計算公式，公式中出現(xiàn)的參數(shù)與第2章中介紹的參數(shù)相同。

3.2.1 偏好信息

對于任意用戶i,j∈U都有一個非負值wij與之關聯(lián)，它揭示了將用戶i和用戶j分到同一合乘組的偏好級別。初始偏好值由用戶間的地理距離、時間窗差值、是否為同事關系以及用戶性別、年齡、歷史評價決定，如式（19）所示，其中α，β是調整因子。用戶間的地理距離和時間窗差值越大，它們之間的偏好值越小，被分到同一合乘組的機會也越小。出于匹配可行性考慮，增加用戶與同性、同年齡段、高歷史評價用戶間的偏好值。偏好值以百分比γ增加。例如，依照距離和時間窗得到U1 與U2 間的偏好值w12為0.3，若U1 與U2 同性，w12=(1+γ)×0.3,若U1 與U2 年齡差在10 歲以內，則w12再增加γ。同理，若U2 的歷史評分高于所有用戶的平均分數(shù)，則w12繼續(xù)以百分比γ增加，否則w12保持不變。

對于任一用戶i∈U，都有一個非負值wii與之關聯(lián)，它揭示用戶對與其他用戶分到一起的容忍程度。初始wii值通過計算用戶可額外駕駛時間來評估，如式（20）所示，其中θ是調整因子。用戶可額外駕駛時間越短，他/她的服務區(qū)域越小，因此用戶可能具有較少的合乘成員。

在初始化偏好信息時，需檢查時間窗約束（21）～（28）。如果用戶i擔任司機去接用戶j共同前往目的地，約束（21）和（22）檢查了用戶i和用戶j是否都能滿足到達時間約束。約束（23）檢查對于用戶i到達目的地時間來說，用戶j的接載時間是否太晚。約束（24）保證用戶j居住地在用戶i可服務的區(qū)域內。

相應的，若用戶i與用戶j可以被分在一個合乘組，則分別由用戶i與用戶j擔任司機一次，故同樣的，需檢查用戶j作為司機時的時間窗約束（25）～（28）。

如果用戶i和j不能滿足上述約束，則偏好值wij被設置為0，這意味著用戶i和j不可以被螞蟻聚集在一起。通過這個過程，能夠避免生成多數(shù)無效合乘組。如果所有約束都能滿足，則按照式（19）、式（20）進行初始化。

偏好信息可以被認為是變體信息素信息，可以將它存儲在n×n矩陣中，其中n=|U|。

3.2.2 吸引力信息

使用式（29）和式（30）定義用戶間的吸引力信息ηij。這兩個公式與初始化偏好信息的公式相同，不同的是在初始化吸引力矩陣時，不進行時間窗約束檢查，并且不會在每次迭代后進行更新。當偏好信息收斂到最佳值時，吸引力信息可以為算法提供多樣性。

其中，α、β、γ和θ與式（19）和式（20）相同。

3.3 聚類

初始化之后，螞蟻開始旅行訪問各用戶，并在旅行過程中聚類，形成各個合乘小組。為了避免每次添加用戶到合乘組中都進行時間窗檢查（啟程到達時間約束、最大駕駛時間約束）增加昂貴的時間開銷，在螞蟻旅行過程中，只檢查車容量約束。待螞蟻旅行完成，即得到了一個滿足車容量約束的分組方案，時間窗檢查將在路由規(guī)劃階段進行。圖2 展示了螞蟻旅行產生分組方案的全過程。

首先，螞蟻會隨機選擇一個用戶訪問并開啟一個合乘組，如果合乘組人數(shù)未達到最大車容量，螞蟻會通過輪盤賭選擇訪問下一個用戶并添加到當前合乘組，或者直接結束當前合乘組，選中概率如式（31）、式（32）所示。螞蟻結束當前合乘組后，搜索新用戶以啟動新的合乘組，用戶被選中的概率基于吸引力信息，計算公式如式（34）所示。當所有的用戶都被訪問，則認為螞蟻的旅行完成。

在聚類過程中，螞蟻被賦予在達到車容量之前結束當前合乘組的概率。當合乘組中的現(xiàn)有用戶與其他未訪問用戶具有較低的偏好值時，螞蟻具有很高的概率結束該合乘組。這是因為所有未被訪問的用戶添加到當前合成組都是不經濟的，所以更好的行為是結束聚類，而不是再將一個用戶添加到其中。這種機制在CAC 中是至關重要的，通過它可以避免由于新加入用戶距離過遠而導致合乘組內部旅行成本過高。同時，除了車容量和時間窗約束之外，它是唯一的對合乘組成員數(shù)量進行控制的方式。

式（31）給出了螞蟻選擇新用戶j訪問并將其插入到當前合乘組k中的概率Psjk。式（32）給出了螞蟻結束當前合乘組k的概率Pek。

其中，δjk是用戶j與合乘組k之間的偏好值，通過式（33）計算得到；ηij是用戶i、j之間的吸引值；wii和ηii是用戶i與自身的偏好值和吸引力值；K是合乘組k中現(xiàn)有用戶的集合；H是尚未訪問的用戶集合；a和b是調整參數(shù)。

當螞蟻需要建立一個新的合乘組時，吸引力變得至關重要。在螞蟻結束當前的合乘組后，它將通過輪盤賭選擇一個新用戶開始一個新的合乘組，找到該用戶的概率只受到吸引力的影響。在該過程中，偏好信息被忽略，因為偏好矩陣中的零值將禁用選擇一些用戶并影響完整解構造的概率。

因此，以類似的方式，螞蟻搜索一個新用戶開始一個新合乘組的概率Pnjk被計算為新用戶j與當前合乘組k中現(xiàn)有用戶之間的吸引力之和，如式（34）所示。

Fig.2 Travel process of ant圖2 螞蟻旅行過程

其中，ηij是用戶i和用戶j之間的吸引力值；K是當前合乘組中現(xiàn)有用戶的集合；H是尚未訪問的用戶集合；b是調整參數(shù)，同式（31）、式（32）。

3.4 路由規(guī)劃

得到分組方案后，進行具體的路由規(guī)劃。路由規(guī)劃的目的是確定合乘組中用戶i擔任司機的行駛路徑Ri，或者稱為接載組內其他成員的次序。此外，需要還記錄與行駛路徑Ri相對應的其他信息，如用戶擔任司機時的總駕駛時間disi和時間timi、接載合乘組成員的時間表Ti、到達目的地時間arvi以及用戶是與其他用戶合乘還是單獨出行φi，這些信息在計算解的適應度時會使用，圖3顯示了一個完整的解決方案表述。

Fig.3 Representation of a solution圖3 一個解決方案的表述

當天擔任司機的用戶從其起點出發(fā)，依次接載合乘組內其他成員，共同前往目的地。尋找用戶最佳行駛路徑，該問題可以看作是不閉合的旅行商問題，即指定起點和終點，尋找連接所有點的最短路徑的問題。目前已有多種精確算法（如枚舉法、動態(tài)規(guī)劃法）和啟發(fā)式算法（如貪心算法、蟻群算法）用于求解該問題。在本文環(huán)境下，一輛私家車通常最多可搭載5人，加上目的地，點的個數(shù)不超過6。以6個點為例，該問題的解空間是除起點和終點外的其他4個點的全排列，可行解個數(shù)為24（4?。Ｓ捎谠搯栴}的解空間極小，采用枚舉法便可在很短的時間內得到問題的最優(yōu)解。具體求解過程如下。

為了得到用戶作為司機時的最佳行駛路徑，即行駛距離最短（或時間最少），通過對同一合乘組中的其他成員的接載次序全排列得到全部的行駛路徑，比較各路徑的行駛距離得到最短的行駛路徑，并確定其他的路由信息。例如合乘組G=(U1,U2,U3)，求解U1 擔任司機時的路由信息時，先對U2、U3 進行全排列得到全部行駛路徑P1=(U1,U2,U3,0)、P2=(U1,U3,U2,0)，進一步計算確認最優(yōu)的行駛路徑。得到路由信息后，計算每個解的適應度。

在這個階段，進行時間窗檢查，不滿足時間窗約束的合乘組，通過將其不斷劃分為更小的合乘組直到所有的合乘組都滿足時間窗約束。這些被劃分后的合乘組會在后面的局部搜索中進行改進以得到更優(yōu)分組方案。

3.5 局部搜索

在每次迭代中，待所有螞蟻完成旅行之后，選擇具有最佳適應度的m個解，應用局部搜索過程進行改進，改進之后的解用于更新偏好矩陣。局部搜索包含4種操作，劃分（divide）、合并（merge）、交換（swap）、移動（move）。對每個選定的解，依次執(zhí)行這4種操作。

對于每個操作，首先根據定義的選擇規(guī)則來選擇一個或者幾個合乘組。然后，對選定的合乘組應用該操作，看是否有改進，并且一旦在當前的合乘組中獲得改進，它就移動到下一個選擇的合乘組。當所有選擇的合乘組處理完之后，應用下一個操作。圖4給出了這4種操作改進解的示例，其中具有相同線條形狀的用戶為同一個合乘組。

（1）劃分操作

劃分操作將所選擇的合乘組劃分為兩個合乘組，以降低總出行成本。該操作選擇n%的具有相對較高的內部旅行成本的合乘組，內部旅行成本是不包含用戶與目的地之間的旅行成本的用戶之間的旅行成本。根據每個合乘組的內部旅行成本，通過輪盤賭進行選擇。選擇合乘組i的概率Pi是按式（35）計算的。

其中，incosti是合乘組i的內部旅行費用，K是所有合乘組的集合。然后，對于每個選定的合乘組，該操作嘗試將合乘組i中的任何成員劃分到一個新的合乘組中。如果解得到改進，則確認此舉。

Fig.4 Instance of local search圖4 局部搜索例子

（2）合并操作

合并操作嘗試將任何未達到車容量的合乘組進行合并。對于每個未滿的合乘組，有一個合乘組列表與之關聯(lián)，列表中的合乘組與該合乘組合并后仍滿足車輛容量約束，且按照已在合乘組成員數(shù)量降序排列。然后，從列表的頂部開始，嘗試將合乘組i與列表中的每個合乘組j合并。如果獲得改進，則確認此舉。

（3）交換操作

交換操作嘗試在兩個合乘組中交換兩個用戶。首先選q%的內部旅行成本高的合乘組，選擇方式同劃分操作。對于每個選定的合乘組i，選擇與其重心距離最近的合乘組j。然后，嘗試交換合乘組i中的每個成員與合乘組j中的每個成員。如果獲得改進，則確認此舉。

（4）移動操作

移動操作嘗試將用戶從選定的合乘組移動到非達到車容量的合乘組中。首先選擇k%的合乘組，選擇方式同劃分操作。對于每個選定的合乘組i，選擇與其重心距離最近的非達到車容量的合乘組j。然后，嘗試將合乘組i的每個成員移動到合乘組j中，每次嘗試一個成員。如果獲得改進，則確認此舉。

3.6 偏好信息更新

根據局部搜索改進后的解結構，更新偏好矩陣。在更新偏好值之前，偏好矩陣中的所有權重值wij將以蒸發(fā)速率μ減小，以便擴大在當前迭代中獲得的新偏好信息的影響。對于每個選定解，同一合乘組中的用戶之間的偏好值以值φs更新,φs按式（36）獲得。

其中，favg是整個蟻群解的平均適應度，fs是當前選擇解的適應度。λ是一個加權因子，用于在前面的迭代中保持φs較低的值，以及在后向迭代中保持較高的值，使得螞蟻在開始迭代中更自由地探索解空間。

因此，新的偏好值wij將按照式（37）更新，其中是先前迭代的偏好值，S是所有選定解的集合。

偏好值wii根據式（39）更新。更新是基于合乘組中的車輛的空位級別vi，被計算為用戶i所在合乘組的最小車容量與合乘組中已有用戶數(shù)量的差值，如式（38）。

例如，對于最小車容量為4 個用戶的合乘組，如果合乘組中已有3個用戶，則合乘組中每個用戶的空位級別是1。因此，較高的空位級別表示，與其車容量相比，合乘組的用戶數(shù)量較少，則合乘組中的用戶能夠接受更多的用戶加入合乘組。相反，空位級別越低，合乘組中的用戶對擁有其他合乘成員具有越低容忍水平。

3.7 分布式計算實現(xiàn)

CAC 是群體智能算法，其尋優(yōu)過程具有并行和分布式的特點，因此很容易進行并行化實現(xiàn)。為了克服集中式串行環(huán)境下對大規(guī)模LTCPP求解效率較低的問題，本文提出了基于Spark的CAC的分布式版本，即分布式聚類蟻群（DCAC）。DCAC 應用Spark編程模式，使算法分布式并行地運行在Spark集群或云計算平臺中，增強了對大規(guī)模問題的處理能力。

3.7.1 Apache Spark簡介

Spark 的核心數(shù)據結構是彈性分布式數(shù)據集（resilient distributed datasets，RDD）。它表示一組已分區(qū)、不可變且可并行操作的數(shù)據?？梢砸圆倏v本地集合的方式操作分布式數(shù)據集。生成RDD有三種方法：（1）從外部存儲創(chuàng)建RDD；（2）從數(shù)據集合中創(chuàng)建RDD；（3）從其他RDD 變換獲得新的RDD。RDD 提供兩種類型的操作：（1）轉換操作。轉換操作返回一個新的RDD，并且轉換的RDD 是惰性求值的，也就是說，它僅在使用這些RDD 時進行求值。（2）行動操作。行動操作將最終結果返回給驅動程序或將其寫入外部存儲器。

因此，只需將數(shù)據轉換成RDD，并對RDD 應用轉換和行動操作，即可達到數(shù)據的分布式處理，借用集群的強大計算能力，提高算法的效率。

3.7.2 分布式聚類蟻群算法

每次迭代過程中，各個螞蟻旅行構造解的過程是完全獨立的。因此，該過程可以采用分布式計算，即多個個體同時進行搜索，以提高算法的計算效率。

采用Spark編程模型對CAC算法重新編程，將蟻群封裝為一個RDD，這樣在集群各節(jié)點中就會存儲RDD的各個分區(qū)，即將蟻群分散到集群各節(jié)點，從而達到蟻群搜索過程的并行化。

CAC 算法必須經過多次迭代才能得到最優(yōu)解，每次迭代結束后根據較優(yōu)的解結構更新偏好信息，更新后的偏好信息作為下次迭代中螞蟻聚類的選擇依據。為此采用Spark提供的共享機制，將偏好矩陣作為廣播變量進行廣播，傳遞到集群中的每一個節(jié)點，以供各個螞蟻搜索過程使用。需要注意的是，每次迭代后需要移除舊的偏好信息，重新對更新后的偏好矩陣進行廣播。DCAC 算法主要過程如算法2所示。

算法2分布式聚類蟻群算法

1.設置參數(shù)，初始化偏好矩陣和吸引力矩陣，初始化蟻群Listants

2.使用SparkContext.broadcast()方法對偏好矩陣、吸引力矩陣、用戶數(shù)據、距離表等進行廣播

3.RDDrdd=SparkContext.parallelize(ants)/*將蟻群轉換為RDD*/

4.While 不滿足退出條件do

①RDDsolutions=rdd.map(ant=>solution)/*每只螞蟻獨自旅行得到一個解，旅行過程參考3.3節(jié)*/

②Solutions=solutions.collect()/*將solutions 返回給驅動器程序*/

③選擇s中具有最佳適應度的前m個解，應用局部搜索過程

④根據改進后的這m個解更新偏好矩陣

⑤重新廣播偏好矩陣

⑥記錄截止目前的最優(yōu)解

5.End While

6.輸出最優(yōu)解

4 實驗與分析

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

4.1 實驗環(huán)境

本文算法均由Java語言實現(xiàn)。分別在單機環(huán)境下與集群環(huán)境下進行實驗。用于測試的Spark 集群由11 個節(jié)點組成，1 個節(jié)點作為Master，其余節(jié)點為Worker 節(jié)點，每個節(jié)點軟硬件環(huán)境配置相同。實驗環(huán)境如表1所示。

4.2 參數(shù)設置

算法相關參數(shù)設置如下：種群規(guī)模（螞蟻數(shù)量）為100；初始化偏好矩陣和吸引力矩陣時的調整參數(shù)α=1,β=1,θ=5,γ=0.2；計算輪盤賭選擇概率時的調整參數(shù)a=2,b=1；選擇具有最佳適應度應用局部搜索的個體數(shù)量為10；φs的調整因子λ=0.5；偏好信息蒸發(fā)速率μ=0.9；局部搜索中，劃分操作選擇合乘組占總合乘組的比率n=0.3，合并操作選擇率為1，交換操作選擇率q=0.3，移動操作選擇率k=0.3；計算解的適應度時，各優(yōu)化目標的權重因子w1=1，w2=0.2，w3=0.2，w4=0.2。連續(xù)迭代次數(shù)達到N=10，解未得到改進，或者迭代次數(shù)達到100，程序終止。

Table 1 Experimental environment表1 實驗環(huán)境

4.3 實驗結果

本文模擬了LTCPP 的輸入數(shù)據得到多個實例，其中參與合乘用戶數(shù)量（Size）分別設置為100、200、400、600、800、1 000、1 500、2 000。實例中的用戶分別采用3 種分布方式：集中方式、隨機與集中混合分布以及隨機分布，分別用C-、RC-、R-標識。對這24個實例，運行10次，選擇目標函數(shù)為中位數(shù)的解決方案進行記錄，仿真結果如表2 所示。在表2 中，記錄了每個解決方案中合乘組數(shù)量（Npool）、單獨出行的用戶數(shù)量（Nalone）、私家車數(shù)量減少率（Rcar）、合乘前所有用戶每天的行駛距離之和（Disbefore）、合乘后所有用戶平均每天的行駛距離之和（Disafter）、合乘后行駛距離減少率（Rdis）、平均每位用戶每天實際啟程到達時間與理想時間之差（TGap）、合乘后平均每位用戶每天的額外駕駛時間（Textra）、CAC（未分布式）運行時間（TCAC）、DCAC 5 節(jié)點集群計算時間（T5node）、DCAC 10節(jié)點集群計算時間（T10node）。

Table 2 Experimental results表2 實驗結果

4.4 結果分析

4.4.1 有效性分析

為了觀察DCAC算法的分組效果，本文選取3個不同規(guī)模、不同分布方式的實例分組結果進行了可視化。圖5、圖6、圖7展示了實例C-1、RC-2、R-3的分組結果，其中坐標原點（0,0）代表目的地，具有相同圖案、相同顏色且用虛線連接在一起的用戶為同一個合乘組。

Fig.5 Grouping result(C-1)圖5 分組結果（C-1）

從圖5～圖7可以看出，不管用戶位置屬于哪種分布方式，DCAC算法都有很好的分組效果。距離近的用戶會被分在同一合乘組，這是因為合乘后，用戶的出行成本會降低。位置分散的用戶大多獨自出行（參照圖6），這是為了避免合乘后用戶的駕駛時間過長。這與本文的研究目標相一致。

Fig.6 Grouping result(RC-2)圖6 分組結果（RC-2）

Fig.7 Grouping result(R-3)圖7 分組結果（R-3）

圖8 顯示了各實例合乘后行駛總距離減少率。合乘后行駛總距離能減少60%左右，其中分布集中（C）的用戶合乘后行駛距離減少最多，其次是集中與隨機混合分布（RC），最后是隨機分布（R）?？梢杂^察到，當用戶數(shù)量達到1 600以上，這3種分布方式合乘后減少的行駛距離逐漸接近，這是因為大量的用戶分布在目的地（0,0）周圍km 范圍內，無論哪種分布方式，用戶分布均比較集中。因此分組結果相近，這也反映了算法有較高的穩(wěn)定性。

圖9 顯示了各實例合乘后私家車出行數(shù)量減少率。私家車數(shù)量即為合乘組數(shù)量，單獨出行的用戶也視為一個合乘組。圖9和圖8趨勢很相似，合乘后私家車數(shù)量能減少68%左右，其中分布集中（C）的用戶合乘后私家車減少數(shù)量最多，其次是集中與隨機混合分布（RC），最后是隨機分布（R）。當用戶數(shù)量達到1 600 以上，這3 種分布方式合乘后的私家車數(shù)量減少率相近，原因同上。

Fig.9 Private car reduction rate after car pooling圖9 合乘后私家車減少率

圖10顯示了各實例合乘后的平均每位用戶對比單獨出行時所產生的額外駕駛時間。合乘后，分布集中（C）的用戶以及集中與隨機混合分布（RC）的用戶的額外駕駛時間相近，在6 min 左右，這說明合乘組內部旅行成本在6 min左右。隨機分布（R）的用戶額外駕駛時間相對較高，在7.5 min左右，這是由于用戶分布過于零散所致。

Fig.10 Extra driving time from car pooling圖10 合乘導致的額外駕駛時間

圖11 顯示了用戶平均的實際啟程/到達時間與理想時間的差距。從圖11 可知，用戶平均每日的實際啟程/到達時間與其理想的啟程/到達時間的差值在14 min左右。

Fig.11 Difference between actual departure/arrival time and ideal time圖11 實際啟程/到達時間與理想時間的差距

本文從分組結果、總行駛距離減少率、私家車出行數(shù)量減少率、用戶的額外駕駛時間、用戶實際啟程/到達時間與其理想的啟程/到達時間的差距5個角度進行了分析，以此來驗證算法的有效性。結果表明，實行車輛合乘，所有用戶平均每日的行駛距離之和可以減少60%左右，每日私家車數(shù)量大約能減少70%，平均每位用戶的額外駕駛時間在7 min左右，用戶平均每日的實際啟程/到達時間與其理想的啟程/到達時間的差值在14 min左右。

4.4.2 效率分析

將表2 中相同規(guī)模的3 個測試實例的平均計算時間作為當前問題規(guī)模的計算時間，可以得到計算時間隨著參與合乘用戶數(shù)量增加的變化趨勢，如圖12所示。

Fig.12 Graph of computing time trend圖12 計算時間趨勢圖

從圖12可以觀察到：（1）CAC與DCAC算法均能高效地處理小規(guī)模問題（200人以內），時間在10 s左右。（2）隨著問題規(guī)模的增大（400以上），CAC算法計算時間有明顯的增加趨勢。相比CAC，DCAC 算法增加趨勢更為緩慢，即DCAC 算法在處理中等以上規(guī)模的問題更有優(yōu)勢。（3）當參與合乘人數(shù)達到600以上，10節(jié)點集群計算時間明顯比5節(jié)點集群計算時間少。（4）對于2 000人的實例，10個節(jié)點的集群計算時間相較于5 個節(jié)點集群的計算時間降低了52.4%，相較于CAC的計算時間降低了77.7%。

由于Spark Master 和Worker 節(jié)點之間存在網絡通信開銷以及Master 任務調度開銷，對于小規(guī)模問題（200人以內），分布式計算時間與單機計算時間相差不多。但隨著問題規(guī)模增大，通信時間和任務調度時間所占的時間損耗比例逐步降低，分布式計算的優(yōu)勢開始顯現(xiàn)。對2 000人的實例，10個節(jié)點集群計算時間比單機計算時間降低了77.7%。因此，CAC算法能很好地解決小規(guī)模問題，DCAC算法能更好地處理大規(guī)模問題。

4.4.3 局部搜索性能分析

為了驗證局部搜索過程對算法全局搜索性能的影響，將局部搜索作為可選的操作，分別在局部搜索啟用（ON）和局部搜索禁用（OFF）情況下，對實例進行計算。觀察應用局部搜索過程最優(yōu)解改進比例，其中Ropt表示最優(yōu)解，t表示計算時間（單位為s），實驗結果如表3所示。

Table 3 Local search experimental results表3 局部搜索實驗結果

實驗結果表明，應用局部搜索過程，解的質量得到顯著提升，平均改進達到10.5%。因此，局部搜索過程能極大提高CAC的全局搜索能力。

4.4.4 與經典蟻群算法比較

為了客觀表明CAC 算法的性能，使用經典蟻群算法（ant colony optimization,ACO）對24個測試實例求解，比較兩種算法的求解效率和所提供的解的質量。為了避免局部搜索過程對實驗結果影響，兩種算法均不應用局部搜索過程。為公平起見，實驗參數(shù)保持一致，即螞蟻個數(shù)均為100，程序終止條件均為連續(xù)迭代次數(shù)達到10，解未得到改進，或者迭代次數(shù)達到100，程序終止。表4是程序運行10次的平均結果，其中Ropt表示最優(yōu)解，t表示求解時間（單位為s）。

Table 4 Comparison of experimental results表4 實驗結果對比

由表4 可見，對于較大規(guī)模實例（1 000 人及以上），ACO已無法在可接受的時間（30 min以內）內獲得問題的解。綜合最優(yōu)解的質量和求解時間指標，CAC 明顯優(yōu)于ACO。由CAC 得到的最優(yōu)解比ACO獲得的解平均改進25.7%，并且CAC 的計算時間比ACO的計算時間平均減少53.4%。因此，對于任意規(guī)模的LTCPP，CAC都比ACO具有明顯的性能優(yōu)勢。

5 結論

車輛合乘可以有效減少私家車出行數(shù)量，對于緩解城市交通擁堵，削減停車位需求，減少空氣污染等具有重要意義。針對LTCPP，本文構建了考慮匹配可行性的帶有車容量和時間窗約束的多目標優(yōu)化模型，并提出一種有效的分布式聚類蟻群算法（DCAC）用于高效地求解該問題。實驗結果表明，DCAC可以為LTCPP 提供高質量的合乘方案，合乘后總的行駛距離約減少60%，私家車出行數(shù)量減少68%，且合乘用戶擔任司機時的額外駕駛時間僅在7 min左右，用戶平均每日的實際啟程/到達時間與其理想的啟程/到達時間的差值在14 min 左右。從求解效率來看，DCAC在求解2 000人的大規(guī)模合乘問題時，10個節(jié)點的集群計算時間在3 min 左右，通過與5 個節(jié)點的集群計算時間對比可以得到，繼續(xù)增加集群節(jié)點數(shù)量，可以進一步加快算法的求解速度。因此，本文提出的DCAC 算法可以為LTCPP 提供有效的合乘方案，且在處理大規(guī)模問題上具有明顯優(yōu)勢。