基于航次串理論的深港珠澳航線客船調度優化*

丁 濤 王 鈺 王 帆

(武漢理工大學交通學院1) 武漢 430063) (長江航運發展研究中心2) 武漢 430014)

0 引 言

水上客運是粵港澳大灣區綜合交通體系的重要組成部分，深港珠澳水上客運航線憑借其班次密集、通關簡便的優勢[1]，成為粵港澳大灣區水上客運眾多航線中客流最多、盈利狀況較好的航線.但同時，面對珠三角高度發達的公路和鐵路運輸的競爭，深港珠澳水上客運必須在運營上不斷優化班期安排，合理調度船舶，才能保持其競爭優勢贏得良好的發展前景，助力港珠澳大灣區綜合交通體系的發展.

針對船舶調度和班期優化，國內外多位學者已進行了卓有成效的研究.高秋穎[2]在計算班輪航線配船時通過人為調整往返航次時間使其成為發船間隔的整數倍.許歡等[3]從低碳經濟的角度進行研究，將總的航行時間在各個航行區段進行有效分配，尋求船舶在各相鄰掛靠港之間的最優航速，使得船舶在航線上各運輸區段的燃油消耗量和碳排放量最少.陳夢[4]采用線性規劃模型對班輪航線配船進行優化，以船公司在規劃期內的總利潤為目標函數，航運市場處于上行期時，在模型中增加租船費用，航運市場處于下行期時，相應地增加船舶閑置費用.司羽[5]研究了集裝箱內支線船舶配置和調度問題，將干線大船甩貨造成的損失計入內支線船舶營運成本，以總成本最小為目標函數構建了非線性規劃模型，并為模型設計了和聲退火算法.Wang[6]在研究船舶調度問題時，除了選取船舶可達性、航次密度、船舶裝載量等約束條件外，還考慮了了支付延遲、空箱送回和船舶回駛等條件.Maxim等[7]采用非線性規劃模型研究了易腐貨物班輪運輸船期表安排問題，特別考慮了貨物腐爛因素對船期表安排的影響.Christiansen[8]將給燃料供應船舶安排船期表看作是帶時間窗的車輛路徑問題，并討論了有新的船舶插隊或有船舶不能嚴格執行計劃時的情況.

1 問題描述

1.1 航線概況

深、港、珠、澳四城七客運碼頭間共有14條水上客運航線，見圖1，可分為交通航線和機場航線兩類，航線網絡上每日運行超過200個客運班次.

1.2 客運航線班期與營運成本關聯度

班期與成本的關系主要體現在：①合理的班期安排可以帶來緊湊的船舶運用計劃，有效提高船舶利用率，降低航線單船成本，減少船舶使用艘數，降低航線投資;②合理的班期安排照顧到乘客出行需求特點，提高上座率，增加營運收入;③科學的班期安排降低了營運風險，減少了營運風險帶來的不必要支出.

以深圳蛇口—澳門外港航線為例說明班次安排對每日運營成本的影響.根據歷年班次安排和客流量數據，計算得不同班次安排下單位成本，二者之間關系見圖2.

圖2 單位成本與每日班次數關系

由圖2可知，隨著班次數增加，船公司單位營運成本先下降再增加.每日班次數在8～11班時，單位成本隨班次數增加而下降，說明在這一區間內，班次增加對客流的吸引作用更顯著.而當班次超過11班，隨著班次數增加，單位成本也增加，說明班次超過11班時，繼續增大班次密度對客流的吸引作用不大，增加的客流帶來的收入將不能彌補班次增加帶來的營運成本增加.

因此，對于班次數和船務公司經營成本、收入之間的關系不能簡單地來看待，決定班次數的依據也不能單純從成本或收入角度進行考慮.

1.3 航次串概念

“航次串”即按照一定順序排列的航次[10-11]，對于客運網絡航線上的船舶來說，船舶要執行的不只是一個航次，而是一系列能夠銜接的航次運輸任務，見圖3.航線網絡上A,B,C三個港口間的六個航次可以首尾相連，成為一條航次串，所包含的六個航次只需指派給一艘船舶執行.

