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

李珍萍， 焦鵬博， 姜崇宇

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

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

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

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

雖然有關IRP的研究成果十分豐富，但現有研究均對問題進行了不同程度的簡化，如嚴格限制單車型單隔艙、單一產品等約束，忽視需求隨機性、車型隔艙種類、油罐車裝載運輸約束等對總成本的影響。而在實際配送過程中，補貨量及配送時間窗確定、車型種類、隔艙數量等條件往往無法忽視。如為避免缺貨現象以及錯峰配送，需要確定合理的補貨量和配送活動的時間窗；為保障成品油在途運輸的安全性，車輛裝載油品時需要盡可能滿載；為保持油品運輸的經濟性，需要配備多種帶有隔艙的車型等。

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

1 問題描述和模型建立

1.1 問題描述與分析

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

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

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

1.2 混合整數規劃模型

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

(1)

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

流量平衡約束：

(2)

(3)

(4)

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

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

(5)

(6)

(7)

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

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

時間窗約束：

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到達加油站i的時間；M為足夠大的正數；vi為車輛在加油站i的服務時間；tij為車輛從節點i到節點j的行駛時間；LTi為加油站i的最晚服務時間；bikr為車型為r的車輛k到達加油站i時晚于ETi的時間。

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

車輛與路徑之間的關系約束：

(11)

(12)

(13)

式(11)表示只有動用的車輛才能從一個加油站到達其他節點；式(12)表示一個加油站至少被服務一次；式(13)表示對一個加油站同一輛車最多提供一次服務。

決策變量取值約束：

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 算法設計

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

2.1 庫存控制

2.1.1 確定各加油站最晚配送時間窗

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

(21)

2.1.2 確定各加油站補貨量和最早配送時間窗

每個加油站的配送時間點根據最晚配送時間和加油站的平均工作時間T/2確定，如式(22)所示：

(22)

進一步根據加油站的有效庫存容量、期初庫存量和配送時間點T′，按照式(23)確定補貨量：

(23)

根據式(23)可知，當加油站的期初庫存量大于平均需求量和安全庫存量之和時，不需要安排補貨，否則安排補貨，按照使加油站在配送時間點的庫存量恢復到有效庫存容量為標準，確定實際補貨量。

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

(24)

2.1.3 確定各加油站最佳服務車型

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

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

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

2.2 路徑優化

2.2.1 遺傳算法

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

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

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

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

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

f(si)=2Cmax-Ci

(25)

(5) 選擇。采用輪盤賭法選擇個體，質量較優的個體優先進入下一代。

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

(7) 變異。采用逆轉變異方法，在選定個體中隨機產生兩個逆轉點，把兩個逆轉點的基因對調，得到新個體。

(8) 終止條件。達到最大迭代次數則終止迭代，否則轉規則(3)。

(9) 輸出結果。將種群中適應度最優個體作為最優解輸出，得到最優路徑。

2.2.2 C-W節約算法

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

算法的基本步驟如下。

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

圖1可表示為解碼后的序列，黃色節點代表油庫，橙色與藍色節點代表客戶。合并節點即將一條路徑內的客戶點合并為一個節點，得到的序列可以看作是直接配送路徑的集合。

圖1 節點合并示意圖Fig.1 Nodes merging diagram

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

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

對每種車型執行以上算法，得到最終配送計劃。

3 模擬計算與結果分析

3.1 算例描述

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

3.2 算例求解與結果分析

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

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

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

表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

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

表5 小規模算例的求解結果Table 5 Results of small instances

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

由表6可知，雖然兩階段啟發式算法在計算時間上不如單階段算法，但也遠遠優于Gurobi求解器算法，同時兩階段啟發式算法比單階段算法和Gurobi最佳可行解算法的求解效果更好。

表6 算法結果對比Table 6 Comparison of algorithm results

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

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

表7 不同規模算例下的結果Table 7 Results of instances under different sizes

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

4 結論

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

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

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