環境與成本兼顧視角下的多車型HFGVRPTW 研究

王 莉 （湖南工商大學 智能工程與智能制造學院，湖南 長沙 410205）

0 引 言

近年來，對綠色車輛路徑選擇問題（Green Vehicle Routing Problem，GVRP）的研究因其對環境和社會的有利影響而日益受到重視。世界能源理事會報告指出，全球運輸部門的主要能源是石油產品，特別是汽油、柴油、燃料油和噴氣燃料，其排放的二氧化碳總量在2010—2050年期間將從16%上升至79%，而排放量增加與車輛移動量及燃油消耗量有直接聯系，并且在大多數情況下與車輛移動量成正比。因此減少車輛運輸過程中的車輛數、油耗量和碳排放量對未來全球環境的改善具有深遠影響。

郭紅霞等[1]以網絡運營成本最低為優化目標，建立了網絡條件下公路港多車型甩掛調度優化模型，并設計了基于動態規劃法、節約里程法和改進模擬退火算法的兩階段啟發式算法對模型求解。何小年等[2]將車輛使用費用分為固定費用和以油耗為主的可變費用，構建了以最小化油耗為目標的多車型車輛路徑問題模型，然后運用禁忌搜索算法對其進行求解。路世昌等[3]以碳排放最小化為優化目標，設計了兩階段啟發式算法進行求解。趙志學等[4]以油耗碳排放成本最低為優化目標，設計了一種融合模擬退火算法的混合差分進化算法求解。趙靜等[5]以物流配送總成本為目標函數，采用改進粒子群算法求解。程元棟等[6]以冷鏈配送總成本最低為目標建立數學函數模型，并采用改進的遺傳算法求解。

梳理國內外文獻可知，諸多學者從不同角度對GVRP進行了探索，并形成了日益豐富的研究成果，但是以下方面仍需進行深入研究：已有文獻中很少同時考慮多車型和時間窗，這與貨物配送的實際情況不符。配送中心通常配備有多種車型，且服務的客戶多集中在城市，這些客戶對貨物送達時間有要求。已有研究雖然考慮了總成本最小化，但也只是將油耗量或碳排放量轉化為了經濟成本，而較少關注環境本身的影響，不利于節能減排。為此，針對上述問題，本文提出了車輛油耗量與配送成本最小化的雙目標優化模型，并采用動態規劃算法結合遺傳算法的混合啟發式算法求解，解決了多車型帶時間窗綠色物流的車輛分配和物資配送問題。

1 問題描述及定義

1.1 問題描述

本文研究的問題可描述為：某配送中心擁有多種不同車型的配送車輛，要求在時間窗和車輛資源有限的條件下，設計科學合理的配送計劃，使車輛油耗量和總成本最低。

本文中定義模型的假設條件有：配送中心每種車型的車輛數有限；配送中心無容量約束；配送中心與客戶點、客戶點之間的距離已知，且車輛的行駛速度不變，為車輛的油耗最優速度；每輛車只執行1次配送任務，可以在不同時刻出發，完成任務后即回到配送中心；每位客戶只能訪問一次且只能被一輛車訪問；每位客戶的貨物量不超過車輛最大容量；考慮的時間為運輸時間、車輛服務時間和車輛等待時間，物資裝卸載時間不予考慮。

1.2 符號與變量定義

符號：G=（V，A）為配送網絡。V表示節點集，V={p|p=0，1，...，P}，其中0表示配送中心，v′=v{0}表示客戶集合。qi為客戶i（i∈V′）的貨物量。A為連接頂點的弧集，A={（i，j）|i，j∈A，i≠j}，dij為路段Aij的距離。U為配送車型集合，U={u|u=1，...，M}，Qu為車型u的額定容量，μu為車型u的凈重，Zu為車型u的車輛數。SQ為所有車型額定容量集合。Qmax=max{Q1，Q2，...，QTY}表示所有車型的最大容量。Ku={k|k=1，...，Zu}為車型u的配送車輛集合，總車輛集合為K={K1，K2，...，KM}。lukij表示車型u的第k輛車在路段Aij上的載重，vf表示車輛的油耗最優速度。sti為客戶i的服務時間，[Bi，Ei]為客戶i的服務時間窗。saik為車輛k到達客戶i的時間，sbik為車輛k到達客戶i的等待時間，如果saik＜Bi，那么sbik=Bi-saik；否則sbik=0。scik為車輛k離開客戶i的時間。Ff表示總油耗，fukij為車型u的第k輛車在路段Aij上的油耗量。UC表示總成本。Pu為車型u的車輛固定發車成本，Ru為車型u的車輛單位時間租用費用，Wu為車型u車輛單位時間的人力成本，ccik為車輛k在路段Aij上的懲罰成本。

