長期車輛合乘問題的復(fù)合變鄰域搜索算法

郭羽含，伊 鵬

(遼寧工程技術(shù)大學(xué) 軟件學(xué)院，遼寧 葫蘆島 125100)(*通信作者電子郵箱591729781@qq.com)

0 引言

隨著我國經(jīng)濟(jì)的高速發(fā)展，私人汽車保有量急劇增加，導(dǎo)致城市交通擁堵和環(huán)境污染情況日益嚴(yán)重。為緩解以上問題并提升市民的出行效率，順風(fēng)車、網(wǎng)約車等車輛合乘模式開始涌現(xiàn)。但傳統(tǒng)車輛合乘均采用即時(shí)匹配模式，缺乏穩(wěn)定性且每天均需重復(fù)匹配過程，用戶需要頻繁操作且對(duì)計(jì)算資源的耗費(fèi)十分巨大。本文研究的長期車輛合乘為解決以上弊端提供了新的手段。長期車輛合乘主要針對(duì)于大中型城市中具有相同或相近的上下班時(shí)間和工作地點(diǎn)，但居住分散的用戶群體。合乘用戶在成功匹配之后，其合乘關(guān)系將長期保持無需再次匹配。這種合乘模式可在很大程度上提高用戶合乘的便利性，增加參與合乘的用戶數(shù)量，繼而減少私人汽車出行率、降低出行花費(fèi)、緩解城市交通壓力和減少污染物的排放。

長期車輛合乘問題(Long-Term CarPooling Problem，LTCPP)中用戶目的地相對(duì)固定且用戶間合乘關(guān)系長期保持相對(duì)穩(wěn)定，屬于一種特殊的車輛路徑規(guī)劃問題(Vehicle Routing Problem,VRP)。傳統(tǒng)的車輛路徑問題研究主要針對(duì)倉儲(chǔ)物流配送問題進(jìn)行路徑規(guī)劃，而長期車輛合乘問題在路徑規(guī)劃的基礎(chǔ)上還需構(gòu)建合乘小組，因此還涵蓋了分組問題，求解更為復(fù)雜且時(shí)空約束數(shù)量更多。國內(nèi)外關(guān)于長期車輛合乘問題的研究起步較晚，研究數(shù)量較少，多數(shù)研究均針對(duì)傳統(tǒng)車輛路徑規(guī)劃問題或單次車輛合乘問題。宋超超等[1]提出一種基于吸引粒子群算法解決車輛合乘問題，通過吸引粒子群算法進(jìn)行初次匹配，然后通過匹配再優(yōu)化的策略對(duì)合乘方案進(jìn)行再優(yōu)化，最后得到搭載成功率較高的車輛合乘匹配方案。楊志家等[2]提出一種分布式并行計(jì)算環(huán)境下的合乘模型，利用合乘概率矩陣的先驗(yàn)知識(shí)對(duì)車輛合乘問題實(shí)現(xiàn)高效的運(yùn)算和求解。Boukhater等[3]提出一種改進(jìn)的遺傳算法以最小的旅行距離、高效的搭乘匹配、及時(shí)到達(dá)和最大的公平性來搜索解決方案。目前的研究主要針對(duì)小規(guī)模車輛合乘問題[4-6]，對(duì)于較大規(guī)模算例求解存在求解效率低、求解質(zhì)量差的問題。而變鄰域搜索算法是一種快速有效的算法，可以在短時(shí)間內(nèi)求出車輛路徑問題的近似解或最優(yōu)解。

本文針對(duì)長期車輛合乘問題提出了涵蓋車容量和時(shí)間窗約束的全面數(shù)學(xué)模型，并在變鄰域搜索的基礎(chǔ)上提出了一種有效的復(fù)合算法。變鄰域搜索算法具有算子設(shè)計(jì)自由度高、收斂速度快、不易陷入局部最優(yōu)等特點(diǎn)，本文針對(duì)長期車輛合乘問題特點(diǎn)設(shè)計(jì)了專用算子，可在短時(shí)間內(nèi)求得高質(zhì)量的解決方案。仿真實(shí)驗(yàn)結(jié)果表明該算法求解質(zhì)量高，且運(yùn)算時(shí)間短，具有很高的時(shí)效性。

1 問題描述

1.1 問題定義

