車(chē)輛合乘問(wèn)題的分布式復(fù)合變鄰域搜索算法*

郭羽含，伊 鵬

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

1 引言

近年來(lái)，隨著國(guó)民收入和購(gòu)買(mǎi)力的增長(zhǎng)，駕駛私家車(chē)已成為人們的主要出行方式。截至2016年末，我國(guó)私人汽車(chē)保有量已達(dá)16 559萬(wàn)輛[1]，私人汽車(chē)保有量增長(zhǎng)的同時(shí)也帶來(lái)了交通擁堵、環(huán)境污染等負(fù)面問(wèn)題。隨著互聯(lián)網(wǎng)與共享經(jīng)濟(jì)的發(fā)展，車(chē)輛合乘的出行方式逐漸在大中型城市涌現(xiàn)，車(chē)輛合乘問(wèn)題也引起了學(xué)術(shù)界的關(guān)注[2-4]。早期的車(chē)輛合乘模式以出租車(chē)搭載多名路途相近乘客的形式出現(xiàn)。這種模式雖然滿足了更多乘客的出行需求并在一定程度上降低了其出行成本，但僅依靠這種合乘模式并不能從根本上減少私人汽車(chē)的出行數(shù)量以緩解其引起的社會(huì)問(wèn)題。針對(duì)大中型城市人口工作地點(diǎn)集中但居住分散的特點(diǎn)，本文提出一種合乘關(guān)系較為固定且長(zhǎng)期保持的車(chē)輛合乘模式，該出行模式不但可以減少私家車(chē)的出行率，減緩交通壓力和環(huán)境污染，還可在較大程度上降低人們的出行花費(fèi)。

目前國(guó)內(nèi)外關(guān)于車(chē)輛合乘問(wèn)題的研究有：邵增珍等人利用匹配度聚類(lèi)算法求解單一車(chē)輛的合乘問(wèn)題，但未涉及多車(chē)輛合乘[5-6]；周和平等人對(duì)合乘者的費(fèi)用分擔(dān)與路徑選擇同時(shí)進(jìn)行優(yōu)化，綜合考慮駕駛員與出行者利益,以出行者時(shí)間費(fèi)用成本最小為目標(biāo)函數(shù),設(shè)計(jì)相應(yīng)的遺傳算法對(duì)其進(jìn)行求解[7]；Li等人將車(chē)輛合乘優(yōu)化問(wèn)題轉(zhuǎn)化為基于圖的模型問(wèn)題，利用貪婪集合覆蓋算法來(lái)解決合乘問(wèn)題[8]；Armant等人對(duì)于車(chē)輛合乘問(wèn)題提出三種混合整數(shù)規(guī)劃模型[9]；Kleiner等人通過(guò)引入個(gè)人偏好與價(jià)格競(jìng)爭(zhēng)機(jī)制來(lái)促使人們進(jìn)行車(chē)輛合乘，但由于其系統(tǒng)限制，一位司機(jī)只能與一位乘客合乘，且缺乏大規(guī)模的實(shí)驗(yàn)論證其性能[10]；Simonin等人通過(guò)建立一個(gè)互聯(lián)網(wǎng)系統(tǒng)來(lái)解決人們動(dòng)態(tài)合乘的需求[11]；Rahimi-Vahed等人提出的路徑重新鏈接算法用以解決合乘問(wèn)題，但對(duì)于規(guī)模較大的合乘問(wèn)題求解效率不高[12]。綜合來(lái)看，現(xiàn)有研究的模型和算法[13-14]在高效求解大規(guī)模多車(chē)輛合乘問(wèn)題上存在局限性。

對(duì)于合乘關(guān)系長(zhǎng)期保持的長(zhǎng)期車(chē)輛合乘問(wèn)題（long-term carpooling problem，LTCPP），本文提出了涵蓋車(chē)容量和時(shí)間窗約束的全面數(shù)學(xué)模型[15-16]，并在變鄰域搜索的基礎(chǔ)上提出了一種基于分布式的復(fù)合變鄰域算法。本文將變鄰域算法與分布式計(jì)算相結(jié)合，可以高效求解大規(guī)模車(chē)輛合乘問(wèn)題，并有效避免了由于變鄰域算法隨機(jī)性而產(chǎn)生質(zhì)量較差優(yōu)化結(jié)果的問(wèn)題。實(shí)驗(yàn)結(jié)果表明該算法求解質(zhì)量高且求解速度快，對(duì)于大規(guī)模的算例具有較好的實(shí)用性。

2 車(chē)輛合乘問(wèn)題數(shù)學(xué)模型

2.1 問(wèn)題定義

長(zhǎng)期車(chē)輛合乘問(wèn)題中每位合乘參與者都擁有車(chē)輛，且具有相近的目的地。每位合乘參與者與其他合乘參與者互相組成合乘小組，組內(nèi)用戶每天輪流接送組內(nèi)其他用戶抵達(dá)目的地。問(wèn)題的目標(biāo)是在滿足合乘參與者約束的條件下將其分配到若干個(gè)合乘小組中，最終得到總出行成本最低的合乘方案[17]。合乘小組中司機(jī)接送組內(nèi)其他用戶的路徑概況如圖1所示。

