考慮時變的綠色3L—CVRP問題研究

摘 要：本文研究速度變化對三維裝箱車輛路徑問題的影響，并且考慮車輛路徑中的能源消耗，建立了一個考慮變速的綠色3L-CVRP模型，提出了求解該問題的禁忌搜索和局部搜索相結合的算法。

關鍵詞：三維裝箱 變速 禁忌搜索 局部搜索

一、引言

進入新世紀以來，物流引起的環境污染問題越來越引起人們的重視。節約能耗費用、減少排污相關稅費以成為企業控制物流成本的重要環節。在我國，隨著工業化進程的加快，由于運輸導致的溫室氣體問題也日趨嚴重。而在車輛實際行駛過程中，由于各種因素的影響，車輛的行駛速度也是時變的，從而導致了車輛的運營成本也跟著發生變化。而車輛行駛速度對于旅行時間和碳排放的影響也是非常直接的，所以研究時變的綠色3L-CVRP問題具有很強的理論和現實意義。

二、模型建立

1.問題描述。考慮時變的綠色3L-CVRP問題可描述為：配送中心派幾輛車為客戶服務，車輛從配送中心出發，送完貨后都要回到配送中心，目標是在考慮速度變化，道路，載重，運行距離和三維裝箱的情形下，找出滿足全部客戶需求的總油耗最小的路線安排。約束如下：

1.1車輛路徑約束：車輛從配送中心出發，必須返回配送中心，每個客戶都被訪問到且只被一輛車訪問一次，使用車輛不能超過配送中心的車輛數。

1.2三維裝箱約束：物體必須正交放進車廂且只能以底面做90度旋轉的擺放，必須滿足后進先出原則，物體不能有重疊，易碎品上方不能放非易碎品，物體與其下面接觸物體的接觸面積必須滿足一定的閾值，即假設接觸面積設為A，設該物體的底面積為A，則必須滿足A>α*A。

2.能耗計算。車輛從客戶 i到客戶j 的單位燃油行駛距離表達式為：

其中α0、α1為正常數；v 表示車輛的平均速度；γij為道路的坡度系數；πij為負載系數，表達式為：

其中β0、β1為正常數；為車輛從客戶i到客戶 j 的載重量，為車輛長期運營下的平均載重量。

本文把速度區間化，假設分M個區間，第z個速度時間區間的范圍是，設車輛離開i時的速度介于第τ個速度時間區間內，跨越p個區間，則車輛離開i的速度可以記為，則車輛在路段內的速度可以按其跨越的時間區間表示為集合，則考慮時變的弧產生的總油耗計算如下：

3.模型構建。目標函數：

其中：；a為 配送中心所擁有的車輛數，xijk：表示車輛k訪問弧的次數，xijk={0，1}。

約束條件：（1）使用車輛數不能超過配送中心擁有的車輛數；（2）每個客戶都有被服務且只能被一輛車服務一次；（3）裝載的貨物必須滿足車輛的體積和載重約束；（4）貨物只能以底面做90度旋轉；（5）非易碎品不能放易碎品上方；（6）支持面積必須滿足一定的閾值；（7）貨物不能有重疊；（8）必須滿足后進先出原則。

三、算法求解

本文采用禁忌搜索與局部搜索相結合的方法求解3L-CVRP。整個算法分為兩個層次：外層用禁忌搜索求解每輛車的客戶分配和行使路徑，內層調用局部搜索算法判斷每輛車的裝箱可行性以及求解裝箱方案，并把結果返回給TS算法，TS算法對此路徑進行調整，以尋找更好的路徑方案。

1.局部搜索算法。為使每個物體在車廂中尋找到合適的位置，本文選擇了基于最深位置填充法和最大接觸面積填充算法的局部搜索算法求解三維裝箱問題。其中裝箱的初始解是按照物體先進后出和最大體積優先的原則生成的，然后隨機選擇兩個位置進行交換生成新解，當算法迭代次數達到一定閾值或成功裝箱，則算法結束。

2.禁忌搜索算法。本文按照文獻[3]提出的改進二維掃描算法生成初始解；使用1-swap，2-opt，3-opt三種鄰域結構生成領域解，使用狀態本身的變化作為禁忌對象。

四、實驗結果分析

本文的算法是以MATLAB語言編寫的，使用的算例是基于3L-CVRP的測試算例，本文最后的結果不但給出了路徑結果，同時也給出了裝箱方案。為了驗證算法的有效性，本文以E16-03算例為例，對比考慮能耗和不考慮能耗兩種方案的差別。

1.基于3L-CVRP的仿真實驗。求解基于3L-CVRP的仿真實驗的最優距離是300.47。其中車輛1的路徑是12-4-13。車輛2的路徑是：2-3-8-1。車輛3的路徑是：11-9-10-15-5。車輛4的路徑是：7-6-14。

2.基于時變的綠色3L-CVRP的仿真實驗。求解基于時變的綠色3L-CVRP的仿 真實驗的最優能耗是55.65，行駛距離是334.6507。其中車輛1的路徑是：6-8-3-1。車輛2的路徑是：13-14-7。車輛3的路徑是：12-5-9-11。車輛4的路徑是：2-10-15-4。

經過計算顯示以能耗為目標和以最優距離為目標的結果是完全不同的，企業以后不能僅僅考慮行駛距離，也要把能耗考慮進去。

參考文獻：

[1]Gendreau M，Iori M ，Laporte G， et al. A tabu search algorithm for a routing and container loading problem[J].Transportation Science， 2006， 40（3）：342-350.

[2]彭碧濤.三維裝載約束下車輛路徑問題研究：[博士學位論文].廣州：華南理工大學，2013.

[3]楊培穎.低碳型機車接送服務的改進二維碼掃描算法[J].東北大學學報，2013（4）：478-481.

[4]周慧，周良.多目標動態車輛路徑問題建模及優化[J].計算機科學，2015，42（6）：204-209.