于建芳， 劉 升

(上海工程技術(shù)大學(xué)管理學(xué)院,上海 201620)

中國是世界上能源消耗和碳排放的大國之一，空氣污染越來越嚴(yán)重，霧霾也是常年伴隨人們的出行，所以“綠色物流”一詞出現(xiàn)的頻率越來越高，城市物流的目標(biāo)不再僅僅是滿足客戶需求的情況下降低配送成本，同時還要考慮物流配送活動對環(huán)境的影響，呼吁社會發(fā)展綠色低碳的可循環(huán)經(jīng)濟(jì)模式迫在眉睫，綠色低碳經(jīng)濟(jì)必將成為未來社會的主流經(jīng)濟(jì)模式。車輛路徑問題(vehicle routing problem，VRP)[1]近年來研究者眾多，物流運(yùn)輸在低碳經(jīng)濟(jì)中的重要性也使得路徑規(guī)劃變得尤為重要，所以車輛路徑問題方面的研究是企業(yè)所亟需的。相應(yīng)的，研究也面臨著復(fù)雜約束條件、求解規(guī)模較大、求解難度大、成本增高等難題。

演化算法的應(yīng)用可以幫助企業(yè)找到成本最低、路徑最短、時間最短相結(jié)合的最佳的科學(xué)配送路徑，節(jié)約能源，減少碳排放，提高服務(wù)質(zhì)量，所以演化算法是綠色物流的最佳選擇方案，對于提高企業(yè)的經(jīng)濟(jì)效益，具有重要的理論意義和實(shí)用價值。以往的研究對具有挑戰(zhàn)性的車輛配送問題作出了十分重要的貢獻(xiàn)，然而，在大規(guī)模部署車輛路徑問題方面還是面臨著很大的挑戰(zhàn)，特別是對于具有不同道路容量和交通延遲約束的區(qū)域網(wǎng)絡(luò)、高速公路瓶頸和城市街道上的信號定時等問題。Gayialis等[2]結(jié)合現(xiàn)有研究文獻(xiàn)對Scopus科學(xué)數(shù)據(jù)庫進(jìn)行了文獻(xiàn)綜述，對過去10年的城市物流運(yùn)輸VRP問題進(jìn)行分類，梳理和分析了城市物流運(yùn)輸VRP的發(fā)展趨勢。Kenan等[3]提出了一種創(chuàng)新性的G-VRP模型，以降低汽車油箱的油耗為目的，以模擬退火算法求解該模型，降低了CO2的濃度。Dulai等[4]為解決車輛配送過程中突發(fā)故障的問題，提出一種容錯算法，當(dāng)突發(fā)故障是可以由其他車輛以最有效的方式代為配送完成剩余任務(wù)，最小化“路線變更成本”，但是使用容錯算法后配送路徑長度平均比原車輛路徑問題短4.1%～8.6%，為車輛路徑問題求解提供新思路。Wang等[5]延伸了車輛路徑問題，把油耗和模糊出行時間加入目標(biāo)函數(shù)中，采用模糊函數(shù)改進(jìn)遺傳算法以解決綠色模糊車輛路徑問題，提高了求解精度，很大程度上縮短了運(yùn)行時間。

葛顯龍等[6]以純電動汽車為研究對象對車輛路徑問題進(jìn)行研究，減少燃油車的使用固然綠色低碳，但電動車的使用受到很多限制，電量續(xù)航是最大的問題，使其比傳統(tǒng)汽車具有更高的使用成本；但是電動車在未來必定是最綠色環(huán)保的物流配送形式。李珍萍等[7]研究了一種具有多種需求且由不同類型車輛提供服務(wù)的顧客需求配送模式，建立了混合整數(shù)規(guī)劃模型，進(jìn)一步設(shè)計了混合遺傳算法求解，驗(yàn)證了改進(jìn)算法的有效性，為解決實(shí)際問題提供了決策依據(jù)。李小川等[8]提出一種基于文化基因的狼群算法，以最小化總距離和車輛數(shù)為目標(biāo)，求解帶時間窗的車輛路徑問題，試驗(yàn)結(jié)果表明文化狼群算法求解效果較好，為解決VRP問題提供了新途徑。錢曉明等[9]提出一種混合模擬退火算法，用于求解固定車輛數(shù)的多車型車輛路徑問題，模型的實(shí)用性和算法的有效性得到了強(qiáng)有力的驗(yàn)證，但是作者僅僅增加禁忌表對模擬退火算法進(jìn)行改進(jìn)，過于簡單。何東東等[10]以節(jié)能減排為目標(biāo)，構(gòu)建了考慮低碳和成本節(jié)約的多種車型且?guī)r間窗的車輛路徑問題模型，采用改進(jìn)的禁忌搜索算法求解該問題，實(shí)驗(yàn)驗(yàn)證了模型和算法的有效性和可行性，但是求解方法不夠新穎。

