多行程帶補貨時間窗的成品油多艙配送路徑優(yōu)化

王旭坪，詹紅鑫，孫自來，李芳芳

多行程帶補貨時間窗的成品油多艙配送路徑優(yōu)化

王旭坪1,2，詹紅鑫1，孫自來1，李芳芳3

（1.大連理工大學 系統(tǒng)工程研究所, 遼寧 大連 116023；2.大連理工大學 商學院, 遼寧 盤錦 124221； 3.長江師范學院 管理學院, 重慶 408100）

本文以多行程帶補貨時間窗的成品油二次配送路徑規(guī)劃為研究對象，以運輸成本和派車成本之和最小為優(yōu)化目標，研究多艙位、多行程、多車型、硬時間窗的車輛路徑問題模型?；谙刃谐毯蠓纸M的求解策略對問題進行劃分，并引入行程池的概念，設計了包含內(nèi)外兩層循環(huán)的啟發(fā)式算法。最后，通過多組仿真算例驗證了上述模型和算法的有效性，并通過數(shù)據(jù)實驗揭示了以下規(guī)律：（1）當加油站補貨時間窗分布均勻時，車輛周轉(zhuǎn)次數(shù)和時間利用率相對較高；分布集中時，車輛周轉(zhuǎn)次數(shù)較低且派車量增加；有效的交通管制時間設置，不僅能降低配送成本，還可提高車輛利用率。（2）相對于艙位配載類型固定的車輛配置，配載類型不固定的車輛配置在運輸成本和車載率上具有優(yōu)越性；但當現(xiàn)有車艙配載方案接近或達到當前配送需求的最優(yōu)配置時，配載類型固定的車輛配置在總成本上具有明顯優(yōu)勢。

成品油二次配送; 補貨時間窗; 多行程; 多艙位; 路徑優(yōu)化

0 引言

成品油二次配送（以下簡稱“配送”）位于油品供應鏈的末端，泛指通過油罐車將成品油從油庫配送到各加油站和社會客戶的過程，是提高油品配送效率，降低物流成本的關鍵環(huán)節(jié)。有別于傳統(tǒng)的被動要油模式，近年來，國內(nèi)成品油銷售公司逐漸引入主動配送策略，對附屬加油站的油品存儲和配送進行主動管理；通過先進的物聯(lián)網(wǎng)技術，配送中心能夠?qū)崟r監(jiān)控并預測加油站各種油品的庫存和銷售情況，同時生成配送訂單對加油站進行油品補給。因此，如何實現(xiàn)成品油配送計劃的統(tǒng)一管理、運力資源的統(tǒng)一調(diào)度、降低運輸成本和提高配送效率已成為成品油配送管理的核心問題。

成品油配送是車輛路徑問題（Vehicle Routing Problem, VRP）在油品運輸領域的典型應用，除了具有傳統(tǒng)VRP問題的復雜性（多車型、多產(chǎn)品等）之外，還具有如下油品配送特性：

（1）車輛多艙：成品油配送車輛多為分艙油罐車，可同時裝載不同型號的油品為多個加油站進行配送。且除非油罐車經(jīng)過清洗操作（此時艙位裝載類型不固定），否則每個艙位的油品裝載類型固定，即不同類型油品嚴禁混裝。

（2）滿艙配載：成品油屬于易燃易爆的危險品，在非滿載情況下，液體與罐壁的摩擦容易引發(fā)車輛事故，且晃動的液體不利于車輛的穩(wěn)定行駛，因此成品油配送需要滿足滿艙配載約束。同時，出于配送管理的需要，每個艙位單次配送只能滿足單個加油站單種油品的需求，因此加油站的油品需求量為可用艙位載重的整數(shù)倍。

（3）補貨時間窗：不同于傳統(tǒng)VRP問題的客戶服務時間窗，由于加油站的每一種油品均有獨立的存儲地罐和監(jiān)測設備，因此即使是同一加油站，每種油品的補貨時間窗也不近相同；因此，可能需要車輛在滿足不同油品補貨時間窗的情況下對同一加油站進行多次配送。

（4）多行程配送：由于滿艙配載和加油站多油品的要求，油罐車單次配送的規(guī)模較小，同一油罐車需要執(zhí)行多個行程的配送任務。當前國內(nèi)成品油配送普遍存在調(diào)度不合理的現(xiàn)象，單周期內(nèi)的平均周轉(zhuǎn)次數(shù)僅為2次，車輛利用率較低。

所以成品油配送需要綜合考慮艙位配載類型指派、多行程構造、多行程分配等問題，其求解難度遠大于一般車輛路徑問題。同時，據(jù)中石油報道，在現(xiàn)有的成品油物流體系中，公路配送成本占總物流成本的比重高達60%~70%。研究成品油多艙配送問題，制定經(jīng)濟高效的配送方案，具有重要的理論和實際意義。

