A MIP-based heuristic for a single trade routing and scheduling problem in roll-on roll-off shipping
研究滚装船公司在单一贸易航线上如何规划船舶航线、时刻表和航速，以满足合同要求并最小化成本，提出一种三阶段混合整数规划启发式算法，测试表明其优于商业求解器。
We study a single trade ship routing and scheduling problem for a roll-on roll-off shipping company. Along the given trade, there is a number of contracts for transportation of cargoes between port pairs. Each contract states a minimum service frequency where the services should be evenly separated in time and possibly transit time requirements. Current planning practice is to visit all ports along the trade every time it is serviced. Here, we aim instead at determining the sailing route and schedule of each voyage along the trade, i.e., which ports to visit when, which contracts to serve, and the sailing speeds, so that all contract requirements are satisfied at minimum cost. To solve this problem, we have developed a three-phase MIP-based heuristic, where each phase consists of solving dedicated a mixed-integer programming (MIP) model. The heuristic constructs solutions by first identifying the most promising candidate routes along the trade. Next, a candidate route is allocated to each available vessel. Finally, the heuristic determines the allocation of cargoes between the vessels, as well as sailing speeds and arrival times. Computational tests show that the heuristic outperforms a commercial MIP-solver and provides high-quality solutions to realistically sized instances in reasonable time.