基于拆分運輸?shù)牡吞架囕v路徑優(yōu)化

李雙艷 ，王忠偉 ，張得志

(1. 中南林業(yè)科技大學 交通運輸工程與物流學院，湖南 長沙 410004；2. 中南林業(yè)科技大學 林業(yè)工程博士后流動站，湖南 長沙 410004；3. 中南大學 交通運輸工程學院，湖南 長沙 410075)

車輛運輸過程會耗費大量的能源，產(chǎn)生大量碳排放。從運作管理角度，優(yōu)化車輛路徑安排降低其排放是現(xiàn)代物流運輸企業(yè)改善運輸環(huán)境績效的必要手段，也是實現(xiàn)綠色、高效物流的一個重要方法。對于低碳車輛路徑問題，Tajik等[1]給出考慮總油耗和溫室氣體排放有時間窗約束的取貨車輛路徑模型。ZHANG等[2]采用二氧化碳排放與載重函數(shù)關(guān)系進行環(huán)境車輛路徑問題的建模。Demir等[3]分別對有時間窗和無時間窗約束的污染路徑問題(PRP，Pollution Routing Problem)建立數(shù)學模型，并分析車輛裝載量和總費用的關(guān)系。李進等[4]建立碳排放交易機制下的物流配送路徑優(yōu)化模型，指出與僅考慮經(jīng)濟成本的模型相比，碳排放限額交易機制能夠有效促使企業(yè)減少碳排放，但可能會帶來企業(yè)成本的上升。唐金環(huán)等[5]以城市貨的為例，建立考慮旅行時間和碳排放量的多目標車輛路徑問題模型。陳玉光等[6]構(gòu)造基于準時送貨與最小化耗油的配送車輛路徑模型，給出最小油耗及最小越界時間懲罰帕累托解集。楊培穎等[7]以最小碳排放量為目標，對現(xiàn)實接送機場服務運作中的車次分配與調(diào)度問題進行優(yōu)化求解。低碳車輛路徑問題是NP-Hard問題，很難由精確算法獲取最優(yōu)解，一般采用啟發(fā)式算法進行求解，Bektas等[8]建立排放污染路徑問題(Pollution-Routing Problem)的數(shù)學模型，給出包含碳排放費用的運輸優(yōu)化方法。Kramer等[9]研究低排放的車輛路徑問題的元啟發(fā)式求解方法。降低運輸過程碳排放與提高車輛運輸效率是密切相關(guān)的。而拆分運輸是提高車輛裝載率和運輸效率的模式之一。拆分運輸允許多條路徑訪問同一個需求點，并且由這幾條路徑來共同承擔該點的需求。因此也就放寬了一般 VRP 問題中對于車輛容量要大于需求點送貨或取貨需求量的要求。需求可拆分的車輛路徑問題(Split Delivery VRP)最早由 Dror等[10]提出。Archetti等[11]提出局部搜索算法，并驗證當任務點需求量較大時 SDVRP得到的結(jié)果明顯優(yōu)于VRP。劉新宇等[12]對需求可拆分車輛路徑問題的研究進行了總結(jié)，說明需求可拆分的取送貨車輛路徑問題研究的必要性?；诓鸱诌\輸?shù)牡吞架囕v路徑問題具有實際的應用前景。如生物質(zhì)電廠的生物質(zhì)燃料運輸、一日多配的快遞包裹運輸?shù)?。但對拆分運輸模式下低碳車輛路徑問題研究還很欠缺。本文在國內(nèi)外研究的基礎(chǔ)上，采用拆分需求運輸?shù)姆绞?，建立多車多次，單點多次的低碳車輛路徑優(yōu)化模型，設(shè)計符合拆分約束的重定位禁忌搜索算法求解算法。分析車型和拆分對運輸碳排放的影響，給出可執(zhí)行的運輸減排建議，從而促進低碳運輸和低碳物流發(fā)展。

1　問題描述

本文研究的拆分運輸?shù)吞架囕v路徑問題是車輛路徑問題的一個擴展，其優(yōu)化目標是運輸過程中的總碳排放量最小，而不是距離最小或時間最短。由于車輛碳排放與車輛載重及距離均相關(guān)。因此該類車輛路徑問題中，需求點訪問的順序、需求點的載/卸貨量都是決策變量。如圖1，將拆分運輸?shù)淖钚√寂跑囕v路徑問題定義在有向拓撲圖中，車場安排一定數(shù)量、固定類型車輛通過有向網(wǎng)絡到各個需求點進行貨物集派，然后返回。各需求點的運輸可以進行拆分，車輛在每次集派時，其裝載重量不能超過其最大載重，決策目的是確定每輛車輛的行程路徑及每個需求點集派貨物量，以最小化拆分運輸?shù)奶寂欧拧?/p>

