基于混合遺傳算法的成品油二次配送優(yōu)化

孫厚舉

（江蘇建筑職業(yè)技術(shù)學(xué)院信電工程學(xué)院，徐州 221000）

0 引言

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

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

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

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

問題模型與假設(shè)條件如下：

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

（2）油庫可設(shè)定當(dāng)前可用油品，并可設(shè)定營業(yè)時段。

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

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

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

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

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

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

2 建立數(shù)學(xué)模型

數(shù)學(xué)符號定義如下：

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

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

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

G={g1,g2,…,gn}：油品列表，其中g(shù)n表示第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) }：所有加油站的各種油品的當(dāng)前體積。

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

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

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

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

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

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

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

v：車輛行駛速度。

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

STi：加油站卸油時間。

c：斷貨時長懲罰。

p：不容納體積懲罰。

根據(jù)以上描述，成品油公路運輸多周期規(guī)劃目標(biāo)定義如下：

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

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

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

3 混合遺傳算法模型

3.1 算法編碼方案

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

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

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

3.2 算法過程

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

3.3 構(gòu)造初始解

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

表1 子回路消除過程

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

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

目標(biāo)函數(shù)［16］是啟發(fā)式算法中最為關(guān)鍵的設(shè)計，對于已經(jīng)構(gòu)造好的規(guī)劃方案，通過目標(biāo)函數(shù)進行評估，淘汰較差的解，保留優(yōu)秀的解，同時配合模擬退火策略，按照一定的比例保留不夠優(yōu)秀的解，加強算法的全局搜索能力。

3.4 迭代搜索

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

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

表3 交換子路徑節(jié)點操作過程

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

4 實驗結(jié)果及分析

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

在小、中規(guī)模算例中，本文提出的RMH 算法在多數(shù)算例上取得了理論最優(yōu)解。與BC 算法和KSH算法的對比結(jié)果如圖2所示。

圖2 小、中規(guī)模算例的對比結(jié)果

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

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

圖3 大規(guī)模算例的對比結(jié)果

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

5 結(jié)語

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