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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.1 問題描述

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

1.2 數(shù)學建模

符號及決策變量說明：

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

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

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

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

1.3 求解算法分析

對于多車型車輛路徑問題（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大學 J.Holland教授于1975年首先提出，它是一種概率搜索算法，具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；能自動獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。遺傳算法的這些性質(zhì)，已被人們廣泛地應(yīng)用于組合優(yōu)化、機器學習、信號處理、自適應(yīng)控制和人工生命等領(lǐng)域。

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

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

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

2）初始種群

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

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

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

4）遺傳算子

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

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

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

5）終止條件

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

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

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

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

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

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

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

2 算例分析

2.1 實例計算

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

表1 客戶的坐標位置及需求量Table1 Coordinates and demands of customers

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

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

2.2 結(jié)果分析

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

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

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

其中一次的運行結(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ù)對比如表3所示。

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)論

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

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

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

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

［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］陳鋒.帶時間窗約束的多類型車輛路徑問題的改進節(jié)約算法［J］.科學技術(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)仿真學報，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］黨立偉，孫小明.多車場車輛路徑問題及混合遺傳算法［J］.科學技術(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］劉冉，江志斌，耿娜，等.半開放式多車場車輛路徑問題［J］.上海交通大學學報，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］.計算機仿真，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)工程理論與實踐，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］熊浩，符卓，鄢慧麗.動態(tài)車輛路徑問題的隱分區(qū)靈活分批策略［J］.同濟大學學報（自然科學版），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］王明陽，陳鑫，張麗華.帶油耗的單車場開放式車輛路徑問題研究［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］田麗娜.碳稅政策下運輸成本與碳排放的關(guān)系研究［C］//第六屆中國智能交通年會暨第七屆國際節(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］謝金星，刑文訓.現(xiàn)代優(yōu)化計算方法［M］.北京：清華大學出版社，1999.XIE Jinxing，XING Wenxun.Modern optimization methods［M］.Beijing：Tsinghua University Press，1999.

（編輯 蔣學東）

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

國家社科基金資助項目（11CGL032）；國家自然科學基金資助項目（71271220）

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