摘 要：設(shè)計了一種新的能量獎勵機制，以提高微正則退火算法擺脫局部極值點的能力,。在狀態(tài)轉(zhuǎn)移被拒絕后,，通過比較兩個能量參數(shù)的大小來啟動獎勵操作。獎勵方式依舊為幾何增長方式,，但增長幅度改為一定區(qū)間內(nèi)的線性調(diào)節(jié),。給出了一個采用改進(jìn)算法的經(jīng)典的單配送中心實例，它提高了微正則退火基本算法的優(yōu)化效果,，降低了搜索過程停滯在局部極值的概率,，它搜索到的運輸費用更貼近最佳解。
　　關(guān)鍵詞：車輛路徑問題,；微正則退火算法,；組合優(yōu)化

?

　　配送車輛路徑問題VRP（Vehicle Routing Problem）是指向一批客戶配送物資，客戶的位置和貨物需求量已知,，現(xiàn)有若干可供派送的車輛,，車輛的運載能力給定，每輛車都從起點出發(fā),，完成若干客戶點的運送任務(wù)后再回到起點,，現(xiàn)尋求以最少的車輛數(shù)、最小的車輛總行程來完成貨物配送任務(wù),。
　　車輛路徑問題是物流配送中的關(guān)鍵決策問題,，已有研究表明該問題屬于NP難題^[1-2]。求解該問題有兩類方法,，一類是精確算法,，另一類是啟發(fā)式算法^[3-5]，后者力圖在有限的時間內(nèi)找到大規(guī)模問題的滿意解,，得到不少工程人員的關(guān)注,。本文研究的微正則退火算法MA（Micro-canonical Annealing）也屬于啟發(fā)式算法的范疇，有關(guān)研究表明,，該算法具有實施簡單,、運行速度快、優(yōu)化效果出色等優(yōu)點^[6],。筆者曾提出一種對該算法的改進(jìn)思路,，針對算法迭代后期的優(yōu)化進(jìn)程放緩問題，適時給予能量獎勵策略,，提高了在旅行推銷員問題上的搜索性能,。本文改進(jìn)了這種能量獎勵思想,，將其用于配送路徑的優(yōu)化問題。實驗研究發(fā)現(xiàn),，改進(jìn)算法提高了最終解的質(zhì)量,，能夠得到更低的運輸費用。
1 配送車輛路徑問題的數(shù)學(xué)模型
　　根據(jù)約束條件和目標(biāo)函數(shù)的差異,，車輛路徑問題的數(shù)學(xué)模型可寫成多種形式。最簡單的情形是設(shè)計從一個位置出發(fā),，到多個不同位置的客戶點的最優(yōu)配送路徑,，即尋找一個運費最小的路徑集合，并滿足如下條件：
　　首先,，每條配送路徑上各個客戶的需求量之和不超過汽車載貨量,。
　　其次，每個客戶的需求必須滿足,，且只能由一輛汽車送貨,。
　　先作如下定義：i、j 為任意兩個客戶的標(biāo)號,，i,、j∈N；N = { 1, 2,…, n},，n為客戶的數(shù)目,，標(biāo)號0表示配送中心（即假定只有一個配送中心的情形）；k為配送車輛的標(biāo)號,；k∈k,，k = {1, 2 , …, m}，m為車輛的數(shù)目,；C_i,j為客戶i,、j 之間的距離；X_ijk為路徑?jīng)Q策變量,，當(dāng)?shù)趉輛車從客戶i駛向客戶j時X_ijk為1,，否則X_ijk為0；Y_ik為車輛與客戶的配對參數(shù),，當(dāng)車輛k服務(wù)客戶i時取值為1,，否則取0；w_j為客戶j的貨物需求量,；D為車輛的最大載貨量,，C_min為最少總費用?？山⑷缦履Ｐ停?BR>　　
　　式（1）為目標(biāo)函數(shù),，使得總費用最?。皇剑?）表示每個客戶都被訪問且僅被訪問一次,；式（3）,、（4）為每條巡回路徑上的配送限制；式（5）為車輛的載貨量限制,。
2? 微正則退火算法及改進(jìn)策略
2.1 算法的基本原理
　　微正則退火與傳統(tǒng)模擬退火的差異在于,，它不再直接依賴系統(tǒng)溫度，配分函數(shù)Z的形式為：
　　　　

