基于混合遺傳算法的成品油二次配送優化

孫厚舉

（江蘇建筑職業技術學院信電工程學院，徐州 221000）

0 引言

多周期庫存路徑問題［1］（inventory routing problem with multi period，IRP?MP）屬于非確定性多項式（non?deterministic polynomial，NP）困難問題［2］的一種，是通過供應商管理庫存策略（vendor managed inventory,VMI）［3］，在無限長的時間內周期性地進行一對多補貨配送方案的規劃和執行。成品油公路運輸問題是典型的多周期庫存路徑問題，石油公司負責對各加油站油品庫存的監控，統籌制定油品配送方案，確保配送高效且可靠。通常情況下，石油公司將制定總運距盡可能短的運送計劃，以實現高質量的物流運輸目標。

學術界對成品油公路運輸的研究經歷了從精確算法到智能化算法的過程。田立新等［4］采用0-1 規劃模型解決單周期成品油運輸問題。宋杰鯤等［5］采用最短路徑和最小費用模型制定成品油運輸模型。張立峰等［6］提出了兩階段路徑規劃模型，首先使用聚類算法將配送需求合并分載，然后改進遺傳算法計算最終配送路線。李珍萍等［7］考慮了多種約束條件，提出了一種混合整數規劃模型，繼而使用遺傳算法模型規劃運送路線。張雄等［8］使用改進蟻群算法求解了帶時間窗口的車輛路徑問題。Xu 等［9］提出了多目標粒子群優化算法制定配送方案。文獻［10?11］研究了啟發式算法求解多周期庫存路徑問題，文獻［12］介紹了運輸成本問題，本文在設計混合遺傳算法的評估函數時參考了其中的部分因素。

1 成品油公路運輸問題描述

成品油公路運輸研究的是成品油運輸二次配送階段問題［13］。一次配送階段主要是從煉油廠將成品油運送至各地級市的油庫，一個省往往只有一個煉油廠，一個地級市只有一個油庫且運送方式多為管道運輸，幾乎不需要復雜的規劃模型。二次配送［14］是從油庫將成品油運送至加油站，目前石油公司統一采用主動配送方式，即石油公司根據液位儀系統時時監控所有加油站多種油品的存量，根據各加油站油品的消耗情況生成配送需求，然后使用算法規劃配送時間和配送量。成品油公路運輸多周期規劃問題中，通常每12 小時為一個周期，將全天運輸計劃分為早班和晚班，少數地區可能存在24小時為一個周期的情況。

問題模型與假設條件如下：

（1）允許油罐車跨地級市選取就近油庫進行提油，各油庫油品存量充足，不存在油品不足的情況。

（2）油庫可設定當前可用油品，并可設定營業時段。

（3）每個地級市擁有大量加油站，且每個加油站都安裝了液位儀，擁有近三年液位儀數據。

（4）油罐車分為汽油車和柴油車，汽油和柴油不可混裝在一輛車上，不同的汽油油品不可以混裝，但可以同時裝在同一輛油罐車的不同隔倉里。

（5）油罐車可以分載，一輛油罐車可以一次給多個加油站配送油品。

（6）擁有油庫到各加油站的距離，加油站與加油站之間的距離。如果運距不存在，則用9999公里代替。

（7）油罐車下班后停車點為油庫。

（8）擁有各種約束數據，例如加油站限制拖車，限制掛車，限制配送時段等數據。

2 建立數學模型

數學符號定義如下：

P={p0,p1,…,pn}：整個規劃時間段，其中元素p0和p1代表第一個規劃周期的開始和結束時間，p2和p3代表第二個規劃周期的開始和結束時間，以此類推。

Q={q1,q2,…,qn}：一輛油罐車的隔倉容量，其中n表示隔倉數量，qn表示第n個隔倉的容量。

K={Q1,Q2,…,Qn}：油罐車輛，其中Qn表示第n輛油罐車的隔倉容量集合。

G={g1,g2,…,gn}：油品列表，其中gn表示第n種油品的油品編號。

V={v1,v2,…,vn}：油品體積，其中vn表示第n種油品的體積。

D={(G1,V1),(G2,V2),…,(Gn,Vn) }：所有油庫信息，其中(Gn,Vn)表示第n個油庫的油品種類以及可用體積。

