基于 CO2排放的車輛路徑優(yōu)化模型及其算法研究

張得志，錢奇，李雙艷，靳方平

（1.中南大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長沙 410075；2.中南林業(yè)科技大學(xué) 交通運(yùn)輸與物流學(xué)院，湖南 長沙 410004）

基于 CO2排放的車輛路徑優(yōu)化模型及其算法研究

張得志1，錢奇1，李雙艷2，靳方平1

（1.中南大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長沙 410075；2.中南林業(yè)科技大學(xué) 交通運(yùn)輸與物流學(xué)院，湖南 長沙 410004）

物流不僅是能源消耗大戶，同時(shí)也是 CO2排放的重要來源。在分析配送車輛燃油消耗和 CO2排放因素的多種車輛類型車輛路徑問題特點(diǎn)的基礎(chǔ)上，構(gòu)建其相應(yīng)的優(yōu)化模型，并給出基于遺傳算法的啟發(fā)式求解算法。最后，針對(duì)該模型和求解算法進(jìn)行數(shù)值算例仿真，研究結(jié)果顯示：路徑最短的路線不一定是能耗最小的路線；與傳統(tǒng)基于路徑最短的車輛路徑對(duì)比，基于 CO2排放的車輛路徑總行駛里程較長，但其綜合成本較低；遺傳算法是解決綠色車輛路徑問題的一個(gè)有效的求解算法。

物流能耗；CO2排放；車輛路徑；優(yōu)化模型；遺傳算法

物流活動(dòng)包括貨物運(yùn)輸，存儲(chǔ)，庫存管理，物料搬運(yùn)，以及所有相關(guān)的信息管理過程。物流的目標(biāo)是協(xié)調(diào)這些活動(dòng)，以最小的成本滿足客戶的需求。過去，這種成本純粹定義為貨幣成本?？紤]到環(huán)境壓力的上升，企業(yè)必須更多的考慮物流活動(dòng)的外部性，這其中涉及到氣候變化、空氣污染、噪聲、振動(dòng)和事故等。

根據(jù)2010年能源交通報(bào)告，2008年美國交通運(yùn)輸業(yè)所排放的二氧化碳占二氧化碳總排放量的31.05%，超過工業(yè)、商業(yè)及居民的二氧化碳排放總量，是最大的二氧化碳產(chǎn)生源。根據(jù)歐洲環(huán)境局2011年發(fā)布的TERM2011報(bào)告，2009年在歐盟27個(gè)國家中，運(yùn)輸（包括國際海運(yùn)）占全部溫室氣體排放總量的24%，其中，公路運(yùn)輸占溫室氣體排放總額的 17%［1］。而在物流活動(dòng)中，公路運(yùn)輸占到了80%以上。由此可見，發(fā)展低碳經(jīng)濟(jì)必須要首先優(yōu)化交通運(yùn)輸。實(shí)現(xiàn)低碳運(yùn)輸?shù)囊粋€(gè)方法就是優(yōu)化運(yùn)輸線路，減少碳排放。因此，本文側(cè)重于研究公路運(yùn)輸在組織車輛路徑的過程中，如何減少CO2排放，減少對(duì)環(huán)境的危害。綠色車輛路徑研究的目的就是研究減少運(yùn)輸外部性的方法，在經(jīng)濟(jì)、社會(huì)、環(huán)境目標(biāo)之間取得更加持續(xù)性的平衡。

車輛路徑問題（Vehicle Routing Problem，VRP）最早由 Dantzig和 Ramser［2］于1959年提出，之后產(chǎn)生了這一問題的許多變種，例如多車型車輛路徑問題［3-5］、多 車 場(chǎng) 車輛路徑 問 題［6-7］、開 放 式車輛路徑問題和動(dòng)態(tài)車輛路徑問題等［8-10］。

