摘要: 针对远洋运输行业船舶承租人的现货配船问题,以快速地找出尽可能多的潜在的匹配方案,减少匹配误差为最终目标;从多属性匹配的思想出发,提出有效的属性描述方法、属性匹配损失惩罚的计算方法以及收益计算方法。借助启发式算法的灵活性、易于与业务特定相结合的优势,构建了对应的多属性约束模型,定义了合理的启发式规则,将各种约束分散在多个阶段考虑,又很好地限制了解空间规模,从而快速地寻求较佳匹配方案。
关键词: 远洋运输;多属性匹配;启发式
中图分类号:TP301·6 文献标识码:A 文章编号:1006-4311(2009)11-0068-04
0引言
伴随着商品市场的全球化发展,物流、运输行业也在快速的成长。在国际市场上,货物运输更多的依赖于海上运输,尤其是远洋运输。根据资料显示,目前全球大约有90%的货物是通过海洋运输实现的[1]。但是,时至今日,全球航运市场却已经趋于饱和,运力供过于求,竞争日趋激烈。同时,由于调配不均,航运企业在空载里程、空箱调配上的成本始终居高不下,惊人的额外支出已经导致绝大多数承运人的运营成本增长大大超出了收入增长。
根据德鲁里航运咨询公司估算,1999年全球集装箱运量约1.96亿TEU,其中空箱运量为 3 900万TEU,以平均200美元/TEU空箱调运费计算,班轮公司就要多支出78亿美元,实际运费只可能会更高[2]。再者,由于世界大宗散货贸易地理分布极不均匀,使不定期船运输航线空载里程相当高。据统计,目前世界不定期船运输航线空载率约占40%[3]。我国近年航运运力增幅较快,导致结构性运量不足,船舶平均空载率高达50%[4]。造成这些现象的重要原因在于航运信息不对称,缺乏对市场供求信息及时准确把握和优化决策分析。为此,要切实提高船舶利用率,降低空载距离,缩短船舶空载航行时间,就必须研制开发基于优化技术的决策支持系统。
基于优化技术的决策支持系统,尤其是船货匹配系统,使得根据现有的货物或船舶,船舶承租人可以迅速获取到大量的货物信息并选择最适合的船舶装运。这样,既可以充分发挥船舶运力,减少船舶的空载航行时间和等待时间,降低空载航程,还可以减少货物的滞留成本,从而在市场水平持续低迷、燃油成本大幅上涨的不利情况下保证收益水平。
在船货匹配业务中,船舶的运力描述和货物的运输要求都是多方位的,船舶与货物的装载匹配属于典型的多属性匹配。在多属性匹配机制中,存在两种典型的匹配方法:完全精确匹配方法和部分匹配方法[5]。启式算法的优点在于可结合行业特点灵活运用启发规则,将各种约束分解到不同的求解阶段考虑,使问题简化而又能求得较好解。
本文针对远洋运输行业的船货匹配,尤其是现货配船,分析了多属性匹配的算法,采用根据远洋运输行业的船货匹配特性和多属性匹配中的部分匹配方法定义启发式规则,快速地找出尽可能多的潜在的匹配方案,同时减少匹配误差,从而可以减少船的空载成本及货物的滞留成本,优化航次任务,为提高航次收益乃至航运企业的业绩提供有力的支持。
1问题描述及多属性匹配模型
1.1 现货配船問题描述
在船舶承租人的业务过程中,常出现因得到新的托运订单,而需要选择合适的船舶来执行订单要求的运输任务,此时,面临的就是现货配船的问题。尤其是,船舶承租人可能拥有不定期船,即没有固定的船期、航线,这类船舶执行航次任务时,由托运需求驱动,在船舶和货物类型吻合的基础上,根据托运货物的时间要求、港口要求等定船期、航线。在现货配船时,如果托运货物的重量或体积过大,超出了船舶的载重量或舱容,不能整票货全部装船时,应把部分货载退掉,用另外的船舶装载。即一批货物可以由一艘船舶装载,也可由多艘船舶共同装载。在本文中,一批货物分散装到多艘船上的前提是:货物的货运量,即体积或重量已经超出当前每一艘候选船舶的承载量,即舱容、载重;否则,一批只允许装在一艘船上。
对于现货配船的问题,将船舶数据作为候选的对象集合,而将货物的各个属性,包括类型、时间、港口、体积/重量等属性的要求作为约束,建立成本型的目标函数,从而依据定义好的启发式规则加以匹配。对于货物重量、体积超出船舶承载能力的部分,视为新的货物对象,参与匹配。
1.2 现货配船的多属性匹配模型
1.2.1 目标函数
现货配船问题,因货物数量确定,且毛收益固定;因此在选择合适的船舶承担运输任务时,追求的目标是:航次成本D最小。故选取属于成本型目标函数。
根据航次成本计算,现货配船的目标函数数学关系表示为:
minD=D1+D2+D3(1)
其中:D1——船舶租金;D2——燃油费用;D3——其他费用。
①船舶租金:
D1=H?鄢T(2)
其中:H——每天的租金;T——天数。
②燃油费用:
D2=■O■?鄢OP■(3)
其中:O■——每次加油数量;OP■——燃油单价。
③其他费用:D3=■d■(4)
其中:di——其他各种费用。
1.2.2 目标约束条件
在上述现货配船问题中,各参数属性关系如下:船为变量;货为值域;现货的空间、时间、类型、装卸方式、舱容载重量等对船属性的限制构成约束集合;亏舱最小、空载里程最小、航次成本最小为惩罚函数。
因为以货物为目标约束,则带时间窗的港口属性约束是唯一的;因而,对于船舶的出发港口属性仅限于当前位置对应的属性值,不考虑途中港口的可能性。
为了便于对模型进行描述,首先对相关的变量进行定义如下:
式(5)表示候选船舶v■能承载的货物类型必须包括当前匹配的目标货物c■的货物类型;式(6)表示获选船舶v■的带时间窗约束的港口属性p■在能满足目标货物c■带时间窗约束的港口属性p■要求时所导致的空载里程成本尽可能的小。港口属性的匹配损失用船舶空载里程与船舶空载油耗和燃油单价的乘积表示,即:D■=em■?鄢BCB■?鄢OP;其中, BCB■表示船舶空载航行的油耗,OP表示燃油单价。式(7)表示候选船舶v■的装载能力,包括载重能力和容量能力;在满足目标货物c■的装载需求,包括货物的重量和体积时,导致的船舶装载能力的损失尽可能小。在约束条件中,船舶非满载的损失效益D■表示为下式:
其中:△W表示船舶尚未被利用的载重;△S表示船舶尚未被利用的仓容。根据匹配的目标,在没能达到满舱满载的情况下,追求满舱不满载或满载不满舱,因此,△W和△S之一必定为0,不会导致重复计算。
■=∑S■∑W■表示该船舶已经装载的货物的平均货物积载因数。
■表示该船舶已经装载的货物的平均运价。按照国际惯例,计重货物是指每公吨的体积小于1.1328m■(40 ft 3)的货物,否则,按体积计费;因此,当■>1.1328m■/t时视为容积货物,按体积计算运费;当■<1.1328m■/t时视为重量货物,按重量计算运费[6]。
2基于解空间限制的启发式求解算法
现货配船的问题是要从船舶集合中找出满足约束的子集,因此,解空间限制的启发式算法的核心在于不断的缩减候选船舶集合的规模,从而,获取最终的满意解,如图1所示。
(1)求解步骤如下:
①类型属性(Type)匹配:遍历船舶集合,只保留允许装载的货物类型包括目标货物种类的船舶元素;
②带时间窗的港口属性(Port)匹配:遍历步骤①产生的结果集,对于货物的出发港口、时间窗与船舶的出发港口、时间窗匹配,以及货物的目的港口、时间窗与船舶的目的港口、时间窗进行匹配。
其中,港口属性的匹配采用非精确匹配,即对于船舶与货物的时间吻合,但港口有偏差,需要通过一定的空载里程来补足的,就产生:匹配损失惩罚=船舶空载里程的费用。
③体积与重量属性的匹配:因为体积和重量因素需要同时与承运船舶的装载能力(包括容量能力和载重能力)匹配,因此,这两个属性需要同时考虑。
从步骤②的结果集合中,选取可以同时满足体积和重量的船舶。如果集合为空,则转向步骤④;否则,直接进入步骤⑤;
④货物体积或重量超出船舶装载能力:经步骤③判断,因货物体积或重量超出可用船舶装载能力,因此采用货物分割方法运输,即一票货分到不同船舶运输。从步骤②的结果集合中选取组合方案:
∑Size of Vessel=Size of Cargo*SF∑Weigh to fVessel=Weight of Cargo
转向步骤⑥。
⑤获取最终结果集或非精确匹配解。根据满舱满载目标,在步骤③和步骤④的结果集中,查找船舶平均舱容系数■(步骤③的方案中平均舱容系数■=船舶的舱容系数μ)与目标货物的积载因数SF相等的元素,即为最终结果集,转向步骤⑥;如果没能找到■=SF的船舶,可以考虑满载不满舱或满舱不满载的船舶为非精确匹配解,转向步骤⑥。
⑥提出参考方案。计算步骤⑤的方案结果,将收益排序,向用户显示最终可供参考的方案。
(2)根据以上思路,利用代码设计的算法如下:
输入:目标货物的信息;
输出:被选择船舶的编号以及对应的航次净收益。
Step1 获取输入,初始化货物 Cargo c;
Step2 从数据库初始化候选的船舶数据 List of
Step3 遍历候选船舶,记录不满足类型约束、带时间窗的港口约束的记录
For eachV in vessels
(船舶始发港口对应的净载重 >= 货物在装船港对应的重量)
3结论
长期以来,远洋运输行业由于航运信息不对称,缺乏对市场供求信息及時准确把握和优化决策分析,导致严重的船舶空载率、货物运输不及时、运输质量不高。因此,需要有满足行业特定需求的船货匹配系统,使交易方可根据现有货物或船舶,迅速为货物选择最适合的船舶装运,以减少船舶空载航行时间和等待时间,降低空载航程,从而在市场水平持续低迷、燃油成本大幅上涨的不利情况下保证收益水平。
本文研究了满足远洋运输需求的船货匹配算法,快速找出尽可能多的匹配方案,以减少匹配误差为目标,从多属性匹配思路出发,提出有效的属性描述方法、属性匹配损失惩罚计算方法及收益计算方法。借助启发式算法灵活性、易于与特定业务结合的优势,为常见现货配船业务,构建了多属性约束模型,定义了合理的启发式规则,将各种约束分散在多个阶段考虑,又很好地限制求解空间规模,可快速求解多属性匹配问题。
参考文献
[1]卜祥智:《基于收益管理的集装箱班轮舱位分配随机模型研究》[D];《西南交通大学经济与管理学院》2005:10。
[2]任昕:《海运集装箱空箱分派优化模型研究》[D];《西南交通大学经济与管理学院》2007:5。
[3]刘建林、施欣:《不定期船运输市场优化决策支持系统构建研究》[J];《交通运输系统工程与信息》2006(04):76-82。
[4]交通部珠江航务管理局:《节能减排,航运先行[J];2008:21-22。
[5]孟兆会、段富:《基于物流信息系统的客户需求算法分析》[J];《电脑开发与应用》2008(04):33-35。
[6]李治平:《货运技术》[M];新世纪出版社,1992:64-66。