內支線配船與船舶調度優(yōu)化

鄭紅星， 李珊珊， 司 羽

(1. 大連海事大學 交通運輸管理學院，遼寧 大連 116026; 2. 天津外輪代理有限公司,天津 300456)

0 引 言

支線運輸作為干線運輸的貨源保障，其地位日益提升[1]。但由于內支線集裝箱運輸市場貨源不穩(wěn)定，如何通過合理調配內支線船舶來降低營運成本，同時考慮客戶滿意度，是當前從事內支線運輸的航運企業(yè)亟待解決的關鍵問題。

目前，國內外有關航線配船和船舶調度的研究主要集中在干線運輸方面。G. BRONOM等[2]針對不定期運輸企業(yè)的航線設計、航線配船與貨載選擇等問題，構建了整數規(guī)劃模型，并用集分隔方法求解；M. CHRISTIANSEN等將VRPPD理論運用到干線散貨船舶調度問題中，構建了集送貨一體的多船型船舶調度模型[3-4]；C. HSU等[5]研究了軸輻式航線網絡設計問題，構建了以營運成本和庫存成本最小為目標的數學模型，得到最佳的船舶航線以及每條航線配置的船型和發(fā)班間隔；徐驊等[6]研究了競爭市場中集裝箱班輪航線優(yōu)化問題，集成考慮了運力閑置與多航線配船問題。在支線運輸方面，靳志宏等[7]研究了支線船舶調度問題，用軟時間窗約束保證箱位利用率，構建了以航行成本最低為目標的數學模型；楊立乾等[8]基于軸輻式航線，構建了支線運輸多船型船舶調度模型，論文中假設各喂給港可被不同船舶掛靠多次，這點和本文問題相似；靳志宏等[9]針對集裝箱支線運輸船舶調度問題，提出了航次串的概念，把航次配船轉化為對“航次串”配船；計明軍等[10]以干線船舶限制時間和支線船舶容量為基礎，建立了集裝箱船舶支線運輸的航線優(yōu)化模型，并應用于珠三角支線運輸中；龐璽斌等[11]針對單航次單喂給港的運輸方式，以船隊總運輸成本最小為目標，構建了整數規(guī)劃模型，模型中一條船可以承擔多條航線的運輸任務，該模型可以同時解決航線選擇、航線配船、船隊組建問題。

綜上，目前對航線配船和船舶調度的研究主要以干線班輪運輸為主，少量文獻對支線班輪運輸進行研究，且多以運輸成本或運輸時間為單一目標，罕有研究支線不定期船舶運輸。而在不定期的內支線配船和船舶調度中，不僅需要考慮樞紐港的船舶限制時間，還需考慮船舶甩貨成本，值得深入研究。

區(qū)別已有文獻，考慮計劃期內各港口不同時段的貨運需求，以內支線船舶的營運成本和甩貨成本之和為優(yōu)化目標，兼顧船舶在調度中可能出現(xiàn)的主動滯港情況，將內支線配船和船舶調度集成為一體，求得計劃期內配置船舶的最佳類型和數量，以及每艘船舶的最優(yōu)調度方案。

1 問題描述

研究一個樞紐港和眾多支線港之間的集裝箱運輸問題，內支線船舶需將支線港貨物在限定時限內運至樞紐港，然后由干線班輪運達目的地。在計劃期期初，依據本計劃期內樞紐港班輪船期和各支線港的貨運量，從事內支線運輸的航運企業(yè)要明確該計劃期內配置船舶類型、數量和支線港的掛靠次序。

為協(xié)調內支線營運成本與客戶服務水平的矛盾，文中引入了甩貨成本、船舶調度最小耗時和主動滯港的概念。其中，在某計劃期內，航運企業(yè)出于營運成本的考慮，導致部分集裝箱未能趕上計劃期內的干線班輪，由此造成班輪箱位利用率降低以及客戶滿意度下降帶來的損失稱為甩貨成本；船舶調度最小耗時是指船舶由樞紐港出發(fā)經過各支線港口最終回到樞紐港所花費的航行時間，進而得到計劃期內每艘船舶的最大調度次數；主動滯港是指船舶為充分發(fā)揮其作業(yè)效能，提高艙位利用率，而采取的在港外停泊若干小時再進港作業(yè)的策略。