Fig.1 Overview diagram of carpooling group route圖1 合乘小組路徑概況圖

2.2 合乘模型符號(hào)定義

2.2.1 常量定義

數(shù)學(xué)模型中常量如表1所示。

Table 1 Constants used by model表1 模型使用的常量

2.2.2 變量定義

數(shù)學(xué)模型中變量如表2所示。

Table 2 Variables used by model表2 模型使用的變量

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

LTCPP以用戶總出行成本作為優(yōu)化目標(biāo)，合乘小組中每位用戶作為司機(jī)時(shí)，該用戶可以有多種接送順序接送組內(nèi)其他用戶，因此對(duì)應(yīng)著有多條行車(chē)路徑，本文通過(guò)路徑規(guī)劃算法對(duì)合乘小組中每位作為司機(jī)的用戶規(guī)劃出一條最短的接送路徑及相應(yīng)的接送順序，為了鼓勵(lì)用戶與其他用戶合乘并減少用戶單獨(dú)駕車(chē)的可能性，在此引入了懲罰因子ρ（1＜ρ＜2），未與其他用戶合乘的用戶將會(huì)受到懲罰付出更多的費(fèi)用。合乘小組Pk總費(fèi)用cost(Pk)定義如下：

則有目標(biāo)函數(shù)：

其中，fLTC為所有合乘小組的出行成本之和。

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

長(zhǎng)期車(chē)輛合乘問(wèn)題的數(shù)學(xué)模型表示如下：

式（3）和式（4）表示司機(jī)d將用戶i和用戶j加入到合乘小組P中；式（5）表示連續(xù)性約束；式（6）表示單獨(dú)出行的用戶需受到懲罰；式（7）和式（8）表示合乘小組載客量約束；式（9）和式（10）表示合乘小組P最晚到達(dá)目的地時(shí)間約束；式（11）表示合乘小組中司機(jī)d的行駛時(shí)間約束；式（12）表示司機(jī)接送用戶的時(shí)間約束；式（13）～（15）為二進(jìn)制完整約束；式（16）和式（17）為非負(fù)約束。

3 LTCPP合乘方案

3.1 合乘方案表述

LTCPP合乘方案表述的目的是在待求解問(wèn)題和算法生成的解決方案之間建立一個(gè)完整的映射。LTCPP的合乘方案包括將用戶劃分到各個(gè)合乘小組，并在組內(nèi)用戶作為司機(jī)時(shí)描述司機(jī)接送組內(nèi)其他用戶的路徑。鑒于該問(wèn)題涉及分組方式和行駛路徑，因此合乘方案需要能夠表述組內(nèi)每個(gè)用戶的路徑信息。合乘方案設(shè)計(jì)為兩層。第一層顯示各個(gè)合乘小組的用戶信息，而第二層則記錄組內(nèi)用戶作為司機(jī)時(shí)接送組內(nèi)其他用戶的路徑。此外，在第二層中，還顯示與組內(nèi)每個(gè)用戶相關(guān)聯(lián)的一些其他信息，例如總行駛時(shí)間和距離，當(dāng)該用戶作為司機(jī)時(shí)接送其他用戶的時(shí)間，以及該用戶是否與其他用戶合乘。

在第二層表述組內(nèi)每位用戶i作為司機(jī)時(shí)的相關(guān)信息，其中包括用戶i的行駛路徑Ri、出發(fā)時(shí)間及到達(dá)其他用戶所在地點(diǎn)的時(shí)間Ti、是否與其他用戶合乘φi、行駛路程disi、行駛時(shí)間ti及到達(dá)目的地時(shí)間avti。合乘方案表述示意圖如圖2所示。

Fig.2 Presentation diagram of carpooling solution圖2 合乘方案表述圖

3.2 初始合乘方案

為了得到質(zhì)量較高的初始合乘方案，本文采用了兩步法。

第一步選擇n個(gè)用戶來(lái)構(gòu)建n個(gè)合乘小組。此n個(gè)用戶作為每個(gè)合乘小組的初始司機(jī)，其余未被選擇為司機(jī)的用戶將被分配至以上合乘小組中。具體步驟如下。

所有用戶按照隨機(jī)順序放入用戶集合中。從列表中隨機(jī)選擇用戶a來(lái)構(gòu)建合乘小組，然后從用戶集合中刪除用戶a和距離用戶a最近的m個(gè)用戶，其中m為通過(guò)對(duì)所有用戶的搭載人數(shù)求平均值而獲得的整數(shù)，如式（18）所示。

然后，從用戶集合的剩余用戶中隨機(jī)選擇用戶b來(lái)構(gòu)建另一個(gè)合乘小組，繼而將用戶b和用戶集合中距離用戶b最近的m個(gè)用戶移除。當(dāng)所有用戶從用戶集合中刪除時(shí)，該過(guò)程結(jié)束。

