基于環(huán)境成本與經濟成本兼顧視角的GVRPTW-MDHV 研究

王 莉，趙志學 WANG Li，ZHAO Zhixue

（1.湖南工商大學 智能工程與智能制造學院，湖南 長沙 410205；2.湖南工商大學 計算機學院，湖南 長沙 410205）

0 引 言

近年來，綠色車輛路徑問題（Green Vehicle Routing Problem，GVRP）的研究因其對環(huán)境和社會的影響而受到了越來越多的關注[1]。國際能源署（IEA）發(fā)布的報告顯示，交通運輸行業(yè)為全球第二大碳排放部門，碳排量占比為25%，而交通運輸領域碳的排放重點源于公路運輸，其產生的碳排放在交通運輸領域中占比高達85%。因此，研究綠色物流運輸具有非常重要的理論和現實意義。

關于多車場綠色車輛路徑問題（Multi-depot Green Vehicle Routing Problem,MDGVRP），國內外學者分別進行了在閉環(huán)路徑和開環(huán)路徑兩種情形下的研究。針對閉環(huán)路徑，周鮮成等[2]采用K-means聚類方法將顧客分配給不同的車場，然后以總成本最小化作為優(yōu)化目標進行建模；胡蓉等[3]提出了一種融合蟻群優(yōu)化算法與知識模型的學習型蟻群優(yōu)化算法進行求解。針對開環(huán)路徑，王順等[4]構建了響應型接駁公交多換乘站多車場地協同運行車輛路徑與調度協調的二階段模型，設計了多染色體遺傳算法。這些文獻分別采用K-means方法和智能算法對多車場與顧客點進行匹配分析，為本文的研究提供了一定的借鑒。

關于多車型綠色車輛路徑問題（Heterogeneous Green Vehicle Routing Problem,HGVRP），國內外學者也進行了相關的研究。以油耗最小化為優(yōu)化目標之一，何小年等[5]運用禁忌搜索算法進行模型求解。以碳排放最小化為優(yōu)化目標，路世昌等[6]設計了兩階段啟發(fā)式算法進行求解。以油耗碳排放成本最小化為優(yōu)化目標，趙志學等[7]設計了一種融合模擬退火算法的混合差分進化算法對問題進行求解。從以上文獻可以看出，HGVRP通常與客戶點的服務時間窗和車輛容量約束相關聯，在求解該類問題時大多采用啟發(fā)式算法。

綜上所述，國內外學者們從不同的角度對GVRP進行了探索，并形成了日益豐富的研究成果，但仍存在以下兩方面需要進行深入研究：第一，考慮了GVRP中的環(huán)境效益和經濟效益，但較少考慮多車場、多車型等約束條件，而這些約束條件卻是實際物流配送中真實存在的；第二，研究MDGVRP和HGVRP的成果較多，但研究MDHGVRP的文獻較少。針對上述問題，本文以車輛油耗成本、碳排放成本、固定發(fā)車成本、車輛租用費用、車輛人力成本和時間窗懲罰成本之和為目標函數，構建GVRPTW-MDHV模型，并設計一種改進差分進化算法進行求解，以期為物流企業(yè)實現低碳運輸、降低能耗、減少環(huán)境污染提供理論參考。

1 問題與模型

1.1 問題描述

本文研究的問題可描述為：多個無容量約束的車場位置已知，擁有多種型號的車輛；顧客的數量、位置、需求量、時間窗和服務時間均已知；多種型號的車輛容量已知；以滿足顧客需求的目標為前提，通過規(guī)劃最優(yōu)車輛路徑，使車輛油耗成本、碳排放成本、固定發(fā)車成本、車輛租用費用、車輛人力成本和車輛早到或晚到的懲罰成本等構成的總成本最小。

為便于分析和研究，現做出如下假設：每個車場中配備多種型號的車輛數有限，且車輛容量有限；車輛均在0時刻從車場出發(fā)，完成配送任務后返回原車場，且行駛速度恒定；同一車輛可配送多個顧客點，但每個顧客點只允許配送一次；每個客戶的需求量不得超過車輛最大容量；配送車輛只在行駛時間內產生油耗和碳排放，且油耗量和碳排放量與時間成正比；顧客的服務時間窗為軟時間窗，當配送車輛不在其硬時間窗內服務時，需支付一定的懲罰費用；考慮的時間為車輛行駛時間、服務時間和等待時間，物資裝卸載時間不予考慮。

