何小年 彭瓊

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

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

中圖分類號：TP391? ? ? ? ? 文獻標(biāo)志碼：A? ? ?文章編號：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 引言

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

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

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

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

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

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

滿足： ⑴

⑵

⑶

⑷

⑸

⑹

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

2 求解MVRPMFC的禁忌搜索算法

2.1 初始解

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

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

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

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

⑴ Or-opt-1，將一段路徑1個頂點在另外兩個頂點間重新定位，例如：

⑵ Or-opt-2，將一段路徑2個頂點在另外兩個頂點間重新定位，例如：

⑶ Or-opt-3，將一段路徑3個頂點在另外兩個頂點間重新定位，例如：

2.3 解的評價

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

2.4 禁忌表

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

2.5 終止準則

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

3 算例測試與比較

3.1 算例一

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

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

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

3.2 算例二

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

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

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

結(jié)果比較表明：文獻[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é)論

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

參考文獻（References）：

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

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

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

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

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

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

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