圖3 航線網絡上一條航次串

引入航次串的概念后，航次分配給船舶的過程便轉化為把航次串分配給船舶的過程，問題復雜性大大降低.

1.4 問題考慮因素

完整的船舶調度問題包括航線網絡確定、班期安排、船型配置、航次指派等問題.本文主要研究的是在既定航線網絡和船型下的班期安排和航次指派問題.

從企業經營的角度來看，影響客運航線班期安排的因素可分為外部因素和內部因素兩類.外部因素包括地區經濟發展現狀及航線客流預期、航道自然條件、港口環境、競爭對手等;內部因素則是企業內部經營相關因素，如船隊規模、企業發展經營戰略、企業其他配套服務能力等.兩類因素都是船舶調度問題所需考慮的.

2 模型建立

2.1 基本假設

為了便于問題研究，做出以下基本假設.

1) 假設航線網絡不變，使用船型已知.

2) 假設航線每次往返航行時間相同.

3) 假設船舶均返回始發港過夜.

2.2 班期優化模型構建

2.2.1變量和參數定義

定義以下集合 運營時段集合T，將1 d劃分為若干個運營時段 時段t∈T；航線集合R，航線r∈R.

參數Qdr為航線r上每日最大客流量；Qtr為時段t內航線r上的平均客流量；B為船舶載客量；cr為船舶在r航線上平均單航次營運成本，qtmax為t時段內航線網絡上的最大發班數；Δt為時段t的長度；ωr為航線r上每位乘客等待時間轉換為損失的乘客等待費用；λ1為船公司船舶運用成本費用加權系數；λ2為乘客等待損失成本費用加權系數，且λ1+λ2=1.

決策變量qtr為時段t航線r上的班次數.

2.2.2模型構建

航線網絡上開行的班次越多，變動成本就越大，班期進行優化的目標就是盡可能地減小每日營運的變動成本.

(1)

(2)

qtrB≥Qtr

(3)

(4)

qtr∈N*

(5)

式(1)為目標函數，表示船公司每日經營變動成本最小；式(2)為運量約束，航線上的每日客運任務必須完成；式(3)也為運量約束，不僅要完成各航線上每日客運任務，航線上分時段客運任務也必須完成；式(4)為運力約束，t時段內的發班數不能超過航線網絡上允許的最大發班數；式(5)為整數約束：各時段內各航線上的發班數量為整數.

2.3 航次指派模型構建

2.3.1變量和參數定義

定義以下集合 航線集合R，航線r∈R；航次集合V，航次v∈V；航次串集合I，航次串i∈I；種子航次集合E，種子航次e∈E；船舶集合S，船舶s∈S.

決策變量：xi為航次串i是否被選中，若選中，則xi=1，否則為0；aiv為航次串i是否包含航次v，若包含，則aiv=1，否則為0；xsi為船舶s是否執行航次串i，若執行，則xsi=1，否則為0.

2.3.2航次數據格式化

根據班期安排得到航次數據之后，首先進行航次數據格式化，見表1.

表1 航次數據格式化

同一個航次串中相鄰的兩個航次要滿足兩個方面的要求：時間上不允許任何重合，前一個航次的到達時間和后一個航次的出發時間之間的間隔要大于船舶在港的最短停靠時間；在空間上相互銜接，前一個航次的到達港口和后一個航次的出發港口必須相同.

2.3.3航次串生成

航次數據格式化之后，按照以下步驟進行航次串的生成：

1) 從所有航次集合V中選取種子航次集合E，種子航次即船舶執行的第一個航次，一般在各航線上出發時間較早的航次中進行選擇.開始時航次串集合P=Ф.

2) 將第i個種子航次ei放入集合P中，記為Pi(0)，并在V中搜索能夠與Pi(0)相連接的航次，放入P中并記為Pi(1)，輸出Pi(1)，再在V中繼續搜索能與Pi(1)相連接的航次.

3) 循環搜索，直至在V中找不到能與Pi(k)相連接的航次.

4) 在P中刪掉Pi(k)，繼續在V中搜索能與Pi(k-1)相連接的航次，重復3)直到k=0，令i=i+1，搜索下一個種子航次.