結(jié)合上述求解車輛路徑問題中的算法改進(jìn)設(shè)計簡單，求解案例點(diǎn)數(shù)過少等不足，提出了一種基于黃金正弦的模擬退火算法(simulated annealing algorithm based on golden sine,GSSA)。該算法結(jié)合新型的啟發(fā)式算法黃金正弦算法，兩個階段法對所提出的車輛路徑模型進(jìn)行求解，并且增加模擬退火算法的鄰域搜索設(shè)計和記憶裝置，使第二階段的鄰域搜索范圍更廣，記錄目前為止的最優(yōu)值，以提高算法的收斂精度，減少搜索時間。

1 有能力約束的車輛路徑問題(CVRP)

有能力約束的車輛路徑問題(capacitated vehicle routing problem，CVRP)是在標(biāo)準(zhǔn)車輛路徑問題的基礎(chǔ)上增加能力約束使模型更加符合現(xiàn)實(shí)生活中遇到的配送問題模型。CVRP可以描述為：某配送中心0用多輛相同汽車向有不同需求的客戶配送貨物，已知每個客戶的位置、需求量以及汽車的容量，配送路徑受車輛的容量、行駛路程等限制，需要合理安排車輛配送選擇最佳車輛路徑，使得總路程最短、總費(fèi)用最小、配送總時間最短等。

車輛路徑問題(VRP)一直都是NP-hard難題，對于這種多目標(biāo)多約束的問題，其結(jié)果也是受到很多因素的影響，需要作出一定的假設(shè)，盡可能地減小不必要的因素對結(jié)果的影響，減少求解難度，使最終結(jié)果更加符合現(xiàn)實(shí)生活中的要求，所作出的假設(shè)如下。

(1)配送中心具有固定的車輛數(shù)且每輛車車型完全相同。

(2)每輛車可以滿足多個客戶點(diǎn)的需求，而每個客戶點(diǎn)只能被一輛車服務(wù)，在配送服務(wù)完成之后車輛要駛回車場。

(3)假設(shè)車輛配送產(chǎn)生的成本與路徑長度線性相關(guān)，每輛車固定成本相同。

(4)每輛車載量有限，客戶點(diǎn)的總需求量不得超過車隊(duì)總裝載量。

(5)有且只有一個配送中心。

VRP涉及的符號及其意義如表1所示。

表1 符號及其意義

設(shè)定決策變量[11]如下。

則CVRP的數(shù)學(xué)模型為

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

式(1)為以行駛距離最短、成本最低為目標(biāo)的目標(biāo)函數(shù)，表示使總配送成本最小，總配送距離最短，配送的車輛數(shù)最少;式(2)為車輛載重約束，限制每輛貨車初始裝載量的最大值，亦即每輛貨車出發(fā)時的最大配貨量是不能超過一定數(shù)值的;式(3)和式(4)為客戶配送唯一性，表示每個客戶只有一輛車配送;式(5)和式(6)為配送中心約束，有且只有一個配送中心; 式(7)為子回路約束; 式(8)為客戶車輛流守恒約束，配送車輛的數(shù)目是固定不變的; 式(9)和式(10)為0～1變量約束。

2 基本模擬退火算法

模擬退火(simulated annealing，SA)[12]算法是一種全局統(tǒng)計優(yōu)化方法，是最適合解決車輛路徑問題的算法之一。它最早由Metropolis提出，是從物質(zhì)的物理退火過程中得到啟發(fā)。退火過程大致是:先將物體不斷加熱至高溫，溫度越高物質(zhì)內(nèi)部的粒子活躍性越高，且處于高速轉(zhuǎn)動的不穩(wěn)定狀態(tài)，此時物質(zhì)具有較高的內(nèi)能;然后緩慢降溫，原子運(yùn)動速度隨著溫度的下降減慢，活躍度下降，物質(zhì)的內(nèi)能下降; 最后，整個物體達(dá)到內(nèi)能最低，變成穩(wěn)定的狀態(tài)。