1.2 符號與變量定義

G=（V1，V2，A）為配送網絡。V1為客戶點集合，V2為車場集合，A為連接頂點的弧集，A={（i，j）|i，j∈A，i≠j}，dij為路段Aij的距離?？蛻簟④噲?、車輛、油耗、成本等相關變量以及決策變量的含義如表1所示。

表1 客戶點相關變量說明

1.3 GVRPTW-MDHV 模型的構建

以車輛油耗成本、碳排放成本、固定發(fā)車成本、車輛租用費用、車輛人力成本和時間窗懲罰成本之和為目標函數，構建GVRPTW-MDHV模型，如下式所示：

其中：

式（1）表示配送總成本最小化，其中，C1表示車輛油耗成本；C2表示碳排放成本；C3表示固定發(fā)車成本；C4表示車輛租用費用；C5表示車輛人力成本；C6表示車輛早到或晚到的懲罰成本。式（2）表示車輛從車場出發(fā)，完成貨物配送之后返回原車場；式（3）表示每個顧客有且僅有一輛車為其服務；式（4）表示進入客戶點服務的車輛必須離開客戶點；式（5）表示顧客時間窗約束；式（6）表示車場中每種類型的車輛數約束；式（7）表示車輛容量約束；式（8）表示變量的取值約束。

1.4 基于速度和載重的油耗與碳排放量計算

根據油耗計算的相關理論，油耗會受到多種因素的影響，其中速度和載重是影響油耗的兩個最重要的因素。本文采用綜合模式排放模型（CMEM）計算車輛行駛過程中的油耗，該模型考慮多種因素對油耗和碳排放的影響，如車重、速度、加速度、坡度以及發(fā)動機排氣量等車輛特征參數，由發(fā)動機功率模塊、速度模塊和重量模塊三個模塊構成。根據CMEM模型，得到車場r中車型為s的第k輛車在路段（i，j）上產生的油耗量為：

FE=2.621 kg/L，為燃油排放參數。

2 改進差分進化算法設計

基本的差分進化算法雖然對目標函數的要求較低但容易陷入局部最優(yōu)，而遺傳算法通過模擬遺傳過程，引導搜索過程朝更優(yōu)解方向移動，因此本文結合以上兩種算法的優(yōu)點，將遺傳算法引入基本差分進化算法的選擇、交叉和變異操作中，形成改進差分進化算法（IDEA），從而對GVRPTW-MDHV模型進行求解。

2.1 染色體的編碼與解碼

本算法的染色體采用實數編碼方式，長度為需要配送的顧客點總數。實數的整數部分表示顧客點服務的車輛編號，小數部分用來排序，其排序結果為車輛的配送路線。例如，某染色體為{1.17，2.31，2.56}，表示一個可行解，該染色體中包含3個實數，代表需要配送的顧客點總數為3；每個實數構成一個基因，基因在染色體中的序號對應顧客點序號，如顧客點3對應的基因為2.56。若要對上述染色體進行解碼，則需對實數的整數部分和小數部分分別進行分析。具體過程如下。

Step1：將每個實數取整，得到{1，2，3}，其中的數字代表車輛編號，因此共2輛車進行配送。接著將整數相同的實數分為一組，則得到車輛編號和顧客點的匹配結果為：編號為1的車輛為顧客點1服務，編號為2的車輛為顧客點2和3服務。編號為1的車輛可直接得到配送路線(0→1→0)，其中0表示車場，代表車輛從車場出發(fā)為顧客點1服務后返回車場；編號為2的車輛同時為多個顧客點進行服務，則進入Step 2。

Step2：取顧客點2、3對應序號位實數的小數部分，得到{0.31，0.56}。根據值的大小進行排序，由于0.56>0.31，因此編號為2的車輛配送路線為(0→3→2→0)，其中0表示車場，代表車輛從車場出發(fā)依次服務完顧客點3、2后返回車場。

結合Step1和Step2，得到染色體的解碼結果為{0，1，0，3，2，0}。

2.2 改進差分進化算法的求解步驟

Step1：車場—顧客點的匹配。根據車場和顧客點的位置坐標，采用K-means聚類方法對每個車場和顧客點進行匹配，將多車場GVRP轉化為單車場GVRP。

