一种基于禁忌搜索算法的散货船船货双边匹配模型

苏 鑫

(中远海运散货运输有限公司， 天津 300010)

0 引 言

不定期船运输方式在世界海运货物运输中占有重要地位。据统计，目前世界上不定期船运输航线的船舶空载率约为40%。由于船货信息不对称和缺少运营决策工具的支持，主要货源的地理位置分布不均匀，大宗散货贸易运输的船舶空载率较高。很多航运企业都在尝试通过现代化的经营管理手段进一步提高船舶的利用率，缩短船舶空载航行时间和空载航程。

船货匹配属于典型的多属性匹配问题。在实际的船货匹配操作中，需考虑船舶运力的基础信息、货物运输的实际要求和挂靠港口的注意事项等内容。根据黄兴文所述航次方案优选分析因素，影响散货运输的属性主要有：

1) 货物属性，包括种类、体积、重量、运费税和佣金等；

2) 船舶属性，包括吃水、夏季载重量、舱容、运河载重量、航速油耗和预估每日费用等；

3) 港口属性，包括港口水深、泊位分类、装/卸货作业效率、港口里程和港口使费等；

4) 路径因素，包括船舶预空位置、加油港选择和航线设计等，具体的货物运输路径由承运人控制。

禁忌搜索(Tabu Search，TS)算法是一种智能优化算法，在组合优化和生产调度等方面得到了广泛应用。TS算法是通过扩展局部邻域搜索模拟人类智力过程，实现全局逐步寻优的算法。该算法使用禁忌表避免出现迂回搜索的问题，借助藐视准则解决优良状态被禁忌的问题，确保探索的多样化和有效性，实现全局优化的目标。

尽管当前有关匹配方法的研究已有很多，但满足远洋贸易运输行业需求的船货匹配方法还比较少。本文在已有研究的基础上,研究复杂场景下散货运输的最优决策问题，选取船货双边匹配案例进行建模，以最小化整体航次时间成本为最终目标，解决多票货物与多艘船舶的匹配问题。

1 船货匹配模型和复杂场景概述

船货匹配属于多属性匹配。散货船运输是一种不定船期的航次货物运输，根据航次任务的需求制订航次计划，综合考虑执行航次任务的船舶情况、货物基本信息、货物特殊运输要求、装/卸货港口的实际运营能力、航线是否途经运河、空载/满载航行里程和燃油消耗等内容。根据以往的研究成果，本文所述船货匹配模型用到的关键数据集包括船盘、货盘和港口里程，具体的数据集属性见表1。

表1 船货匹配模型关键数据集属性

简单场景下的船货匹配模型主要包括以货定船和以船定货2种，其中：以货定船是指为确定的货物(已知信息包括货量、货种信息、装/卸货时间、装/卸货港口和运费等)选取合适的执行航次任务的船舶；以船定货是指挑选合适的货物，由指定的船舶完成航次任务。试验分析中，选取2项关键成本费用(燃油费和港口使费)进行研究。

1) 在以货定船模型中，在运费收入固定的情况下追求的是航次成本最低，以货定船的成本目标函数为

=+

(1)

式(1)中：为运输成本；为燃油费；为港口使费。

2) 以船定货模型相对以货定船模型需考虑不同的收入变动，为指定船舶匹配合适的货物，追求净利润最大化，的计算公式为

=-(+)

(2)

式(2)中：为运费。

以上2个模型适用于简单场景下的船货匹配，无法满足复杂场景下的多艘船舶与多票货物的双边匹配要求。

在实际应用这2个模型过程中会出现船货匹配冲突的情况，下面通过一个案例进行说明(船舶和货物信息分别见表2和表3)。对表2中的船舶执行以船定货操作，通过模型计算发现为它们匹配的最优货物为同一票货物M。由表2可知，存在竞争的可执行航次任务的船舶的基本情况类似，主要区别在于船舶的预空港口和预空时间不同。简单地通过以船定货模型为船舶V1、V2、V3和V4求解最优匹配货物已无法满足实际决策要求，需借助新的匹配模型解决此类问题。

