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

郭羽含，伊 鵬

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

0 引言

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

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

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

1 問題描述

1.1 問題定義

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

1.2 合乘模型

1.2.1 常量定義

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

1.2.2 變量定義

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

1.2.3 目標函數

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

(1)

目標函數為：

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

2 初始解決方案

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

圖1 雙層編碼結構Fig. 1 Two-levels structure

2.1 司機的篩選

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

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

(11)

其中n為用戶集合C的用戶數量。

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

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

2.2 初始解的構造

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

μ|eca+tcacb-ecb|

(12)

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

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

(13)

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

2.3 約束驗證與修復

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

P1∪P2∪…∪Pn=Pr

(14)

P1∩P2∩…∩Pn=?

(15)

(16)

3 變鄰域搜索

3.1 鄰域設計

為了能夠得到LTCPP的高質量解決方案，本文設計了具體的鄰域搜索操作對初始解方案進行優化。鄰域搜索定義如下。

1)交換鄰域。

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

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

2)鏈式鄰域。

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

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

(17)

(18)

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

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

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

(19)

f)若當前操作節點的合乘小組人數違反車容量約束，則將該合乘小組中符合式(17)的用戶從當前操作節點的合乘小組移動到當前節點的下一節點合乘小組中，并將操作節點移動到下一節點，再次執行步驟f)操作;否則鏈式鄰域操作結束。

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

鏈式鄰域的示意圖如圖3所示，合乘小組PL1中離合乘小組重心最遠的用戶14被移動到L中的下一節點的合乘小組PL2中，由于新的合乘小組PL2人數超過車容量約束，故選出離該合乘小組重心最遠的用戶11移動到L中PL2的下一節點的合乘小組PL3,新的合乘小組PL3滿足車容量約束，該操作結束。該操作的復雜度為O(n)。

圖3 鏈式鄰域示意圖Fig. 3 Schematic diagram of chain neighborhood

3)切割鄰域。

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

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

4)合并鄰域。

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

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

3.2 結果評估

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

傳統成本評估需要計算當前方案S的總花費和鄰域操作前后的解決方案S1的總花費，S和S1總花費計算如式(20)、(21)所示，這樣會浪費大量的計算時間，由于S1與S僅部分合乘小組用戶發生變化，本文設計了一種有效的方法來對VNSA-LTCPP提供的解決方案進行評估。這種評估僅應用于鄰域操作后小組成員發生變化的合乘小組，S′為發生變化的合乘小組在鄰域操作前的原合乘小組集合，S"為鄰域操作后發生變化的合乘小組集合。成本評估如式(22)、(23)所示。這種增量評估及其復雜性取決于目標優化問題所使用的鄰域操作。其中交換、切割和合并鄰域操作只評估兩個變換的合乘小組。對于鏈式鄰域操作，變換的合乘小組數量由實際的鄰域操作所決定。由于減少了評估對象的數量，這種評估方法可以大幅提高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求解過程依次應用交換鄰域(Exchange Neighborhood)、鏈式鄰域(Chain Neighborhood)、切割鄰域(Cut Neighborhood)、合并鄰域(Combine Neighborhood)這四個鄰域搜索操作。VNSA-LTCPP求解具體流程如下：

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

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

3)對S進行鏈式鄰域操作，每次操作完成后對新生成的合乘方案進行約束驗證與修復并進行結果評估得到S1,若出行總花費沒有降低則執行步驟4)；否則用S1替代S,重新對S進行步驟3)操作，直至操作次數達到該鄰域操作規定的局部優化次數。

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

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

6)若迭代次數i達到規定的迭代次數，則VNSA-LTCPP求解過程結束；否則迭代次數i加1，轉到步驟2)。

4 實驗

4.1 測試環境

軟件環境為Java虛擬機SUN JDK1.8.0_111，硬件環境為64位Windows10系統,Intel Core i7 2.5 GHz CPU,8 GB RAM。

4.2 實驗算例

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

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

4.3 實驗結果與分析

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

為了驗證計算時間與迭代次數和算例規模之間的關系，本文對于每種規模算例的平均計算時間進行分析，其中每種規模算例的平均計算時間為每種規模5組算例的平均計算時間。從圖7可以看出，當算例規模一定時，計算時間隨著迭代次數的增加而增長，同時計算時間的增長速率隨著迭代次數的增加而趨緩，這是由于隨著迭代次數的增加，合乘方案的質量逐步提高，鄰域搜索中的交換鄰域和鏈式鄰域的局部優化概率降低，對應的鄰域搜索時間會減少。當迭代次數一定時，計算時間會隨著算例規模的增長而增長，時間增長速率約為算例規模增長速率的80%～90%，因此對于1 000人以上的較大規模算例HVNSA仍具有一定的時效性。

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

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

第一組：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。

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

表1 S1-1、S2-1、S3-1和S4-1的計算結果Tab. 1 Calculation results of S1-1, S2-1, S3-1 and S4-1

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

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

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

表2 四種規模算例的計算結果Tab. 2 Calculation results of four scale examples

5 結語

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