求解V RP的一種改進(jìn)模擬退火算法

李珊珊

（山東科技大學(xué)，山東青島266000）

1 引言

車輛路徑問題（Vehicle Routing Problem,VRP）由Dantzig等[1]提出后，便使運(yùn)籌學(xué)理論和生產(chǎn)生活實(shí)際聯(lián)系在一起，因此很快便引起運(yùn)籌學(xué)、數(shù)學(xué)、物流學(xué)、計(jì)算機(jī)應(yīng)用等學(xué)科專家的廣泛關(guān)注。VRP問題的求解算法一直是國(guó)內(nèi)外專家研究的重點(diǎn)問題，目前最主要的求解算法是啟發(fā)式算法[1]，包括：模擬退火算法、禁忌搜索算法、粒子群算法、蟻群算法和伊藤算法等。

Kirkpatrick等人發(fā)現(xiàn)數(shù)學(xué)中的組合優(yōu)化問題和物理上固體退火過程之間所存在的相似性，于是他們把固體物理退火的思想引入組|合優(yōu)化問題中，再基于Monte-Carlo迭代策略提出了模擬退火算法（Simulated Annealing,SA）。在計(jì)算過程中，SA能夠以一定的概率收斂至全局最優(yōu)解，因此，SA在這種意義上說是一種全局優(yōu)化算法，并善于求解高復(fù)雜度的問題，以上觀點(diǎn)已經(jīng)在理論上被證明。SA求解效率快而且求解質(zhì)量很高[2]，所以本文采用對(duì)傳統(tǒng)SA進(jìn)行改進(jìn)，并求解VRP問題。

2 VRP問題模型

VRP問題可描述為：一個(gè)配送中心，多位顧客，并且已知每位顧客的位置和需求量，用一定數(shù)量的車輛從配送中心出發(fā)，規(guī)劃車輛行駛路徑，滿足每位顧客的需求且每位顧客僅能由1輛車服務(wù)，不能超過車輛相關(guān)的約束，目標(biāo)是使距離最短或者運(yùn)輸費(fèi)用最少[3]。

本文相關(guān)符號(hào)說明：

C：表示每輛車的最大裝載能力；

ci：表示顧客i的需求量，且max（ci）≤C（1≤i≤n）；

D：表示每輛車的最大行駛距離；

dij：表示顧客與顧客或者顧客與配送中心之間的距離；

n：表示配送過程中出現(xiàn)的顧客總數(shù)；

r：表示配送中心具有的車輛數(shù)；

hijk：表示車輛k從顧客i到j(luò)，經(jīng)過為1，不經(jīng)過為0；

gik：表示顧客i由車輛k服務(wù)，經(jīng)過為1，不經(jīng)過為0。此問題數(shù)學(xué)規(guī)劃模型為：

約束條件：

其中Ak表示第k輛車服務(wù)的顧客集合（1≤k≤r）

式（1）為目標(biāo)函數(shù)，表示所有配送車輛的總行駛路徑長(zhǎng)度最短；式（2）表示每輛車的裝載能力約束；（3）表示每輛車的行駛距離約束；式（4）、（5）、（6）表示每個(gè)客戶僅能被 1 輛車服務(wù)1次；式（7）約束了所有車輛的起始點(diǎn)和終點(diǎn)都在配送中心；式（8）表示每輛車行駛的路徑軌跡恰好為一個(gè)簡(jiǎn)單圈，式（9）、（10）分別為決策變量。

3 改進(jìn)模擬退火算法

SA是一種隨機(jī)尋優(yōu)算法，從某一較高初始溫度開始，隨著溫度參數(shù)的逐漸下降，結(jié)合概率突跳特性在解空間里隨機(jī)找尋目標(biāo)函數(shù)的全局最優(yōu)解[3]。

本文對(duì)傳統(tǒng)SA的改進(jìn)包括以下三個(gè)方面：

①鄰域操作方法。傳統(tǒng)SA采取的鄰域操作是兩點(diǎn)置換法（也稱為2-swap交換法）。該方法的思想是：在每一次迭代中只交換兩個(gè)節(jié)點(diǎn)，這種鄰域操作方法簡(jiǎn)單易行，但其對(duì)解空間的搜索能力不強(qiáng)[4]。因此在每一個(gè)溫度參數(shù)下，若要保證得到當(dāng)前溫度參數(shù)下的一個(gè)優(yōu)解，就需要比較長(zhǎng)的時(shí)間對(duì)解空間進(jìn)行搜索。隨著溫度參數(shù)的逐漸降低，外循環(huán)的次數(shù)增多，執(zhí)行算法的時(shí)間便成倍增加，進(jìn)而使得算法整體的搜索時(shí)間過長(zhǎng)。本文將鄰域操作分為兩步：第一步先進(jìn)行線路內(nèi)交換，對(duì)線路內(nèi)交換采用2-swap、2-opt及2-insert三種交換方法隨機(jī)協(xié)作的方式實(shí)施鄰域操作，產(chǎn)生一新的可行解。即基于概率論的方法來決定使用某一種具體的交換法來實(shí)施鄰域操作，這樣一來便大大增加了產(chǎn)生新解空間的隨機(jī)性，為算法跳出局部最優(yōu)提高了可能性。第二步是在第一步線路內(nèi)的節(jié)點(diǎn)交換產(chǎn)生可行解后，對(duì)產(chǎn)生的可行解進(jìn)行線路間節(jié)點(diǎn)的交換，線路間節(jié)點(diǎn)的交換是引入Osman的λ-interchange交換思想，并規(guī)定每一溫度下鄰域操作的次數(shù)=λ，從而保證在一定的時(shí)間內(nèi)，能夠獲得相對(duì)較高質(zhì)量的優(yōu)解。

②記憶裝置的設(shè)計(jì)。在改進(jìn)SA中內(nèi)嵌一個(gè)記憶數(shù)組，用來存儲(chǔ)各優(yōu)解的值，從而構(gòu)成一種具有記憶功能的SA，進(jìn)而使得算法的輸出為本次搜索的最優(yōu)解。

③終止準(zhǔn)則的確定。采用混合停止準(zhǔn)則，即當(dāng)溫度低于某值時(shí)或者記憶數(shù)組連續(xù)γ次無變化時(shí)，算法終止。本文取γ=20，就能保證所獲得的值為本次計(jì)算的最優(yōu)解。

4 結(jié)語

本文隨機(jī)選擇Solomon標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)[5]中的R101中的50個(gè)顧客點(diǎn)進(jìn)行了測(cè)試（如圖）。

圖1

圖2

如圖1所示，節(jié)點(diǎn)代表顧客的位置，線代表車輛路線，箭頭代表車輛行駛方向。圖2是增加了記憶數(shù)組存儲(chǔ)的每次迭代的各個(gè)解的值，記錄每次的數(shù)值，從而能夠保證最終輸出值為搜索解空間后本次計(jì)算的最優(yōu)解。通過對(duì)算例進(jìn)行求解，證明改進(jìn)后的SA能較好的解決VRP問題，且求解質(zhì)量較高，求解速度很快。