PC集群環(huán)境下的并行地理網(wǎng)絡(luò)車(chē)輛路徑算法

閆志遠(yuǎn),孫文彬,陳宗娟,趙帥陽(yáng)

中國(guó)礦業(yè)大學(xué)(北京)地球科學(xué)與測(cè)繪工程學(xué)院,北京 100083

PC集群環(huán)境下的并行地理網(wǎng)絡(luò)車(chē)輛路徑算法

閆志遠(yuǎn),孫文彬,陳宗娟,趙帥陽(yáng)

中國(guó)礦業(yè)大學(xué)(北京)地球科學(xué)與測(cè)繪工程學(xué)院,北京 100083

針對(duì)PC集群計(jì)算節(jié)點(diǎn)內(nèi)存小、進(jìn)程間通信速度慢的問(wèn)題,設(shè)計(jì)了分布式的數(shù)據(jù)存儲(chǔ)機(jī)制;提出了用同步變換規(guī)則代替解編碼傳輸?shù)倪M(jìn)程間通信方式;基于鄰域分解策略實(shí)現(xiàn)了禁忌搜索過(guò)程的并行化,發(fā)展了一種適用于PC集群環(huán)境的并行地理網(wǎng)絡(luò)VRP算法。應(yīng)用模擬路網(wǎng)數(shù)據(jù)進(jìn)行了相關(guān)試驗(yàn),結(jié)果表明,本文算法的計(jì)算結(jié)果與ArcGIS基本一致,二者平均偏差率在2．11%～2．87%之間;分布式數(shù)據(jù)存儲(chǔ)策略有效地降低了各進(jìn)程對(duì)內(nèi)存的需求量,保證了算法的穩(wěn)健性和擴(kuò)展性;通過(guò)算法的并行化提高了VRP算法的求解效率;該算法具有良好的加速性能,8進(jìn)程時(shí)在各測(cè)試數(shù)據(jù)集中的加速比均在4．46～6．32之間。

地理網(wǎng)絡(luò)分析;車(chē)輛路徑問(wèn)題;禁忌搜索;并行算法

1 引 言

車(chē)輛路徑問(wèn)題(vehicle routing problem, VRP)是對(duì)車(chē)輛的運(yùn)行線(xiàn)路進(jìn)行合理規(guī)劃與優(yōu)化,在滿(mǎn)足各種約束條件的情況下,使車(chē)輛以最小的費(fèi)用通過(guò)所有裝貨點(diǎn)或卸貨點(diǎn)[1]。獲取VRP問(wèn)題的最優(yōu)解具有重要的實(shí)用價(jià)值,能有效降低物流運(yùn)輸?shù)某杀?。因?VRP問(wèn)題一直是運(yùn)籌學(xué)、GIS網(wǎng)絡(luò)分析研究中的熱點(diǎn)問(wèn)題之一。VRP是一個(gè)經(jīng)典的NP(non-deterministic polynomial)問(wèn)題,無(wú)法在多項(xiàng)式時(shí)間內(nèi)獲取精確解,且隨著客戶(hù)點(diǎn)數(shù)的增加,可選車(chē)輛路徑方案數(shù)量和求解時(shí)間均呈幾何級(jí)數(shù)式增長(zhǎng)[2]。隨著實(shí)際應(yīng)用中VRP規(guī)模的不斷擴(kuò)大,傳統(tǒng)的串行算法已無(wú)法滿(mǎn)足大規(guī)模地理網(wǎng)絡(luò)VRP問(wèn)題的求解需要。

而并行技術(shù)能夠充分利用多核、多CPU、GPU、PC集群、大規(guī)模并行計(jì)算機(jī)等提供的高性能計(jì)算能力,大幅提高地理運(yùn)算的效率[3-6]。國(guó)內(nèi)外學(xué)者應(yīng)用不同的并行策略對(duì)VRP算法進(jìn)行了深入的研究。文獻(xiàn)[7—8]基于迭代局部搜索框架和禁忌搜索算法,設(shè)計(jì)了并行VRP算法;文獻(xiàn)[9]應(yīng)用客戶(hù)點(diǎn)集分割的策略,發(fā)展了一種結(jié)合局部搜索與整數(shù)規(guī)劃的并行算法;文獻(xiàn)[10]將多種不同的鄰域結(jié)構(gòu)融入禁忌搜索過(guò)程,提出多鄰域協(xié)作并行VRP算法;文獻(xiàn)[11]設(shè)計(jì)了自適應(yīng)大鄰域局部搜索算法;文獻(xiàn)[12]提出了基于雙禁忌對(duì)象的并行禁忌搜索算法。但上述并行VRP算法多以大規(guī)模并行服務(wù)器(計(jì)算節(jié)點(diǎn)數(shù)＞128)為基礎(chǔ),針對(duì)基于PC集群的并行VRP算法研究較少。PC集群成本低廉,易于搭建與維護(hù),是應(yīng)用最為廣泛的并行算法運(yùn)行平臺(tái)。但與大規(guī)模并行硬件環(huán)境相比,PC集群存在著計(jì)算節(jié)點(diǎn)內(nèi)存小、通信速度慢等問(wèn)題。為此,本文擬以PC集群環(huán)境為基礎(chǔ),設(shè)計(jì)分布式數(shù)據(jù)存儲(chǔ)結(jié)構(gòu),以降低算法對(duì)內(nèi)存的需求量,并采用鄰域分解策略實(shí)現(xiàn)VRP算法的并行化,通過(guò)精簡(jiǎn)通信數(shù)據(jù)結(jié)構(gòu)降低計(jì)算節(jié)點(diǎn)間的通信開(kāi)銷(xiāo),進(jìn)而提高PC集群環(huán)境中求解大規(guī)模地理網(wǎng)絡(luò)VRP問(wèn)題的效率。