針對成品油二次配送路徑優(yōu)化問題，國內(nèi)外學者分別結合不同的配送情景和配送策略展開了研究。國內(nèi)最早由宋潔蔚等對該問題進行了研究，他們根據(jù)加油站的庫存情況和配送網(wǎng)絡結構，對加油站的油品需求量和配送時間窗進行分析，設計了一種可便捷求解的啟發(fā)式算法[1]；熊靜進研究了非滿載情況下的成品油調(diào)度問題，設計了魯棒性較強的禁忌搜索算法和遺傳算法，并結合武鋼交運集團的加油站配送業(yè)務，開發(fā)了成品油配送管理的計算機系統(tǒng)原型[2]；孫麗君采用情景建模的方式分析了成品油配送干擾管理問題，通過決策情景的分析，獲取了關鍵情景要素及其相互間的關系，并構建了決策情景的表示模型，為成品油調(diào)度的實時建模奠定了基礎[3]。李敏等引入了訂單鄰域的概念，將成品油多艙配送訂單的時間、空間和油品類別進行綜合度量，通過聚類的方式構建訂單鄰域系統(tǒng)，并結合改進的量子遺傳算法對所構建的成品油多艙配送模型進行求解[4]。近期，張源凱等建立了多車型多車艙的車輛優(yōu)化調(diào)度模型，提出基于C-W節(jié)約算法的“需求拆分→合并裝載”的車輛裝載策略，并利用Relocate和Exchange算子進行并行鄰域搜索[5]。張立峰等引入了油罐車的最遠分載距離約束，研究了大規(guī)模多車場帶時間窗的成品油配送問題，并提出了“期望節(jié)約里程”指標用于指導遺傳算法的搜索[6]。

在國外相關研究中，成品油配送路徑優(yōu)化問題也被稱為加油站補貨問題。Fabien Cornillier等一直致力于該問題的研究，并針對帶時間窗約束、多油庫配送、多周期配送等情景，分別設計了高效的求解算法，并通過真實算例，驗證算法的有效性[7-10]。此外，針對多周期的加油站配送問題，Vidovi?等提出了可以求解小規(guī)模配送問題（3個配送周期，10個待配送加油站）的整數(shù)規(guī)劃算法，設計了可求解50個加油站，5個配送周期的啟發(fā)式算法[11]。而Popovi?等在考慮多周期配送的同時，引入了庫存優(yōu)化變量，設計了求解的變鄰域搜索算法，最終輸出結果包括油品的配送類別和配送量，以及具體的配送方案[12]。

綜上所述，目前國內(nèi)外學者主要從多車型、多周期、庫存-路徑聯(lián)合配送等方面對成品油多艙配送問題進行研究，較少考慮多行程、多補貨時間窗以及艙位配載類型約束等實際因素的影響。本文在已有研究的基礎上，對固定車輛數(shù)和補貨時間窗約束下的多車型、多車艙、多行程的成品油配送路徑優(yōu)化問題（Multi-Compartment Multi-trips Vehicle Routing Problem with Time Windows，MCMTVRPTW）展開研究；設計了求解的啟發(fā)式算法，該算法借鑒了Christian Prins等[13]提出的先行程后分組的求解策略，利用最大評價因子順序插入法及大鄰域算子分別進行行程的構建和優(yōu)化，采用貪婪策略完成艙位配載類型的指派以及行程的分配。最后，根據(jù)成品油配送實際情況構造算例，驗證了算法的有效性，并進一步通過數(shù)據(jù)實驗分析了多種情景下成品油多艙配送的特點，為配送中心的調(diào)度提供決策建議。

1 問題描述及模型構建

1.1 問題描述

為便于模型的構建和問題的求解，本文有如下說明及假設：

（1）任意訂單的油品需求量均不超過可用車型的最大艙位，且由于成品油配送具有明顯時效性，本文只討論補貨時間窗為嚴格硬時間窗的情形，即配送時間超過時間窗要求，就會造成配送失敗。

（2）忽略油罐車的裝油時間，在執(zhí)行多個行程的間隙，允許在油庫停留，且油庫無服務時間限制，初始時刻設為0；

（3）同一行程不允許重復訪問相同加油站，即無加油站訪問回路，因此，當任意行程包含同一加油站的多種油品訂單時，上述訂單必須在滿足各自補貨時間窗約束的前提下被連續(xù)服務。

1.2 模型構建

結合上述參數(shù)和變量定義，本文構造的成品油配送模型如下：

2 算法整體設計

：初始化行程池AMR和其他算法參數(shù)；

3 MCVRPTW問題可行解的構造與優(yōu)化

3.1 順序插入法

3.1.1 插入有效性檢測

更新早配送時間和最遲配送時間： （1）fortodo（2）;（3）end for（4）fortodo（5）;（6）end for

3.1.2 評價因子

其中：

3.1.3 最大評價因子順序插入法

結合模型特點，本文定義種子訂單的選取遵循以下兩條規(guī)則：

種子訂單的選取兼顧了訂單補貨服務的緊急性以及待配送加油站的距離，并按二者的優(yōu)先級得到了上述兩種規(guī)則。本文采用輪換交替的方式使用這兩個規(guī)則。

最大評價因子順序插入算法的總體步驟如下：

3.2 大鄰域算子

3.2.1 行程拆分

3.2.2 行程重組

（3）分別計算各行程中訪問加油站節(jié)點構成的重心坐標，并按求解TSP問題的貪婪策略，將所有行程根據(jù)各自重心的位置連接成為一條完整的訪問序列。

3.2.3 序列分割

4 MAPLV問題的求解與優(yōu)化

4.1 MCVRPTW可行解的接受規(guī)則

4.2 行程分配算子

4.3 艙位配載類型指派

4.4 MAPLV問題解的評價

4.5 MAPLV問題解的后優(yōu)化

4.5.1 局部優(yōu)化算子

基于盡可能不破壞原有行程結構的原則，本文以單位行程為操作對象，定義三種局部優(yōu)化算子，即重定位算子、交換算子以及插入算子。

