基于需求緊迫度的成品油配送方法

摘要：針對成品油配送中出現(xiàn)不同程度緊急配送請求時的路徑規(guī)劃問題，文章建立了一種基于需求緊迫度的成品油配送路徑規(guī)劃模型，在考慮常規(guī)配送成本的基礎(chǔ)上，針對違反時間窗約束的配送請求，根據(jù)需求緊迫度的不同，施加相應(yīng)程度的追加懲罰，以實現(xiàn)對緊急程度較高的供油請求進(jìn)行優(yōu)先配送。為了驗證模型效果，文章通過借鑒大規(guī)模鄰域搜索算法中的破壞修復(fù)策略，將破壞修復(fù)操作引入遺傳算法中，形成改進(jìn)遺傳算法，并應(yīng)用該算法進(jìn)行實驗仿真。實驗結(jié)果表明，文章所提出的模型及算法在應(yīng)對出現(xiàn)不同緊迫度的成品油配送路徑規(guī)劃問題時能夠取得良好的效果。

關(guān)鍵詞：需求緊迫度；成品油配送；路徑規(guī)劃；破壞修復(fù)操作；改進(jìn)遺傳算法

中圖分類號：F252.1;U116.2 文獻(xiàn)標(biāo)志碼：A" DOI：10.13714/j.cnki.1002-3100.2023.20.001

Abstract： Aiming at the path planning problem when there are different degrees of urgent delivery requests in refined oil distribution， this paper establishes a refined oil distribution path planning model based on the urgency of demand. For distribution requests，aceording to the different urgency of demand，additional penalties are imposed to achieve priority distribution of fuel supply requests with higher urgency. In order to verify the effectof the model，the article introduces the damage repair operation into the genetic algorithm by referring to the damage repair strategy in the large-scale neighborhood search algorithm to form an improwved genetic algorithm， and uses the algorithm for experimental simulation. The experimental results show that the model and algorithm proposed in this paper can achieve good results in dealing with the problem of route planning for refined oil distribution with different urgency.

Key words： demand urgency; refined oil distribution; path planning： damage repair operation; improved genetic algorithm

0引言

成品油配送是指石油銷售公司根據(jù)各加油站的需求，將成品油從油庫配送到各加油站的過程，在此過程中進(jìn)行合理的路徑規(guī)劃可以起到降低配送成本、提高配送效率的作用\"。針對該問題，楊渝華構(gòu)建了多車型多油品的成品油配送車輛調(diào)度模型，并應(yīng)用了改進(jìn)遺傳算法進(jìn)行求解，王博弘等以配送總距離最短為目標(biāo)構(gòu)建了優(yōu)化模型，并運用混合遺傳模擬退火算法進(jìn)行求解，王旭坪等4，金驍5則搭建了以配送成本最小為目標(biāo)的路徑規(guī)劃模型，并應(yīng)用蟻群算法進(jìn)行求解，羅思妤同時考慮到成品油在運輸過程中的損耗和車輛的燃油消耗，構(gòu)建了考慮油品損耗的成品油的配送路徑規(guī)劃模型，并應(yīng)用改進(jìn)遺傳算法進(jìn)行求解，李珍萍等則在研究該問題時重點考慮了司機(jī)的工作量均衡問題，并設(shè)計了變鄰域禁忌搜索算法進(jìn)行求解。

然而，隨著我國經(jīng)濟(jì)的迅速發(fā)展，石油消費總量快速增加，油料配送過程中緊急配送請求的頻率也在隨之增加回，這導(dǎo)致油料配送請求可能會呈現(xiàn)出不同的緊迫度。對于緊迫度較高的配送請求，若無法及時滿足，可能會導(dǎo)致加油站出現(xiàn)斷供風(fēng)險，這不僅會影響到加油站內(nèi)客戶的用油需求，還會給加油站帶來較大的經(jīng)濟(jì)損失，而對于緊迫度較低的請求，其影響則相對較小，通常為常規(guī)配送請求。目前，針對成品油配送方面的研究多以配送距離和成本為主，而較少考慮到配送請求的緊迫度所帶來的影響，這可能導(dǎo)致部分緊迫配送請求因無法及時得到滿足而產(chǎn)生較大的損失。