上述經(jīng)典的車輛路徑研究文獻(xiàn)中，其目標(biāo)函數(shù)大多是最小化運(yùn)輸成本或者運(yùn)輸距離，其中，運(yùn)輸成本一般包括 2個(gè)方面的內(nèi)容，其一為車輛的啟動(dòng)成本，包括車輛的使用費(fèi)、折舊、司機(jī)工資等；其二為車輛的行駛費(fèi)用，一般文獻(xiàn)中設(shè)定為行駛距離的線性函數(shù)。但是隨著社會(huì)的發(fā)展，“綠色物流”的概念逐漸深入人心，在考慮行駛成本的同時(shí)，有必要考慮 CO2排放對(duì)社會(huì)的作用。因此，我們需要綜合考慮油耗和 CO2排放對(duì)車輛路徑的影響。

王明陽等［11］建立了帶油耗的單車場(chǎng)開放式車輛路徑問題。另外，國家發(fā)改委和財(cái)政部已經(jīng)形成了“中國碳稅稅制框架設(shè)計(jì)”的專題報(bào)告，表示我國碳稅將在未來若干年內(nèi)推出?？紤]到碳稅的計(jì)費(fèi)依據(jù)是二氧化碳排放量，根據(jù)《2006年 IPCC國家溫室氣體清單指南》提供的方法，二氧化碳排放量的計(jì)算公式為：單位化石燃料二氧化碳的估算值=低位發(fā)熱量 ×碳排放因子 ×碳氧化率 ×碳轉(zhuǎn)換系數(shù)，本文采用的碳稅成本為每 20元/t［12］。

因此，本文在車輛路徑問題的研究中同時(shí)考慮油耗和碳排放兩個(gè)因素，構(gòu)建基于 CO2排放的車輛路徑優(yōu)化模型，并對(duì)比分析了考慮 CO2排放外部成本的車輛路徑優(yōu)化和傳統(tǒng)車輛路徑優(yōu)化，探索適應(yīng)綠色車輛路徑優(yōu)化的規(guī)律和管理啟示。

1 問題描述與數(shù)學(xué)建模

1.1 問題描述

本研究同時(shí)考慮油耗和碳排放的單車場(chǎng)多車型閉合式綠色車輛路徑問題。問題的描述如下：只有1個(gè)車場(chǎng)，車場(chǎng)中有 L種不同類型的車輛（每種車輛足夠多），每種車輛具有不同的容量、固定成本、單位燃油消耗、碳排放因子。該車場(chǎng)服務(wù) N個(gè)客戶點(diǎn)，每個(gè)客戶點(diǎn)的坐標(biāo)位置已知，需求量已知。配送車輛從車場(chǎng)裝上貨物出發(fā)，為 N個(gè)客戶送貨，要求每個(gè)客戶只由1輛車為其完成送貨任務(wù)，車輛將貨物運(yùn)送完畢后回到車場(chǎng)。被派出完成配送任務(wù)的配送車輛，其總費(fèi)用由 3部分組成：車輛的固定成本、燃油消耗費(fèi)用和車輛排放 CO2的外部成本。該問題的優(yōu)化目標(biāo)是：在綜合考慮車輛運(yùn)行費(fèi)用（含固定成本和變動(dòng)成本）與碳排放的環(huán)境成本情況下，如何合理配置車輛及安排各車輛配送線路，使得總成本最小。

1.2 數(shù)學(xué)建模

符號(hào)及決策變量說明：

N=［0，1，2，…，n］表示客戶點(diǎn)；其中0表示車場(chǎng)，1到 n表示可用車輛的類型；kl表示第 l型車的數(shù)量；ql表示第l型車的容量；sij表示客戶點(diǎn) i和j之間的距離；di表示客戶點(diǎn) i的需求量；c表示單位體積的油價(jià)；fl表示第 l型車輛的單位油耗；tl表示第 l型車輛的排放因子；gl表示第 l型車的固定使用成本；λ表示單位 CO2排放外部成本。

目標(biāo)函數(shù)可以表述為如下：

相應(yīng)的約束條件為：

在上述模型中，公式（1）是目標(biāo)函數(shù)，表示車輛燃油成本、車輛使用固定成本、車輛的碳排放成本；公式（2）確保每條線路的載重量不超過車輛的容量要求；公式（3）表示對(duì)于每個(gè)顧客，有且僅有1輛車為它服務(wù)；公式（4）表示到達(dá)每個(gè)客戶只有 1輛車；公式（5）表示離開每個(gè)客戶只有 1輛車；公式（6）表示離開車場(chǎng)的車輛和回到車場(chǎng)的車輛相等，即所有車輛從車場(chǎng)出發(fā)，最后又回到車場(chǎng)；公式（7）和公式（8）表示0-1整數(shù)約束，分別表示車輛訪問順序與車輛選擇。