這種機(jī)制避免了選擇兩個(gè)距離過(guò)近的用戶構(gòu)建兩個(gè)合乘小組，從而保證合乘小組中用戶的均勻分布，為下一步算法提供了良好的基礎(chǔ)。

在第二步中，本研究設(shè)計(jì)了一種Regret Insertion算法。該算法針對(duì)在第一步中未被選擇為司機(jī)的所有用戶的Regret值進(jìn)行計(jì)算，以便將這些用戶分配到各個(gè)合乘小組中。

首先，通過(guò)式（19）計(jì)算每一位在第一步中未被選擇為司機(jī)的用戶i和被選為司機(jī)的用戶j之間的距離dij。

其中，(xi，yi)，(xj，yj)分別為用戶i和用戶j的坐標(biāo)；ei和ej為用戶i和用戶j的最早出發(fā)時(shí)間；tij為用戶i到用戶j的行駛時(shí)間；α和β為調(diào)整參數(shù)。

然后，計(jì)算用戶i的Regret值，即上文中計(jì)算的第二短距離dij和最短距離dik之差，如等式（20）所示。

該算法在分配用戶時(shí)優(yōu)先分配Regret值最大的用戶，避免將其分配到第二近的司機(jī)所在的合乘小組，使得合乘方案的質(zhì)量產(chǎn)生較大幅度的降低。該分配過(guò)程受合乘小組車(chē)容量約束限制，用戶不能被分配到超出車(chē)容量限制的合乘小組中，如果離用戶最近的司機(jī)所在的合乘小組人數(shù)達(dá)到車(chē)容量限制，則依次嘗試將該用戶分配至下一個(gè)最近的司機(jī)所在的合乘小組。當(dāng)所有未選擇的用戶均被分配至合乘小組中或者不可能再將任何未選擇用戶分配到任何合乘小組時(shí)，該過(guò)程停止分配，未被分配的用戶被視為單獨(dú)駕駛。

為降低算法的復(fù)雜度，在用戶分配階段未檢查行駛時(shí)間和時(shí)間窗約束。因此，需要在分配結(jié)束后對(duì)各合乘小組進(jìn)行約束驗(yàn)證及修復(fù)以確保初始合乘方案中所有的合乘小組均滿足行駛時(shí)間和時(shí)間窗約束。如果合乘小組違反行駛時(shí)間和時(shí)間窗約束，將被修復(fù)為符合約束且出行成本增長(zhǎng)最少的兩個(gè)或多個(gè)合乘小組。修復(fù)過(guò)程具體如下，其中n的初始值為2。

（1）選出該合乘小組中n個(gè)相互距離最遠(yuǎn)的用戶作為新的n個(gè)合乘小組的司機(jī)。

（2）將其余用戶按照Regret Insertion算法分配到新的合乘小組中，并執(zhí)行步驟（3）操作。

（3）若新的合乘小組滿足行駛時(shí)間和時(shí)間窗約束，修復(fù)過(guò)程結(jié)束。否則對(duì)該合乘小組進(jìn)行重新修復(fù)，將n的值加1，并執(zhí)行步驟（1）操作。

獲取初始合乘方案的算法設(shè)計(jì)如下所示：

4 變鄰域搜索

為了使變鄰域搜索算法適應(yīng)本文特定的長(zhǎng)期車(chē)輛合乘問(wèn)題，需定義針對(duì)本問(wèn)題的鄰域結(jié)構(gòu)，建立適用于合乘方案的搜索過(guò)程，并且利用Spark分布式平臺(tái)將算法部署到多臺(tái)計(jì)算機(jī)上進(jìn)行并行計(jì)算。

4.1 鄰域設(shè)計(jì)

根據(jù)長(zhǎng)期車(chē)輛合乘問(wèn)題的特點(diǎn)，本研究設(shè)計(jì)了四種不同的鄰域搜索Nk(S)，四種鄰域搜索分別為混合鄰域（mixed neighborhood）N1、鏈?zhǔn)洁徲颍╟hain neighborhood）N2、分割鄰域（divide neighborhood）N3和合并鄰域（merge neighborhood）N4。其中混合鄰域N1與鏈?zhǔn)洁徲騈2為主優(yōu)化鄰域，同時(shí)引入分割鄰域N3和合并鄰域N4以防止混合鄰域N1與鏈?zhǔn)洁徲騈2陷入局部最優(yōu)，這四種鄰域互相補(bǔ)充，彌補(bǔ)其他鄰域的不足，通過(guò)迭代優(yōu)化逐步提升合乘方案的質(zhì)量。DVNS-LTCPP（distributed variable neighborhood search for long-term carpooling problem）算法鄰域的具體定義如下：

（1）混合鄰域N1?；旌相徲蛲ㄟ^(guò)交換兩個(gè)合乘小組中的用戶達(dá)到降低兩個(gè)合乘小組總出行成本的目的。首先計(jì)算合乘方案S中的所有合乘小組P的重心坐標(biāo)(wx，wy)，如式（21）所示。