2 并行地理網(wǎng)絡(luò)VRP算法

2．1 地理網(wǎng)絡(luò)VRP算法流程

求解VRP時(shí),需要反復(fù)用到網(wǎng)絡(luò)節(jié)點(diǎn)(包括客戶(hù)點(diǎn)和車(chē)場(chǎng)點(diǎn))中任意兩點(diǎn)間的距離。圖論中,網(wǎng)絡(luò)節(jié)點(diǎn)間的距離多采用歐氏距離[13],見(jiàn)圖1(a),計(jì)算簡(jiǎn)單快捷,無(wú)須設(shè)計(jì)相應(yīng)的矩陣進(jìn)行存儲(chǔ)。而地理網(wǎng)絡(luò)中,網(wǎng)絡(luò)節(jié)點(diǎn)間距離多采用節(jié)點(diǎn)間最短路徑的距離值,見(jiàn)圖1(b)。由于最短路徑求解用時(shí)遠(yuǎn)多于歐氏距離的計(jì)算耗時(shí),因此,地理網(wǎng)絡(luò)VRP求解過(guò)程中需建立網(wǎng)絡(luò)節(jié)點(diǎn)間的距離矩陣, 即origin-destination(OD)矩陣。隨著地理網(wǎng)絡(luò)規(guī)模的擴(kuò)大,OD矩陣所需存儲(chǔ)空間將呈指數(shù)形式增長(zhǎng),從而導(dǎo)致PC集群各計(jì)算節(jié)點(diǎn)出現(xiàn)內(nèi)存不足的問(wèn)題。因此,需采用分布式存儲(chǔ)結(jié)構(gòu),以減少OD矩陣對(duì)內(nèi)存的占用量。在獲取OD矩陣的基礎(chǔ)上,應(yīng)用隨機(jī)法產(chǎn)生初始解,采用鄰域分解策略對(duì)VRP迭代優(yōu)化過(guò)程進(jìn)行并行化,以獲取客戶(hù)點(diǎn)序號(hào)編碼,即VRP問(wèn)題的解。最后,為了獲取實(shí)際的運(yùn)輸路徑,需將客戶(hù)點(diǎn)序號(hào)編碼轉(zhuǎn)換為車(chē)輛的實(shí)際運(yùn)送路徑。地理網(wǎng)絡(luò)VRP問(wèn)題的求解流程如圖2所示。

圖1 VRP中的距離值Fig．1 Distance in VRP

圖2 地理網(wǎng)絡(luò)VRP求解流程Fig．2 Procedure of solving VRP in geographical network

2．2 OD矩陣計(jì)算及并行化

OD矩陣包括距離矩陣D和前趨矩陣P兩部分:前者記錄了任意兩節(jié)點(diǎn)間的最短距離;后者記錄了任意兩節(jié)點(diǎn)間的最短路徑。它們均是地理網(wǎng)絡(luò)VRP求解的基礎(chǔ)。假設(shè)c為客戶(hù)點(diǎn)數(shù),w為車(chē)場(chǎng)數(shù),n為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù),則矩陣D的大小為(c＋w)×(c＋w),矩陣P的大小為(c＋w)×n。通常網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)n遠(yuǎn)大于c,因此P遠(yuǎn)大于D。以網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)n＝200 000,客戶(hù)點(diǎn)數(shù)c＝3000,車(chē)場(chǎng)數(shù)w＝1的VRP問(wèn)題為例,假設(shè)每個(gè)矩陣元素占4 Byte,OD矩陣將占用大約2．4 GB的內(nèi)存空間。若不對(duì)OD矩陣的存儲(chǔ)方式進(jìn)行優(yōu)化處理,很容易出現(xiàn)各計(jì)算節(jié)點(diǎn)內(nèi)存不足的問(wèn)題。此外, OD矩陣的計(jì)算也是VRP求解過(guò)程中耗時(shí)最多的環(huán)節(jié)。筆者利用ArcGIS提供的VRP分析工具,使用試驗(yàn)數(shù)據(jù)(網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為100 703個(gè),邊數(shù)為124 164條,車(chē)場(chǎng)個(gè)數(shù)為1,客戶(hù)點(diǎn)數(shù)為1000 個(gè),車(chē)輛數(shù)為10輛)測(cè)試了OD矩陣計(jì)算用時(shí)占算法整體時(shí)間的比重。結(jié)果表明:OD矩陣計(jì)算耗時(shí)占VRP算法總用時(shí)的65%,是VRP算法中耗時(shí)最多的環(huán)節(jié)之一。因此,降低OD矩陣的存儲(chǔ)開(kāi)銷(xiāo)、減少OD矩陣的計(jì)算用時(shí)對(duì)保證VRP算法的穩(wěn)健性和高效性具有重要意義。

