基于航次串理論的深港珠澳航線客船調(diào)度優(yōu)化*

丁 濤 王 鈺 王 帆

(武漢理工大學(xué)交通學(xué)院1) 武漢 430063) (長江航運(yùn)發(fā)展研究中心2) 武漢 430014)

0 引 言

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

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

1 問題描述

1.1 航線概況

深、港、珠、澳四城七客運(yùn)碼頭間共有14條水上客運(yùn)航線，見圖1，可分為交通航線和機(jī)場航線兩類，航線網(wǎng)絡(luò)上每日運(yùn)行超過200個(gè)客運(yùn)班次.

1.2 客運(yùn)航線班期與營運(yùn)成本關(guān)聯(lián)度

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

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

圖2 單位成本與每日班次數(shù)關(guān)系

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

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

1.3 航次串概念

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

圖3 航線網(wǎng)絡(luò)上一條航次串

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

1.4 問題考慮因素

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

從企業(yè)經(jīng)營的角度來看，影響客運(yùn)航線班期安排的因素可分為外部因素和內(nèi)部因素兩類.外部因素包括地區(qū)經(jīng)濟(jì)發(fā)展現(xiàn)狀及航線客流預(yù)期、航道自然條件、港口環(huán)境、競爭對手等;內(nèi)部因素則是企業(yè)內(nèi)部經(jīng)營相關(guān)因素，如船隊(duì)規(guī)模、企業(yè)發(fā)展經(jīng)營戰(zhàn)略、企業(yè)其他配套服務(wù)能力等.兩類因素都是船舶調(diào)度問題所需考慮的.

2 模型建立

2.1 基本假設(shè)

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

1) 假設(shè)航線網(wǎng)絡(luò)不變，使用船型已知.

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

3) 假設(shè)船舶均返回始發(fā)港過夜.

2.2 班期優(yōu)化模型構(gòu)建

2.2.1變量和參數(shù)定義

定義以下集合 運(yùn)營時(shí)段集合T，將1 d劃分為若干個(gè)運(yùn)營時(shí)段 時(shí)段t∈T；航線集合R，航線r∈R.

參數(shù)Qdr為航線r上每日最大客流量；Qtr為時(shí)段t內(nèi)航線r上的平均客流量；B為船舶載客量；cr為船舶在r航線上平均單航次營運(yùn)成本，qtmax為t時(shí)段內(nèi)航線網(wǎng)絡(luò)上的最大發(fā)班數(shù)；Δt為時(shí)段t的長度；ωr為航線r上每位乘客等待時(shí)間轉(zhuǎn)換為損失的乘客等待費(fèi)用；λ1為船公司船舶運(yùn)用成本費(fèi)用加權(quán)系數(shù)；λ2為乘客等待損失成本費(fèi)用加權(quán)系數(shù)，且λ1+λ2=1.

決策變量qtr為時(shí)段t航線r上的班次數(shù).

2.2.2模型構(gòu)建

航線網(wǎng)絡(luò)上開行的班次越多，變動(dòng)成本就越大，班期進(jìn)行優(yōu)化的目標(biāo)就是盡可能地減小每日營運(yùn)的變動(dòng)成本.

(1)

(2)

qtrB≥Qtr

(3)

(4)

qtr∈N*

(5)

式(1)為目標(biāo)函數(shù)，表示船公司每日經(jīng)營變動(dòng)成本最小；式(2)為運(yùn)量約束，航線上的每日客運(yùn)任務(wù)必須完成；式(3)也為運(yùn)量約束，不僅要完成各航線上每日客運(yùn)任務(wù)，航線上分時(shí)段客運(yùn)任務(wù)也必須完成；式(4)為運(yùn)力約束，t時(shí)段內(nèi)的發(fā)班數(shù)不能超過航線網(wǎng)絡(luò)上允許的最大發(fā)班數(shù)；式(5)為整數(shù)約束：各時(shí)段內(nèi)各航線上的發(fā)班數(shù)量為整數(shù).

2.3 航次指派模型構(gòu)建

2.3.1變量和參數(shù)定義

定義以下集合 航線集合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是否執(zhí)行航次串i，若執(zhí)行，則xsi=1，否則為0.

2.3.2航次數(shù)據(jù)格式化

根據(jù)班期安排得到航次數(shù)據(jù)之后，首先進(jìn)行航次數(shù)據(jù)格式化，見表1.

表1 航次數(shù)據(jù)格式化

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

2.3.3航次串生成

航次數(shù)據(jù)格式化之后，按照以下步驟進(jìn)行航次串的生成：

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

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

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

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

5) 當(dāng)i=E時(shí)，搜索完畢，生成所有航次串.

2.3.4航次串篩選

經(jīng)過上述過程，生成了所有的可能的航次串.在運(yùn)營中，船務(wù)公司希望用最少的航次串去覆蓋所有的航次，也就是所運(yùn)營的航線網(wǎng)絡(luò)需要的船舶數(shù)量最少.

采用如下模型對航次串進(jìn)行篩選.

(6)

(7)

?i∈N*

(8)

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

2.3.5航次串分配

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

構(gòu)建數(shù)學(xué)模型如下.

(9)

(10)

(11)

式中：Z為所需的航次串?dāng)?shù)量；Cr為航線r上執(zhí)行票價(jià)；Ps為船舶s的造價(jià)；csi為船舶s執(zhí)行航次串i所需花費(fèi)的成本費(fèi)用；θ為船舶折舊殘值，取10%；L為折舊年限，取20年.

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

至此，客運(yùn)航線班期優(yōu)化和航次串指派模型構(gòu)建完成.

3 模擬計(jì)算和結(jié)果分析

3.1 參數(shù)選擇

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

表2 X公司航線參數(shù)

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

八艘船舶客位數(shù)均在280人左右，為計(jì)算方便，取B=280，船舶造價(jià)及各艘船舶在各航線上單航次變動(dòng)成本見表3.

表3 X公司船舶參數(shù)

3.2 優(yōu)化結(jié)果

借助LINGO軟件，通過分支定界法對優(yōu)化模型進(jìn)行計(jì)算求解，得到各航線上各營運(yùn)時(shí)段內(nèi)的發(fā)班數(shù)，見表4.

表4 各航線每日發(fā)班數(shù)

不過，雖然求解出的發(fā)班數(shù)是整數(shù)，但由此確定的發(fā)班間隔卻不一定是整數(shù)，為便于營運(yùn)，需人為再進(jìn)行調(diào)整.

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

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

3.3 結(jié)果分析

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

4 結(jié) 論

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

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

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