油耗最小化多車型車輛路徑問題研究

何小年 彭瓊

摘? 要： 研究最小化油耗的多車型車輛路徑問題，將車輛使用費(fèi)用分為固定費(fèi)用和以油耗為主的可變費(fèi)用。建立了該問題的數(shù)學(xué)模型，運(yùn)用禁忌搜索算法進(jìn)行模型求解。算法采用隨機(jī)選擇車型產(chǎn)生初始解，設(shè)計(jì)三種Or-opt鄰域結(jié)構(gòu)，利用罰函數(shù)接受導(dǎo)致不可行解的變換。通過案例測試驗(yàn)證了模型的正確性和算法的有效性。結(jié)果表明，采用最小化油耗為目標(biāo)比最小化距離為目標(biāo)更加經(jīng)濟(jì)和環(huán)保。

關(guān)鍵詞： 多車型車輛路徑問題; 最小化油耗; 禁忌搜索算法; Or-opt算法

中圖分類號(hào)：TP391? ? ? ? ? 文獻(xiàn)標(biāo)志碼：A? ? ?文章編號(hào)：1006-8228（2019）02-09-04

Research on the multi-type vehicle routing problem with minimizing fuel consumption

He Xiaonian， Peng Qiong

（School of Information and Electrical Engineering， Hunan International Economics University， Changsha， Hunan 410205， China）

Abstract： The Multi-type Vehicles Routing Problem with Minimizing Fuel Consumption （MVRPMFC） is researched; And the use costs of vehicles are divided into the fixed cost and the variable cost arising mainly from fuel consumption. The MVRPMFC is modeled mathematically; and Tabu Search Algorithm （TSA） is used to solve it. According to TSA， the initial solution is generated with the random selection of the vehicle type， three kinds of mixed neighborhood structure are designed for Or-opt， and the penalty function is used to accept the transformation which leads to infeasible solution. The experiment shows the model is correct and the TSA is effective; and minimizing fuel consumption as a goal is more economical and environmentally friendly than minimizing the distance.

Key words： Multi-type Vehicle Routing Problem; minimizing fuel consumption; Tabu Search Algorithm; Or-opt

0 引言

降低燃油消耗，能有效減少汽車尾氣排放，同時(shí)降低配送成本。本文在經(jīng)典車輛路徑問題（Vehicle Routing Problem，VRP）的基礎(chǔ)上，研究最小化油耗的多車型車輛路徑問題（Multi-type Vehicle Routing Problem with Minimizing Fuel Consumption， MVRPMFC）。MVRPMFC綜合考慮不同型號(hào)車輛的配合使用，在安排車輛路徑時(shí)考慮最小化油耗約束，以配送成本最小化和盡可能降低碳排放為目標(biāo)。

近年來，國內(nèi)外在配送的碳排放約束方面的研究并不多。李淑琴等設(shè)計(jì)模擬退火算法求解了帶時(shí)間窗的環(huán)保多車型車輛路徑問題[1];段鳳華等人應(yīng)用基于最佳插入和交換的混合鄰域禁忌搜索算法求解帶碳排放約束的異型車輛路徑問題[2]。葛顯龍等研究了考慮碳排放因素的帶時(shí)間窗的多車型車輛路徑模型，設(shè)計(jì)了混合遺傳算法求解[3];李進(jìn)等提出了考慮車輛運(yùn)量和速度的能耗計(jì)算方法，建立了非滿載運(yùn)輸方式下的低碳路徑LCRP模型，設(shè)計(jì)了基于路徑劃分的禁忌搜索算法RS-TS[4]。

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