每次操作選取一個(gè)合乘小組P1，篩選出P1中距P1重心最遠(yuǎn)的用戶i，然后計(jì)算該用戶與P1重心的距離dP1i，最后計(jì)算P1與S中其余合乘小組重心的距離差wdP，如式（22）所示。在S中選出滿足式（23）約束的合乘小組，并將這些合乘小組按照wdP值由小到大依次插入到合乘小組集合Stemp中。

對(duì)于Stemp中合乘小組與P1進(jìn)行如下操作：

①選出Stemp中第一個(gè)合乘小組Pt1，并將該合乘小組從Stemp中刪除。

②從P1與Pt1兩個(gè)合乘小組的所有用戶中篩選出距離最遠(yuǎn)的兩個(gè)用戶，將這兩個(gè)用戶作為兩個(gè)新的合乘小組的司機(jī)，然后將P1與Pt1中其余用戶按照Regret Insertion算法分配到兩個(gè)新的合乘小組中。

③對(duì)新的合乘小組進(jìn)行結(jié)果評(píng)估，若總出行成本降低，則對(duì)S進(jìn)行更新，混合鄰域搜索操作結(jié)束，否則繼續(xù)執(zhí)行步驟①直至Stemp為空集合。

混合鄰域操作的示例圖如圖3所示。該操作的復(fù)雜度為O(n2)。

Fig.3 Example of mixed neighborhood圖3 混合鄰域示例圖

（2）鏈?zhǔn)洁徲騈2。鏈?zhǔn)洁徲驅(qū)?dāng)前合乘小組中距離合乘小組重心較遠(yuǎn)的用戶移動(dòng)到距離當(dāng)前合乘小組重心距離更近的其他合乘小組中，從而降低出行成本。鏈?zhǔn)洁徲虿僮魅缦滤荆?/p>

①構(gòu)建一個(gè)合乘小組循環(huán)鏈表L存儲(chǔ)合乘小組。

②首先從S中的每一個(gè)合乘小組P中篩選出距離該合乘小組重心最遠(yuǎn)的用戶i，計(jì)算用戶i與該合乘小組重心的距離dPi，然后計(jì)算用戶i與S中其他合乘小組重心距離，其中diPx為這些重心距離值中最小的重心距離。最后計(jì)算dPi與diPx的差值disP，如式（24）所示。

③在S中隨機(jī)選擇一個(gè)滿足式（25）的合乘小組Pr作為L(zhǎng)的第一個(gè)元素，并從S中刪除Pr；如果S中沒(méi)有滿足式（25）的合乘小組，則鏈?zhǔn)洁徲蛩阉鹘Y(jié)束。

④標(biāo)記L中最近插入的合乘小組Pj，在S中篩選出與Pj重心距離差wd最小的合乘小組Pf，將Pf插入L中，并從S中刪除Pf。

⑤重復(fù)步驟④直到S中所有的合乘小組全部插入到L中。

⑥以L中第一個(gè)合乘小組Pr作為起始點(diǎn)。將Pr中距離重心最遠(yuǎn)的用戶移動(dòng)到L中的下一節(jié)點(diǎn)的合乘小組Pnext中。

⑦如果下一節(jié)點(diǎn)的合乘小組違反了式（8）約束，則將該合乘小組中距離重心最遠(yuǎn)的用戶移動(dòng)到下一節(jié)點(diǎn)的合乘小組中。重復(fù)此操作直至操作節(jié)點(diǎn)的合乘小組滿足車(chē)容量為止。

鏈?zhǔn)洁徲虻氖纠龍D如圖4所示。該操作的復(fù)雜度為O(n2)。

Fig.4 Example of chain neighborhood圖4 鏈?zhǔn)洁徲蚴纠龍D

（3）分割鄰域N3。分割鄰域?qū)⒁粋€(gè)出行成本較高、用戶間距離較遠(yuǎn)的合乘小組分割成多個(gè)合乘小組，使各合乘小組總出行成本降低。分割鄰域每次可以將一個(gè)非獨(dú)自駕車(chē)的合乘小組分為兩個(gè)合乘小組。分割鄰域首先對(duì)每一個(gè)非獨(dú)自駕車(chē)的合乘小組計(jì)算該小組中所有用戶的重心距離差之和sumP，如式（26）所示。

在sumP值最大的n個(gè)合乘小組中隨機(jī)選出一個(gè)合乘小組進(jìn)行分割操作。其中如果n設(shè)置得過(guò)大則容易導(dǎo)致隨機(jī)性較強(qiáng)，算法收斂速度較慢；n設(shè)置過(guò)小，會(huì)導(dǎo)致該鄰域操作的隨機(jī)性下降，容易產(chǎn)生對(duì)某些無(wú)法成功分割的合乘小組進(jìn)行重復(fù)分割的情況，致使計(jì)算效率下降。經(jīng)過(guò)多次實(shí)驗(yàn)，將n設(shè)置為非獨(dú)自駕車(chē)的合乘小組數(shù)量的1/4效果較好。然后將該合乘小組中互相之間距離最遠(yuǎn)的兩個(gè)用戶分到兩個(gè)合乘小組中作為司機(jī)，其余用戶按Regret Insertion算法分配到兩個(gè)合乘小組中。分割鄰域的示例圖如圖5所示。該操作的復(fù)雜度為O(n)。

