蔡 虹,吳 斌，殷南晨

(南京工業(yè)大學(xué) 經(jīng)濟(jì)與管理學(xué)院，南京 210009)

以降低油耗為目標(biāo)的車(chē)輛路徑問(wèn)題研究

蔡 虹,吳 斌，殷南晨

(南京工業(yè)大學(xué) 經(jīng)濟(jì)與管理學(xué)院，南京 210009)

車(chē)輛路徑問(wèn)題是物流及供應(yīng)鏈管理優(yōu)化的核心環(huán)節(jié)。為實(shí)現(xiàn)低碳運(yùn)輸，文中綜合考慮運(yùn)輸車(chē)輛的載重、車(chē)速及行駛距離等因素，以降低車(chē)輛在運(yùn)輸過(guò)程中的油耗成本和單位車(chē)輛的固定成本為目標(biāo)優(yōu)化車(chē)輛路徑, 建立數(shù)學(xué)模型并創(chuàng)新交叉算子設(shè)計(jì)改進(jìn)遺傳算法，并通過(guò)仿真實(shí)驗(yàn)對(duì)算法的效果進(jìn)行驗(yàn)證。仿真結(jié)果表明，所提出的算法簡(jiǎn)潔、有效。

降低油耗；車(chē)輛路徑問(wèn)題；改進(jìn)遺傳算法 ；Matlab軟件

以節(jié)能減排為目標(biāo)的車(chē)輛路徑問(wèn)題是經(jīng)典車(chē)輛路徑問(wèn)題(vehicle routing problem，VRP)的一個(gè)新方向，它不再以傳統(tǒng)的總運(yùn)輸成本為目標(biāo)，而是將降低油耗作為關(guān)鍵目標(biāo)。近年來(lái)，低碳、環(huán)保、節(jié)約能源已經(jīng)成為世界各國(guó)的關(guān)鍵詞，對(duì)于迫切要求經(jīng)濟(jì)增長(zhǎng)方式轉(zhuǎn)型的中國(guó)，這方面的研究意義重大，對(duì)于物流企業(yè)、零售企業(yè)均具有較強(qiáng)的實(shí)用價(jià)值。

國(guó)內(nèi)外已有學(xué)者在車(chē)輛路徑問(wèn)題的研究中考慮車(chē)輛的能耗和排放問(wèn)題。Miguel Figliozzi[1]以運(yùn)輸車(chē)輛二氧化碳的排放量為優(yōu)化目標(biāo)開(kāi)展研究，用車(chē)程和車(chē)速計(jì)算運(yùn)輸車(chē)輛的二氧化碳排放量，并建立有時(shí)間窗的車(chē)輛路徑問(wèn)題模型，用迭代路線(xiàn)算法進(jìn)行優(yōu)化計(jì)算；Miguel Figliozzi等[2]在運(yùn)輸車(chē)輛選擇的經(jīng)濟(jì)性和環(huán)境影響方面做了研究，通過(guò)綜合比較不同車(chē)型的購(gòu)買(mǎi)、維護(hù)、運(yùn)行、折舊、排放費(fèi)用等，選出最經(jīng)濟(jì)環(huán)保的運(yùn)輸車(chē)輛；李進(jìn)，傅培華[3]對(duì)多車(chē)型低碳路徑問(wèn)題的研究則以降低碳排放為目標(biāo)，綜合考慮運(yùn)量和車(chē)速來(lái)計(jì)算油耗，并運(yùn)用禁忌搜索算法進(jìn)行優(yōu)化計(jì)算；邱雅軍，宋國(guó)防[4]用車(chē)輛所行駛的路程來(lái)量化車(chē)輛路徑問(wèn)題中的碳排放，并運(yùn)用改進(jìn)的遺傳算法進(jìn)行優(yōu)化計(jì)算。綜上所述，已知文獻(xiàn)的研究中很少考慮車(chē)輛的載重量對(duì)車(chē)輛排放的影響；針對(duì)該問(wèn)題所設(shè)計(jì)的遺傳算法優(yōu)化效果有限，算子的設(shè)計(jì)有待改進(jìn)。