圖1　拆分運輸車輛路徑問題示意圖Fig.1　Schematic diagram of split delivery vehicle routing problem

2　數(shù)學模型

2.1　符號定義

輸入?yún)?shù)：dij表示節(jié)點i和j之間的車程距離；k表示特定燃料的碳排系數(shù)；m表示參與運輸?shù)能囕v數(shù)；C表示車輛的最大載重量，所有車輛最大載重量相等；qi表示收購站點 i的需要運輸?shù)呢浳镏亓?；a表示車輛單位周轉(zhuǎn)量油耗系數(shù)，單位：L/(t·km)；b表示車輛空載油耗量，單位：L/km。

決策變量：Xvij表示從i到j的有向路段是否屬于車輛v行駛路段，為0-1變量；Yvij表示從i到j的有向路段上車輛 v的裝載量，為連續(xù)變量；Zvij表示從i到j的有向路段上車輛v的剩余裝載量，為連續(xù)變量。

根據(jù)英國交通部對油耗與載重量關(guān)系的研究,車輛的油耗與載重可以簡化為線性關(guān)系：

其中：Q為貨物載重；a為車輛的油耗系數(shù)；b為車輛空載油耗。這樣對于一定類型的車輛，若已知載重量，可以根據(jù)對應的油耗技術(shù)參數(shù)，計算單位里程的油耗量，然后乘以碳排放系數(shù)和行駛里程，得到碳排放量 F (Q ) = k (a Q + b )d。

2.2　模型表示

構(gòu)建對應的車輛路徑數(shù)學模型，目標函數(shù)(1)為非線性函數(shù)，包含了車輛載重和行駛路段長度的積。

約束式(2)表示每輛車必須從1點發(fā)出，(3)表示每輛車必須回到1點，(4)表示到達每個點的車輛數(shù)大于等于1。(5)表示每個點發(fā)出的車輛數(shù)必然等于到達的車輛數(shù)。(6)表示從1點出發(fā)時所有車輛的載重量總和為零，即空載。(7)表示任何回到1點的車輛載重量的邊界約束。(8)表明對每個節(jié)點而言，所有發(fā)出車輛的載重和與流入車輛的載重和之差為該點的取貨量qi，即拆分約束。(9)表明對于每輛車而言，在每個路段上的載重量和剩余載重量和必然為CXvij。(10)是每條路段上的車輛裝載量約束。該模型針對集貨問題，配貨問題模型與之對稱。

3　求解算法

3.1　算法流程

Lensatr等[13]證明了幾乎所有類型的VRP均為NP一難問題。因此，拆分運輸?shù)吞架囕v路徑問題也是NP-hard問題。其優(yōu)化目標碳排放量是車輛運輸距離和車輛載重二類變量的非線性函數(shù)。需要求出各個站點的拆分量及其分派的車輛，所有車輛的路徑。該問題決策變量有2類，求解變量較傳統(tǒng)的車輛路徑問題有所增加，求解復雜度高。為了在有限的時間內(nèi)求解出“可接受”的最佳近似解，采用元啟發(fā)算法進行求解。將求解過程分為2個階段。第1個階段解采用貪婪插入法生成初始可行解。第2階段采用禁忌搜索迭代優(yōu)化初始解。當允許拆分生物質(zhì)收集點的收集量分派給不同車輛時，車輛的利用率會增大。最少車輛需求為M。

算法流程如下。

Step 1：初始化，車輛剩余裝載容量為 C，收集站點i的秸稈量為qi；

Step 2：將收集站點按照秸稈數(shù)量大小降序 排序；

Step 3：車輛到排序最前的收集站裝載秸稈；

Step 4：根據(jù)貪婪插入方法在路線中依次添加其他收集站點裝載秸稈，更新車輛剩余裝載容量和收集站點的秸稈量值；

Step 5：判斷車輛的剩余裝載容量是否為0，若是，使用車輛數(shù)增加1，并跳至Step 6。否則，跳到Step 4；

Step 6：判斷車輛全部使用否，即使用車輛數(shù)是否為M，若是則循環(huán)結(jié)束，否則，跳到Step 2；

Step 7：重定位算子產(chǎn)生的候選解；

Step 8：進行選優(yōu)、禁忌和解禁操作，并更新禁忌表和最優(yōu)解；

Step 9：滿足終止條件，算法停止。

3.2　重定位算子

