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

史雨同 尹靜 王柏琳

關(guān)鍵詞： 制造供應鏈; 碳排放; 新能源車; 集貨模型; 路徑優(yōu)化; 遺傳算法; 節(jié)約算法

中圖分類號： 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 ?引 ?言

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

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

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

1 ?問題描述與建模

1.1 ?問題描述

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

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

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

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

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

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

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

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

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

1.2 ?符號和決策變量

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

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

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

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

4 ?結(jié) ?論

本文考慮純電動車的多車型集貨問題，將路徑優(yōu)化和最小碳排放量結(jié)合起來，建立統(tǒng)一的多目標優(yōu)化模型。為了尋找具有通用性的計算方法，根據(jù)模型特征，本文設(shè)計了分階段算法進行求解。首先用遺傳算法解決最短車輛路徑問題，產(chǎn)生初始集貨方案;進而基于節(jié)約算法的基本思想對方案中的路徑進行拆分和重組，通過新能源電動貨車和傳統(tǒng)柴油貨車的統(tǒng)一調(diào)度和有效利用，得到更為低碳的集貨方案。實例中拆分重組后的集貨方案較之前降低了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].物流技術(shù)，2012（13）：226?229.

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

[4] 李進，傅培華.具有固定車輛數(shù)的多車型低碳路徑問題及算法[J].計算機集成制造系統(tǒng)，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] 李進，傅培華，李修琳，等.低碳環(huán)境下的車輛路徑問題及禁忌搜索算法研究[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.