1.3 求解算法分析

對(duì)于多車型車輛路徑問題（Fleet Size and Mixed Vehicle Routing Problem，F(xiàn)SMVRP），由于基本的VRP是NP完全問題，因此，F(xiàn)SMVRP也是NP完全問題。另外，由于 FSMVRP中的車輛類型不同，因此，F(xiàn)SMVRP比基本 VRP的求解更加困難和復(fù)雜。FSMVRP的研究還處于初步階段，目前尚沒有求解該問題的精確算法。因此本文采用遺傳算法求解。

遺傳算法（Genetic Algorithm，GA）最初由美國Michigan大學(xué) J.Holland教授于1975年首先提出，它是一種概率搜索算法，具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。遺傳算法的這些性質(zhì)，已被人們廣泛地應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、信號(hào)處理、自適應(yīng)控制和人工生命等領(lǐng)域。

1）染色體結(jié)構(gòu)

遺傳算法以編碼的方式將解空間映射為遺傳空間，將可能的解編碼為一個(gè)向量，稱為一個(gè)染色體或者個(gè)體。因此，解的編碼方法很大程度上決定了解空間的搜索方向。本文采用客戶與虛擬物流中心共同編碼的方法來表示一個(gè)可能的解。例如（以10個(gè)城市為例）：

表示1輛車從配送中心出發(fā)，依次服務(wù)第 1，3，5號(hào)客戶后返回配送中心，然后另 1輛車從配送中心出發(fā)依次服務(wù)第2，6，8，4號(hào)客戶后返回，第3輛車從配送中心出發(fā)依次服務(wù)第7，9和10號(hào)客戶后返回。

2）初始種群

初始種群的生成方法是在客戶隨機(jī)全排列的兩端及中間插入若干數(shù)量的虛擬配送中心，即生成一個(gè)若干車輛服務(wù)全部所有客戶的初始解，因?yàn)殡S機(jī)生成的解，必然有一部分是不符合約束條件的，因此，需要根據(jù)車輛載重能力修正初始解，直到所有初始解滿足條件位置。

3）適應(yīng)度函數(shù)

由于目標(biāo)函數(shù)是基于車輛固定成本、燃油消耗成本和 CO2排放成本構(gòu)成的綜合成本最??；因此，簡單起見，適應(yīng)度函數(shù)可以取目標(biāo)函數(shù)的倒數(shù)。

4）遺傳算子

選擇算子：采用保存最佳策略的輪盤賭法來選擇個(gè)體。

交叉算子：由于編碼的特點(diǎn)決定染色體組間無序（車輛的前后順序）、組內(nèi)有序（車輛的訪問順序），因此，若采用傳統(tǒng)的部分匹配交叉，可能會(huì)破壞解的優(yōu)良特性。因而，本文利用參考文獻(xiàn)［13］中提供的交叉方法。具體過程為：①如果染色體交叉點(diǎn)處有0，就直接采用部分匹配交叉的方法；②如果染色體交叉點(diǎn)處沒有0，就將交叉點(diǎn)向后移動(dòng)直到出現(xiàn)0，再采用部分匹配交叉的方法。

變異算子：采用2點(diǎn)交換作為染色體變異的算子。隨機(jī)選擇染色體的2點(diǎn)，交換這2個(gè)點(diǎn)位上的基因。若染色體中出現(xiàn)連續(xù)的0，表示變異向良好的方向，減少了所使用的車輛數(shù)。

5）終止條件

因?yàn)檫z傳算法是隨機(jī)搜索算法，很難找到一個(gè)明確的終止條件。為簡單起見，本文設(shè)置一定的進(jìn)化代數(shù)T（一般T∈［100，1 000］），作為算法終止的條件。

6）算法實(shí)現(xiàn)步驟

步驟1：初始化運(yùn)行環(huán)境，配置變量；

步驟2：構(gòu)造染色體，生成初始解空間，并進(jìn)行約束檢查，對(duì)不符合約束條件的解進(jìn)行修正；