為了降低OD矩陣的內(nèi)存開(kāi)銷(xiāo),本文采用了分布式存儲(chǔ)的策略。矩陣D占用內(nèi)存空間較小,且為后續(xù)禁忌搜索過(guò)程的基礎(chǔ),因此各進(jìn)程均存儲(chǔ)完整的D;而矩陣P十分龐大,且僅用于后續(xù)的路徑轉(zhuǎn)換過(guò)程,因而將其分布式存儲(chǔ)于各進(jìn)程中。通過(guò)這種策略,單進(jìn)程內(nèi)存開(kāi)銷(xiāo)近似減少為原來(lái)的1/p(p為進(jìn)程數(shù))。同時(shí),為了提高OD矩陣的計(jì)算效率,引入并行Johnson算法來(lái)獲取各客戶(hù)點(diǎn)及車(chē)場(chǎng)點(diǎn)間的最短路徑。具體實(shí)現(xiàn)過(guò)程如下:首先,將c＋w個(gè)源點(diǎn)(包括客戶(hù)點(diǎn)和車(chē)場(chǎng)點(diǎn))平均分配至p個(gè)進(jìn)程,每個(gè)進(jìn)程分別計(jì)算(c＋w)/p個(gè)源點(diǎn)的最短路徑,得到部分D和P;然后,應(yīng)用訊息傳遞接口(message passing interface, MPI)中的Allgather函數(shù)對(duì)D進(jìn)行同步操作,使得各進(jìn)程均獲得完整的矩陣D,如圖3所示(以4進(jìn)程為例)。通過(guò)分布式存儲(chǔ)策略和并行Johnson算法,OD矩陣計(jì)算過(guò)程的時(shí)間復(fù)雜度降低為O(cn log n/p),空間復(fù)雜度降低為O(cn/p)。由此可以看出,隨著進(jìn)程數(shù)的增加,該算法能夠處理更大規(guī)模的OD矩陣,具有很強(qiáng)的擴(kuò)展性。

圖3 DM矩陣的同步方法Fig．3 Synchronizing of distance matrix

2．3 禁忌搜索過(guò)程及并行化

VRP問(wèn)題無(wú)法在多項(xiàng)式時(shí)間內(nèi)獲得精確解,因此多采用啟發(fā)式算法來(lái)求解[14]。禁忌搜索算法是一種常用的啟發(fā)式算法,是解決組合優(yōu)化問(wèn)題行之有效的方法[15]。該算法采用一定的藐視準(zhǔn)則使搜索過(guò)程跳出局部最優(yōu)解,從而提高了獲得全局最優(yōu)解的可能性[16]。國(guó)內(nèi)外大量研究成果表明,禁忌搜索算法是解決VRP問(wèn)題的有效途徑,具有求解效率高、解質(zhì)量穩(wěn)定等優(yōu)點(diǎn)[17-23]。因此,本文擬對(duì)串行禁忌搜索算法進(jìn)行并行化,來(lái)完成VRP問(wèn)題的求解。

禁忌搜索算法的實(shí)現(xiàn)流程如圖4所示。首先,采用隨機(jī)法(輔以最低成本增加法)構(gòu)建若干初始解,選取目標(biāo)函數(shù)值最小的解作為當(dāng)前解S和最優(yōu)解S?。然后利用迭代鄰域搜索對(duì)最優(yōu)解進(jìn)行優(yōu)化,具體過(guò)程如下:①利用隨機(jī)交換法和插入法得到S的鄰域;②從鄰域中搜索目標(biāo)函數(shù)值最小的解S′,判斷其是否滿(mǎn)足特赦準(zhǔn)則,若滿(mǎn)足則用該解更新最優(yōu)解S?,否則判斷其禁忌屬性,若未被禁忌則用該解更新當(dāng)前解S,否則繼續(xù)搜索鄰域中其他解;③更新禁忌表,判斷是否滿(mǎn)足終止條件。當(dāng)該迭代過(guò)程達(dá)到終止條件后,即得到最終解S?。從禁忌搜索算法的實(shí)現(xiàn)過(guò)程可以看出,由于禁忌準(zhǔn)則的使用,各次迭代間具有內(nèi)在的關(guān)聯(lián)性。若采用任務(wù)劃分的方式進(jìn)行并行化,會(huì)破壞禁忌搜索機(jī)制,從而影響最終的求解質(zhì)量。因此,本文采用細(xì)粒度的并行方式,對(duì)鄰域搜索過(guò)程進(jìn)行并行化。具體實(shí)現(xiàn)過(guò)程如下:首先,將待搜索鄰域中的N個(gè)鄰解平均分配至p個(gè)進(jìn)程,各進(jìn)程分別搜索N/p個(gè)鄰域解得到局部最優(yōu)解;然后,由主進(jìn)程回收各進(jìn)程的局部最優(yōu)解,比較得到全局最優(yōu)解后再?gòu)V播給各進(jìn)程;最后,各進(jìn)程根據(jù)鄰域搜索獲得的最優(yōu)解更新當(dāng)前解、最優(yōu)解和禁忌表。在解的迭代優(yōu)化過(guò)程中,鄰域搜索過(guò)程耗時(shí)最多,通過(guò)對(duì)該過(guò)程的并行化可以有效提高禁忌搜索的效率。

