摘 要：設(shè)計(jì)了一種新的能量獎(jiǎng)勵(lì)機(jī)制，以提高微正則退火算法擺脫局部極值點(diǎn)的能力。在狀態(tài)轉(zhuǎn)移被拒絕后，通過比較兩個(gè)能量參數(shù)的大小來啟動(dòng)獎(jiǎng)勵(lì)操作。獎(jiǎng)勵(lì)方式依舊為幾何增長方式，但增長幅度改為一定區(qū)間內(nèi)的線性調(diào)節(jié)。給出了一個(gè)采用改進(jìn)算法的經(jīng)典的單配送中心實(shí)例，它提高了微正則退火基本算法的優(yōu)化效果，降低了搜索過程停滯在局部極值的概率，它搜索到的運(yùn)輸費(fèi)用更貼近最佳解。
關(guān)鍵詞：車輛路徑問題；微正則退火算法；組合優(yōu)化
?
配送車輛路徑問題VRP（Vehicle Routing Problem）是指向一批客戶配送物資，客戶的位置和貨物需求量已知，現(xiàn)有若干可供派送的車輛，車輛的運(yùn)載能力給定，每輛車都從起點(diǎn)出發(fā)，完成若干客戶點(diǎn)的運(yùn)送任務(wù)后再回到起點(diǎn)，現(xiàn)尋求以最少的車輛數(shù)、最小的車輛總行程來完成貨物配送任務(wù)。
車輛路徑問題是物流配送中的關(guān)鍵決策問題，已有研究表明該問題屬于NP難題[1-2]。求解該問題有兩類方法，一類是精確算法，另一類是啟發(fā)式算法[3-5]，后者力圖在有限的時(shí)間內(nèi)找到大規(guī)模問題的滿意解，得到不少工程人員的關(guān)注。本文研究的微正則退火算法MA（Micro-canonical Annealing）也屬于啟發(fā)式算法的范疇，有關(guān)研究表明，該算法具有實(shí)施簡單、運(yùn)行速度快、優(yōu)化效果出色等優(yōu)點(diǎn)[6]。筆者曾提出一種對(duì)該算法的改進(jìn)思路，針對(duì)算法迭代后期的優(yōu)化進(jìn)程放緩問題，適時(shí)給予能量獎(jiǎng)勵(lì)策略，提高了在旅行推銷員問題上的搜索性能。本文改進(jìn)了這種能量獎(jiǎng)勵(lì)思想，將其用于配送路徑的優(yōu)化問題。實(shí)驗(yàn)研究發(fā)現(xiàn)，改進(jìn)算法提高了最終解的質(zhì)量，能夠得到更低的運(yùn)輸費(fèi)用。
1 配送車輛路徑問題的數(shù)學(xué)模型
根據(jù)約束條件和目標(biāo)函數(shù)的差異，車輛路徑問題的數(shù)學(xué)模型可寫成多種形式。最簡單的情形是設(shè)計(jì)從一個(gè)位置出發(fā)，到多個(gè)不同位置的客戶點(diǎn)的最優(yōu)配送路徑，即尋找一個(gè)運(yùn)費(fèi)最小的路徑集合，并滿足如下條件：
首先，每條配送路徑上各個(gè)客戶的需求量之和不超過汽車載貨量。
其次，每個(gè)客戶的需求必須滿足，且只能由一輛汽車送貨。
先作如下定義：i、j 為任意兩個(gè)客戶的標(biāo)號(hào)，i、j∈N；N = { 1, 2,…, n}，n為客戶的數(shù)目，標(biāo)號(hào)0表示配送中心（即假定只有一個(gè)配送中心的情形）；k為配送車輛的標(biāo)號(hào)；k∈k，k = {1, 2 , …, m}，m為車輛的數(shù)目；Ci,j為客戶i、j 之間的距離；Xijk為路徑?jīng)Q策變量，當(dāng)?shù)趉輛車從客戶i駛向客戶j時(shí)Xijk為1，否則Xijk為0；Yik為車輛與客戶的配對(duì)參數(shù)，當(dāng)車輛k服務(wù)客戶i時(shí)取值為1，否則取0；wj為客戶j的貨物需求量；D為車輛的最大載貨量，Cmin為最少總費(fèi)用。可建立如下模型：
式（1）為目標(biāo)函數(shù)，使得總費(fèi)用最小；式（2）表示每個(gè)客戶都被訪問且僅被訪問一次；式（3）、（4）為每條巡回路徑上的配送限制；式（5）為車輛的載貨量限制。
2? 微正則退火算法及改進(jìn)策略
2.1 算法的基本原理
微正則退火與傳統(tǒng)模擬退火的差異在于，它不再直接依賴系統(tǒng)溫度，配分函數(shù)Z的形式為：
式（6）中，E0是初始能量值，K(P)是動(dòng)量P在狀態(tài)C下的能量，上式中沒有出現(xiàn)溫度參數(shù)。
在這一仿真方法中，假設(shè)熱系統(tǒng)中存在一個(gè)具有能量交換能力的妖，它的作用類似式（6）中的動(dòng)量P。這只妖可以在狀態(tài)空間中隨機(jī)行走，并通過改變熱系統(tǒng)的狀態(tài)變量達(dá)到調(diào)節(jié)系統(tǒng)能量的目的。仿真過程中，系統(tǒng)與妖的能量之和保持定值并且逐步降低，促使系統(tǒng)積累足夠的能量以脫離亞穩(wěn)態(tài)。令妖的能量為ED，ED為正數(shù)且初始值一般等于0。此時(shí)Z的形式為：
系統(tǒng)初始狀態(tài)可以隨機(jī)配置，妖在狀態(tài)空間中每隨機(jī)行走一步，就會(huì)嘗試改變當(dāng)前的系統(tǒng)狀態(tài)，若此舉能降低系統(tǒng)能量，則系統(tǒng)接收狀態(tài)變遷。與此同時(shí)，系統(tǒng)釋放的能量將會(huì)被妖吸收。當(dāng)這種退火機(jī)制用于尋求目標(biāo)函數(shù)最小值時(shí)，狀態(tài)空間對(duì)應(yīng)于自變量空間，系統(tǒng)能量對(duì)應(yīng)于目標(biāo)函數(shù)值。妖的能量變更可用如下公式表達(dá)：
式中Enew、Eold分別表示新舊狀態(tài)所對(duì)應(yīng)的系統(tǒng)能量。為保證妖的能量總是正值，若妖的隨機(jī)行走導(dǎo)致系統(tǒng)能量升高且升高幅度超過ED，該狀態(tài)轉(zhuǎn)移將被拒絕。另一方面，妖的能量ED也有上界約束M，該值隨著迭代過程逐步減小。
2.2 能量獎(jiǎng)勵(lì)策略
妖的當(dāng)前能量ED直接限制了系統(tǒng)能量回升的最大幅度，這一數(shù)值刻畫出系統(tǒng)脫離亞穩(wěn)態(tài)的能力大小。在算法后期，由于Emax的作用，ED總體處于下降趨勢(shì)，劣狀態(tài)被接受的概率非常低，若系統(tǒng)陷入一個(gè)比較深的能量局部極小狀態(tài)，確定性的狀態(tài)接受規(guī)則將使得系統(tǒng)幾乎不能脫離該狀態(tài)。
筆者曾考慮對(duì)妖的能量ED施加一種幾何方式的能量獎(jiǎng)勵(lì)策略，在拒絕新狀態(tài)后，適當(dāng)增大ED的數(shù)值，以期逐步提高妖脫離局部極值的能力。具體操作方法是：對(duì)ED實(shí)施比例為q的增幅，即ED←ED×(1＋q)，其中q值一般很小。在先前所做的實(shí)例仿真中發(fā)現(xiàn)，一種被稱為無上界約束的能量獎(jiǎng)勵(lì)策略效果很小，這種方式在實(shí)施能量獎(jiǎng)勵(lì)后不檢查ED是否超過Emax（當(dāng)妖主動(dòng)吸收能量后仍然要對(duì)ED做越界約束）。
3?改進(jìn)微正則退火算法的實(shí)施
微正則退火算法用于組合優(yōu)化時(shí)，算法的實(shí)施流程與傳統(tǒng)模擬退火算法類似，具體體現(xiàn)在：第一，算法需要一個(gè)初始解，算法的主過程將在該初始解上執(zhí)行領(lǐng)域變換；第二，算法的主流程也是雙層循環(huán)結(jié)構(gòu)，內(nèi)循環(huán)按照退火策略更新狀態(tài)。外循環(huán)是縮減妖的能量上界約束M（模擬退火中是降低溫度）。
3.1 鄰域變換
領(lǐng)域解的產(chǎn)生有兩類常用方法，第一類是路徑間優(yōu)化，如路徑插入法和路徑交換法。第二類是路徑內(nèi)優(yōu)化，如常用的二交換法，假設(shè)( i，i + 1) 和( j，j + 1) 是當(dāng)前路徑的兩條邊, 二交換后得到兩條新邊( i，j) 和(i+1，j +1)，且原路徑中j和i+1節(jié)點(diǎn)之間的整段路徑需要翻轉(zhuǎn)，后續(xù)實(shí)驗(yàn)中使用了二交換方法。
3.2 退火策略
妖的能量上界約束M值在內(nèi)循環(huán)中保持不變，內(nèi)循環(huán)結(jié)束后該值將按比例縮減，即有M(i+1) =αM(i)，M(i)表示內(nèi)循環(huán)執(zhí)行了i次后的M值，α為縮減系數(shù)。
??? 內(nèi)循環(huán)的停止標(biāo)準(zhǔn)包括兩種情形，一是在當(dāng)前M下，已經(jīng)嘗試了U次循環(huán)；二是在當(dāng)前M下，最好解成功已改進(jìn)了L次，其中U與L是預(yù)定義的常數(shù)。
外循環(huán)在M低于預(yù)設(shè)值e，或找到指定解時(shí)即被終止，最后輸出最終搜索結(jié)果。
3.3 改進(jìn)的能量獎(jiǎng)勵(lì)策略
實(shí)施能量獎(jiǎng)勵(lì)策略時(shí)，需要做好兩項(xiàng)決策，首先是獎(jiǎng)勵(lì)時(shí)機(jī)的選擇，之前筆者曾設(shè)計(jì)過一種容忍機(jī)制，只在當(dāng)前狀態(tài)沒改變累計(jì)達(dá)到一定次數(shù)后才實(shí)施獎(jiǎng)勵(lì)，這種方式操作起來比較簡單，但容忍次數(shù)的設(shè)置沒有可靠依據(jù)，只能通過經(jīng)驗(yàn)預(yù)定。本文實(shí)驗(yàn)中通過能量差額比較的方法來啟動(dòng)能量獎(jiǎng)勵(lì)步驟，當(dāng)未被接受的能量差額累計(jì)值超過某個(gè)數(shù)額時(shí)，妖將獲得一次能量獎(jiǎng)勵(lì)。
為此，需再設(shè)定一個(gè)變量Er和Eg。Er以累加的方式記錄連續(xù)的、未被接收的能量差額值。譬如當(dāng)前領(lǐng)域變換得到的新狀態(tài)將使得系統(tǒng)能量值提高12，而妖的能量值ED=8，按照狀態(tài)接收規(guī)則，新狀態(tài)不被接受，此時(shí)Er的數(shù)值將增加12。若新狀態(tài)被接收，此時(shí)Er將被清零，使得能量獎(jiǎng)勵(lì)機(jī)制只在當(dāng)前解連續(xù)多次沒有改進(jìn)時(shí)發(fā)揮作用。若新狀態(tài)使得系統(tǒng)能量回升過大，Er的累計(jì)操作將會(huì)被忽略，實(shí)際執(zhí)行時(shí)，若未被接受的能量回升值超過了妖的最大能量上限M，該差額不被計(jì)入Er。
Eg控制了獎(jiǎng)勵(lì)操作的閾值，可直接令Eg＝M，并隨M的縮減而變化。在算法運(yùn)行過程中，當(dāng)Er>Eg時(shí)，將執(zhí)行能量獎(jiǎng)勵(lì)操作，隨后Er被清零。
能量獎(jiǎng)勵(lì)策略的另一項(xiàng)決策是確定獎(jiǎng)勵(lì)幅度，在最初的算法改進(jìn)方案中，執(zhí)行固定比例的獎(jiǎng)勵(lì)（如獎(jiǎng)勵(lì)增幅q可設(shè)為0.01）。考慮到妖在算法運(yùn)行前期獲得額外獎(jiǎng)勵(lì)的需求并不強(qiáng)烈，而陷入停滯狀態(tài)，往往是算法后期才表現(xiàn)出來，因此本文設(shè)計(jì)了一種新的獎(jiǎng)勵(lì)方法，增幅q將以線性增大的方式在預(yù)先選定的區(qū)間內(nèi)變化（如0.005～0.05）。
3.4 算法流程
（1）相關(guān)變量初始化操作，創(chuàng)建初始可行解，并釋放能量ED＝0的妖。
（2）外層循環(huán)控制，若M小于e則終止程序。
（3）更新M，按比例縮減；更新Eg與q。
（4）內(nèi)循環(huán)控制，若滿足3.2節(jié)所列條件，程序返回到步驟（2）。
（5）創(chuàng)建鄰域解。
（6）若系統(tǒng)能量值降低或系統(tǒng)能量值增大幅度小于ED時(shí)均接受鄰域解；更新Er；更新ED。
（7）若領(lǐng)域狀態(tài)被拒絕，則將此未被接收的能量增幅記入Er中，并比較Er與Eg，以決定是否實(shí)施能量獎(jiǎng)勵(lì)。
（8）返回步驟（4）。
4 實(shí)例分析
采用包含20個(gè)需求點(diǎn)的單配送中心實(shí)例來驗(yàn)證改進(jìn)算法的效果[4]。其中運(yùn)輸車輛的最大載貨量D等于8。根據(jù)有關(guān)文獻(xiàn)的建議，已有經(jīng)驗(yàn)公式估計(jì)車輛總數(shù)[7]，本文約定有6輛運(yùn)輸車。配送中心的坐標(biāo)為（52，4），其他客戶節(jié)點(diǎn)的坐標(biāo)及需求量如表1所示。
?
根據(jù)筆者之前對(duì)該實(shí)例的模擬經(jīng)驗(yàn)，令初始M=100；α=0.95；U=100；L=30；e=0.01；q在0.005～0.05之間變化。在上述參數(shù)下，微正則退火基本算法的表現(xiàn)比較穩(wěn)定。
表2展示了改進(jìn)算法中能量獎(jiǎng)勵(lì)策略的效果。其中算法1指未進(jìn)行任何改進(jìn)的微正則退火基本算法；算法2施加了簡單的能量獎(jiǎng)勵(lì)策略（即2.2節(jié)描述的方式）；算法3以能量差額比較的方式啟動(dòng)獎(jiǎng)勵(lì)策略，獎(jiǎng)勵(lì)幅度固定；算法4指以能量差額比較的方式啟動(dòng)獎(jiǎng)勵(lì)策略，獎(jiǎng)勵(lì)幅度線性變化。各組算法均以相同的初始解開始搜索，并對(duì)30次隨機(jī)實(shí)驗(yàn)的結(jié)果進(jìn)行統(tǒng)計(jì)。
?
?
為了便于比較，以運(yùn)輸費(fèi)用降到901作為算法搜索成功的標(biāo)準(zhǔn)，此運(yùn)輸費(fèi)用是本實(shí)例一個(gè)較好的結(jié)果。表2中的第二列指最終找到這個(gè)滿意解的次數(shù)。第三列指該算法的全部30次實(shí)驗(yàn)中，最終運(yùn)輸費(fèi)用距離901的平均距離（費(fèi)用差額值占901%），該比例越小，說明最終解越好。
對(duì)表2分析可見：首先，能量獎(jiǎng)勵(lì)策略是有效的，從一定程度上提高了算法搜索到指定滿意解的能力。實(shí)施了能量獎(jiǎng)勵(lì)策略的三組算法，對(duì)于本實(shí)例的搜索成功次數(shù)都比基本算法要高。其次，利用能量差額比較來判定是否獎(jiǎng)勵(lì)的效果得到了驗(yàn)證，與簡單的能量獎(jiǎng)勵(lì)策略相比，它的成功次數(shù)更大。再次，從表2的第三列可知，實(shí)施能量獎(jiǎng)勵(lì)策略后，多次實(shí)驗(yàn)的平均解要更列可知，實(shí)施能量獎(jiǎng)勵(lì)策略后，多次實(shí)驗(yàn)的平均解要更接近指定的滿意解，而且本文提出的能量獎(jiǎng)勵(lì)實(shí)施策略進(jìn)一步提高了微正則退火算法的搜索能力。
圖1是上述實(shí)驗(yàn)中4種算法最低運(yùn)輸成本的變化軌跡。可以看出微正則退火基本算法在最開始階段的下降速度很快，但到后期不如其他算法。根據(jù)能量獎(jiǎng)勵(lì)策略的特點(diǎn)可知，它使得整個(gè)搜索過程更為平緩一些，前期目標(biāo)函數(shù)值下降稍慢，這從一定程度上消弱了微正則退火算法本身的快速優(yōu)化優(yōu)勢(shì)，但從圖1可發(fā)現(xiàn)，施加了改進(jìn)的能量獎(jiǎng)勵(lì)策略后，對(duì)上述問題有了明顯的改善。
?
?
微正則退火算法具有快速收斂特征，不少研究文獻(xiàn)中都探討了這種退火算法的工程應(yīng)用價(jià)值。本文首先對(duì)筆者曾提出的能量獎(jiǎng)勵(lì)策略進(jìn)行改進(jìn)，根據(jù)能量差額比較的方法來決定是否啟動(dòng)獎(jiǎng)勵(lì)操作，并且嘗試能量增幅比例q按線性方式調(diào)節(jié)。隨后將新的改進(jìn)算法應(yīng)用車輛路徑優(yōu)化問題，并通過一個(gè)典型的單配送中心實(shí)例給出了初步比較。實(shí)驗(yàn)結(jié)果證明這種改進(jìn)的微正則退火算法用于路徑優(yōu)化是十分有效的。本文的改進(jìn)思路也有缺點(diǎn)，增加了算法代碼的復(fù)雜程度，理論上會(huì)耗費(fèi)更長的搜索時(shí)間，但在本實(shí)例上表現(xiàn)不明顯，應(yīng)該用更大規(guī)模的實(shí)例來檢驗(yàn)，這將是下一步的工作內(nèi)容。
參考文獻(xiàn)
[1] PAOLO T, DANIELE V. The vehicle routing problem[M]. Philadelphia: Society for Industrial and Applied Mathematics,2002.
[2]?祝崇雋, 劉民, 吳澄. 供應(yīng)鏈中車輛路徑問題的研究進(jìn)展及前景[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2001, 7 (11) :1-6.
[3]?崔雪麗, 馬良, 范炳全. 車輛路徑問題( VRP) 的螞蟻搜索算法[J]. 系統(tǒng)工程學(xué)報(bào), 2004, 19(4) :418-422.
[4]?胡大偉, 朱志強(qiáng), 胡勇. 車輛路徑問題的模擬退火算法[J]. 中國公路學(xué)報(bào), 2006, 19(4) :123-126.
[5]?張波, 葉家瑋, 胡郁蔥. 模擬退火算法在路徑優(yōu)化問題中的應(yīng)用[J]. 中國公路學(xué)報(bào), 2004,17(1):79-81.
[6]?CREYTZ M. Microcanonical Monte Carlo simulation[J]. Physical Review Letters, 1983, 50(19): 1411-1414.
[7]?李軍, 謝秉磊, 郭耀煌. 非滿載車輛調(diào)度問題的遺傳算法[J]. 系統(tǒng)工程理論與實(shí)踐, 2000, 20(3):235-239.