Full-shipload tramp ship routing and scheduling with variable speeds
Full-shipload tramp ship routing and scheduling with variable speeds
复制标题
DOI：
10.1016/j.cor.2015.10.002
复制
发表时间：
2016-06
期刊：
影响因子：
--
通讯作者：
Min Wen;S. Røpke;H. Petersen;Rune Larsen;O. Madsen
中科院分区：
文献类型：
--
作者：
Min Wen;S. Røpke;H. Petersen;Rune Larsen;O. Madsen
研究满载不定期船运输条件下的航线选择和航速同时优化问题。在这个问题中，一组货物可以从他们的负载运输到卸货港的异质船舶不同的速度范围和负载依赖的燃料消耗的船队。其目标是确定哪些订单服务，并找到最佳的路线，为每艘船和最佳的航行速度在每一个腿的路线，使总利润最大化。这个问题源于丹麦一家不定期船运输公司在油轮业务中面临的现实挑战。为了解决这个问题，一个三指标的混合整数线性规划公式，以及一个集包装公式。提出了一种新的具有高效数据预处理和启发式列生成的Branch-and-Price算法。对真实数据生成的测试实例的计算结果表明，该启发式算法在较短的运行时间内对小测试实例提供了最优解，对大测试实例提供了近优解.分析了速度优化的效果和解对燃料价格变化的敏感性。结果表明，航速优化可使总利润平均提高16%，燃油价格对平均航速和总利润有显著影响。
This paper investigates the simultaneous optimization problem of routing and sailing speed in the context of full-shipload tramp shipping. In this problem, a set of cargoes can be transported from their load to discharge ports by a fleet of heterogeneous ships of different speed ranges and load-dependent fuel consumption. The objective is to determine which orders to serve and to find the optimal route for each ship and the optimal sailing speed on each leg of the route so that the total profit is maximized. The problem originated from a real-life challenge faced by a Danish tramp shipping company in the tanker business. To solve the problem, a three-index mixed integer linear programming formulation as well as a set packing formulation is presented. A novel Branch-and-Price algorithm with efficient data preprocessing and heuristic column generation is proposed. The computational results on the test instances generated from real-life data show that the heuristic provides optimal solutions for small test instances and near-optimal solutions for larger test instances in a short running time. The effects of speed optimization and the sensitivity of the solutions to the fuel price change are analyzed. It is shown that speed optimization can improve the total profit by 16% on average and the fuel price has a significant effect on the average sailing speed and total profit.