綠色車輛路徑問(wèn)題研究

王璐瑤 楊巍 曹竹 汪弘 李雅婷

摘要：現(xiàn)在社會(huì)上對(duì)各類熱點(diǎn)問(wèn)題格外重視，特別能源危機(jī)與環(huán)保問(wèn)題，這兩個(gè)難題已經(jīng)成為了焦點(diǎn)。而如今，世界經(jīng)濟(jì)發(fā)展的態(tài)勢(shì)逐漸向較低的能耗，較低的排放量的增長(zhǎng)模式趨近，而這個(gè)模式最終目標(biāo)就是保護(hù)環(huán)境，使綠色可持續(xù)發(fā)展。。在日常生活中交通運(yùn)輸業(yè)是造成環(huán)境問(wèn)題的主要原因之一，并且隨著電子商務(wù)的發(fā)展，物流配送成為城市經(jīng)濟(jì)發(fā)展和居民生活消費(fèi)多樣化的重要支柱，其造成的城市污染問(wèn)題已引起人們的高度關(guān)注。

針對(duì)該問(wèn)題，首先我們選定沈陽(yáng)市物流配送的28個(gè)站點(diǎn)進(jìn)行研究，收集并整理其2018年的全部相關(guān)數(shù)據(jù)，之后采用多目標(biāo)規(guī)劃模型，分各個(gè)站點(diǎn)進(jìn)行分析，假設(shè)各個(gè)站點(diǎn)車輛有效利用臺(tái)數(shù)占各個(gè)站點(diǎn)的總運(yùn)輸車輛臺(tái)數(shù)比值不變，分別設(shè)置車輛有效利用系數(shù)、碳排放量以及車輛運(yùn)營(yíng)效率等變量，先把目標(biāo)和約束函數(shù)列出，之后會(huì)用到數(shù)學(xué)建模上的遺傳算法，以及運(yùn)用MATLAB軟件對(duì)算法進(jìn)行求解，并最終得到結(jié)論。

層次分析法則在遺傳算法后使用，對(duì)車輛路徑選擇上有直接影響的各個(gè)考量進(jìn)行加權(quán)分析，量化評(píng)分其余的預(yù)選路徑因素。在實(shí)際情況中可根據(jù)決策者的需求對(duì)路徑進(jìn)行評(píng)價(jià)排序，進(jìn)而得到最佳車輛行駛路徑。

最后，我們根據(jù)研究得出結(jié)論，得到最優(yōu)綠色車輛路徑。

一、問(wèn)題背景

由于現(xiàn)在社會(huì)上對(duì)各類熱點(diǎn)問(wèn)題格外重視，特別能源危機(jī)與環(huán)保問(wèn)題，這兩個(gè)難題已經(jīng)成為了焦點(diǎn)。而如今，世界經(jīng)濟(jì)發(fā)展的態(tài)勢(shì)逐漸向低能耗，低排放的增長(zhǎng)模式趨近，而這個(gè)模式最終目標(biāo)就是保護(hù)環(huán)境，使綠色可持續(xù)發(fā)展。而交通運(yùn)輸業(yè)是造成環(huán)境問(wèn)題的其中的一個(gè)主要原因，并且電子的商務(wù)發(fā)展的如此迅速，物流配送成為城市經(jīng)濟(jì)發(fā)展和居民生活消費(fèi)多樣化的重要支柱，其造成的城市污染問(wèn)題引起人們的高度關(guān)注。所以把經(jīng)濟(jì)性當(dāng)做目標(biāo)的傳統(tǒng)車輛的路徑研究的問(wèn)題已不能很好地應(yīng)對(duì)這個(gè)趨勢(shì)，在降低經(jīng)濟(jì)成本的同時(shí)如何保護(hù)環(huán)境已經(jīng)成為車輛路徑優(yōu)化需要考慮的重要因素，這就是所謂的綠色車輛路徑問(wèn)題。

二、備選較優(yōu)路徑——多目標(biāo)規(guī)劃模型的建立

本文求解在確保車輛載重、容積、起點(diǎn)及終點(diǎn)和客戶服務(wù)要求的前提下，保證碳排放量呈下降趨勢(shì)以及車輛有效利用率提高到0.6以上的目標(biāo)。這道題是多目標(biāo)總體規(guī)劃問(wèn)題，因此我們?cè)谶@里，用到的是多目標(biāo)規(guī)劃模型，來(lái)解決。