模擬退火過程類似于沿水平方向晃動裝有小球的托盤，溫度越高則意味著晃動的幅度越大，小球會從一個低谷跳入另一個低谷。從全局優(yōu)化的角度考慮，每一步低谷的高度要比小球原來所在低谷的高度低，才能最終得到最優(yōu)解;但正是托盤中小球“爬山”的能力，才使增大小球從局部低谷跳出而落入全局低谷的概率，達(dá)到最終的最優(yōu)值。當(dāng)然，退火的溫度要適合，由強(qiáng)至弱，慢慢減弱小球跳動的能力，使小球不會越爬越高。

固體物質(zhì)退火過程和組合優(yōu)化問題有很多共同點(diǎn):金屬溫度設(shè)置控制參數(shù)T來代替，金屬狀態(tài)i及其當(dāng)前內(nèi)能類比于實(shí)際問題中的結(jié)果x及其費(fèi)用函數(shù)f(x)。所以固體物質(zhì)退火過程和組合優(yōu)化問題有很大的共性特點(diǎn)，后來人們成功把模擬退火算法用于求解各種組合優(yōu)化問題。

SA算法迭代優(yōu)化尋找最優(yōu)解的過程中，首先需要確定一個初始溫度T0，設(shè)置參數(shù)，并以問題解空間的初始狀態(tài)作為初始解，然后在一定溫度下，對當(dāng)前解進(jìn)行搜索算子干擾，模擬固體內(nèi)部粒子的狀態(tài)轉(zhuǎn)移過程。之后比較在干擾后狀態(tài)下得出的新解和當(dāng)前解，依據(jù)Metropolis準(zhǔn)則進(jìn)行替換。該算法準(zhǔn)則是以概率1來接受適應(yīng)度值中的最優(yōu)解，以一定的概率來接受適應(yīng)值中的較差點(diǎn)。Metropolis準(zhǔn)則的這種特殊能力使得算法不易陷入局部最優(yōu)停滯，具有跳出局部獲得全局最優(yōu)解的能力。Me-tropolis準(zhǔn)則[13]定義為

(11)

由式(11)可知，當(dāng)E(j)≤E(i)時，即物質(zhì)的系統(tǒng)能量函數(shù)適應(yīng)值減少時，該系統(tǒng)將會以概率1來接受新的適應(yīng)度值，即會100%接受；反之，以一定的概率來接受適應(yīng)值中的較差點(diǎn)。

基本退火算法的Metropolis準(zhǔn)則設(shè)計使得算法有接受較差解的優(yōu)勢，但是亦導(dǎo)致了可能錯過最優(yōu)解的問題，還有鄰域搜索能力不強(qiáng)，導(dǎo)致搜索時間過長等，所以算法仍存在改進(jìn)空間。

3 基于黃金正弦的模擬退火算法(GSSA)

模擬退火的依據(jù)是金屬的退火過程，其實(shí)質(zhì)為內(nèi)外兩層溫度發(fā)生的變溫循環(huán)：外循環(huán)控制溫度下降，使其達(dá)到適合內(nèi)循環(huán)的溫度狀態(tài)，內(nèi)循環(huán)以當(dāng)前溫度重復(fù)抽樣直至內(nèi)部達(dá)到穩(wěn)定為止。模擬退火算法主要包括溫度更新函數(shù)、初始溫度T0、狀態(tài)函數(shù)、狀態(tài)接受函數(shù)、內(nèi)循環(huán)和外循環(huán)終止準(zhǔn)則。模擬退火算法在理論上是一種全局最優(yōu)算法，但實(shí)際上存在以下不足：①降溫過程越緩慢得到的解的質(zhì)量越高，但相對的收斂速度就會太慢；反之，降溫過快很大可能影響全局優(yōu)化，得不到全局最優(yōu)解；②求解的質(zhì)量對參數(shù)設(shè)置有很強(qiáng)的依賴性；③在解決大規(guī)模的實(shí)際問題時，運(yùn)行時間過長。

3.1 編碼與解碼

Prins[14]提出了一種新型的路徑劃分方法，根據(jù)該路徑劃分方法，采用無分隔符的編碼解碼方式，科學(xué)合理地對車輛路徑問題的算例進(jìn)行了編碼，編碼結(jié)構(gòu)形式類似為S=[0—4—6—15—0]。

