Benchmark Suite for Industrial and Tramp Ship Routing and Scheduling Problems

Abstract

This paper considers a class of cargo ship routing and scheduling problems from industrial and tramp shipping and presents a wide range of benchmark instances that have been created to represent realistic planning problems for various shipping segments. Initial results for the benchmark instances are provided both through exact and heuristic methods. Optimal solutions to smaller problem instances are provided by a commercial mixed-integer programming solver, and high-quality solutions to larger problem instances are provided by a state-of-the-art adaptive large neighborhood search heuristic. The provided benchmark instances, as well as an instance generator, intend to stimulate future development of solution algorithms for this important planning problem, and to provide a basis for modelling and solving various real-life problem extensions that go beyond what is included in the benchmark instances.