石油海運領域運籌優化方法應用研究綜述

王 薇，鄭瀾波

（武漢理工大學 物流工程學院，湖北 武漢 430063）

1 引言

化學品生產體量較大，且屬危險品必須以安全方式運輸，因此化學品相關行業供應鏈成本在所有行業中排名最高。作為全球化學品供應鏈重要組成部分，石油的海洋運輸物流成本高達采購成本的20%。石油海上運輸涉及油輪作業、航線制定等決策問題，都直接影響石油運輸成本，這些問題大多涉及多類型資源且具備多種約束，是決策復雜性高的組合優化問題。隨著運籌技術的發展，運籌優化技術在調度及路由問題上有著豐富的實際應用與研究成果，同樣適用于石油海上運輸的優化場景。越來越多的學者借助運籌優化方法解決石油海運優化問題，提升海運效率和經濟效益。

2 文獻檢索及場景劃分

通過知網、萬方等搜索引擎進行檢索，得到國內有關石油海上運輸優化的研究較少，研究多數集中在內陸運輸領域，對石油海運缺乏關注。通過谷歌學者數據庫檢索同時包含“運籌優化”和“石油海上運輸”關鍵字的文獻，發現1980 至2019年相關研究數量增勢明顯。以搜索詞“石油”、“海上運輸”和“運籌優化”識別文檔標題、摘要和關鍵字，通過連接運算符與“油船”、“港口”以及“調度”等檢索詞進行組合篩選，創建各短語的文獻數據集后整合為本文的目標文獻集。具體如圖1所示。

圖1 谷歌學者庫術語包含“石油海上運輸”和“運籌優化”的文章數

以是否涉及石油運輸船舶調度為標準，包括針對石油運輸船舶的調度以及船舶與其他銜接資源的聯合調度，定義石油海上運輸優化的范圍，將對象相同、約束類似的優化問題進行歸納劃分。得到運籌優化方法在石油海上運輸方向的應用場景劃分如下：石油運輸船舶調度及路由、石油在港作業調度及油輪海上駁運。以原油為例，對應場景如圖2所示。

圖2 原油海上運輸流程及對應優化場景

3 石油運輸船舶調度及路由

石油運輸船舶調度及路由問題中，船隊需決策執行哪些訂單，以及港口的訪問順序，期間裝載容量不得超過船舶容量。該問題的理論基礎為車輛路徑問題（VRP），車輛路徑問題自 1959年被 Dantzig 和Ramser[1]提出以來，一直是優化調度研究中的熱點，并衍生出諸多分支，取送貨車輛路徑問題(Vehicle Routing Problem with Simultaneous Delivery and Pickup，VRPSDP)與需求可分割的車輛路徑問題(Split Delivery Vehicle Routing Problem，SDVRP)是很重要的兩個分支。

3.1 石油船舶取送貨路徑問題

VRPSDP 問題由Min[2]首次提出，大部分石油海運問題都是取送貨問題，油船根據長期合同訂單，將石油從取貨港運輸到目的港，如何分配船舶、制定航線使得費用最小、效率最高是決策的難點。此外，為了平衡高額運輸成本，船舶公司在完成合同訂單同時，會根據船舶情況承接市場現貨訂單。因此，在滿足車輛容量條件下，需進一步決策組合運輸哪些市場訂單使得盈利最大。

相關研究較多采用混合整數線性規劃（MILP）模型或者網絡流模型。兩種模型可以相互借鑒轉化，達到優化模型表達的效果，但需要根據實際問題具體分析。早在1987年，Brown 等[3]便提出原油海上運輸是一個油輪路由調度問題，首次將基礎的單艙單型油輪運輸多種原油的航線制定問題表述為一個彈性集合分割問題。隨著多船型選擇，多種貨物協同運輸等條件出現，問題逐漸復雜，常見處理方式是將復雜問題通過D-W 分解、Benders 分解等算法，拆分為主問題、子問題進行求解。Kobayashi等[4]提出將帶時間窗的船舶取送貨問題拆分為兩個子問題：

