陳高華，郗傳松

（1.太原科技大學電子信息工程學院，山西 太原 030024；2.太原科技大學電子信息工程學院，山西 太原 030024）

1 引言

隨著全球污染日益嚴峻，低碳環(huán)保問題引起了各行業(yè)的重視，根據(jù)國際能源屬2016年數(shù)據(jù)統(tǒng)計，車輛在物流配送中產(chǎn)生的碳排放量大約占全球總量的16.9%，因此降低車輛配送中所排出的二氧化碳（CO2）逐漸成為車輛路徑優(yōu)化問題的新的研究熱點。文獻［1］分別以配送成本最小、環(huán)境成本最小、配送成本與環(huán)境成本之和最小為目標構建3種VRP模型。文獻［2］根據(jù)配送車輛載重不同建立碳排放成本模型，并設計帶混沌擾動的蟻群算法來求解該模型。文獻［3］以車輛載重、客戶時間窗和冷鏈產(chǎn)品變質(zhì)率為約束，考慮客戶滿意度的條件下建立了以碳排放量最小的冷鏈車輛路徑優(yōu)化模型。文獻［4］在考慮低碳條件下，建立了車輛路徑選擇模型，并提出多種群遺傳算法來求解模型，但該研究僅考慮碳排放量僅與車輛的行駛速度與行駛距離有關，其研究模型還存在改進空間。文獻［5］通過分析最短路徑建立了碳排放量最少的模型，并根據(jù)模型特點設計了改進算法來求解。文獻［6］構建了低碳條件下新能源車輛路徑問題模型建立最短路徑和最小碳排放的多目標集貨模型，通過改進兩階段啟發(fā)式算法求解模型。文獻［7］以帶時間窗車輛路徑為基礎，通過對車輛行駛速度、載重和運行里程的改變建立了總成本最低、周轉時間最小的車輛路徑優(yōu)化模型。文獻［8］通過地圖軟件獲取實際配送距離，以配送車輛載重為約束，構建了碳排放成本和時間窗懲罰成本等綜合成本最低的物流配送模型。文獻［9］在時變網(wǎng)絡下將道路擁堵因素引入綠色車輛路徑優(yōu)化數(shù)學模型中，根據(jù)模型特點，設計了改進蟻群算法來求解。文獻［10］針對AGV路徑規(guī)劃問題，根據(jù)規(guī)劃模型提出了一種改進的蟻群算法來求解。文獻［11］考慮車輛配送過程中載重的實時變化對油耗與碳排放量的影響，并給出配送網(wǎng)絡內(nèi)的最優(yōu)路徑?jīng)Q策。文獻［12］在低碳環(huán)境下研究冷鏈物流配送路徑優(yōu)化問題，分別以為碳排放量最低和總行駛距離最少為目標構建了模型，不足是沒有將兩個目標進行綜合考慮。

通過上述文獻的研究，可以分析出碳排放量與車輛載重、行駛速度和行駛距離之間存在一定的關系，但既有研究大多都將研究重點放在了單目標優(yōu)化方面，且沒有將碳排放量與車輛載重、車輛速度和行駛距離等因素綜合考慮，不符合實際的配送情況，降低了優(yōu)化結果的適用性。在綜合考慮車輛實時載重、行駛速度和行駛距離的基礎上提出多目標車輛路徑優(yōu)化模型，并對模型設計了一種改進算法來求解，通過算例驗證了模型和算法的有效性。

2 多目標車輛路徑模型

2.1 問題描述

假設有一定數(shù)量的客戶，各自有不同的貨物和配送時間需求，在一定的約束下，達到配送總成本最低，碳排放量最小的要求，為了方便建模，假設如下：

（1）配送中心和需求點的地理位置、需求、時間窗全部已知。

（2）車輛由配送中心發(fā)出后，最后返回配送中心。每一個顧客只能有一輛車來進行配送，且服務時間恒定。