針對以上問題，本文建立了一種基于需求緊迫度的成品油配送路徑規(guī)劃模型，在考慮常規(guī)配送成本的基礎(chǔ)上，根據(jù)不同配送請求的緊迫度，對違反時間窗約束的配送請求施加相應(yīng)程度的追加懲罰，以實現(xiàn)對緊迫度較高的配送請求進(jìn)行優(yōu)先配送。同時，通過借鑒大規(guī)模領(lǐng)域搜索算法中的破壞修復(fù)策略，將破壞修復(fù)操作引入遺傳算法中，形成改進(jìn)遺傳算法，并應(yīng)用其對模型進(jìn)行求解，從而得到符合當(dāng)下實際配送需要的路徑規(guī)劃結(jié)果。

1考慮需求緊迫度的配送模型

1.1問題描述

本文所研究的問題可以簡單描述為：存在一個油庫和多個加油站，油庫通過使用一定數(shù)量的油罐車對所在區(qū)域內(nèi)的多個加油站進(jìn)行配送，加油站的位置、油料需求，以及緊迫度等數(shù)據(jù)已知，考慮油罐車載重、加油站可接受的最晚配送時間、以及需求緊迫度等約束條件，對配送路徑進(jìn)行合理規(guī)劃，實現(xiàn)對緊迫度較高的需求點進(jìn)行優(yōu)先配送，并使得總配送費用最少。

1.2模型假設(shè)

為方便構(gòu)建數(shù)學(xué)模型，本文針對上述問題做出如下假設(shè)：第一，假設(shè)各加油站配送請求的時間窗及緊迫度數(shù)據(jù)已知，且不存在相互沖突的現(xiàn)象；第二，假設(shè)油庫與各加油站的位置信息、單位距離運費、車輛固定成本等信息均已知；第三，假設(shè)所用的油罐車型號相同，且相關(guān)信息均已知，無需考慮行駛里程約束；第四，假設(shè)所有油罐車均從油庫出發(fā)進(jìn)行配送，且在完成配送后，需返回油庫；第五，假設(shè)每個油罐車所運輸?shù)挠推废嗤?，且在各加油站卸油前后需靜置一次；第六，假設(shè)每個加油站僅能由一輛油罐車進(jìn)行配送，但每輛油罐車在滿足約束的前提下可以為多個加油站提供配送服務(wù)。

1.3符號說明

本文模型構(gòu)建需要的符號及其說明如表1所示。

1.4模型建立

由所述問題可知，在配送時應(yīng)考慮對緊迫度較高的請求進(jìn)行優(yōu)先配送，同時使總配送成本最少，因此得到如下目標(biāo)函數(shù)。

約束條件，如下。

式（1）為目標(biāo)函數(shù)，包括油罐車的固定使用成本、可變運輸成本、超時懲罰成本、卸油成本、以及對緊急配送請求超時配送時的追加懲罰成本；式（2）要求油罐車所能裝載的最大油量不能超過油罐車的載重量；式（3）要求每個加油站僅被一輛油罐車服務(wù)一次；式（4）要求所有從油庫出發(fā)的油罐車在完成配送后，最終將返回油庫；式（5）要求到達(dá)加油站與離開加油站的油罐車是同一輛；式（6）表示油罐車到達(dá)加油站j的時間與到達(dá)前一個加油站i的關(guān)系；式（7）表示關(guān)聯(lián)系數(shù)x，μ，x， Xa，ya是0，1變量，取值只能為0或1。

2引入破壞修復(fù)的遺傳算法

遺傳算法最早由Holland°提出，是一種用于尋找問題最優(yōu)解的優(yōu)化算法，它通過模擬達(dá)爾文進(jìn)化論中的遺傳變異、自然選擇等生物進(jìn)化方式，從而逐漸逼近問題的最優(yōu)解，具有適應(yīng)性強(qiáng)、魯棒性強(qiáng)等特點，但也存在容易陷入局部最優(yōu)解的問題1。引入破壞修復(fù)操作的改進(jìn)遺傳算法，通過借鑒大規(guī)模鄰域搜索算法中的破壞和修復(fù)策略，從而使其局部搜索能力得到較大提升川，在求解復(fù)雜的組合優(yōu)化問題時，也能取得良好的效果。考慮需求緊迫度的成品油配送問題是典型的多目標(biāo)組合優(yōu)化問題，因此，本文選用該算法進(jìn)行求解，步驟如下。