假定在一個(gè)物流網(wǎng)絡(luò)中，N={0，1，2，…，n}為節(jié)點(diǎn)的集合，節(jié)點(diǎn)0表示車場，節(jié)點(diǎn)1，2，…，n表示客戶，Qk：k型車的容量。在車場有容量異型車隊(duì)K，假定車隊(duì)規(guī)模固定，每輛車只可行駛在一條線路上，每個(gè)客戶需求為正。問題是在客戶需求、車輛容量、車輛固定成本、空載與滿載時(shí)的油耗既定的情形下，確定車輛配送路線，以最小化固定運(yùn)輸成本，以及可變油耗成本的總成本，其中可變油耗成本與車輛運(yùn)輸量、運(yùn)輸距離和車載率密切相關(guān)。

為構(gòu)建數(shù)學(xué)模型，做如下符號(hào)說明。k：車輛類型，k=1，2，…，Mk表示k型車的數(shù)量;qi：客戶i的需求量;dij：客戶i和j之間的距離，距離矩陣視為對(duì)稱，即dij=dji;車型為k的車輛m從客戶i行駛到客戶j，則xijkm=1，否則xijkm=0;客戶i的貨物由車型為k車輛m服務(wù)，則yikm=1，否則yikm=0;pijkm表示車型為k的車輛m從客戶o行駛到客戶j的實(shí)際載重量;Fkm表示車型為k的車輛m的固定使用費(fèi)用。

因此，MVRPMFC數(shù)學(xué)模型為：

滿足： ⑴

⑵

⑶

⑷

⑸

⑹

目標(biāo)函數(shù)表示運(yùn)營成本、碳排放交易成本和違反時(shí)間窗懲罰成本的總和。約束⑴表示車輛裝載能力的限制，約束⑵限制了每種車型數(shù)量，約束⑶表示每個(gè)客戶只由一輛車訪問一次，約束⑷表示進(jìn)入和離開一給定客戶點(diǎn)的車輛數(shù)相同，約束⑸表示車型為k的車輛m在客戶i到j(luò)的實(shí)載率，約束⑹表示每一輛車都從車場出發(fā)，最后都回到車場。

2 求解MVRPMFC的禁忌搜索算法

2.1 初始解

本算法初始解設(shè)計(jì)為：以隨機(jī)方式生成客戶點(diǎn)的排列，然后再隨機(jī)從異型車隊(duì)中選一輛車，在客戶點(diǎn)排列中最左端選擇一個(gè)客戶分配給該輛車，如此循環(huán)，直至該車不再能完成其后的最左端客戶裝載任務(wù)。隨后，又從異型車隊(duì)中隨機(jī)選一輛車作為當(dāng)前車輛，將剩余客戶點(diǎn)集中最左邊的客戶點(diǎn)安排給該車。依次循環(huán)，直到所有的客戶點(diǎn)都服務(wù)完畢。

2.2 鄰域結(jié)構(gòu)

本文使用Or-opt方法，Or-opt方法是k-opt中的一種，k-opt通過每次交換條k邊來改進(jìn)初始解。目前都認(rèn)為3-opt算法是一種比較有效的算法[5]，Or-opt方法是Or提出將一段路徑（1個(gè)、2個(gè)、3個(gè)連續(xù)的頂點(diǎn)）在另外兩個(gè)頂點(diǎn)間重新定位，相當(dāng)于一個(gè)受約束的3-opt交換。本文根據(jù)Or-opt將一段路徑（1個(gè)、2個(gè)、3個(gè)連續(xù)的頂點(diǎn)）在另外兩個(gè)頂點(diǎn)間重新定位，設(shè)計(jì)了Or-opt-1，Or-opt-2，Or-opt-3三種交換的組合，以隨機(jī)的方式選擇其中一種應(yīng)用于當(dāng)前解。下面對(duì)可行變換加以說明，其中帶下劃線者為所挑選的頂點(diǎn)。

在同一線路或不同兩條線路中隨機(jī)挑選兩個(gè)頂點(diǎn)（客戶點(diǎn)或車場），隨機(jī)的執(zhí)行下列三種變換之一。

⑴ Or-opt-1，將一段路徑1個(gè)頂點(diǎn)在另外兩個(gè)頂點(diǎn)間重新定位，例如：

