考慮新能源車的低碳集貨模型與算法研究

史雨同 尹靜 王柏琳

關鍵詞： 制造供應鏈; 碳排放; 新能源車; 集貨模型; 路徑優化; 遺傳算法; 節約算法

中圖分類號： TN911.1?34; F253.9 ? ? ? ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2019）03?0101?06

Abstract： Aiming at the consolidation problem of manufacture supply chain scattered in various areas of China， the multi?object consolidation model with shorted path and lowest carbon emission is established by considering the vehicle types such as new energy electrical vehicle and traditional diesel vehicle. A two?stage heuristic algorithm was designed according to model feature to solve the model. In the first stage of the algorithm， the genetic algorithm is used to find the consolidation scheme with shortest path as the initial consolidation scheme. On the basis of first stage， the basic thought of saving algorithm is used to perform route splitting， match the limited quantity new energy vehicles， and replan the consolidation method for residue node and vehicle， so as to optimize the carbon emission. The simulation experimental results show that the proposed model and two?stage algorithm can utilize the new energy vehicle effectively， and satisfy the economic benefit and environmental benefit in consolidation process.

Keywords： manufacturing supply chain; carbon emission; new energy vehicle; consolidation model; route optimization; genetic algorithm; saving algorithm

0 ?引 ?言

制造供應鏈中的集貨運輸活動由于具有節點較多且位置分散等特征，會引起物流成本上升和碳排放增多等問題，不利于我國綠色經濟的發展。新能源貨車尤其是純電動車具有零排放等優勢，代表了未來的發展方向。研究考慮純電動車的集貨運輸活動，對于減少集貨過程中的碳排放具有積極的意義。

大部分學者將集貨問題歸結于車輛路徑問題（Vehicle Routing Problem，VRP）進行研究。文獻[1]利用禁忌搜索和自適應大鄰域搜索構造了一個新的啟發式算法來解決容量化的車輛路徑問題，文獻[2]用人工蜂群算法解決交通擁堵導致車輛路徑效率低下的問題。在低碳集貨問題方面，文獻[3]通過改進遺傳算法求解考慮碳排放因素的VRP問題。文獻[4]研究了具有固定車輛數的多車型低碳路徑問題，實驗分析表明，采用固定車輛數的多車型低碳路徑問題比傳統安排更加經濟環保。

以往的研究大多把汽油車或柴油車作為研究對象，考慮新能源車特別是純電動貨車的研究較少。本文研究了同時具有傳統柴油車和純電動車的集貨問題，并針對當今技術條件下純電動車裝載量小、續航里程短的特點，建立最短距離和最小碳排放的多目標優化模型，進而采用基于遺傳算法和啟發式節約算法的兩階段算法進行求解，通過純電動車的有效利用尋找同時滿足環境效益和經濟效益的集貨方案。

1 ?問題描述與建模

1.1 ?問題描述

本文所研究的考慮新能源貨車的集貨模型可描述為：配送中心派遣一組車輛前往供貨商處取貨，然后返回配送中心，目標是找到總路徑最短和碳排放量最小的集貨方案。集貨過程中的約束如下：

1） 配送中心約束：所有車輛由配送中心駛出，完成取貨任務后返回配送中心;

2） 車輛約束：配送中心有多車型的貨車，每種車型的數量和參數已知;

3） 訪問唯一性約束：每個供貨商只能被一輛車一次性服務;

4） 載重約束：每種類型車輛的裝載量需滿足該車型的容量限制;

5） 載運距離約束：每種車型車輛的行駛距離不能超過該車型的最大行駛距離;

6） 時間窗約束：供貨商只能在規定的時間窗內被車輛服務，如果車輛到達的時間早于最早開始服務時間，車輛將在供貨商處等待，如果車輛在最晚開始服務時間之后到達，則產生不可行解;

7） 裝貨時間約束：車輛到達供貨商后需完成裝貨過程，裝貨時間固定且已知;

8） 速度約束：行駛過程中所有車輛以相同的速度勻速行駛。

1.2 ?符號和決策變量

[G=（V，E）]：物流配送網絡;[V]表示定點，即配送中心或供貨商;[E]表示弧集即頂點間的路徑集合，[E=（i，j）i，j∈V，i≠j]。

[P]表示路徑，[VP]表示路徑[P]的點集合;[Dij]表示弧[（i，j）]的距離;[Tij]表示弧[（i，j）]的運輸時間;[ST]表示系統開始的時間;[UTi]表示供貨商[i]的裝貨時間;[[ETi，LTi]]為供貨商[i]的時間窗，[ETi]為最早開始服務時間，[LTi]為最晚開始服務時間。

