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

何小年 彭瓊

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

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

中圖分類號：TP391? ? ? ? ? 文獻標志碼：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 引言

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

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

1 MVRPMFC問題描述與數學模型

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

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

因此，MVRPMFC數學模型為：

滿足： ⑴

⑵

⑶

⑷

⑸

⑹

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

2 求解MVRPMFC的禁忌搜索算法

2.1 初始解

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

2.2 鄰域結構

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

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

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

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

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

2.3 解的評價

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

2.4 禁忌表

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

2.5 終止準則

當總迭代步數達到一個給定值，或在給定的連續迭代步數內當前的最好解沒有改變時，則終止搜索。

3 算例測試與比較

3.1 算例一

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

本文以距離為優化目標固定費用為600，可變油耗費用為1112.35，總費用為1712.35;以油耗為優化目標固定費用為620，可變油耗費用為958.27，總費用為1578.27。

表1中結果表明：雖然以距離為優化目標總距離比以油耗為優化目標要短，但是以油耗為優化目標總費用比以距離為優化目標的總費用節約了134.08，節約了7.83%。

3.2 算例二

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

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

文獻[7]以距離為目標的動態求解的最優線路成本為393.22，線路油耗為9977.7;以油耗為目標的動態求解最優解油耗成本為9070.9，運輸總路程為443.3。本文以距離為優化目標線路油耗為11749.21;以油耗為優化目標線路總油耗為11363.37。

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

4 結論

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

參考文獻（References）：

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

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

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

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

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

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

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