步驟3：計(jì)算初始解的適應(yīng)度；

步驟4：gen=1，對(duì)群體進(jìn)行選擇、交叉、變異操作，對(duì)最終生成的子代進(jìn)行約束檢查，使之全部成為可行解；將子代插入父代中，形成新的父代；

步驟5：當(dāng) gen小于指定的終止代數(shù)，返回步驟4，繼續(xù)執(zhí)行；否則，評(píng)價(jià)最后的解，當(dāng)取得最小的目標(biāo)函數(shù)值即滿意解，算法結(jié)束。

2 算例分析

2.1 實(shí)例計(jì)算

假設(shè)某一配送中心為30個(gè)客戶配送貨物，各個(gè)客戶的需求量及坐標(biāo)見表 1及圖 1所示。車場(chǎng)坐標(biāo)為（11，11），該配送中心共有 3種類型配送車輛，每種類型車輛足夠用，各種車輛的運(yùn)行參數(shù)如表2所示。如何合理安排配送車輛的行駛路線，使得包括車輛購置固定成本、燃油費(fèi)和 CO2排放費(fèi)用等綜合配送成本最小。

表1 客戶的坐標(biāo)位置及需求量Table1 Coordinates and demands of customers

圖1 客戶位置示意圖Fig.1 Location of customers

表2 3種車輛的運(yùn)行參數(shù)Table2 Operation parameters of three kinds of vehicles

2.2 結(jié)果分析

針對(duì)算法的性能，記錄其在1 000代中的最優(yōu)解以及均值如圖 2所示，由圖 2可以看出，算法具有較好的收斂性和穩(wěn)定性。

圖2 收斂效果示意圖Fig.2 Convergence effect

1）仿真結(jié)果分析

其中一次的運(yùn)行結(jié)果如下：總成本3 865.8元，碳排放量1 020.1 kg，路徑長度2 197.3 km。共需要7輛車，其中，4輛20 t的車，3輛30 t的車。每輛車的容量為20，30，19，30，18，20和30 t。每輛車的路徑 長 度 為 334.166 6，264.859 8，355.512 7，246.739 5，300.977 2，262.701 3和 432.343 8 km。車輛路徑圖如圖3所示。

圖3 車輛路徑示意圖Fig.3 Vehicle routing

若只考慮行車路徑最短，得出的結(jié)果如下：路徑長度為1 741.4 km，碳排放量為1 403.1 kg。完成配送需要4輛車，即載重50 t的車4輛。每輛車的裝載量為 50，39，48和 49 t。路徑長度分別為320.841 1，333.444 3，554.653 6和542.111 5 km。車輛路徑示意圖如圖4所示。

圖4 車輛路徑示意圖Fig.4 Vehicle routing

2 組數(shù)據(jù)對(duì)比如表3所示。

表3 2種結(jié)果對(duì)比分析Table3 Contrast of two kinds of results

由上面的數(shù)據(jù)可以看出，當(dāng)只考慮路徑最短時(shí)，需要4輛車來完成，總路徑長度為1 741.4 km。碳排放量為 1 403.1 kg。當(dāng)考慮燃油消耗以及碳排放成本時(shí)，需要 7輛車來完成，路徑長度為2 197.3 km，碳排放量1 020.1 kg。

上述數(shù)據(jù)說明，當(dāng)只考慮路徑最短時(shí)，需要盡可能的利用載重量較大的車，本例中使用了4輛50 t的車。當(dāng)考慮燃油消耗時(shí)，由于大車的燃油消耗率過高，導(dǎo)致車輛燃油消耗以及碳排放成本升高，因此利用載重量較小的車來配送成本更低。

由此可以發(fā)現(xiàn)，路徑最短的路線不一定是能耗最小的路線。在本案例中，由于大型車輛的燃油消耗高于中型車輛，因此在優(yōu)化過程中，就選擇了利用中型車輛來完成配送以減輕成本。如上表中的分析，后者比前者的路徑長度增加了 26.18%，然而，碳排放量卻減少了27.3%。

為了更好的說明這個(gè)問題，現(xiàn)在將多車型問題改寫為單車型問題，分 3種車型分別討論：

