海上供應(yīng)船的周期性調(diào)度與規(guī)劃

侯春媛，鐘銘，岳美

(大連海事大學(xué)交通運(yùn)輸工程學(xué)院，遼寧 大連 116026)

0 引 言

許多石油和天然氣生產(chǎn)商運(yùn)營著海上設(shè)施。因?yàn)楹Ｉ显O(shè)施空間有限，所以需要定期進(jìn)行補(bǔ)給，以保證海上設(shè)施生產(chǎn)活動的正常進(jìn)行。對于海上設(shè)施的補(bǔ)給需要專門的船將所需物資從陸上供應(yīng)基地運(yùn)送到海上設(shè)施。這種在供應(yīng)基地與海上設(shè)施之間來回運(yùn)輸補(bǔ)給的船舶即為供應(yīng)船。在海上供應(yīng)鏈中，供應(yīng)船是一種非常昂貴的資源，一艘供應(yīng)船的日租金可達(dá)數(shù)萬美元。因此，為提高供應(yīng)服務(wù)的成本效益，對供應(yīng)船進(jìn)行規(guī)劃是非常有必要的。供應(yīng)船規(guī)劃問題(supply vessel planning problem, SVPP)包括確定最優(yōu)的船隊組成、確定規(guī)劃期內(nèi)各供應(yīng)船的航線和時間表(即供應(yīng)船的船期表)。船期表的有效期取決于何時出現(xiàn)新的需求或者需求發(fā)生巨大的變化(例如，新的勘探鉆機(jī)需要進(jìn)行維修，或者某海上設(shè)施的主要作業(yè)從鉆井改為生產(chǎn)，或者其作業(yè)從鉆井和生產(chǎn)改為僅生產(chǎn))，一般為幾個月。SVPP的目標(biāo)是最小化運(yùn)營成本，同時保持可靠的供應(yīng)服務(wù)，要盡量減少的費(fèi)用是供應(yīng)船的定期租船費(fèi)用(固定成本)和航行費(fèi)用(可變成本)。供應(yīng)船的一次航行起止于陸上供應(yīng)基地，且供應(yīng)船在一次航行中訪問一個或多個海上設(shè)施。

SVPP是一個船隊組成和周期性的路線問題，與車輛路徑問題(vehicle routing problem，VRP)相似。DANTZIG等最早提出VRP，并基于線性規(guī)劃給出該問題的求解過程。

SVPP雖然與VRP有許多相似之處，但也有其自身的特性，如在規(guī)劃期內(nèi)需要多次訪問海上設(shè)施。目前，研究SVPP的文獻(xiàn)較少。BORTHEN等提出一個針對SVPP的雙目標(biāo)模型及其遺傳搜索求解方法，使規(guī)劃人員能夠同時考慮成本和與持久性相關(guān)的目標(biāo)。NORLUND等提出一種多步驟模擬優(yōu)化方法，生成能同時考慮成本、排放和魯棒性等3個因素的規(guī)劃期供應(yīng)船計劃。KISIALIOU等引入優(yōu)化與仿真相結(jié)合的魯棒方法，在生成船舶交貨時刻表時考慮特定航程的魯棒性。BORTHEN等提出一種基于混合遺傳搜索和自適應(yīng)多樣性控制的元啟發(fā)式算法，成功地解決了多周期的VRP。CUESTA等研究了一艘船的裝卸和交貨問題，即單艘船在一組海上石油平臺上執(zhí)行裝卸和交貨操作，并涉及訂單選擇。HALVORSEN-WEARE等提出一個新的弧流模型和一個基于航行的模型來解決SVPP。KISIALIOU等研究了具有靈活出發(fā)時間和多類型船舶的周期性供應(yīng)船規(guī)劃問題，并開發(fā)了一個自適應(yīng)大鄰域搜索算法對其進(jìn)行了求解。MAISIUK等提出一個離散事件模擬模型，以評估考慮不確定性天氣條件和未來現(xiàn)貨船費(fèi)率的船隊規(guī)模配置，并利用實(shí)際算例對模型進(jìn)行了驗(yàn)證和測試。HALVORSEN-WEARE等考慮海上供應(yīng)船服務(wù)中出現(xiàn)的船隊組成和周期路徑問題，提出一種基于航次的求解方法。NORLUND等開發(fā)了一個模擬優(yōu)化工具，用于估計在各種天氣條件下船舶在規(guī)劃期內(nèi)的平均燃料消耗，并生成在不同天氣條件下的航次，提高了在環(huán)境目標(biāo)與成本目標(biāo)之間進(jìn)行優(yōu)先權(quán)衡來生成船期表的可行性。NORLUND等通過優(yōu)化航行速度來減少供應(yīng)船在海上設(shè)施供應(yīng)服務(wù)中的排放，并介紹了幾種用于船舶周期調(diào)度的速度優(yōu)化策略。