生物質(zhì)收集具有大批量，節(jié)點密集的特點，必須進行拆分收集。在產(chǎn)生候選解過程中應考慮車輛容限和收集序列。對應設(shè)計2類重定位算子，一類是部分重定位操作，另一類為整體重定位操作。假設(shè)i為路徑r1中的一個節(jié)點，車輛在該點的裝載量若為δi,r1。將該收集任務重新分配給r2，其分配量為，當r2路徑對應的車輛剩余容量小于δi,r1，則原收集任務部分轉(zhuǎn)派給r2，重新定位i到r2，派量為 Qr2- Lr2。否則，原收集任務全部轉(zhuǎn)派給r2，重新定位i到r2，派量為δi,r1，如圖2所示。在進行候選解選優(yōu)時，根據(jù)目標函數(shù)進行計算，包括距離和路段載重對碳排放的影響。

圖2　重定位算子Fig.2　Relocation operation

4　實例仿真

4.1　仿真數(shù)據(jù)

為了研究上述優(yōu)化模型及其算法的有效性，以湖南省衡陽祁東縣凱迪生物質(zhì)發(fā)電廠為例，計算其收集運輸?shù)淖钚√寂怕窂?。祁東凱迪生物質(zhì)發(fā)生物質(zhì)發(fā)電廠項目座落在湖南省祁東縣經(jīng)濟開發(fā)區(qū)工業(yè)園，由武漢凱迪控股投資有限公司投資建設(shè)，占地面積250畝，總建設(shè)規(guī)模為2×12 MW機組，配2臺48 t/h生物質(zhì)鍋爐。生物質(zhì)發(fā)電廠年燃料需求量27.611 4萬t，年運行300 d，年運行時間7 200 h，日需求量為 920.48 t，燃料來源是祁東縣所管轄的鄉(xiāng)鎮(zhèn)。祁東縣轄19個鎮(zhèn)、4個鄉(xiāng)，各個鄉(xiāng)鎮(zhèn)設(shè)燃料收購站點。根據(jù)交通路網(wǎng)數(shù)據(jù)可獲得各鄉(xiāng)鎮(zhèn)之間的運輸距離。運輸車輛的類型根據(jù)運輸生物質(zhì)的重量確定，生物質(zhì)發(fā)電廠對生物質(zhì)需求量大，各收購站點的燃料重量都超過了 18 t，且多數(shù)站點燃料重量大于 30 t，甚至高達 74 t，因此要選用大噸位的牽引拖車進行運輸。根據(jù)車輛空載等速燃料消耗量、綜合燃料消耗量，可以得出不同的車型的油耗相關(guān)系數(shù)見表1。不同的車型車輛油耗系數(shù)a和空載油耗b不一樣，見表1。仿真采用MATLAB7.2數(shù)值仿真軟件編程，在3.20 GHz 主頻、1.96 G 內(nèi)存、Windows 7操作系統(tǒng)平臺進行運算。

4.2　結(jié)果與分析

采用型號ZZ4251N3241C的牽引拖掛車運輸生物質(zhì)燃料時，仿真結(jié)果如表2和圖3所示。為了驗證基于拆分運輸?shù)牡吞架囕v路徑模型和算法的有效性，同時計算了拆分運輸下距離最優(yōu)的結(jié)果，即表3中情形2。說明低碳車輛路徑模型和距離最小車輛路徑模型的不同。情形1為基本情形，是以碳排量為優(yōu)化目標。情形2是以行駛總距離為優(yōu)化目標。而情形3以碳排量為優(yōu)化目標，但油耗系數(shù)a擴大10倍。情形4也是以碳排量為優(yōu)化目標，其中空載油耗b擴大10倍。以車型1為例，在情形1下得出的仿真收集路線及其收斂情況如圖3和圖4。

表1　車輛技術(shù)參數(shù)Table1　Technical parameters of delivery vehicles

圖3　情景1下的需求拆分的車輛路徑安排Fig.3　Vehicle routing with split demand under scenario 1

圖4　情景1算法收斂曲線Fig.4　Algorithm convergence curve under scenario 1

表2　情形1下拆分收集運輸安排Table2　Vehicle schedule with split demand under scenario 1

表3　ZZ4251N3241C車型生物質(zhì)燃料運輸?shù)牟煌瑑?yōu)化目標的對比分析Table3　Comparative analysis of optimal solutions for different optimal objectives based on ZZ4251N3241C vehicle

仿真還對其他2種車型進行了優(yōu)化。表4是3種不同載重的牽引拖掛車對應的總碳排和總運輸距離的優(yōu)化結(jié)果對比。3種車載重分別為24.2，27.2和33 t。其載重量逐漸增大，空載油耗b也隨之增大，而油耗系數(shù)a則逐漸減小，最少需要的運輸次數(shù)減少。

表4　3種車型優(yōu)化計算結(jié)果對比Table4　Comparative analysis of optimal solutions for different vehicle types

