Fleet repositioning in the tramp ship routing and scheduling problem with bunker optimization: A matheuristic solution approach
研究了干散货航运中考虑燃油优化的不定期船航线规划与调度问题，提出两阶段随机规划模型和自适应大邻域搜索数学启发式算法，在120个货物、30艘船和10个加油港的实例中一小时内求得高质量解。
This paper investigates an important planning problem faced by dry bulk shipping operators, referred to as the Tramp Ship Routing and Scheduling Problem with Bunker Optimization (TSRSPBO). The problem is to maximize the overall profit of a fleet of vessels by selecting cargoes and determining ship routes and schedules. We consider this problem under a set of practically relevant features such as flexibility in cargo quantities, as well as bunkering decisions on where to procure fuel and how much. As a particularly novel feature, we address the regional allocation of vessels at the end of the planning period to be well prepared for meeting (uncertain) future demand. To incorporate this, we consider the TSRSPBO as a two-stage stochastic programming problem, where cargo selection, routing, and bunkering decisions are solved in the first-stage problem, and the recourse cost of fleet repositioning is considered in the second stage. We present arc flow and path flow formulations, where the latter employs a priori generation of feasible routes as input. For solving realistically sized instances, we propose a matheuristic based on an Adaptive Large Neighborhood Search (ALNS) framework that iteratively generates columns and solves the path flow model. Computational experiments based on real data show that this matheuristic finds high-quality solutions for large test instances with 120 cargoes, 30 vessels, and ten bunker ports in less than one hour. Also, considering the TSRSPBO as a two-stage stochastic problem achieves the highest profits and is solved almost as quickly as the deterministic problem variant.