（1）任務劃分子問題：將訂單分配給各船舶，劃分子問題的結果為路由子問題的輸入。

（2）路由子問題：制定最佳的單個船舶訪問港口的航線順序。

基于集合劃分的思想建立模型，將路由子問題轉化為最短路問題求解。最終利用列生成算法求解，帶來了5%-16%的成本改進。

精確算法在大規模航線規劃中表現欠佳的情況下，可基于問題特征添加合適的啟發式規則來加速算法求解。Cóccola等[5]將帶時間窗的多船型多種原油運輸航線制定問題拆分為單船問題和多船問題，開發了一種迭代算法，單船—多船迭代啟發式規則如圖3所示。

圖3 單船-多船迭代啟發式規則

該算法在求解性能上同時對比了Jetlund[6]所提出的啟發式算法和Daniel[7]提出的精確算法。對比Jetlund 的實驗結果，迭代MILP 算法能獲得40%的利潤提升。求解速度方面也有極大改進，與Daniel的精確算法對比，求解結果雖然只提升了0.31%，但求解時間從62 067s 縮減到了764s。在大規模算例中，群智能算法求解也是有效途徑之一。應用群智能算法的關鍵在于確定合適參數。Chan 等[8]通過靈敏度分析得到了改進的多目標蟻群優化算法的最佳參數組合。

3.2 需求可拆分的石油船舶取送貨路徑問題

SDVRP問題由Dror等[9]首次提出，并證明了在需求可拆分情況下分割運輸，運輸總距離和派車數都能得到優化。油船在港取送貨且單個石油訂單可拆分由多個油船滿足，即為需求可分割的取送貨問題（Vehicle Routing Problem with Split Delivery and Split Pickup，VRPSDSP）。該問題結合了VRPSDP 與SDVRP的特征。已知提貨和交貨數量，決策提、交貨的分配以及裝運數量，多艘船舶需協同一致滿足同一訂單的時間及數量要求，相較于單純取送貨問題，其求解難度進一步加大。

該問題約束較多，建模要充分考慮變量設置及約束表達，避免約束數量增長過快。Hennig等[10]在拓展Mckay[11]模型的基礎上引入了路徑流模型，與前者相比具有約束數不隨生成的路由數增長的優勢。模型求解上，Hennig等[12]進一步研究比較了兩種替代路徑流模型方法，并分析了它們在列生成設置中的適用程度。Nishi等[13]將石油船舶調度問題轉化為需求可拆分的車輛路由問題，提出了一種基于列生成的高效算法，與啟發式算法進行了比較并驗證了算法有效性。隨后，又提出了一種基于列生成的高效啟發式算法，與分枝定界算法和人工算子性能比較效果更優[14]。

3.3 帶庫存約束的石油庫存船舶路徑問題

從是否考慮庫存約束的角度，石油海運路由問題可進一步衍生出庫存路由問題。Miller[15]等人提出了第一個海運庫存航線問題。發貨是確保收貨點沒有缺貨而不由訂單發起，這種交付環境下的問題稱為庫存路由問題。

Christiansen 等就同一個結合庫存管理的帶時間窗船舶航線問題建立了MILP 問題[16]和網絡流模型[17]，結合D-W 分解與分枝定界解得了一致的結果。在此基礎上，Al-Khayya[18]等人解決了涉及非線性約束的多類型船隊航線制定問題，采用了Christiansen 的網絡流公式開發了MILNP 模型，并證明該模型可重構為具有特殊結構的等價MILP模型，為非線性問題轉化為線性問題求解提供了新的思路。Shen 等[19]開發了路徑重鏈接方法增強的貪婪隨機自適應搜索元啟發式方法，該方法對于隨機生成的中小型實例效果良好。在此基礎上，Shen等[20]采用拉格朗日松弛方法求解近似最優解，與之前實驗結果對比更優，特別是在較大規模算例情況下。