沈陽(yáng)市2018年車輛有效利用率、碳排放量、總運(yùn)輸車輛臺(tái)數(shù)以及車輛運(yùn)營(yíng)效率變量，列出目標(biāo)和約束函數(shù)。而我們假設(shè)沈陽(yáng)各個(gè)站點(diǎn)的車輛有效利用臺(tái)數(shù)占其總運(yùn)輸車輛臺(tái)數(shù)比值、各個(gè)站點(diǎn)碳排放量占沈陽(yáng)市總碳排放量的總比值不變，以及可通過(guò)查找數(shù)據(jù)得出。

根據(jù)MATLAB編制程序可求得2018年車輛有效利用系數(shù)、碳排放量、總運(yùn)輸車輛以及車輛運(yùn)營(yíng)效率：

（1）形成相對(duì)較優(yōu)綠色車輛路徑

由于模型中有多個(gè)目標(biāo)，同時(shí)求解較為困難，所以運(yùn)用禁忌搜索算法對(duì)這個(gè)進(jìn)行求解，形成相對(duì)較優(yōu)綠色車輛路徑。

（2）評(píng)價(jià)較優(yōu)綠色車輛路徑

由于前面得到的相對(duì)較優(yōu)綠色車輛路徑包括三個(gè)目標(biāo)的各自較優(yōu)路徑，對(duì)其進(jìn)行評(píng)價(jià)。

求解方法：

對(duì)于上述綠色車輛路徑問(wèn)題中所建立的多目標(biāo)規(guī)劃模型，鑒于多目標(biāo)約束下模型的求解方法比較復(fù)雜，因此我們采取禁忌搜索算法來(lái)求解考慮到油耗的單個(gè)車場(chǎng)多個(gè)車型的車輛路徑問(wèn)題。

我們假定一個(gè)車場(chǎng)共有L種類型的車輛，設(shè)第 種類型車共有 輛（ 足夠大），每輛車的容量為 ，油耗費(fèi)為 。該車場(chǎng)共為N個(gè)站點(diǎn)服務(wù)，其中第 個(gè)站點(diǎn)所需貨物重為 。配送車輛從站點(diǎn)裝上貨物出發(fā)為客戶送貨，要求每個(gè)客戶只由一輛車配送，車輛將貨物運(yùn)送完畢后停留在最后的站點(diǎn)，每輛車的費(fèi)用均為其油耗費(fèi)，目標(biāo)為使所有被派出的車輛的費(fèi)用之和最小。

禁忌搜索算法：

（1）禁忌算法中解的表示：由于上述問(wèn)題為多車型單車場(chǎng)問(wèn)題，又本文用 MATLAB 實(shí)現(xiàn)該禁忌搜索算法，為了便于進(jìn)行鄰域操作，所以采用車型代替車場(chǎng)，例如，假設(shè)一車場(chǎng)共有2種類型車輛，為10個(gè)站點(diǎn)配送貨物，用1，2表示車型，1--10表示10個(gè)站點(diǎn)，則1維元胞數(shù)組：{[4] ，[1，3，5，7]，[2，2，1，6]，[1，4，19]，[2，8]}表示該問(wèn)題的一個(gè)解，該解中共有4條路徑，它們分別為：

（1）禁忌算法中鄰域操作：根據(jù)車型不同而導(dǎo)致啟動(dòng)費(fèi)用不同的特殊情況，用一些特殊的鄰域操作方法來(lái)減少車輛的剩余容量，從而減少車輛的使用數(shù)量，以達(dá)到減少目標(biāo)函數(shù)的目的。隨機(jī)從 （其含義與改進(jìn)的最近鄰算法中的 相同）中任取兩條路徑，再分別從兩條路徑中任取出兩個(gè)節(jié)點(diǎn)：

①若取出的兩個(gè)節(jié)點(diǎn)均為車型，則檢測(cè)是否有容量更加適合，若有則更換車型，若無(wú)則進(jìn)入下一步操作。

②若取出兩節(jié)點(diǎn)中分別為車型和客戶點(diǎn)。則將客戶點(diǎn)插入在路徑車型之后，并將此點(diǎn)在原路徑中剔除，若仍然有客戶點(diǎn)存在，則將車型替換成容量與此路徑中總裝載量最近的車型，若無(wú)客戶點(diǎn)存在，則直接刪除此路徑。

