Optimization Systems That Set New Standards



DS-OPT


Characteristics

DS-OPT is an optimization tool for duty scheduling problems of public transit companies. Typically, it is used to plan duties for drivers and train guards. For more than 20 years DS-OPT is in use in a multitude of train and bus companies all over the world.


Problem


Duty scheduling in public transport is a task of operational planning, which is generally carried out by the transport companies in several successive steps: the network planning is followed by the line planning, time tabling, vehicle rotation scheduling, duty scheduling, roster planning and, finally, personnel deployment planning.

Duty scheduling involves creating anonymous daily duties for individual drivers from a set of elementary tasks (the so-called service elements), which together form a service plan. Legal, tariff and operational rules for admissibility, monetary and working time assessment of individual services and the plan as a whole, as well as the synchronization with the upstream and downstream steps of the vehicle rotation and roster planning. The planning horizon is typically a day of operation, the main goal is to minimize the costs, secondary objectives are the satisfaction of drivers and operational stability. In the following, we roughly sketch the problem of duty scheduling in public transport. For a more detailed description, please refer to BGL2001 and the references mentioned there.
Duty scheduling is divided into four levels.

Four levels of service planning


Figure 1 – Duty scheduling graph with solution

Mathematical methodology

The mathematical methodology of duty scheduling accurately reflects the four levels.
The basis and first level is a graph theoretical model of the duty scheduling problem.


Practice and Outlook


DS-OPT is successfully used by many national and international bus and railway companies. Railway companies using DS-OPT include e.g. BLS (press release) and Trenitalia (press release). Many public transport companies like the BVG and some of the German suburban railways use DS-OPT. In addition, many of the smaller and medium-sized public transport companies in Germany are among our customers. DS-OPT is constantly being developed. On the one hand, new requirements flow into the product; on the other hand, we are constantly working on the performance of the algorithm. So we have developed a novel concept for creating service plans similar to existing service schedules to meet uniformity requirements (see BLLSW2012). Also for research purposes, e.g. Integration of service and service order optimization we use DS-OPT (see BDLSW2014).