船货双边匹配是一种复杂场景下的匹配问题。以货定船和以船定货2种模型能解决针对1票特定货物从众多候选船舶中选取最优船舶和为指定船舶挑选最大利润货物的问题。在实际业务操作中，存在一种复杂场景，即：业务人员将船舶信息和货物信息录入系统之后，不会立即执行匹配操作，而是在新的匹配对象录入之后再进行区域性船货匹配操作。系统中会存在一定数量的未配载船舶和待匹配货物，需依靠船货双边匹配模型，从充分运用船舶运力、减少船舶空载航行时间和降低货物滞留成本的角度充分挖掘潜在的机会，更好地为业务人员提供决策支持。

表2 执行“以船定货”存在冲突的船舶列表

表3 执行“以船定货”存在冲突的船舶最优匹配货物信息

决策偏好决定双边匹配的优化目标。从船舶所有人的角度考虑，优化目标包括最小化船舶航行距离和最小化船舶最长完工时间；从货主的角度考虑，优化目标为最小化货物等待时间；从整体的角度考虑，优化目标包括最大化船货匹配订单数和最大化经营收益等。此外，还有更加个性化的决策偏好，例如大客户的货物优先匹配和考虑船位价值的船舶摆位等。在激烈的航运市场竞争环境中，基于决策偏好进行高效、准确的船货双边匹配是保证船舶所有人盈利的关键基础，对进一步提高货主的满意度和提升航运服务水平具有重要意义。

2 基于TS算法的船货双边匹配模型

本文借鉴经典的带时间窗车辆路径问题(Vehicle Routing Problem with Time Windows，VRPTW)的思想解决船货双边匹配问题，利用TS算法求解组合最优化问题。

TS算法是一种智能化的组合最优化算法。该算法借助禁忌技术，能有效避免因邻域搜索而陷入局部最优的窘境，通过禁忌表记录已取得的局部最优解和取得局部最优解的过程，达到在下一次搜索时跳出局部最优解的目标。TS算法的设计核心包括禁忌对象、禁忌长度、邻域结构、评价函数、候选集、特赦规则和终止规则。表4为本文提出的基于TS算法的船货双边匹配模型详细信息。

表4 基于TS算法的船货双边匹配模型详细信息

本文基于开源框架Open TS(Open Tabu Search)对模型进行二次开发，求解船货双边匹配问题。在搭建船货双边匹配模型过程中，重点将船货匹配的特定问题转换为通用VRPTW问题，从而利用Open TS求解最优匹配组合。表5为Open TS的关键模块和船货双边匹配对应功能实现。下面以具体问题为例阐述基于Open TS求解VRPTW问题的原理，相关说明见图1，其中:r1和r2为2个队列;方框表示起点和终点。每个队列对应1艘船舶，队列中每个圆圈的先后顺序代表船舶执行不同载货任务，1个圆圈代表1项装/卸货任务。r1的执行顺序为4→1→9→2→3；r2的执行顺序为7→8→5→11→12。当前的船货双边匹配关系认为是Open TS中的一个解决方案(Solution)，经过TS的迭代发现，r1中的4与r2中的7交换执行任务有助于提高整体收益，此时产生了1个移动动作(ComplexMove)。经过1个移动动作之后，r1的执行顺序为7→1→9→2→3，r2的执行顺序为4→8→5→11→12。不断地进行迭代搜索，直至寻找到整体最优的匹配方案。

表5 Open TS的关键模块和船货双边匹配对应功能实现

图1 基于Open TS求解VRPTW问题的原理说明

3 算法设计和算例分析

3.1 基于TS的船货双边匹配算法设计

本文提出的算法侧重于解决多艘船与多票货物在执行以船定货或以货定船操作过程中存在的最优匹配冲突问题，从最小化时间成本函数的角度求解船货双边匹配问题。匹配算法的应用要求和实施步骤如下。

1) 应用要求：

(1) 同一票货物只会配载到1艘船上。若有1票货物装多艘船的需要，提前进行货物拆分操作，将该情况视为多票货物配载处理。

(2) 若执行航次任务的船舶提前抵达装货港口,需进行等待;若执行航次任务的船舶提前抵达卸货港口,无需等待，直接进行卸货作业即可。

(3) 暂时不考虑货物在装/卸货港口的作业时间。

(4) 船舶必须按货物的受载时间抵达装/卸货港口。

2) 实施步骤：

(1) 为船盘中的每艘船执行以船定货操作，生成按利润最大化倒序排列的货物信息列表，汇总待匹配货物信息，生成待匹配的货盘；

(2) 按船货匹配利润最大化的原则将货盘中的货物依次分配到各船上，生成初始可行解；

