王 莉，趙志學(xué) WANG Li，ZHAO Zhixue

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

0 引 言

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

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

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

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

1 問題與模型

1.1 問題描述

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

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

1.2 符號與變量定義

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

表1 客戶點相關(guān)變量說明

1.3 GVRPTW-MDHV 模型的構(gòu)建

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

其中：

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

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

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

FE=2.621 kg/L，為燃油排放參數(shù)。

2 改進差分進化算法設(shè)計

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

2.1 染色體的編碼與解碼

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 算例仿真分析

3.1 參數(shù)設(shè)置

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

表2 不同車型車輛參數(shù)

3.2 算例仿真結(jié)果分析

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

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

表3 車輛分配及配送路線決策結(jié)果

由表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#車型車輛配送的顧客點數(shù)量顯著不同，1#車型配送顧客點數(shù)量最多為23個（路線1），最少為12個（路線4），而2#車型配送顧客點數(shù)量只有6個（路線5），究其原因主要是本算例中客戶點的需求量相差不大，車輛行駛距離和時間窗也比較相近，因此應(yīng)盡可能由同一種車輛完成配送。

4 結(jié) 論

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