假設(shè)每位合乘參與者都擁有各自的車輛，并前往相同的目的地。每位參與者可單獨(dú)駕車或與他人合乘，且每位用戶都有各自的最長行駛時(shí)間和最大搭載量。長期車輛合乘問題的目標(biāo)是求出一種合乘方案，將參與者分到若干個(gè)合乘小組中，小組中的用戶按固定規(guī)律輪流駕駛各自的車輛按照算法計(jì)算出的最短路徑接送組內(nèi)其他用戶抵達(dá)目的地，使得所有小組的出行花費(fèi)總和達(dá)到最低。

1.2 合乘模型

1.2.1 常量定義

在本模型中：S表示合乘的解決方案；每個(gè)合乘小組P包含該合乘小組的所有用戶；C表示所有用戶的集合；capcj表示當(dāng)用戶cj作為司機(jī)時(shí)能夠搭載的最大人數(shù)；timcj表示用戶cj作為司機(jī)時(shí)能夠接受的最長行駛時(shí)間；arvcj表示用戶cj最晚到達(dá)目的地的時(shí)間；ecj表示用戶cj最早出發(fā)時(shí)間。

1.2.2 變量定義

φcj表示用戶cj是否獨(dú)自駕車，若該用戶獨(dú)自駕車則變量φcj為0，否則為1；numPk表示合乘小組Pk的實(shí)際搭載人數(shù)；QPk表示合乘小組Pk的車容量；arrtcj表示合乘小組中用戶cj到達(dá)目的地的時(shí)間；TlPk表示合乘小組Pk最晚到達(dá)目的地的時(shí)間。

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

LTCPP優(yōu)化目標(biāo)在于降低用戶出行總花費(fèi)，由于每位司機(jī)可以有多條行車路線，因此算法通過路徑規(guī)劃對(duì)合乘小組Pi中每位用戶找到一條最短路徑。costcj表示在合乘小組Pi中用戶cj作為司機(jī)時(shí)用戶cj的最少出行費(fèi)用，為了減少單獨(dú)駕車的情況出現(xiàn)，本文引入懲罰因子ρ(1<ρ<2)，單獨(dú)駕車的用戶將會(huì)受到懲罰；合乘小組Pi的人數(shù)定義為numPi總費(fèi)用為cost(Pi)。

(1)

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

(2)

其中fLTC為所有合乘小組的出行總花費(fèi)。

1.2.4 約束條件

QPk=min(capcj);Pk∈S,?cj∈Pk

(3)

(4)

1≤numPk≤QPk;Pk∈S

(5)

ecj≤TlPk-arrtcj;cj∈Pk,Pk∈S

(6)

TlPk≤min(arvci);ci∈Pk,Pk∈S

(7)

arrtcd≤timcd;cd∈P

(8)

φci∈{0,1};ci∈Pk,Pk∈S

(9)

(10)

其中：式(3)～(5)表示合乘小組載客量約束;式(4)表示司機(jī)cd經(jīng)過用戶ci點(diǎn)，將用戶ci載入合乘小組Pk中后合乘小組Pk中的人數(shù)；式(6)限定了用戶最早出發(fā)時(shí)間；式(7)限定了合乘小組最晚到達(dá)目的地時(shí)間；式(8)限定了合乘小組中司機(jī)的行駛時(shí)間；式(9)、(10)為二進(jìn)制完整約束。

2 初始解決方案

為了得到合乘小組成員地理分布合理的初始解，本文設(shè)計(jì)兩步法生成初始解：第一步進(jìn)行司機(jī)的篩選；第二步應(yīng)用Regret Insertion算法構(gòu)造初始解；并且采用雙層編碼的結(jié)構(gòu)顯示合乘小組中各個(gè)用戶的信息。雙層編碼結(jié)構(gòu)如圖1所示。第一層編碼中包含合乘小組的用戶編號(hào)及分組方式；第二層編碼顯示第一層中的用戶作為司機(jī)時(shí)的詳細(xì)信息，依次包括合乘小組成員、到達(dá)小組其他用戶位置的時(shí)間、是否獨(dú)自駕車、行駛距離、司機(jī)可接受的最長行駛時(shí)間和合乘小組到達(dá)目的地時(shí)間。

圖1 雙層編碼結(jié)構(gòu)Fig. 1 Two-levels structure

2.1 司機(jī)的篩選

1)在用戶集合中隨機(jī)篩選一名用戶ci作為司機(jī)，構(gòu)建一個(gè)合乘小組Pi。

