綠色車輛路徑問題研究

王璐瑤 楊巍 曹竹 汪弘 李雅婷

摘要：現在社會上對各類熱點問題格外重視，特別能源危機與環保問題，這兩個難題已經成為了焦點。而如今，世界經濟發展的態勢逐漸向較低的能耗，較低的排放量的增長模式趨近，而這個模式最終目標就是保護環境，使綠色可持續發展。。在日常生活中交通運輸業是造成環境問題的主要原因之一，并且隨著電子商務的發展，物流配送成為城市經濟發展和居民生活消費多樣化的重要支柱，其造成的城市污染問題已引起人們的高度關注。

針對該問題，首先我們選定沈陽市物流配送的28個站點進行研究，收集并整理其2018年的全部相關數據，之后采用多目標規劃模型，分各個站點進行分析，假設各個站點車輛有效利用臺數占各個站點的總運輸車輛臺數比值不變，分別設置車輛有效利用系數、碳排放量以及車輛運營效率等變量，先把目標和約束函數列出，之后會用到數學建模上的遺傳算法，以及運用MATLAB軟件對算法進行求解，并最終得到結論。

層次分析法則在遺傳算法后使用，對車輛路徑選擇上有直接影響的各個考量進行加權分析，量化評分其余的預選路徑因素。在實際情況中可根據決策者的需求對路徑進行評價排序，進而得到最佳車輛行駛路徑。

最后，我們根據研究得出結論，得到最優綠色車輛路徑。

一、問題背景

由于現在社會上對各類熱點問題格外重視，特別能源危機與環保問題，這兩個難題已經成為了焦點。而如今，世界經濟發展的態勢逐漸向低能耗，低排放的增長模式趨近，而這個模式最終目標就是保護環境，使綠色可持續發展。而交通運輸業是造成環境問題的其中的一個主要原因，并且電子的商務發展的如此迅速，物流配送成為城市經濟發展和居民生活消費多樣化的重要支柱，其造成的城市污染問題引起人們的高度關注。所以把經濟性當做目標的傳統車輛的路徑研究的問題已不能很好地應對這個趨勢，在降低經濟成本的同時如何保護環境已經成為車輛路徑優化需要考慮的重要因素，這就是所謂的綠色車輛路徑問題。

二、備選較優路徑——多目標規劃模型的建立

本文求解在確保車輛載重、容積、起點及終點和客戶服務要求的前提下，保證碳排放量呈下降趨勢以及車輛有效利用率提高到0.6以上的目標。這道題是多目標總體規劃問題，因此我們在這里，用到的是多目標規劃模型，來解決。

沈陽市2018年車輛有效利用率、碳排放量、總運輸車輛臺數以及車輛運營效率變量，列出目標和約束函數。而我們假設沈陽各個站點的車輛有效利用臺數占其總運輸車輛臺數比值、各個站點碳排放量占沈陽市總碳排放量的總比值不變，以及可通過查找數據得出。

根據MATLAB編制程序可求得2018年車輛有效利用系數、碳排放量、總運輸車輛以及車輛運營效率：

（1）形成相對較優綠色車輛路徑

由于模型中有多個目標，同時求解較為困難，所以運用禁忌搜索算法對這個進行求解，形成相對較優綠色車輛路徑。

（2）評價較優綠色車輛路徑

由于前面得到的相對較優綠色車輛路徑包括三個目標的各自較優路徑，對其進行評價。

求解方法：

對于上述綠色車輛路徑問題中所建立的多目標規劃模型，鑒于多目標約束下模型的求解方法比較復雜，因此我們采取禁忌搜索算法來求解考慮到油耗的單個車場多個車型的車輛路徑問題。