此外，有學者在多式聯運場景下從系統網絡層面優化石油運輸。如Lakovou等[21]采用網絡流模型替代傳統最短路徑公式，提出僅考慮起訖點的航線規劃可能導致某些環節超載，應從多起訖點、多商品網絡角度考慮。Li 等[22]解決了競爭性多式聯運和多產品網絡中的油流分配問題。還有一些特殊問題，例如周曉玲等[23]基于零散批次油品的拼船運輸問題總結了7類運輸優化限制條件，并應用改進差分進化算法求解。

綜上，石油船舶路徑問題多采用MILP 模型，非線性約束可轉化為線性求解，有些轉化可能會加大模型的求解難度。網絡流模型在某些約束表達上具備優勢，還可借鑒利用圖論的相關算法框架。算法研究中，基于搜索的啟發式算法較多，測試已知的啟發式方法是否適合油輪海上運輸的路徑調度可能會是研究熱點?；诹猩傻木_算法較多，精確算法研究關鍵是開發有效解決定價問題的方法。

4 石油在港作業調度問題

石油在港調度包括原油從油輪卸載、原油在碼頭罐區存儲、原油從碼頭罐區運送到裝置罐區、原油在裝置罐區存儲、原油從裝置罐區到生產裝置的管道輸送。

學術界主要還是采用數學規劃建模解決石油在港作業調度問題。原油調度一般同時包含連續操作和離散決策變量，建模關鍵是時間約束的表達，分為離散時間和連續時間兩大類。離散時間建模簡單直觀，但對時間的離散化近似降低了模型精度。連續時間表達模型更精確，在離散事件發生頻率不高且具有一定規律性的問題中整數變量規模較小，求解更容易。

對原油調度問題的早期研究采用離散時間建模方法建立MIP 或MINLP 模型。早在1996年，Shah[24]開發離散時間MILP模型，將原油調度分為兩個子問題，上游問題包括左舷油罐卸載，下游問題包括煉油廠儲罐與原油蒸餾裝置的連接，以及從港口泵送至煉油廠的順序和數量。若出現港口子問題不可行的現象，則通過松弛子問題的約束條件后重新求解，直至港口子問題可行。同年，Lee 等人[25]提出的離散時間MIP 模型通過限定裝置罐內原油關鍵組分濃度的上下限，將原油混合操作視為單獨的原油組分流而規避非線性，但模型得到的解會出現濃度不一致的現象。隨著油輪、油罐數目增加或調度周期延長，計算量驟然增大，出現求解時間過長甚至無法獲得可行解的情況。為了能在合理時間內求解，可采用減少調度模型的最小調度單元數的辦法，但會損失部分可行域。Li[26]為了避免直接求解MINLP問題，提出將模型分解成MIP 和NLP 兩部分迭代求解，但這種方法可能會在最優解存在的情況下找不到解。Reddy等[27]針對沿海型煉油企業建立離散時間MINLP模型，并采用按時間軸滾動迭代求解MIP，一定程度上克服了非線性的問題。

連續時間建模方面，Jia等[28-29]將連續時間建模方法應用于原油調度問題，建立基于事件的連續時間MIP模型，仍采用線性化方法處理原油混合操作帶來的非線性約束，未解決濃度不一致問題。Moro等[30]建立了同步連續時間模型求解通過管線輸油至廠區油庫的原油調度問題，并比較了連續時間MINLP 模型和將儲油罐庫存體積離散化后形成的MIP 模型。考慮到連續時間表達方式的優勢，Reddy等[31]在之前離散模型的基礎上建立連續時間MINLP 模型，同樣采用按時間軸滾動迭代求解MIP 的方法。后由Karimi所帶領的研究小組對此模型做了一系列改進：為了解決迭代過程中出現不可行解的情況，討論了當出現不可行解時按單個時間段往前回溯和按大的時間段塊往前回溯的方法[32]；考慮到實際調度應用中油輪到期波動等異常事件[33]；設計啟發式重調度方法快速獲得高質量可行解[34]等。

綜上，數學規劃模型求解難度與整型變量和非線性約束關系密切，體現在：設置各工作單元的狀態變量均為0-1變量，混輸過程中原油的二次混合帶來一些非線性因素。盡管線性規劃對于解決收斂問題最優解有著無以倫比的優勢，但在實際應用中仍有許多不足：

