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