Solving crew scheduling problem in offshore supply vessels, heuristics and decomposition methods

Rights statement
Awarding institution
  • University of Strathclyde
Date of award
  • 2017
Thesis identifier
  • T14819
Person Identifier (Local)
  • 201357148
Qualification Level
Qualification Name
Department, School or Faculty
  • For the efficient utilisation of resources in various transportation settings, scheduling is a significant area of research. Having crew as the main resource for operation maintenance, scheduling crew have been a powerful decision making tool for optimisation studies. This research provides a detailed real case study analysis regarding the difficulties in planning crew in maritime industry. As a special case study, this thesis researches crew scheduling in offshore supply vessels which are used for specific operations of a global scaled company in oil and gas industry deeply with modified formulations, heuristics and decomposition methods.An extended version of computational study for a simple formulation approach (Task Based Model) is applied as deeper analysis to Leggate (2016). Afterwards, more realistic approach to the same problem is revised. Following the revision, a customized and thorough computational study on the heuristic method with various settings is designed and implemented in C++. After elaborated analysis completed on the suggested models firstly, a modification on Time Windows model is presented to increase the efficacy. This modification provides a sharp decrease in upper bounds within a short time compared to the previously suggested models. Through this suggestion, more economic schedules within a short period of time are generated.Achieving high performances from the modified model, an application of a decomposition algorithm is provided. We implemented a hybrid solution of Benders Decomposition with a customized heuristic for the modified model. Although this hybrid solution does not provide high quality solutions, it evaluates the performance of possible decomposed models with potential improvements for future research. An introduction to robust crew scheduling in maritime context is also given with a description of resources of uncertainty in this concept and initial robust formulations are suggested.
Resource Type
Date Created
  • 2017
Former identifier
  • 9912590988902996