Modelling uncertainty in vessel crew scheduling

Crew scheduling is an extensive and important subject for scheduling problems in optimization. It is concerned with the assignment of crew members to create work timetables (schedules) for an organization depending on the requirements and aims of the organization. There are several factors that have to be taken into consideration to decide the assignment of crew members. Apart from the required number of staff and required skills of employees, assignments should conform to the rules and regulations of the specific sector. The basic input of most crew scheduling problems is the set of crew members and the set of tasks that should be carried out according to the definition of tasks and skill levels of employees. The common features of these problems are that the tasks should be completed in the defined time window, in an actual task environment by taking into consideration the legal and contractual requirements. According to these characteristics, the solution methods searches for the best allocation of staff members in general. In this study we aim to evaluate reasonable solution methods for a cost minimization problem based on changes in the scheduling of vessel crews. The focus of this study will be based on crew scheduling in transportation settings specific to the maritime industry. The crew cost for this transportation cost problem depends on different variables. The cost includes the salary of the crew members, accommodation and food expenses and movement cost of crew members. Movement cost is calculated with respect to the travel expenses from a gateway city near their home to the departure port of the ship, airfare, visa expenses, hotel, meals, and crew members return expenses after their duty. As a result, crew cost is a comparatively significant cost factor for shipping companies [25]. Apart from the importance of the crew costs, crew scheduling problems are inherently intractable problems and this feature makes them attractive as optimization problems. To obtain an optimal solution with a solver in a reasonable time is not generally possible for problems of a realistic size. Most of the crew scheduling problems are known to be NP-Hard problems; as the size of the problem becomes larger, the complexity level of this kind of problems also increases. Even though crew scheduling problems in the transportation industry have a significant place in the scheduling literature, maritime crew scheduling problems are not as popular as airline settings. There are several reasons to explain the lack of studies for crew scheduling problems in vessels. These reasons can be explained by the long planning time horizons in maritime context, lower visibility of the shipping industry compared to rail, road and air, and the higher level of uncertainty and the greater need for recovery schedules [10]. In our study, instead of scheduling the crew members from scratch, we are more interested in how the current schedule could be recovered in the face of environmental uncertainty. Since crew schedules in vessels tend to be affected by environmental factors, such schedules need to be adjusted or updated. This feature changes the basis of the study to the field of recovery scheduling problems. Barnhart et. al. [4] give a place to the recovery problem in their study by presenting a crew recovery model developed by Lettovsky et. al. [38]. In this model, the cost of adjusted pairings, reserve crew, deadheaded crews and cancellation are aimed to be minimized. However, there are not too many studies for the recovery problem: some heuristic search algorithms, dynamic programming algorithm, and column generation methods play a role in the existing literature [4]. A good survey paper is provided by [12] which includes recent disruption management (recovery) methods in the airline industry. The authors give comprehensive information about the recovery problem in an airline setting with respect to different objective functions for the different resources of the disruptions. Wei et.al.[51] developed a multi commodity network flow for the crew management problem during airline irregular operations. Their objective is to minimize the cost of returning to the original schedule. They gave a depth-first branch-and-bound search algorithm to solve their set covering formulation for this problem. Their algorithm provides flexibility in terms of the constraints defined by business. Guo [27] has a different approach to the recovery problem. His study is aimed at minimizing the changes in the current schedule. The problem is formulated as a set partitioning problem and he used both a column generation approach and a hybrid of a genetic algorithm with a local search. In relation to the above studies, it is hard to have a completely deterministic data set and construct a model without making strong assumptions. Since we aim to obtain practical results for a real life problem, we want to explore the source of uncertainty in this problem setting and to look for contributions from robust optimization