S={s1,s2,…,sn}：所有加油站。

D={(G1,V1),(G2,V2),…,(Gn,Vn) }：所有加油站的各種油品的當前體積。

SV={{S1,V1},{S2,V2},…,{Sn,Vm}}：各加油站實際配送量。

VM={v1,v2,…,vn}：加油站油品的最大容納體積，其中vn表示第n種油品的最大可容納體積。

SM={(G1,VM1),(G2,VM2),…,(Gn,VMn) }：所有加油站每種油品的最大可容納體積。

T={t1,t2,…,tn}：加油站油品的預計斷貨時間。

O={(G1,T1),(G2,T2),…,(Gn,Tn)} ：所有加油站的所有油品的預計斷貨時間。

DS={ds1,1,ds1,2,…,dsi,j,…,dsn-1,n}：各運輸節點間的距離，其中dsi,j表示節點i到節點j之間的距離，其中節點i和節點j可以是油庫也可以是加油站或者停車場。

R={r1,r2,…,rn}：各加油站預計需求量。

v：車輛行駛速度。

SLi：油罐車在油庫提油時間。

STi：加油站卸油時間。

c：斷貨時長懲罰。

p：不容納體積懲罰。

根據以上描述，成品油公路運輸多周期規劃目標定義如下：

式（1）表示規劃方案的總運輸成本；式（2）表示規劃方案的總斷貨懲罰；式（3）表示規劃方案的總不容納懲罰；式（4）表示該問題的總目標是實現所有周期中每輛油罐車的總運輸成本、斷貨懲罰和不容納懲罰最小。

在實際運輸方案中存在如下約束：

式（5）表示限制每個加油站節點的入度和出度都必須為1；式（6）表示限制油罐車的每個隔倉滿載率必須大于90%。此外還需要滿足部分其他約束條件，比如加油站可容納約束，因為油罐車的每一個隔倉在運輸途中滿載率要么為0，要么必須大于90%，所以隔倉卸油時必須一次卸完，不允許出現加油站油罐已滿而隔倉未卸完的情況。部分城市對油罐車有交通管制，要求凌晨0點到6點通行，其他時段不允許通行。

3 混合遺傳算法模型

3.1 算法編碼方案

本文提出一種混合遺傳算法（RMH），算法采用一位編碼方式表示配送方案，但因為配送方案較為復雜，所以在編碼時將每輛油罐車的配送路線進行了封裝，所有油罐車的配送路線組合在一起就形成了完整的配送方案。其中，每輛油罐車的配送路線都再次被細化為三部分，即時間節點、配送路線和裝載方案。時間節點包括油罐車到達油庫時間、等待油庫營業時長、裝油時長、到達加油站時間、卸油等待時長、卸油時間，如果存在分載情況，則提供到達下一加油站時間以及卸油等待時長和卸油時間，最后加上到達下一次提油油庫時間。配送路線包括油庫和加油站。裝載方案包括每個隔倉裝載的油品種類和裝載量。如圖1所示，該編碼表示某油罐車一次配送路線的編碼。

圖1 油罐車一次配送路線編碼

編碼中將時間節點、配送路線、裝載方案、油罐車配送方案分別封裝為類，則通過這些類的對象即可表示多周期配送路線方案。

3.2 算法過程

求解成品油公路運輸多周期規劃問題的算法流程如下。

3.3 構造初始解

首先利用松弛下界模型將部分約束條件放開，快速構造符合松弛模型的解，然后利用子回路消除方法［15］將配送方案中的子回路消除，再使用精確計算方法找到較為優秀的解放入初始解集合。假設某配送規劃問題中只包含1個油庫D，和16個加油站，記為{s1,s2,…,s16}，在松弛下界模型下構造的解可能并不是一條連續路徑，而是多條子路徑，其中多條子路徑并不經過油庫D。每條路徑用R{si,sj,…,sn}表示，經過子回路消除操作之后，得到一條經過所有節點的回路，這條回路是開銷最小的。如表1所示。

表1 子回路消除過程

