仝凌云 王琳

摘要 為了解決以低油耗為優(yōu)化目標的具有固定車輛數的多車型車輛路徑問題，從低碳環(huán)保角度出發(fā)，建立以固定發(fā)車費用和油耗費用為優(yōu)化目標的數學模型，并提出了一種融合鄰域搜索算法的混合模擬退火算法，解決了傳統(tǒng)模擬退火算法全局搜索能力差的缺點。模型中的油耗費用考慮了車輛車載率和行駛里程，算法中客戶采用自然數編碼方式，首先采用前向插入算法產生初始解；然后在解變換過程中融合了3種鄰域搜索算子即互換、逆轉、插入操作生成新解；最后通過實例對算法性能進行測試。通過與其他算法的計算結果對比驗證了模型的實用性與算法的有效性。

關 鍵 詞 車輛路徑問題；多車型；低油耗；模擬退火算法；鄰域搜索算法

中圖分類號 TP301.6 文獻標志碼 A

0 引言

2015年4月環(huán)保部發(fā)布的源解析結果表明機動車已成為天津市第二大氣污染來源[1]；世界經濟合作組織（Organization for Economic Co-operation and Development， OECD）在 2003 年《配送：21 世紀城市貨運的挑戰(zhàn)》報告中指出：貨車對美國、日本等國家主要城市造成的城市污染占總量的40%～60%，但貨物運輸僅占城市交通總量的10%～15%；2014 年我國快遞業(yè)務量達到 140 億件，同比增長52%[2]。因此，本文在研究城市配送車輛路徑規(guī)劃問題時改變傳統(tǒng)的對車輛行駛距離最短的研究，而使用車輛的油耗費用和固定費用作為優(yōu)化目標，希望可以實現降低能源消耗和減少空氣污染的目標。

自1959年Dantzig和Ramser初次研究車輛路徑問題（VRP）[3]，多年來，學者們對VRP的多種變形問題進行了研究，研究結果大多集中在單車型的研究[4-6]。然而在生活中運輸公司有多種車型，且車輛數一定。因而研究具有固定車輛數的多車型VRP（Heterogeneous Fixed Fleet Vehicle Routing Problem， HFFVRP）更貼近現實情形。目前，對于HFFVRP的研究成果比較少，馬建華等[7]用變異蟻群算法實現了以最快完成作為最優(yōu)目標的多車場多車型VRP；潘雯雯等[8] 建立需求可拆分的多車型車輛路徑問題混合整數規(guī)劃模型，并以路徑優(yōu)化和路徑改進相結合的兩階段算法求解；Subramanian 等[9]提出自適應記憶規(guī)劃求解多車型VRP；Taillard[10]提出了一種列產生啟發(fā)式算法求解具有固定車輛數的多車型車輛路徑問題。

這些文獻雖然比單車型更符合實際，但是在研究中僅僅以旅行最短時間或者最短距離為最優(yōu)化目標，欠缺考慮車輛調度對油耗的影響，可能會給物流企業(yè)造成財產損失，也不符合國內節(jié)能減排的大趨勢。

一些學者意識到車輛運輸對環(huán)境的影響[11]，開始把目標轉向以最小油耗、最少碳排放為目標的車輛路徑問題。葛顯龍等[12]構建了以車輛固定費用和油耗費用最小為優(yōu)化目標的數學模型，并用量子遺傳算法求解；李進等[13]運用禁忌搜索算法求解了以油耗和碳排放費用為最小的車輛路徑問題，并證實求解結果相比以往的車輛調度更加經濟與環(huán)保；李長征等[14] 建立了碳排量最小的車輛路徑優(yōu)化模型，并用改進的遺傳算法求解，取得了較好的結果；Abdullah-Konak等[15] 開發(fā)了一個精確的動態(tài)規(guī)劃算法來確定碳排放最少的車輛路徑。

綜合分析現有文獻在研究問題方面有以下不足之處：1）配送中心大多由混合車輛組成，不同的車輛類型其車輛固定成本和油耗必定不同，但目前大多研究僅考慮單一車型；2）計算油耗時忽略了車輛載重對油耗的影響。

