摘要： 针对散货航运市场的航次方案优选问题，使得公司能够在自身的能力约束下获得最大收益，最终目标是快速地在潜在的商业机会中找出最优的航次方案组合。通过调研定义了合理的航次收益、成本定量预估方法，在此基础上结合背包问题构建了航次方案优选模型，并进行改进，从而快速地求解航次方案优选问题, 提高企业的核心竞争力。
Abstract: Focusing on the research of method of optimal voyage selection to meet the specific needs of bulk cargo shipping, this paper analyzes how three factor of cargo, vessel and port influence the decision qualitatively and quantitatively. Then based on the knapsack problem, we create the corresponding optimal voyage selection model and define reasonable constraint rules to accelerate getting final results.
关键词： 航次预估；背包问题；航次优选；投资组合
Key words: Voyage Estimate；Knapsack Problem；Optimal Voyage Selection；Investment Portfolio
中图分类号：U69 文献标识码：A文章编号：1006-4311（2011）05-0221-02
0引言
全球每年的海运量中，除集装箱货和成组货等干杂货由定期船运输外，其余75%～80%的货物均由不定期船运输，其主要的运输对象为对运费负担能力低，对运输速度和运输规则性要求不严的大宗散货。而且近几年来，散货需求不断增长，因此散货运输的市场前景大好。以铁矿石为例，1999至2009年海运量翻了一番多，而且维持着持续快速的增长。然而随着国际经济的发展，全球经济的一体化，以及国际干散货航运市场的规模不断扩大，带来了船舶散货运输业的竞争不断加剧。而且经济的波动、世界政治事件、自然因素等都会影响到国际散货航运市场的行情[1]。航运企业的经营风险大大增加。另一方面，因为散货运输从本质上看散货航运市场多属于不定期船市场中的航次租船，其在营运时，没有固定的航线，而是根据租船合同中约定的时间、地点和所承租货物不同不断变更。航次租船是租船市场上最为活跃，且对运费水平的波动最为敏感的一种租船方式[2]。所以各航运企业都试图通过现代化的经营管理策略和先进的预测方法来提高航次经济性，以快速应对散货运输市场的变化，主要包括进行航次估算、先进的航次优选、以及合理规避运价风险等措施。本文以航次估算的结果为基础，基于背包算法构建了航次优选模型，大大提高散货运输的决策效率。
1问题描述及航次预估
船舶承租人业务始于船舶信息与货物信息的获取。船舶的运力信息来自于船东，可能是船舶所有者或船舶管理公司；货物运输信息来自于货主，可能是货物所有者或货代组织。根据庞大的船舶信息和货物信息，得到船货匹配的结果，形成若干可行方案，如图1所示。然后估算可行方案的收益成本，承租人根据自身运营能力等信息，得到航次方案优选组合。
船舶租金、燃油费、港口使费是租船业务的三大成本[3]，是航次预估的重点。根据企业的现行计算方法，总结得到航次预估模型。
航次标准航时：
T= （1）
其中T表示航次标准航时，L表示各港航距，V表示船的静水速度，根据船的载货情况，分为空载速度和载重速度。
航次总航时：T=T+T=+T+T（2）
其中T0表示船舶在港总时间，T1表示船舶在港空闲时间，T2表示在港工作时间。
1）船舶租金：
R=H×T总 （3）
其中，H是指船舶每天的租金，T总是该航次所需的时间，包括行驶时间、在港时间（含货物装卸与额外时间）和其他时间（如加油等）。
2）燃油费
燃油费是指船舶在航行、停泊、装卸作业时所好用的各种燃料之和。由于燃油费用占到整个航次变动费用的60%左右，特别是航程较长的航次运输，所以燃油费用估算的准确与否是决定本航次的航次变动费用估算准确的关键。
这里的燃油消耗是该航次正常消耗的燃油,与航次时间一一对应,由船舶数据可计算航行时间、港口时间等。按照当时的燃料价格，即可以分别求得航行、港口时间的燃料费用，计算燃料消耗公式[4]：
重油耗油量：Q=q×T+q×T+q×T （4）
轻油耗油量：Q=q′×T+q×T+q×T（5）
其中q表示船舶航行单位重油消耗量，q1表示在港空闲单位时间重油消耗量，q2表示在港空闲单位时间重油消耗量；其中q′表示船舶航行单位轻油消耗量，q表示在港空闲单位时间轻油消耗量，q表示在港空闲单位时间轻油消耗量。
燃料费：O=C1×Q1+C2×Q2 （6）
燃料费是轻油费用与重油费用之和，其中C1表示重油价格，C2表示轻油价格。
3）港口使费
港口使费是指航运公司所经营的船舶在营运期间在装卸港口所发生的各项支出和费用。是航运公司三大营运成本（船期费，燃油费和港口使费）之一，是核算航次利润的主要依据，也可称之为航次费用。
港口使费是一项复杂的计算选项。在实际的远洋运输操作中，一般向港口管理部门询问，不需要自行预估。P表示各个港口使费之和，即：
港口使费：P=P（7）
2基于背包问题的优选算法
背包问题的名称来源于如何选择最合适的物品放置于给定背包中，是在1978年由Merkel和Hellman提出的，相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。它是一个特殊的整数规划问题[5]。
在运用背包问题解决航次方案优选的问题时，我们需要有几个初始条件，一是航次方案的初始投资额是确定的，二是航次方案的收益是可以预测的，三是每一个航次只有投资和不投资这两种选择。
在这里初始投资额即为航次执行所需的成本C，航次方案的收益即为航次方案执行所得到的运费F。
（1）航次方案成本
C=P+O+R （8）
航次方案的成本主要包括港口使费、燃油费、以及船的租金。具体计算见公式（3）（6）（7）。
（2）航次方案运费
F=∑fj （9）
fj是每一票货物的运费。在运费的计算中，需要区分重量货物和容积货物，因此，对于重量货物，根据货物重量计算运费；对于容积货物，根据货物体积计算运费。即
f=W*+S*CP，＞1.1328m/tW*+S*CP，＜1.1328m/t（10）
其中，W表示货物c重量吨，S表示货物c体积吨。=S/W表示该货物c的积载因数。
CP表示该货物c的平均运价。当＞1.1328m3/t时视为容积货物，按体积计算运费；当<1.1328m3/t时视为重量货物，按重量计算运费。
对于承租人来说，经常面临的是对一个方案选择或不选择的问题，用数学的语言来描述就是一个0-1规划问题。因此方案优选问题可以看作是一个背包问题。假设某租船公司有一笔数量为B的闲置资金，欲投资新的散货运输，以获得必要的投资回报。现有n个可供选择的项目，项目i所需的总成本为Ci，预期收益为Fi（i=1，2，…，n）。要使得公司投资后获得的收益最大，应如何分配资金，或者说应将资金投入到那些项目中？针对这一问题，建立如下形式的0-1背包问题模型，输入数据如表1所示。
max Z=Fx （11）
s.t.CxBx∈0，1（i=1…n） （12）
其中：x=1，表示第i航次个方案被选中；x=0表示第i个航次方案未被选中。为使所研究的问题有意义，不妨假设0CB，C＞B。
实际中投资行为都是一个持续不断的过程，而且各个方案的实施时间其实并不是完全同一的。因此有动态的背包模型输入，表2所示，例如方案在实施到一定时刻的时候。时间顺序点si表示方案i的开始时间，ei表示方案i的结束时间，必定有siei。在这里，为了问题的讨论，只考虑投入和产出都只是在一个时间点的情况。
max Z=Fx（13）
s.t.Cx-FxB，（ejsi）x∈0，1，（i=1…n）（14）
其中表示si方案i的开始时间序列号，ei表示方案i的结束时间序列号，即有si 根据模型的数据输入，得到资金的投入产出的时间顺序表。表中数据即为投入或产出的金额。按时间顺序投入时间顺序将方案排序。再根据背包算法回溯法，深度优先，进行搜索。 从解空间中选取（1，1，1，1）和（0，1，1，1），绘制各个时间点资金余额图。如图2所示，其中系列1表示解（1，1，1，1），系列2表示解（0，1，1，1）。 从图中可以看出，当解为（0，1，1，1）的情况下，在时刻点5，无法投资方案4。然而在解（1，1，1，1）中，因为所投资的方案1在时刻点3获得收益30000元，所以能够继续和所剩余的基础投资金额一起投入到后期的方案中，从而进一步获利。这也正是建立动态模型的意义所在。 3结论 本文就是对航次方案优选方法进行深入研究，即公司在现有的能力下，选择合适的方案组合，以获得公司利益的最大化，在提高其核心竞争力方面具有良好的实际应用意义。对背包问题进行改进，使之更符合实际的航次方案优选情况。从成本与收益出发，在背包算法的基础上构建了航次方案优选模型，通过调研定义了合理的规则约束，从而快速地求解航次优选问题。另外还能辅助解决以下问题：辅助确定运价，根据结果显示的收益状况，合理调整货物的运输价格，以便既能扩大业务量、又能保证航次执行结果的收益。 参考文献： [1]谭威：基于VAR模型的干散货航运市场分析研究[R].大连：大连海事大学，2005. [2]胡美芬，王义源.远洋运输业务[M].人民交通出版社，2009：29. [3]谭宇.船舶营运成本的分析与控制[R].大连：大连海事大学，2005：10. [4]谭锋，钟骏杰.船舶航次经营效益估算及计算机实现[J].中国水运，2009，9（11）：67. [5]王晓东.算法设计与分析[M].清华大学出版社，2006：92.