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

于建芳， 劉 升

(上海工程技術大學管理學院,上海 201620)

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 符號及其意義

設定決策變量[11]如下。

則CVRP的數學模型為

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

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

2 基本模擬退火算法

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

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

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

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

(11)

由式(11)可知，當E(j)≤E(i)時，即物質的系統能量函數適應值減少時，該系統將會以概率1來接受新的適應度值，即會100%接受；反之，以一定的概率來接受適應值中的較差點。

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

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

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

3.1 編碼與解碼

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

如圖1所示，解碼方法如下：假設有5個客戶需求點需要配送中心0向其配貨，配送中心有車型1、車型2兩種車型，fi表示固定費用，vi表示不同車型的速度。計算各個路徑的配送成本，比較得出最小成本來確定最優路徑。比如需求點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

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

3.2 算法設計

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

3.2.1 黃金正弦算法

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

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

(12)

3.2.2 增加鄰域操作方法

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

2-opt算法比圖2所示的(i,i+1)和(j,j+1)是兩條可行解路徑，若2-opt法進行運算，則j和i+1兩個點進行翻轉交換，從而得到交換后的兩條新邊(i,j)和(i+1,j+1)，當然，只有交換后的成本低于交換前，即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法類似但是搜索能力更強，具有產生新解更大的可能性，更加全面快速地搜索最優解，提高全局搜索能力。

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

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

3.2.3 設計記憶裝置和改變退火溫度

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

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

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

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

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

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

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

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

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

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

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

步驟2：隨機產生可行解f0，令fi=f0。

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

步驟4：構造鄰域解。4種鄰域搜索方法隨機協作得到多個鄰域解fj，記憶裝置記錄當前最優的解，且令u=u+1。

步驟5：比較。如果fj≥fi，則轉步驟6；否則fi=fj，記錄當前解為最優解，l=l+1，轉步驟7。

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

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

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

4 改進模擬退火算法在綠色物流車輛路徑問題中的應用

4.1 案例問題描述

低碳物流運輸的發展是勢在必行的，車輛路徑的優化是低碳物流最有效可行的措施之一。CVRP問題模型是最能體現現實生活中低碳物流的數學模型。某一物流運輸公司A，在當地只有一個配送中心0，需要向20 個客戶配送所需要的物品。已知配送中心有6輛車，車型都是相同的，車輛固定成本為100，容量為8，客戶之間的運輸成本與車輛行駛的路徑有關。表2所示為配送中心以及各客戶的坐標位置以及需求信息。

4.2 參數設置及結果分析

算法所在的實驗平臺為Window7、64 bit系統、32 GB內存。采用MATLAB 2017b進行環境仿真實驗。

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

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

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

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

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

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

路徑仿真測試結果如表3所示。為證明本文的改進算法的優越性，與其他文獻的結果作相應的對比。為顯示測試的公平性，與對比文獻均采用相同的數據信息，設置相同的參數，對比結果如下。

文獻[16]中采用改進蟻群算法對該問題進行求解，相同參數下求得最優路徑平均值為863. 44，單次最優為855. 68，優化效果一般，沒有達到最優結果。

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

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

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

表3 路徑仿真測試結果

5 結論

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

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