Fig.5 Example of divide neighborhood圖5 分割鄰域示例圖

（4）合并鄰域N4。合并鄰域?qū)蓚€(gè)合乘小組合并成一個(gè)合乘小組從而降低出行成本。合并鄰域操作每次可合并兩個(gè)人數(shù)沒(méi)有達(dá)到車(chē)容量約束的合乘小組，并且合并后的合乘小組滿足式（8）的約束。其具體操作如下：

①構(gòu)建一個(gè)合乘小組S1存儲(chǔ)合乘小組集合S中人數(shù)未達(dá)到車(chē)容量的合乘小組。若S1中的合乘小組數(shù)量小于2，則合并鄰域搜索結(jié)束。

②構(gòu)建一個(gè)合乘小組鏈表l存儲(chǔ)合乘小組，計(jì)算S1中各個(gè)合乘小組的車(chē)容量與實(shí)際搭載人數(shù)的差值difP，選出difP最大的合乘小組Pm存入l中，并從S1中刪除合乘小組Pm。

③計(jì)算S1中的各個(gè)合乘小組Pk重心與Pm重心之間的距離差wdPk，并將S1中各個(gè)合乘小組按wdPk

值由小到大依次存入到l中。

④將Pm與l中第二個(gè)合乘小組進(jìn)行合并，如果合并后的合乘小組滿足式（8）的約束，則合并鄰域搜索結(jié)束；否則Pm與l中下一個(gè)節(jié)點(diǎn)的合乘小組進(jìn)行合并，直至合并成功或與l中最后一個(gè)節(jié)點(diǎn)的合乘小組進(jìn)行合并操作，合并鄰域搜索結(jié)束。

合并鄰域的示例圖如圖6所示。該操作的復(fù)雜度為O(n)。

4.2 結(jié)果評(píng)估

Fig.6 Example of merge neighborhood圖6 合并鄰域示例圖

目標(biāo)函數(shù)的評(píng)估通常是所有的啟發(fā)式算法中最費(fèi)時(shí)的操作。對(duì)于長(zhǎng)期車(chē)輛合乘問(wèn)題，一個(gè)完整的結(jié)果評(píng)估包括計(jì)算成本、驗(yàn)證每個(gè)合乘小組的車(chē)容量、司機(jī)行駛時(shí)間和時(shí)間窗口約束。由于鄰域操作后的合乘方案S′與S僅部分合乘小組不同，本文提出了一種更有效的評(píng)估方法。該方法評(píng)估合乘方案中發(fā)生變化的合乘小組E(s，g)，其中s是當(dāng)前合乘方案，g是組內(nèi)用戶發(fā)生變化的合乘小組，而并非對(duì)S′中所有的合乘小組進(jìn)行評(píng)估，因此極大地提升了評(píng)估效率。這種評(píng)估方法的復(fù)雜度與搜索過(guò)程中使用的鄰域相關(guān)。其中混合、分割和合并鄰域操作只對(duì)兩個(gè)組內(nèi)用戶發(fā)生變化的合乘小組進(jìn)行評(píng)估。對(duì)于鏈?zhǔn)洁徲虿僮?，組內(nèi)用戶發(fā)生變化的合乘小組數(shù)量不定。

在評(píng)估之前首先檢查各合乘小組的行駛時(shí)間和時(shí)間窗約束，對(duì)于不滿足行駛時(shí)間和時(shí)間窗口約束的合乘小組將通過(guò)與構(gòu)建初始合乘方案中使用的相同修復(fù)過(guò)程進(jìn)行修復(fù)。

4.3 VNS-LTCPP的主要結(jié)構(gòu)

綜上所述，VNS-LTCPP算法主要應(yīng)用四種不同的鄰域結(jié)構(gòu)連續(xù)對(duì)合乘方案進(jìn)行鄰域搜索操作，并對(duì)各合乘小組進(jìn)行行駛時(shí)間和時(shí)間窗約束驗(yàn)證與修復(fù)，最終得到優(yōu)化后的合乘方案。VNS-LTCPP算法的整體結(jié)構(gòu)介紹如下。

首先根據(jù)Regret Insertion算法構(gòu)建初始合乘方案S0，并對(duì)S0中各合乘小組進(jìn)行行駛時(shí)間和時(shí)間窗約束驗(yàn)證與修復(fù)得到S。然后對(duì)S進(jìn)行迭代優(yōu)化，每次迭代優(yōu)化過(guò)程中所應(yīng)用的鄰域搜索依次為混合鄰域N1、鏈?zhǔn)洁徲騈2、分割鄰域N3和合并鄰域N4。這四種鄰域搜索依次對(duì)S進(jìn)行鄰域搜索操作，當(dāng)前鄰域搜索Nk對(duì)S進(jìn)行鄰域搜索操作后生成S′，VNS-LTCPP算法對(duì)S′中各合乘小組進(jìn)行行駛時(shí)間和時(shí)間窗約束驗(yàn)證與修復(fù)得到S″。如果S″的總出行成本比S低，則將S″替代S，并對(duì)S進(jìn)行下一次迭代優(yōu)化；否則切換到下一個(gè)鄰域搜索。當(dāng)?shù)螖?shù)超過(guò)規(guī)定次數(shù)n時(shí)，優(yōu)化過(guò)程停止。