Step2：初始化。設種群規(guī)模為N，當前迭代次數Iter=1，最大迭代次數為Itermax。

Step3：構建可行解。由于存在車輛額定載重和客戶點時間窗等集合約束，隨機產生的染色體很有可能產生非法解，因此需要對種群進行調整。

Step4：適應度函數計算。根據式（1）計算適應度函數fitness=λ1（C1+C2）+λ2（C3+C4+C5+C6），其中λ1+λ2=1，λ1，λ2＜1。為突出節(jié)能減排，令λ1＞λ2。

Step5：選擇、交叉、變異操作。

Step5.1：設定F∈[0，2]為變異因子，CR1∈[0，1]為差分進化的交叉概率因子，CR2∈[0，1]為遺傳基因的交叉概率因子。隨機選擇父代個體xat、xbt和xct；

Step5.2：按差分進化方式進行變異，如式（11）所示，得到變異向量vzi，t；

Step 5.3：由于染色體為實數編碼，為增加種群的多樣性，在對染色體進行交叉操作時將同時使用數值交叉和遺傳基因交叉，以產生新的染色體。本文對種群中70%的個體進行數值交叉操作（如式（12）所示），剩下30%的個體進行基因順序交叉操作。將x（i）與變異矢量vzi，t進行數值交叉，產生新個體(i)；

Step5.4：采用精英保留策略進行選擇操作，從父代個體xi，t和新個體x～i,t1+中選擇最優(yōu)個體直接替換掉最差個體，從而形成新的種群。

Step6：算法結束判斷。進化代數Iter=Iter+1，記錄當前染色體和個體。如果Iter大于最大迭代數Itermax，則終止算法輸出最優(yōu)解；否則返回Step 6。

3 算例仿真分析

3.1 參數設置

采用Solomon數據庫中的集中分布型算例C101、隨機分布型算例R201，以及混合分布型算例RC101、RC201作為本文測試數據。新增坐標為（20，60）和（75，55）的兩個車場，與以上算例共同構成本文的仿真算例。每個車場配備2種車型，每種車型的車輛數為2，即三個車場共配備12輛車進行配送。有關費用設置如下：Cf=8元/L，Ce=0.052 8元/kg，β1=β2=10元/分鐘。不同車型車輛參數值如表2所示。兩種車型的行駛速度均為60 km/h，程序采用Matlab R2018a編程實現，在Windows10環(huán)境下，在CPU3.40 GHz、內存8G的微機上運行。

表2 不同車型車輛參數

3.2 算例仿真結果分析

為了驗證本文模型及提出算法的有效性，本文采用算例RC201進行測試，程序的運行時間為129.4 s。程序的最優(yōu)車輛路徑規(guī)劃方案如圖1所示，圖中紅色正方形為車場。車輛分配方案及配送路線決策結果如表3所示，表中DN表示車場序號，ST表示車輛型號，SN表示路線序號，VR表示車輛行駛路徑。

圖1 算例RC201 的最優(yōu)車輛路徑規(guī)劃圖

表3 車輛分配及配送路線決策結果

由表3可以看出：第一，ST顯示，3個車場中車場101和車場103只采用1種車型，而車場102采用了2種車型。第二，SN顯示，3個車場一共使用7輛車完成配送，其中車場101使用2輛1#車型車輛，車場102使用2輛1#車型車輛和1輛2#車型車輛，車場103使用2輛1#車型車輛。第三，VR顯示，1#車型和2#車型車輛配送的顧客點數量顯著不同，1#車型配送顧客點數量最多為23個（路線1），最少為12個（路線4），而2#車型配送顧客點數量只有6個（路線5），究其原因主要是本算例中客戶點的需求量相差不大，車輛行駛距離和時間窗也比較相近，因此應盡可能由同一種車輛完成配送。

4 結 論

為降低物流配送成本、滿足綠色物流的配送需求，本文針對多車場多車型的綠色物流車輛路徑問題，構建了GVRPTWMDHV數學模型，并設計了改進的差分進化算法進行求解。仿真結果表明：針對多車場多車型帶時間窗GVRP，本文以總配送成本最小化為目標構建的模型和算法能夠有效降低車輛的油耗碳排放及總配送成本，實現了經濟效益和環(huán)境效益的協同優(yōu)化。