Solving the vessel routing and scheduling problem at a Canadian maritime transportation company

Abstract

This paper describes the development of a scheduling tool to help a Canadian shipping company optimize the routing and scheduling of their ships and allocate the right assets to the right cargo. The problem can be formulated as a variant of the vehicle routing problem with pickup and delivery, and it is solved by adapting a tabu search heuristic originally developed for the latter problem. The decision support tool is currently implemented within the company, and it is used by the scheduling team to validate assumptions and schedule their fleet over short- to long-term planning horizons. A user interface lets the users visualize results and carry out manual changes to the schedule. The decision support tool yields important savings compared to manual planning practices that were previously in place at the company.

Keywords:

• Maritime transportation
• vessel routing and scheduling
• heuristics

Acknowledgements

This research was supported by MITACS and by the Natural Sciences and Engineering Research Council of Canada. This support is gratefully acknowledged. We are also grateful to two anonymous referees for their valuable comments that have helped improve the paper.

Disclosure statement

No potential conflict of interest was reported by the authors.