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:
- Creating an equal distribution of holiday periods during Christmas is
expensive and time consuming;
- In case of major operational changes, adjusting the tactical planning
is too complicated;
- In general, the tactical planning process is inefficient;
- 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:
- What are the characteristics of ihe tactical planning situation and
what are the causes of the above mentioned difficulties?
- 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:
- 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;
logistics@3mE.tudelft.nl
, TU Delft
/ 3mE
/ TT
/ LT.