本文綜合運(yùn)輸車(chē)輛的載重、車(chē)速及行駛路程來(lái)計(jì)算運(yùn)輸任務(wù)中的油耗，參考文獻(xiàn)[5-6]建立油耗計(jì)算公式，考慮油耗的經(jīng)濟(jì)成本和單位車(chē)輛的固定成本設(shè)定目標(biāo)函數(shù)并建立模型；設(shè)計(jì)了遺傳算法算子用于計(jì)算；通過(guò)仿真實(shí)驗(yàn)對(duì)算法的效果進(jìn)行驗(yàn)證。仿真結(jié)果表明，經(jīng)過(guò)優(yōu)化的調(diào)度方案的總油耗大幅降低，從而達(dá)到節(jié)能環(huán)保的目標(biāo)。

1 問(wèn)題描述

2 建立降低油耗為目標(biāo)的車(chē)輛路徑模型

(1)

約束條件：

(2)

(3)

(4)

(5)

(6)

式(2)保證了每個(gè)所需經(jīng)過(guò)的路段都有且僅有一輛車(chē)經(jīng)過(guò)，保證每個(gè)客戶(hù)有且僅有一輛車(chē)為他服務(wù)；式(3)保證了每個(gè)客戶(hù)站點(diǎn)有同一輛車(chē)到達(dá)和離開(kāi)；式(4)表明車(chē)輛出發(fā)后直到完成所有任務(wù)，中間不再回到車(chē)站；式(5)保證每輛車(chē)都由車(chē)站出發(fā)，并保證了每輛車(chē)都會(huì)回到車(chē)站；式(6)保證了每輛車(chē)都不會(huì)超重。

3 改進(jìn)遺傳算法設(shè)計(jì)

3.1 編碼及染色體適應(yīng)度的計(jì)算

將車(chē)站v以及所有的客戶(hù)C={v1,v2，…，vn}用整數(shù)進(jìn)行編碼。其中車(chē)站的編碼為“0”，其余客戶(hù)編碼依次為“1”“2”“3”…“n”。一條染色體擁有L+K+1個(gè)基因(L為客戶(hù)數(shù)，K為參加運(yùn)輸?shù)能?chē)輛數(shù))，其中包括L個(gè)客戶(hù)的唯一的編碼，并在其中穿插了K+1個(gè)車(chē)站編碼“0”以區(qū)別客戶(hù)對(duì)應(yīng)的車(chē)輛。

3.2 變異算子

本文以基本位變異法為基礎(chǔ)，根據(jù)實(shí)際需要做出改進(jìn)，以一定的變異概率分別對(duì)染色體的每一個(gè)基因位進(jìn)行變異操作，具體步驟如下：

Step1：設(shè)變量i為從左到右基因的編號(hào)，初始值i=1，xi表示染色體R內(nèi)基因；

Step2：若xi=0，則i=i+1，回到Step1；

Step3：隨機(jī)取一個(gè)除xi以外的基因yi≠0，交換xi和yi的位置，得到新染色體R′；

Step4：如果R″不滿(mǎn)足載重要求或者適應(yīng)度小于R，則放棄該次變異操作，變回原染色體R；

Step5：如果i

4 仿真實(shí)驗(yàn)

本文用如下實(shí)例測(cè)試上述遺傳算法并由Matlab實(shí)現(xiàn)，共有6輛同型號(hào)車(chē)輛供運(yùn)輸使用，需要完成16位客戶(hù)的運(yùn)輸任務(wù)，要求總成本盡可能低。具體參數(shù)分別見(jiàn)表1和表2。

表1 基本數(shù)據(jù)

續(xù) 表

表2 每個(gè)客戶(hù)的貨物重量

4.1 實(shí)驗(yàn)結(jié)果

針對(duì)前述實(shí)例，交叉改進(jìn)前后的線(xiàn)路優(yōu)化結(jié)果分別如圖1和圖2所示。