隨著HFFVRP的研究成果不斷增長，其求解方法也層出不窮。作為典型的NP-hard難題，目前大多數研究者把精力放在怎樣構造高質量的求解算法上，如遺傳算法[16]、蟻群算法[17]、分支定界算法[18-20]及禁忌搜索算法[21]等，且均取得了一些較好的效果。其中模擬退火算法（Simulated Annealing，SA）思想最早是由Metropolis等提出的，因為同時具備較強的魯棒性、隱含并行性及通用性[22]等優(yōu)點深受研究者的青睞。錢曉明等[23] 采用禁忌搜索中的禁忌表對模擬退火算法進行改進；Atiye Ghorbani等[24]將帝國主義競爭算法與模擬退火算法結合求解車輛路徑問題。王超等[25]設計的并行模擬退火算法用于求解同時送取貨和帶時間窗的車輛路徑問題，求解30個大規(guī)模算例的結果可以作為該類問題的新基準；Yu等[26]在傳統(tǒng)模擬退火算法基礎上融合3種局部搜索算法用來求解選址-路徑問題。盡管如此，模擬退火算法仍然有求解問題規(guī)模有限、算法運行時間長等缺點，所以本文對算法做進一步改進，在算法解變換產生新解的過程中融合了3種鄰域搜索算法（交叉、變異、逆轉操作），增加了算法中解的多樣性，加快收斂。

本文研究配送中心采用固定車輛數的多種車型，以車輛使用的油耗費用和固定費用之和最小為目標的車輛路徑問題。為了解決上述車輛路徑問題，本文首先引入了油耗的計算方法，構建了以油耗和固定發(fā)車費用之和為優(yōu)化目標的數學模型；而后設計了融合3種鄰域搜索算法的混合模擬退火算法求解該問題；最后通過與禁忌搜索算法、遺傳算法和量子遺傳算法對比驗證本算法的有效性和可行性。

1 問題描述

本文研究了單一配送中心調派多種車型的車輛對若干個客戶派送商品，每一個顧客的位置和商品需求量已知，每一次派送都需要從配送中心發(fā)車，完工后返回配送中心。目標是在油耗及車輛固定費用的情況下，找出滿足客戶貨物需求的總運輸費用最小的路徑安排。配送過程中，采用具有車輛數限制的最優(yōu)的車輛類型。約束為：所有車輛在行駛過程中不能超載；每一個顧客都被服務且只能被一輛車服務一次；配送中心有多種車型且每種車型數量有限。

符號與決策變量為：1）[G=V，A]為配送網絡；2）[V]為節(jié)點集，[V=0，1，2，…， N]，其中0表示配送中心，[1，2，…，N]表示客戶；3）[A]為弧集，[A=][（i，j）|i，j∈V，i≠j]；4）[dij]為弧[i，j]的距離；5）[M]表示配送中心的車輛類型數，以[m][m∈M]表示具體車輛類型；6）[Qm]為車型[m]的容量，[m=1， 2， …， M] ；7）[nm]為車型[m]的數量；8）[Fkm]為車型[m]、車輛[k]發(fā)車的固定成本，[k∈（1，nm）]；9）[pmijk]表示車型為[m]的車輛[k]在段弧[（i，j）]上車輛的實載率；10）[qmijk]表示車型為[m]的車輛[k]在段弧[（i，j）]上車輛的裝載量；11）[qi]為節(jié)點[i]的需求量；12）[xmijk]為0或1變量，[xmijk=1]表示車型為[m]的車輛[k]經過弧[（i，j）]，否則為0。

2 模型建立

2.1 車輛油耗的計算