如圖1所示，解碼方法如下：假設(shè)有5個客戶需求點(diǎn)需要配送中心0向其配貨，配送中心有車型1、車型2兩種車型，fi表示固定費(fèi)用，vi表示不同車型的速度。計算各個路徑的配送成本，比較得出最小成本來確定最優(yōu)路徑。比如需求點(diǎn)1，采用車型1配送，成本c(0,1)=f1+v1[d(0,1)×2]，其中d(i,j)表示需求點(diǎn)之間的距離；然后將點(diǎn)2加入，若不超過容量約束則車型1配送路線為S=[0-2]，成本c(0,2)=f1+v1[d(0,1)+d(1,2)+d(2,0)]。增加點(diǎn)3，由于容量限制，增加車型2 配送，成本c(0,3)=f2+v2[d(0,1)+d(1,2)+d(2,3)+d(3,0)]。如此類推直到所有的點(diǎn)都被加入路線中，比較最終成本。

圖1 編碼和解碼Fig.1 Encoding and decoding

利用該編碼方式有效簡化了初始解的結(jié)構(gòu)，避免了線路間鄰域的計算，節(jié)約運(yùn)行時間，增加了模擬退火算法的搜索精度和速度。

3.2 算法設(shè)計

為彌補(bǔ)上述基本模擬退火算法中的不足，進(jìn)行以下3個方面的策略改進(jìn)，優(yōu)化基本模擬退火算法的性能，更加快速高效地求解出最優(yōu)的結(jié)果。

3.2.1 黃金正弦算法

黃金正弦算法(golden sine algorithm，Gold-SA)是Tanyildizi等[15]于2017年提出的新型元啟發(fā)式算法，該算法的設(shè)計靈感來源于數(shù)學(xué)中的正弦函數(shù)，該算法利用數(shù)學(xué)中的正弦函數(shù)進(jìn)行計算迭代尋優(yōu)，其優(yōu)點(diǎn)是收斂速度快、魯棒性好、易于實(shí)現(xiàn)、調(diào)節(jié)的參數(shù)和運(yùn)算符少。

Gold-SA根據(jù)正弦函數(shù)與單位圓的關(guān)系，可以遍歷正弦函數(shù)上的所有值，即尋遍單位圓上所有的點(diǎn)，同時在其位置更新過程中引入黃金分割數(shù)縮小解決方案的空間，以便掃描可能只產(chǎn)生良好結(jié)果的區(qū)域，很大提高了搜索速度，且使“搜索”和“開發(fā)”達(dá)到良好的平衡。

(12)

3.2.2 增加鄰域操作方法

基本SA的鄰域搜索操作是2-swap兩點(diǎn)置換法。因?yàn)樵摲椒看缓唵谓粨Q其中2個節(jié)點(diǎn)，如果要保證得到每一個溫度下的最優(yōu)解，就需要搜索更長的時間，所以該鄰域搜索方法對解空間的搜索能力比較弱。加上溫度降低，外循環(huán)更加頻繁，每次迭代的執(zhí)行時間成倍增長，使得算法的整體運(yùn)行時間過長。所以線路內(nèi)交換需要增加鄰域搜索，即增加2-opt、3-opt和2-insert 3種交換方法。4種交換方法隨機(jī)協(xié)作實(shí)施鄰域搜索操作，產(chǎn)生新的可行解。隨機(jī)協(xié)作是基于一定概率來隨機(jī)確定使用某一種交換方法來進(jìn)行鄰域搜索操作，這樣交替更換鄰域搜索的方式使產(chǎn)生新解空間的可能性增加，提高了基本算法跳出局部最優(yōu)停滯的可能性。

2-opt算法比圖2所示的(i,i+1)和(j,j+1)是兩條可行解路徑，若2-opt法進(jìn)行運(yùn)算，則j和i+1兩個點(diǎn)進(jìn)行翻轉(zhuǎn)交換，從而得到交換后的兩條新邊(i,j)和(i+1,j+1)，當(dāng)然，只有交換后的成本低于交換前，即Ci,i+1+Cj,j+1>Ci,j+Ci+1,j+1，才算得到新的可行解。

圖2 2-opt法Fig.2 2-opt method

3-opt算法，從前往后隨機(jī)選擇3 個點(diǎn)依次交換位置，與2-opt法類似但是搜索能力更強(qiáng)，具有產(chǎn)生新解更大的可能性，更加全面快速地搜索最優(yōu)解，提高全局搜索能力。