③若取出的兩點(diǎn)均為客戶點(diǎn)，則將第二個(gè)客戶點(diǎn)插在第一個(gè)客戶點(diǎn)之后，并將此點(diǎn)在原徑中剔除，如果仍然有客戶點(diǎn)存在，則將車型替換成容量與此路徑中總裝載量最近的車型，若無(wú)客戶點(diǎn)存在，則直接刪除此路徑。

（3）計(jì)算禁忌算法中的評(píng)價(jià)值：為了擴(kuò)大算法的搜索范圍，防止局部最優(yōu)解的生成，在每次迭代中，本算法允許不可行解產(chǎn)生鄰居，但由于不可行解的違反目標(biāo)約束的特點(diǎn)，對(duì)不可行解加以懲罰，設(shè)懲罰因子為 ，且令 若解x中總共有 條路不可行，設(shè)x對(duì)應(yīng)的目標(biāo)函數(shù)值為 ，則解x的評(píng)價(jià)值為 。

（4）禁忌對(duì)象及禁忌長(zhǎng)度：將每次迭代得到的局部最好解（評(píng)價(jià)值最小）作為禁忌對(duì)象放入禁忌表中;取禁忌長(zhǎng)度為一個(gè)常數(shù)，其值根據(jù)問(wèn)題的規(guī)模來(lái)確定;將從當(dāng)前解的鄰域中隨機(jī)選擇N個(gè)鄰居作為候選集合;采用迭代指定步數(shù)T的終止準(zhǔn)則。

三、評(píng)價(jià)預(yù)選較好路徑——運(yùn)用層次分析法確立層次分析模型

根據(jù)不同的實(shí)際情形，我們分析了各項(xiàng)原因，并對(duì)其進(jìn)行了加權(quán)，這一步用到了層次分析法。為挑選出最佳車輛路徑，我們采取各項(xiàng)指標(biāo)權(quán)重系數(shù)與實(shí)際數(shù)據(jù)相結(jié)合的評(píng)分制度，以此定量評(píng)價(jià)各備選路徑。

（一）建立影響車輛路徑選擇的指標(biāo)體系

由上一模型的建立我們已知路徑選擇主要有成本、路程和污染三大目標(biāo)，而各個(gè)目標(biāo)又由多種指標(biāo)決定，分別有總運(yùn)輸車輛臺(tái)數(shù)、車輛有效利用率、行駛里程、行駛時(shí)間、耗油量、碳排放量六項(xiàng)指標(biāo)。而這六項(xiàng)基準(zhǔn)方便于根據(jù)執(zhí)行者的需要明確權(quán)重。

（二）確定各項(xiàng)指標(biāo)的權(quán)重并建立矩陣

運(yùn)用層次分析法，簡(jiǎn)稱為AHP，加權(quán)定量分析各項(xiàng)指標(biāo)，這個(gè)指標(biāo)是指可以決定路徑選擇的。

第一步先將指標(biāo)構(gòu)造一個(gè)成對(duì)比較陣，兩兩對(duì)比比較這個(gè)方案里面的所有因素，用成對(duì)比較矩陣A，B表示出所有的比較成果。

矩陣A、B是一致陣，權(quán)向量就是取對(duì)應(yīng)于最大根的歸一化的向量表示對(duì)上層原因的權(quán)重。下一步將各層權(quán)重結(jié)果進(jìn)行乘法和加法的運(yùn)算，得到的結(jié)果就是各個(gè)目標(biāo)的權(quán)重值。

（三）一致性檢驗(yàn)

再接著下一步就是一致性檢驗(yàn)，將一致性指標(biāo)，這里簡(jiǎn)稱為CI，隨機(jī)一致性指標(biāo)，這里簡(jiǎn)稱為RI，這兩個(gè)指標(biāo)引入算法中。一致性比例是需要根據(jù)隨機(jī)一致性指標(biāo)給定的數(shù)值表來(lái)計(jì)算的。 若CR均小于0.1，則通過(guò)一致性檢驗(yàn)。

（四）計(jì)算各路徑得分

根據(jù)各權(quán)重計(jì)算各備選路徑得分并進(jìn)行排名。

分?jǐn)?shù)越高者，越滿足決策者的要求。

四、挑選最佳路徑——依據(jù)不同需求挑選

根據(jù)實(shí)際情況，依據(jù)不同決策者的需求，可以調(diào)整各指標(biāo)的權(quán)重，以挑選出適合不同情況的最佳車輛路徑。