（3）所有的車為同一規(guī)格，每臺車能服務一次，每輛車載重量要大于單個客戶需求量，且每條路線上的客戶需求總量不大于車輛最大載重。

（4）配送車輛的速度恒定，不考慮道路擁堵程度。

2.2 數(shù)學模型

綜合考慮碳排放量最少和配送總成本最低兩方面因素，其優(yōu)化目標如下：

式中：minλ1—最小化碳排放量λ1；minλ2—最小化配送總成本λ2。

2.2.1 碳排放量因素分析

車輛在實際行駛過程中，由于以汽油，柴油等作為燃料，必然會產(chǎn)生碳排放的問題，其受到影響因素也比較多，這里主要考慮影響因素較大的車輛載重負荷、行駛速度和行駛距離。根據(jù)相關研究可知車輛碳排放量λ1與燃油消耗Cfuel呈倍數(shù)關系，所以采用一個燃油消耗因子F，即消耗單位燃油所釋放的二氧化碳數(shù)量來計算碳排放量，表達式為：

假設配送車輛的載重量限制為f，配送車輛從客戶i點到客戶j點，其距離為dij，實時載重負荷為fij，行駛速度為vij。

（1）車輛的載重負荷與燃油消耗量存在一定的關系因車輛載重負荷的所產(chǎn)生的燃油消耗的表達式［13］為：

式中：w—配送車輛自身重量；ε0—空載時燃油消耗率；ε*—滿載時燃油消耗率。

（2）車輛的行駛速度與燃油消耗量存在一定的關系［14］，因行駛速度產(chǎn)生的燃油消耗表達式為：

式中：β1= 0.5Cd Ap，Cd—載重汽車的牽引力系數(shù)；A—載重汽車正面表面積；p—空氣密度。

2.2.2 配送總成本因素分析

物流車輛配送時配送總成本λ2主要包括三個方面，分別為車輛固定使用成本λ12、車輛行駛距離成本λ22和違反客戶服務時間的時間窗懲罰成本λ32，具體表達式如下：

式中：m—配送中心使用的配送車輛總數(shù)；g—每輛車的固定使用成本；N={1 ，2，…，n}—客戶需求點個數(shù)；1—配送中心；c—配送車輛行駛單位距離的成本；e(i)—客戶接受服務的最早時間；l(i)—客戶接受服務最晚時間；time(i)—客戶點接受服務的時間；p1—物流車輛提前到達客戶點而產(chǎn)生的單位時間懲罰成本；p2—車輛晚于最遲時間到達而產(chǎn)生的單位時間懲罰成本。

決策變量：

通過對碳排放量因素、配送總成本因素的分析建立，構建碳排放量最少、配送總成本最低的多目標數(shù)學模型如下：

約束條件：

式（8）表示車輛配送過程中產(chǎn)生碳排放量最少的目標函數(shù)；式（9）表示物流車輛配送時配送總成本最低的目標函數(shù)，主要包括三個方面，分別為車輛行駛距離成本、車輛固定使用成本和時間窗懲罰成本；式（10）表示客戶點的載重負荷限制；式（11）表示每個客戶點僅被訪問一次；式（12）、式（13）表示每個需求點僅被一輛車服務；式（14）表示配送車輛的起點和終點必須為配送中心；式（15）表示配送車輛從配送中心出發(fā)的時刻為0。

3 基于改進蟻群算法的模型求解

蟻群算法是一種新型的啟發(fā)式算法，被廣泛應用于各個領域，在解決車輛路徑問題時，雖然能規(guī)劃出從起始點到目標點的路徑，并且具有很強的魯棒性，但存在容易陷入局部最優(yōu)、過早停止收斂、搜索時間長、效率低等缺點，這里分別從初始信息素，轉移規(guī)則和信息素更新方式方面進行了改進，加快了算法在初始階段的尋優(yōu)速度，提高了算法的搜索效率。

3.1 初始信息素

在初始時刻，將信息素總量與各個需求點和配送中心的距離作為信息素分布矩陣，因此，各個需求點之間影響不同，增加了較優(yōu)路徑被選擇的概率，加快了算法在初始階段的尋優(yōu)速度。初始信息素的改進數(shù)學表達式為：