2.1染色體編碼

染色體編碼方式主要包括二進(jìn)制編碼、Gray編碼、自然數(shù)編碼等，本文研究的是基于次序的組合優(yōu)化問題，因此采用自然數(shù)編碼，以減少無效解的生成。

假設(shè)當(dāng)前有n個加油站， k輛油罐車，將每個加油站從1到n進(jìn)行編號，將每輛油罐車從n+1到n+k進(jìn)行編號，可以使用這些編號表示對各加油站的配送順序，考慮到使用k輛車進(jìn)行配送，因此可以將每輛車的編號用于分隔不同的配送路線，以表示各車輛不同的配送路徑。

2.2初始化種群

為了實現(xiàn)初始種群在搜索空間內(nèi)的均勻分布，同時避免在搜索過程中陷入局部最優(yōu)，本文采用隨機(jī)數(shù)生成器生成初始種群。由于本文采用自然數(shù)編碼，在使用k輛車對n 個客戶點進(jìn)行配送的情況下，在初始化種群時只需生成p個長度為n+k-1的初始染色體編碼，且每個編碼為一個1到n+h-1的全排列，p 代表設(shè)定的初始種群規(guī)模。

2.3適應(yīng)度函數(shù)

在遺傳算法中個體的優(yōu)劣可以通過適應(yīng)度函數(shù)來衡量，對于最小化的組合優(yōu)化問題，其目標(biāo)是使目標(biāo)函數(shù)值最小，為了實現(xiàn)這一目標(biāo)，我們需要將目標(biāo)函數(shù)轉(zhuǎn)換為適應(yīng)度函數(shù)。在適應(yīng)度函數(shù)中，個體的適應(yīng)度值越大，說明個體性能越好，故此時適應(yīng)度應(yīng)為目標(biāo)函數(shù)的逆函數(shù)。令Z 為種群中個體i對應(yīng)的目標(biāo)函數(shù)值，f 代表個體i的適應(yīng)度，則轉(zhuǎn)換方式為： f=1/Z。

2.4選擇操作

選擇算子以一定的概率從種群中選擇若干個體，是一種基于適應(yīng)度高低的優(yōu)勝劣汰過程，輪盤賭算法是最簡單常用的選擇算子之一，在該方法中，個體被選擇的概率與其適應(yīng)度成正比，個體的適應(yīng)度值越大，被選擇的概率也越大?，F(xiàn)假設(shè)某種群大小為M， 染色體為i， 對應(yīng)的目標(biāo)函數(shù)值為Z， 適應(yīng)度為f， 則具體操作步驟如下。

步驟1：計算種群中每個個體的適應(yīng)度值，fi=1/Z。

步驟2：計算個體適應(yīng)度占種群總適應(yīng)度的比例，

步驟3：計算種群中每個個體的累計概率， q=Zp。

步驟4：隨機(jī)生成0-1之間的隨機(jī)數(shù)x， 若q-≤x≤q，則選擇選擇個體i。

2.5交叉操作

傳統(tǒng)的單點交叉或多點交叉方法操作簡單，但存在無法遍歷所有非法情況的問題，搜索效果不佳，且本文在之前的編碼環(huán)節(jié)采用了自然數(shù)編碼，故本文采用當(dāng)前主流的類部分匹配交叉法作為交叉算子，見圖1，主要步驟如下。

步驟1：隨機(jī)在父代個體中產(chǎn)生兩個交叉點，并定義兩點之間的區(qū)域為交叉區(qū)域。

步驟2：將父代B的交叉區(qū)域移動到A的前面，A的交叉區(qū)域移動到B的前面，得到中間個體a'，b'。

步驟3：在中間個體a'和b'中，自交叉區(qū)域后依次刪除與交叉區(qū)域重復(fù)的基因位，從而得到新的個體a，b。

2.6變異操作

本文采用經(jīng)典的倒位變異算子來調(diào)整種群中的個體，從而增加種群的多樣性，防止過早收斂的現(xiàn)象，優(yōu)化算法的尋優(yōu)性能，見圖2，具體步驟如下。

步驟1：隨機(jī)在個體中產(chǎn)生兩個變異點，并定義兩點之間的區(qū)域為變異區(qū)域。