對不同車型，統(tǒng)計各收集站運拆分次數(shù)的情況如圖5所示。對最小容量的車型ZZ4251N3241C，在情形1下，其被分割次數(shù)最多的是收集站3，情形2下，分割次數(shù)最多的是收集站3，10和11。情形3和4下，其被分割次數(shù)最多的是收集站3。即路徑優(yōu)化目標的拆分頻次比碳排優(yōu)化目標的要多。

在情形 1下，ZZ4181N361GD1(車型 2)和ZZ4259M28CCC1B(車型 3)分割次數(shù)最多的是收集站為3，10和11。且單次完成收集運輸?shù)目蛻酎c數(shù)相比容量小的車型(車型1)減少?？梢婋S著車載容量的提升，分割點增多且有向生物質(zhì)發(fā)電廠靠近的趨勢。

綜上可分析得出：1) 碳排總量和運輸總距離為優(yōu)化目標的2種情況對比。發(fā)現(xiàn)兩者碳排總量區(qū)別不大，為4.248%，距離變化則更小，不到1%，這是因為油耗因子都比較小的原因。而情況1下車輛的載重量更為平均，載重均方差為8.01。情況2的則為23.35。

2) 單位油耗系數(shù)a和空載油耗b影響分析。分別增大單位油耗系數(shù)和空載油耗 10倍的結(jié)果見表3，其碳排相對基本情形(1)的變化為 233.11%和663.44%，顯然空載油耗變化對碳排的影響更大。增大空載油耗系數(shù)時，各個車輛載荷也更為平均，車輛的載重方差為7.52。而增大單位油耗系數(shù)時，車輛的載重均方差為 12.90，且其優(yōu)化結(jié)果的行駛距離和碳排都會有所增加。以上結(jié)果表明碳排優(yōu)化決策使車輛路徑安排趨向載重均衡，而距離最短優(yōu)化決策不具有此特點。

3) 路徑點訪問順序分析。對于多點服務路徑而言的，在每條路徑中，距離生物質(zhì)發(fā)電廠最短的客戶點安排在最后訪問。如路徑[0, 10, 12, 1, 0]，其中各個點距離生物質(zhì)發(fā)電廠的距離為12.6，37.7，7.1 km。再如路徑[0, 18, 21, 0]，其中各個點距離生物質(zhì)發(fā)電廠的距離為56.9，51.9 km。這是因為在集貨運輸過程中，載重量是不斷增加的，是遞增的，為了降低碳排，會形成重載短程現(xiàn)象。即把距離短客戶點的安排靠后。也就是說在同一條路線不同的訪問順序(順時針、逆時針)的油耗存在差異，最短路不存在該特點。

4) 拆分特點分析。從結(jié)果可見，距離生物質(zhì)發(fā)電廠較遠的且集貨量小于車載容量的收購站點，運輸是單趟完成的，不進行拆分。如收購站點編號為20，21，22的點距離生物質(zhì)發(fā)電廠的距離分別為72.8，51.9和69.7 km。其貨物量分別為19.66，19.81和18.26 t，均小于車載容量。根據(jù)結(jié)果，可以發(fā)現(xiàn)20和22號收購站的集貨單次完成，21號收購站的集貨分2次拆分完成。

5) 隨著車輛載重的增大，單位距離碳排減小，空載碳排增大，碳排放總量減小，行駛總距離也減小。如車型1和車型3的碳排總量相差128.36，減小了20.59%。載重量越大的車型碳排量越小，環(huán)保性能也越好。

圖5　運輸拆分次數(shù)分析結(jié)果Fig.5　Result analysis of split times of the corresponding demand

5　結(jié)論

1) 由于碳排總量為優(yōu)化目標可以降低運輸過程的碳排，同時與最短路結(jié)果的總行駛距離差別很小，企業(yè)在安排生物質(zhì)集貨運輸時，以碳排總量為優(yōu)化目標更為有效。

2) 由于碳排放與載重距離均有關(guān)系，所以不同于最短路，同一條路線不同的訪問順序(順時針、逆時針)的油耗存在差異，對于多點服務路徑安排，應將距離生物質(zhì)發(fā)電廠最短的客戶點安排在最后。

3) 對于距離生物質(zhì)發(fā)電廠較遠的且集貨量小于車載容量的收購站點，運輸盡量單趟完成，不進行拆分。對于距離生物質(zhì)發(fā)電廠較遠但集貨量大的收購站點，應優(yōu)先滿足其運輸需求。

4) 隨著車輛載重的增大，單位距離碳排減小，碳排放總量和行駛的單位總距離也減小。所以如果路段負重允許條件下，盡可能使用載重量大的車型。