圖4 禁忌搜索算法流程Fig．4 Flow chart of tabu search

在并行鄰域搜索過(guò)程中,各進(jìn)程需要頻繁地進(jìn)行數(shù)據(jù)交換。若采用發(fā)送解編碼的方式進(jìn)行同步,一次迭代中的通信量將達(dá)到2s個(gè)整型值(s為解編碼長(zhǎng)度,約等于客戶(hù)點(diǎn)數(shù)),會(huì)產(chǎn)生大量的通信開(kāi)銷(xiāo)。為此,本文引入一種新的通信模式。為了減少通信量,采用發(fā)送解編碼變換規(guī)則的方式,無(wú)須發(fā)送完整的解編碼。與解編碼相比,編碼變換規(guī)則的長(zhǎng)度僅為8個(gè)整型,大幅降低了通信量,提高了進(jìn)程間的通信效率。具體實(shí)現(xiàn)步驟如下:①各從進(jìn)程發(fā)送局部最優(yōu)解的目標(biāo)函數(shù)值至主進(jìn)程(通信量為1個(gè)整型);②主進(jìn)程進(jìn)行比較后得到全局最優(yōu)值,并將該值對(duì)應(yīng)的解所在進(jìn)程編號(hào)廣播給各進(jìn)程(通信量為1個(gè)整型);③由包含最優(yōu)解的進(jìn)程向其他各進(jìn)程廣播最優(yōu)解的編碼變換規(guī)則(通信量為8個(gè)整型)。由此過(guò)程可以看出,每次鄰域搜索的通信量為10個(gè)整型數(shù)據(jù)。解編碼變換規(guī)則可用向量T(含8個(gè)整型)表示

式中,r1、r2為線(xiàn)路編號(hào);c1、c2為客戶(hù)點(diǎn)編號(hào); p11、p12、p21、p22為客戶(hù)點(diǎn)在線(xiàn)路中的位置編號(hào)。試驗(yàn)表明,當(dāng)客戶(hù)點(diǎn)數(shù)c＝1000時(shí),采用同步“變換規(guī)則”的方式可將進(jìn)程間的通信量減少為原來(lái)的1/200。

3 試驗(yàn)與分析

3．1 試驗(yàn)環(huán)境及測(cè)試數(shù)據(jù)

為了驗(yàn)證算法的有效性和正確性,本文利用模擬的路網(wǎng)數(shù)據(jù)進(jìn)行了相關(guān)試驗(yàn)。試驗(yàn)環(huán)境為兩臺(tái)雙核計(jì)算機(jī)(CPU為Intel Core i3-530,內(nèi)存為3．24 GB)和一臺(tái)四核計(jì)算機(jī)(CPU為Intel Core i5-2400,內(nèi)存為3．24 GB)組成的Windows PC集群,最多可運(yùn)行8個(gè)進(jìn)程。消息傳遞接口采用MPICH2。試驗(yàn)數(shù)據(jù)為6個(gè)人工生成的測(cè)試數(shù)據(jù)集,如表1所示。試驗(yàn)均將車(chē)輛數(shù)(等價(jià)于距離約束)和每輛車(chē)的容量設(shè)為約束條件,以配送路徑長(zhǎng)度總和為目標(biāo)函數(shù)值?？蛻?hù)點(diǎn)和車(chē)場(chǎng)點(diǎn)均從網(wǎng)絡(luò)節(jié)點(diǎn)中隨機(jī)選取。

表1 測(cè)試數(shù)據(jù)集Tab．1 Testing datasets

3．2 串行VRP算法的耗時(shí)情況分析

CT(Computed Tomography)，即電子計(jì)算機(jī)斷層掃描技術(shù)在醫(yī)學(xué)病情診斷等領(lǐng)域具有重要地位。然而CT技術(shù)的應(yīng)用對(duì)其系統(tǒng)精度具有較高的要求，少許誤差即可能造成診斷失誤。[1-2]但實(shí)際CT系統(tǒng)成像往往存在一定的機(jī)械誤差，使得其成像效果與理想設(shè)計(jì)值之間偏差較大。且CT系統(tǒng)射線(xiàn)源、轉(zhuǎn)臺(tái)和探測(cè)器間的相對(duì)位置關(guān)系，以及標(biāo)定模板信息的離散性均會(huì)影響重建圖像是否存在偽影。此外，運(yùn)動(dòng)偽影也是造成CT系統(tǒng)誤差的一個(gè)重要因素，[3-5]研究運(yùn)動(dòng)偽影的消除技術(shù)對(duì)研究如何提高成像質(zhì)量具有重要意義。