步驟2：將變異區(qū)域中的基因位按照相反的順序重新插入到原位置中，從而得到新的個體。

2.7破壞修復(fù)操作

破壞修復(fù)的實質(zhì)是通過交替對基因位進(jìn)行破壞和修復(fù)操作，來嘗試改善解的質(zhì)量，破壞算子的主要方法有隨機(jī)移除、最差移除、相似移除等，修復(fù)算子的主要方法有隨機(jī)插入、貪婪插入等，本文采用當(dāng)前主流的隨機(jī)移除法及貪婪插入法作為破壞算子及修復(fù)算子，具體步驟如下。

步驟1：首先使用隨機(jī)移除法，隨機(jī)移除當(dāng)前個體中的任意基因位，如個體W=“7215643”， 隨機(jī)移除基因位2，5，則得到中間個體w'=“71643”。

步驟2：使用貪婪修復(fù)法對個體進(jìn)行逐位修復(fù)，首先嘗試將基因位2重新插入中間個體，并依據(jù)貪婪原則，選擇其中有效且最優(yōu)的中間個體，如w\"=“271643”。

步驟3：繼續(xù)使用貪婪修復(fù)法對個體進(jìn)行逐位修復(fù)，直到修復(fù)完成，如此時w=“2571643”。

3實驗仿真

現(xiàn)假設(shè)某油庫負(fù)責(zé)對所在區(qū)域內(nèi)的25個加油站進(jìn)行供油配送，以此為例進(jìn)行仿真，其中，6號、7號、8號、12號、14號加油站由于節(jié)假日突發(fā)的用油高峰，預(yù)計將出現(xiàn)油料短缺的情況，緊迫度較高，若無法得到及時配送，可能帶來較大的損失，現(xiàn)將部分?jǐn)?shù)據(jù)展示如下，該仿真數(shù)據(jù)以Solomon算例為基礎(chǔ)進(jìn)行改編，其中0號點為油庫，1—25號點為加油站。具體配送詳情見表2。

假設(shè)該油庫所采用的油罐車載重為25噸，車輛固定成本為300元，單位運費為30元/公里，超時懲罰系數(shù)為120元/小時，追加懲罰系數(shù)為500，卸油成本為10元/分鐘，卸油前后所需的總靜置時間為30分鐘，卸油前后處理膠管余油時間約為5分鐘，卸油速度為0.5噸/分鐘。

首先以MatLab為工具，對本文所提出的引入破壞修復(fù)操作的改進(jìn)遺傳算法的有效性進(jìn)行驗證，圖3為算法的收斂性對比圖，通過對比可以發(fā)現(xiàn)，在引入破壞修復(fù)操作后，遺傳算法的收斂速度與全局搜索能力得到明顯提升。

接著我們使用引入破壞修復(fù)操作的改進(jìn)遺傳算法對考慮緊迫度的油料配送路徑規(guī)劃模型進(jìn)行求解，得到3條最優(yōu)配送路徑，如圖4（b）所示，其中路線1：0→6→7→8→5→3→1→4→2→0，路線2：0→12→14→17→16→15→13→11→9→10→0， 路線3：0→20→19→18→21→23→25→24→22→0，車輛的總行駛距離為299.58千米，距離成本為8987.4元，用車固定成本為900元，卸油成本9950元，總費用為19837.4元。

為驗證模型的有效性，繼續(xù)求解不考慮緊迫度的油料配送路徑規(guī)劃模型，以進(jìn)行對比，如圖4（a）所示，所得的路線1：0→2→6→7→8→4→5→3→1→0，路線2：0→10→11→9→13→15→16→17→14→12→0，路線3：0→20→19→18→21→23→25→24→22→0，車輛的總行駛距離為294.99千米，距離成本為8849.7元，時間窗懲罰成本為30.15元，用車固定成本為900元，卸油成本9950元，總費用為19729.85元，此時若將違背緊急配送請求的時間窗約束所造成的追加懲罰成本考慮到其中，則該路線還將產(chǎn)生1950元的追加懲罰成本。

