郭羽含，胡芳霞

遼寧工程技術(shù)大學(xué) 軟件學(xué)院，遼寧 葫蘆島 125105

1 引言

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

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

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

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

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

2 問(wèn)題定義和數(shù)學(xué)模型

2.1 問(wèn)題定義

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

Fig.1 Example of car pooling圖1 一個(gè)合乘組示例

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

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

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

（1）車容量約束

（2）時(shí)間窗約束

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

用戶實(shí)際啟程時(shí)間不早于最早啟程時(shí)間：

用戶實(shí)際到達(dá)時(shí)間不晚于最晚到達(dá)時(shí)間：

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

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

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

（1）最小化額外駕駛時(shí)間。額外駕駛時(shí)間是指用戶參與合乘導(dǎo)致的相對(duì)于單獨(dú)出行所增加的額外駕駛時(shí)間?？梢员挥?jì)算為所有用戶額外駕駛時(shí)間之和。

（2）最小化實(shí)際啟程到達(dá)時(shí)間與用戶理想時(shí)間的差距。該目標(biāo)可以被計(jì)算為所有用戶平均每日實(shí)際啟程、到達(dá)時(shí)間與理想啟程到達(dá)時(shí)間差之和。

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

2.2 數(shù)學(xué)模型

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=所有用戶平均每日行駛距離之和權(quán)重因子

w2=所有用戶平均每日實(shí)際啟程到達(dá)時(shí)間與理想時(shí)間差值之和的權(quán)重因子

w3=所有用戶擔(dān)任司機(jī)時(shí)的駕駛時(shí)間與獨(dú)自出行時(shí)間差值之和的權(quán)重因子

w4=所有合乘組不可行級(jí)別之和的權(quán)重因子

決策變量：

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

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

ti=用戶i擔(dān)任司機(jī)時(shí)的駕駛時(shí)間

Sk=合乘組k的不可行級(jí)別

2.2.3 模型

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

2.2.4 約束

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

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

③同事關(guān)系。具體計(jì)算公式如下：

合乘組k的不可行級(jí)別Sk可以通過(guò)的求和得到：

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

（3）約束（4）確保司機(jī)總行駛時(shí)間不超過(guò)其最大駕駛時(shí)間。

（4）約束（5）～（8）確保用戶滿足啟程/到達(dá)時(shí)間約束。

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

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

（7）約束（13）～（18）為二進(jìn)制和非負(fù)約束。

3 分布式聚類蟻群算法

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

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

3.1 主要結(jié)構(gòu)

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

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

算法1聚類蟻群算法

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

2.While不滿足退出條件do

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

聚類：

①選擇新用戶訪問(wèn)并建立新的合乘小組；

②檢查車容量約束：

If車容量已滿，轉(zhuǎn)至步驟①；

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

If 選擇新用戶訪問(wèn)并加入當(dāng)前合乘組，然后轉(zhuǎn)至步驟②；

Else 結(jié)束當(dāng)前合乘小組并轉(zhuǎn)至步驟①；

Until所有用戶都被遍歷到；

路由規(guī)劃：

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

⑤計(jì)算解的適應(yīng)度；

（2）End for

（3）選擇m個(gè)具有最佳適應(yīng)度的解應(yīng)用局部搜索；

（4）依據(jù)改進(jìn)后的解結(jié)構(gòu)更新偏好矩陣；

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

3.End while

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

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

3.2 初始化

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

3.2.1 偏好信息

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

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

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

相應(yīng)的，若用戶i與用戶j可以被分在一個(gè)合乘組，則分別由用戶i與用戶j擔(dān)任司機(jī)一次，故同樣的，需檢查用戶j作為司機(jī)時(shí)的時(shí)間窗約束（25）～（28）。

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

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

3.2.2 吸引力信息

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

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

3.3 聚類

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

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

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

式（31）給出了螞蟻選擇新用戶j訪問(wèn)并將其插入到當(dāng)前合乘組k中的概率Psjk。式（32）給出了螞蟻結(jié)束當(dāng)前合乘組k的概率Pek。

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

當(dāng)螞蟻需要建立一個(gè)新的合乘組時(shí)，吸引力變得至關(guān)重要。在螞蟻結(jié)束當(dāng)前的合乘組后，它將通過(guò)輪盤賭選擇一個(gè)新用戶開始一個(gè)新的合乘組，找到該用戶的概率只受到吸引力的影響。在該過(guò)程中，偏好信息被忽略，因?yàn)槠镁仃囍械牧阒祵⒔眠x擇一些用戶并影響完整解構(gòu)造的概率。

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