（1）重定位算子（Relocate）：任意選取一個行程，將其從當前車輛的配送計劃中移除，并插入到同一配送計劃的其他位置；

（2）交換算子（Swap）：隨機選取兩個位于不同車輛配送計劃的行程，并交換對應位置；

（3）插入算子（Insert）：與重定位算子類似，僅將被選行程插入不同車輛的配送計劃中。

規(guī)則2：優(yōu)先選擇所在配送計劃包含較少行程數(shù)的行程運用插入算子，將其插入至其他配送計劃中；

規(guī)則4：優(yōu)先對車輛運行時間接近上限的配送計劃，采用重定位算子和交換算子；

為了加強整體優(yōu)化效果，上述規(guī)則與隨機規(guī)則一起采用交替使用的方式進行。

4.5.2 重排序算子

（1）上浮操作（Shift_up）：隨機選擇一個訂單，并將其與對應的父節(jié)點交換位置；

（2）下沉操作（Shift_down）：隨機選擇一個訂單，并隨機與其左右子節(jié)點交換位置；

重排序算子中，非首尾端點處的油庫節(jié)點0也參與交換操作，且當有多個0節(jié)點相連時，將其合并為一個，即進行油庫節(jié)點的刪除操作。因此，將油庫節(jié)點引入上述交換操作中，能夠起到減少行程數(shù)目的作用。

5 行程池的更新及行程選擇算子

5.1 行程池的更新

5.2 行程選擇算子

：若AMR不為空，則轉(zhuǎn)Step2；否則轉(zhuǎn)Step6；

6 求解算法的整體描述

綜上所述，MCMTVRPTW問題求解的流程偽代碼如下：

7 算例分析

7.1 算例設置

目前關于成品油多艙配送的研究較少，且實際數(shù)據(jù)獲取難度較大。因此本文分別參考中石油大連市旅順配送區(qū)（以臺山油庫為配送分站，負責轄區(qū)20座加油站配送），東部配送區(qū)（以莊河油庫為配送分站，負責轄區(qū)26座加油站配送）以及北部配送區(qū)（以瓦房店油庫為配送分站，負責轄區(qū)56座加油站配送）的配送規(guī)模和站點分布規(guī)律，仿真生成三組分別包含20，26和56個加油站的坐標數(shù)據(jù)集，定義為區(qū)域0（A0）、區(qū)域1（A1）和區(qū)域2（A2），分別如圖1所示，可知油庫遠離市區(qū)，且所有加油站分布具有中心區(qū)域分布密集、遠郊區(qū)分布稀疏的規(guī)律。

圖1 加油站布局情況

Figure 1 Distribution of gas stations

本文定義4種類型的補貨時間窗分布，即聚集分布（Clustered，C）、均勻分布（Uniform，U）、管制分布（Traffic Control，TC）以及隨機分布（Random，R）。其中，管制分布的出現(xiàn)是由于成品油配送屬于危險品運輸，而在某些城市配送中，其補貨時間窗會根據(jù)交通管制要求做出相應調(diào)整，例如沈陽市規(guī)定：青年大街晝夜禁止貨車通行；而關系民生的槽罐車可以在規(guī)定時間限時進入限行區(qū)域行駛。管制分布類似于聚集分布，不同之處在于管制分布要求管制區(qū)域加油站的補貨時間必須在固定時間范圍內(nèi)，且不同管制區(qū)域的時間要求不盡相同。本文按照算例的信息進行命名，包括坐標數(shù)據(jù)集和補貨時間窗分布類型，例如算例A1-R代表在區(qū)域1執(zhí)行且補貨時間滿足隨機分布的數(shù)值算例。

此外，通過訪談加油站工作人員，獲得成品油配送過程中的一些實際特征，例如國內(nèi)常用油罐車最多分4個艙，加油站每次需求多為2種油品，且單種油品需求量多為5t/10t，而油罐車的固定派車成本與清艙費用均按噸位進行計算?；谏鲜鎏卣?，設置本文所使用車型的相關參數(shù)如表1所示，其中油罐車的固定派車成本為12元/噸，而油罐車清艙費用根據(jù)市場調(diào)研設置為125元/噸；同時，K1類車輛艙位隨機對應一種油品，且使用K2類車輛時需要支付額外的清艙費用。

表1 油罐車車型

7.2 算法參數(shù)設置

算法通過MATALB7.0編程實現(xiàn)，所有程序均是在主頻2.0Ghz、4GB內(nèi)存、Windows7操作系統(tǒng)環(huán)境下運行。

下面對算法中需要預先設定的主要參數(shù)值進行說明：

圖2 門檻值與目標值關系

圖3 運行時間對最優(yōu)解的影響

Figure 3 Traveling time influences on optimal solution

7.3 算法有效性分析

為驗證算法設計的有效性，我們將本文算法與另外兩種算法作了對比，所有對比算法均采用相同運行參數(shù)和環(huán)境，不同之處在于，算法1采用隨機插入的方式構造MCVRPTW問題的初始解；而算法2忽略了后優(yōu)化過程，在調(diào)用行程分配算子對行程進行分配后，直接將其用于行程池的更新；針對每個算例和算法，重復20次獨立運算，分別記錄得到的MCMTVRPTW初始解目標值、優(yōu)化解目標值，并計算20次運算結果的均值、標準差、最優(yōu)值以及搜索到最優(yōu)值的耗時。

