Kürzeste-Wege-Probleme mit Ressourcenbeschränkungen

• Antragsteller: Professor Dr. Timo Gschwind; Professor Dr. Stefan Irnich
• Fachliche Zuordnung: Accounting und Finance
• Förderung: Förderung seit 2019
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 418727865

Zentrale Fragestellungen des Operations Research sind die Tourenplanung und das Crew Scheduling. Bei Tourenplanungsproblemen gilt es, für eine gegebene Flotte von Fahrzeugen die kostengünstigsten Routen zu finden, um eine gegebene Menge von Kunden/Aufträgen unter Berücksichtigung verschiedener Restriktionen zu besuchen/erledigen. Beim Crew Scheduling muss für Mitarbeiter (Piloten, Kabinenpersonal, Zug-, Bus- oder Schiffsführer etc.) ein bester zulässiger Schichtplan gefunden werden, so dass alle anstehenden Arbeiten ausgeführt werden. Zahlreiche Varianten dieser beiden Problemtypen existieren. Der Einsatz von Optimierungverfahren in diesem Bereich verspricht große Kosteneinsparungen durch Automatisierung und Beschleunigung der Planung und die höhere Qualität der Planungsergebnisse.Die leistungsfähigsten exakten Algorithmen zur Tourenplanung und zum Crew Scheduling basieren auf Branch-Cut-and-Price (BCP), welches seinerseits auf Techniken der Spaltengenerierung beruht. Hierbei ist ein Master-Problem zuständig für die beste Auswahl der zur Verfügung stehenden Routen bzw. Schichten, während ein oder mehrere sog. Pricing-Probleme (=Subprobleme) sukzessive neue Routen bzw. Schichten generieren. Dieses Subproblem ist ein Kürzeste-Wege-Problem mit Ressourcenbeschränkungen (Shortest Path Problem with Resource Constraints, SPPRC). Im einfachsten Fall sind Ressourcenbeschränkungen gegeben durch die Fahrzeugkapazität und die Zeitfenster oder die maximale Schichtdauer. Bei praxisnahen Varianten sind oft eine größere Zahl von Attributen notwendig, die zu komplizierteren Ressourcenbeschränkungen zusammengesetzt werden. Standardverfahren zur Lösung von SPPRCs basieren auf Dynamischer Programmierung und sind sog. Labeling-Algorithmen.Diverse aktuelle Rechenstudien zeigen, dass in vielen BCP-Verfahren zur Tourenplanung und zum Crew Scheduling der Hauptaufwand, oft mehr als 95% der gesamten Rechenzeit, in der Lösung der SPPRC-Pricing-Probleme liegt. Jegliche Verbesserung von SPPRC-Algorithmen führt damit direkt zur Beschleunigung des gesamten Verfahrens. Das übergeordnete Ziel des Forschungsprojekts ist die Generierung neuer Erkenntnisse und die Entwicklung und Analyse neuer Verfahren im Bereich von SPPRCs. Es sollen neue generische Techniken für noch effektivere Labeling-Algorithmen entwickelt und neue Problemstellungen handhabbar gemacht werden. Die neuen Methoden sollen dabei insbesondere auch für konkrete Anwendungen umgesetzt (d.h. programmiert) und ihr Nutzen durch Rechenstudien evaluiert werden.

• DFG-Verfahren: Sachbeihilfen