考慮多車型軟時(shí)間窗的成品油二次配送庫存-路徑問題

李珍萍， 焦鵬博， 姜崇宇

(北京物資學(xué)院信息學(xué)院， 北京 101149)

石油石化產(chǎn)業(yè)在國民經(jīng)濟(jì)、軍事、社會安全和穩(wěn)定方面發(fā)揮著無可替代的作用。作為成品油供應(yīng)鏈的末端環(huán)節(jié)，僅成品油二次配送產(chǎn)生的運(yùn)輸成本就占據(jù)成品油供應(yīng)鏈總成本的60%～70%[1]。由于加油站的油罐容量有限，而需求量具有隨機(jī)性，如何控制各個(gè)加油站的庫存，避免缺貨，是石油石化企業(yè)制定配送方案時(shí)首先要考慮的關(guān)鍵問題；另外，由于成品油屬于液體危險(xiǎn)品，在配送過程中還需要考慮隔艙運(yùn)輸、是否允許分卸等條件，因此成品油二次問題屬于帶多種約束條件的庫存-路徑問題(inventory routing problem， IRP)，結(jié)合實(shí)際場景研究成品油二次配送庫存-路徑問題可以為石油石化企業(yè)制定成品油二次配送計(jì)劃，降低配送成本提供決策參考，具有重要的現(xiàn)實(shí)意義。

中外學(xué)者從不同角度對成品油二次配送問題開展廣泛深入的研究。王博弘等[2]對成品油二次配送的兩種主要模式(被動配送和主動配送模式)進(jìn)行了研究。大部分學(xué)者針對被動配送模式下(即加油站需求量已知情況下)的成品油二次配送車輛路徑問題開展了研究。Carotenuto等[3]研究了涉及單一產(chǎn)品單車型的成品油二次配送問題。張?jiān)磩P等[4]針對多產(chǎn)品多車型多隔艙的成品油二次配送問題，提出了可求解大規(guī)模算例的啟發(fā)式算法。Wang等[1]分別考慮了單車型和多車型條件下，需求可拆分的成品油二次配送問題。王旭坪等[5]和李珍萍等[6]研究了帶有硬時(shí)間窗約束的成品油二次配送問題，利用啟發(fā)式算法對模型進(jìn)行求解。Cornillier等[7]將成品油二次配送問題擴(kuò)展至多周期，并設(shè)計(jì)了多階段啟發(fā)式算法。在考慮時(shí)間窗的基礎(chǔ)上，Cornillier等[8]進(jìn)一步研究了具有多油庫的成品油二次配送問題。

上述針對被動配送模式下的成品油二次配送問題研究均假設(shè)加油站的需求量和時(shí)間窗已知，將問題簡化為帶約束的車輛路徑問題。實(shí)際中很多石油石化企業(yè)采取由供應(yīng)商管理庫存(vendor managed inventory， VMI)的主動配送模式，在主動配送模式下各個(gè)加油站的補(bǔ)貨量需要由供應(yīng)商確定，此時(shí)問題歸結(jié)為庫存-路徑問題(IRP)。IRP問題在實(shí)際中有著廣泛的應(yīng)用，如危化品配送[9]、物流配送[10]、可持續(xù)發(fā)展配送[11]等。針對成品油二次配送場景下的IRP問題，Li等[12]對于成品油二次配送中帶時(shí)間窗的單車型單一產(chǎn)品IRP問題，設(shè)計(jì)了一種基于禁忌搜索的啟發(fā)式算法。在單車型單一產(chǎn)品的基礎(chǔ)上，Wang等[13]進(jìn)一步研究了帶時(shí)間窗約束的成品油二次配送IRP問題，并考慮了碳稅政策對總成本的影響。Li等[14]研究了直接配送模式下單車型單一產(chǎn)品考慮隨機(jī)需求的成品油二次配送IRP問題，并使用CPLEX求解器求解模型。Wu等[15]研究了考慮時(shí)間窗和燃料消耗率的IRP問題，利用兩階段混合啟發(fā)式算法確定最優(yōu)的庫存和路徑?jīng)Q策方案。

