黃金正弦模擬退火算法求解低碳有能力約束的車輛路徑問題

于建芳， 劉 升

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

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

演化算法的應(yīng)用可以幫助企業(yè)找到成本最低、路徑最短、時間最短相結(jié)合的最佳的科學(xué)配送路徑，節(jié)約能源，減少碳排放，提高服務(wù)質(zhì)量，所以演化算法是綠色物流的最佳選擇方案，對于提高企業(yè)的經(jīng)濟效益，具有重要的理論意義和實用價值。以往的研究對具有挑戰(zhàn)性的車輛配送問題作出了十分重要的貢獻(xiàn)，然而，在大規(guī)模部署車輛路徑問題方面還是面臨著很大的挑戰(zhàn)，特別是對于具有不同道路容量和交通延遲約束的區(qū)域網(wǎng)絡(luò)、高速公路瓶頸和城市街道上的信號定時等問題。Gayialis等[2]結(jié)合現(xiàn)有研究文獻(xiàn)對Scopus科學(xué)數(shù)據(jù)庫進行了文獻(xiàn)綜述，對過去10年的城市物流運輸VRP問題進行分類，梳理和分析了城市物流運輸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ù)改進遺傳算法以解決綠色模糊車輛路徑問題，提高了求解精度，很大程度上縮短了運行時間。

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

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

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

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

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

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

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

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

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

(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)能;然后緩慢降溫，原子運動速度隨著溫度的下降減慢，活躍度下降，物質(zhì)的內(nèi)能下降; 最后，整個物體達(dá)到內(nèi)能最低，變成穩(wěn)定的狀態(tài)。

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

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

SA算法迭代優(yōu)化尋找最優(yōu)解的過程中，首先需要確定一個初始溫度T0，設(shè)置參數(shù)，并以問題解空間的初始狀態(tài)作為初始解，然后在一定溫度下，對當(dāng)前解進行搜索算子干擾，模擬固體內(nèi)部粒子的狀態(tài)轉(zhuǎn)移過程。之后比較在干擾后狀態(tài)下得出的新解和當(dāng)前解，依據(jù)Metropolis準(zhǔn)則進行替換。該算法準(zhǔn)則是以概率1來接受適應(yīng)度值中的最優(yōu)解，以一定的概率來接受適應(yīng)值中的較差點。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)值中的較差點。

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

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

模擬退火的依據(jù)是金屬的退火過程，其實質(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)算法，但實際上存在以下不足：①降溫過程越緩慢得到的解的質(zhì)量越高，但相對的收斂速度就會太慢；反之，降溫過快很大可能影響全局優(yōu)化，得不到全局最優(yōu)解；②求解的質(zhì)量對參數(shù)設(shè)置有很強的依賴性；③在解決大規(guī)模的實際問題時，運行時間過長。

3.1 編碼與解碼

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

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

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

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

3.2 算法設(shè)計

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

3.2.1 黃金正弦算法

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

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

(12)

3.2.2 增加鄰域操作方法

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

2-opt算法比圖2所示的(i,i+1)和(j,j+1)是兩條可行解路徑，若2-opt法進行運算，則j和i+1兩個點進行翻轉(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算法，從前往后隨機選擇3 個點依次交換位置，與2-opt法類似但是搜索能力更強，具有產(chǎn)生新解更大的可能性，更加全面快速地搜索最優(yōu)解，提高全局搜索能力。

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

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

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

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

模擬退火算法在其退火的過程中，隨著溫度的下降其內(nèi)部的熵值越來越低，接受較差值的概率也隨之降低。所以在算法降溫過程的適當(dāng)時機，將溫度以一定比例適當(dāng)提高，增加固體內(nèi)部的活躍性，以激活搜索進程中當(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é)合模擬退火算法的特點進行的改進，既彌補了模擬退火算法收斂速度慢的問題，又吸收了模擬退火算法在解決VRP方面的優(yōu)勢；而記憶數(shù)組的設(shè)置和退火溫度的改變又提高了算法全局搜索獲得最優(yōu)的可能性，在一定程度上節(jié)約了運行時間，從側(cè)面提高算法得到最優(yōu)結(jié)果的運行速度，優(yōu)化了模擬退火算法的性能。

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

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

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

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

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

圖4 改進模擬退火算法流程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：隨機產(chǎn)生可行解f0，令fi=f0。

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

步驟4：構(gòu)造鄰域解。4種鄰域搜索方法隨機協(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)隨機數(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 改進模擬退火算法在綠色物流車輛路徑問題中的應(yīng)用

4.1 案例問題描述

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

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

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

經(jīng)過多次仿真試驗,在參數(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的路徑對比，基本模擬退火算法和改進的模擬退火算法相比明顯沒有基于黃金正弦的模擬退火算法路徑優(yōu)化路程短，證明該改進算法的良好性能，對求解車輛路徑問題有很好的全局優(yōu)化效果。

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

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

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

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

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

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

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

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

5 結(jié)論

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

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