2)在用戶集合中選出距離用戶ci最近的m個(gè)用戶，然后將這m個(gè)用戶從用戶集合C中刪除。

(11)

其中n為用戶集合C的用戶數(shù)量。

3)重復(fù)1)、2)操作直至用戶集合C為空。

這樣可以避免選擇兩個(gè)距離太近的用戶c1和c2來構(gòu)建兩個(gè)合乘小組，從而減少由于組間用戶距離過近對(duì)合乘小組造成質(zhì)量上的影響。

2.2 初始解的構(gòu)造

應(yīng)用Regret Insertion算法，基于上一步?jīng)]有被選為司機(jī)的用戶的Regret值將用戶分配到合乘小組中。通過式(12)計(jì)算每一位未被選擇為司機(jī)的用戶ca與每位司機(jī)cb之間的距離。

μ|eca+tcacb-ecb|

(12)

其中：xca、yca、xcb、ycb分別為用戶ca和用戶cb的地理坐標(biāo)；eca和ecb分別為用戶ca和用戶cb的最早出發(fā)時(shí)間；tcacb為司機(jī)從用戶ca行駛到用戶cb所需要的時(shí)間；|eca+tcacb-ecb|為用戶ca到用戶cb可接受的時(shí)間與實(shí)際從用戶ca到用戶cb行駛時(shí)間的偏差；λ和μ為影響因子。然后計(jì)算用戶ca的Regret值，如式(13)所示：

Regretca=dcacs-dcacf;ca,cf,cs∈C

(13)

其中dcacs、dcacf分別表示用戶ca與距用戶ca第二近的司機(jī)cs之間的距離和距用戶ca最近的司機(jī)cf之間的距離。把這些用戶按Regret值降序依次分配到人數(shù)小于車容量約束的合乘小組中，這樣可以避免由于用戶分配到與之距離差距較大的第二近司機(jī)的合乘小組而對(duì)初始解質(zhì)量造成不好的影響。當(dāng)所有的用戶被分配到合乘小組中或者所有合乘小組人數(shù)均達(dá)到車容量時(shí)，該過程將停止，未被分配到合乘小組中的用戶獨(dú)自駕駛。

2.3 約束驗(yàn)證與修復(fù)

為了降低VNSA-LTCPP(Variable Neighborhood Search Algorithm-LTCPP)的復(fù)雜性，本文在用戶分配期間不對(duì)式(6)～(7)的時(shí)間窗和式(8)的行駛時(shí)間約束進(jìn)行檢查；而是需要通過在合乘小組中每位用戶充當(dāng)司機(jī)時(shí)對(duì)該司機(jī)用戶進(jìn)行時(shí)間窗和行駛時(shí)間約束驗(yàn)證來檢驗(yàn)初始解決方案的可行性。如果合乘小組中有用戶違反時(shí)間窗和行駛時(shí)間約束條件，則對(duì)該合乘小組Pr進(jìn)行修復(fù)，即將該合乘小組Pr分割成包含若干個(gè)符合時(shí)間窗和行駛時(shí)間約束條件的合乘小組的合乘小組集合Sr={P1,P2,…,Pn},如式(14)～(15)所示，其中Sr中的各個(gè)合乘小組之間用戶互不相同，并且Sr滿足式(16)的目標(biāo)函數(shù)。

P1∪P2∪…∪Pn=Pr

(14)

P1∩P2∩…∩Pn=?

(15)

(16)

3 變鄰域搜索

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

為了能夠得到LTCPP的高質(zhì)量解決方案，本文設(shè)計(jì)了具體的鄰域搜索操作對(duì)初始解方案進(jìn)行優(yōu)化。鄰域搜索定義如下。

1)交換鄰域。

交換鄰域操作每次選擇兩個(gè)來自于不同合乘小組的用戶cx1和cy1,如果將這兩個(gè)用戶交換到對(duì)方的合乘小組中，形成的兩個(gè)新的合乘小組人數(shù)均滿足式(5)的車容量約束，則交換鄰域操作成功，將這兩個(gè)用戶進(jìn)行交換；否則這兩個(gè)用戶不能交換到對(duì)方的合乘小組中，交換鄰域搜索結(jié)束。該鄰域搜索設(shè)定20次局部優(yōu)化，每次局部優(yōu)化后進(jìn)行一次結(jié)果評(píng)估，對(duì)合乘用戶發(fā)生變化的合乘小組進(jìn)行時(shí)間窗和行駛時(shí)間約束驗(yàn)證并進(jìn)行成本評(píng)估。若局部優(yōu)化后出行成本沒有降低則該鄰域搜索結(jié)束，否則進(jìn)行下一次局部優(yōu)化。該過程的示意圖如圖2所示，用戶16與用戶21在滿足車容量約束的條件下互換到對(duì)方的合乘小組中。該操作的復(fù)雜度為O(n)。