雖然有關(guān)IRP的研究成果十分豐富，但現(xiàn)有研究均對問題進(jìn)行了不同程度的簡化，如嚴(yán)格限制單車型單隔艙、單一產(chǎn)品等約束，忽視需求隨機(jī)性、車型隔艙種類、油罐車裝載運(yùn)輸約束等對總成本的影響。而在實(shí)際配送過程中，補(bǔ)貨量及配送時(shí)間窗確定、車型種類、隔艙數(shù)量等條件往往無法忽視。如為避免缺貨現(xiàn)象以及錯峰配送，需要確定合理的補(bǔ)貨量和配送活動的時(shí)間窗；為保障成品油在途運(yùn)輸?shù)陌踩裕囕v裝載油品時(shí)需要盡可能滿載；為保持油品運(yùn)輸?shù)慕?jīng)濟(jì)性，需要配備多種帶有隔艙的車型等。

在已有研究的基礎(chǔ)上，現(xiàn)針對隨機(jī)需求、多車型多隔艙、油品可分卸配送、帶軟時(shí)間窗的成品油二次配送庫存-路徑問題開展研究。以車輛配送成本、等待成本以及非滿載的懲罰成本之和最小為目標(biāo)，建立混合整數(shù)規(guī)劃模型。根據(jù)模型特點(diǎn)將求解過程分解為庫存控制(確定補(bǔ)貨量及時(shí)間窗)和路徑優(yōu)化兩個(gè)階段，首先利用加油站需求量的概率分布信息確定安全庫存、補(bǔ)貨量和軟時(shí)間窗，并且為每個(gè)加油站選擇一種車型；然后采用遺傳算法求解各車型單艙車的可行配送路徑，最后利用C-W節(jié)約算法對單艙車可行路徑中的節(jié)點(diǎn)進(jìn)行合并，得到多艙車對應(yīng)的近似最優(yōu)配送路徑。

1 問題描述和模型建立

1.1 問題描述與分析

考慮一個(gè)VMI模式下的成品油二次配送網(wǎng)絡(luò)，某地區(qū)有一個(gè)油庫為n個(gè)加油站提供單一類型成品油。油庫擁有R種帶有隔艙的油罐車，每種類型車輛擁有一個(gè)或多個(gè)相同容量的隔艙，每輛油罐車同一隔艙中的油品允許分卸到多個(gè)加油站。已知油庫與加油站、加油站與加油站之間的最短距離，各加油站的最大庫存容量、期初庫存和銷售量服從的概率分布，各種車型的單位距離成本、最大載重量、車輛維護(hù)費(fèi)用及固定費(fèi)用。所有車輛均需從油庫出發(fā)，完成配送任務(wù)后重新返回油庫。問如何制定配送方案，才能滿足各個(gè)加油站的需求，并且使總配送成本最小。

在制定成品油二次配送方案時(shí)，需要確定為每個(gè)加油站配送的油品數(shù)量(補(bǔ)貨量)、完成配送任務(wù)需要的最少車輛數(shù)及每輛車的配送路徑、配送量、等待時(shí)間等，使總成本最小。總成本包括：車輛的固定成本、行駛成本、等待成本以及非滿載的懲罰成本。等待成本與車輛提前到達(dá)加油站時(shí)的等待時(shí)間有關(guān)；懲罰成本與車輛非滿載運(yùn)輸造成的空余容量有關(guān)。

為便于問題求解，做出如下假設(shè)：①油庫的庫存充足，能夠滿足所有加油站需求；②各個(gè)加油站在一天中不同時(shí)段的銷售速率穩(wěn)定；③一個(gè)加油站在同一時(shí)間只能接受一輛油罐車的服務(wù)；④在給定的服務(wù)水平下，各個(gè)加油站不允許缺貨；⑤加油站每天的銷售量不超過罐容量。