我們假定一個車場共有L種類型的車輛，設第 種類型車共有 輛（ 足夠大），每輛車的容量為 ，油耗費為 。該車場共為N個站點服務，其中第 個站點所需貨物重為 。配送車輛從站點裝上貨物出發為客戶送貨，要求每個客戶只由一輛車配送，車輛將貨物運送完畢后停留在最后的站點，每輛車的費用均為其油耗費，目標為使所有被派出的車輛的費用之和最小。

禁忌搜索算法：

（1）禁忌算法中解的表示：由于上述問題為多車型單車場問題，又本文用 MATLAB 實現該禁忌搜索算法，為了便于進行鄰域操作，所以采用車型代替車場，例如，假設一車場共有2種類型車輛，為10個站點配送貨物，用1，2表示車型，1--10表示10個站點，則1維元胞數組：{[4] ，[1，3，5，7]，[2，2，1，6]，[1，4，19]，[2，8]}表示該問題的一個解，該解中共有4條路徑，它們分別為：

（1）禁忌算法中鄰域操作：根據車型不同而導致啟動費用不同的特殊情況，用一些特殊的鄰域操作方法來減少車輛的剩余容量，從而減少車輛的使用數量，以達到減少目標函數的目的。隨機從 （其含義與改進的最近鄰算法中的 相同）中任取兩條路徑，再分別從兩條路徑中任取出兩個節點：

①若取出的兩個節點均為車型，則檢測是否有容量更加適合，若有則更換車型，若無則進入下一步操作。

②若取出兩節點中分別為車型和客戶點。則將客戶點插入在路徑車型之后，并將此點在原路徑中剔除，若仍然有客戶點存在，則將車型替換成容量與此路徑中總裝載量最近的車型，若無客戶點存在，則直接刪除此路徑。

③若取出的兩點均為客戶點，則將第二個客戶點插在第一個客戶點之后，并將此點在原徑中剔除，如果仍然有客戶點存在，則將車型替換成容量與此路徑中總裝載量最近的車型，若無客戶點存在，則直接刪除此路徑。

（3）計算禁忌算法中的評價值：為了擴大算法的搜索范圍，防止局部最優解的生成，在每次迭代中，本算法允許不可行解產生鄰居，但由于不可行解的違反目標約束的特點，對不可行解加以懲罰，設懲罰因子為 ，且令 若解x中總共有 條路不可行，設x對應的目標函數值為 ，則解x的評價值為 。

（4）禁忌對象及禁忌長度：將每次迭代得到的局部最好解（評價值最小）作為禁忌對象放入禁忌表中;取禁忌長度為一個常數，其值根據問題的規模來確定;將從當前解的鄰域中隨機選擇N個鄰居作為候選集合;采用迭代指定步數T的終止準則。

三、評價預選較好路徑——運用層次分析法確立層次分析模型

根據不同的實際情形，我們分析了各項原因，并對其進行了加權，這一步用到了層次分析法。為挑選出最佳車輛路徑，我們采取各項指標權重系數與實際數據相結合的評分制度，以此定量評價各備選路徑。

（一）建立影響車輛路徑選擇的指標體系

由上一模型的建立我們已知路徑選擇主要有成本、路程和污染三大目標，而各個目標又由多種指標決定，分別有總運輸車輛臺數、車輛有效利用率、行駛里程、行駛時間、耗油量、碳排放量六項指標。而這六項基準方便于根據執行者的需要明確權重。

（二）確定各項指標的權重并建立矩陣

運用層次分析法，簡稱為AHP，加權定量分析各項指標，這個指標是指可以決定路徑選擇的。

第一步先將指標構造一個成對比較陣，兩兩對比比較這個方案里面的所有因素，用成對比較矩陣A，B表示出所有的比較成果。

矩陣A、B是一致陣，權向量就是取對應于最大根的歸一化的向量表示對上層原因的權重。下一步將各層權重結果進行乘法和加法的運算，得到的結果就是各個目標的權重值。

（三）一致性檢驗

