郭羽含，伊 鵬

遼寧工程技術大學 軟件學院，遼寧 葫蘆島 125100

1 引言

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

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

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

2 車輛合乘問題數(shù)學模型

2.1 問題定義

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

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

2.2 合乘模型符號定義

2.2.1 常量定義

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

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

2.2.2 變量定義

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

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

2.3 目標函數(shù)

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

則有目標函數(shù)：

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

2.4 數(shù)學模型

長期車輛合乘問題的數(shù)學模型表示如下：

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

3 LTCPP合乘方案

3.1 合乘方案表述

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

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

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

3.2 初始合乘方案

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

第一步選擇n個用戶來構建n個合乘小組。此n個用戶作為每個合乘小組的初始司機，其余未被選擇為司機的用戶將被分配至以上合乘小組中。具體步驟如下。

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

然后，從用戶集合的剩余用戶中隨機選擇用戶b來構建另一個合乘小組，繼而將用戶b和用戶集合中距離用戶b最近的m個用戶移除。當所有用戶從用戶集合中刪除時，該過程結束。

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

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

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

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

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

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

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

（1）選出該合乘小組中n個相互距離最遠的用戶作為新的n個合乘小組的司機。

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

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

獲取初始合乘方案的算法設計如下所示：

4 變鄰域搜索

為了使變鄰域搜索算法適應本文特定的長期車輛合乘問題，需定義針對本問題的鄰域結構，建立適用于合乘方案的搜索過程，并且利用Spark分布式平臺將算法部署到多臺計算機上進行并行計算。

4.1 鄰域設計

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

（1）混合鄰域N1。混合鄰域通過交換兩個合乘小組中的用戶達到降低兩個合乘小組總出行成本的目的。首先計算合乘方案S中的所有合乘小組P的重心坐標(wx，wy)，如式（21）所示。

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

對于Stemp中合乘小組與P1進行如下操作：

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

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

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

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

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

（2）鏈式鄰域N2。鏈式鄰域將當前合乘小組中距離合乘小組重心較遠的用戶移動到距離當前合乘小組重心距離更近的其他合乘小組中，從而降低出行成本。鏈式鄰域操作如下所示：

①構建一個合乘小組循環(huán)鏈表L存儲合乘小組。

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

③在S中隨機選擇一個滿足式（25）的合乘小組Pr作為L的第一個元素，并從S中刪除Pr；如果S中沒有滿足式（25）的合乘小組，則鏈式鄰域搜索結束。

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

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

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

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

鏈式鄰域的示例圖如圖4所示。該操作的復雜度為O(n2)。

Fig.4 Example of chain neighborhood圖4 鏈式鄰域示例圖

（3）分割鄰域N3。分割鄰域將一個出行成本較高、用戶間距離較遠的合乘小組分割成多個合乘小組，使各合乘小組總出行成本降低。分割鄰域每次可以將一個非獨自駕車的合乘小組分為兩個合乘小組。分割鄰域首先對每一個非獨自駕車的合乘小組計算該小組中所有用戶的重心距離差之和sumP，如式（26）所示。

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

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

（4）合并鄰域N4。合并鄰域將兩個合乘小組合并成一個合乘小組從而降低出行成本。合并鄰域操作每次可合并兩個人數(shù)沒有達到車容量約束的合乘小組，并且合并后的合乘小組滿足式（8）的約束。其具體操作如下：

①構建一個合乘小組S1存儲合乘小組集合S中人數(shù)未達到車容量的合乘小組。若S1中的合乘小組數(shù)量小于2，則合并鄰域搜索結束。

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

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

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

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

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

4.2 結果評估

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

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

在評估之前首先檢查各合乘小組的行駛時間和時間窗約束，對于不滿足行駛時間和時間窗口約束的合乘小組將通過與構建初始合乘方案中使用的相同修復過程進行修復。

4.3 VNS-LTCPP的主要結構

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

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

4.4 VNS-LTCPP分布式結構

4.4.1 Spark基本概念

Spark是一個分布式的內存計算框架，其特點是能處理大規(guī)模數(shù)據(jù)，計算速度快。Spark延續(xù)了Hadoop的MapReduce計算模型，相比之下Spark的計算過程保持在內存中，減少了硬盤讀寫，能夠將多個操作進行合并后計算，因此提升了計算速度。同時Spark也提供了更豐富的計算API。

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

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

4.4.2 VNS-LTCPP算法分布式設計

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

Fig.7 VNS-LTCPPalgorithm distributed structure diagram圖7 VNS-LTCPP算法分布式結構圖

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

為了減少通信時間的損耗，Master節(jié)點將任務傳輸給各個Worker節(jié)點中進行計算，每個Worker節(jié)點中的任務負責對合乘方案進行規(guī)定迭代次數(shù)的優(yōu)化得到最終的優(yōu)化合乘方案，任務完成迭代優(yōu)化后通過Reduce操作將合乘方案傳輸回Master節(jié)點進行處理。

5 實驗結果與分析

5.1 實驗配置環(huán)境

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

5.2 實驗數(shù)據(jù)及參數(shù)設置

Table 3 Cluster configuration表3 集群配置

實驗所用算例由Solomon標準算例修改所得，算例的規(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ù)設置：α=0.8,β=0.2，100人算例迭代次數(shù)為500次，200人算例迭代次數(shù)為1 000次，400人算例迭代次數(shù)為1 500次，1 000人算例迭代次數(shù)為3 000次。

5.3 實驗結果分析

為驗證VNS-LTCPP算法的收斂速度，本文對S1_1、S2_1、S3_1和S4_1進行實驗計算，其中S1_1與S2_1的最低成本由Cplex平臺計算得出，S3_1、S4_1由于算例規(guī)模較大通過Cplex平臺無法在合理時間內計算出最低成本。實驗對4個算例分別運行計算10次，并從每個算例10組實驗結果中隨機選取5組實驗數(shù)據(jù)，實驗結果如圖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算法可以快速收斂，但實驗的收斂速度隨著算例的規(guī)模增大而減緩，實驗結果的偏差也會隨著算例規(guī)模的增大而變大。同時由于在構建初始合乘方案時，司機的選擇具有隨機性，因此在相同算例的各次實驗中所得合乘方案均有所不同，造成了初始合乘方案的出行成本有所差異。對于生成質量較差的初始合乘方案同樣可以得到很好的優(yōu)化結果。由圖8、圖9可以看出VNS-LTCPP算法的收斂所得的最終成本也趨近于最低成本。

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

Table 4 Precision experimental test表4 精度實驗測試

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

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

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

Table 5 Distributed contrast experiment表5 分布式對比實驗

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

6 結束語

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