1.2 混合整數(shù)規(guī)劃模型

考慮多車型多隔艙軟時(shí)間窗的成品油二次配送庫存-路徑問題可表示為如下混合整數(shù)規(guī)劃模型，其中目標(biāo)函數(shù)可表示為

(1)

式(1)中：N={0，1，2，…，n，n+1}為配送網(wǎng)絡(luò)節(jié)點(diǎn)集合，其中0、n+1為油庫，其余節(jié)點(diǎn)為加油站；R={1，2，…，l}為車輛類型集合；Kr={1，2，…，mr}為每種類型車輛的集合；e為車輛的單位距離行駛成本；cij為節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短距離；xijkr為0-1變量，若車型為r的車輛k經(jīng)過弧(i，j)為1，否則為0；OC為車輛的固定派遣費(fèi)用；ykr為0-1變量，使用車型為r的車輛k為1，否則為0；WC為車輛的單位時(shí)間等待成本；wikr為車型為r的車輛k到達(dá)加油站i時(shí)的等待時(shí)間；PC為車輛非滿載的單位懲罰成本；hkr為車型為r的車輛k的非滿載容量。式(1)表示極小化總配送成本，包括車輛行駛成本、車輛固定成本、早于時(shí)間窗到達(dá)的等待成本和非滿載時(shí)的懲罰成本。

流量平衡約束：

(2)

(3)

(4)

式(2)和式(3)表示每條路徑的起點(diǎn)和終點(diǎn)均為油庫；式(4)表示若一輛車服務(wù)加油站，則要從該加油站離開。

車容量和加油站需求量約束：

(5)

(6)

(7)

式(5)中：qikr為車型為r的車輛k為加油站i配送的油品數(shù)量；Qkr為車型為r的車輛k擁有的最大載重量；T為加油站每天的工作時(shí)間；ui為加油站i的單位時(shí)間銷售率；Ii為加油站i的期初庫存；Si為加油站i的有效庫存容量；ETi為加油站i的最早服務(wù)時(shí)間。

式(5)表示車輛容量約束；式(6)表示只有車輛經(jīng)過加油站才能為其提供服務(wù)；式(7)表示加油站可接受的配送量范圍。

時(shí)間窗約束：

sikr+vi+tij-sjkr≤M(1-xijkr)，

?i，j∈N，i≠j，k∈Kr，r∈R

(8)

?i∈N，i≠j，k∈Kr，r∈R

(9)

?i∈N，k∈Kr，r∈R

(10)

式(8)中：sikr為車型為r的車輛k到達(dá)加油站i的時(shí)間；M為足夠大的正數(shù)；vi為車輛在加油站i的服務(wù)時(shí)間；tij為車輛從節(jié)點(diǎn)i到節(jié)點(diǎn)j的行駛時(shí)間；LTi為加油站i的最晚服務(wù)時(shí)間；bikr為車型為r的車輛k到達(dá)加油站i時(shí)晚于ETi的時(shí)間。

式(8)表示車輛到達(dá)兩個(gè)相鄰加油站之間的時(shí)間關(guān)系；式(9)和式(10)表示不允許車輛晚于最晚時(shí)間到達(dá)加油站，但允許提前到達(dá)。

車輛與路徑之間的關(guān)系約束：

(11)

(12)

(13)

式(11)表示只有動用的車輛才能從一個(gè)加油站到達(dá)其他節(jié)點(diǎn)；式(12)表示一個(gè)加油站至少被服務(wù)一次；式(13)表示對一個(gè)加油站同一輛車最多提供一次服務(wù)。

決策變量取值約束：

xijkr∈{0，1}， ?i，j∈N，i≠j，k∈Kr，r∈R

(14)