4.4 VNS-LTCPP分布式結(jié)構(gòu)

4.4.1 Spark基本概念

Spark是一個(gè)分布式的內(nèi)存計(jì)算框架，其特點(diǎn)是能處理大規(guī)模數(shù)據(jù)，計(jì)算速度快。Spark延續(xù)了Hadoop的MapReduce計(jì)算模型，相比之下Spark的計(jì)算過(guò)程保持在內(nèi)存中，減少了硬盤(pán)讀寫(xiě)，能夠?qū)⒍鄠€(gè)操作進(jìn)行合并后計(jì)算，因此提升了計(jì)算速度。同時(shí)Spark也提供了更豐富的計(jì)算API。

MapReduce是Spark的計(jì)算模型，其特點(diǎn)是Map和Reduce過(guò)程高度可并行化;過(guò)程間耦合度低，單個(gè)過(guò)程失敗后可以重新計(jì)算，而不會(huì)導(dǎo)致整體失敗;最重要的是數(shù)據(jù)處理中的計(jì)算邏輯可以很好地轉(zhuǎn)換為Map和Reduce操作。

RDD（resilient distributed dataset）是Spark中最主要的數(shù)據(jù)結(jié)構(gòu)，RDD是分布式的數(shù)據(jù)集，每個(gè)RDD都支持MapReduce類(lèi)操作，經(jīng)過(guò)MapReduce操作后會(huì)產(chǎn)生新的RDD，而不會(huì)修改原有RDD。RDD的數(shù)據(jù)集是分區(qū)的，因此可以把每個(gè)數(shù)據(jù)分區(qū)放到不同的分區(qū)上進(jìn)行計(jì)算。

4.4.2 VNS-LTCPP算法分布式設(shè)計(jì)

VNS-LTCPP算法可以很好地應(yīng)用于分布式系統(tǒng)，本文基于Spark平臺(tái)將算法計(jì)算部分部署到多臺(tái)計(jì)算機(jī)上進(jìn)行并行化計(jì)算。Master節(jié)點(diǎn)負(fù)責(zé)構(gòu)建初始合乘方案，為每個(gè)Worker節(jié)點(diǎn)調(diào)度任務(wù)，通過(guò)對(duì)比各Worker節(jié)點(diǎn)返回的優(yōu)化合乘方案的總出行成本得到總出行成本最低的合乘方案；各Worker節(jié)點(diǎn)負(fù)責(zé)對(duì)初始合乘方案進(jìn)行迭代優(yōu)化。VNS-LTCPP算法分布式結(jié)構(gòu)如圖7所示。

Fig.7 VNS-LTCPPalgorithm distributed structure diagram圖7 VNS-LTCPP算法分布式結(jié)構(gòu)圖

VNS-LTCPP算法并行化主要基于Spark的Map及Reduce操作來(lái)實(shí)現(xiàn)，首先Master節(jié)點(diǎn)按照初始合乘方案算法求解初始合乘方案，與集群管理器通信，通過(guò)集群管理器啟動(dòng)Worker節(jié)點(diǎn)。然后Master節(jié)點(diǎn)創(chuàng)建RDD存儲(chǔ)合乘方案，并將RDD及Map、Reduce操作以任務(wù)的形式提交到各個(gè)Worker節(jié)點(diǎn)的執(zhí)行器中。程序配置分區(qū)數(shù)為8，每個(gè)分區(qū)都存儲(chǔ)一個(gè)完整的合乘方案數(shù)據(jù)，每個(gè)Worker節(jié)點(diǎn)啟動(dòng)一個(gè)執(zhí)行器，每個(gè)執(zhí)行器執(zhí)行兩個(gè)獨(dú)立的分區(qū)任務(wù)，4臺(tái)Worker節(jié)點(diǎn)一次可產(chǎn)生8個(gè)優(yōu)化合乘方案。其中Map操作執(zhí)行對(duì)合乘方案的迭代優(yōu)化運(yùn)算，經(jīng)過(guò)規(guī)定迭代次數(shù)優(yōu)化后得到優(yōu)化合乘方案，Map操作產(chǎn)生新的RDD存儲(chǔ)優(yōu)化合乘方案。Reduce操作負(fù)責(zé)將Worker節(jié)點(diǎn)中每個(gè)任務(wù)所得的存儲(chǔ)優(yōu)化合乘方案的RDD返回Master節(jié)點(diǎn)。最后Master節(jié)點(diǎn)通過(guò)對(duì)Worker節(jié)點(diǎn)傳回的優(yōu)化合乘方案進(jìn)行總出行成本計(jì)算，并篩選出總出行成本最低的優(yōu)化合乘方案作為最終的車(chē)輛合乘方案。

