杜玲玲

（華東交通大學(xué)信息工程學(xué)院，江西南昌 330013）

車輛路徑問(wèn)題（vehicle routing problem，VRP）是一個(gè)涉及運(yùn)籌學(xué)、管理學(xué)、交通運(yùn)輸、計(jì)算機(jī)科學(xué)等領(lǐng)域的著名NP難題。由于它在許多行業(yè)（如公共汽車線路制定、垃圾回收、郵件傳遞、銀行系統(tǒng)貨幣收集、航空鐵路時(shí)間安排表等）的物流分配系統(tǒng)規(guī)劃中起著至關(guān)重要的作用，因而是一個(gè)具有重要理論意義和實(shí)際應(yīng)用價(jià)值的研究課題。

車輛路徑問(wèn)題可簡(jiǎn)單描述為對(duì)一系列客戶組織適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過(guò)，在滿足一定的約束條件下（如貨物的需求量、發(fā)貨量、交貨時(shí)間、車輛的容量限制、行駛里程限制、時(shí)間限制等），且在客戶可以接受的演算時(shí)間內(nèi)，給出盡可能優(yōu)化的路線規(guī)劃方案，最大限度地降低客戶的運(yùn)營(yíng)成本。

對(duì)VRP的求解，傳統(tǒng)的精確算法只適合求解小規(guī)模問(wèn)題，隨著實(shí)際問(wèn)題規(guī)模的擴(kuò)大，求解時(shí)間呈幾何級(jí)數(shù)上升，人們逐漸傾向于采用元啟發(fā)式算法。目前，國(guó)內(nèi)外研究VRP的文獻(xiàn)也主要把精力放在構(gòu)造高質(zhì)量的啟發(fā)式算法上。目前已成功用于求解VRP的啟發(fā)式算法有模擬退火算法、遺傳算法、禁忌搜索算法和蟻群優(yōu)化等。關(guān)于這些算法的描述，可以查閱以下研究論文：Brandao等[1]的文獻(xiàn)，劉志碩等[2-3]的文獻(xiàn)，Tar?antilis[4]的文獻(xiàn)，Baldacci等[5]的文獻(xiàn)，Laporte[6]的文獻(xiàn)。近年來(lái)，混合不同元啟發(fā)式算法的搜索策略和優(yōu)化技術(shù)的混合啟發(fā)式算法成為了一個(gè)新研究熱點(diǎn)，并取得了一定的研究成果。如在求解大規(guī)模的帶時(shí)間窗的車輛路徑問(wèn)題上，Battarra[7]等結(jié)合導(dǎo)向性局部搜索和演化策略的優(yōu)點(diǎn)，設(shè)計(jì)了一種主動(dòng)引導(dǎo)演化策略。Homberger和Gehring[8]提出了一種兩階段（即初始階段和優(yōu)化階段）混合元啟發(fā)式算法，分別使用演化策略和禁忌搜索來(lái)優(yōu)化使用車輛數(shù)最少和旅行時(shí)間最短兩個(gè)目標(biāo)，已被證明能成功地解決超過(guò)1 000個(gè)客戶的大規(guī)模問(wèn)題。

1 問(wèn)題描述

帶容量約束的車輛路徑問(wèn)題（capacitated vehicle routing problem，CVRP）是VRP的基本類型。在CVRP中，客戶的需求是事先已知的，并且不可分裂。給定的K輛車輛具有相同車型，開(kāi)始時(shí)都位于配送中心，受車輛容量約束（有時(shí)還有車輛最大旅行時(shí)間限制），其目標(biāo)是如何安排這K輛車的服務(wù)對(duì)象和路線，使得車輛總的運(yùn)輸成本最小。

近年來(lái)，研究者采用結(jié)合局部最近鄰搜索法（nearest neighbor search，NNS）的混合啟發(fā)式算法設(shè)計(jì)了一些求解CVRP的方法。如Crispim等[9]提出了一種混合遺傳算法；Tang Montane等[10]提出一種兩個(gè)種群的混合遺傳算法；Chen和Wu[11]提出了一種基于“記錄”和“禁忌表”的混合啟發(fā)式算法，Bianchessi和Righini[12]提出了構(gòu)造性混合算法，Zachariadis等[13]提出了基于模擬退火和禁忌搜索（tabu search，TS）[14]的混合啟發(fā)式算法。

上述算法對(duì)初始解和鄰域的依賴較大，求解后容易陷入局部最優(yōu)，且一旦陷入幾乎沒(méi)有機(jī)會(huì)跳出。為進(jìn)一步擴(kuò)大對(duì)解空間的搜索，以取得更好質(zhì)量的解。本文提出一種將NNS和TS結(jié)合的混合超啟發(fā)式算法。

2 數(shù)學(xué)模型

在CVRP中，其總體目標(biāo)是在滿足容量約束條件下盡量減少總運(yùn)輸成本。一般情況下，運(yùn)輸成本與車輛行駛路徑成正比，行駛路徑越短，車輛的耗油量越少，司機(jī)的工作時(shí)間越少，總的運(yùn)輸費(fèi)用也就越少。

