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

孫厚舉

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

0 引言

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

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

1 成品油公路運(yùn)輸問(wèn)題描述

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

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

（1）允許油罐車(chē)跨地級(jí)市選取就近油庫(kù)進(jìn)行提油，各油庫(kù)油品存量充足，不存在油品不足的情況。

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

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

（4）油罐車(chē)分為汽油車(chē)和柴油車(chē)，汽油和柴油不可混裝在一輛車(chē)上，不同的汽油油品不可以混裝，但可以同時(shí)裝在同一輛油罐車(chē)的不同隔倉(cāng)里。

（5）油罐車(chē)可以分載，一輛油罐車(chē)可以一次給多個(gè)加油站配送油品。

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

（7）油罐車(chē)下班后停車(chē)點(diǎn)為油庫(kù)。

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

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

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

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

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

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

G={g1,g2,…,gn}：油品列表，其中g(shù)n表示第n種油品的油品編號(hào)。

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

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

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

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

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

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

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

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

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

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

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

v：車(chē)輛行駛速度。

SLi：油罐車(chē)在油庫(kù)提油時(shí)間。

STi：加油站卸油時(shí)間。

c：斷貨時(shí)長(zhǎng)懲罰。

p：不容納體積懲罰。

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

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

在實(shí)際運(yùn)輸方案中存在如下約束：

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

3 混合遺傳算法模型

3.1 算法編碼方案

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

圖1 油罐車(chē)一次配送路線編碼

編碼中將時(shí)間節(jié)點(diǎn)、配送路線、裝載方案、油罐車(chē)配送方案分別封裝為類(lèi)，則通過(guò)這些類(lèi)的對(duì)象即可表示多周期配送路線方案。

3.2 算法過(guò)程

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

3.3 構(gòu)造初始解

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

表1 子回路消除過(guò)程

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

表2 改進(jìn)后子回路消除過(guò)程

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

3.4 迭代搜索

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

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

表3 交換子路徑節(jié)點(diǎn)操作過(guò)程

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

4 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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