ESPRIT-Project
DISSY
Driver Scheduling System for Public Transport
Duration of
Research Project |
Jan/01/1998 - May/31/1999 |
| Keywords |
shift duty scheduling, staff rostering, rota
scheduling, human resources planning, public transport, decision support,
simulation, optimization, high performance computing |
Technical
Features |
Client/Server, distributed multi-tier architecture,
WinSockets, MS
Windows NT, Visual
C++, ActiveX |
Objectives
The objectives of the DISSY project are the development, evaluation, and
dissemination of an HPCN-based simulation and decision support system for
the bus and tram driver duty rostering problem in urban public transport
(UPT). The tool allows for simulating and evaluating different scheduling
scenarios, thereby enabling to better adapt human resource management to
new market conditions. It multiplies the productivity of the users of the
planning department and produces transparency for management and drivers.
Leading to a new flexibility in urban public transport, the integrated
tool gives new impulses to innovating the business process of urban public
transport companies and other industries using shift work.
The Business Case
The following figure shows the network of tram and bus lines underlying
the timetable of BSAG. In this application, more than 800 daily shift duties
and more than 1300 drivers must be scheduled.
The network of tram and bus lines at the BSAG
A roster defines the (driving) duties which are served by a group of
workers (drivers) on each day of the planning horizon. The driver duty
scheduling problem consists of
-
assigning the duties to be served to the groups of drivers according to
the qualifications and preferences of the workers in each group whilst
-
sequencing, for each group of drivers, the duties in their roster in order
to meet federal work regulations, union contracts, and company agreements
as well as recommendations of industrial medicine and individual preferences
of the group, mainly regarding the duration of (nightly as well as weekly)
rest periods. The rhythm of duty periods and off-days is called turnus.
In traditional systems, for each position (which is not an off-day) in
each roster it needs to be specified by the user what kind of duty the
automatic scheduler should schedule at this position. Likewise, the turnusses
must be defined beforehand by the user. This way it is easy to optimize
the schedule but it is inconvenient for the user because it is a tedious
work to adopt the setting to new boundary conditions and obtain a new solution.
Also the extent to which the rosters can be optimized is limited.
Changes in boundary conditions such as
-
the introduction of new lines, which result in a new set of duties to be
served,
-
a change in workforce, such as a new group of drivers with a new profile,
-
a modified profile or size of a group of drivers,
-
new work regulations by federal law, union contracts or company agreements
which allow for new types of turnusses or rosters, or
-
new insights of industrial medicine regarding the sequencing of duties
which promise to reduce the sick rate or to improve the fitness for work
in the long run,
however, require a flexible decision support tool to facilitate the adaptation
of the business process to the new situation. A need for what-if analysis,
simulation and comparison of different scenarios arises. Simulating driver
duty scheduling helps to understand the influence of parameters and interdependencies
between optimization objectives, giving new ideas of how to organize the
operations. Alternative variants and new roster and turnus types can be
discussed between planning department, works committee, and management
and evaluated on the basis of sound information.
Benefits
The system has the following overall benefits.
-
Increasing the satisfaction of the personnel by taking their preferences
into account.
-
Higher quality of the schedules: e.g. the desired duration of the daily
rest periods could be improved by a factor of about 30 compared to manually
produced schedules.
-
Cutting costs by
-
reducing the sick rate,
-
helping to ensure the drivers' health and fitness for work in the long
run,
-
maximizing the utilization of the work force, and
-
minimizing overtime.
-
New flexibility in long-term planning of human resources.
-
Higher transparency of the schedules for management and drivers alike.
-
Increased productivity of the planning staff.
These benefits are to be achieved by the following means.
-
Worker Profiles. Instead of specifying details of the various rosters,
the system allows for the definition of groups of workers each of which
has got a profile. These profiles specify characteristics of the workers
in the group (such as licenses) as well as preferences and objectives of
the group with regard to the assignment and the sequencing of duties. These
profiles can easily be changed. The system then computes turnusses and
rosters which match the profiles of the individual groups as far as possible.
This way the UPT company is enabled to better meet the drivers' needs and
preferences, thereby easing the strain of shift work and increasing the
drivers' satisfaction. The chance to actively participate at the rostering
process through the specification of the preferences should further motivate
the drivers.
-
Multi criteria decision making. An increased scheduling quality
is guaranteed by taking into account a large set of optimization criteria
(objectives). For each group of workers, a set of 18 different criteria
model law, union and company restrictions as well as aspects of economics,
industrial medicine and drivers' preferences in the desired solution.
-
Rota Simulation. Automatic optimization of the set of turnusses
underlying the rosters. The system suggests good turnusses which suit the
drivers' profile as well as the set of duties to be served in the sense
that they supply the work capacity which optimally matches the demand for
drivers. Economic performance is further improved by an optimized scheduling
of reserve duties which is aimed at maximizing the utilization of the work
force.
-
Roster Simulation. The system allows for an easy, fast and reliable
evaluation of scheduling variants and new rostering models through case
studies (what-if analysis) and simulations in order to adopt the business
process to boundary conditions.
-
Optimization of the business process. Many of the scheduling objectives
are conflicting (such as a long daily rest period vs. a long weekly rest
period). The preferences of groups of drivers may compete for „pleasant
duties". The drivers' preferences may object recommendations of industrial
medicine which are to ensure the drivers' health and fitness for work in
the long run. That is, in practice, not mathematical optimality but an
optimal fit to the specific economical and social environment and conditions
of the enterprise is crucial. DISSY supports the human power of judgement
which is required at this point: acceptable compromises can be found through
parameter studies. The planner becomes an architect of tomorrow's solutions:
DISSY just supplies quick feedback to his ideas and creativity, releasing
him from the tedious task of manually assigning single duties to rosters.
-
The graphical user interface. DISSY does not alone allow for the
traditional manual scheduling process (whereby fully exploiting the whole
of the Windows facilities), the DISSY GUI also supports for the set-up
and the evaluation of the studies / simulations: facilitating the setting
of the parameters and characteristics of the case to be studied as well
as processing the results of the simulations for readily comprehensible
visualization. The MDI technology and the object-oriented approach allow
for comfortably assessing, comparing and manipulating multiple alternative
schedules at a time.
A screenshot of the MDI graphical user interface
The Concept
The solution of combinatorial optimization problems is in many areas such
as logistics, transport and production the key to an economic use of resources,
to increasing the efficiency of processes, and to improving product quality.
Due to the required short response times and the complex nature of decision
support systems which allow for automatic optimization of large-scale real-world
problems, the usability of common sequential computing techniques is very
limited. Parallel and distributed computing systems offer a way of solving
large and complex optimization problems economically by using the joint
power of multiple processors connected by a fast communication network.
In the DISSY project, the methodology to solve the driver rostering
problem is transferred from an airline crew scheduling prototype developed
by the partner HUB in the BMBF-funded project PARALOR.
In order to allow for the comparison of various scenarios the system must
yield reliable results, i.e. high quality solutions must be computed for
each parameter setting. The complexity of the optimization problem (the
number of variables and optimization criteria involved) requires advanced
combinatorial optimization and operations research techniques such as modern
metaheuristics. These techniques, however, consume considerable computing
time for problems of the given size (i.e.some hours depending on the problem
size and quality required). In order to still have reasonable response
times the use of HPCN technology is introduced to the scheduling process
at UPT companies. The computing load is distributed among a cluster of
orinary desk-top PCs communicating by any network which supports TCP/IP
protocol. As this technology has become a common commodity the architecture
underlying DISSY often does not even imposes any investment and is easily
maintained. Furthermore, the architecture is easily extendible and scalable
to the needs of the user (the UPT company). The HPCN-based system has been
tuned through an implementation and evaluation at the partner BSAG.
Further Information
Participants
Contact
Dr. Thomas Emden-Weinert
E-mail: Thomas.Emden-Weinert@ePost.de |
Hans-Georg Kotas
Bremer Straßenbahn AG
Fachbereich B2: Fahr-, Umlauf-, Dienstplanung
Flughafendamm 12
D-28199 Bremen
Germany
Tel.: [++49] (+421) 5596-488
Fax: [++49] (+421) 5596-135
E-mail: bsag-b2@t-online.de |
TEW
- created 98/4/23, last changed 2002/03/14
Diese
Seite auf Deutsch