5) 當i=E時，搜索完畢，生成所有航次串.

2.3.4航次串篩選

經過上述過程，生成了所有的可能的航次串.在運營中，船務公司希望用最少的航次串去覆蓋所有的航次，也就是所運營的航線網絡需要的船舶數量最少.

采用如下模型對航次串進行篩選.

(6)

(7)

?i∈N*

(8)

式(6)為目標函數，表示所選用的航次串最少；式(7)保證了選中的航次串覆蓋了所有航次.

2.3.5航次串分配

經過航次串的篩選，已經得到了航次串的最優組合形式，接下來要為每一個航次串分配一艘具體的船舶去執行，于是構建航次串的分配模型.本文將固定成本中占比最大的船舶折舊納入模型主要考慮因素，并以船公司每日經營利潤最大為目標函數.

構建數學模型如下.

(9)

(10)

(11)

式中：Z為所需的航次串數量；Cr為航線r上執行票價；Ps為船舶s的造價；csi為船舶s執行航次串i所需花費的成本費用；θ為船舶折舊殘值，取10%；L為折舊年限，取20年.

式(9)為在分配航次串時以船公司獲得純利潤最大，式(10)保障了每艘船舶最多執行一個航次串，式(11)保障了每個航次串有且只有一艘船舶執行.

至此，客運航線班期優化和航次串指派模型構建完成.

3 模擬計算和結果分析

3.1 參數選擇

該公司使用8艘客運船舶經營著深圳蛇口—澳門外港、深圳蛇口—香港港澳、深圳蛇口—香港海天、深圳福永—香港海天碼頭四條航線.目前，該公司在四條航線上每日安排37個班次，每日營運變動成本約25.3萬元.各航線參數見表2.

表2 X公司航線參數

船舶在各航線上均安排簡單往返航次，即到達目的地后立即組織上下客返回，每次碼頭上下客作業時間為20 min.

八艘船舶客位數均在280人左右，為計算方便，取B=280，船舶造價及各艘船舶在各航線上單航次變動成本見表3.

表3 X公司船舶參數

3.2 優化結果

借助LINGO軟件，通過分支定界法對優化模型進行計算求解，得到各航線上各營運時段內的發班數，見表4.

表4 各航線每日發班數

不過，雖然求解出的發班數是整數，但由此確定的發班間隔卻不一定是整數，為便于營運，需人為再進行調整.

將班期優化模型確定的35個往返航次數據格式化后，共可生成54條航次串，篩選之后僅需6條航次串便可覆蓋所有航次.借助LINGO軟件利用分支定界法進行計算，6條航次串分別指派給2,4,5,6,7,8號船舶執行，X船公司現有的1,3號船舶并未指派航次串.得到帶船舶調度計劃的船期表見表5.

表5 帶航次指派的完整班期表

3.3 結果分析

受粵港澳大灣區日趨完善的道路和軌道交通體系影響，深港珠澳水上客運客流在近年來趨于穩定，略有下降.與該公司現行班期表相比，優化結果在深圳蛇口—澳門外港、深圳蛇口—香港海天兩條航線上每日減少一個班次，其余航線班次數量與現狀相同.在船舶運用方面，通過“航次串”篩選和指派，僅需6艘船舶就可完成網路航線上每日35個班次的運輸任務，減少2艘船舶使用，每艘船舶執行4～7個班次，船舶運用率有所提高.在該優化方案下，船舶平均每日航行變動成本約為17.4萬元，可節約30%航行變動成本.

4 結 論

1) 航運企業經營成本和開行的班期數量關系密切，但二者并非簡單線性關系，單位經營成本隨著班期數的增加先下降后上升.

2) 引入“航次串”理論后，只需將篩選出的航次串分配給對應船舶去執行，即可得到船舶調度方案，簡化了在多港口間執行多個航次的船舶調度問題.

3) 優化結果表明，在完成運輸任務并使獲利最大的前提下，X公司經營的4條航線僅需6艘客船便可完成每日35個往返班次的運營.優化結果可以有效節約船公司的運力、提高船舶利用率，為航線經營者在實際經營決策中提供參考.