表2為采用三種算法對算例進行求解得到的初始解和優(yōu)化解的最優(yōu)值，在初始解取值方面，算法1明顯劣于其他兩種算法，其構造的初始解取值相對于最優(yōu)取值來說平均高出43.83%（最高為110.45%，最低為15.31%），表明本文設計的最大評價因子順序插入法能夠產(chǎn)生較為優(yōu)秀的初始解；同時，12組算例中，算法2和本文算法所得的最優(yōu)初始解取值接近，平均相對差僅為3.87%，且兩種算法獲得初始解最優(yōu)取值的次數(shù)比為1:1.4，在一定程度上說明了本文算法求解結果的穩(wěn)定性。在優(yōu)化解取值方面，本文算法具有明顯優(yōu)勢，相對算法1，其平均優(yōu)化比率達到5.67%（最高為9.98%，最低為0.27%），說明了優(yōu)秀的初始解有利于優(yōu)化解的搜索；而相對算法2，其平均優(yōu)化比率為6.06%（最高為11.59%，最低為2.21%），表明了本文設計的后優(yōu)化算法能夠有效的對可行解進行再優(yōu)化，有助于優(yōu)秀解的發(fā)現(xiàn)；此外，對比算法1和2的求解結果可發(fā)現(xiàn)，盡管算法2產(chǎn)生的初始解均優(yōu)于算法1，但其部分優(yōu)化解卻相對較差，這一現(xiàn)象進一步說明了后優(yōu)化過程的有效性。

表2 最優(yōu)值取值情況

表3為采用三種算法對算例進行求解得到初始解和優(yōu)化解最優(yōu)值所對應的計算時間，在初始解運算時間方面，可以發(fā)現(xiàn)，算法1初始解構造所需的時間要高于其余兩種算法，這主要是由于本文時間窗為硬時間窗，采用隨機插入方式構造初始解時，需要進行更多的時間窗檢測和裝載方案檢測；同時，算法2和本文算法初始解構造所花費時間的平均相對差為3.72%，且獲得最優(yōu)耗時的次數(shù)比為1:1.5，表明了本文算法求解時間的穩(wěn)定性。而在優(yōu)化解的運算耗時方面，本文算法搜索到最優(yōu)解所需的時間整體高于其他兩種算法，并且差距隨著實例規(guī)模的擴大而增加，結合表2結果分析可知，在采用啟發(fā)式方法構造初始解，并增加后優(yōu)化算子之后，本文提出的求解算法能夠在犧牲一定求解時間的前提下，獲取到更為優(yōu)秀的解。

表3 搜索到最優(yōu)值的耗時

圖4 相關結果取值關系

Figure 4 A series of relevant statistical indicators

為進一步證明本文算法求解的穩(wěn)定性，分別記錄每種算法對每個算例進行20次獨立運算后所得優(yōu)化解的均值和標準差，并分別計算每個算例最優(yōu)值與均值的比值、標準差與均值的比值，得到結果如圖4所示。由圖4-1可知，相較于算法1和2，本文算法所得最優(yōu)值與均值的平均差距較?。ㄇ€較為平滑），12組算例中最優(yōu)值與均值的比值控制在范圍[90.62%, 96.65%]內(nèi)，表明算法每次計算均能收斂到固定范圍；此外，由圖4-2可知，本文算法對應的曲線抖動程度相對較弱，12組算例中所得標準差與均值的比值在范圍[3.19%, 7.86%]內(nèi)，說明每個算例的標準差相較于平均值來說較小，即多次運算結果的離散程度不高，因此，對涉及的成品油多行程配送問題來說，本文設計的算法具有較強穩(wěn)定性。

7.4 時間窗分布對調(diào)度結果的影響

為了分析時間窗分布對成品油調(diào)度結果的影響，這一節(jié)調(diào)用本文算法計算各算例在四種時間窗分布情況下的優(yōu)化解，并分別記錄對應的總派車數(shù)、車輛平均執(zhí)行行程數(shù)（平均車輛周轉(zhuǎn)率）、車輛平均執(zhí)行訂單數(shù)、車輛平均工作時長以及車輛平均時間利用率，其中時間利用率定義為車輛運行時長與最小時間跨度（車輛執(zhí)行最后一個行程的最早完成時間與執(zhí)行第一個行程的最晚發(fā)車時間之差）的比值。由于本文模型允許車輛在兩個配送行程間隙在油庫等待，因此車輛時間利用率取值越大，說明車輛在油庫的等待時間越短，配送方案的時間利用效率就越高。

圖5給出了各算例中總派車數(shù)、車輛平均執(zhí)行行程數(shù)、車輛平均執(zhí)行訂單數(shù)三類指標的變化趨勢。可以發(fā)現(xiàn)，在不同時間窗分布情況下，各算例指標的變化趨勢大體相同；相較于其他分布類型來說，時間窗聚集分布的情況類似于油品銷售旺季的配送情景，要求必須在較集中的時間范圍內(nèi)滿足轄區(qū)加油站的所有需求，因此當時間窗跨度較小時，需要同時派出更多的車輛，并且每輛車能夠執(zhí)行的行程數(shù)和訂單數(shù)相對較少，油罐車的周轉(zhuǎn)次數(shù)較低。而對于具有管制特點的時間窗分布，其反應了現(xiàn)實中城市物流的管制要求，由于本文僅考慮多區(qū)域管制分布（配送區(qū)域按行政劃分為多個管制區(qū)域，各區(qū)域的管制時間服從均勻分布）的情景，因此相較于其他類型，其不僅所需的車輛數(shù)較少，且每輛車所執(zhí)行的行程數(shù)和訂單數(shù)較高，提高了油罐車的周轉(zhuǎn)次數(shù)。此外，時間窗聚集分布也可視為一類交通管制情景，即配送區(qū)域均屬于同一管制區(qū)域的情景；此時需要對固定區(qū)域進行集中配送，當油罐車數(shù)量不足時，會引發(fā)加油站斷油現(xiàn)象，對比兩種管制情景下的配送方案可發(fā)現(xiàn)，針對不同配送區(qū)域，采用合適的管制策略，不僅能夠有效的緩解城市交通壓力，更能降低油品的配送成本，提高車輛周轉(zhuǎn)率。