再接著下一步就是一致性檢驗，將一致性指標，這里簡稱為CI，隨機一致性指標，這里簡稱為RI，這兩個指標引入算法中。一致性比例是需要根據隨機一致性指標給定的數值表來計算的。 若CR均小于0.1，則通過一致性檢驗。

（四）計算各路徑得分

根據各權重計算各備選路徑得分并進行排名。

分數越高者，越滿足決策者的要求。

四、挑選最佳路徑——依據不同需求挑選

根據實際情況，依據不同決策者的需求，可以調整各指標的權重，以挑選出適合不同情況的最佳車輛路徑。

參考文獻：

[1] 唐修柏.財務風險跟蹤評價方法初探[J].科技視界，2016（01）：278.

[2] 陶大俊. 基于小波與層次分析法的電子銀行風險評價與研究[D].西安電子科技大學，2009.

[3] 趙志學，李夏苗，周鮮成.考慮擁堵區域的多車型綠色車輛路徑問題優化研究[J/OL].計算機應用：1-11[2019-11-21].

[4] 高飛. 不確定因素下配送路徑優化問題研究[D].北京交通大學，2019.

[5] 李英，李惠，成琪.基于文獻計量和知識圖譜的國際綠色車輛路徑問題研究發展分析[J].中國管理科學，2016，24（S1）：206-216.

[6] C.H.Lin，K.L.Choy，G.T.S.Ho，S.H.Chung，H.Y.Lam. Survey of green vehicle routing problem，past and future trends[J]. Expert Systems with Applications，2014，41：1118–1138.

[7] 陳玉光，陳志祥. 基于準時送貨和最小耗油的配送車輛路徑問題研究[J]. 中國管理科學，2015，23：156-164.

[8] 饒衛振，金淳，王新華等. 考慮道路坡度因素的低碳 VRP 問題模型與求解策略[J]. 系統工程理論與實踐，2014，34（8）：2092-2105.

[9] Kü?üko?lu，S. Ene，A. Aksoy et al. A memory structure adapted simulated annealing algorithm for a green vehicle routing problem[J]. Environmental Science & Pollution Research，2015，22 （5）：3279-3297.

[10] 葛顯龍，黃鈺，譚柏川. 基于油耗的帶時間窗變速車輛路徑問題研究[J]. 物流技術，2015，34（8）：127-149.

[11] 李進，張江華. 基于碳排放與速度優化的帶時間窗車輛路徑問題[J]. 系統工程理論與實踐，2014，34（12）：3063-3072.

[12] J. Zhang，Y. Zhao，W. Xue et al. Vehicle routing problem with fuel consumption and carbon emission [J]. International Journal of Production Economics，2015，170：234-242.

[13] 李進，傅培華，李修琳等.低碳環境下的車輛路徑問題及禁忌搜索算法研究[J].中國管理科學，2015，23（10）：98-106.

[14] 康凱，韓杰，馬艷芳等. 基于碳排放的模糊約定時間車輛路徑問題研究 [J]. 工業工程與管理，2017，22（4）：17-22.

[15] T. Bektas，G. Laporte. The Pollution-Routing Problem[J]. Transportation Research Part B，2011，45：1232-1250.

[16] R. Kramer，A. Subramanian，T. Vidal et al. A matheuristic approach for the Pollution-Routing Problem[J]. European Journal of Operational Research，2015，243 （2）：523-539 .

[17] 左秋玲，李景山.AHP-模糊數學模型在高層工業建筑火災風險評估中的應用[J].城市建筑，2017（11）：25-27.

[18] 肖曉偉，肖迪，林錦國，肖玉峰. 多目標優化問題的研究概述[J]. 計算機應用研究，2011，28（ 3）：805-808

[19] 潘斌斌.多目標路徑規劃問題的算法綜述[J].重慶工商大學學報（自然科學版），2012，29（05）：78-84.

[20] 滕立春. 電器連鎖零售企業的供應商評價研究[D].西北工業大學，2005.

（作者單位：沈陽師范大學）