綜合分析以上文獻(xiàn)可知，現(xiàn)有解決SVPP的方法主要為求其近似解的啟發(fā)式算法，不能保證解的質(zhì)量。本文在現(xiàn)有研究的基礎(chǔ)上，考慮各海上設(shè)施需要訪問的次數(shù)、供應(yīng)基地和供應(yīng)船容量約束、船舶均勻離港等因素，以最小化運(yùn)營成本為目標(biāo)，建立海上供應(yīng)船調(diào)度與規(guī)劃模型；運(yùn)用分支定價算法對模型進(jìn)行求解，并提出一種生成船期表的方法；通過算例分析證明算法和模型的合理性與有效性。

1 問題描述

SVPP既可作為確定性問題求解，也可以作為隨機(jī)問題求解。確定性供應(yīng)船規(guī)劃意味著參數(shù)值不隨時間動態(tài)變化，不受不確定因素(比如不確定天氣條件)的影響。本文研究確定性SVPP。

=∪{0}∪{+1}為所有網(wǎng)絡(luò)節(jié)點(diǎn)的集合，其中為海上設(shè)施集合，={1,2,…,}，0代表陸上供應(yīng)基地，+1代表虛擬陸上供應(yīng)基地；=∪{0}；+1=∪{+1}；={(,)|,∈,≠}為弧集；={,}為供應(yīng)網(wǎng)絡(luò)集合；為海上設(shè)施集合的包含任意個海上設(shè)施的真子集，即?；為航次集合，∈；為供應(yīng)船類型集合，∈；為型供應(yīng)船的數(shù)量；為型供應(yīng)船的容量；f,為型供應(yīng)船的固定成本；,,為型供應(yīng)船從海上設(shè)施到的可變成本；為供應(yīng)基地第天的服務(wù)能力；和分別為航次最短和最長持續(xù)時間；為在供應(yīng)船的一次航行中所訪問海上設(shè)施的貨物需求量；s,為服務(wù)海上設(shè)施的時間；為一個規(guī)劃期內(nèi)海上設(shè)施所需的訪問次數(shù)；,,為型供應(yīng)船從海上設(shè)施到的航行時間；為規(guī)劃期，其中∈。,,和,,為決策變量：型供應(yīng)船經(jīng)過弧(,)時,,為1，否則為0；型供應(yīng)船在第天開始航次時,,為1，否則為0。

2 模型及算法

2.1 模型建立

SVPP的目標(biāo)是在保證可靠的供應(yīng)服務(wù)的情況下使運(yùn)營成本最小化。通常石油公司通過定期租賃供應(yīng)船進(jìn)行供應(yīng)服務(wù)，并確定規(guī)劃期內(nèi)的船期表，該計劃通常在幾個月內(nèi)是有效的。因此，本文給定海上設(shè)施在規(guī)劃期內(nèi)的總需求。由于海上設(shè)施空間有限，供應(yīng)船規(guī)劃還需要滿足海上設(shè)施在規(guī)劃期內(nèi)所需的訪問次數(shù)，則每次訪問海上設(shè)施的需求為總需求除以訪問次數(shù)，且對于任一航次，供應(yīng)船所訪問的海上設(shè)施的總需求量不應(yīng)超過其容量。根據(jù)SVPP區(qū)別于VRP的特性，本文模型考慮在規(guī)劃期內(nèi)需要訪問海上設(shè)施的次數(shù)、供應(yīng)基地和供應(yīng)船容量約束、船舶均勻離港等，并采用由Dantzig-Fulkerson-Johnson提出的方法(簡稱DFJ法)來消除航次內(nèi)的子回路。模型目標(biāo)函數(shù)包含固定的定期租船成本和可變的航行成本兩部分，具體描述如下：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

,,∈{0,1}

(9)

(10)

(11)

(12)

式(1)表示目標(biāo)函數(shù)為航行的固定成本和變動成本的總和最?。皇?2)和(3)表示在規(guī)劃期內(nèi)各供應(yīng)船必須從陸上供應(yīng)基地出發(fā)并返回到虛擬陸上供應(yīng)基地；式(4)為流量守恒約束，表示到達(dá)和離開同一海上設(shè)施的弧的數(shù)量必須相等；式(5)表示供應(yīng)船的裝載量不得超過其容量；式(6)表示一個航次的持續(xù)時間約束；式(7)表示采用DFJ法消除任意一個包含任意個海上設(shè)施的子回路；式(8)表示任意一個航次訪問一個海上設(shè)施最多只能有一次；式(9)表示變量約束；式(10)表示同一航次供應(yīng)船不能連續(xù)訪問同一個海上設(shè)施；式(11)表示必須保證海上設(shè)施在規(guī)劃期內(nèi)所需的訪問次數(shù)；式(12)表示可用型供應(yīng)船的數(shù)量約束。