⑵ Or-opt-2，將一段路徑2個(gè)頂點(diǎn)在另外兩個(gè)頂點(diǎn)間重新定位，例如：

⑶ Or-opt-3，將一段路徑3個(gè)頂點(diǎn)在另外兩個(gè)頂點(diǎn)間重新定位，例如：

2.3 解的評(píng)價(jià)

對(duì)MVRPMFC類型的車輛調(diào)度問題需要優(yōu)化的目標(biāo)為運(yùn)輸成本（可變成本和固定成本）。為了充分對(duì)解空間進(jìn)行搜索，算法接受導(dǎo)致不可行解的變換。違反了車輛裝載能力限制時(shí)，其不可行性的程度可以通過引入一個(gè)罰值而將該約束條件包含到目標(biāo)函數(shù)中去進(jìn)行度量，即。其中K是該解中所使用的車輛數(shù)（線路數(shù)），T（r）為車輛r的行駛費(fèi)用，C（r）為在線路r上超出車輛載重量的部分，而p*是懲罰系數(shù)。若一個(gè)解是可行的，則所有線路上的C（r）都等于零。p*∈[0.0001，10000]，p*開始時(shí)等于1，并通過一個(gè)自調(diào)整參數(shù)來加權(quán)：每隔10次迭代測試一次，若前面的10個(gè)解都是可行的，則將其除以2;若所有的10個(gè)解都是不可行的，則將其乘以2。這種機(jī)制可以產(chǎn)生一種可行解和不可行解的混合，有利于減少陷入局部最優(yōu)的可能性[6]。

2.4 禁忌表

禁忌表用于記載最近的5～10（隨機(jī)挑選）次迭代中解的變換特征?？梢詷?gòu)造一組（n+1）×（n+1）階矩陣來記錄禁忌情況。若點(diǎn)i和j被挑選來進(jìn)行以下三種變換：Or-opt-1，Or-opt-2，Or-opt-3三種交換，則將其禁忌情況存入矩陣的元素（i，j）中。在每一次迭代時(shí)，都必須將上一步所進(jìn)行的變換填入到禁忌表中，而表中的其他元素相應(yīng)地減1直到等于零為止。

2.5 終止準(zhǔn)則

當(dāng)總迭代步數(shù)達(dá)到一個(gè)給定值，或在給定的連續(xù)迭代步數(shù)內(nèi)當(dāng)前的最好解沒有改變時(shí)，則終止搜索。

3 算例測試與比較

3.1 算例一

本文提出的禁忌搜索算法已用Delphi編程。為了測試算法的計(jì)算效果，采用文獻(xiàn)[5]算例，所有車型車輛不受行駛距離限制，要求合理安排配送車輛的配送路線，使完成配送任務(wù)的總油耗最少。以距離為優(yōu)化目標(biāo)和油耗為優(yōu)化目標(biāo)分別利用本文算法對(duì)文獻(xiàn)[5]進(jìn)行求解，經(jīng)過20次運(yùn)算結(jié)果中最優(yōu)解見表1。

本文以距離為優(yōu)化目標(biāo)固定費(fèi)用為600，可變油耗費(fèi)用為1112.35，總費(fèi)用為1712.35;以油耗為優(yōu)化目標(biāo)固定費(fèi)用為620，可變油耗費(fèi)用為958.27，總費(fèi)用為1578.27。

表1中結(jié)果表明：雖然以距離為優(yōu)化目標(biāo)總距離比以油耗為優(yōu)化目標(biāo)要短，但是以油耗為優(yōu)化目標(biāo)總費(fèi)用比以距離為優(yōu)化目標(biāo)的總費(fèi)用節(jié)約了134.08，節(jié)約了7.83%。

3.2 算例二