Fig.2 Travel process of ant圖2 螞蟻旅行過(guò)程

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

3.4 路由規(guī)劃

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

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

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

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

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

3.5 局部搜索

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

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

（1）劃分操作

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

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

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

（2）合并操作

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

（3）交換操作

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

（4）移動(dòng)操作

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

3.6 偏好信息更新

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

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

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

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

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

3.7 分布式計(jì)算實(shí)現(xiàn)

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

3.7.1 Apache Spark簡(jiǎn)介

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

因此，只需將數(shù)據(jù)轉(zhuǎn)換成RDD，并對(duì)RDD 應(yīng)用轉(zhuǎn)換和行動(dòng)操作，即可達(dá)到數(shù)據(jù)的分布式處理，借用集群的強(qiáng)大計(jì)算能力，提高算法的效率。

3.7.2 分布式聚類蟻群算法

每次迭代過(guò)程中，各個(gè)螞蟻旅行構(gòu)造解的過(guò)程是完全獨(dú)立的。因此，該過(guò)程可以采用分布式計(jì)算，即多個(gè)個(gè)體同時(shí)進(jìn)行搜索，以提高算法的計(jì)算效率。

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

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

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

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

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

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

4.While 不滿足退出條件do

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

②Solutions=solutions.collect()/*將solutions 返回給驅(qū)動(dòng)器程序*/

③選擇s中具有最佳適應(yīng)度的前m個(gè)解，應(yīng)用局部搜索過(guò)程

④根據(jù)改進(jìn)后的這m個(gè)解更新偏好矩陣

⑤重新廣播偏好矩陣

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

5.End While

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

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

本章進(jìn)行了大量的仿真實(shí)驗(yàn)，以驗(yàn)證算法的有效性和效率，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。

4.1 實(shí)驗(yàn)環(huán)境

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

4.2 參數(shù)設(shè)置

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

Table 1 Experimental environment表1 實(shí)驗(yàn)環(huán)境

4.3 實(shí)驗(yàn)結(jié)果

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

Table 2 Experimental results表2 實(shí)驗(yàn)結(jié)果

4.4 結(jié)果分析

4.4.1 有效性分析

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

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

從圖5～圖7可以看出，不管用戶位置屬于哪種分布方式，DCAC算法都有很好的分組效果。距離近的用戶會(huì)被分在同一合乘組，這是因?yàn)楹铣撕?，用戶的出行成本?huì)降低。位置分散的用戶大多獨(dú)自出行（參照?qǐng)D6），這是為了避免合乘后用戶的駕駛時(shí)間過(guò)長(zhǎng)。這與本文的研究目標(biāo)相一致。

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

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

圖8 顯示了各實(shí)例合乘后行駛總距離減少率。合乘后行駛總距離能減少60%左右，其中分布集中（C）的用戶合乘后行駛距離減少最多，其次是集中與隨機(jī)混合分布（RC），最后是隨機(jī)分布（R）?？梢杂^察到，當(dāng)用戶數(shù)量達(dá)到1 600以上，這3種分布方式合乘后減少的行駛距離逐漸接近，這是因?yàn)榇罅康挠脩舴植荚谀康牡兀?,0）周圍km 范圍內(nèi)，無(wú)論哪種分布方式，用戶分布均比較集中。因此分組結(jié)果相近，這也反映了算法有較高的穩(wěn)定性。

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

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

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

Fig.10 Extra driving time from car pooling圖10 合乘導(dǎo)致的額外駕駛時(shí)間

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

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

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

4.4.2 效率分析

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

Fig.12 Graph of computing time trend圖12 計(jì)算時(shí)間趨勢(shì)圖

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

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

4.4.3 局部搜索性能分析

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

Table 3 Local search experimental results表3 局部搜索實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)結(jié)果表明，應(yīng)用局部搜索過(guò)程，解的質(zhì)量得到顯著提升，平均改進(jìn)達(dá)到10.5%。因此，局部搜索過(guò)程能極大提高CAC的全局搜索能力。

4.4.4 與經(jīng)典蟻群算法比較

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

Table 4 Comparison of experimental results表4 實(shí)驗(yàn)結(jié)果對(duì)比

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

5 結(jié)論

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