In the case of duty scheduling, the aim is to summarize tasks to daily duties which can be carried out by individual employees. These duties are subject to a wide range of complicated and complex rules of laws, regulations, tariffs and company agreements. DS-OPT has already been used to plan duties for bus drivers, train drivers, train crew and ship personnel. We have also carried out successful concept studies to prove the suitability of DS-OPT for the planning of air traffic controllers, flight handlers and aircraft crews.
The basic model of DS-OPT is a set-covering / partitioning model, which is solved with column generation and branch-and-bound heuristics. Our methodology has been developed in collaboration with the Zuse Institute Berlin and has been described in a number of scientific publications. The strength of DS-OPT, however, is the wide range of requirements that it covers. It is used by a large number of different companies, whose requirements are almost completely integrated into our standard product. In doing so, the wishes and requirements of each of our customers are improving DS-OPT for all our customers, as it is our goal to integrate all requirements into DS-OPT and to offer a broad-based optimizer. In this way, we have a uniform optimization core for small bus companies with 20 buses as well as for large urban companies such as the BVG, which can also be used by railway companies such as Deutsche Bahn and Trenitalia.

DS-OPT not only enables automatic duty scheduling, but significant cost savings have also been realized. The Stadtwerke Bonn, for example, were able to save 4.3% of their bus driver duties and 2.5% of their tram driver duties. The transport companies Ennepetal-Ruhr were even able to save 9.1% of their bus duties. At the same time the driver’s interests are taken into account and, for example, the number of split duties or of the aforementioned stress duties were kept low.

DS-OPT was originally developed in a research project funded by the German Federal Ministry of Education and Research (BMBF) at the Konrad-Zuse-Zentrum für Informationsstechnik Berlin, the further development was taken over by Dres. Löbel, Borndörfer & Weider GbR in 2000 and handed over to LBW Optimization GmbH in 2017. Since 2000, distribution has been carried out exclusively through IVU Traffic Technologies AG in its planning system IVU.plan and its rail version IVU.rail.

In this service graph, the tasks and supplemental elements form the nodes, while the edges represent the possible transitions. Nodes and edges carry the attributes relevant to duty scheduling such as driving time, break time, home area, stress factor and many more.
The duties at the second level correspond to paths in the duty scheduling graph. However, not every path is a duty. Only paths that comply with all rules of a duty type define permissible duties.

In this terminology, duty scheduling is a problem of covering nodes (the service element nodes) by paths of certain types. To each path belongs a cost, and DS-OPT searches for a path covering with minimal cost. At the level of the duty schedule, there are still requirements for the mix of paths of different types.

The integration of the duty scheduling into the overall planning is aimed at the fourth level by the construction of appropriate duty scheduling graphs and duty types as well as by the selection of suitable objective functions.

This graph-theoretic model forms the basis for the algorithms of our optimization system. The solution to problems of path covering is one of the best studied questions in combinatorial optimization. We rely on column-generation methods based on set-partitioning and set-covering models. With such methods, great success is achieved in all types of service planning problems: see, e.g. BSSW2006, RLW2004, and W2007.