這里，我們定義以下符號(hào)來(lái)進(jìn)行描述：

A為弧線集；

n為節(jié)點(diǎn)總數(shù)；

N為節(jié)點(diǎn)-弧線關(guān)聯(lián)矩陣；

V為節(jié)點(diǎn)集；

T為路線；

3 求解大規(guī)模VRP的混合超啟發(fā)算法

在實(shí)際物流配送中，類似于煙草公司這樣需要為城市某個(gè)范圍內(nèi)的上百個(gè)甚至幾百個(gè)零售商送貨，單個(gè)零售商送貨量又不大的CVRP大量存在，因此，求解這類規(guī)模的CVRP需要解決的是如何安排最優(yōu)線路，使整個(gè)網(wǎng)絡(luò)的總運(yùn)輸費(fèi)用最小。

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

由于NNS算法操作簡(jiǎn)單，容易較快得到初始解。所以，首先利用該算法構(gòu)建初步路線。其算法思想是以配送中心為起始點(diǎn)，搜索距中心最近的、未訪問(wèn)的節(jié)點(diǎn)作為下一個(gè)節(jié)點(diǎn)，在不超出容量限制的情況下重復(fù)步驟，達(dá)到容量限制后結(jié)束該條線路，繼續(xù)尋找其他新的線路，直到將所有的節(jié)點(diǎn)都訪問(wèn)過(guò)。

令V*表示車輛尚沒(méi)有訪問(wèn)過(guò)的客戶點(diǎn)的集合。從倉(cāng)庫(kù)（即調(diào)度中心，用節(jié)點(diǎn)0表示）開(kāi)始，構(gòu)造一條由節(jié)點(diǎn)0，i1，…，ij組成的線路，其中

當(dāng)u≥di1+di2+...+dij，對(duì)于任何其它節(jié)點(diǎn)s∈V*都有u＜di1+di2+...+dij+ds。重復(fù)這個(gè)過(guò)程直到所有客戶點(diǎn)都被訪問(wèn)到。

由于每個(gè)客戶都可作為車輛路線的第一個(gè)客戶，這樣有n個(gè)客戶就可形成n種路線安排，選擇其中最好的路線安排（即目標(biāo)值最?。┳鳛樗惴ǖ某跏冀?。

3.2 禁忌搜索算法的優(yōu)化設(shè)計(jì)

由于采用NNS求解后容易陷入局部最優(yōu)，且一旦陷入幾乎沒(méi)有機(jī)會(huì)跳出。而TS算法具有收斂速度快，能在第30代左右就能跳出局部最優(yōu)并達(dá)到全局最優(yōu)點(diǎn)。因此，再利用它來(lái)對(duì)線路進(jìn)行優(yōu)化。

在TS中有多種鄰域操作方法，這里，我們采用內(nèi)部交換和交叉交換法相混合來(lái)構(gòu)造一個(gè)求解CVRP的新禁忌搜索算法。

在兩條路線之間交換客戶，給定由線路集所表示的問(wèn)題的一個(gè)解，其中ri是對(duì)應(yīng)的1條車輛路徑：

在交叉交換過(guò)程中，首先從第1條線路中刪除兩條邊（i-1，i）和（k，k+1），同時(shí)從第2條線路中刪除兩條邊（j-1，j）和（l，l+1）；然后通過(guò)引入新的四條邊（i-1，j），（l，k+1），（j-1，i）和（k，l+1）實(shí)現(xiàn)線段i-1和j-1的互換，其中，線段i-k和j-1中可能包含任意數(shù)量的客戶。

結(jié)點(diǎn)交換后，為優(yōu)化一些單獨(dú)的線路，可將交叉鄰域法的范疇進(jìn)行擴(kuò)大，包含僅用于單一線路的線內(nèi)交換。從一條給定的線路中刪除兩條邊，且將這兩條邊之間的線段移動(dòng)到同一條線路內(nèi)的另一位置。

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

我們采用基于標(biāo)準(zhǔn)的基準(zhǔn)數(shù)據(jù)集，即Homberger 400 customer Rc2-410和湖北隨州市6 772名真實(shí)煙草商數(shù)據(jù)集為實(shí)驗(yàn)數(shù)據(jù)。

4.1 基于標(biāo)準(zhǔn)的基準(zhǔn)數(shù)據(jù)集

標(biāo)準(zhǔn)基準(zhǔn)數(shù)據(jù)集Rc2-410是一個(gè)隨機(jī)集群客戶的組合，包含了400個(gè)客戶。分別利用最近鄰搜索（NNS）、內(nèi)部交換（NNS+intra-exchange）、交叉交換（NNS+cross-exchange）和混合交換法（NNS+intra-&cross-exchange）四種方法在matlab上仿真其路線結(jié)構(gòu)。

實(shí)驗(yàn)結(jié)果表明，采用混合交換法后，線路密度降低了，這就意味著所構(gòu)建線路的總路程減少了。因此，該算法能夠比其它算法構(gòu)建出更好的路線。

在表1中列出了這四種算法的詳細(xì)比較。它們具有相同的路徑數(shù)，但其消耗的總路程明顯不同?？梢钥闯?，NNS+intra-&cross-exchange法與NNS法相比，極大地減少了總路程。