圖2 交換鄰域示意圖Fig. 2 Schematic diagram of exchange neighborhood

2)鏈?zhǔn)洁徲颉?/p>

a)構(gòu)建一個(gè)合乘小組循環(huán)鏈表L,隨機(jī)在S中選擇一個(gè)合乘小組Pi作為L的第一個(gè)元素，并從S中刪除Pi。

b)在S中選出與L中第一個(gè)插入的合乘小組Pl重心距離差wd最小的合乘小組Pf插入L中，然后從S中刪除Pf。其中重心坐標(biāo)(wx,wy)的計(jì)算如式(17)所示。重心距離差wd的計(jì)算如式(18)所示。

(17)

(18)

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

d)在L中選出一個(gè)合乘小組PL1作為起始點(diǎn)。

e)PL1中滿足式(19)的用戶被移動(dòng)到L中的下一節(jié)點(diǎn)的合乘小組PL2中。

(19)

f)若當(dāng)前操作節(jié)點(diǎn)的合乘小組人數(shù)違反車容量約束，則將該合乘小組中符合式(17)的用戶從當(dāng)前操作節(jié)點(diǎn)的合乘小組移動(dòng)到當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)合乘小組中，并將操作節(jié)點(diǎn)移動(dòng)到下一節(jié)點(diǎn)，再次執(zhí)行步驟f)操作;否則鏈?zhǔn)洁徲虿僮鹘Y(jié)束。

該鄰域搜索設(shè)定50次局部優(yōu)化，每次局部優(yōu)化后進(jìn)行一次結(jié)果評(píng)估，對(duì)合乘用戶發(fā)生變化的合乘小組進(jìn)行時(shí)間窗和行駛時(shí)間約束驗(yàn)證并進(jìn)行成本評(píng)估。若局部優(yōu)化后出行成本沒有降低，則該鄰域搜索結(jié)束；否則進(jìn)行下一次局部優(yōu)化。

鏈?zhǔn)洁徲虻氖疽鈭D如圖3所示，合乘小組PL1中離合乘小組重心最遠(yuǎn)的用戶14被移動(dòng)到L中的下一節(jié)點(diǎn)的合乘小組PL2中，由于新的合乘小組PL2人數(shù)超過車容量約束，故選出離該合乘小組重心最遠(yuǎn)的用戶11移動(dòng)到L中PL2的下一節(jié)點(diǎn)的合乘小組PL3,新的合乘小組PL3滿足車容量約束，該操作結(jié)束。該操作的復(fù)雜度為O(n)。

圖3 鏈?zhǔn)洁徲蚴疽鈭DFig. 3 Schematic diagram of chain neighborhood

3)切割鄰域。

切割鄰域操作每次可將任意一個(gè)非單獨(dú)駕車的合乘小組Pg分成兩個(gè)非空的合乘小組Pg1和Pg2。對(duì)合乘小組Pg1和Pg2進(jìn)行成本評(píng)估。若出行成本沒有降低，則合乘小組Pg不能進(jìn)行切割操作。切割鄰域的示意圖如圖4所示。該操作的復(fù)雜度為O(1)。

圖4 切割鄰域示意圖Fig. 4 Schematic diagram of cut neighborhood

4)合并鄰域。

合并鄰域操作每次可隨機(jī)選擇并合并任意兩個(gè)人數(shù)小于車容量約束的合乘小組Pd1和Pd2,如果合并后的合乘小組Pcb人數(shù)滿足式(5)的車容量約束，則合乘小組合并初步成功；否則合乘小組Pd1與合乘小組Pd2不能合并。若合乘小組合并初步成功，對(duì)合乘小組Pcb進(jìn)行時(shí)間窗和行駛時(shí)間約束驗(yàn)證并進(jìn)行成本評(píng)估，若成本降低，則合乘小組Pd1與合乘小組Pd2最終合并成功；否則合乘小組Pd1與合乘小組Pd2不能合并。合并鄰域的示意圖如圖5所示，包含用戶2和用戶3的合乘小組Pd1與包含用戶4和用戶5的合乘小組Pd2的人數(shù)都沒有達(dá)到車容量約束，故將這兩個(gè)合乘小組合并成一個(gè)合乘小組Pcb,最后通過驗(yàn)證合乘小組Pcb的車容量約束來判斷合乘小組Pd1與合乘小組Pd2是否能夠合并。該操作的復(fù)雜度是O(1)。