圖6給出了各算例中車輛平均工作時長以及車輛平均時間利用率的變化趨勢。結合圖5內(nèi)容可知，由于每輛車所執(zhí)行的行程數(shù)和訂單數(shù)較少，時間窗聚集分布算例的單車平均工作時間最短，且時間利用率最高（本文算例中均達到100%）；而針對時間窗為多區(qū)域管制分布的算例，油罐車需要在多個時間范圍內(nèi)執(zhí)行多區(qū)域的配送任務，其單車平均工作時間會相對增加，但由于不同配送區(qū)域所在位置和管制時間存在差異，同一車輛的多個行程不一定連續(xù)，因此，其時間利用率反而較低。此外，對于需求時間分布均勻的算例來說，由于配送時間具有較高的連續(xù)性，其單車平均工作時間和車輛平均時間利用率均處于較高水平，車輛利用率較高。

圖5 三類指標的變化趨勢

Figure 5 Change trend of those three indexes

圖6 兩類指標的變化趨勢

Figure 6 Change trend of those two indexes

7.5 車輛配置對調(diào)度結果的影響

為了分析不同車輛配置對調(diào)度結果的影響，本節(jié)將車輛配置情況分為3類，包括所有車輛均為K1類型（即艙位配載類型固定）、K2類型（即艙位配載類型不固定）以及混合類型（即同時存在K1和K2類型的油罐車，本節(jié)中令二者比例為1:1）。由于實際運營中，K2類車輛需要支付額外的清洗費用，其固定派車成本遠高于K1類車輛，因此本節(jié)僅討論車輛配置對運輸成本以及車載率的影響，表4展示了針對算例A0-R，A1-R，A2-R，在不同車輛配置情況下各執(zhí)行參數(shù)的取值。

表4 運行結果中各執(zhí)行參數(shù)的取值

從表4可以看出，不同車輛配置下，同一算例對應的派車數(shù)均相等，這在一定程度上說明了求解結果的有效性和穩(wěn)定性。此外，得益于K2類型車輛艙位配載類型不固定的特點，與其他類型的車輛配置相比，采用K2類型的車輛配置能夠擴大搜索空間，并有效的適應當前配送需求，能夠得到運輸成本最小且車載率較高的配送方案。但同時，由于K2類型車輛的固定派車成本較高，因此盡管其運輸成本較小，但其總成本卻遠高于其他類型，算例中，其運輸成本占總成本的比重遠低于其他車輛配置類型。

表5 兩種車輛配置下的優(yōu)化解及車艙配載方案

此外，分析可知，若K1類車輛的車艙配載類型接近或達到當前配送需求的最優(yōu)配載方案，此時采用K1類車輛執(zhí)行配送方案既能有效降低配送成本，同時也能提高平均車載率。為了驗證上述結論，針對算例A0-R，分別擴大K1和K2類車輛的規(guī)模（其中K1類在增加車輛數(shù)目的同時，盡可能多樣化每個艙位的裝載類型），并調(diào)用本文算法進行求解，最終對比兩種車輛配置下的優(yōu)化解及車艙配載方案結果如表5所示。同時，為直觀的反應兩種配送方案的差異，圖7展示了上述兩種配置下的車輛行駛路徑。可知，兩種車輛配置情況下所得的配送路徑具有相似性，并且除了由于K2類車輛的單位固定派車成本較高，導致固定派車成本差異較大以外，其他執(zhí)行參數(shù)（包括執(zhí)行車輛數(shù)、車型選擇、車艙配載方案、運輸成本以及平均車載率）均相等或小范圍變化。綜上所述，當K1類車輛的艙位配載方案達到或接近當前配送需求的最優(yōu)配置時，能夠有效的降低總成本并提高車輛利用率；對于成品油多艙配送來說，K2類車輛配置的情況，類似于油品換季時，配送中心對油罐車進行統(tǒng)一清罐后的情況，因此，配送中心需要提前預估下個季度每個加油站每種油品的需求情況，并以此為依據(jù)對清罐后的車輛進行配載指派；并且，在配送期間，若當前的艙位配載方案不能滿足配送需求，需要及時對部分車輛進行清罐處理并調(diào)整配載方案。

