郭羽含，伊 鵬

(遼寧工程技術(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)車輛合乘均采用即時匹配模式，缺乏穩(wěn)定性且每天均需重復(fù)匹配過程，用戶需要頻繁操作且對計算資源的耗費十分巨大。本文研究的長期車輛合乘為解決以上弊端提供了新的手段。長期車輛合乘主要針對于大中型城市中具有相同或相近的上下班時間和工作地點，但居住分散的用戶群體。合乘用戶在成功匹配之后，其合乘關(guān)系將長期保持無需再次匹配。這種合乘模式可在很大程度上提高用戶合乘的便利性，增加參與合乘的用戶數(shù)量，繼而減少私人汽車出行率、降低出行花費、緩解城市交通壓力和減少污染物的排放。

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

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

1 問題描述

1.1 問題定義

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

1.2 合乘模型

1.2.1 常量定義

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

1.2.2 變量定義

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

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

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

(1)

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

(2)

其中fLTC為所有合乘小組的出行總花費。

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點，將用戶ci載入合乘小組Pk中后合乘小組Pk中的人數(shù)；式(6)限定了用戶最早出發(fā)時間；式(7)限定了合乘小組最晚到達(dá)目的地時間；式(8)限定了合乘小組中司機(jī)的行駛時間；式(9)、(10)為二進(jìn)制完整約束。

2 初始解決方案

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

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

2.1 司機(jī)的篩選

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

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

(11)

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

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

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

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

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

μ|eca+tcacb-ecb|

(12)

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

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

(13)

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

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

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

P1∪P2∪…∪Pn=Pr

(14)

P1∩P2∩…∩Pn=?

(15)

(16)

3 變鄰域搜索

3.1 鄰域設(shè)計

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

1)交換鄰域。

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

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

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

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

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

(17)

(18)

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

d)在L中選出一個合乘小組PL1作為起始點。

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

(19)

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

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

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

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

3)切割鄰域。

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

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

4)合并鄰域。

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

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

3.2 結(jié)果評估

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

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

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

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

3)對S進(jìn)行鏈?zhǔn)洁徲虿僮鳎看尾僮魍瓿珊髮π律傻暮铣朔桨高M(jìn)行約束驗證與修復(fù)并進(jìn)行結(jié)果評估得到S1,若出行總花費沒有降低則執(zhí)行步驟4)；否則用S1替代S,重新對S進(jìn)行步驟3)操作，直至操作次數(shù)達(dá)到該鄰域操作規(guī)定的局部優(yōu)化次數(shù)。

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

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

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

4 實驗

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 實驗算例

本文所用的算例是在Solomon車輛路徑問題(Vehicle Routing Problem，VRP)實例基礎(chǔ)上修改得到的。實驗算例規(guī)模分別為100人、200人、400人和1 000人，每個規(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)點分布圖，如圖6所示。

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

4.3 實驗結(jié)果與分析

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

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

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

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

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

表1 S1-1、S2-1、S3-1和S4-1的計算結(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ù)也隨之增加，實驗計算出的出行成本也隨之降低。

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

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

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

5 結(jié)語

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