為了減少通信時(shí)間的損耗，Master節(jié)點(diǎn)將任務(wù)傳輸給各個(gè)Worker節(jié)點(diǎn)中進(jìn)行計(jì)算，每個(gè)Worker節(jié)點(diǎn)中的任務(wù)負(fù)責(zé)對(duì)合乘方案進(jìn)行規(guī)定迭代次數(shù)的優(yōu)化得到最終的優(yōu)化合乘方案，任務(wù)完成迭代優(yōu)化后通過(guò)Reduce操作將合乘方案?jìng)鬏敾豈aster節(jié)點(diǎn)進(jìn)行處理。

5 實(shí)驗(yàn)結(jié)果與分析

5.1 實(shí)驗(yàn)配置環(huán)境

Spark集群由一個(gè)主節(jié)點(diǎn)（Master）和四個(gè)從節(jié)點(diǎn)（Worker）組成，Spark版本為1.6.0。集群中各節(jié)點(diǎn)具體配置如表3所示。

5.2 實(shí)驗(yàn)數(shù)據(jù)及參數(shù)設(shè)置

Table 3 Cluster configuration表3 集群配置

實(shí)驗(yàn)所用算例由Solomon標(biāo)準(zhǔn)算例修改所得，算例的規(guī)模為100人（S1）、200人（S2）、400人（S3）和 1 000人（S4）四種規(guī)模。其中100人規(guī)模的算例有五組：S1_1,S1_2,S1_3,S1_4,S1_5；200人規(guī)模的算例有五組：S2_1,S2_2,S2_3,S2_4,S2_5；400人規(guī)模的算例有五組：S3_1,S3_2,S3_3,S3_4,S3_5；1 000人規(guī)模的算例有五組：S4_1,S4_2,S4_3,S4_4,S4_5。實(shí)驗(yàn)的參數(shù)設(shè)置：α=0.8,β=0.2，100人算例迭代次數(shù)為500次，200人算例迭代次數(shù)為1 000次，400人算例迭代次數(shù)為1 500次，1 000人算例迭代次數(shù)為3 000次。

5.3 實(shí)驗(yàn)結(jié)果分析

為驗(yàn)證VNS-LTCPP算法的收斂速度，本文對(duì)S1_1、S2_1、S3_1和S4_1進(jìn)行實(shí)驗(yàn)計(jì)算，其中S1_1與S2_1的最低成本由Cplex平臺(tái)計(jì)算得出，S3_1、S4_1由于算例規(guī)模較大通過(guò)Cplex平臺(tái)無(wú)法在合理時(shí)間內(nèi)計(jì)算出最低成本。實(shí)驗(yàn)對(duì)4個(gè)算例分別運(yùn)行計(jì)算10次，并從每個(gè)算例10組實(shí)驗(yàn)結(jié)果中隨機(jī)選取5組實(shí)驗(yàn)數(shù)據(jù)，實(shí)驗(yàn)結(jié)果如圖8～圖11所示。

Fig.8 Convergence diagram of S1_1圖8 S1_1算例收斂圖

Fig.10 Convergence diagram of S3_1圖10 S3_1算例收斂圖

Fig.11 Convergence diagram of S4_1圖11 S4_1算例收斂圖

由圖8～圖11可以看出，VNS-LTCPP算法可以快速收斂，但實(shí)驗(yàn)的收斂速度隨著算例的規(guī)模增大而減緩，實(shí)驗(yàn)結(jié)果的偏差也會(huì)隨著算例規(guī)模的增大而變大。同時(shí)由于在構(gòu)建初始合乘方案時(shí)，司機(jī)的選擇具有隨機(jī)性，因此在相同算例的各次實(shí)驗(yàn)中所得合乘方案均有所不同，造成了初始合乘方案的出行成本有所差異。對(duì)于生成質(zhì)量較差的初始合乘方案同樣可以得到很好的優(yōu)化結(jié)果。由圖8、圖9可以看出VNS-LTCPP算法的收斂所得的最終成本也趨近于最低成本。

為了驗(yàn)證VNS-LTCPP算法的精度和可靠性，本文對(duì)100人規(guī)模和200人規(guī)模的算例進(jìn)行實(shí)驗(yàn)，每個(gè)算例進(jìn)行10次運(yùn)行計(jì)算。其中Ropt表示算例的最低總出行成本，Rmin表示實(shí)驗(yàn)所得的最低總出行成本，Rave表示實(shí)驗(yàn)的平均總出行成本，AME表示實(shí)驗(yàn)的平均誤差，ME表示實(shí)驗(yàn)的最小誤差。實(shí)驗(yàn)結(jié)果如表4所示。

Table 4 Precision experimental test表4 精度實(shí)驗(yàn)測(cè)試

由表4可以看出，實(shí)驗(yàn)的平均誤差為0.31%～0.65%，VNS-LTCPP算法具有很高的精度和可靠性，對(duì)于200人以內(nèi)規(guī)模的算例可以得到質(zhì)量可靠的合乘方案。