[k]表示車輛集合，[Lk]表示車輛[k]的最大行駛距離;[Qijk]表示車輛[k]在從[i]發往[j]的過程中的載重。

表7中的總費用分別由式（21）和式（22）計算得到，因為所用成本系數不同，所以沒有可比性。由表5和表6對比可知，在以總費用最小為目標優化集貨問題時，即使針對同一問題，當費用組成中的成本系數不一致時也會得出不一樣的路徑方案。如今還沒有公認的成本系數，大多數研究只能針對所研究的現實問題設計符合自身問題的成本系數，而成本系數的設定直接影響最終方案的產生。本文為了消除成本系數的影響，尋找更具通用性的模型和算法，采用兩階段的計算方法，首先在階段1解決最短路徑問題，然后在階段2集貨方案的基礎上進行路徑的拆分重組，尋找碳排放更少的集貨方案。由于階段2集貨方案是在階段1解的基礎上得到的，因此階段2的集貨方案同時考慮了路徑和碳排放的影響。案例中階段2的結果相比于階段1，距離僅增加了74 km，碳排放降低了125 kg，在最短距離方案的基礎上降低碳排放量，優化環境效益是切實可行的。

4 ?結 ?論

本文考慮純電動車的多車型集貨問題，將路徑優化和最小碳排放量結合起來，建立統一的多目標優化模型。為了尋找具有通用性的計算方法，根據模型特征，本文設計了分階段算法進行求解。首先用遺傳算法解決最短車輛路徑問題，產生初始集貨方案;進而基于節約算法的基本思想對方案中的路徑進行拆分和重組，通過新能源電動貨車和傳統柴油貨車的統一調度和有效利用，得到更為低碳的集貨方案。實例中拆分重組后的集貨方案較之前降低了125 kg碳排放量，可以看到本文提出的模型和算法是有效的。

參考文獻

[1] SENA K， HARUN R Y， EMRE T. A novel heuristic algorithm for capacitated vehicle routing problem [J]. Journal of industrial engineering international， 2017， 13（3）： 323?330.

[2] LEE C K M，WU K，WILLIAM H， et al. A multiple colonies artificial bee colony algorithm for a capacitated vehicle routing problem and re?routing strategies under time?dependent traffic congestion [J]. Computers & industrial engineering， 2017， 5（4）： 151?168.

[3] 邱雅君，宋國防.考慮碳排放因素的車輛路徑問題研究[J].物流技術，2012（13）：226?229.

QIU Yajun， SONG Guofang. Study on carbon emissions consi?dered VRP [J]. Logistics technology， 2012（13）： 226?229.

[4] 李進，傅培華.具有固定車輛數的多車型低碳路徑問題及算法[J].計算機集成制造系統，2013，19（6）：1351?1362.

LI Jin， FU Peihua. Heterogeneous fixed fleet low?carbon rou?ting problem and algorithm [J]. Computer integrated manufactu?ring systems， 2013， 19（6）： 1351?1362.

[5] 史春陽，趙磊.同時取送貨的車輛路徑問題中的低碳研究[D].北京：清華大學，2011.

SHI Chunyang， ZHAO Lei. The low carbon study of the take and delivery vehicle routing problem [D]. Beijing： Tsinghua University， 2011.

[6] 雷英杰，張善文.Matlab遺傳算法工具箱及應用[M].西安：西安電子科技大學出版社，2014：82?84.

LEI Yingjie， ZHANG Shanwen. Application of Matlab genetic algorithms toolbox [M]. Xian： Xidian University Publishing House， 2014： 82?84.

[7] UBEDA S， ARCELUS F J， FANLIN J. Green logistics at Eroski： a case study [J]. International journal of production economics， 2011， 131： 44?51.

[8] 李進，傅培華，李修琳，等.低碳環境下的車輛路徑問題及禁忌搜索算法研究[J].中國管理科學，2015，23（10）：98?106.

LI Jin， FU Peihua， LI Xiulin， et al. Study on vehicle routing problem and tabu search algorithm under low?carbon environment [J]. Chinese journal of management science， 2015， 23（10）： 98?106.

[9] 張津.考慮碳排放的帶時間窗約束的車輛路徑問題研究[D].重慶：重慶大學，2016.

ZHANG Jin. Vehicle routing problem with time windows constraint considering carbon emission [D]. Chongqing： Chongqing University， 2016.

[10] 葛顯龍，許茂增，王偉鑫.多車型車輛路徑問題的量子遺傳算法研究[J].中國管理科學，2013，21（1）：125?133.

GE Xianlong， XU Maozeng， WANG Weixin. Study on multi?types vehicle routing problem and its quantum genetic algorithm [J]. Chinese journal of management science， 2013， 21（1）： 125?133.