為了驗(yàn)證VRP并行策略的可行性,分別統(tǒng)計(jì)了串行VRP算法中各計(jì)算環(huán)節(jié)的耗時(shí)情況。由于禁忌搜索算法是啟發(fā)式算法,每次的運(yùn)行結(jié)果略有不同,取10次運(yùn)行結(jié)果的平均值作為最終結(jié)果。測(cè)試結(jié)果如表2和圖5所示。其中,OD項(xiàng)表示OD矩陣計(jì)算時(shí)間;TS項(xiàng)表示禁忌搜索時(shí)間;其他項(xiàng)表示數(shù)據(jù)讀取、預(yù)處理等過(guò)程所消耗的時(shí)間。

圖5 串行VRP算法各部分耗時(shí)比重Fig．5 Time consumption of each procedure in serial VRP algorithm

表2 串行VRP算法耗時(shí)分析Tab．2 Running time of serial VRP algorithm

表2中,采用單進(jìn)程進(jìn)行VRP求解時(shí),由于計(jì)算過(guò)程均放在一個(gè)計(jì)算節(jié)點(diǎn)內(nèi)執(zhí)行,未進(jìn)行數(shù)據(jù)的分布式存儲(chǔ),導(dǎo)致測(cè)試數(shù)據(jù)集6出現(xiàn)內(nèi)存不足的問(wèn)題,無(wú)法求出最終結(jié)果。其他測(cè)試結(jié)果表明,OD計(jì)算耗時(shí)占算法總用時(shí)的比重在14．1%～60．0%之間,TS計(jì)算過(guò)程用時(shí)占算法總用時(shí)的比重在30．2%～85．4%之間;OD矩陣計(jì)算和TS過(guò)程用時(shí)總和占算法總用時(shí)的比重在90．2%～99．5%之間。因此,對(duì)VRP算法中的OD矩陣計(jì)算和TS搜索過(guò)程進(jìn)行并行化,能有效提高VRP算法的整體性能。

3．3 OD矩陣計(jì)算的存儲(chǔ)開(kāi)銷(xiāo)及并行效率分析

為了進(jìn)一步分析分布式存儲(chǔ)策略對(duì)內(nèi)存使用的影響,以測(cè)試數(shù)據(jù)6為例,分別測(cè)試了采用不同進(jìn)程數(shù)時(shí)OD矩陣計(jì)算過(guò)程的內(nèi)存消耗情況。采用單進(jìn)程時(shí),由于無(wú)法發(fā)揮分布式存儲(chǔ)策略的作用,VRP求解過(guò)程中出現(xiàn)了內(nèi)存不足的現(xiàn)象。因此,本文僅測(cè)試采用2～8個(gè)進(jìn)程時(shí),OD矩陣計(jì)算的內(nèi)存使用情況,如圖6所示。結(jié)果表明:采用兩個(gè)進(jìn)程時(shí),每個(gè)進(jìn)程的內(nèi)存開(kāi)銷(xiāo)約為1．2 GB;隨著進(jìn)程數(shù)的增加,單進(jìn)程的內(nèi)存消耗量逐步降低;采用8個(gè)進(jìn)程時(shí),每個(gè)進(jìn)程的內(nèi)存開(kāi)銷(xiāo)減少為約0．35 GB。盡管采用8個(gè)進(jìn)程時(shí)的總內(nèi)存消耗量與單進(jìn)程時(shí)基本一致,但是分布式的存儲(chǔ)機(jī)制充分利用了PC集群中各節(jié)點(diǎn)的內(nèi)存資源,從而有效避免了單節(jié)點(diǎn)內(nèi)存消耗過(guò)大的問(wèn)題。

圖6 OD矩陣計(jì)算的內(nèi)存開(kāi)銷(xiāo)情況Fig．6 Per-process memory consumption of OD matrix computing

為了測(cè)試并行OD矩陣計(jì)算過(guò)程的效率,應(yīng)用測(cè)試數(shù)據(jù)進(jìn)行了相關(guān)試驗(yàn),結(jié)果如表3所示。由表3可知:隨著參與運(yùn)算的進(jìn)程數(shù)的增加,OD矩陣計(jì)算用時(shí)在各測(cè)試數(shù)據(jù)中均出現(xiàn)了明顯的加速效果。采用兩個(gè)進(jìn)程時(shí),算法在各測(cè)試數(shù)據(jù)中的加速比(算法單進(jìn)程運(yùn)行時(shí)間與多進(jìn)程運(yùn)行時(shí)間的比值)均在1．81以上;采用8個(gè)進(jìn)程時(shí),算法加速比均在4．63以上。為了更直觀地表示算法時(shí)間與進(jìn)程之間的關(guān)系,依據(jù)所用進(jìn)程數(shù)和算法運(yùn)行時(shí)間繪制了二者的關(guān)系曲線(xiàn),如圖7所示。由圖可見(jiàn),隨著進(jìn)程數(shù)的增加,算法耗時(shí)呈下降趨勢(shì),加速效果明顯。

表3 并行OD矩陣計(jì)算的運(yùn)行時(shí)間和加速比Tab．3 Running time and speedup of parallel OD matrix computing

圖7 并行OD矩陣計(jì)算的運(yùn)行時(shí)間Fig．7 Running time of parallel OD matrix computing