進一步的分析可知，相較于K1類型和混合類型的車輛配置，盡管K2類型車輛配置能夠獲得更優(yōu)的平均車載率，但由于滿艙配載、硬時間窗、以及車型限制等約束的存在，使得優(yōu)化方案不可避免的出現(xiàn)了艙位空載的現(xiàn)象。尤其是當時間窗較窄時，需要以犧牲車載率為代價滿足上述配送約束。為體現(xiàn)硬時間窗的特點，本文算例的時間窗寬度均設置較窄，而在實際配送中，加油站補貨時間窗的設置并不一定嚴格（均為窄時間窗），因此，平均車載率可達到更高值。為驗證時間窗對車輛裝載率的影響，針對算例A0-R，將所有訂單的時間窗寬度擴大5倍（即盡可能保證在任意情況下，配送方案均滿足時間窗需求），調(diào)用本文算法可知在K1類、K2類、混合類車輛配置情況下，配送方案的車輛使用數(shù)平均減小了21%，同時平均車載率可分別達到78.16%，94.21%，86.38%。上述分析也說明了有效的補貨時間窗設定，能進一步提高車輛利用率。

圖7 兩種車輛配置下的車輛行駛路

Figure 7 Driving route under two kind of truck configurations

8 結論

文中針對帶補貨時間的成品油二次配送問題建立了多艙位、多行程、多車型、硬時間窗的車輛路徑問題模型，將原問題（MCMTVRPTW）分解為帶時間窗的多艙位車輛路徑問題（MCVRPTW）和有車輛數(shù)量限制的多行程指派問題（MAPLV），通過引入行程池的概念，按先行程后分組的求解策略設計了包含內(nèi)外兩層循環(huán)的啟發(fā)式算法。其中，外循環(huán)通過最大評價因子順序插入法及行程選擇算法構造MCVRPTW問題的初始解和可行解，而內(nèi)循環(huán)采用行程分配算子用于行程的指派并對部分車輛的艙位配載類型進行安排；同時，還調(diào)用多種局部搜索算子對原問題可行解進行再優(yōu)化。本文結合大連市中石化加油站的分布情況，構造多組算例驗證了上述模型和算法的有效性，算例結果表明：（1）本文設計的求解算法性能穩(wěn)定且有效，其中，最大評價因子順序插入法能夠快速生成較優(yōu)的MCVRPTW問題初始解，而后優(yōu)化算子能夠以犧牲部分求解時間為代價搜尋到更優(yōu)秀的可行解。（2）針對同一配送區(qū)域，不同補貨時間窗分布會對調(diào)度結果產(chǎn)生不同的影響，其中，聚集分布的時間窗會增加派車量，其車輛周轉(zhuǎn)次數(shù)較低，但時間利用率最高；分布均勻的時間窗，其車輛周轉(zhuǎn)次數(shù)和時間利用率均處在較高水平；此外，有效的交通管制措施，能在降低配送成本的同時，提高車輛利用率。（3）盡管派車成本較高，但由于艙位裝載的靈活性，艙位配載類型不固定的車輛配置能夠在降低運輸成本的同時提高車載率；而當現(xiàn)有車艙配載類型接近或達到當前配送需求的最優(yōu)配置時，總成本將得到極大降低，同時車載率也能得到有效提升。

[1] 宋潔蔚,榮岡.成品油配送中時間窗的確定及運輸?shù)陌才臶J]. 系統(tǒng)工程理論與實踐,2003,(04):63-69+81.

Song J W, Rong G. Time Window Confirmation and Transportation Arrangement of Oil Distribution [J]. Systems Engineering-Theory Practice, 2003,(04):63-69+81.

[2] 熊靜進.成品油配送中車輛優(yōu)化調(diào)度問題的研究與應用[D].武漢大學,2005.

Xiong J J. The Research of Vehicle Routing Problem in oil distribution [D].Wuhan University, 2005.

[3] 孫麗君.成品油配送干擾管理問題決策情境的表示方法研究[A]. 中國系統(tǒng)工程學會.中國系統(tǒng)工程學會第十八屆學術年會論文集——A01系統(tǒng)工程[C].中國系統(tǒng)工程學會:2014:3.

Sun L J.Representation of decision scenario for disruption management of petroleum products distribution. Systems Engineering Society of China. Proceeding of 18th Annual Conference of Systems Engineering Society of China-A01 Systems Engineering [C]. Systems Engineering Society of China: 2014: 3.

[4] 李敏,倪少權,周凌,等.基于訂單鄰域的成品油二次配送中帶時間窗車輛路徑規(guī)劃問題[J].計算機集成制造系統(tǒng),2015,21(8):2158-2169.

Li M, Ni S Q, Zhou L, et al. Vehicle routing problem with time windows of petroleum products distribution based on order neighborhood system[J]. Computer Integrated Manufacturing Systems, 2015, 21(8): 2158-2169.

[5] 張源凱,孫麗君,胡祥培.成品油配送多車艙車輛指派及路徑優(yōu)化問題研究[J].運籌與管理,2017,26(07):1-9.

Zhang Y K，Sun L J，Hu X P, Multi-compartment Vehicle Dispatching and Routing for Product Oil Distribution[J].Operations Research and Management Science,2017,26(07):1-9.

[6] 張立峰,易萬里,劉曉蘭.基于兩階段算法的大規(guī)模成品油二次配送優(yōu)化[J].系統(tǒng)工程理論與實踐,2016,36(11):2951-2963.

Zhang L F, Yi W L, Liu X L. Two-stage optimization algorithm for large scale secondary petroleum product delivery planning[J]. Systems Engineering-Theory Practice, 2016, (11): 2951-2963.

[7] Cornillier F, Boctor F, Laporte G, et al. A heuristic for the multi-period petrol station replenishment problem [J]. European Journal of Operational Research, 2008, 191(2): 295-305.