ζ表示燃油空氣質量比，K表示典型柴油的熱值（kJ/g），N表示發動機排量（升），V發動機轉速（rev/s），ψ為換算系數（g/L），ε表示車輛傳動效率，ω表示柴油機效率參數，g為重力加速度（m/s2），θ為道路坡度，Cr表示滾動阻力系數，Cd表示空氣阻力系數，As為車輛鋒面面積（m2），ρ為空氣密度（kg/m3）。

決策變量：xuk為0—1變量，當車型u的第k輛車被使用時該值為1，否則為0。yij為0—1變量，若路段Aij被配送車輛訪問，該值為1，否則為0。zik為0—1變量，客戶i由車輛k服務時該值為1，否則為0。

2 模型構建

根據油耗計算相關理論，油耗會受多種因素共同影響，其中速度和載重是影響油耗的兩個最重要的因素。Barth等人在2005年提出了綜合模式排放CMEM模型。指出車型為u的第k輛車在路段Aij上的油耗量為：

式（2）為目標函數1，表示車輛配送過程中最小的油耗量。式（3）為目標函數2，表示車輛最低的配送總成本最低。式（4）表示每種型號的每輛車只能服務每位客戶一次。式（5）表示每種型號的每輛車最多只能使用一次。式（6）表示所有從配送中心出發的車輛最都要返回配送中心。式（7）表示配送車輛只能從客戶點的一個方向往另一個方向單向行駛。式（8）與（9）表示客戶時間窗約束。式（10）表示車輛離開客戶的時間為到達客戶的時間、等待時間、服務時間的總和。式（11）表示車輛到達下個客戶點的時間為車輛離開上個客戶點的時間與該車輛在兩客戶點之間的路段上行駛時間的總和。式（12）—式（14）表示車輛容量約束。式（15）表示變量的取值約束。

3 算法設計

本文研究的HFGVRPTW是一個多目標優化問題，屬于NP-hard問題。傳統求解多目標優化問題的方法主要包括兩種：一種是將多個目標轉化為單一目標，再分別進行優化，求解速度快；另一種是將多目標優化問題作為整體進行求解，以期得到更優解。本文基于第二種方法，設計了一種動態規劃算法結合遺傳算法的混合啟發式算法來求解上述模型。

3.1 參數初始化及適應度函數

3.1.1 參數初始化

設定配送中心地址坐標DZ、客戶點數量CN、客戶點坐標CD、車型數量TY、車型集合U、車型額定容量集合SQ、動態規劃算法最大循環次數N、遺傳算法最大循環次數Gen_max、交叉概率pc、變異概率pm、以及CMEM計算模型中ζ、K、N、V、ψ、ε、ω、g、θ、Cr、Cd、As、ρ的初始值。令當前遺傳算法的循環次數itre=1。

3.1.2 適應度函數

本文采用加權法對目標函數O1和O2進行處理，并將其作為適應度函數。定義λ1和λ2分別為目標函數O1和目標函數O2的權重，λ1+λ2=1，如此一來，原本的多目標問題就轉變成了單目標問題，即：

3.2 種群編碼及種群結構調整

3.2.1 種群編碼

種群中每一條染色體上都包含若干子串。子串1為自然數編碼，長度為m×n×p，其數值表示m車型的n輛車配送p個客戶點的情況；子串2為實數編碼，長度為m×n×p，其數值表示車輛n運輸物資到客戶點j的時間。因此，染色體的總長度為2×m×n×p。

3.2.2 種群結構調整

隨機產生的染色體可能會導致客戶的需求量超過車輛最大載重量或車輛到達時間超過時間窗的情況發生，產生非法解，因此需對種群結構進行調整，具體過程可參照2.4。

3.3 適應度計算

為評價模型種群中個體的優劣性，根據式（16）對每個染色體的適應度進行計算，適應度最大的染色體為最優染色體，其中的個體為最佳個體。

3.4 遺傳操作