2 優(yōu)化模型

2.1 假設條件

1)船舶從樞紐港出發(fā)至返回樞紐港為一次調度，船舶每次調度經過的支線港不能重復，不考慮支線港之間的運輸業(yè)務；

2)同一支線港在計劃期內可被多次掛靠，并假設船舶航速相同；

3)計劃期按小時分為若干時段；

4)取3 h為船舶停泊(滯港)時間最小單位，即1、2、3表示滯港時間為0 h、3 h和6 h等；

5)船舶在港作業(yè)時間已知；

6)各支線港的集裝箱根據要趕上的班輪不同進行分類。

2.2 符號定義

2.2.1 參數說明

2.2.2 中間變量

2.2.3 決策變量

Xvkij為0～1變量，若船舶v在第k次調度中，由港口i行駛到港口j，則為1，否則為0；Wvki為船舶v在第k次調度中，在港口i的滯港時間；Yvki為0～1變量，若船舶v在第k次調度中，在港口i掛靠，則為1，否則為0；Zv為0～1變量，若船舶v在計劃期內投入使用，則為1，否則為0。

2.3 模型建立

在計劃期內，總成本由兩大部分組成，第一部分為內支線營運成本，包括船舶配置成本Z1、船舶在各港口間的總運輸成本Z2、船舶在各港口的總停泊成本Z3以及支線港集裝箱處理成本Z4；第二部分為內支線配船與船舶調度后的甩貨成本Z5。以上述成本之和最小為目標，建立了如下數學模型。

目標函數:

MinZ=Z1+Z2+Z3+Z4+Z5

(1)

(2)

(3)

(4)

(5)

約束條件：

(6)

(7)

(8)

Yvkm=1,v∈V,k∈K

(9)

(10)

(11)

v∈V,k∈K,i,j∈W

(12)

(13)

(14)

(15)

(16)

(17)

(18)

t≤Avki+BvkiM

(19)

t≥Avki-(1-Bvki)M

(20)

(21)

式(1)～式(4)表示內支線營運成本；式(5)表示甩貨成本，為班輪到達樞紐港前各港口的總貨運需求量與限制時間內運輸量之差乘以單位缺貨成本；式(6)、式(7)船舶在每次調度中，由樞紐港出發(fā)最后回到樞紐港；式(8)計劃期內每個港口至少被掛靠一次；式(9)表示船舶在每次調度中必須掛靠樞紐港；式(10)表示船舶駛入某支線港就必須從該港駛出；式(11)保證船舶每次調度中航行時間的連續(xù)性；式(12)表示上次調度中到達樞紐港的時間與下次調度到達各港口時間的關系；式(13)、式(14)表示船舶每次調度中在各港口裝載量的約束；式(15)表示船舶在每次調度中，總裝載量不得超過船舶容量；式(16)表示船舶每次調度中，抵達各港口時船舶的剩余容量；式(17)表示在每次調度中，船舶在某港口的裝貨量不大于其到達該港時的剩余容量；式(18)～式(20)表示各港口在不同時段的剩余貨量；式(21)表示各支線港的不同集裝箱送達樞紐港的時間限制，即如果船舶在某次調度中在某個港口裝載了d類集裝箱，則該船舶返回樞紐港的時間不得超過d班輪的限制時間。

2.4 求 解

筆者研究問題屬于NP-Hard問題，基于模型特點設計了和聲退火混合算法。該算法在模擬退火算法中嵌入和聲搜索算法的和聲記憶庫，并結合問題特點，基于啟發(fā)式規(guī)則初始化和聲記憶庫。算法步驟如圖1。其中HMCR為記憶庫保留概率，HMS為和聲記憶庫中的和聲數。