[8] Cornillier F, Boctor F, Renaud J. Heuristics for the multi-depot petrol station replenishment problem with time windows [J]. European Journal of Operational Research, 2012, 220(2): 361-369.

[9] Boctor F, Renaud J, Cornillier F. Trip packing in petrol stations replenishment [J]. Omega, 2011, 39(1): 86-98.

[10] Cornillier F, Laporte G, Boctor F, et al. The petrol station replenishment problem with time windows [J]. Computers & Operations Research, 2009, 36(3): 919-935.

[11] Vidovi? M, Popovi? D, Ratkovi? B. Mixed integer and heuristics model for the inventory routing problem in fuel delivery [J]. International Journal of Production Economics, 2014, 147(147): 593-604.

[12] Popovi? D, Vidovi? M, Radivojevi? G. Variable neighborhood search heuristic for the inventory routing problem in fuel delivery [J]. Expert Systems with Applications, 2012, 39(18): 13390-13398.

[13] Prins C, Lacomme P, Prodhon C. Order-first split-second methods for vehicle routing problems: A review[J]. Transportation Research Part C, 2014, 40(1):179-200.

[14] Beasley J E. Route first—Cluster second methods for vehicle routing[J]. Omega, 1983, 11(4):403-408.

[15] 呂圣杰.我國成品油二次配送路徑優(yōu)化分析[J].中國儲運,2016(2):118-120.

Lv S J.Optimization analysis of secondary petroleum product delivery in China.China Storage and Transport,2016(2):118-120.

[16] 余國印.成品油二次物流配送車輛調(diào)度問題研究[D].重慶交通大學,2016.

Yu G Y, Research on Vehicle Scheduling Problem Of the Refined Oil Secondary Logistics Distribution[D].Chongqing Jiaotong University, 2016.

[17] 程少雄.基于C-W節(jié)約算法成品油二次配送車輛路線優(yōu)化研究[D].長安大學,2015.

Chen S X. The Research of Refined Oil Secondary Distribution Vehicle Route Optimization Problem Based on the C-W Saving Algorithm[D].Chang’an University.2015.

[18] 李敏,黃強,周凌,等.面向?qū)ο驪etri網(wǎng)的成品油配送模型構建研究[J].計算機工程與應用, 2015, 51(20):55-61.

Li M, Hung Q, Zhou L. et al. Research on modeling of petroleum products distribution system based on object-oriented Petri nets[J]. CEA, 2015, 51(20): 55-61.

[19] 林宇肖.考慮油品隔離的成品油城市配送路徑優(yōu)化[D].大連海事大學,2015.

Lin Y X, Vecicle Routing Optimization of the Refined Oil Product Redistribution Considering the Isolation[D].Dalian Maritime University,2015.

[20] Villegas P A, Albornoz V M. Large Scale Petrol Station Replenishment Problem with Time Windows: A Real Case Study[C]// International Conference on Operations Research and Enterprise Systems. 2016:408-415.

[21] Benantar A, Ouafi R, Boukachour J. A Petrol Station Replenishment Problem: New Variant and Formulation[C]// IEEE International Conference on Logistics Operations Management. IEEE, 2014.

[22] Carotenuto P, Giordani S, Massari S, et al. A Multi-depot Periodic Vehicle Routing Model for Petrol Station Replenishment [J]. 2016.

[23] Triki C, Al-Hinai N. The Periodic Petrol Station Replenishment Problem: An Overview[C]// Biennial Conference of the Indian Society of Industrial and Applied Mathematics. 2015.

[24] Wassan N, Wassan N. The Multiple Trip Vehicle Routing Problem with Backhauls[J]. Computers & Operations Research, 2017, 78(C):454-467.

[25] Braga N, Alves C, Macedo R. Exact Solution of the Multi-trip Inventory Routing Problem using a Pseudo-polynomial Model[C]// International Conference on Operations Research and Enterprise Systems. 2017:250-257.

[26] Grangier P, Gendreau M, Lehuédé F, et al. An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization[J]. European Journal of Operational Research, 2016, 254(1):80-91.

[27] Coelho V N, Grasas A, Ramalhinho H, et al. An ILS-based algorithm to solve a large-scale real heterogeneous fleet VRP with multi-trips and docking constraints[J]. European Journal of Operational Research, 2016, 250(2):367-376.

[28] 宋強. 多行程車輛路徑問題中變鄰域搜索算法的應用[J]. 數(shù)學的實踐與認識, 2017(19).

Song Q. The Application of Variable Neighborhood Search Algorithm for MTVRP.Journal of Mathematics in Practice and Theory, 2017(19).

[29] 梁文博. 多車程帶時間窗車輛路徑問題的模型和算法[D]. 大連理工大學, 2011.

Liang W B. Model and Algorithm of the Vehicle Routing Problem with Multiple Trips and Time Windows[D].Dalian University of Technology,2011.

[30] 許爭爭, 唐加福. 基于協(xié)作的三階段啟發(fā)式算法求解多行程車輛行程問題[J]. 南開大學學報(自然科學版), 2015(5):51-59.

Xu Z Z, Tang J F. Three-stage Algorithm to Multi-trip Vehicle Routing Problem Based on Coordination[J]. Acta Scientiarum Naturalium Universitatis Nankaiensis(Natural Science Edition) 2015(5):51-59.

Optimization of routes for multi-compartment, multi-trip refined oil distribution with replenishment time