表1 算法比較Tab.1 Algorithm comparasion

4.2 基于真實(shí)數(shù)據(jù)集

我們以湖北隨州市中心和郊區(qū)的6 772位煙草客戶為應(yīng)用數(shù)據(jù)，根據(jù)實(shí)際需要，將這些客戶劃分為5個(gè)區(qū)域，如圖1所示。圖中每個(gè)點(diǎn)代表了一個(gè)客戶的位置，如：點(diǎn)（37.1232，113.3423）代表緯度37.1232，經(jīng)度113.3423。

圖2-6分別是采用混合交叉法NNS+intra-&cross-exchange法為這5個(gè)區(qū)域所構(gòu)建的路線圖，每個(gè)區(qū)域都使用了多條線路來(lái)進(jìn)行應(yīng)用驗(yàn)證。圖中，直線表示的是某條線路上第1個(gè)客戶點(diǎn)和最后1個(gè)客戶點(diǎn)，和車場(chǎng)之間的連接；曲線則表示這條線路上的其他點(diǎn)，按照其實(shí)際行走的線路連接起來(lái)（實(shí)際也是用直線連的，只是點(diǎn)多，形成了多段折線）。這里的x和y也是表示客戶點(diǎn)的經(jīng)緯度。

從這些區(qū)域線路圖可以看出，新方法在實(shí)際應(yīng)用中可以取得良好的效果，大大減少了線路的總路程，因而能降低運(yùn)輸成本，提高煙草運(yùn)輸?shù)男省?/p>

5 結(jié)束語(yǔ)

本文研究了啟發(fā)式算法及其在車輛路徑問(wèn)題中的應(yīng)用，重點(diǎn)解決帶容量約束的大規(guī)模車輛路徑問(wèn)題，將最近鄰搜索法和禁忌搜索法的優(yōu)勢(shì)相結(jié)合，提出結(jié)構(gòu)簡(jiǎn)單、求解精度高、時(shí)間代價(jià)小、擴(kuò)展性好的混合超啟發(fā)式算法，形成兩階段求解法。第1階段利用最近鄰搜索法構(gòu)建初步路線，第2階段再利用禁忌搜索法對(duì)內(nèi)部線路和互跨線路進(jìn)行優(yōu)化。

實(shí)驗(yàn)結(jié)果表明：采用新算法在線路優(yōu)化上具有顯著地改善效果，為大規(guī)模CVRP的求解提供了新的求解思路。

[1]BRANDAO J.A deterministic tabo search algorithm for the fleet siza and mix vehicle routing problem[J].European Journal of Operational Resrach，2009，195（3）：716-728.

[2]劉志碩，申金升.蟻群算法及其在有硬時(shí)間窗的車輛路徑問(wèn)題中的應(yīng)用[J].計(jì)算機(jī)繼承制造系統(tǒng)，2006，12（4）：596-602.

[3]劉志碩，申金升.一種求解車輛路徑問(wèn)題的混合多蟻算法[J].系統(tǒng)仿真學(xué)報(bào)，2007，19（15）：3513-3520.

[4]TARANTILIS C D，IOANNOU G，KIRANOUDIS C T，et al.Solving the open vehicle routing problem via a single parameter metaheuristic algorithm[J].Journal of the Operational Research Society，2005，56（5）：588-596.

[5]BALDACCI R，CHRISTOFIDES N，MINGOZZI A.An exact al-gorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts[J].Mathematical Programming，2008，115（2）：351-385.

[6]LAPORTE G.Fifty years of vehicle routing[J].Transportation Science，2009，43（4）：408-416.

[7]BATTARRA M，GOLDEN B，VIGO D.Tuning a parametric Clarke-Wright heuristic via a genetic algorithm[J].Journal of the Operational Research Society，2008，59（11）：1568-1572.

[8]HOMBERGER JORG，HERMANN GEHRING.A two-phase hybrid metaheuristic for the vehicle routing problem with time windows[J].European Journal of Operational Research，2005，162（1）：220-238.

[9]CRISPIM J，BRANDAO J.Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls[J].Journal of the Operational Reseach Socitey，2005，56（11）：1296-1302.

[10]TANG MONTANC F，GALVAO R.A tabu search algorithm for the vechicle routing problem with simultancous pick-up and delivery service[J].Comuputers and Operations Research，2006，33（3）：595-619.

[11]CHEN J，WU T.Vechicle routing problem with simultancous deliverics and pick-ups[J].Journal of the Operations Research Socitey，2006，57（5）：579-587.

[12]BIANCHESSI N，RIGHINI G.Heuristic algorithm for the cechicle routing problem with simultaneous pick-up and delivery[J].Comuputers and Operations Research，2007，34（2）：578-594.

[13]ZACHARIADIS E E，TARANTILIS C D，KIRANOUDIS C T.Ahybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service[J].Expert Systems with Applications，2009，36（2）：1070-1081.

[14]LAI MINGYONG，CAO ERBAO.An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows[J].EngineeringApplications ofArtificial Intelligence，2010，23（2）：188-195.