Dienstplanung ist die Verteilung von Aufgaben auf Personale mit einem Arbeitsplan. Typischerweise treten eine Vielzahl von gesetzlichen, tariflichen, betrieblichen, technischen und sonstigen Regeln für die Gültigkeit und die Bewertung von Diensten auf. In unserem Projekt werden Dienste im Nahverkehr geplant, also der Einsatz der Busfahrer, U-Bahnfahrer, etc. Vergleichbare Fragen treten aber auch im Lufverkehr, bei der Bahn, in Krankenhäusern und an vielen anderen Stellen auf.

Wir haben in diesem Projekt auf Set-Covering/Partitioning-Modellen basierende Column-Generation-Optimierungsverfahren zur Dienstplanung entwickelt. Bei der Diensterzeugung kommen spezielle Lagrange-Pfadsuchtechniken zur Anwendung, mit denen auch große und komplexe Szenarien mit mehreren Tausend Dienstelementen und Dutzenden von Dienstarten gelöst werden können (dies entspricht einem kompletten mittleren Verkehrsbetrieb oder einem Betriebshof eines großen Verkehrsbetriebs).

Damit sind signifikante Einsparungen möglich. So haben etwa die Stadtwerke Bonn im Busbereich 4.3% und im Trambereich 2.5% der Dienste gespart, die Verkehrsbetriebe Ennepetal-Ruhr im Busbereich sogar 9.1% der Dienste.

• IVU Traffic Technologies AG
• HanseCom GmbH
• Löbel, Borndörfer & Weider GbR