A MIP-based heuristic for a single trade routing and scheduling problem in roll-on roll-off shipping. (October 2022)

• Record Type: Journal Article
• Authors: Hansen, Jone R.; Fagerholt, Kjetil; Meisel, Frank
• Is Part Of: Computers & operations research. Volume 146(2022)
• Publication Date: 2022-10
• Subjects: Maritime transportation -- Roll-on roll-off shipping -- Evenly spread requirement -- Speed optimization -- Transit time constraints -- Heuristic; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.105904
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: 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. Highlights: We study the single trade ship routing and scheduling problem (STSRSP). STSRSP determines routes and schedules for a roll-on roll-off shipping company. We propose a three-phased matheuristic to solve the STSRSP. Computations show that the matheuristic quickly provides high-quality solutions. We present a case study to evaluate gains of a merger between shipping companies.