(3) 执行TS算法，求解最优的船货双边匹配方案。

在迭代搜索中，移动动作设计为将1票货物M从A船移动到B船时，1个动作会被分为2步执行。第一步会将货物M从A船已有的执行计划中删除，删除的位置有3种可能(队列头部、队列尾部和队列中间)；第二步会将货物M插入B船现有的执行任务中，插入的位置有4种可能(队列为空、队列头部、队列尾部和队列中间)。计算执行动作之后引起成本目标函数发生变化。采用TS算法，不断更新最优解的匹配方案。

3.2 船货双边匹配算例分析

选取5艘船进行以船定货操作，按最大利润货物优先配载的原则初始化船舶运输任务，初始化的船货双边匹配方案见表6,其中“初始运输任务计划”一列中的数字为货物编号。以船舶V1为例，其运输任务计划包含5票货物(20、24、31、50和53)，5艘船的初始运输任务计划共包含12票货物。执行TS算法，经过1 000次迭代，最优解被更新7次，表7为历次更新最优解时船货双边匹配方案的变化情况，其中“船货双边匹配方案”一列中的数字为货物编号。对比第1次更新后的匹配方案与初始化的匹配方案可发现，V1原有的31号货物被挪动到了V3执行。经过数次更新，算法最终得到收敛，得到了最优解，第6次更新与第7次更新的最优匹配方案相同。表8为历次更新最优解时关键指标变化情况，从目标函数值、总收入和净利润的维度展示了数次更新中相关指标的变化情况。 随着搜索的不断进行，目标函数值不断减小，从38.91减小至32.89。本文提出的船货双边匹配模型的目标函数设计包含航行时间成本、停时成本和违反时间窗口成本，具体情况参考表4中有关评价函数的描述。

表6 初始化的船货双边匹配方案

表7 历次更新最优解时船货双边匹配方案的变化情况

表8 历次更新最优解时关键指标变化情况

3.3 船货双边匹配方案的利润计算

一次解更新生成的双边匹配方案的利润计算可拆分成多个单票货物与指定船舶匹配之后的利润计算。以表7中第7次更新生成的方案关于船舶V2的货物运输任务为例，V2的配载计划为74→77→79→80。已有研究支持单票货物与指定船舶匹配之后的利润计算。首先计算V2运输74号货物的利润，74号货物最终的卸货港口是执行77号货物运输任务的起始预空港口；以此类推，直至V2完成所有货物运输任务，计算该船完成所有货物运输任务之后产生的利润。以此类推，对所有船舶(V1、V2、V3、V4和V5)执行运输任务之后产生的利润求和，将所得结果作为此次更新方案的最终利润。

基于保护商业机密考虑，采用统一标识表示总收入，采用标准量化处理净利润，以初始解的净利润为参照。每次更新最优匹配方案时，货物在不同船舶的运输计划中挪动，船舶不会拒绝某票货物的配载服务，因此整体收入保持不变。观察净利润指标的变化情况，随着最优匹配解的更新，净利润先下降后升高。出现净利润下降现象的原因是目标函数更侧重于时间和违规惩罚(例如超载、违反时间窗口要求)，净利润的计算与目标函数直接相关，但还需考虑不同船舶空载/满载航行时的耗油量区别。经过TS的不断更新迭代，净利润最优解在初始解的基础上提升了5%，进一步验证了本文提出的船货双边匹配模型的有效性。

4 结 语

本文针对散货运输的复杂业务场景构建了船货双边匹配模型，根据多属性匹配的思想提出了考虑货物受载期、空载/满载航行距离、港口使费和燃油成本等因素的损失惩罚计算方法和收益计算方法，快速求解潜在匹配方案，实现最优船货双边匹配。后续可进一步对该模型进行改进，例如：

1) 目前船抵达装/卸货港口的时间窗口约束采用的是硬时间窗口约束，即若运输任务不能在规定的时间内完成，则直接舍弃当前方案。该约束条件过于严苛，调整决策偏好接受软时间窗口，能发现更多潜在高利润方案，需由业务人员根据经营管理需要调整评价函数。

2) 对评价函数进行优化设计和丰富完善。本文提出的船货双边匹配评价函数侧重于航行时间和硬时间窗口约束，未来可结合业务决策关注的重点，进一步完善评价函数的设计内容。