ykr∈{0，1}， ?i∈N，k∈Kr，r∈R

(15)

sikr≥0， ?i∈N，k∈Kr，r∈R

(16)

qikr≥0， ?i∈N，k∈Kr，r∈R

(17)

wikr≥0， ?i∈N，k∈Kr，r∈R

(18)

bikr≥0， ?i∈N，k∈Kr，r∈R

(19)

hkr≥0， ?k∈Kr，r∈R

(20)

式(14)～式(20)為決策變量取值約束。

2 算法設(shè)計(jì)

由于庫存-路徑問題屬于NP-hard問題，對于大規(guī)模成品油二次配送問題，采用多階段分解策略求解，既可以降低問題復(fù)雜度，又可以設(shè)計(jì)啟發(fā)式算法在滿足精度要求的同時(shí)兼顧問題求解的速度。因此，將結(jié)合模型特征，將問題分解為庫存控制和路徑優(yōu)化兩個(gè)階段，首先根據(jù)加油站銷售量的概率分布信息和給定的服務(wù)水平確定各加油站的補(bǔ)貨量，為每個(gè)加油站選擇合適的車型，然后利用車型分組結(jié)合遺傳算法和C-W節(jié)約算法對路徑進(jìn)行優(yōu)化。

2.1 庫存控制

2.1.1 確定各加油站最晚配送時(shí)間窗

根據(jù)各個(gè)加油站的歷史銷售數(shù)據(jù)，確定計(jì)劃期內(nèi)每天加油站銷售量服從的概率分布(銷售量均值di和標(biāo)準(zhǔn)差σi)，在給定的服務(wù)水平下，確定各加油站的安全庫存水平SIi。假設(shè)加油站每天各個(gè)時(shí)段的銷售速率穩(wěn)定，根據(jù)每天的銷售量均值di和加油站每天的工作時(shí)間T，計(jì)算單位時(shí)間的銷售速率ui=di/T。為保證配送車輛到達(dá)時(shí)，加油站的實(shí)際庫存水平不低于安全庫存，按照式(21)可確定車輛到達(dá)加油站的最晚時(shí)間LTi：

(21)

2.1.2 確定各加油站補(bǔ)貨量和最早配送時(shí)間窗

每個(gè)加油站的配送時(shí)間點(diǎn)根據(jù)最晚配送時(shí)間和加油站的平均工作時(shí)間T/2確定，如式(22)所示：

(22)

進(jìn)一步根據(jù)加油站的有效庫存容量、期初庫存量和配送時(shí)間點(diǎn)T′，按照式(23)確定補(bǔ)貨量：

(23)

根據(jù)式(23)可知，當(dāng)加油站的期初庫存量大于平均需求量和安全庫存量之和時(shí)，不需要安排補(bǔ)貨，否則安排補(bǔ)貨，按照使加油站在配送時(shí)間點(diǎn)的庫存量恢復(fù)到有效庫存容量為標(biāo)準(zhǔn)，確定實(shí)際補(bǔ)貨量。

為保證配送車輛到達(dá)時(shí)加油站有足夠空余容量裝載配送量，按照式(24)可確定每個(gè)加油站接受服務(wù)的最早時(shí)間ETi：

(24)

2.1.3 確定各加油站最佳服務(wù)車型

在多車型成品油配送問題中，由于不同車型隔艙容量和總裝載量不同，對應(yīng)的配送成本也不同，因此制定配送計(jì)劃應(yīng)該盡可能提高車輛利用率，減少車輛的使用數(shù)和空載率。在允許分卸的情況下，車容量越大，可以服務(wù)加油站越多，平均使用成本越低。因此優(yōu)先使用大容量車型可以有效減少配送成本。

另一方面，由于不同加油站的補(bǔ)貨量不同，對于補(bǔ)貨量較少的加油站，如果使用大容量車型進(jìn)行配送，車輛空載率較高。因此應(yīng)該將加油站的補(bǔ)貨量與車型進(jìn)行匹配，盡可能提高車輛的滿載率。