WANG Xuping1,2, ZHAN Hongxin1, SUN Zilai1, LI Fangfang3

(1. Institute of Systems Engineering, Dalian University of Technology, Dalian 116023, China; 2. School of Business, Dalian University of Technology, Panjin 124221, China;3. School of Management, Yangtze Normal University, Chongqing 408100, China)

Oil refining logistics integrate the functions of transportation, warehousing, distribution, information processing, and so on. They are embedded throughout the entire petrochemical industry chain and connect refineries, oil depots, and gas stations to form the complete sales network. At present, China's refined oil consumption ranks third in the world, and its refined oil industry has become important to national economic development. Domestic refined oil distribution mainly refers to the process of distributing oil products from oil depots to gas stations and consumers in society. In recent years, domestic petroleum companies have gradually introduced active oil distribution strategies to affiliated gas stations, and product storage and distribution are being actively managed, a change from the traditional passive oil model. Using advanced logistics network technology, distribution centers can monitor and predict inventory and sales of various oil products in gas stations in real time, then generate distribution orders to these stations. Therefore, achieving unified management of refined oil distribution and scheduling of transportation resources, reducing transportation costs, and improving distribution efficiency have become core issues of refined oil distribution management.

Multi-compartment Vehicle Routing Problem (MCVRP) is widely used in all aspects of social production including livestock transportation, chemical recycling, and cold chain distribution. However, unlike other applications, multi-cabin distribution of refined oil products has the following characteristics:

(1) Unless the tanker has been cleaned, the oil loading type of each compartment is fixed, that is, different types of oil are strictly prohibited to be mixed.

(2) The refined oil is a dangerously flammable and explosive product. Under the condition of non-full load, the friction between the liquid and the tank wall is likely to cause a vehicle accident, and the sloshing liquid is not conducive to the stable running of the vehicle, so the oil product distribution needs to meet the full tank load constraint.

(3) Since each oil product of the gas station has an independent storage tank, monitoring equipment and replenishment time window, the vehicle must make multiple deliveries to the same gas station to satisfy the different oil replenishment time windows. In addition, due to the requirements of full tank load and multi-type at the gas station, the single distribution of a tank truck is small, and the same tank truck needs to perform multiple distribution tasks. The average vehicle in a single cycle turns over twice, and the vehicle utilization rate is low.

In conclusion, the distribution of refined oil products needs to comprehensively consider a series of decisions, such as cabin load type assignment, multi-trip construction, multi-trip distribution, etc., and the difficulty of solving is much larger than the general vehicle routing problem. At present, domestic and foreign scholars mainly study the multi-cabin distribution problem of refined oil products from the perspective of multi-type, multi-cycle, inventory-path joint distribution, etc., and few consider the impact of practical factors such as multi-trip, multiple replenishment time windows, and multi-compartment load type. Based on the above background, this paper takes multi-trip with replenishment time window for secondary distribution route planning of refined oil products as the research object, and builds the vehicle path problem model for hard time windows, multi-compartment, multi-trip, and multi-vehicle with the combined minimum of transportation and dispatching costs.

In order to solve this problem, this paper introduces the concept of Adaptive Memory of Routes (AMR) and designs a heuristic algorithm with two layers of iterative algorithm. The algorithm divides the original problem into a Multi-compartment Vehicle Routing Problem with Time Windows (MCVRPTW) and a multi-trip distribution problem with limited vehicles (Multi-trip Assigning Problem with Limited Vehicles, MAPLV), based on the solution strategy of route-first grouping-second, wherein MCVRPTW is used for the construction of feasible trips - ignoring multi-trip in the original problem and limited vehicle constraints - to minimize the total transportation time of the vehicles, and MAPLV is used to assign limited vehicles and designate the load type of each compartment, based on the above-mentioned itinerary. Meanwhile, heuristic methods such as the sequential insertion algorithm, large neighborhood operator, trip assignment operator, and re-optimization operator are designed to solve the above two kinds of problems independently, and the original problem is continuously searched through the interactive iteration of the above two problems to reach the optimal feasible solution.

In this paper, the effectiveness of the above models and algorithms is verified by multiple simulation examples, and the following patterns are revealed through data experiments: (1) When the refueling time window of the gas station is evenly distributed, the vehicle turnover and time utilization rate are relatively high. When the distribution is concentrated, the vehicle turnover is lower and the number of dispatched vehicles is higher; the effective traffic control time setting can not only reduce the distribution cost, but also improve the vehicle utilization rate. (2) Compared with the fixed vehicle load type configuration, the non-fixed vehicle configuration is superior in terms of transportation cost and loading rate; however, when the existing compartment load type is close to or meets the current distribution requirements in an optimal configuration, a fixed load type configuration has significant advantages in terms of total cost.

Refined oil distribution; Replenishment time windows; Multi-trip; Multi-compartment; Route optimization

2017-12-10

2018-06-04

National Natural Science Foundation of China (71471025, 71531002)

TP301.6

A

1004-6062(2020)04-0182-014

10.13587/j.cnki.jieem.2020.04.020

2017-12-10

2018-06-04

國家自然科學基金資助項目（71471025、71531002）

王旭坪（1962—），男，遼寧錦州人；大連理工大學系統(tǒng)工程研究所教授，博士，博士生導師；研究方向：電子商務與物流管理、突發(fā)事件應急管理。

中文編輯：杜 ?。挥⑽木庉嫞築oping Yan