圖1 算法流程Fig. 1 Algorithm flowchart

2.4.1 解的表示及編碼

對于m個港口、n艘船舶、最大調度次數為G的內支線配船與船舶調度問題，用1×[n×(G×m+1)]的一維行向量來表示和聲個體。具體解的表示如圖2。1到m列表示船舶1第1次調度方案，m+1到2×m列表示船舶1第2次調度方案，以此類推，其中0代表不掛靠對應的港口，1代表掛靠對應的港口，2代表掛靠對應的港口且主動滯港3 h后進港，3代表掛靠對應的港口且主動滯港6 h后進港，以此類推；第n×G×m+1列到n×(G×m+1)列表示船舶是否投入使用，1代表使用，0代表不使用。此外，由問題特點可知樞紐港m的值必為1。

圖2 解的表示圖Fig. 2 The representation graph of the solution

2.4.2 初始和聲記憶庫的生成

為有效提高算法的搜索性能，考慮各港口集裝箱貨運需求量對船舶調配方案的影響，設計了基于問題特點的記憶庫生成策略，具體如下。

Step1：初始化算法參數及和聲記憶庫，輸入相關數據，令和聲數p=1，和聲列數i=1；

Step2：計算各港口在不同時段對集裝箱貨運需求量的總和，記為行向量HCL，轉至Step3；

Step3：計算HCL中的最大值，即為maxHCL，將HCL中各元素分別除以maxHCL，記為新行向量NHCL，轉至Step4；

Step4：若第i列對應的是港口序號，則轉至Step5；否則，轉至Step7；

Step5：若第i列對應的是樞紐港(港口m)，則第p個和聲個體第i列的取值為1；否則，轉至Step 6；

Step6：結合行向量NHCL確定第p個和聲個體第i列的取值，按行向量NHCL中取值的大小接受，轉至Step8；

Step7：隨機生成第p個和聲個體第i列的取值(0或1)，轉至Step8；

Step 8：若小于n×(G×m+1)，則令j=j+1，轉至Step4；否則，轉至Step9；

Step9：若p小于HMS，則令p=p+1，轉至Step4；否則，輸出初始和聲記憶庫HM。

2.4.3 新和聲產生策略

采用3種策略生成新和聲，分別為和聲微調、對全局最優(yōu)和聲微調以及隨機生成和聲。其中，和聲微調策略包括兩種，第1種是隨機選擇某局部片段進行+1或-1處理，如圖3，第2種是將全局最優(yōu)和聲的某片段嫁接至當前和聲個體中，如圖4，且這兩種策略的選擇受到參數全局優(yōu)化率的影響，取值在0.5與0.8之間；對全局最優(yōu)和聲微調同和聲微調1類似；隨機生成和聲同2.4.2節(jié)中的步驟類似。

圖3 和聲微調1Fig. 3 Harmonic fine-tuning 1

圖4 和聲微調2Fig. 4 Harmonic fine-tuning 2

2.4.4 和聲修復策略

不可行和聲的出現(xiàn)，主要有以下3種情況：① 前G×m×n列中樞紐港對應的元素值不為1，其余港對應的元素值小于0，以及最后n列的元素值超出[0,1]區(qū)間；② 各船舶未能按照第1次調度、第2次調度、第3次調度的順序進行調度；③ 船舶進行調度，而對應的船舶是否投入使用列為0，或者船舶未投入使用，卻進行船舶調度。針對這些問題，設計了以下和聲修復策略。

1)依次檢查所有列，若對應的為樞紐港序號，將取值不為1的列修復為1；若對應的為非樞紐港和非船舶是否投入使用列，將小于0的列修復為0；其余列取值若不在[0,1]區(qū)間，則隨機生成為0或1。

2)依次檢查所有列，對于某艘船舶，若第1次調度對應的列(除樞紐港)為0，則其余取值為0；否則檢查第2次調度對應的列，如果除樞紐港外，取值為0，則后面所有港口列取值為0,對應的船舶是否投入使用列取值為1。