　　式（6）中,，E₀是初始能量值,，K(P)是動量P在狀態(tài)C下的能量，上式中沒有出現(xiàn)溫度參數(shù),。
　　在這一仿真方法中,，假設(shè)熱系統(tǒng)中存在一個具有能量交換能力的妖，它的作用類似式（6）中的動量P,。這只妖可以在狀態(tài)空間中隨機行走,，并通過改變熱系統(tǒng)的狀態(tài)變量達(dá)到調(diào)節(jié)系統(tǒng)能量的目的。仿真過程中,，系統(tǒng)與妖的能量之和保持定值并且逐步降低,，促使系統(tǒng)積累足夠的能量以脫離亞穩(wěn)態(tài)。令妖的能量為ED,，ED為正數(shù)且初始值一般等于0,。此時Z的形式為：
　　
　　系統(tǒng)初始狀態(tài)可以隨機配置，妖在狀態(tài)空間中每隨機行走一步,，就會嘗試改變當(dāng)前的系統(tǒng)狀態(tài),，若此舉能降低系統(tǒng)能量，則系統(tǒng)接收狀態(tài)變遷,。與此同時,，系統(tǒng)釋放的能量將會被妖吸收。當(dāng)這種退火機制用于尋求目標(biāo)函數(shù)最小值時,，狀態(tài)空間對應(yīng)于自變量空間,，系統(tǒng)能量對應(yīng)于目標(biāo)函數(shù)值。妖的能量變更可用如下公式表達(dá)：
　　
　　式中E^new,、E^old分別表示新舊狀態(tài)所對應(yīng)的系統(tǒng)能量,。為保證妖的能量總是正值，若妖的隨機行走導(dǎo)致系統(tǒng)能量升高且升高幅度超過ED,，該狀態(tài)轉(zhuǎn)移將被拒絕,。另一方面，妖的能量ED也有上界約束M,，該值隨著迭代過程逐步減小,。
2.2 能量獎勵策略
　　妖的當(dāng)前能量ED直接限制了系統(tǒng)能量回升的最大幅度,，這一數(shù)值刻畫出系統(tǒng)脫離亞穩(wěn)態(tài)的能力大小。在算法后期,，由于Emax的作用,，ED總體處于下降趨勢，劣狀態(tài)被接受的概率非常低,，若系統(tǒng)陷入一個比較深的能量局部極小狀態(tài),，確定性的狀態(tài)接受規(guī)則將使得系統(tǒng)幾乎不能脫離該狀態(tài)。
　　筆者曾考慮對妖的能量ED施加一種幾何方式的能量獎勵策略,，在拒絕新狀態(tài)后,，適當(dāng)增大ED的數(shù)值，以期逐步提高妖脫離局部極值的能力,。具體操作方法是：對E_D實施比例為q的增幅，即E_D←E_D×(1＋q),，其中q值一般很小,。在先前所做的實例仿真中發(fā)現(xiàn)，一種被稱為無上界約束的能量獎勵策略效果很小,，這種方式在實施能量獎勵后不檢查ED是否超過E_max（當(dāng)妖主動吸收能量后仍然要對ED做越界約束）,。
3?改進(jìn)微正則退火算法的實施
　　微正則退火算法用于組合優(yōu)化時，算法的實施流程與傳統(tǒng)模擬退火算法類似,，具體體現(xiàn)在：第一,，算法需要一個初始解，算法的主過程將在該初始解上執(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é)點之間的整段路徑需要翻轉(zhuǎn),，后續(xù)實驗中使用了二交換方法,。
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,，或找到指定解時即被終止,，最后輸出最終搜索結(jié)果。
3.3 改進(jìn)的能量獎勵策略
　　實施能量獎勵策略時,，需要做好兩項決策,，首先是獎勵時機的選擇，之前筆者曾設(shè)計過一種容忍機制,，只在當(dāng)前狀態(tài)沒改變累計達(dá)到一定次數(shù)后才實施獎勵,，這種方式操作起來比較簡單，但容忍次數(shù)的設(shè)置沒有可靠依據(jù),，只能通過經(jīng)驗預(yù)定,。本文實驗中通過能量差額比較的方法來啟動能量獎勵步驟，當(dāng)未被接受的能量差額累計值超過某個數(shù)額時,，妖將獲得一次能量獎勵,。
　　為此，需再設(shè)定一個變量E_r和E_g,。E_r以累加的方式記錄連續(xù)的,、未被接收的能量差額值。譬如當(dāng)前領(lǐng)域變換得到的新狀態(tài)將使得系統(tǒng)能量值提高12,，而妖的能量值E_D=8,，按照狀態(tài)接收規(guī)則，新狀態(tài)不被接受,，此時E_r的數(shù)值將增加12,。若新狀態(tài)被接收，此時Er將被清零,，使得能量獎勵機制只在當(dāng)前解連續(xù)多次沒有改進(jìn)時發(fā)揮作用,。若新狀態(tài)使得系統(tǒng)能量回升過大，E_r的累計操作將會被忽略，實際執(zhí)行時,，若未被接受的能量回升值超過了妖的最大能量上限M,，該差額不被計入E_r。
　　E_g控制了獎勵操作的閾值,，可直接令E_g＝M,，并隨M的縮減而變化。在算法運行過程中,，當(dāng)E_r>E_g時,，將執(zhí)行能量獎勵操作，隨后Er被清零,。
　　能量獎勵策略的另一項決策是確定獎勵幅度,，在最初的算法改進(jìn)方案中，執(zhí)行固定比例的獎勵（如獎勵增幅q可設(shè)為0.01）,?？紤]到妖在算法運行前期獲得額外獎勵的需求并不強烈，而陷入停滯狀態(tài),，往往是算法后期才表現(xiàn)出來,，因此本文設(shè)計了一種新的獎勵方法，增幅q將以線性增大的方式在預(yù)先選定的區(qū)間內(nèi)變化（如0.005～0.05）,。
3.4 算法流程
　　（1）相關(guān)變量初始化操作,，創(chuàng)建初始可行解,，并釋放能量E_D＝0的妖。
　?。?）外層循環(huán)控制,，若M小于e則終止程序。
　?。?）更新M,，按比例縮減；更新E_g與q,。
　?。?）內(nèi)循環(huán)控制，若滿足3.2節(jié)所列條件,，程序返回到步驟（2）,。
　　（5）創(chuàng)建鄰域解,。
　?。?）若系統(tǒng)能量值降低或系統(tǒng)能量值增大幅度小于ED時均接受鄰域解；更新Er；更新E_D,。
　?。?）若領(lǐng)域狀態(tài)被拒絕，則將此未被接收的能量增幅記入E_r中,，并比較E_r與E_g,，以決定是否實施能量獎勵。
　?。?）返回步驟（4）,。
4 實例分析
　　采用包含20個需求點的單配送中心實例來驗證改進(jìn)算法的效果^[4]。其中運輸車輛的最大載貨量D等于8,。根據(jù)有關(guān)文獻(xiàn)的建議,，已有經(jīng)驗公式估計車輛總數(shù)^[7]，本文約定有6輛運輸車,。配送中心的坐標(biāo)為（52,，4），其他客戶節(jié)點的坐標(biāo)及需求量如表1所示,。