式中：Q—每一次搜索螞蟻釋放的信息素總量；d1i—需求點i和配送中心的實際距離。

3.2 轉移規(guī)則

基本蟻群算法在轉移規(guī)則中只考慮了客戶i與客戶j的距離，易陷入局部最優(yōu)。綜合考慮客戶i與客戶j的時間窗寬度及碳排放量，改進表達式如下：

式（17）中概率模型pkij，如式（18）所示。

式中：q—假定的固定閾值，用來控制狀態(tài)轉移規(guī)則參數(shù)；q0—一個在區(qū)間［0，1］上的隨機數(shù)，當q＜q0，采用確定性搜索模型，當q≥q0時采用改進的概率模型；α—信息素濃度重要因子；β、ω和γ—啟發(fā)函數(shù)重要程度因子；ηij= 1/dij—啟發(fā)函數(shù)；Widthij=l(i) -e(i)—客戶的時間窗寬度，時間窗越緊，表示客戶的需求越緊迫，優(yōu)先服務此類顧客；Zij—路徑上需求點i到需求點j配送車輛產(chǎn)生的碳排放量，其值越小，說明點i到點j的所積累的信息素濃度越高，則螞蟻選擇該條路徑的可能性越高。

3.3 全局信息素更新策略

蟻群算法收斂到最優(yōu)解的過程是信息素濃度不斷增強的體現(xiàn)，信息素的更新策略對于蟻群算法的成功搜索具有重要的意義。傳統(tǒng)蟻群算法僅利用螞蟻經(jīng)過路徑的整體信息（經(jīng)過路徑的總長）計算釋放的信息素濃度，沒有區(qū)分當前最優(yōu)路徑和較差路徑，使其信息素分布無法進行較快改變，從而使算法的收斂速度和求解質(zhì)量較差。改進的信息素更新數(shù)學表達式為：

其中，Δτij、Δτijkk和Δτij*的表達式，如式（20）所示。

式中：Δτij(t)—在第t次迭代時，需求點i和需求點j之間路徑上的信息素濃度；p—每一次迭代后，路徑上信息素的揮發(fā)因子；Δτij—每一次迭代的i點與j點信息素改變總量；在該次迭代中，第kk個螞蟻對于點i與j點信息素改變的貢獻值；額外對目前獲得的最優(yōu)路徑的獎勵，讓該路徑上的信息素進一步加強；lkk—第kk個螞蟻選擇的路徑的總長；lbest—目前獲得的最優(yōu)路徑的總長；sizepop—螞蟻總數(shù)。

3.4 混沌擾亂機制

蟻群算法在應用于車輛路徑問題時，如果蟻群（車輛）搜索得到的可行解都相同，算法此時可能陷入局部最優(yōu)，這時引入混沌擾動機制，首先對信息素進行混沌初始化，給出新的啟發(fā)式信息來對路徑進行搜索，具體改進方法為：首先根據(jù)混沌迭代方程生成一組混沌變量，混沌變量是通過Logistic 映射（一種經(jīng)典的混沌映射）產(chǎn)生的，具體方式如下：

但混沌初始化在加快收斂速度的同時也可使算法陷入局部最優(yōu)解，因此為在螞蟻完成一輪搜尋后，在信息素更新中加入混沌擾動，可以增加搜尋的遍歷性及隨機性。引入混沌擾動后的信息素更新表達式為：

式中：ξ—可調(diào)節(jié)系數(shù)，是一個常數(shù)；Fij(t)—混沌變量；μ—控制變量，μ的取值范圍一般為［3.5-4.0］。

模型求解的具體流程如下：

（1）初始化參數(shù)，設定最大迭代次數(shù)Maxiter，按照式（16）對每個客戶點之間產(chǎn)生初始信息素，初始化Nc（迭代次數(shù)）=0，確定每個參數(shù)的函數(shù)值。