（1）通用性差，實際問題結構與運作情況互不相同，且問題規模大導致求不出解；

（2）MIP 雖能把非線性問題線性化，但非所有的非線性方程都能有理想的處理方法。

5 油輪海上駁運調度

超大型原油船、巨型油輪等運輸船無法通過淺航道或淺港口碼頭，需通過小型船舶將原油從大型油輪轉運至小型船舶，是石油供應鏈中的一個關鍵步驟。油輪駁運增加了原油供應靈活性并提高輸送效率，并有助于減少大型油輪的定期租船成本或滯期費。

Daskin 等[35]為一個超大型油輪的一般過駁問題建立了一組排隊模型，包括用于駁船操作的循環排隊模型和用于油輪延誤的近似排隊模型。Lin等[36]開發了一種連續時間MILP數學模型，為每艘船舶引入一系列事件點，并定義0-1變量以確定船舶是否要在每個事件點開始一項任務，包括安裝油輪、從油輪上泵油、拆卸油輪、行駛到煉油廠、?？繜捰蛷S、泵油、卸船、回到錨地。Huang 和Karimi[37]進一步研究利用不同的線性化方法開發了連續時間MILP模型，解決了油輪駁運的一般現實問題，彌補了Lin研究忽略一些實際問題特征的不足，包括多艙服務船在一次航行中提取不同的原油包裹，在一次航行中多次訪問不同的超大型油輪，考慮原油密度、滯期費和時間租賃成本影響等。Huang和Karimi[38]為區域分銷的一般駁運場景建立調度模型，采用大M 松弛法求解每艘接收船接收貨物的順序、側面（左舷或右舷）和時間，在簡單案例中降低成本6.3%。

綜上，駁運調度的研究相對較少，不科學調度導致的擁堵會使得滯期費迅速增加，減少等待時間、提高駁船利用率至關重要。油輪海上駁運的優化目標往往設置為最小化成本，包括油輪滯期費和駁船作業費。

除了以上場景，一些細分問題的研究數量不多，但也為石油海上運輸優化奠定了理論和實際研究基礎。例如石油運輸風險評估，風險評估量化模型作為構建海上石油運輸多目標模型相當重要的部分，在過去很長一段時間里相關文獻存在嚴重空白。前文提到的Li 和Lakovou 都旨在解決包括石油產品在內，考慮風險影響的危險品海上運輸問題。

6 結論及建議

廣大學者利用以線性規劃為主的運籌優化方法，為石油海上運輸實際應用帶來了切實的好處。結合以上各場景的綜述分析提出以下建議：

（1）拓展優化范圍研究全局優化調度。目前已有一些將原油調度問題和煉油生產過程調度、成品油配送等集成的研究（如 Guyonnet 等[39]和 lee 等[40]）。但問題規模巨大，嚴格優化方法應用在全局調度還有困難，所以原油在港調度等局部優化問題仍是近幾年的研究熱點。隨著計算技術的發展，基于全局的優化將是具有挑戰性和前景的研究方向之一。

（2）根據實際添加特殊約束和設置變量。危險化學品的調度問題具備多種特殊約束，如貨物/船貨不兼容等。此外，當前研究常將船速簡化為常量，但燃油消耗率其實是航速的非線性函數，加入有關船速的決策可限制油耗帶來成本的進一步優化。

（3）利用約束規劃、人工智能等方法彌補線性規劃求解的不足?；谌斯ぶ悄艿募s束規劃方法可直接處理非線性問題，并根據變量的邏輯關系對問題進行建模和求解。且因搜索機制不同，可求解較大規模邏輯組合很強的問題。此外，以往研究方案通用性差，約束規劃以其靈活的建模特點，有助于開發靈活的求解框架。

總的來說，石油海上運輸優化是化工物流管理的重要研究領域，運籌規劃擁有科學的理論及適合的工具方法來推動該領域向前發展。在國內研究相對較少的情況下，國內學者更應重視石油海運優化的相關課題，以帶來更多有價值的研究成果。