2-insert算法，遍歷所有的點(diǎn)隨機(jī)選擇相連兩個點(diǎn)i,j，若Cj>Ci，則將i點(diǎn)放在j點(diǎn)后面，同樣提高算法的搜索能力。

通過隨機(jī)性選擇上述4種鄰域操作，增加對解的結(jié)構(gòu)破壞力，共同協(xié)作完成搜索，加強(qiáng)了鄰域的搜索能力，及時地跳出局部最優(yōu)停滯，有利于改進(jìn)算法的全局尋優(yōu)能力。

3.2.3 設(shè)計記憶裝置和改變退火溫度

由于Metropolis準(zhǔn)則，在執(zhí)行概率接受環(huán)節(jié)中較易遺失當(dāng)前遇到的最優(yōu)解，所以在改進(jìn)的SA中設(shè)計一個記憶數(shù)組，用來記錄最優(yōu)解的值，從而使得算法運(yùn)行過程中輸出一直是“Best So Far”的最優(yōu)解。通過這種方法記憶目前為止的適應(yīng)度函數(shù)最小的解為最優(yōu)解，避免錯過可能的最優(yōu)值，很大程度上節(jié)約算法運(yùn)行的時間，提高了算法運(yùn)行的效率。

模擬退火算法在其退火的過程中，隨著溫度的下降其內(nèi)部的熵值越來越低，接受較差值的概率也隨之降低。所以在算法降溫過程的適當(dāng)時機(jī)，將溫度以一定比例適當(dāng)提高，增加固體內(nèi)部的活躍性，以激活搜索進(jìn)程中當(dāng)前狀態(tài)接受概率，避免算法陷入局部最優(yōu)停滯。退火過程的溫度曲線如圖3所示。

圖3 退火過程中隨降溫次數(shù)變化的適應(yīng)函數(shù)曲線Fig.3 The curve of the adaptive function varies with the times of cooling during annealing

新穎的黃金正弦算法結(jié)合模擬退火算法的特點(diǎn)進(jìn)行的改進(jìn)，既彌補(bǔ)了模擬退火算法收斂速度慢的問題，又吸收了模擬退火算法在解決VRP方面的優(yōu)勢；而記憶數(shù)組的設(shè)置和退火溫度的改變又提高了算法全局搜索獲得最優(yōu)的可能性，在一定程度上節(jié)約了運(yùn)行時間，從側(cè)面提高算法得到最優(yōu)結(jié)果的運(yùn)行速度，優(yōu)化了模擬退火算法的性能。

3.3 基于黃金正弦的模擬退火算法

綜合以上幾種方法，從改善初始解、鄰域搜索、運(yùn)行時間、接受可行解的范圍幾方面對基本模擬退火算法進(jìn)行改進(jìn)，以提高SA的優(yōu)化性能。

在模擬退算法的初始位置引入黃金正弦算法作為第一階段，由于Gold-SA函數(shù)與單位圓的關(guān)系，可以遍歷正弦函數(shù)上的所有值即尋遍單位圓上所有的點(diǎn)，使尋優(yōu)區(qū)域更加全面；同時通過參數(shù)R1和R2的隨機(jī)選擇控制位置更新距離和方向，可以逐步縮小搜索空間，快速引領(lǐng)蟻獅個體趨近最優(yōu)值，從而減少算法的尋優(yōu)時間，提高算法的尋優(yōu)速度和精度，獲得理想的尋優(yōu)結(jié)果；最后引入黃金分割數(shù)，可以根據(jù)式(12)確定其更新位置，確定最優(yōu)初始解。

