Models for a vessel crew scheduling problem

Optimization techniques for the scheduling of employees have been widely studied in many areas of the transportation industry, including railway crew and most notably airline crew scheduling. The problem of crew scheduling in maritime transportation appears to be no less challenging to solve by other means, while the high proportion of expenditure on crew costs suggests an opportunity to use modelling tools to achieve cost savings. Despite this, the use of optimization tools in the industry appears scarce, and there are very few occurrences of maritime crew scheduling problems in the literature. Our research has focussed on the crew scheduling problem faced by a large maritime company conducting an Offshore Service Vessel type operation on a global scale, which by its nature requires an approach to be taken that is distinct from other maritime crew scheduling problems that have been studied. We discuss our experience of formulating the problem, which has seen the development of two mathematical models. The first is relatively simple to solve with standard techniques, but makes a number of simplifying assumptions; the second is much more realistic, but requires a more tailored solution approach. We will give an outline of our solution approaches, which have been designed to underpin the implementation of a decision support tool within the company's scheduling process.