基于航次串理论的深港珠澳航线客船调度优化*

丁 涛 王 钰 王 帆

(武汉理工大学交通学院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个往返班次的运营.优化结果可以有效节约船公司的运力、提高船舶利用率，为航线经营者在实际经营决策中提供参考.