為了保證算法具有較強的全局搜索性、較高的搜索精度和較快的收斂速率，本文采用遺傳算法進一步優化動態規劃算法的全局最優解。選擇操作采用精英選擇，交叉操作采用順序交叉法，變異操作采用逆轉變異法。

3.5 算法結束

用進化代數，記錄當前染色體和個體。如果滿足要求，則終止算法輸出最優結果；否則返回3.2繼續運行。

4 算例仿真分析

4.1 參數設置

算例采用Solomon數據庫中的C103算例作為本文的測試數據，其中各算例都有100位客戶與一個配送中心。將配送中心坐標設為（40,50）。擁有2種配送車輛，其最大車輛數、凈重、額定容量、運營成本、租車費用和人力成本的具體情況如表1所示。兩種車型的行駛速度均為50 km/h，懲罰成本均為10元/分，車輛在客戶點的服務時間為10分鐘。油耗量CMEM計算模型中各典型參數值如表2所示。

表1 車輛數據

表2 CMEM 模型的典型參數

為了求解測試算例，本文設計的混合式啟發式算法在Windows7、CPU為1.90 GHz、內存為4G的微機上采用Matlab R2014a編程來實現。算法參數設置如下：N=50，gen_max=500，pc=0.9，pm=0.01，λ1=0.8，λ2=0.2。

4.2 算例仿真結果分析

4.2.1 車型分配及車輛行駛路徑結果分析

將算法運行10次，平均運行時間為201.8s，說明該算法的收斂性較好，能滿足物流管理工作的時間需要。車輛分配方案與計算結果如表3所示。

由表4可知：a.并未將所有車輛完全使用，只使用了7輛3.5噸的車，5.5噸的車也只使用了6輛，原因是3.5噸車輛的油耗量和車輛使用成本等都低于5.5噸車輛，而在本算例中客戶點需求量都比較接近，因此優先安排3.5噸車輛進行配送；b.不同車型車輛配送的客戶點數量沒有較大差別，100個客戶點中由3.5噸車輛和5.5噸車輛分別配送其中的50個客戶點。原因是客戶點的需求量都不是很大，時間窗比較接近，應盡可能由同一種車輛完成配送。但是在本算例中3.5噸車輛的油耗量和車輛使用成本等都低于5.5噸車輛，因此在油耗量和成本均為最小化的雙目標下，通過減少使用載重5.5噸的車輛數來降低配送中產生的油耗量和總成本。

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

4.2.2 不同最大車輛數約束條件下的車型分配及車輛路徑規劃

為了比較最大車輛數約束對HFGVRPTW的影響，本文通過設置不同的最大車輛數對凈重為3.5噸和5.5噸的兩種車型進行仿真實驗，計算結果見表4，適應度值變化情況如圖1所示。

圖1 不同最大車輛數約束條件下的適應度值

由表4和圖1可知，最大車輛數約束條件對不同車型的油耗量和總成本有顯著影響。當最大車輛數為10、15時，所有車輛都投入使用，意味著每輛車的行駛距離和行駛時間會延長，油耗量和總成本也會增大；當最大車輛數為20、25和30時，雖然并未使用所有車輛，但是由于每輛車配送的客戶數減少，投入使用的車輛反而增多，同樣導致產生的油耗量和總成本更大；車輛使用率對油耗量和總成本有顯著影響。最大車輛數為20時，車輛使用率僅為65%，產生的油耗量和總成本明顯低于車輛數最大時的結果。因此在車輛數充足的前提下降低車輛使用率可有效減少油耗量和總成本；在不同的最大車輛數約束條件下，不同車型車輛配送的客戶點數量無較大差別，原因是載重3.5噸車輛的油耗量和車輛使用成本等都低于載重5.5噸的重型車，因此優先使用載重3.5噸車輛進行配送。

5 結 論

為降低物流配送成本、滿足綠色物流的配送需求，本文構建了異構車型帶時間窗的HFGVRPTW數學模型，并設計了動態規劃算法結合遺傳算法的混合啟發式算法進行求解。實驗結果表明相對于單車型車輛，選擇多車型進行配送，其油耗量和配送成本都會降低，更有利于綠色物流配送；當客戶點的需求量和時間窗比較接近時，在車輛數充足的前提下，降低車輛利用率可有效降低油耗量和總成本；如果只考慮環境目標，會導致總配送成本增加；而如果只考慮經濟目標，會導致環境進一步惡化。因此實現節能減排需要綜合考慮環境目標與經濟目標。