油耗最小化多車(chē)型車(chē)輛路徑問(wèn)題研究

何小年 彭瓊

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

關(guān)鍵詞： 多車(chē)型車(chē)輛路徑問(wè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 引言

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

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

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

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

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

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

滿足： ⑴

⑵

⑶

⑷

⑸

⑹

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

2 求解MVRPMFC的禁忌搜索算法

2.1 初始解

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

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

本文使用Or-opt方法，Or-opt方法是k-opt中的一種，k-opt通過(guò)每次交換條k邊來(lái)改進(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ì)可行變換加以說(shuō)明，其中帶下劃線者為所挑選的頂點(diǎn)。

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

2.4 禁忌表

禁忌表用于記載最近的5～10（隨機(jī)挑選）次迭代中解的變換特征。可以構(gòu)造一組（n+1）×（n+1）階矩陣來(lái)記錄禁忌情況。若點(diǎn)i和j被挑選來(lái)進(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)前的最好解沒(méi)有改變時(shí)，則終止搜索。

3 算例測(cè)試與比較

3.1 算例一

本文提出的禁忌搜索算法已用Delphi編程。為了測(cè)試算法的計(jì)算效果，采用文獻(xiàn)[5]算例，所有車(chē)型車(chē)輛不受行駛距離限制，要求合理安排配送車(chē)輛的配送路線，使完成配送任務(wù)的總油耗最少。以距離為優(yōu)化目標(biāo)和油耗為優(yōu)化目標(biāo)分別利用本文算法對(duì)文獻(xiàn)[5]進(jìn)行求解，經(jīng)過(guò)20次運(yùn)算結(jié)果中最優(yōu)解見(jiàn)表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]中沒(méi)有考慮車(chē)輛的固定成本，本文假設(shè)三種車(chē)型的固定費(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種車(chē)型中最大車(chē)型的容量的限制。

文獻(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)兩種情況中都有一條線路上的配送量超出車(chē)輛裝載量的限制。本文所得到的解是可行的，以距離為優(yōu)化目標(biāo)雖然距離比以油耗為優(yōu)化目標(biāo)的距離要短，但是以油耗為目標(biāo)比以距離為優(yōu)化目標(biāo)線路總油耗節(jié)約了3.28%。

4 結(jié)論

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

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

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

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

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

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

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

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

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