文档介绍：班轮运输的船队规划和网络设计摘要:班轮承运人面临的一个普遍的问题就是其服务网络设计。对于给定的待运输的货物需求及港口,承运人要利用已有资源,尽可能高效的为其船舶设计运输路线。而且,运输路线的利润,取决于运输货物所选择的路线。本论文构建一个整合模型,即混合整数线性规划模型来同时解决船队规划和路径选择问题。这个模型合并了相关约束(比如营运航线的周频率约束)和可能的中转情况(比如两个或两个以上运输路线上的货物中转)。为了解决这个混合整数规划,本文提出一些算法来探索问题的分离性。具体说有贪婪算法、遗传算法和两阶段 Benders (班德尔)分解算法,考虑解决问题的效果,各算法的计算效率和计算时间也被考虑在内。提出了一种有效的迭代探索算法来计算船舶规划,并在 20多个港口、 100 多艘船舶中随机生成距离进行计算机仿真试验,最终结果有较高的船舶利用率和有效地中转。关键词:海上运输;班轮运输; Benders (班德尔)分解算法前言海运货物, 即船舶运输的货物, 它包括除了邮件、人及随身行李等一切经由海运的货物。国际海运承运人, 可以是一个人, 一个企业或一个能在全球范围内通过海运提供运输服务的组织。货主可以是人, 也可以是一个企业, 他们是待运货物的提供者或者所有人。在各种运输方式中, 海运拥有运费低( 十分之一的航空运输费用)、事故少、污染小的优势, 因此也被认为是一种经济、安全、环保的运输方式。逐渐发展的全球化和各经济体间相互依赖促进了航运业的蓬勃发展, 并使许多国家的国际国内贸易都依赖于此种运输方式。美国是世界上最大的进出口贸易国家,其贸易量占世界贸易量的接近 20% ,根据美国港务局协会 2006 年统计,国际货物运输的 99% 是由海运完成。美国港口和水路每年完成超过 25 亿吨的贸易货量, 且这一数据在未来十五年内能翻一番。世界海运贸易的发展,带动了世界船队的发展。联合国贸发会 2006 的数据显示, 2005 年,世界海运贸易装载量增长到 亿吨,并以每年 % 的速度增长,而同时,世界船队增长到 亿载重吨,并以每年 % 的速度增长。尽管船队类型和规模已随着时间改变, 但是船舶的高效利用仍是承运人利润的主要决定因素。一艘船舶需要巨大的资本投资, 一般都是几百万美元, 而且其日常营运成本也有几万美元,因此,最优决策支持系统的发展对于船队有效管理非常必要。海运业已经有很大改变并正在形成新的格局。一个最显著的改变就是集装箱的大量使用。集装箱货物是指, 把货物空间上和经济上储存在集装箱里。货物集装箱化减少了港口人力和设备的装卸作业,是航运业的一次改革。集装箱也已经标准化,术语 TEU 表示 20 英尺长的集装箱。根据德鲁克航运 2001 年报告, 在十九世纪九十年代初, 只有 20% 的杂货是由集装箱运输的。在 2001 年这年, 这一数据就增加到 60% 。 IBM 业务咨询白皮书(作者 Naresh Hingorani 、 Derek Moore 、 Keld Tornqvist 2005 年) 显示, 集装箱航运市场仍以每年 8%-10% 的速度增长。趋势详见图 1. 伴随集装箱化运输的另一个重大改变是集装箱空箱调配。在运输航线上贸易量巨大的不平衡性, 承运人需要调配空箱, 这也是一笔很大的成本。R OI 研究所 2002 年报告显示, 在设备和调配上减少 10% 的成本,利润就可以增加 30%-50% 。海运业的发展见证了中转港数量的增多、规模的增大。中转港是指货物从一艘船上, 在某港口转运到另一艘船上。通过一系列岸桥的移动, 货物从一艘船上直接换装到另一艘船上, 或者卸到港口暂时储存再装载到出港船舶上继续运输。集装箱的使用, 使得这种中转非常方便并且成本效率高。中转服务为承运人提供了额外的路线选择,减少了中转次数并担当了国际贸易促进者的角色。比如, 巴哈马弗理波特( Freeport ) 的和黄( Hutchinson ) 集装箱码头已经成为美东海岸、墨西哥湾、加勒比海、南美到欧洲、地中海沿岸、远东和澳大利亚地区的贸易通道。其他重要的国际中转港包括新加坡、马来西亚巴生港和香港。 2003 年,将近 30% 的集装箱都需要进行中转,而且这个数字还在增加。美国消费者服务 2003 年数据表明, 在新加坡装卸的所有集装箱的 80% 都是中转箱。新加坡是世界第二大集装箱码头,按照船舶吨位计算,新加坡则是世界上最繁忙的港口。海上承运人之间的合作也并非新见。早在 1875 年, 承运人就采用协商的方式来抑制竞争控制运费。最近常见的是, 承运人形成战略联盟来实现规模经济,通过为客户提供高频率的航班和高速度的中转, 扩大其客户基础和增加设备利用率( Song and Panayides 2002 )。从 199