其中，s2、s7、s11三個節點在構造時就沒有包括在子回路中，子回路消除是通過依次計算子回路之間的距離將子回路串聯在一起，形成一條回路，所以消除子回路后依然包含s2、s7、s11三個節點。通過松弛下界模型構造的規劃路徑R1至R5，只有R1是包含了油庫的，其他規劃路徑都沒有取油油庫，經過子回路消除之后合并成為一條規劃路徑，然而一輛油罐車的油罐數量一般為4～5 個，也就是說，一輛油罐車到油庫提一次油，最多只能配送5個加油站，如果子回路中加油站數量小于等于三個，則設定一個油庫即可。所以調整后的子回路消除算法的消除過程如表2所示。

表2 改進后子回路消除過程

目標函數［16］是啟發式算法中最為關鍵的設計，對于已經構造好的規劃方案，通過目標函數進行評估，淘汰較差的解，保留優秀的解，同時配合模擬退火策略，按照一定的比例保留不夠優秀的解，加強算法的全局搜索能力。

3.4 迭代搜索

合法的初始解生成之后，通過啟發式算法的迭代進行局部搜索［17］，在解空間中不停地探索更優秀的解，然后用更優秀的解替換解集中較差的解，然而迭代搜索需要既保持當前解的優點，又要實現解的優化，這在實際問題中很難實現，也是設計迭代搜索的目的。首先我們認為整個問題的解空間在多維坐標系中是連續的，因此迭代時需要在解的鄰域做搜索，所以鄰域操作［18］是啟發式算法迭代的核心操作。

本文提供了兩種測量用于調整配送方案的領域操作。第一種鄰域操作為簡單的刪除或者添加更為經濟的新節點，或者刪除某個節點；第二種是在不同配送路徑中交換節點。第一種操作方式較為簡單，可以根據目標函數直接評估，決定新增節點和刪除節點。第二種操作方式不需要考慮某個節點被多次配送或者未被配送。第二種鄰域操作方式的調整過程如表3所示。

表3 交換子路徑節點操作過程

為防止一次鄰域操作導致解在解空間中偏移過多，建議一次鄰域操作只交換1～2次節點。

4 實驗結果及分析

為了驗證算法的有效性，本研究對3 個周期、5～50 個客戶的小規模算例和6 個周期5～30 個客戶的中規模算例，以及6 個周期，客戶數分別為50、100、200的大規模算例進行測試。本節將對分支切割算法（branch?and?cut，BC）算法［19］、核啟發式算法（kernel search heuristic，KSH）算法［20］和本文提出的RMH算法進行對比。

在小、中規模算例中，本文提出的RMH 算法在多數算例上取得了理論最優解。與BC 算法和KSH算法的對比結果如圖2所示。

圖2 小、中規模算例的對比結果

圖2給出的是小、中規模算例計算結果的平均值。其中BC 算法為精確算法，在同樣取得較優解的情況下，所用時間最短。從圖2 不難看出，對于3周期的算例來說，三種算法得到的最優解的平均值幾乎沒有太大區別。中等規模算例下，KSH 算法和RMH 算法的平均值較BC 算法稍微有一些優勢，但總體差別不大，但計算用時明顯比BC算法要高。

對于大規模算例，周期達到6個，客戶節點最多達到200 個。隨著客戶節點數量的增加，BC 算法的劣勢越發明顯。大規模算例的對比結果如圖3所示。

圖3 大規模算例的對比結果

從大規模算例的求解結果可以看出，該研究提出的RMH 算法和KSH 算法的平均結果明顯比BC 算法更優秀，而且客戶節點數量越多，差距越明顯，證明了精確算法在求解大規模庫存路徑問題上存在缺陷。而RMH 算法相比于KSH算法依舊有明顯優勢，總運送成本平均降低12.3%，而且平均計算時間也相對更短，通過實驗對比，從求解質量和時間代價兩個方面體現了RMH算法的性能和效率。

5 結語

針對成品油公路運輸多周期規劃問題，該研究提出一種混合遺傳算法模型RMH，該模型可在多數小、中規模算例中求解到理論最優解。相較于BC 算法和KSH 算法，RMH 算法在大規模算例集獲取的規劃方案中優勢明顯。當然，該方案也存在一些不足。實際操作中，若后續需人工調整5%左右的規劃路線，則會影響其它路線正常運輸，牽一發而動全身，最終導致規劃方案無法正常使用。因此，如何獲得100%可用的規劃方案是后續的重要研究工作。