王 薇，鄭瀾波

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

1 引言

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

2 文獻(xiàn)檢索及場(chǎng)景劃分

通過(guò)知網(wǎng)、萬(wàn)方等搜索引擎進(jìn)行檢索，得到國(guó)內(nèi)有關(guān)石油海上運(yùn)輸優(yōu)化的研究較少，研究多數(shù)集中在內(nèi)陸運(yùn)輸領(lǐng)域，對(duì)石油海運(yùn)缺乏關(guān)注。通過(guò)谷歌學(xué)者數(shù)據(jù)庫(kù)檢索同時(shí)包含“運(yùn)籌優(yōu)化”和“石油海上運(yùn)輸”關(guān)鍵字的文獻(xiàn)，發(fā)現(xiàn)1980 至2019年相關(guān)研究數(shù)量增勢(shì)明顯。以搜索詞“石油”、“海上運(yùn)輸”和“運(yùn)籌優(yōu)化”識(shí)別文檔標(biāo)題、摘要和關(guān)鍵字，通過(guò)連接運(yùn)算符與“油船”、“港口”以及“調(diào)度”等檢索詞進(jìn)行組合篩選，創(chuàng)建各短語(yǔ)的文獻(xiàn)數(shù)據(jù)集后整合為本文的目標(biāo)文獻(xiàn)集。具體如圖1所示。

圖1 谷歌學(xué)者庫(kù)術(shù)語(yǔ)包含“石油海上運(yùn)輸”和“運(yùn)籌優(yōu)化”的文章數(shù)

以是否涉及石油運(yùn)輸船舶調(diào)度為標(biāo)準(zhǔn)，包括針對(duì)石油運(yùn)輸船舶的調(diào)度以及船舶與其他銜接資源的聯(lián)合調(diào)度，定義石油海上運(yùn)輸優(yōu)化的范圍，將對(duì)象相同、約束類似的優(yōu)化問(wèn)題進(jìn)行歸納劃分。得到運(yùn)籌優(yōu)化方法在石油海上運(yùn)輸方向的應(yīng)用場(chǎng)景劃分如下：石油運(yùn)輸船舶調(diào)度及路由、石油在港作業(yè)調(diào)度及油輪海上駁運(yùn)。以原油為例，對(duì)應(yīng)場(chǎng)景如圖2所示。

圖2 原油海上運(yùn)輸流程及對(duì)應(yīng)優(yōu)化場(chǎng)景

3 石油運(yùn)輸船舶調(diào)度及路由

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

3.1 石油船舶取送貨路徑問(wèn)題

VRPSDP 問(wèn)題由Min[2]首次提出，大部分石油海運(yùn)問(wèn)題都是取送貨問(wèn)題，油船根據(jù)長(zhǎng)期合同訂單，將石油從取貨港運(yùn)輸?shù)侥康母郏绾畏峙浯?、制定航線使得費(fèi)用最小、效率最高是決策的難點(diǎn)。此外，為了平衡高額運(yùn)輸成本，船舶公司在完成合同訂單同時(shí)，會(huì)根據(jù)船舶情況承接市場(chǎng)現(xiàn)貨訂單。因此，在滿足車輛容量條件下，需進(jìn)一步?jīng)Q策組合運(yùn)輸哪些市場(chǎng)訂單使得盈利最大。

相關(guān)研究較多采用混合整數(shù)線性規(guī)劃（MILP）模型或者網(wǎng)絡(luò)流模型。兩種模型可以相互借鑒轉(zhuǎn)化，達(dá)到優(yōu)化模型表達(dá)的效果，但需要根據(jù)實(shí)際問(wèn)題具體分析。早在1987年，Brown 等[3]便提出原油海上運(yùn)輸是一個(gè)油輪路由調(diào)度問(wèn)題，首次將基礎(chǔ)的單艙單型油輪運(yùn)輸多種原油的航線制定問(wèn)題表述為一個(gè)彈性集合分割問(wèn)題。隨著多船型選擇，多種貨物協(xié)同運(yùn)輸?shù)葪l件出現(xiàn)，問(wèn)題逐漸復(fù)雜，常見(jiàn)處理方式是將復(fù)雜問(wèn)題通過(guò)D-W 分解、Benders 分解等算法，拆分為主問(wèn)題、子問(wèn)題進(jìn)行求解。Kobayashi等[4]提出將帶時(shí)間窗的船舶取送貨問(wèn)題拆分為兩個(gè)子問(wèn)題：

（1）任務(wù)劃分子問(wèn)題：將訂單分配給各船舶，劃分子問(wèn)題的結(jié)果為路由子問(wèn)題的輸入。

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