2.4.5 相關約束處理

2.4.6 算法終止條件

以算法的迭代溫度達到終止溫度作為終止條件。

3 算例分析

3.1 算例描述

經營渤海內支線集裝箱運輸的S企業(yè)擁有7條支線船舶，負責班輪船舶A和B的集裝箱收集工作，將集裝箱由7個支線港向大連港集運。其中，班輪船舶A每周五上午4點到達大連港，船舶B每周日上午6點到達大連港，計劃開始時間為周一0點，計劃期為一周(24×7)h，A班輪集裝箱送往樞紐港的限制時間最遲為第100時，B班輪集裝箱送往樞紐港的限制時間最遲為第150時。

結合港口的地理位置分布，規(guī)定大連港為樞紐港，標號為8，各支線港標號為1～7，將港間運輸距離轉化為運輸時間，見表1。結合港口間運輸時間，可以確定船舶調度最小耗時為49 h，因此假設各船舶計劃期內最大調度次數為3次；由于存在甩貨情況，因此計劃期初在各港口有上計劃期未運輸的集裝箱，各支線港口期初和本計劃期總運輸需求量見表2；各支線船舶資料具體見表3。

表1 港間運輸時間Table 1 Transport time between any two ports h

表2 各港口貨運需求量、作業(yè)時間和集裝箱處理成本Table 2 Freight demand, operation time and container handling cost of each port

表3 船舶相關信息Table 3 Ship related information

設定算法參數為：和聲記憶庫大小30，初始溫度100 ℃，終止溫度1 ℃，降溫系數0.95，內循環(huán)迭代次數15，記憶庫概率0.95，和聲微調概率1(溫度30以上)、0.5(溫度30以下)，全局優(yōu)化率0.7。

3.2 方案有效性檢驗

根據調研，經營渤海內支線集裝箱運輸的公司主要有兩種不定期船舶調度方案，方案1為支線船沿著8-1-2-3-4-5-6-7-8順次掛靠，不可跳躍，船舶最大限度裝載，不考慮滯港情況；方案2為支線船舶結合港口不同時段的貨運需求進行跳躍掛靠，每次調度中最大限度裝載，不考慮滯港情況。對于方案1，由于其為不可跳躍掛靠，會出現(xiàn)當港口貨量很少也必須掛靠，造成時間的消耗和運輸成本的大幅增加，使總成本較高，因此筆者主要與方案2進行對比。

考慮6種規(guī)模的貨量，分別為原始數據的0.8倍、1倍、1.2倍、1.4倍、1.6倍和1.8倍。其中計劃期內各港口各時段的貨運需求量結合各港口的周需求量隨機產生，得到如表4的方案對比結果。

表4 方案結果對比Table 4 Comparison of different scheduling results

注：優(yōu)化率=(現(xiàn)實方案-本文方案)/現(xiàn)實方案服務率=限制時間內的運輸總量/班輪到達樞紐港前貨運需求量

由表4可知，在不同規(guī)模下，方案同現(xiàn)實方案的目標值平均相對優(yōu)化率為18.54%,方案的服務率也高于現(xiàn)實方案。這是由于班輪船期不同，當采取最大限度裝載時，會使得不滿足班輪船期要求的集裝箱占用了部分船舶容量，例如船舶到達某港口的時間超過較近班輪的船期，而根據裝載原則，卻可能裝載該類集裝箱，從而使本計劃期的服務率降低，造成較高的成本，而裝載時優(yōu)先滿足本次計劃期內兩艘班輪的需求，在此基礎上，如還有剩余容量才可能裝載下計劃期班輪的集裝箱，使得本計劃期服務率較高。且考慮滯港情況，使支線船舶得到充分利用。

以原始數據為例進行試驗，闡述依據模型和算法得出的優(yōu)化方案。利用和聲退火混合算法求解得總成本收斂結果見圖5，此時的總成本為488 330元，耗時28.544 405 s。配置船舶1、船舶3，調度方案為，船舶1：000001111111000101011101，船舶2:

101121011010022111321221。以船舶1的為例，調度方案如圖6。

圖5 最優(yōu)方案收斂Fig. 5 Optimal scheme convergence graph

圖6 船舶1調度方案示意Fig. 6 Ship 1 scheduling plan

4 敏感性分析

4.1 樞紐港船舶限制時間靈敏度分析

樞紐港船舶限制時間(即集裝箱送達樞紐港的限制時間)的變化會對總成本和服務率產生影響，為分析其影響，將限制時間分為5種情況，分別為T1、T2、T3、T4、T5，取值為原限制時間減20、減10、不變、加10、加18(計劃期為168 h，限制時間不超過計劃期)。不同限制時間下的總成本和服務率如圖7、圖8。

圖7 限制時間對成本的影響Fig. 7 Total cost under different time constraints

圖8 不同限制時間對服務率的影響Fig. 8 Service rate under different time constraints

可以看出，限制時間的放大，兩種方案的目標值都在降低，優(yōu)化率上升，服務率增加。這是因為當限制時間放大后，限制時間內到達各港口的集裝箱總量增加，同時支線船舶有更充足的時間進行調度，使得服務率提高；隨著服務率的增加，總營運成本降低，可視為集裝箱運輸量的增加帶來甩貨成本的減少量大于運輸成本和集裝箱處理成本的增加量，且不同限制時間下本文方案成本下降的比例大于現(xiàn)實方案，優(yōu)化率呈上升趨勢。

4.2 單位甩貨成本靈敏度分析

甩貨成本是由于干線班輪箱位利用率降低和客戶滿意度下降所造成的損失，客戶對企業(yè)的重要性以及企業(yè)對客戶服務水平的重視程度均會對單位甩貨成本造成影響。為了分析其影響，取初始數據的1倍、1.5倍、2倍、2.5倍進行試驗。不同單位甩貨成本下方案對比如圖9、圖10。

圖9 甩貨成本對總成本的影響Fig. 9 Total cost under different rejection costs

圖10 單位甩貨成本對服務率的影響Fig. 10 Service rate under different rejection costs

可以看出，隨著單位甩貨成本的增加，兩種方案的目標值和服務率均增加。這是由于隨著單位甩貨成本的增加，甩貨成本對總成本的影響增大，從而運輸更多的集裝箱；但現(xiàn)實方案的服務率水平較低，所以隨著單位甩貨成本的增加，總成本增加較大，使得本文方案相對現(xiàn)實方案的優(yōu)化率不斷提升；本文方案中隨著單位甩貨成本的增加，總成本小幅度增加，但獲得了服務率的提升。這表明航運企業(yè)在制定船舶調度方案時應在總成本和服務率之間尋求平衡，給出整體最優(yōu)的決策。

5 結 論

1)建立了基于不定期船舶的內支線配船與船舶調度模型，在樞紐港班輪船期和計劃期內各港口不同時段貨運需求已知的前提下，考慮營運成本和甩貨成本，有利于平衡營運成本和服務水平，提高企業(yè)的整體運營績效。

2)設計了和聲退火混合算法，包括初始記憶庫的生成、新和聲的產生以及和聲修復，有效提升了算法的搜索性能。

3)敏感性分析實驗表明，樞紐港船舶限制時間對總成本和服務率的影響較大，隨著限制時間的放大，總成本降低，服務率提高；單位甩貨成本的變化對總成本和服務率也會產生影響，隨著單位甩貨成本的增大，本文方案的總成本小幅度增加，服務率上升，相對現(xiàn)實方案的優(yōu)化效果越明顯。因此，航運企業(yè)應盡量放大限制時間，同時關注單位甩貨成本，做出有利于整體的最優(yōu)決策。

未來的研究可考慮多樞紐港、集送貨一體以及各港口集裝箱到達規(guī)律可變等因素，使該問題的研究更符合現(xiàn)實需求。