（2）創(chuàng)建禁忌表，讓所有的螞蟻（配送車輛）從配送中心出發(fā)，在滿足約束的前提下，按照式（17）來選擇下一個需求點，并將此需求點添加至禁忌表。

（3）若配送車輛不滿足下一個客戶點的需求，則配送車輛返回配送中心，更新禁忌表，重復該過程，直到所有的客戶點全部加入到禁忌表中，禁忌表更新滿足時間窗和載重限制。

（4）采用2-opt對每次路徑內(nèi)的配送路徑進行局部優(yōu)化。

（5）所有螞蟻完成循環(huán)后，按照式（19）來更新信息素，計算當前迭代得到的可行解，并與前代所得到的可行解進行對比，記錄最優(yōu)解，若算法5次得出的可行解不變，則引入混沌擾動機制，按照式（21）、式（22）來更新信息素。

（6）當Nc=Nc+1且Nc＜Maxiter則執(zhí)行步驟（2）～步驟（5），否則算法迭代結束，輸出最優(yōu)解。

4 算例求解及結果分析

4.1 算例求解

為了驗證所提方法的有效性，這里所有測試都在數(shù)據(jù)集都采用solomom中的R101算例，但R101的各個數(shù)據(jù)沒有設定具體的量綱，所以人為設定載重量以kg為單位，距離以km為單位，時間以s為單位，假設車輛載重f= 200kg，車輛自重W= 100kg，β1= 1.75，信息素濃度Q= 100，螞蟻數(shù)量sizepop= 60，信息素重要程度因子α= 1.5，啟發(fā)函數(shù)重要程度因子β= 3、γ= 1、ω= 1.5，轉移閾值q= 0.3，最大迭代次數(shù)maxiter= 200，信息素揮發(fā)因子p= 0.4車輛固定使用成本g= 200，每公里運輸固定成本c= 20元/km時間窗懲罰系數(shù)p1= 0.2元/s、p2= 0.4元/s，車輛行駛速度v= 13m/s，車輛空載時燃油消耗率ε0= 0.254，車輛滿載時燃油消耗率ε*=0.276，燃油消耗因子F= 2.61kg/L。

由于這里是解決多目標優(yōu)化問題，對于一個多目標優(yōu)化問題而言，由于存在目標之間的沖突和無法比較的現(xiàn)象，在目標函數(shù)沒有進行加權處理的情況下，一個解在某個目標上可能是最好的，在其他目標上可能是最差的，這些在改進任何一個目標函數(shù)的同時，必然削弱至少一個其他目標函數(shù)的解稱為非劣解（非支配解）或Pareto（帕累托）解，其Pareto解不是唯一的，而是多個解構成Pareto最優(yōu)解集。

采用所提出的算法通過Intel（R）Core（TM）i5-8300H CPU@2.30GHz，運行內(nèi)存為8GB，操作系統(tǒng)為Win10家庭中文版的matlab2016a上迭代200次，這里提出的多目標模型算例求解結果的非劣解分布圖，如圖1所示。多目標模型下目標λ1（碳排放量）取極值時對應的車輛路徑規(guī)劃圖，如圖2所示。多目標模型下目標λ2（配送總成本）取極值時對應的車輛路徑規(guī)劃圖，如圖3所示。

圖1 非劣解分布圖Fig.1 Distribution of Non-Inferior Solutions

圖2 碳排放量最少時車輛最優(yōu)路徑分布Fig.2 Optimal Path Distribution for Vehicles with the Lowest Carbon Emission

圖3 配送總成本最低時車輛最優(yōu)路徑分布Fig.3 Optimal Path Distribution of Vehicles at the Lowest Total Distribution

將所提算法對不同目標函數(shù)進行求解，求解的結果，如表1所示。其中A是只慮碳排放量最少，不考慮配送總成本時的單目標優(yōu)化結果，B只考慮配送總成本最低，不考慮碳排放量時的單目標優(yōu)化結果，C1是多目標模型下目標λ1（碳排放量）取極值時對應的數(shù)據(jù)。C2是多目標模型下目標λ2（配送總成本）取極值時對應的數(shù)據(jù)。

