李珊珊

【摘 要】建立車輛路徑問題（Vehicle Routing Problem， VRP）的數(shù)學(xué)模型，在傳統(tǒng)模擬退火算法的基礎(chǔ)上提出三方面的改進(jìn)，通過算例驗(yàn)證模型和改進(jìn)算法的有效性。

【Abstract】The mathematical model of VRP is established， and 3 improvements are put forward on the basis of traditional simulated algorithm. The validity of the model and the improved algorithm are proved by an example.

【關(guān)鍵詞】VRP；數(shù)學(xué)模型；改進(jìn)模擬退火算法

【Keywords】VRP； mathematical model； improved simulated annealing algorithm

【中圖分類號(hào)】F503 【文獻(xiàn)標(biāo)志碼】A 【文章編號(hào)】1673-1069（2018）02-0147-02

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問題的求解算法一直是國內(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ī)劃模型為：

式（1）為目標(biāo)函數(shù)，表示所有配送車輛的總行駛路徑長度最短；式（2）表示每輛車的裝載能力約束；（3）表示每輛車的行駛距離約束；式（4）、（5）、（6）表示每個(gè)客戶僅能被1輛車服務(wù)1次；式（7）約束了所有車輛的起始點(diǎn)和終點(diǎn)都在配送中心；式（8）表示每輛車行駛的路徑軌跡恰好為一個(gè)簡單圈，式（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)，這種鄰域操作方法簡單易行，但其對(duì)解空間的搜索能力不強(qiáng)[4]。因此在每一個(gè)溫度參數(shù)下，若要保證得到當(dāng)前溫度參數(shù)下的一個(gè)優(yōu)解，就需要比較長的時(shí)間對(duì)解空間進(jìn)行搜索。隨著溫度參數(shù)的逐漸降低，外循環(huán)的次數(shù)增多，執(zhí)行算法的時(shí)間便成倍增加，進(jìn)而使得算法整體的搜索時(shí)間過長。本文將鄰域操作分為兩步：第一步先進(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所示，節(jié)點(diǎn)代表顧客的位置，線代表車輛路線，箭頭代表車輛行駛方向。圖2是增加了記憶數(shù)組存儲(chǔ)的每次迭代的各個(gè)解的值，記錄每次的數(shù)值，從而能夠保證最終輸出值為搜索解空間后本次計(jì)算的最優(yōu)解。通過對(duì)算例進(jìn)行求解，證明改進(jìn)后的SA能較好的解決VRP問題，且求解質(zhì)量較高，求解速度很快。

【參考文獻(xiàn)】

【1】Dantzig GB， Ramser JH. The truck dispatching problem[J]. Management Science， 1959， 6（1）： 80-91.

【2】辛振銘. 一種改進(jìn)的模擬退火算法在TSP問題中的研究與應(yīng)用[D].長春：東北師范大學(xué)，2010.

【3】K. Lund， O. B. C. Madsen， and J.M. Rygaard， Vehicle routing problems with varying degrees of dynamism. Technical report， Institute of Mathematical Modelling， Technical University of Denmark，1996.

【4】Chen， H.K.， Hsueh， C.F.， Chang， M.S. The real-time time-dependent vehicle routing problem[J]. Transportation Research Part E ，2006.42（5）：383-408.

【5】Solomon，M.M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J].Operations Research ，1987.35（2）：254-265.endprint