圖5 合并鄰域示意圖Fig. 5 Schematic diagram of combine neighborhood

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

目標(biāo)函數(shù)的評(píng)估通常是啟發(fā)式算法中最耗時(shí)的操作。對(duì)于LTCPP所涉及的結(jié)果評(píng)估包括成本的計(jì)算。在結(jié)果評(píng)估之前首先要驗(yàn)證合乘小組的時(shí)間窗和行駛時(shí)間約束，對(duì)于合乘小組中用戶不滿足式(6)、(7)的時(shí)間窗和式(8)的行駛時(shí)間約束的合乘小組要進(jìn)行修復(fù)，其修復(fù)方法與初始解決方案的構(gòu)建中使用的修復(fù)方法相同，其中切割鄰域不需要對(duì)合乘小組中用戶進(jìn)行時(shí)間窗和行駛時(shí)間約束驗(yàn)證。

傳統(tǒng)成本評(píng)估需要計(jì)算當(dāng)前方案S的總花費(fèi)和鄰域操作前后的解決方案S1的總花費(fèi)，S和S1總花費(fèi)計(jì)算如式(20)、(21)所示，這樣會(huì)浪費(fèi)大量的計(jì)算時(shí)間，由于S1與S僅部分合乘小組用戶發(fā)生變化，本文設(shè)計(jì)了一種有效的方法來對(duì)VNSA-LTCPP提供的解決方案進(jìn)行評(píng)估。這種評(píng)估僅應(yīng)用于鄰域操作后小組成員發(fā)生變化的合乘小組，S′為發(fā)生變化的合乘小組在鄰域操作前的原合乘小組集合，S"為鄰域操作后發(fā)生變化的合乘小組集合。成本評(píng)估如式(22)、(23)所示。這種增量評(píng)估及其復(fù)雜性取決于目標(biāo)優(yōu)化問題所使用的鄰域操作。其中交換、切割和合并鄰域操作只評(píng)估兩個(gè)變換的合乘小組。對(duì)于鏈?zhǔn)洁徲虿僮?，變換的合乘小組數(shù)量由實(shí)際的鄰域操作所決定。由于減少了評(píng)估對(duì)象的數(shù)量，這種評(píng)估方法可以大幅提高VNSA-LTCPP的求解效率。

f1=∑cost(i);i∈S

(20)

f2=∑cost(j);j∈S1

(21)

f3=∑cost(k);k∈S′,S′?S

(22)

f4=∑cost(k1);k1∈S",S"?S1

(23)

3.3 VNSA-LTCPP求解過程

VNSA-LTCPP求解過程依次應(yīng)用交換鄰域(Exchange Neighborhood)、鏈?zhǔn)洁徲?Chain Neighborhood)、切割鄰域(Cut Neighborhood)、合并鄰域(Combine Neighborhood)這四個(gè)鄰域搜索操作。VNSA-LTCPP求解具體流程如下：

1)首先求解出初始合乘方案S0,對(duì)S0進(jìn)行約束驗(yàn)證與修復(fù)得到S。設(shè)置迭代次數(shù)i為0。

2)對(duì)S進(jìn)行交換鄰域操作，每次操作完成后對(duì)新生成的合乘方案進(jìn)行約束驗(yàn)證與修復(fù)并進(jìn)行結(jié)果評(píng)估得到S1,若出行總花費(fèi)沒有降低則執(zhí)行步驟3)；否則用S1替代S,重新對(duì)S進(jìn)行步驟2)操作，直至操作次數(shù)達(dá)到該鄰域操作規(guī)定的局部優(yōu)化次數(shù)。

