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

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

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

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

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

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

1.1問題描述

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

1.2模型假設(shè)

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

1.3符號(hào)說明

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

1.4模型建立

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

約束條件，如下。

式（1）為目標(biāo)函數(shù)，包括油罐車的固定使用成本、可變運(yùn)輸成本、超時(shí)懲罰成本、卸油成本、以及對(duì)緊急配送請(qǐng)求超時(shí)配送時(shí)的追加懲罰成本；式（2）要求油罐車所能裝載的最大油量不能超過油罐車的載重量；式（3）要求每個(gè)加油站僅被一輛油罐車服務(wù)一次；式（4）要求所有從油庫出發(fā)的油罐車在完成配送后，最終將返回油庫；式（5）要求到達(dá)加油站與離開加油站的油罐車是同一輛；式（6）表示油罐車到達(dá)加油站j的時(shí)間與到達(dá)前一個(gè)加油站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)等特點(diǎn)，但也存在容易陷入局部最優(yōu)解的問題1。引入破壞修復(fù)操作的改進(jìn)遺傳算法，通過借鑒大規(guī)模鄰域搜索算法中的破壞和修復(fù)策略，從而使其局部搜索能力得到較大提升川，在求解復(fù)雜的組合優(yōu)化問題時(shí)，也能取得良好的效果?？紤]需求緊迫度的成品油配送問題是典型的多目標(biāo)組合優(yōu)化問題，因此，本文選用該算法進(jìn)行求解，步驟如下。

2.1染色體編碼

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

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

2.2初始化種群

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

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

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

2.4選擇操作

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

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

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

步驟3：計(jì)算種群中每個(gè)個(gè)體的累計(jì)概率， q=Zp。

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

2.5交叉操作

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

步驟1：隨機(jī)在父代個(gè)體中產(chǎn)生兩個(gè)交叉點(diǎn)，并定義兩點(diǎn)之間的區(qū)域?yàn)榻徊鎱^(qū)域。

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

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

2.6變異操作

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

步驟1：隨機(jī)在個(gè)體中產(chǎn)生兩個(gè)變異點(diǎn)，并定義兩點(diǎn)之間的區(qū)域?yàn)樽儺悈^(qū)域。

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

2.7破壞修復(fù)操作

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

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

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

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

3實(shí)驗(yàn)仿真

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

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

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

接著我們使用引入破壞修復(fù)操作的改進(jìn)遺傳算法對(duì)考慮緊迫度的油料配送路徑規(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元，總費(fèi)用為19837.4元。

為驗(yàn)證模型的有效性，繼續(xù)求解不考慮緊迫度的油料配送路徑規(guī)劃模型，以進(jìn)行對(duì)比，如圖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元，時(shí)間窗懲罰成本為30.15元，用車固定成本為900元，卸油成本9950元，總費(fèi)用為19729.85元，此時(shí)若將違背緊急配送請(qǐng)求的時(shí)間窗約束所造成的追加懲罰成本考慮到其中，則該路線還將產(chǎn)生1950元的追加懲罰成本。

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

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

4總結(jié)與展望

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

參考文獻(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].油氣儲(chǔ)運(yùn)，2019，38（11）：1251-1256

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

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

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

[7]李珍萍，楊光，韓倩倩.考慮工作量均衡的成品油二次配送車輛路徑問題[J].系統(tǒng)仿真學(xué)報(bào)，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]李珍萍，焦鵬博，姜崇宇.考慮多車型軟時(shí)間窗的成品油二次配送庫存-路徑問題[J].科學(xué)技術(shù)與工程，2022，22（18）：8043-8049.