船期表和均勻離港是由給定的海上設(shè)施在規(guī)劃期內(nèi)需要的訪問次數(shù)決定的。用、和分別表示在規(guī)劃期內(nèi)需要訪問2次、3次和4次的海上設(shè)施集合，則船期表和均勻離港約束如下：

(13)

(14)

(15)

(16)

(17)

,,∈{0,1}

(18)

將決策變量，，中的用(+)mod||代替就為式(14)～(17)中的，,(+)mod||，其中(+)mod||表示(+)除以||的余數(shù)，||表示規(guī)劃期的長度。式(13)表示陸上供應(yīng)基地服務(wù)供應(yīng)船的能力約束；式(14)確保在規(guī)劃期內(nèi)訪問海上設(shè)施2次，在任何2天(=0,1)內(nèi)最多有1次離開；式(15)確保在規(guī)劃期內(nèi)訪問海上設(shè)施3次，在任何3天(=0,1,2)內(nèi)至少有1次且不超過2次的離開；式(16)確保在規(guī)劃期內(nèi)訪問海上設(shè)施4次，在任何4天(=0,1,2,3)內(nèi)至少有2次且不超過3次的離開；式(17)表示任意連續(xù)2天同一艘船最多只能離開1次；式(18)表示變量約束。

2.2 算法設(shè)計

2.2.1 基本概念與流程

列生成算法可以快速求解大規(guī)模問題，但無法獲得整數(shù)最優(yōu)解；分支定界法雖然可以獲得整數(shù)最優(yōu)解，但對求解大規(guī)模問題乏力。DESROSIERS等于1992年提出分支定價算法，獲得VRP的整數(shù)最優(yōu)解。分支定價算法就是在分支定界法的基礎(chǔ)上，采用列生成算法對每個分支進(jìn)行求解。圖1簡要概括了分支定價算法的主要步驟。其中列生成算法的核心思想為：用單純形法求解經(jīng)過線性松弛后的主問題，用所得約束的對偶變量對子問題進(jìn)行定價，并調(diào)用MATLAB的LPSolve工具箱對定價后的子問題進(jìn)行求解，然后將對子問題求解所得的路徑集作為新的列加入原有路徑集中;再用單純形法求解松弛后的主問題，得到新的后對子問題重新定價，并繼續(xù)尋找有效路徑集；如此迭代，直到無法找到有效路徑，即獲得了松弛后主問題的最優(yōu)解。

圖1 分支定價算法設(shè)計流程

采用上述步驟可以獲得最優(yōu)的航次集合，但無法獲得各航次的離港日期，即船期表。本文提出一種生成船期表的方法，該方法的具體流程見圖2。

圖2 船期表生成流程

2.2.2 模型分解

由于上述模型中含有大量的約束和變量，為求得模型的最優(yōu)解，本文根據(jù)Dantzig-Wolfe分解原理，把上述模型分解成一個基于航行路徑的主問題和一個含資源約束的最短路徑子問題。

f,,≠；,,，若型供應(yīng)船的航次訪問海上設(shè)施，則為1，否則為0；,，若解中包含組合(,)，則為1，否則為0。主模型如下：

(19)

s.t.

(22)

式(20)和(21)與式(11)和(12)類似，式(22)表示變量約束。由于可行航次集中的組合(,)數(shù)量較多，本文采用列生成算法通過不斷迭代為求解松弛后的主問題加入有效列(,)。

(2)子問題模型。表示海上設(shè)施到的距離；表示型供應(yīng)船航行單位距離的可變成本；、分別代表式(20)和式(21)的對偶變量。主問題的檢驗(yàn)數(shù)

(23)

令+1=，則

(24)

(25)

s.t.式(2)～(10)

式(25)表示在中尋找檢驗(yàn)數(shù)小于零的組合(,)。子問題則為求解個獨(dú)立問題，對于每一個問題所求得的目標(biāo)函數(shù)值，只有小于零才能作為新的列代入主問題中進(jìn)行迭代，以優(yōu)化主問題的目標(biāo)函數(shù)值；其中的定價是根據(jù)修改,,，得到新的可變成本,-，當(dāng)不存在使得目標(biāo)函數(shù)值小于零的列時，當(dāng)前解即為松弛后主問題的最優(yōu)解。

3 算例及分析

3.1 數(shù)據(jù)收集