3．4 禁忌搜索的參數(shù)設(shè)置及并行效率分析

禁忌搜索中的鄰域大小直接影響求解的質(zhì)量和效率。經(jīng)大量試驗(yàn)得出:鄰域大小為(c＋w)2/ 200(c＋w為客戶(hù)點(diǎn)數(shù)和車(chē)場(chǎng)數(shù)之和)時(shí)效果最佳;此時(shí),VRP算法能夠兼顧計(jì)算效率和解質(zhì)量。并行禁忌搜索過(guò)程的運(yùn)行時(shí)間如表4所示。表4表明:隨著進(jìn)程數(shù)的增加,并行禁忌搜索耗時(shí)總體呈下降趨勢(shì)。在禁忌搜索過(guò)程中,新解的生成采用了一些隨機(jī)方法,以保證解的多樣性。這使得生成新解的時(shí)間不穩(wěn)定,導(dǎo)致整個(gè)鄰域搜索過(guò)程的時(shí)間出現(xiàn)波動(dòng)。因此,表4中測(cè)試數(shù)據(jù)1、2、3、5在多進(jìn)程計(jì)算時(shí),出現(xiàn)了超加速比的情況(表中用黑體表示);在進(jìn)程數(shù)為7和8時(shí)產(chǎn)生了耗時(shí)波動(dòng)情況。根據(jù)禁忌搜索耗時(shí)和進(jìn)程數(shù)的關(guān)系繪制它們之間的關(guān)系曲線(xiàn),如圖8所示。由圖可見(jiàn),測(cè)試數(shù)據(jù)1和4、2和5、3和6的曲線(xiàn)基本重合。該結(jié)果表明:在不同規(guī)模的測(cè)試數(shù)據(jù)中,禁忌搜索的時(shí)間主要取決于客戶(hù)點(diǎn)的數(shù)量,與網(wǎng)絡(luò)規(guī)模無(wú)關(guān)。

表4 并行禁忌搜索的運(yùn)行時(shí)間和加速比Tab．4 Running time and speedup of parallel tabu search

圖8 并行禁忌搜索的運(yùn)行時(shí)間Fig．8 Running time of parallel tabu search

3．5 并行VRP算法的效率及解質(zhì)量分析

為了對(duì)算法的整體效率進(jìn)行評(píng)價(jià),對(duì)算法的總用時(shí)情況進(jìn)行統(tǒng)計(jì),結(jié)果如表5和圖9所示。隨著進(jìn)程數(shù)的增加,算法的運(yùn)行時(shí)間均呈明顯的下降趨勢(shì)。在測(cè)試數(shù)據(jù)3中的運(yùn)行時(shí)間由單進(jìn)程時(shí)的603．6 s減少為8進(jìn)程時(shí)的95．42 s;采用7～8個(gè)進(jìn)程時(shí),在各測(cè)試數(shù)據(jù)中的算法加速比均在4．46～6．32之間。由此可見(jiàn),采用并行技術(shù)能有效提高算法的運(yùn)算效率。某些試驗(yàn)結(jié)果出現(xiàn)了超加速比的現(xiàn)象(表中用黑體表示),其原因在3．4節(jié)中已闡述。

圖9 并行VRP算法的運(yùn)行時(shí)間Fig．9 Running time of parallel VRP algorithm

表5 并行VRP算法的運(yùn)行時(shí)間和加速比Tab．5 Running time and speedup of parallel VRP algorithm

為了驗(yàn)證計(jì)算結(jié)果的正確性,本文將算法的運(yùn)行結(jié)果與ArcGIS進(jìn)行了對(duì)比。首先,將測(cè)試數(shù)據(jù)導(dǎo)入Arc GIS中,用ArcGIS的VRP分析工具求出運(yùn)輸路徑的目標(biāo)函數(shù)值。結(jié)果如表6所示,測(cè)試數(shù)據(jù)1—6的目標(biāo)函數(shù)值見(jiàn)欄目“ArcGIS結(jié)果”。然后,將本文算法的計(jì)算結(jié)果與上述結(jié)果進(jìn)行比較,用偏差率表示其差異性

式中,SPGVRP表示本文算法的計(jì)算結(jié)果;SArcGIS表示在ArcGIS中得到的結(jié)果。由表6可以看出,采用不同進(jìn)程數(shù)時(shí),本文算法在各測(cè)試數(shù)據(jù)中得到的目標(biāo)函數(shù)值與ArcGIS中的結(jié)果基本一致:最壞情況時(shí),偏差率為3．96%;最優(yōu)情況時(shí),偏差率為1．23%;平均偏差率均在2．11%～2．87%之間。

表6 并行VRP算法的分析結(jié)果Tab．6 The results of parallel VRP algorithm

4 結(jié) 論