3)對(duì)S進(jìn)行鏈?zhǔn)洁徲虿僮?，每次操作完成后?duì)新生成的合乘方案進(jìn)行約束驗(yàn)證與修復(fù)并進(jìn)行結(jié)果評(píng)估得到S1,若出行總花費(fèi)沒有降低則執(zhí)行步驟4)；否則用S1替代S,重新對(duì)S進(jìn)行步驟3)操作，直至操作次數(shù)達(dá)到該鄰域操作規(guī)定的局部優(yōu)化次數(shù)。

4)對(duì)S進(jìn)行切割鄰域操作，操作完成后對(duì)新生成的合乘方案進(jìn)行結(jié)果評(píng)估得到S1,若出行總花費(fèi)降低則將S1替代S。

5)對(duì)S進(jìn)行合并鄰域操作，操作完成后對(duì)新生成的合乘方案進(jìn)行約束驗(yàn)證與修復(fù)并進(jìn)行結(jié)果評(píng)估得到S1,若出行總花費(fèi)降低則將S1替代S。

6)若迭代次數(shù)i達(dá)到規(guī)定的迭代次數(shù)，則VNSA-LTCPP求解過程結(jié)束；否則迭代次數(shù)i加1，轉(zhuǎn)到步驟2)。

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

4.1 測試環(huán)境

軟件環(huán)境為Java虛擬機(jī)SUN JDK1.8.0_111，硬件環(huán)境為64位Windows10系統(tǒng),Intel Core i7 2.5 GHz CPU,8 GB RAM。

4.2 實(shí)驗(yàn)算例

本文所用的算例是在Solomon車輛路徑問題(Vehicle Routing Problem，VRP)實(shí)例基礎(chǔ)上修改得到的。實(shí)驗(yàn)算例規(guī)模分別為100人、200人、400人和1 000人，每個(gè)規(guī)模的算例各有五組，分別為S1-1、S1-2、S1-3、S1-4、S1-5；S2-1、S2-2、S2-3、S2-4、S2-5；S3-1、S3-2、S3-3、S3-4、S3-5；S4-1、S4-2、S4-3、S4-4、S4-5。由于篇幅原因，在此只列出S1-1的用戶地理坐標(biāo)點(diǎn)分布圖，如圖6所示。

圖6 用戶地理坐標(biāo)點(diǎn)分布示意圖Fig. 6 Schematic diagram of user geographic coordinate distribution

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

本文對(duì)于S1、S2、S3和S4四種規(guī)模算例設(shè)定1 000～10 000 十個(gè)不同的HVNSA-LTCPP求解迭代次數(shù)進(jìn)行實(shí)驗(yàn)。其中影響因子λ和μ分別設(shè)定為0.8和0.2。每組算例的實(shí)驗(yàn)次數(shù)均為10。

為了驗(yàn)證計(jì)算時(shí)間與迭代次數(shù)和算例規(guī)模之間的關(guān)系，本文對(duì)于每種規(guī)模算例的平均計(jì)算時(shí)間進(jìn)行分析，其中每種規(guī)模算例的平均計(jì)算時(shí)間為每種規(guī)模5組算例的平均計(jì)算時(shí)間。從圖7可以看出，當(dāng)算例規(guī)模一定時(shí)，計(jì)算時(shí)間隨著迭代次數(shù)的增加而增長，同時(shí)計(jì)算時(shí)間的增長速率隨著迭代次數(shù)的增加而趨緩，這是由于隨著迭代次數(shù)的增加，合乘方案的質(zhì)量逐步提高，鄰域搜索中的交換鄰域和鏈?zhǔn)洁徲虻木植績?yōu)化概率降低，對(duì)應(yīng)的鄰域搜索時(shí)間會(huì)減少。當(dāng)?shù)螖?shù)一定時(shí)，計(jì)算時(shí)間會(huì)隨著算例規(guī)模的增長而增長，時(shí)間增長速率約為算例規(guī)模增長速率的80%～90%，因此對(duì)于1 000人以上的較大規(guī)模算例HVNSA仍具有一定的時(shí)效性。

圖7 算例時(shí)間趨勢圖Fig. 7 Trend diagram of instances’ time

本文列出S1-1、S2-1、S3-1和S4-1四組算例的部分實(shí)驗(yàn)數(shù)據(jù)，如表1所示。表1中：Ravg表示實(shí)驗(yàn)運(yùn)行的結(jié)果平均值；Ropt表示算例的最優(yōu)解；Eavg表示算例的平均誤差；T表示計(jì)算時(shí)間。其中：100人、200人規(guī)模算例的最低出行成本由Cplex平臺(tái)計(jì)算得出，400人算例和1 000人算例由于算例規(guī)模較大無法在合理時(shí)間內(nèi)通過Cplex平臺(tái)計(jì)算出算例的最低出行成本。S2-1的部分合乘小組接送順序分配結(jié)果如下所示：