影響車輛油耗的因素十分復雜，一般將影響因素分為3大類：車輛因素、環(huán)境因素、人為因素[27]，具體因素如表1 所示。本文研究的是多車型車輛路徑問題，側重不同車型的載重對油耗的影響。油耗可以通過車輛實載率和行駛里程求得。車輛的碳排放量與油耗量成正比，耗油量大的車輛通常排放更多的碳，通常1 L燃油（汽油）會產生2.32 kg的CO2[28]。實載率[pmijk]有效反映車輛在運輸過程中是否被有效利用，主要考慮車輛的容量與在弧[（i，j）]上的裝載量兩個方面，第[m]種車型車輛[k]在弧[（i，j）]的實載率為：[pmijk=qmijkQm]。假設車輛的油耗正比于運輸量，[em1]是[m]車型空載時的單位距離油耗成本，[em2]是滿載時的油耗成本，弧[（i，j）]運輸距離中第[m]種車型車輛[k]油耗成本為：[emijk=em1+pmijkem2-em1]，若運輸距離為[dij]，則該車在弧[（i，j）]上運輸的總油耗成本為：[Cmijk=dijem1+pmijkem2-em1][12]。

2.2 模型

本文研究的問題為具有固定車輛數的多種車型，每種車型具有不同的油耗費用和固定費用。因此在優(yōu)化整個配送網絡時，還需要選擇具有車輛數限制的合適的車輛類型，以盡可能減少油耗和車輛的固定費用之和。低油耗多車型車輛路徑問題模型為

[minz=m=1Mk=1nmi=0Nj=0Ndijxmijkem1+pmijkem2-em1+ m=1Mk=1nmj=0NFmkxm0jk ]， （1）

[s.t.]

[pmijk=（j=0Nqjxmijk-i=1j-1qixmijk）Qm ?i， j]， （2）

[j=1Nk=1nmxm0jk=i=1Nk=1nmxmj0k ?i，j，k，m]， （3）

[j=0Nk=1nmm=1Mxmijk=1 ?j，k，m] ， （4）

[i=0Nk=1nmm=1Mxmijk=1 ?i，k，m]， （5）

[i=1Nqij=0Nxmijk≤Qm ?i，j，k，m] ， （6）

[j=1Nk=1nmxm0jk≤nm ?m]， （7）

[xmijk=0，1 ?i，j，k，m]。 （8）

式（1）為目標函數，表示總費用之和最小，包括油耗費用和固定發(fā)車費用；式（2）表示車型為[m]的車輛[k]在客戶[i]到客戶[j]的實載率；式（3）表示每輛車的配送線路的起點和終點都必須是配送點；式（4）～式（5）表示每個客戶都被訪問并且保證客戶僅被一輛車訪問一次；式（6）為每輛車的裝載能力約束；式（7）為每種車型的車輛數限制；式（8）為決策變量約束。

3 設計求解算法

模擬退火算法是在初始階段設置某一初溫和降溫速率。隨著溫度參數的持續(xù)下降，結合Metropolis抽樣過程在解空間隨機尋找目標函數全局最優(yōu)解的一種智能優(yōu)化算法。其物理退火過程和相應的算法操作與之對應：1）加溫過程與算法的設置初溫對應；2）等溫過程與算法的Metropolis抽樣過程對應；3）冷卻過程與控制參數的降低對應。但基本的模擬退火算法在求解大規(guī)模問題的最優(yōu)解時運行的時間難以承受。為避免基本模擬退火算法的缺點，本文設計了一種新的混合算法，在模擬退火算法解變換過程中融合了3種鄰域搜索算法。鄰域搜索算法擴展了當前解的搜索空間，減小了算法陷入局部最優(yōu)的可能性，提高了算法的穩(wěn)定性，使得算法能夠在較短的時間內求得問題的最優(yōu)解。下面將分別介紹混合模擬退火算法的實現過程。

3.1 編碼

采用自然數編碼方式，車輛數[k]已知，配送站用0表示；客戶由（1，2，…，[i]，…，[n]）表示。多車型VRP解的編碼形式為（0，[i11]，[i12] ，…，[i1s]，0，[i21]，[i22] ，…，[i2t]，0，[ik1]，[ik2] ，…，[ikn]，0）。例如編碼（0，1，2，3，0，4，5，0，6，7，8，0，9，10，0）是指由4輛車完成進行10個客戶貨物配送的路徑安排，4條路徑分別如下。

路徑1：配送站→1→2→3→配送站；

路徑 2：配送站→4→5→配送站；

路徑 3：配送站→6→7→8→配送站；

路徑4：配送站→9→10→配送站。

3.2 改進的模擬退火算法的實現

3.2.1 求初始解