采用文獻(xiàn)[7]的算例，文獻(xiàn)[7]中沒有考慮車輛的固定成本，本文假設(shè)三種車型的固定費(fèi)用分別為60，100，150。以距離為目標(biāo)，20次運(yùn)算結(jié)果中取最優(yōu)解如表2所示。以距離為優(yōu)化目標(biāo)，可變油耗成本為11749.21，固定費(fèi)用為300，總費(fèi)用為12049.21;以油耗為優(yōu)化目標(biāo)結(jié)，可變油耗成本為11363.37，固定費(fèi)用為300，總費(fèi)用為11663.37。

注：表2中標(biāo)“☆”文獻(xiàn)[7]中兩條路徑的配送量都超出了3種車型中最大車型的容量的限制。

文獻(xiàn)[7]以距離為目標(biāo)的動(dòng)態(tài)求解的最優(yōu)線路成本為393.22，線路油耗為9977.7;以油耗為目標(biāo)的動(dòng)態(tài)求解最優(yōu)解油耗成本為9070.9，運(yùn)輸總路程為443.3。本文以距離為優(yōu)化目標(biāo)線路油耗為11749.21;以油耗為優(yōu)化目標(biāo)線路總油耗為11363.37。

結(jié)果比較表明：文獻(xiàn)[7]結(jié)果雖然比本文結(jié)果總成本要優(yōu)，但是以距離為優(yōu)化目標(biāo)和以油耗為優(yōu)化目標(biāo)兩種情況中都有一條線路上的配送量超出車輛裝載量的限制。本文所得到的解是可行的，以距離為優(yōu)化目標(biāo)雖然距離比以油耗為優(yōu)化目標(biāo)的距離要短，但是以油耗為目標(biāo)比以距離為優(yōu)化目標(biāo)線路總油耗節(jié)約了3.28%。

4 結(jié)論

以隨機(jī)選擇車型、從三種鄰域變換中隨機(jī)選擇一種、禁忌長度在一定數(shù)值區(qū)間隨機(jī)選取的方式，設(shè)計(jì)求解MVRPMFC問題的禁忌搜索算法混合鄰域變換，并且借助罰函數(shù)實(shí)現(xiàn)搜索過程中對(duì)不可行解的試探，以跳出局部最優(yōu)點(diǎn)。研究表明，如果針對(duì)物流行業(yè)開發(fā)新的合適的智能配送管理系統(tǒng)，并普及應(yīng)用，對(duì)運(yùn)輸配送業(yè)開征碳稅，并不會(huì)增加行業(yè)成本。相反，碳稅的開征可促進(jìn)運(yùn)輸配送領(lǐng)域提升其智能化程度，這不僅可以促進(jìn)其效率和效益的提升，還可以緩解能源供給壓力、實(shí)現(xiàn)低碳物流、綠色物流，促進(jìn)物流業(yè)轉(zhuǎn)型升級(jí)。

參考文獻(xiàn)（References）：

[1] 李淑琴，楊斌，趙磊，易宣齊.需求帶時(shí)間窗的環(huán)保多車型組合配送路徑優(yōu)化[J].廣西大學(xué)學(xué)報(bào)（自然科學(xué)版），2003.2：388-394

[2] 段鳳華，符卓.帶碳排放約束的異型車輛路徑問題及其禁忌搜索算法[J].鐵道科學(xué)與工程學(xué)報(bào)，2015.12（4）：941-948

[3] 葛顯龍，譚柏川，吳寧謙.基于碳交易機(jī)制的帶時(shí)間窗車輛路徑問題與算法研究[J].管理工程學(xué)報(bào)，2018.32（4）：141-148

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

[5] 葛顯龍，許茂增，王偉鑫.多車型車輛路徑問題的量子遺傳算法研究[J].中國管理科學(xué)，2013：125-133

[6] 符卓.開放式車輛路徑問題及其應(yīng)用研究[D].中南大學(xué)，2004.

[7] 熊浩，胡列格.多車型動(dòng)態(tài)車輛調(diào)度及其遺傳算法[J].系統(tǒng)工程，2009.27（10）：21-24