根據(jù)各個(gè)加油站的補(bǔ)貨量和各種車輛的隔艙容量，為每個(gè)加油站匹配一種合適的隔艙容量和車型。對于某個(gè)加油站，根據(jù)其補(bǔ)貨量，分別計(jì)算使用各種隔艙對應(yīng)的滿載率。選擇滿載率最大的隔艙對應(yīng)的車型作為該加油站的實(shí)際使用車型。然后，根據(jù)各加油站的匹配車型，將加油站進(jìn)行分組，同一組加油站使用相同的車型。這樣，同一組加油站的成品油配送問題簡化為單一車型VRP問題。

2.2 路徑優(yōu)化

2.2.1 遺傳算法

加油站的補(bǔ)貨量和匹配車型隔艙確定之后，多車型IRP問題轉(zhuǎn)化為多個(gè)單車型VRP問題。對服務(wù)加油站的同一種車型，首先假設(shè)每輛車只有一個(gè)隔艙，根據(jù)隔艙容量確定需要使用的單艙車數(shù)量及配送路徑。按照下列規(guī)則設(shè)計(jì)遺傳算法求解。

(1) 編碼。采用自然數(shù)編碼表示染色體結(jié)構(gòu)，0表示油庫，1，2，…，n表示加油站。為方便運(yùn)算，去掉每條路徑中的起點(diǎn)和終點(diǎn)0，將所有路徑合并在一起形成一條染色體。

(2) 解碼。對于編碼[4 5 7 3 6 1 9 2 8]，首先安排車輛從油庫出發(fā)前往加油站4，考慮時(shí)間窗、車輛剩余油品量、加油站5的補(bǔ)貨量等約束決定是否服務(wù)加油站5，如果滿足約束，則繼續(xù)服務(wù)加油站5，即[0-4-5]，否則回到油庫，即[0-4-0]，之后重新安排車輛服務(wù)加油站5，然后判斷約束決定是否服務(wù)后續(xù)加油站。循環(huán)上述過程，直到遍歷完所有染色體編碼為止，此時(shí)恰好將染色體序列拆分為若干個(gè)滿足約束的配送回路，得到一個(gè)可行解。

(3) 種群初始化。通過隨機(jī)生成M個(gè)含有1～9序列，形成初始種群。

(4)適應(yīng)度計(jì)算。對于種群中的每個(gè)個(gè)體si(i=1，2，…，M)，首先通過解碼得到一組可行路徑，計(jì)算其對應(yīng)的總配送成本Ci。找出所有個(gè)體對應(yīng)的總成本最大值Cmax，按照式(25)計(jì)算每個(gè)個(gè)體的適應(yīng)度f(si)：

f(si)=2Cmax-Ci

(25)

(5) 選擇。采用輪盤賭法選擇個(gè)體，質(zhì)量較優(yōu)的個(gè)體優(yōu)先進(jìn)入下一代。

(6) 交叉。采用部分匹配交叉法。