基于集合劃分的思想建立模型，將路由子問(wèn)題轉(zhuǎn)化為最短路問(wèn)題求解。最終利用列生成算法求解，帶來(lái)了5%-16%的成本改進(jìn)。

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

圖3 單船-多船迭代啟發(fā)式規(guī)則

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

3.2 需求可拆分的石油船舶取送貨路徑問(wèn)題

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

該問(wèn)題約束較多，建模要充分考慮變量設(shè)置及約束表達(dá)，避免約束數(shù)量增長(zhǎng)過(guò)快。Hennig等[10]在拓展Mckay[11]模型的基礎(chǔ)上引入了路徑流模型，與前者相比具有約束數(shù)不隨生成的路由數(shù)增長(zhǎng)的優(yōu)勢(shì)。模型求解上，Hennig等[12]進(jìn)一步研究比較了兩種替代路徑流模型方法，并分析了它們?cè)诹猩稍O(shè)置中的適用程度。Nishi等[13]將石油船舶調(diào)度問(wèn)題轉(zhuǎn)化為需求可拆分的車輛路由問(wèn)題，提出了一種基于列生成的高效算法，與啟發(fā)式算法進(jìn)行了比較并驗(yàn)證了算法有效性。隨后，又提出了一種基于列生成的高效啟發(fā)式算法，與分枝定界算法和人工算子性能比較效果更優(yōu)[14]。

3.3 帶庫(kù)存約束的石油庫(kù)存船舶路徑問(wèn)題

從是否考慮庫(kù)存約束的角度，石油海運(yùn)路由問(wèn)題可進(jìn)一步衍生出庫(kù)存路由問(wèn)題。Miller[15]等人提出了第一個(gè)海運(yùn)庫(kù)存航線問(wèn)題。發(fā)貨是確保收貨點(diǎn)沒(méi)有缺貨而不由訂單發(fā)起，這種交付環(huán)境下的問(wèn)題稱為庫(kù)存路由問(wèn)題。

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

此外，有學(xué)者在多式聯(lián)運(yùn)場(chǎng)景下從系統(tǒng)網(wǎng)絡(luò)層面優(yōu)化石油運(yùn)輸。如Lakovou等[21]采用網(wǎng)絡(luò)流模型替代傳統(tǒng)最短路徑公式，提出僅考慮起訖點(diǎn)的航線規(guī)劃可能導(dǎo)致某些環(huán)節(jié)超載，應(yīng)從多起訖點(diǎn)、多商品網(wǎng)絡(luò)角度考慮。Li 等[22]解決了競(jìng)爭(zhēng)性多式聯(lián)運(yùn)和多產(chǎn)品網(wǎng)絡(luò)中的油流分配問(wèn)題。還有一些特殊問(wèn)題，例如周曉玲等[23]基于零散批次油品的拼船運(yùn)輸問(wèn)題總結(jié)了7類運(yùn)輸優(yōu)化限制條件，并應(yīng)用改進(jìn)差分進(jìn)化算法求解。