第二階段的模擬退火算法結(jié)合新增的鄰域搜索方法和記憶裝置，4種方法隨機(jī)協(xié)作增加算法跳出局部最優(yōu)的可能性，記憶裝置增加算法的記憶功能，記錄迄今為止的最優(yōu)值，節(jié)約運(yùn)行時間，提高算法的優(yōu)化效率。首先進(jìn)行線路內(nèi)交換，4種交換方法隨機(jī)協(xié)作實(shí)施鄰域搜索操作，這樣交替更換鄰域搜索的方式破壞解空間結(jié)構(gòu)，增加產(chǎn)生新可行解的可能性，提高了基本算法跳出局部最優(yōu)停滯的可能性。然后進(jìn)行線路間的調(diào)整，引入λ-interchange思想對產(chǎn)生的可行解進(jìn)行操作，規(guī)定當(dāng)前溫度下鄰域搜索的次數(shù)為λ，以保證規(guī)定時間內(nèi)獲得較高質(zhì)量的最優(yōu)解。最后將適應(yīng)度值最小的解儲存到記憶裝置，避免接受解Metropolis準(zhǔn)則的采用錯過當(dāng)前遇到的最優(yōu)解；在適當(dāng)時機(jī)增加固體金屬的退火溫度，使金屬內(nèi)部物質(zhì)活躍性增加，加大可接受解的范圍，很大程度上節(jié)約了算法運(yùn)行的時間，大大提高了算法運(yùn)行的效率。

改進(jìn)的模擬退火算法的流程如圖4所示，具體步驟如下。

圖4 改進(jìn)模擬退火算法流程Fig.4 Flow chart of improved simulated annealing algorithm

步驟1：設(shè)置退火參數(shù)，初始溫度T0、溫度衰減系數(shù)α、終止溫度tf、當(dāng)前迭代次數(shù)u、當(dāng)前成功迭代次數(shù)l、最大迭代次數(shù)U、最大成功迭代次數(shù)L。

步驟2：隨機(jī)產(chǎn)生可行解f0，令fi=f0。

步驟3：利用黃金正弦算法可以遍歷正弦函數(shù)上的所有值等特點(diǎn)，能夠得到較優(yōu)的適應(yīng)值作為第二階段的初始解。

步驟4：構(gòu)造鄰域解。4種鄰域搜索方法隨機(jī)協(xié)作得到多個鄰域解fj，記憶裝置記錄當(dāng)前最優(yōu)的解，且令u=u+1。

步驟5：比較。如果fj≥fi，則轉(zhuǎn)步驟6；否則fi=fj，記錄當(dāng)前解為最優(yōu)解，l=l+1，轉(zhuǎn)步驟7。

步驟6：Metropolis準(zhǔn)則接受解。Δfij=fj-fi，若exp(-Δfij/Ti)>ε，ε是(0，1)隨機(jī)數(shù)，則fi=fj，l=l+1；否則，轉(zhuǎn)步驟7。

步驟7：最終溫度。若u≥U或l≥L，Ti+1=αTi，適當(dāng)提高溫度后，u=0，l=0，轉(zhuǎn)步驟7；否則返回步驟4。

步驟8：算法終止。若連續(xù)r=20次迭代結(jié)果相同，則算法終止；若當(dāng)前溫度Ti+1≤tf，則算法終止；否則返回步驟4。

4 改進(jìn)模擬退火算法在綠色物流車輛路徑問題中的應(yīng)用

4.1 案例問題描述

低碳物流運(yùn)輸?shù)陌l(fā)展是勢在必行的，車輛路徑的優(yōu)化是低碳物流最有效可行的措施之一。CVRP問題模型是最能體現(xiàn)現(xiàn)實(shí)生活中低碳物流的數(shù)學(xué)模型。某一物流運(yùn)輸公司A，在當(dāng)?shù)刂挥幸粋€配送中心0，需要向20 個客戶配送所需要的物品。已知配送中心有6輛車，車型都是相同的，車輛固定成本為100，容量為8，客戶之間的運(yùn)輸成本與車輛行駛的路徑有關(guān)。表2所示為配送中心以及各客戶的坐標(biāo)位置以及需求信息。

4.2 參數(shù)設(shè)置及結(jié)果分析

算法所在的實(shí)驗(yàn)平臺為Window7、64 bit系統(tǒng)、32 GB內(nèi)存。采用MATLAB 2017b進(jìn)行環(huán)境仿真實(shí)驗(yàn)。

經(jīng)過多次仿真試驗(yàn),在參數(shù)T0=50、α=0.85、U=100、L=30、tf=0.01時，得到結(jié)果為840.134 5，耗時為4.656 s，選取30次仿真測試中優(yōu)化結(jié)果最好的一次，路徑對比如圖5所示，成本收斂曲線對比如圖6所示。

表2 配送中心與各客戶的坐標(biāo)位置以及需求信息

圖5 20位客戶的仿真車輛路徑對比Fig.5 Simulated vehicle path diagram of 20 customers

