海上供應船的周期性調度與規劃

侯春媛，鐘銘，岳美

(大連海事大學交通運輸工程學院，遼寧 大連 116026)

0 引 言

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

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

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

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

1 問題描述

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

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

2 模型及算法

2.1 模型建立

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

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

,,∈{0,1}

(9)

(10)

(11)

(12)

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

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

(13)

(14)

(15)

(16)

(17)

,,∈{0,1}

(18)

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

2.2 算法設計

2.2.1 基本概念與流程

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

圖1 分支定價算法設計流程

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

圖2 船期表生成流程

2.2.2 模型分解

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

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

(19)

s.t.

(22)

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

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

(23)

令+1=，則

(24)

(25)

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

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

3 算例及分析

3.1 數據收集

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

表1 供應船的主要參數

圖3 渤海海域海上設施和陸上供應基地的分布情況

3.2 算例驗證

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

表2 算例優化結果

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

表3 供應船離港模式

3.3 敏感性分析

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

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

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

4 結 論

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