針對(duì)圖論VRP問(wèn)題的并行算法已有較多研究成果,但是在地理網(wǎng)絡(luò)VRP中的實(shí)際應(yīng)用以及針對(duì)特定并行環(huán)境的算法中,還有很多問(wèn)題需要解決。本文提出的基于PC集群環(huán)境的并行VRP算法,通過(guò)分布式存儲(chǔ)結(jié)構(gòu)充分利用集群的內(nèi)存資源,有效避免了求解地理網(wǎng)絡(luò)VRP時(shí)單節(jié)點(diǎn)內(nèi)存不足的問(wèn)題;同時(shí),采用精簡(jiǎn)的通信策略以及基于鄰域分解的并行禁忌搜索算法,大幅提升了計(jì)算效率?；谀M路網(wǎng)數(shù)據(jù)的相關(guān)試驗(yàn)表明:本文算法能夠在保證計(jì)算精度的前提下(平均偏差率在2．11%～2．87%之間)高效地求解大規(guī)模地理網(wǎng)絡(luò)VRP問(wèn)題,且具有良好的擴(kuò)展性;同時(shí)能夠在PC集群環(huán)境中獲得良好的加速性能,采用8個(gè)進(jìn)程時(shí)的算法加速比在4．46～6．32之間。此外,本文研究著重于PC集群環(huán)境下的并行化方法,核心的求解算法僅采用了基本的禁忌搜索。因此,在求解質(zhì)量方面本文算法還有很大的提升空間。下一步研究工作將引入更高級(jí)的策略對(duì)禁忌搜索過(guò)程進(jìn)行優(yōu)化,進(jìn)一步提升求解質(zhì)量。

[1] LIU Xia．Research on Vehicle Routing Problem[D]．Wuhan: Huazhong University of Science and Technology,2007．(劉霞．車(chē)輛路徑問(wèn)題的研究[D]．武漢:華中科技大學(xué),2007．)

[2] LI Jun,GUO Yaohuang．Theories and Methods of Vehicle Scheduling Optimization[M]．Beijing:Chinese Materials Press,2001．(李軍,郭耀煌．車(chē)輛優(yōu)化調(diào)度理論與方法[M]．北京:中國(guó)物資出版社,2001．)

[3] XIAO Han,ZH ANG Zuxun．Parallel Image Matching Algorithm Based on GPGPU[J]．Acta Geodaetica et Cartographica Sinica,2010,39(1):46-51．(肖漢,張祖勛．基于GPGPU的并行影像匹配算法[J]．測(cè)繪學(xué)報(bào),2010, 39(1):46-51．)

[4] ZHAO Yuan,ZHANG Xinchang,KANG Tingjun．A Parallel Ant Colony Optimization Algorithm for Site Location[J]．Acta Geodaetica et Cartographica Sinica,2010,39(3):322-327．(趙元,張新長(zhǎng),康停軍．并行蟻群算法及其在區(qū)位選址中的應(yīng)用[J]．測(cè)繪學(xué)報(bào),2010,39(3):322-327．)

[5] ZOU Xiancai,LI Jiancheng,WANG Haihong,et al．Application of Parallel Computing with Open MP in Data Processing for Satellite Gravity[J]．Acta Geodaetica et Cartographica Sinica,2010,39(6):636-641．(鄒賢才,李建成,汪海洪,等．Open MP并行計(jì)算在衛(wèi)星重力數(shù)據(jù)處理中的應(yīng)用[J]．測(cè)繪學(xué)報(bào),2010,39(6):636-641．)

[6] SHEN Jie,GUO Lishuai,ZHU Wei,et al．Parallel Computing Suitability of Contour Simplification Based on MPI[J]．Acta Geodaetica et Cartographica Sinica,2013,42(4):621-628．(沈婕,郭立帥,朱偉,等．消息傳遞接口環(huán)境下等高線(xiàn)簡(jiǎn)化并行計(jì)算適宜性研究[J]．測(cè)繪學(xué)報(bào),2013,42(4): 621-628．)

[7] MAISCHBERGER M,CORDEAU J．Solving Variants of the Vehicle Routing Problem with a Simple Parallel Iterated Tabu Search,in Network Optimization[M]．Berlin:Springer,2011:395-400．

[8] CORDEAU J,MAISCHBERGER M．A Parallel Iterated Tabu Search Heuristic for Vehicle Routing Problems[J]．Computers and Operations Research,2012,39(9): 2033-2050．

[9] GROЁR C,GOLDEN B,WASIL E．A Parallel Algorithm for the Vehicle Routing Problem[J]．INFORMS Journal on Computing,2011,23(2):315-330．

[10] JIN J Y,CRAINIC T G,LOKKETANGEN A．A Parallel Multi-neighborhood Cooperative Tabu Search for Capacitated Vehicle Routing Problems[J]．European Journal of Operational Research,2012,222(3):441-451．

[11] RIBEIRO G M,LAPORTE G．An Adaptive Large Neighborhood Search Heuristic for the Cumulative Capacitated Vehicle Routing Problem[J]．Computers and Operations Research,2012,39(3):728-735．

[12] ZHU Haodong,LI Hongchan．Parallel Tabu Search Algorithm Based on Double Tabu Objects[J]．Computer Engineering and Applications,2011,47(29):31-33．(朱顥東,李紅嬋．基于雙禁忌對(duì)象的并行禁忌搜索算法[J]．計(jì)算機(jī)工程與應(yīng)用,2011,47(29):31-33．)