參考文獻(xiàn)：

[1] 唐修柏.財(cái)務(wù)風(fēng)險(xiǎn)跟蹤評(píng)價(jià)方法初探[J].科技視界，2016（01）：278.

[2] 陶大俊. 基于小波與層次分析法的電子銀行風(fēng)險(xiǎn)評(píng)價(jià)與研究[D].西安電子科技大學(xué)，2009.

[3] 趙志學(xué)，李夏苗，周鮮成.考慮擁堵區(qū)域的多車型綠色車輛路徑問(wèn)題優(yōu)化研究[J/OL].計(jì)算機(jī)應(yīng)用：1-11[2019-11-21].

[4] 高飛. 不確定因素下配送路徑優(yōu)化問(wèn)題研究[D].北京交通大學(xué)，2019.

[5] 李英，李惠，成琪.基于文獻(xiàn)計(jì)量和知識(shí)圖譜的國(guó)際綠色車輛路徑問(wèn)題研究發(fā)展分析[J].中國(guó)管理科學(xué)，2016，24（S1）：206-216.

[6] C.H.Lin，K.L.Choy，G.T.S.Ho，S.H.Chung，H.Y.Lam. Survey of green vehicle routing problem，past and future trends[J]. Expert Systems with Applications，2014，41：1118–1138.

[7] 陳玉光，陳志祥. 基于準(zhǔn)時(shí)送貨和最小耗油的配送車輛路徑問(wèn)題研究[J]. 中國(guó)管理科學(xué)，2015，23：156-164.

[8] 饒衛(wèi)振，金淳，王新華等. 考慮道路坡度因素的低碳 VRP 問(wèn)題模型與求解策略[J]. 系統(tǒng)工程理論與實(shí)踐，2014，34（8）：2092-2105.

[9] Kü?üko?lu，S. Ene，A. Aksoy et al. A memory structure adapted simulated annealing algorithm for a green vehicle routing problem[J]. Environmental Science & Pollution Research，2015，22 （5）：3279-3297.

[10] 葛顯龍，黃鈺，譚柏川. 基于油耗的帶時(shí)間窗變速車輛路徑問(wèn)題研究[J]. 物流技術(shù)，2015，34（8）：127-149.

[11] 李進(jìn)，張江華. 基于碳排放與速度優(yōu)化的帶時(shí)間窗車輛路徑問(wèn)題[J]. 系統(tǒng)工程理論與實(shí)踐，2014，34（12）：3063-3072.

[12] J. Zhang，Y. Zhao，W. Xue et al. Vehicle routing problem with fuel consumption and carbon emission [J]. International Journal of Production Economics，2015，170：234-242.

[13] 李進(jìn)，傅培華，李修琳等.低碳環(huán)境下的車輛路徑問(wèn)題及禁忌搜索算法研究[J].中國(guó)管理科學(xué)，2015，23（10）：98-106.

[14] 康凱，韓杰，馬艷芳等. 基于碳排放的模糊約定時(shí)間車輛路徑問(wèn)題研究 [J]. 工業(yè)工程與管理，2017，22（4）：17-22.

[15] T. Bektas，G. Laporte. The Pollution-Routing Problem[J]. Transportation Research Part B，2011，45：1232-1250.

[16] R. Kramer，A. Subramanian，T. Vidal et al. A matheuristic approach for the Pollution-Routing Problem[J]. European Journal of Operational Research，2015，243 （2）：523-539 .

[17] 左秋玲，李景山.AHP-模糊數(shù)學(xué)模型在高層工業(yè)建筑火災(zāi)風(fēng)險(xiǎn)評(píng)估中的應(yīng)用[J].城市建筑，2017（11）：25-27.

[18] 肖曉偉，肖迪，林錦國(guó)，肖玉峰. 多目標(biāo)優(yōu)化問(wèn)題的研究概述[J]. 計(jì)算機(jī)應(yīng)用研究，2011，28（ 3）：805-808

[19] 潘斌斌.多目標(biāo)路徑規(guī)劃問(wèn)題的算法綜述[J].重慶工商大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，29（05）：78-84.

[20] 滕立春. 電器連鎖零售企業(yè)的供應(yīng)商評(píng)價(jià)研究[D].西北工業(yè)大學(xué)，2005.

（作者單位：沈陽(yáng)師范大學(xué)）