1）當(dāng)只考慮50 t車型時(shí)，總成本 5 117.2元。路徑長度1 808.6 km，碳排放量1 724.1 kg，車輛裝載分別為37，40，34，50和25 t。

2）當(dāng)只考慮30 t車型時(shí)，總成本 4 580.5元。路徑長度2 156.8 km，碳排放量 875.9 kg，車輛裝載分別為21，28，18，30，16，22，25和26 t。

3）當(dāng)只考慮20 t車型時(shí)，總成本 3 696.9元。路徑長度2 652.8 km，碳排放量717.9 kg，車輛裝載分別為13，10，20，18，17，11，18，6，19，19，19和16 t。

以上3種類型的對(duì)比分析如表4所示。

表4 單一車輛仿真結(jié)果分析Table4 Analysis of simulation results of a single vehicle

以上的數(shù)據(jù)充分說明了當(dāng)考慮最短路徑時(shí)，應(yīng)當(dāng)充分使用載重量較大的車輛來進(jìn)行運(yùn)輸，但如果考慮能耗問題的話，由上面的分析可以發(fā)現(xiàn)大型車輛由于單位距離能耗過大，導(dǎo)致最短的運(yùn)輸路徑并沒有對(duì)應(yīng)于最小的能源消耗。因此，在考慮能耗時(shí)，應(yīng)當(dāng)綜合優(yōu)化，充分考慮各種車輛的能源消耗率以及固定成本等因素。

3 結(jié)論

1）考慮了車輛運(yùn)行過程中CO2排放的外部成本，最優(yōu)車輛路徑與傳統(tǒng)的基于距離或者時(shí)間最短的車輛路徑不一致。

2）基于 CO2排放的車輛路徑優(yōu)化結(jié)果中，其最優(yōu)路徑與車輛屬性、車輛行駛速度和裝載量密切相關(guān)。

3）當(dāng)只考慮路徑最短時(shí)，需要盡可能的利用載重量較大的車；當(dāng)考慮燃油消耗時(shí)，由于大車的燃油消耗率過高，導(dǎo)致車輛燃油消耗以及碳排放成本升高，因此利用載重量較小的車來配送成本更低。

4）將車輛的碳排放水平設(shè)為靜態(tài)，這與實(shí)際運(yùn)作情況存在一定的差異。未來進(jìn)一步的研究應(yīng)該考慮基于時(shí)變速度的車輛 CO2排放問題，以便更科學(xué)的調(diào)度配送車輛，以獲得最佳時(shí)間和最佳配送路線。

［1］Vicente.Laying the foundations for greener transport：transport indicators tracking progress towards environmental targets in Europe［R］.European Environment Agency，Copenhagen，Denmark，2011.

［2］Dantzig G B.The truck dispatching problem［J］.Management Science，1959，1（6）：50-53.

［3］陳鋒.帶時(shí)間窗約束的多類型車輛路徑問題的改進(jìn)節(jié)約算法［J］.科學(xué)技術(shù)與工程，2012，20（24）：6082-6086.CHEN Feng.The improved saving method of vehicle routing problem with time window［J］.Science Technology and Engineering，2012，20（24）：6082-6086.

［4］Duhamel，Lacomme，Prodhon.A hybrid evolutionary local search with depth first search split procedure for the heterogeneous vehicle routing problems［J］.Engineering Application of Artificial Intelligence，2012，25（2）：345-358.

［5］陳萍，黃厚寬，董興業(yè).求解多車型車輛路徑問題的變鄰域搜索算法［J］.系統(tǒng)仿真學(xué)報(bào)，2011，23（9）：1945-1950.CHEN Ping，HUANG Houkuan，DONG Xingye.Variable neighborhood search algorithm for fleet size and mixed vehicle routing problem［J］.Journal of System Simulation，2011，23（9）：1945-1950.

［6］黨立偉，孫小明.多車場(chǎng)車輛路徑問題及混合遺傳算法［J］.科學(xué)技術(shù)與工程，2012，20（8）：1816-1820.DANG Liwei，SUN Xiaoming.Multi-depot vehicle routing problem with hybrid genetic algorithm［J］.Science Technology and Engineering，2012，20（8）：1816-1820.