本文提出的基于分布式的復(fù)合變鄰域算法由于分布式的算法設(shè)計(jì)和集群節(jié)點(diǎn)之間網(wǎng)絡(luò)通信原因，理論上在相同實(shí)驗(yàn)環(huán)境下其整體計(jì)算時(shí)間要高于非分布式的計(jì)算時(shí)間，此外由于VNS-LTCPP算法具有隨機(jī)性，會(huì)出現(xiàn)優(yōu)化效果較差的優(yōu)化合乘方案，而分布式計(jì)算可以有效地過(guò)濾掉較差的優(yōu)化合乘方案，能夠最大限度地得到成本更低的優(yōu)化合乘方案。因此本文進(jìn)行了分布式計(jì)算與非分布式計(jì)算之間的對(duì)比實(shí)驗(yàn)。分布式計(jì)算每臺(tái)Worker節(jié)點(diǎn)一次計(jì)算出兩個(gè)優(yōu)化合乘方案，故分布式計(jì)算一次可以得到8個(gè)優(yōu)化合乘方案并從中選取總出行成本最低的優(yōu)化合乘方案。每個(gè)算例的分布式計(jì)算實(shí)驗(yàn)次數(shù)為10次，其中Rdis表示平均成本，Tdis表示平均計(jì)算時(shí)間。非分布式計(jì)算實(shí)驗(yàn)分為兩組實(shí)驗(yàn)，其中實(shí)驗(yàn)1為一次計(jì)算出1個(gè)優(yōu)化合乘方案，實(shí)驗(yàn)次數(shù)為8次，其中R1表示平均總出行成本；實(shí)驗(yàn)2為一次計(jì)算出8個(gè)優(yōu)化合乘方案，實(shí)驗(yàn)次數(shù)為10次，其中T2表示平均計(jì)算時(shí)間，時(shí)間單位為ms。Per表示Tdis相對(duì)于T2節(jié)約的時(shí)間的百分比。具體數(shù)據(jù)如表5所示。

由表5可以看出VNS-LTCPP算法分布式計(jì)算的平均總出行成本Rdis整體上要低于實(shí)驗(yàn)1的平均總出行成本R1，其中1 000人算例的效果最為明顯。在計(jì)算時(shí)間上，由于通信時(shí)間和任務(wù)調(diào)度時(shí)間的時(shí)間損耗對(duì)于100人和200人規(guī)模的算例，分布式計(jì)算的平均計(jì)算時(shí)間Tdis對(duì)于實(shí)驗(yàn)2的平均計(jì)算時(shí)間T2并沒(méi)有明顯減少，但隨著算例規(guī)模和優(yōu)化迭代次數(shù)的擴(kuò)大，通信時(shí)間和任務(wù)調(diào)度時(shí)間所占的時(shí)間損耗比例逐步降低。400人和1 000人規(guī)模算例分布式計(jì)算所需時(shí)間明顯低于實(shí)驗(yàn)2的平均計(jì)算時(shí)間，其中1 000人規(guī)模算例約為分布式計(jì)算的平均計(jì)算時(shí)間較實(shí)驗(yàn)2的平均計(jì)算時(shí)間節(jié)省60.6%～63.0%，因此對(duì)于大規(guī)模算例分布式計(jì)算的時(shí)間具有明顯的優(yōu)勢(shì)。

Table 5 Distributed contrast experiment表5 分布式對(duì)比實(shí)驗(yàn)

從整體上看，對(duì)于100人、200人規(guī)模的算例VNS-LTCPP算法分布式計(jì)算的優(yōu)勢(shì)并不明顯，但隨著算例規(guī)模和迭代次數(shù)的增大VNS-LTCPP算法分布式計(jì)算在合乘方案優(yōu)化和計(jì)算時(shí)間上的優(yōu)勢(shì)明顯增強(qiáng)。因此VNS-LTCPP算法分布式計(jì)算可以更好地解決1 000人及更大規(guī)模算例的合乘方案優(yōu)化問(wèn)題。

6 結(jié)束語(yǔ)

本文構(gòu)建了LTCPP的數(shù)學(xué)模型，提出了針對(duì)該問(wèn)題的復(fù)合變鄰域搜索算法，并將算法與分布式計(jì)算相結(jié)合。通過(guò)實(shí)驗(yàn)結(jié)果分析，VNS-LTCPP算法與分布式計(jì)算能夠在短時(shí)間內(nèi)求解出較高質(zhì)量的車(chē)輛合乘方案，可以有效降低機(jī)動(dòng)車(chē)出行數(shù)量，降低環(huán)境污染，節(jié)約出行成本，具有很高的實(shí)用性。此外，由于本文用戶目的地相同，而在實(shí)際生活中用戶群體的目的地不盡相同，因此在下一步研究中可將用戶群體按目的地劃分為多個(gè)用戶群體，對(duì)多目的地的用戶群體進(jìn)行分布計(jì)算。經(jīng)過(guò)實(shí)驗(yàn)觀察，本文算法在構(gòu)建初始合乘方案時(shí)，出行總成本還有很大的波動(dòng)，將來(lái)的研究擬對(duì)初始合乘方案的構(gòu)造進(jìn)行完善。