綜上，石油船舶路徑問(wèn)題多采用MILP 模型，非線性約束可轉(zhuǎn)化為線性求解，有些轉(zhuǎn)化可能會(huì)加大模型的求解難度。網(wǎng)絡(luò)流模型在某些約束表達(dá)上具備優(yōu)勢(shì)，還可借鑒利用圖論的相關(guān)算法框架。算法研究中，基于搜索的啟發(fā)式算法較多，測(cè)試已知的啟發(fā)式方法是否適合油輪海上運(yùn)輸?shù)穆窂秸{(diào)度可能會(huì)是研究熱點(diǎn)?；诹猩傻木_算法較多，精確算法研究關(guān)鍵是開(kāi)發(fā)有效解決定價(jià)問(wèn)題的方法。

4 石油在港作業(yè)調(diào)度問(wèn)題

石油在港調(diào)度包括原油從油輪卸載、原油在碼頭罐區(qū)存儲(chǔ)、原油從碼頭罐區(qū)運(yùn)送到裝置罐區(qū)、原油在裝置罐區(qū)存儲(chǔ)、原油從裝置罐區(qū)到生產(chǎn)裝置的管道輸送。

學(xué)術(shù)界主要還是采用數(shù)學(xué)規(guī)劃建模解決石油在港作業(yè)調(diào)度問(wèn)題。原油調(diào)度一般同時(shí)包含連續(xù)操作和離散決策變量，建模關(guān)鍵是時(shí)間約束的表達(dá)，分為離散時(shí)間和連續(xù)時(shí)間兩大類。離散時(shí)間建模簡(jiǎn)單直觀，但對(duì)時(shí)間的離散化近似降低了模型精度。連續(xù)時(shí)間表達(dá)模型更精確，在離散事件發(fā)生頻率不高且具有一定規(guī)律性的問(wèn)題中整數(shù)變量規(guī)模較小，求解更容易。

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

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

綜上，數(shù)學(xué)規(guī)劃模型求解難度與整型變量和非線性約束關(guān)系密切，體現(xiàn)在：設(shè)置各工作單元的狀態(tài)變量均為0-1變量，混輸過(guò)程中原油的二次混合帶來(lái)一些非線性因素。盡管線性規(guī)劃對(duì)于解決收斂問(wèn)題最優(yōu)解有著無(wú)以倫比的優(yōu)勢(shì)，但在實(shí)際應(yīng)用中仍有許多不足：

（1）通用性差，實(shí)際問(wèn)題結(jié)構(gòu)與運(yùn)作情況互不相同，且問(wèn)題規(guī)模大導(dǎo)致求不出解；

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

5 油輪海上駁運(yùn)調(diào)度

超大型原油船、巨型油輪等運(yùn)輸船無(wú)法通過(guò)淺航道或淺港口碼頭，需通過(guò)小型船舶將原油從大型油輪轉(zhuǎn)運(yùn)至小型船舶，是石油供應(yīng)鏈中的一個(gè)關(guān)鍵步驟。油輪駁運(yùn)增加了原油供應(yīng)靈活性并提高輸送效率，并有助于減少大型油輪的定期租船成本或滯期費(fèi)。

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

綜上，駁運(yùn)調(diào)度的研究相對(duì)較少，不科學(xué)調(diào)度導(dǎo)致的擁堵會(huì)使得滯期費(fèi)迅速增加，減少等待時(shí)間、提高駁船利用率至關(guān)重要。油輪海上駁運(yùn)的優(yōu)化目標(biāo)往往設(shè)置為最小化成本，包括油輪滯期費(fèi)和駁船作業(yè)費(fèi)。

除了以上場(chǎng)景，一些細(xì)分問(wèn)題的研究數(shù)量不多，但也為石油海上運(yùn)輸優(yōu)化奠定了理論和實(shí)際研究基礎(chǔ)。例如石油運(yùn)輸風(fēng)險(xiǎn)評(píng)估，風(fēng)險(xiǎn)評(píng)估量化模型作為構(gòu)建海上石油運(yùn)輸多目標(biāo)模型相當(dāng)重要的部分，在過(guò)去很長(zhǎng)一段時(shí)間里相關(guān)文獻(xiàn)存在嚴(yán)重空白。前文提到的Li 和Lakovou 都旨在解決包括石油產(chǎn)品在內(nèi)，考慮風(fēng)險(xiǎn)影響的危險(xiǎn)品海上運(yùn)輸問(wèn)題。

6 結(jié)論及建議

廣大學(xué)者利用以線性規(guī)劃為主的運(yùn)籌優(yōu)化方法，為石油海上運(yùn)輸實(shí)際應(yīng)用帶來(lái)了切實(shí)的好處。結(jié)合以上各場(chǎng)景的綜述分析提出以下建議：

（1）拓展優(yōu)化范圍研究全局優(yōu)化調(diào)度。目前已有一些將原油調(diào)度問(wèn)題和煉油生產(chǎn)過(guò)程調(diào)度、成品油配送等集成的研究（如 Guyonnet 等[39]和 lee 等[40]）。但問(wèn)題規(guī)模巨大，嚴(yán)格優(yōu)化方法應(yīng)用在全局調(diào)度還有困難，所以原油在港調(diào)度等局部?jī)?yōu)化問(wèn)題仍是近幾年的研究熱點(diǎn)。隨著計(jì)算技術(shù)的發(fā)展，基于全局的優(yōu)化將是具有挑戰(zhàn)性和前景的研究方向之一。

（2）根據(jù)實(shí)際添加特殊約束和設(shè)置變量。危險(xiǎn)化學(xué)品的調(diào)度問(wèn)題具備多種特殊約束，如貨物/船貨不兼容等。此外，當(dāng)前研究常將船速簡(jiǎn)化為常量，但燃油消耗率其實(shí)是航速的非線性函數(shù)，加入有關(guān)船速的決策可限制油耗帶來(lái)成本的進(jìn)一步優(yōu)化。

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

總的來(lái)說(shuō)，石油海上運(yùn)輸優(yōu)化是化工物流管理的重要研究領(lǐng)域，運(yùn)籌規(guī)劃擁有科學(xué)的理論及適合的工具方法來(lái)推動(dòng)該領(lǐng)域向前發(fā)展。在國(guó)內(nèi)研究相對(duì)較少的情況下，國(guó)內(nèi)學(xué)者更應(yīng)重視石油海運(yùn)優(yōu)化的相關(guān)課題，以帶來(lái)更多有價(jià)值的研究成果。