［7］劉冉，江志斌，耿娜，等.半開放式多車場(chǎng)車輛路徑問題［J］.上海交通大學(xué)學(xué)報(bào)，2010，15（11）：1539-1545.LIU Ran，JIANG Zhibin，DI Na，et al.The half open multi-depot vehicle routing problem［J］.Journal of Shanghai Jiaotong University，2010，15（11）：1539-1545.

［8］鐘雪靈，王雄志.開放式車輛路徑問題的混合算法［J］.計(jì)算機(jī)仿真，2011，28（8）：207-210，232.ZHONG Xueling，WANG Xiongzhi.Hybrid algorithm for open vehicle routing problem［J］.Computer Simulation，2011，28（8）：207-210，232.

［9］李相勇，田澎.開放式車輛路徑問題的蟻群優(yōu)化算法［J］.系統(tǒng)工程理論與實(shí)踐，2008，28（6）：81-93.LI Xiangyong，TIAN Peng.Research on ant colony optimization algorithm for the open vehicle routing problem ［J］.Systems Engineering-Theory&Practice，2008，28 （6）：81-93.

［10］熊浩，符卓，鄢慧麗.動(dòng)態(tài)車輛路徑問題的隱分區(qū)靈活分批策略［J］.同濟(jì)大學(xué)學(xué)報(bào)（自然科學(xué)版），2013，41（5）：676-681.XIONG Hao，F(xiàn)U Zhuo，YAN Huili.Virtual partition and flexible batch strategy of dynamic vehicle routing problem［J］.Journal of Tongji University（Natural Science），2013，41（5）：676-681.

［11］王明陽，陳鑫，張麗華.帶油耗的單車場(chǎng)開放式車輛路徑問題研究［J］.物流科技，2012（10）：18-21.WANG Mingyang，CHEN Xin，ZHANG Lihua.Research on a single depot open vehicle routing problem with fuel consumption［J］.Logistics Sci-Tech，2012 （10）：18-21.

［12］田麗娜.碳稅政策下運(yùn)輸成本與碳排放的關(guān)系研究［C］//第六屆中國智能交通年會(huì)暨第七屆國際節(jié)能與新能源汽車創(chuàng)新發(fā)展論壇，北京：2011：3-7.TIAN Lina.Relationship of transportation cost and cabron emissions under the cabron tax policy［C］//The sixth sessionh of the china intelligent transport annual meeting and the seventh session of the internation alenergy souing and new energy antomoble forum on innovatoon and development，Beijing：2011：3-7.

［13］謝金星，刑文訓(xùn).現(xiàn)代優(yōu)化計(jì)算方法［M］.北京：清華大學(xué)出版社，1999.XIE Jinxing，XING Wenxun.Modern optimization methods［M］.Beijing：Tsinghua University Press，1999.

（編輯 蔣學(xué)東）

Research on an optimization model and its algorithm for vehicle routing problem based on CO2emission

ZHANG Dezhi1，QIAN Qi1，LI Shuangyan2，JIN Fangping1

（1.School of Traffic and Transportation Engineering，Central South University，Changsha 410075，China；2.College of Transportation&Logistics，Central South University of Forestry and Technology，Changsha 410004，China）

Logistics is not only the major part of energy consumption，but also an important source of CO2emissions.When considering the characteristics of energy consumption and CO2emission factors in vehicle routing problem with multiple vehicles，the corresponding optimization model was constructed，and a heuristic algorithm was given based on genetic algorithm.Finally，numerical simulation was performed for the model and solution algorithm.The results show that the shortest route is not always the least energy consumption route.When compared with the traditional shortest path vehicle routing，vehicle routing based on CO2emissions has a longer path length，but with a lower comprehensive cost.Genetic algorithm is an effective algorithm to solve the green vehicle routing problem.

logistics energy consumption；CO2emission；vehicle routing；optimization model；genetic algorithm

F275.5

A

1672-7029（2015）02-0424-06

2014-10-29

國家社科基金資助項(xiàng)目（11CGL032）；國家自然科學(xué)基金資助項(xiàng)目（71271220）

張得志（1976-），男，湖南祁東人，副教授，博士，從事物流系統(tǒng)優(yōu)化研究；E-mail：dzzhang@mail.csu.edu.cn