圖5(a)和圖5(b)分別為配送中心和客戶之間兩種算法SA和GSSA的路徑對比，基本模擬退火算法和改進(jìn)的模擬退火算法相比明顯沒有基于黃金正弦的模擬退火算法路徑優(yōu)化路程短，證明該改進(jìn)算法的良好性能，對求解車輛路徑問題有很好的全局優(yōu)化效果。

由圖6可知，兩種算法在50次迭代以內(nèi)均達(dá)到了最優(yōu)的結(jié)果，且之后一直保持，但是GSSA的結(jié)果明顯優(yōu)于基本SA，收斂性極強(qiáng)，仿真曲線表明GSSA具有很強(qiáng)的穩(wěn)定性，全局收斂速度快，收斂精度高。

圖6 算法運(yùn)行優(yōu)化過程中成本的對比收斂曲線Fig.6 Convergence curve of costs during algorithm operation optimization

路徑仿真測試結(jié)果如表3所示。為證明本文的改進(jìn)算法的優(yōu)越性，與其他文獻(xiàn)的結(jié)果作相應(yīng)的對比。為顯示測試的公平性，與對比文獻(xiàn)均采用相同的數(shù)據(jù)信息，設(shè)置相同的參數(shù)，對比結(jié)果如下。

文獻(xiàn)[16]中采用改進(jìn)蟻群算法對該問題進(jìn)行求解，相同參數(shù)下求得最優(yōu)路徑平均值為863. 44，單次最優(yōu)為855. 68，優(yōu)化效果一般，沒有達(dá)到最優(yōu)結(jié)果。

文獻(xiàn)[17]中采用模擬退火算法對VRP中的TSP進(jìn)行了求解，但求解點(diǎn)數(shù)過少，僅對10個節(jié)點(diǎn)進(jìn)行了優(yōu)化，而本文中提出的基于黃金正弦的模擬退火算法用于VRP的求解，對20個節(jié)點(diǎn)數(shù)據(jù)的客戶需要進(jìn)行了配送求解。結(jié)果表明：最優(yōu)解比改進(jìn)前的優(yōu)化解更低，優(yōu)化能力更強(qiáng)。

文獻(xiàn)[18]中采用模擬退火算法對本案例進(jìn)行了求解，算法設(shè)計較為簡單，設(shè)置相同的參數(shù)求得最終運(yùn)輸費(fèi)用為855.68，很明顯優(yōu)化效果并沒有本改進(jìn)模擬退火算法的優(yōu)化能力強(qiáng)。

文獻(xiàn)[19]中采用遺傳算法對本案例進(jìn)行了求解，車輛數(shù)目為6，其運(yùn)輸成本結(jié)果為964.48。本改進(jìn)模擬退火算法設(shè)置相同的參數(shù)及車輛數(shù)目，測得最終結(jié)果為845.99。相較之下，本文的改進(jìn)算法所求得的成本最優(yōu)，具有更好的全局優(yōu)化性能。

表3 路徑仿真測試結(jié)果

5 結(jié)論

針對模擬退火算法容易陷入局部最優(yōu)、收斂速度慢、收斂精度不高等缺點(diǎn)，提出了一種基于黃金正弦的模擬退火算法。該算法以黃金正弦算法優(yōu)化模擬退火的初始值，第二階段增加了鄰域搜索方式，隨機(jī)協(xié)作提高模擬退火算法的搜索能力；增加記憶裝置，記錄迭代到目前為止適應(yīng)值最小值，避免陷入局部最小值；適當(dāng)提高物體下降溫度，增加物體內(nèi)部活躍性，加大可接受解的范圍，很大程度上優(yōu)化了算法的性能。通過一個運(yùn)輸實(shí)例對該改進(jìn)算法進(jìn)行了仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果證明該改進(jìn)算法解決車輛路徑問題具有很好的全局優(yōu)化效果，對于縮短配送路程、降低碳排放、降低成本費(fèi)用的城市綠色物流有著很強(qiáng)的實(shí)用意義。

燃油車輛運(yùn)輸無論怎么縮短路程、降低排放，都會不同程度地對環(huán)境造成污染，所以就需要更加清潔的新能源車輛、電動車輛等來代替燃油車輛，而且噸公里指標(biāo)的設(shè)置能更好衡量油量消耗和碳排放成本，都是未來物流運(yùn)輸市場的新趨勢，可為綠色物流及管理提供更多嘗試的新方向。