首先設置控制參數：降溫速率[q]、初始溫度[T0]、結束溫度[Tend]和確定每個[T]時內的迭代次數即鏈長[L]，本文采用多車型前向插入算法[29]生成初始解。具體步驟如下：

步驟1 構造一條從配送中心發(fā)車并返回配送中心的初始空路徑，對當前路徑，選擇未被分配路徑的顧客插入到空路徑中，優(yōu)先考慮距離配送中心最遠的且未分配路徑的顧客作為潛在顧客并試探插入當前路徑；

步驟2 在路徑中隨機選擇滿足車輛容量約束插入點插入；

步驟3 重復步驟2直到當前路徑的配送需求超過車輛的配送能力為止；

步驟4 重復步驟1～3直到所有客戶都被插入到路徑中為止，此時形成一條新路徑。

根據文獻[13]的結論，小車型（6 t）比大車型（16 t）油耗低，所以在車型的選擇上除了滿足裝載約束，要優(yōu)先考慮使用小車型。

3.2.2 鄰域搜索算法產生新解

為增強算法的搜索能力，本算法采用混合鄰域結構，即隨機互換、逆轉、插入操作對初始解進行鄰域搜索。3種操作分別標號為1、2、3，在[1，3]中隨機產生整數[α]，則對當前最優(yōu)解進行操作[α]。下面將簡要介紹這些鄰域搜索算法。

1）互換操作?；Q操作首先隨機選擇當前路徑中的任意兩個客戶點，然后交換這兩個客戶點的位置，最后要檢測通過互換操作得到的新路徑是否滿足車輛載重等約束條件，如果滿足則新路徑產生?；Q操作通過改變同一條路徑或者不同路徑中兩個不同客戶的位置來降低總費用。具體互換過程如圖1所示。

2）逆轉操作。逆轉操作即2-opt操作，該方法首先通過選擇操作選出一條路徑中任意兩個客戶點，然后通過將兩客戶間所有客戶的排列順序逆轉來減少路徑總成本。每接受一次2-opt操作，都要根據約束條件重新安排車輛，將新的路徑成本與當前最優(yōu)值比較，假如該路徑的成本減少，則改進的路徑被保留；否則，保留當前最優(yōu)值。具體逆轉過程如圖2所示。

3）插入操作。插入操作首先通過選擇操作選擇一條路徑中任意兩個客戶點，然后將某一客戶點插入到另一客戶點后由此產生新路徑。這種插入操作可以很好的避免算法早熟的現象，保證最優(yōu)路徑可以迭代到下一次，同時可以使算法更快的向最優(yōu)解收斂，防止算法陷入局部最優(yōu)。具體插入過程如圖3所示。

3.2.3 解的評價

解的評價關鍵是懲罰不可行的解。如果某條路徑中配送總量超過車輛裝載能力[Q]，則該路徑方案不可行。該算法設計為暫時不可行解，可行解中夾雜不可行解，以便通過不可行解的過渡，對鄰域空間進行充分搜索，找到更優(yōu)的可行解，避免過早陷入局部最優(yōu)。首先計算[Xnew]中每輛車的實際裝載量[Cu]；然后判斷車輛是否超載，[Cv=max（CuQ -1，0）]，若[Cv]非零則車輛超載，并求出[Cv]的平均值[Cvmean]；最后將[βCvmean]與目標函數式（1）一起求最小，其中[β]為懲罰因子。

3.2.4 Metropolis準則

若運輸總成本函數為[zX]，則當前解的運輸總成本為[zX1]，新解的運輸總成本為[zXnew]，總成本之差[dz=zX1-zXnew]，則Metropolis準則為

[P=1 ， dz<0 ，exp（-dzT） ， dz≥0 。] （9）

如果[dz<0]，則以概率1接受新的路徑；否則以概率[exp（-dz/T）]接受新的路徑。

3.2.5 降溫