圖1 交叉改進(jìn)前的優(yōu)化結(jié)果

圖2 交叉改進(jìn)后的優(yōu)化結(jié)果

在兩個(gè)優(yōu)化結(jié)果中都只有四條運(yùn)輸線(xiàn)路，說(shuō)明6輛運(yùn)輸車(chē)輛中只有4輛參與了運(yùn)輸任務(wù)，其余兩輛閑置。

利用本文的遺傳算法，計(jì)算前述實(shí)例，結(jié)果見(jiàn)表3。

表3 實(shí)驗(yàn)結(jié)果

5 結(jié)束語(yǔ)

本文將降低運(yùn)輸過(guò)程中的油耗經(jīng)濟(jì)成本和單位車(chē)輛的固定成本作為車(chē)輛路徑問(wèn)題的目標(biāo)，通過(guò)創(chuàng)新交叉算子設(shè)計(jì)改進(jìn)遺傳算法。通過(guò)仿真實(shí)驗(yàn)可以看出，優(yōu)化后的調(diào)度方案的總經(jīng)濟(jì)成本大幅降低，并且算法簡(jiǎn)單、有效。下一步可以將服務(wù)的時(shí)間窗考慮進(jìn)來(lái)，將更具實(shí)踐意義。

[1]MiguelFigliozzi.Vehicleroutingproblemforemissionsminimization[J].TransportationResearchBoard，2010，2197：1-7.

[2]MiguelAFigliozzi，JesseABoudart，WeiFeng.Economicandenvironmentaloptimizationofvehiclefleets：acasestudyoftheimpactsofpolicy，market，utilization，andtechnologicalfactors[J].TransportationResearchBoard，2011，2252:1-6.

[3] 李進(jìn)，傅培華. 具有固定車(chē)輛數(shù)的多車(chē)型低碳路徑問(wèn)題及算法[R].浙江：浙江工商大學(xué)計(jì)算機(jī)與信息工程學(xué)院，2012.

[4] 邱雅君，宋國(guó)防. 考慮碳排放因素的車(chē)輛路徑問(wèn)題研究[J].技術(shù)與方法，2012，36(7)：227-229.

[5] 莊志華，何仁，李麗. 運(yùn)行參數(shù)對(duì)客車(chē)燃料經(jīng)濟(jì)性影響的參數(shù)靈敏度分析[J].輕型汽車(chē)技術(shù)，2007(2)：4-7.

[6] 何仁.汽車(chē)動(dòng)力性燃料經(jīng)濟(jì)性模擬計(jì)算方法及 應(yīng) 用[M].北京：機(jī)械工業(yè)出版社，1996:18-21.

Research on Vehicle Routing Problem for Fuel Consumption Reduction

CAI Hong, WU Bin,YIN Nanchen

(College of Economics Management,Nanjing University of Technology,Nanjing 210009,China)

Vehicle routing problem is the core of optimization on logistics and supply chain management. According to the requirement of low-carbon transportation, the paper takes vehicle weight, vehicle velocity and distance into consideration, and optimizes the vehicle routing problem by setting the fuel consumption economics cost and fixed-cost of vehicle as objective function. Then the improved genetic algorithm is proposed, applying new crossover operator. Simulation results show that the designed algorithm is simple and effective.

fuel consumption reduction; vehicle routing problem; improved genetic algorithm; Matlab software

2014-05-25；修改日期: 2014-06-21

江蘇省自然科學(xué)基金資助項(xiàng)目(BK2010555)；江蘇省高教改革基金資助項(xiàng)目(2011JSJG182);江蘇省高等學(xué)校大學(xué)生實(shí)踐創(chuàng)新訓(xùn)練計(jì)劃基金資助項(xiàng)目(2012JSSPITP0903)。

蔡 虹(1978-),女，博士研究生，講師，研究方向：物流系統(tǒng)建模與優(yōu)化，收益管理。

U

Adoi:10.3969/j.issn.1672-4550.2015.03.005