由于部分?jǐn)?shù)據(jù)較難獲得，所以本文參照我國某石油服務(wù)公司的公開信息和HALVORSEN-WEARE等的相關(guān)數(shù)據(jù)，并根據(jù)實(shí)際情況進(jìn)行設(shè)置。在備選船隊方面，本文給出了6類船型(見表1)并提供了供應(yīng)船甲板面積、經(jīng)濟(jì)航速等船舶信息。假定各類型船舶在規(guī)劃期內(nèi)的使用次數(shù)不超過3次，存在10個海上設(shè)施和1個陸上供應(yīng)基地，且需要訪問1次的海上設(shè)施為1、2、10，需要訪問2次的海上設(shè)施為3、7、9，需要訪問3次的海上設(shè)施為5、8，需要訪問4次的海上設(shè)施為4、6。在渤海海域選取海上設(shè)施和陸上供應(yīng)基地，圖3為渤海海域海上設(shè)施和陸上供應(yīng)基地的具體分布情況。

表1 供應(yīng)船的主要參數(shù)

圖3 渤海海域海上設(shè)施和陸上供應(yīng)基地的分布情況

3.2 算例驗(yàn)證

本文程序的運(yùn)行環(huán)境如下：計算機(jī)參數(shù)配置為AMD Ryzen 5 4600H with Radeon Graphics 3.00 GHz，應(yīng)用MATLAB調(diào)用LPSolve工具箱編寫計算程序。結(jié)合本文所提出的生成船期表的方法，得到表2所示算例優(yōu)化結(jié)果。表2展示了在規(guī)劃期內(nèi)，根據(jù)各海上設(shè)施的需求及其所需的訪問次數(shù)分別配置了相應(yīng)的供應(yīng)船、各船的航行路徑、各航次的持續(xù)時間、各船的離港次數(shù)和離港日期等，并在可行的候選航次中選擇了5個最優(yōu)航次組合，使用了C、E兩種船型。算例優(yōu)化結(jié)果滿足了規(guī)劃期內(nèi)各海上設(shè)施的訪問次數(shù)需求、船舶容量約束、船舶使用次數(shù)約束，且每個航次的船舶裝載量非常接近船舶容量，驗(yàn)證了本文模型及算法的有效性。

表2 算例優(yōu)化結(jié)果

表3顯示了在式(13)～(18)約束下，在規(guī)劃期內(nèi)需要進(jìn)行多次訪問的海上設(shè)施對應(yīng)航次的離港日期分布比較均勻，驗(yàn)證了所提出的生成船期表的方法是可行的。

表3 供應(yīng)船離港模式

3.3 敏感性分析

當(dāng)船舶的固定成本(即定期租船成本)不變時，可變成本直接影響運(yùn)營收益。因此，本文通過對可變成本進(jìn)行敏感性分析，分析可變成本對船型選擇的影響。在保證其他條件不變的情況下，將可變成本分別設(shè)為相對初始值逐漸增加0、50%、100%和150%，結(jié)果見圖4。

圖4 各類型船舶離港次數(shù)及航次數(shù)變化趨勢

由圖4可以得出兩點(diǎn)結(jié)論：(1)隨著可變成本的增加，離港船舶的船型分布更加廣泛；(2)當(dāng)可變成本增加到一定程度時，總航次數(shù)呈現(xiàn)上升趨勢，這是因?yàn)殡S著可變成本的增加，固定成本已經(jīng)不是決定性因素。由可變成本敏感性分析可知，在進(jìn)行船舶類型選擇和航次規(guī)劃時，供應(yīng)船規(guī)劃工作者應(yīng)該考慮船舶使用期間可變成本的變化。

4 結(jié) 論

針對供應(yīng)船規(guī)劃問題(SVPP)，考慮在規(guī)劃期內(nèi)各海上設(shè)施需要訪問的次數(shù)、供應(yīng)基地和供應(yīng)船容量約束、船舶均勻離港等因素，建立海上供應(yīng)船調(diào)度與規(guī)劃模型。運(yùn)用分支定價算法求解模型并提出一種生成船期表的方法。以渤海海域?yàn)槔M(jìn)行算例驗(yàn)證，得到了規(guī)劃期內(nèi)的最優(yōu)航次組合、每艘船的航行路徑和離港次數(shù)、船期表，證明了算法和模型的合理性與有效性。通過對可變成本的敏感性分析可知：(1)隨著可變成本的增加，離港船舶的船型分布更加廣泛；(2)當(dāng)可變成本增加到一定程度時，航次數(shù)呈現(xiàn)上升趨勢。由此可知，在進(jìn)行船舶類型選擇和航次規(guī)劃時，應(yīng)該考慮船舶服役期間可變成本的變化。本文研究可以為供應(yīng)船規(guī)劃工作者提供更好的決策依據(jù)。