利用降溫速率[q]進行降溫，即[T=qT]，若[T

改進的模擬退火算法的流程圖如圖4所示。

4 仿真

4.1 測試問題

為了驗證構建模型和設計的改進的模擬退火算法對于求解多車型車輛調度問題的有效性，本文對文獻[12]的算例進行求解。所用車輛車型分別為6 t、8 t、16 t，每種車型有4輛，相關數據如表2所示[12]。

算例規(guī)模為30個客戶，所有車型車輛不受行駛距離和行駛時間的限制。配送中心坐標為（41 km，70 km），客戶的信息見表3。要求合理安排配送車輛的配送路線，使完成配送任務的總運輸費用最少。

4.2 參數設置

本文的模擬退火算法參數設置如下：降溫速率[q=0.95]、初始溫度[T0=1 000]、結束溫度[Tend=10]以及確定每個[T]時的迭代次數即鏈長[L=500]。算法是基于MATLAB R2017a 軟件編程實現的，電腦的配置為內存4 GB，Windows10專業(yè)版操作系統(tǒng)，處理器Intel（R）Core（TM）i5-3337U CPU @ 1.80 GHz。

4.3 算法比較

改進的模擬退火算法與遺傳算法[30]、禁忌搜索算法[30]和量子遺傳算法[12]進行對比分析。從油耗、距離、運行時間等方面進行對比，結果如表4所示。

表4對比了4種不同算法的優(yōu)化結果和計算時間。表5為本文算法以費用為最優(yōu)目標的車輛路線，圖5為相應的路徑圖和迭代圖。由表4可以看出，本文算法的油耗費用優(yōu)于其他算法，能夠顯著提高解的質量。運輸距離雖然比量子遺傳算法增加52.05 km，但是油耗費用減少了13.4%。由圖5可以看出算法基本能在450代以內找到問題的最優(yōu)解，將算法最高迭代次數設置為600代，運行時間為99.42 s，運行時間比遺傳算法、禁忌搜索算法和量子遺傳算法分別減少了57.15%、50.25%、36.89% ，表明本文算法在提高解質量的同時也大大提高了算法的求解效率。以上分析說明了本文算法在求解多車型以配送總費用最小為優(yōu)化目標的車輛路徑問題是有效的。

5 總結

研究低油耗的固定車輛數的多車型車輛路徑問題可以幫助企業(yè)找到適合自身需求的車輛調度，有助于其總成本和碳排放的下降，同時也符合我國建設資源節(jié)約型、環(huán)境友好型社會的目標。本文模型考慮了車輛的實載率和運輸距離與油耗之間的關系，在此基礎上，建立了以固定發(fā)車費用和油耗費用為優(yōu)化目標的數學模型。由于該模型是NP-hard問題，改進了模擬退火算法對模型進行求解，算法使用前向插入啟發(fā)式算法生成初始解，在解變換產生新解的過程中融合了交叉、變異、逆轉操作3種鄰域搜索算法。通過相關實例的應用和對比，表明本文提出的算法在提高解質量的同時也大大提高了算法的求解效率，從而指導物流企業(yè)如何合理安排不同型號載運車輛。

參考文獻：

[1] 郭薇. 全國環(huán)境監(jiān)測工作會議召開[J]. 中國環(huán)境報，2014，4（1）：11-20.

[2] 俞明健. 城市貨運交通問題與城市地下物流[J]. 交通與運輸，2017，33（3）：1-3.

[3] DANTAIG G B，RAMSER J H. The truck dispatching problem[J]. Institute of Management Sciences，1959，6（1）：80-91.

[4] NAZIF H，LEE L S. Optimised crossover genetic algorithm for capacitated vehicle routing problem[J]. Applied Mathematical Modelling，2012，36（5）：2110-2117.

[5] MORETTI B R，AMAEAL A V，Arne L. Adaptive granular local search heuristic for a dynamic vehicle routing problem[J]. Computers and Operations Research，2009，36（11）：2955-2968.

[6] MüLLER J. Approximative solutions to the bicriterion vehicle routing problem with time windows[J]. European Journal of Operational Research，2010，202（1）：223-231.

[7] 馬建華，房勇，袁杰. 多車場多車型最快完成車輛路徑問題的變異蟻群算法[J]. 系統(tǒng)工程理論與實踐，2011，31（8）：1508-1516.

[8] 潘雯雯，郭海湘，周光勇，等. 基于兩階段算法的需求可拆分多車型車輛路徑問題[J]. 中國管理科學，2016，24（S1）：55-61.

[9] SUBRAMANIANA，PENNAP H V，UCHOA E，et al. A hybrid algorithm for the heterogeneous fleet vehicle routing problem[J]. European Journal of Operational Research，2012，221（2）：285-295.

[10] TAILLARDE D . A heuristic column generation method for the heterogeneous fleet VRP [J]. Operations Research，1999，33（1）：1-14.

[11] DEKKER R，BLOEMHOF J，Mallidis I. Operations research for green logistics-An overview of aspects，issues，contributions and challenges [J]. European Journal of Operational Research，2012，219（3）：671-679.

[12] 葛顯龍，許茂增，王偉鑫. 多車型車輛路徑問題的量子遺傳算法研究[J]. 中國管理科學，2013，21（1）：125-133.

[13] 李進，傅培華. 具有固定車輛數的多車型低碳路徑問題及算法[J]. 計算機集成制造系統(tǒng)，2013，19（6）：1351-1362.

[14] 朱長征，李艷玲. 碳排量最小的車輛路徑優(yōu)化問題研究[J]. 計算機工程與應用，2013，49（22）：15-18.

[15] XIAOY Y，KONAK A. A genetic algorithm with exact dynamic programming for the green vehicle routing & scheduling problem[J]. Journal of Cleaner Production，2017，167：1450-1463.

[16] 葛顯龍，許茂增，王偉鑫. 多車型車輛路徑問題的量子遺傳算法研究[J]. 中國管理科學，2013，21（1）：125-133.

[17] 郭海湘，潘雯雯，周欣然，等. 基于單車場多車型車輛路徑問題的混合求解算法[J]. 系統(tǒng)管理學報，2017，26（5）：824-834.

[18] CHENG C，YANG P，QI M Y，et al. Modeling a green inventory routing problem with a heterogeneous fleet[J]. Transportation Research Part E：Logistics and Transportation Review，2017，97：97-112.

[19] 揭婉晨，楊珺，楊超，等. 多車型電動汽車車輛路徑問題的分支定價算法研究[J]. 系統(tǒng)工程理論與實踐，2016，36（7）：1795-1805.

[20] PESSOAX A，SADYKOV R，UCHOA E. Enhanced Branch-Cut-and-Price algorithm for heterogeneous fleet vehicle routing problems[J]. European Journal of Operational Research，2018，270（2）：530-543.

[21] BRANDAO J. A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem[J]. Computers & Operations Research，2011，38（1）：140-151.

[22] 史峰. MATLAB智能算法30個案例分析[M]. 北京：北京航空航天大學出版社，2011：178-187.

[23] 錢曉明，孫穎，劉建，等. 基于混合模擬退火算法求解電表配送車輛路徑問題[J]. 計算機集成制造系統(tǒng)，2017，23（11）：2553-2560.

[24] GHORBANI A，AKBARI JOKAR M R. A hybrid imperialist competitive-simulated annealing algorithm for a multisource multi-product location-routing-inventory problem[J]. Computers & Industrial Engineering，2016，101：116-127.

[25] WANG C，MU D，ZHAO F，et al. A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows[J]. Computers and Industrial Engineering，2015，83：111-122.

[26] YU V F，LIN S W，LEE W，et al. A simulated annealing heuristic for the capacitated location routing problem[J]. Computers and Industrial Engineering，2010，58（2）：288-299.

[27] DEMIR E，BEKTAS T，LAPORTE G. A review of recent research on green road freight transportation[J]. European Journal of Operational Research，2014，237（3）：775-793.

[28] COE E. Average carbon dioxide emissions resulting from gas-oline and diesel fuel[R]. Seattle，Wash，USA：United States Environmental Protection Agency，2005.

[29] 穆東，王超，王勝春，等. 基于并行模擬退火算法求解時間依賴型車輛路徑問題[J]. 計算機集成制造系統(tǒng)，2015，21（6）：1626-1636.

[30] 邢文訓，謝金星. 現代優(yōu)化計算方法[M]. 北京：清華大學出版社，2009：101-120.

[責任編輯 田 豐]