通過對比可以發(fā)現(xiàn)，考慮需求緊迫度后，所得到的路線1將對緊迫度較高的6號、7號、8號加油站進(jìn)行優(yōu)先配送，所得到的路線2將對緊迫度較高的12號、14號加油站進(jìn)行優(yōu)先配送，從而可以在一定程度上避免由于緊急配送請求超時配送而可能帶來的追加懲罰成本。若不考慮需求緊迫度，則在所得到的路線1中，6號、7號、8號加油站相對靠后，而在路線2中，12號、14號加油站則將在最后才能得到配送。路線3由于不存在緊迫度較高的加油站，因此考慮與不考慮緊迫度所得到的配送路線相同（見表3）。

因此，考慮需求緊迫度后所得到的路徑規(guī)劃方案雖然在車輛的總行駛里程和運輸成本上，相較不考慮緊迫度的路徑規(guī)劃方案有所增加，但可以實現(xiàn)對緊迫度較高的加油站進(jìn)行優(yōu)先配送，以盡可能避免緊迫度較高的加油站因油料短缺而可能造成的潛在損失，驗證了模型的有效性。

4總結(jié)與展望

本文針對成品油配送中出現(xiàn)不同程度的緊急配送請求時的路徑規(guī)劃問題，提出了一種考慮需求緊迫度的成品油配送路徑規(guī)劃模型，通過對違反時間窗約束的配送請求，根據(jù)需求緊迫度的不同，施加相應(yīng)程度的追加懲罰，以實現(xiàn)對緊迫度較高的供油請求進(jìn)行優(yōu)先配送。同時，通過引入破壞修復(fù)操作的改進(jìn)遺傳算法對模型進(jìn)行了實驗仿真，驗證了模型和算法的有效性。然而，本文的研究還存在一些需要探討和改進(jìn)的方向，例如：可以考慮在配送中使用多油庫或不同規(guī)格的油罐車等情況，以便更貼合實際情況。此外，還可以探索更加高效的求解算法，以提高模型求解的效率。這些改進(jìn)可以使研究更加全面，更貼近實際，有助于提高模型的適用性和可行性。

參考文獻(xiàn)：

[1] SEAR T N.Logistics planning in the downstream oil industry[J].Journal of the Operational Research Society，1993，44（1）：9-17.

[2] 楊渝華，李敏.基于改進(jìn)遺傳算法的成品油配送車輛調(diào)度問題研究[J].物流科技，2015，38（1）：6.

[3]王博弘，梁永圖，張浩然，等.成品油二次配送路徑優(yōu)化模型及混合求解算法[J].油氣儲運，2019，38（11）：1251-1256

.[4]王旭坪，詹紅鑫，孫自來，等.多行程帶補(bǔ)貨時間窗的成品油多艙配送路徑優(yōu)化[J].管理工程學(xué)報，2020，34（4）：14.

[5]金驍.成品油配送路徑優(yōu)化問題研究[J].中國市場，2017（18）：4.

[6]羅思好.考慮油品損耗的成品油二次物流配送路徑優(yōu)化研究[D].重慶：重慶交通大學(xué)，2019.

[7]李珍萍，楊光，韓倩倩.考慮工作量均衡的成品油二次配送車輛路徑問題[J].系統(tǒng)仿真學(xué)報，2022，34（2）：221-233.

[8]詹紅鑫.成品油多艙位配送路徑優(yōu)化問題研究[D].大連：大連理工大學(xué)，2018.

[9] HOLLAND J H.Adaption in natural and artificial system：An introductory analysis with applicaions to biology，controlandartificial intelligence[M].Cambridge：The MIT Press，1992.

[10]HOMBERGER J，GEHRING H.Two evolutionary metaheuristics for the vehicle routing problem with time windows[J].INFOR：Information Systems and Operational Research，1999，37（3）：297-318.

[11]唐傳茵，劉春龍.基于遺傳算法和破壞重組算法的外賣配送研究[J].物流科技，2022，45（2）：6.

[12]SOLOMON M M.Algorithms for the vehicle routing and scheduling problems with time window constraints[J].Operations Research，1987，35（2）：254-265.

[13]王瑜.成品油二次配送庫存-路徑問題研究[J].化工管理，2019（9）：1-4.

[14]李珍萍，焦鵬博，姜崇宇.考慮多車型軟時間窗的成品油二次配送庫存-路徑問題[J].科學(xué)技術(shù)與工程，2022，22（18）：8043-8049.