表1 不同目標函數(shù)下的結果統(tǒng)計Tab.1 Results Statistics Under Different Objective Functions

對A和C1的數(shù)據(jù)進行分析可得，相比于多目標優(yōu)化，在只考慮碳排放量這一單目標優(yōu)化時，雖然碳排放量降低了1.9%，但是配送總成本卻增加了7.04%；對B和C2的數(shù)據(jù)進行分析得，相比于多目標優(yōu)化，在只考慮配送總成本這一單目標優(yōu)化時，其成本降低了1.7%，碳排放量卻增加了3.2%，所以提出的多目標優(yōu)化模型在同時解決配送總成本和碳排量這兩個目標時，相比于單目標，具有更好的實用性。

4.2 算法性能分析

為了驗證這里算法的性能，在參數(shù)設置完全相同的情況下，將改進蟻群算法和經(jīng)典蟻群算法各運行10次后，兩種算法的非劣解分布，如圖4所示。兩種算法的碳排放量收斂曲線對比，如圖5所示。兩種算法的配送總成本的收斂曲線的對比，如圖6所示。兩種算法的優(yōu)化改進比例統(tǒng)計結果，如表2所示。

圖4 非劣解分布對比Fig.4 Distribution Comparison of Non-Inferior Solutions

圖5 碳排放量收斂曲線Fig.5 Convergence Curve of Carbon Emission

圖6 配送總成本收斂曲線Fig.6 Convergence Curve of Distribution Cost

由圖4可知，相比于經(jīng)典的蟻群算法，改進蟻群算法的Pareto解集中非劣解不僅在數(shù)量上更多，而且Pareto前沿也具有更好的分布性。由圖5、圖6可以看出改進算法在求解質(zhì)量和收斂速度上具有明顯優(yōu)勢。由表2可知，在配送總成本方面，最低成本的改進比例為4.5%，最高成本的改進比例為8.4%，平均成本改進比例為6.5%；在碳排放量方面，最少碳排放量的改進比例為4.2%，最高碳排放量改進比例為1.4%，平均碳排放的改進比例為3.5%。與經(jīng)典蟻群算法相比，所提出改進算法在降低配送總成本和減少碳排放量方面均有明顯改進。

5 結語

在帶軟時間窗和容量限制的車輛路徑優(yōu)化問題上，綜合考慮了汽車載重負荷、行駛速度和行駛距離等影響碳排放量的因素，提出了同時考慮碳排放量和配送總成本的多目標車輛路徑優(yōu)化模型，針對經(jīng)典蟻群算法的不足，重新設計了初始信息素和路徑轉移規(guī)則等環(huán)節(jié)，提高了算法的全局搜索能力，再用2-opt算法對局部進行搜索，進一步優(yōu)化了解的質(zhì)量，其次引入了新的信息素更新公式和混沌擾動機制來更新路徑上的信息素，加強了解的多樣性，通過對模型的求解，算例分析結果如下：（1）分別以只考慮碳排放量，不考慮配送總成本、只考慮配送總成本，不考慮碳排放量和同時考慮碳排放量和配送總成本為目標函數(shù)，在相同的數(shù)據(jù)集中測試表明所提出的多目標模型能夠在降低物流企業(yè)配送成本的同時實現(xiàn)節(jié)能減排，更符合企業(yè)的發(fā)展。（2）通過對solomo數(shù)據(jù)集的測試，所提出的改進的蟻群算法在配送總成本的和碳排放量的優(yōu)化上均優(yōu)于經(jīng)典的蟻群算法，證明該算法在一定程度上能求解出有效的滿意解。所提出的模型和改進的算法能夠有效的解決物流配送問題，但筆者未考慮當客戶需求點發(fā)生動態(tài)變化以及道路擁堵等動態(tài)因素，這是下一步研究的重點。