?

　　根據(jù)筆者之前對該實例的模擬經(jīng)驗,，令初始M=100；α=0.95,；U=100,；L=30；e=0.01,；q在0.005～0.05之間變化,。在上述參數(shù)下，微正則退火基本算法的表現(xiàn)比較穩(wěn)定,。
　　表2展示了改進(jìn)算法中能量獎勵策略的效果,。其中算法1指未進(jìn)行任何改進(jìn)的微正則退火基本算法；算法2施加了簡單的能量獎勵策略（即2.2節(jié)描述的方式）,；算法3以能量差額比較的方式啟動獎勵策略,，獎勵幅度固定；算法4指以能量差額比較的方式啟動獎勵策略,，獎勵幅度線性變化,。各組算法均以相同的初始解開始搜索，并對30次隨機實驗的結(jié)果進(jìn)行統(tǒng)計,。

?

?

　　為了便于比較,，以運輸費用降到901作為算法搜索成功的標(biāo)準(zhǔn)，此運輸費用是本實例一個較好的結(jié)果,。表2中的第二列指最終找到這個滿意解的次數(shù),。第三列指該算法的全部30次實驗中，最終運輸費用距離901的平均距離（費用差額值占901%），該比例越小,，說明最終解越好,。
　　對表2分析可見：首先，能量獎勵策略是有效的,，從一定程度上提高了算法搜索到指定滿意解的能力,。實施了能量獎勵策略的三組算法，對于本實例的搜索成功次數(shù)都比基本算法要高,。其次,，利用能量差額比較來判定是否獎勵的效果得到了驗證，與簡單的能量獎勵策略相比,，它的成功次數(shù)更大,。再次，從表2的第三列可知,，實施能量獎勵策略后,，多次實驗的平均解要更列可知，實施能量獎勵策略后,，多次實驗的平均解要更接近指定的滿意解,，而且本文提出的能量獎勵實施策略進(jìn)一步提高了微正則退火算法的搜索能力。
　　圖1是上述實驗中4種算法最低運輸成本的變化軌跡,?？梢钥闯鑫⒄齽t退火基本算法在最開始階段的下降速度很快，但到后期不如其他算法,。根據(jù)能量獎勵策略的特點可知,，它使得整個搜索過程更為平緩一些，前期目標(biāo)函數(shù)值下降稍慢,，這從一定程度上消弱了微正則退火算法本身的快速優(yōu)化優(yōu)勢，但從圖1可發(fā)現(xiàn),，施加了改進(jìn)的能量獎勵策略后,，對上述問題有了明顯的改善。

?

?