Delft University of Technology
Faculty Mechanical, Maritime and Materials Engineering
Transport Technology / Logistic Engineering

W.A. Warrens Development of a Tactical Crew Planning System
Masters thesis, Report 95.3.LT.4461, Transport Technology, Logistic Engineering.

Chemical Tankers of America, an American shipping company is currently facing four difficulties regarding the crew planning:
  1. Creating an equal distribution of holiday periods during Christmas is expensive and time consuming;
  2. In case of major operational changes, adjusting the tactical planning is too complicated;
  3. In general, the tactical planning process is inefficient;
  4. The company is too dependent on the crewing manager for execution of the planning task.
This report describes a study of the tactical planning situation, to come to recommendations for solving these difficulties. The following questions will be answered:
  1. What are the characteristics of ihe tactical planning situation and what are the causes of the above mentioned difficulties?
  2. Is software available that meets the requirements imposed by both the planning situation and the company?
A negative answer to the second question leads to a third question:
  1. Can a suitable planning algorithm be written and is it useable in practice?
The tactical planning situation can be formalized into a tactical planning problem. This problem comprises of six vessels, divided into two groups. Each vessel requires four different officers and has one permanent officer for every rank. Each group has one flying squad, consisting of the same ranks to replace the permanent officers during their vacation. The officers have to be scheduled for a three year period, divided into 72 terms.
The planning problem is constrained by hard restrictions which may only be violated in case of emergency and by soft restrictions which are used as objectives. The most important objective is to minimize relieve cost, which are mainly traveling expenses.
The planning problem can be split into four independent subproblems, which can be solved separately.

From the four difficulties mentioned above, the first difficulty is caused by a new hard restriction the company imposed upon the problem, namely: each officer should be home for Christmas once every four years. This restriction increases the combinatorial complexity of the planning problem.
The second difficulty is caused both by the combinatorial complexity of the problem and the procedure for permanent replacement of officers.
Inefficiency of the tactical planning, the third difficulty is due to the absence of evaluation criteria for a planning and to the manual execution of the planning process. The fourth difficulty is caused by the general complexity of the planning task and the required experience to perform this task.

These difficulties can be overcome by implementation of an automated planning tool. The software package Crewplan is the most suitable software for the execution of the planning task. However, the company has not come to an agreement with the developers of this tool, so this study took an other turn, investigating the possibility of writing a suitable planning algorithm.

For this purpose, six mixed integer programming models were developed. The combinatorial complexity, determined by the number of integer variables, combined with the problem structure caused most models to be unsolvable within the time limit. From the models tested only one could be used in practice. The use of special ordered sets, a formulation which exploits the structure of integer programming problems lead to an unsolvable model.

The mixed integer models used can not be improved much further and do not qualify for further research. However, a set partitioning formulation combined with column generation techniques could lead to a solvable model. This needs a further investigation. A less laborious way to accomplish a significant improvement in the tactical planning situation might be the development of an interactive planning tool, including a simple planning algorithm.

Reports on Logistic Engineering (in Dutch)
Modified: 2000.01.17; , TU Delft / 3mE / TT / LT.