第一組：197→13→58→73;58→197→13→73;13→197→58→73;73→58→197→13。

第二組：129→95→96→195;95→129→96→195;195→96→95→129;96→195→95→129。

第三組：119→27→191→18;18→191→27→119;191→18→27→119;27→191→18→119。

第四組：39→151→168→152;168→152→39→151;151→39→168→152;152→168→39→151。

第五組：88→104→20→14;20→88→104→14;14→20→88→104;104→88→20→14。

其中，對(duì)于每個(gè)用戶所分配接送順序所行駛的路徑都是該用戶接送其他用戶到達(dá)目的地的最短路徑，例如第一組的用戶197按照順序接用戶13、58和73最后到達(dá)目的地，用戶197按照這個(gè)順序所行駛的路徑最短。

表1 S1-1、S2-1、S3-1和S4-1的計(jì)算結(jié)果Tab. 1 Calculation results of S1-1, S2-1, S3-1 and S4-1

從表1中可以看出：算例S1-1，S2-1平均出行成本均接近算例的最優(yōu)出行成本；隨著迭代次數(shù)的增加，初始解方案得到局部優(yōu)化的次數(shù)也隨之增加，實(shí)驗(yàn)計(jì)算出的出行成本也隨之降低。

為了驗(yàn)證算法的有效性，這里對(duì)四種規(guī)模的20組實(shí)驗(yàn)算例進(jìn)行實(shí)驗(yàn)，并與遺傳算法(Genetic Algorithm, GA)和蟻群算法(Ant Colony Algorithm, ACA)的實(shí)驗(yàn)結(jié)果比較，實(shí)驗(yàn)數(shù)據(jù)如表2所示。HVNSA的迭代次數(shù)設(shè)定為10 000，由于算法不同，故通過一定的迭代次數(shù)來驗(yàn)證三種算法在求解時(shí)間和求解質(zhì)量上的優(yōu)劣無法保證公平性。本文采用HVNSA求解質(zhì)量作為終止條件來比較三種算法計(jì)算時(shí)間的對(duì)比方案。其中：T表示計(jì)算時(shí)間；Rmax表示實(shí)驗(yàn)運(yùn)行結(jié)果的最大值；Rmin表示實(shí)驗(yàn)運(yùn)行結(jié)果的最小值；Eavg表示HVNSA的平均誤差；TGA表示HVNSA計(jì)算時(shí)間與GA計(jì)算時(shí)間的比值；TACA表示HVNSA計(jì)算時(shí)間與ACA計(jì)算時(shí)間的比值。

由表2的結(jié)果分析可得HVNSA對(duì)于求解LTCPP具有很高的時(shí)效性和可靠的求解精度，能夠在短時(shí)間內(nèi)求解出高質(zhì)量的合乘方案。其中：100人規(guī)模的算例平均誤差在0.41%左右，200人規(guī)模的算例平均誤差在0.58%左右。在相同求解質(zhì)量條件下，HVNSA的計(jì)算時(shí)間比GA和ACA的計(jì)算時(shí)間均大幅減少，并且隨著算例規(guī)模的增長，計(jì)算時(shí)間減少的幅度更大。

表2 四種規(guī)模算例的計(jì)算結(jié)果Tab. 2 Calculation results of four scale examples

5 結(jié)語

本文構(gòu)建了LTCPP模型，并且提出了基于啟發(fā)式算法的變鄰域搜索算法。通過實(shí)驗(yàn)對(duì)比分析，該算法在計(jì)算速度上對(duì)于遺傳算法和蟻群算法具有明顯的優(yōu)勢，能夠在短時(shí)間內(nèi)產(chǎn)生高質(zhì)量的長期車輛合乘方案，對(duì)于緩解交通擁堵、降低人們出行成本具有很高的實(shí)用性。將來的研究可以結(jié)合分布式計(jì)算在相同計(jì)算時(shí)間內(nèi)生成更優(yōu)的合乘方案，此外引入用戶的偏好和環(huán)境影響因素等約束也是將來研究的一個(gè)方向。