(7) 變異。采用逆轉(zhuǎn)變異方法，在選定個(gè)體中隨機(jī)產(chǎn)生兩個(gè)逆轉(zhuǎn)點(diǎn)，把兩個(gè)逆轉(zhuǎn)點(diǎn)的基因?qū)φ{(diào)，得到新個(gè)體。

(8) 終止條件。達(dá)到最大迭代次數(shù)則終止迭代，否則轉(zhuǎn)規(guī)則(3)。

(9) 輸出結(jié)果。將種群中適應(yīng)度最優(yōu)個(gè)體作為最優(yōu)解輸出，得到最優(yōu)路徑。

2.2.2 C-W節(jié)約算法

根據(jù)遺傳算法求出服務(wù)所有加油站需要使用的各車型單艙車數(shù)量及配送路徑，該方案可以看成單艙車的可行配送方案。接下來根據(jù)C-W節(jié)約算法將單艙車配送方案合并，得到多艙車對應(yīng)的配送方案。

算法的基本步驟如下。

(1) 合并節(jié)點(diǎn)。先將遺傳算法得到每條單艙車配送路徑上的客戶點(diǎn)合并為一個(gè)節(jié)點(diǎn)，同時(shí)更新單艙車到達(dá)各個(gè)節(jié)點(diǎn)的時(shí)間，得到的新序列作為節(jié)約算法的初始解。節(jié)點(diǎn)合并過程如圖1所示。

圖1可表示為解碼后的序列，黃色節(jié)點(diǎn)代表油庫，橙色與藍(lán)色節(jié)點(diǎn)代表客戶。合并節(jié)點(diǎn)即將一條路徑內(nèi)的客戶點(diǎn)合并為一個(gè)節(jié)點(diǎn)，得到的序列可以看作是直接配送路徑的集合。

圖1 節(jié)點(diǎn)合并示意圖Fig.1 Nodes merging diagram

(2) 節(jié)約操作。應(yīng)用經(jīng)典C-W節(jié)約算法，將合并后的獨(dú)立節(jié)點(diǎn)進(jìn)行連接，計(jì)算連接后的里程節(jié)約值，按照里程節(jié)約值由大到小的順序，在滿足時(shí)間窗的條件下對路徑進(jìn)行合并操作，對初始解進(jìn)行優(yōu)化。如，路徑0-1-0和0-4-0(0為油庫)的里程分別是5、8 km，合并后總里程為10 km，合并后的路徑長度比兩條獨(dú)立路徑的總長度節(jié)約了3 km，此時(shí)可以將兩條路徑合并為0-1-4-0或0-4-1-0(由時(shí)間窗順序決定)。節(jié)約操作中路徑合并數(shù)量不超過車輛的隔艙數(shù)，合并后得到多艙車的配送路徑。

(3) 輸出結(jié)果。將節(jié)約算法得到的最優(yōu)路徑展開還原，如合并后序列為0-a-b-0，a包含2-4，b包含3-1，則展開還原后的路徑為0-(2-4)-(3-1)-0，該路徑即為雙艙車的實(shí)際配送路徑。

對每種車型執(zhí)行以上算法，得到最終配送計(jì)劃。

3 模擬計(jì)算與結(jié)果分析

3.1 算例描述

在VMI模式下，一個(gè)油庫為50個(gè)加油站配送單一品種成品油，使用的車輛類型有4種，油罐車的行駛速度相同均為30 km/h。給出一個(gè)油庫(編號為0)和前10個(gè)加油站(編號為1～10)，各個(gè)加油站的橫坐標(biāo)(X)、縱坐標(biāo)(Y)等信息如表1所示，車輛信息如表2所示，各項(xiàng)成本信息如表3所示，其中加油站及油庫的位置由平面直角坐標(biāo)系確定，各加油站最大庫存容量、期初庫存、服務(wù)時(shí)間，根據(jù)加油站前30日銷量服從的概率分布確定的銷量均值和給定90%服務(wù)水平確定的安全庫存已知，各加油站每天的工作時(shí)間為24 h。

3.2 算例求解與結(jié)果分析

根據(jù)上述算例數(shù)據(jù)，首先利用第一階段算法確定需要服務(wù)的加油站以及各加油站的補(bǔ)貨量和時(shí)間窗，然后利用第二階段算法優(yōu)化各車型對應(yīng)的路徑。設(shè)置種群規(guī)模為30，最大迭代次數(shù)為200次，得到按車型分組后的計(jì)算結(jié)果如表4所示。

結(jié)果顯示，50個(gè)加油站中，有30個(gè)加油站的庫存量可以滿足加油站的銷量，不需要安排補(bǔ)貨，其余20個(gè)加油站需要配送油品。配送計(jì)劃使用了4種車型共12輛車，其中車型2與車型3均使用雙艙車進(jìn)行配送，車型4則動用了3艙車與4艙車。對于大部分加油站來說，允許服務(wù)的最早時(shí)間與最晚時(shí)間之間的跨度較長，時(shí)間窗較為寬松，因此需要服務(wù)的加油站均可滿足時(shí)間窗要求，未出現(xiàn)等待現(xiàn)象。在50個(gè)節(jié)點(diǎn)的算例規(guī)模下，總配送成本為7 438.6 元，程序運(yùn)行10次的平均總用時(shí)為 1.717 s。

由于VMI模式下的成品油二次配送庫存-路徑問題屬于NP-hard問題，因此，將通過小規(guī)模算例分析兩階段啟發(fā)式算法的求解質(zhì)量與時(shí)間。根據(jù)表1～表3的加油站、車輛、各項(xiàng)成本信息，在各種信息保持不變的基礎(chǔ)上，隨機(jī)選取n個(gè)加油站(n=5，7，9，11)，生成4個(gè)小規(guī)模算例。利用商業(yè)求解器Gurobi直接求解針對每個(gè)算例的混合整數(shù)規(guī)劃模型得到精確解。然后利用兩階段啟發(fā)式算法對同一算例運(yùn)行10次得到近似最優(yōu)解，將求解器得到的精確解與算法運(yùn)算10次得到的平均近似最優(yōu)解進(jìn)行對比，其中第二階段算法參數(shù)設(shè)置不變。

表1 油庫及加油站信息Table 1 Information of the oil deport and petrol stations

表2 車輛信息Table 2 Information of the vehicles

表3 成本信息Table 3 Information of the cost

表4 配送方案Table 4 Results of the distribution

兩種方法得到的結(jié)果如表5所示。從表5可以觀察到，對于包含加油站個(gè)數(shù)最多的算例，兩階段啟發(fā)式算法的平均求解時(shí)間在1 s左右，而求解器的求解時(shí)間則隨加油站個(gè)數(shù)的增加呈指數(shù)級增長。對于包含5個(gè)加油站的最小規(guī)模算例，求解器求解出最優(yōu)解需要359.52 s，但隨著算例規(guī)模的增加，求解器的求解時(shí)間遠(yuǎn)遠(yuǎn)超過兩階段啟發(fā)式算法的平均時(shí)間，當(dāng)算例包含11個(gè)加油站時(shí)，求解器無法在可接受時(shí)間內(nèi)求出最優(yōu)解。在求解質(zhì)量方面，Gurobi求解器得到的最優(yōu)總成本比兩階段啟發(fā)式算法的結(jié)果更優(yōu)，但兩者結(jié)果的差值在包含不同加油站個(gè)數(shù)的算例中仍可接受且較為穩(wěn)定。并且當(dāng)加油站個(gè)數(shù)超過9個(gè)時(shí)，求解器無法在可接受時(shí)間內(nèi)得到最優(yōu)解，而兩階段啟發(fā)式算法則可以快速求出近似最優(yōu)解，因此當(dāng)問題規(guī)模逐漸增加時(shí)，兩階段啟發(fā)式算法的時(shí)間優(yōu)勢將更加明顯。

表5 小規(guī)模算例的求解結(jié)果Table 5 Results of small instances

為驗(yàn)證本文算法的有效性，設(shè)計(jì)求解該問題的單階段算法，在單階段算法中，油庫只能在已知初始庫存和庫存容量的前提下選擇合適車型，采用直接配送模式避免加油站出現(xiàn)缺貨現(xiàn)象。設(shè)置Gurobi求解時(shí)間為1 800 s，得到可接受時(shí)間內(nèi)的最佳可行解。針對表1的50個(gè)加油站，將本文兩階段算法(算法1)與單階段算法(算法2)、Gurobi最佳可行解算法(算法3)進(jìn)行比較，結(jié)果如表6所示。

由表6可知，雖然兩階段啟發(fā)式算法在計(jì)算時(shí)間上不如單階段算法，但也遠(yuǎn)遠(yuǎn)優(yōu)于Gurobi求解器算法，同時(shí)兩階段啟發(fā)式算法比單階段算法和Gurobi最佳可行解算法的求解效果更好。

表6 算法結(jié)果對比Table 6 Comparison of algorithm results

此外，為驗(yàn)證本文算法與研究結(jié)果的可靠性，在不同規(guī)模算例中對算法進(jìn)行測試，并對比不同算法得到的結(jié)果。加油站個(gè)數(shù)從100 開始，每次遞增50，直到加油站數(shù)量達(dá)到500。分別調(diào)用算法1、算法2 求解9組算例，每組算例分別運(yùn)行10次并記錄平均總配送成本以及平均求解時(shí)間，記算法3求解時(shí)間為1 800 s。針對算法2，使用SC表示算法2的總成本(元)；ST表示算法2的求解時(shí)間(s)。調(diào)用三種算法得到不同規(guī)模算例的結(jié)果如表7所示。

由表7可知，在不多于500個(gè)加油站的算例中，算法1與算法2耗時(shí)隨算例規(guī)模的增加存在緩慢上升趨勢，并且雖然算法2的平均求解時(shí)間小于算法1的求解時(shí)間，但對于規(guī)模最大的算例，算法1的平均求解時(shí)間也不超過6 s，說明針對此數(shù)量級下的問題規(guī)模，本文研究的兩階段啟發(fā)式算法仍然可以保持滿意的求解速度。

表7 不同規(guī)模算例下的結(jié)果Table 7 Results of instances under different sizes

綜合對比三種算法的求解時(shí)間，以及得到的平均總成本或最佳可行成本可知，雖然算法1在各個(gè)算例中的平均求解時(shí)間大于算法2，但在實(shí)際應(yīng)用中仍可接受并且明顯小于算法3的求解時(shí)間，同時(shí)，算法1的平均總成本優(yōu)于另外兩種算法，算法3的平均總成本次于算法1但優(yōu)于算法2，說明本文的兩階段啟發(fā)式算法在不同規(guī)模算例下得到的結(jié)果仍然具有較高的可靠性。

4 結(jié)論

結(jié)合成品油二次配送問題的實(shí)際場景，研究了隨機(jī)需求、多車型軟時(shí)間窗、滿載可分卸的成品油二次配送庫存-路徑問題，以總配送成本極小化為目標(biāo)建立了混合整數(shù)規(guī)劃模型，利用分解策略將問題求解過程分解為庫存控制和路徑優(yōu)化兩個(gè)階段，并設(shè)計(jì)了路徑優(yōu)化階段的遺傳算法和C-W節(jié)約算法，通過不同規(guī)模算例驗(yàn)證了模型和算法的有效性。

本文算法的設(shè)計(jì)思路可推廣其他類似問題，為解決其他背景下考慮隨機(jī)需求的多車型軟時(shí)間窗庫存-路徑問題提供了研究思路。

在成品油二次配送庫存-路徑問題的研究中，對加油站的銷售量進(jìn)行了一定的簡化，假設(shè)加油站的銷售量在一天中各個(gè)時(shí)段服從相同的分布規(guī)律。實(shí)際中，加油站每天不同時(shí)段的銷量變化可能比較大，此時(shí)需要分時(shí)段考慮銷售量服從的分布規(guī)律，這種情況下，為了確保加油站不斷貨，需要用更科學(xué)的方法計(jì)算補(bǔ)貨時(shí)間窗和補(bǔ)貨量。另外，本文算法仍然屬于啟發(fā)式算法，無法保證找到精確最優(yōu)解，接下來可以結(jié)合模型特點(diǎn)，研究精確算法或其他類型的智能算法。