[13] SHI Yarong,WAN Difang,LI Shuangyan,et al．Research of Vehicle Routing Problem Based on GIS[J]．System Engineering Theory and Practice,2009,29(10):76-84．(史亞蓉,萬(wàn)迪昉,李雙燕,等．基于GIS的物流配送路線(xiàn)規(guī)劃研究[J]．系統(tǒng)工程理論與實(shí)踐．2009,29(10):76-84．)

[14] KEENAN P．Modeling Vehicle Routing in GIS[J]．Operational Research,2008,8(3):201-218．

[15] BOYER V,ELKIHEL M,BAZ D E．Heuristics for the 0-1 Multidimensional Knapsack Problem[J]．European Journal of Operational Research,2009,199(3):658-664．

[16] GENDREAU M,POTVIN J Y．Handbook of Metaheuristics [M]．Norwell:Kluwer Academic Publishers,2010:41-60．[17] ZACHARIADIS E E,TARANTILIS C D,KIRANOUDIS C T．A Guided Tabu Search for the Vehicle Routing Problem with Two-dimensional Loading Constraints[J]．European Journal of Operational Research,2009,195(3): 729-743．

[18] LI Zhiping,GAO Xingguo．Comparison Analysis of Simulated Annealing and Tabu Search for VRP[J]．Science Information,2010,22:79-80．(李志萍,高興國(guó)．模擬退火法與禁忌搜索法求解VRP的對(duì)比分析[J]．科技信息,2010,22: 79-80．)

[19] BOLDUC M C,LAPORTE G,RENAUD J,et al．A Tabu Search Heuristic for the Split Delivery Vehicle Routing Problem with Production and Demand Calendars[J]．European Journal of Operational Research,2010,202(1): 122-130．

[20] NGUEVEU S U,PRINS C,CALVO R W．A Hybrid Tabu Search for the m-peripatetic Vehicle Routing Problem,in Matheuristics[M]．New York:Springer,2010:253-266．

[21] BRAND?O J．A Tabu Search Algorithm for the Heterogeneous Fixed Fleet Vehicle Routing Problem[J]．Computers and Operations Research,2011,38(1):140-151．

[22] CESCHIA S,GASPERO L D,SCHAERF A．Tabu Search Techniques for the Heterogeneous Vehicle Routing Problem with Time Windows and Carrier-dependent Costs[J]．Journal of Scheduling,2011,14(6):601-615．

[23] MOCCIA L,CORDEAU J F,LAPORTE G．An Incremental Tabu Search Heuristic for the Generalized Vehicle Routing Problem with Time Windows[J]．Journal of the Operational Research Society,2011,63(2):232-244．

(責(zé)任編輯:陳品馨)

A Parallel Geographical Network Vehicle Routing Algorithm on PC Clusters

YAN Zhiyuan,SUN Wenbin,CHEN Zongjuan,ZHAO Shuaiyang
College of Geosciences and Surveying Engineering,China University of Mining and Technology,Beijing 100083,China

In PC clusters,the memory in each compute node is limited and the communication is inefficient．To solve these problems,a novel parallel algorithm for geographical network vehicle routing is proposed．The main contents are as follows．Firstly,a distributed storage mechanism is designed to avoid the low memory problem．Then,instead of sending the complete solution,synchronizing the transformation of the solution is used to reduce the quantity of communication and improve the efficiency．Finally,a parallel geographical network vehicle routing algorithm is implemented by parallelizing the OD matrix computing and the tabu search procedure．Several experiments are conducted on a PC cluster using simulated traffic networks．The results show that:the computational results of the proposed algorithm are consistent with ArcGIS,and the average deviation is between 2．11%－2．87%;the distributed storage mechanism reduces the memory usage in each process and enhances the robustness and scalability of the algorithm;the parallelizing of the algorithm improves the efficiency of solving vehicle routing problem;the proposed algorithm has good parallel performance,and the speedup is between 4．46～6．32 in all test datasets using 8 processe．

geographical network analysis;vehicle routing problem;tabu search;parallel algorithm

YAN Zhiyuan(1983—),male,PhD candidate,majors in GIS network analysis and parallel computing．

P208

A

1001-1595(2014)07-0753-08

2013-12-18

閆志遠(yuǎn)(1983—),男,博士生,研究方向?yàn)镚IS網(wǎng)絡(luò)分析算法與并行計(jì)算。

E-mail:yan_zhi_yuan＠163．com

YAN Zhiyuan,SUN Wenbin,CHEN Zongjuan,et al．A Parallel Geographical Network Vehicle Routing Algorithm on PC Clusters[J]．Acta Geodaetica et Cartographica Sinica,2014,43(7):753-760．(閆志遠(yuǎn),孫文彬,陳宗娟,等．PC集群環(huán)境下的并行地理網(wǎng)絡(luò)車(chē)輛路徑算法[J]．測(cè)繪學(xué)報(bào),2014,43(7):753-760．)

10．13485/j．cnki．11-2089．2014．0116

國(guó)家863計(jì)劃(2011AA120302);國(guó)家自然科學(xué)基金(41201416);中國(guó)礦業(yè)大學(xué)(北京)大學(xué)生創(chuàng)新計(jì)劃(Y20131213)

修回日期:2014-03-20