Automatisierte Planung
- Details
- Veröffentlicht: Donnerstag, 04. März 2021 10:32
- Geschrieben von David Schmider
Kann die Planung von Transportaufträgen in der Baustoff-Industrie automatisiert werden?
Welche Algorithmen eignen sich für die globale Optimierung des Belegungsplanes?
Kurze Reisezeiten, maximale Beladung, minimale externe Ressourcen und sinnvolle Mitarbeiter-Arbeitszeiten – wie lässt sich das unter einen Hut bringen?
Im Rahmen einer Master Thesis wurde ein Projekt für die Automatisierung der Planung durchgeführt. Die Master Thesis wurde von der Berner Fachhochschule als "herausragend" bewertet und mit einem Preis gewürdigt: Link zur BFH News-Seite
Ausgangslage
Der Auftraggeber will die Planung seiner Dispositionslösung automatisieren. Den vom Bestell-Desk erfassten Bestellungen sollen automatisch die optimalen Ressourcen – Werke, Fahrzeuge und FahrerInnen – für den Transport zugewiesen werden. Dabei müssen Bedingungen bezüglich Lieferbarkeit, Fahrzeugart und Mitarbeiterqualifikation eingehalten werden. Die Bewertungskriterien müssen an Kundenwünsche angepasst werden können.
Zielsetzung
Der aus dem Bestellprozess resultierende, pro Auftrag optimierte Belegungsplan, ist nicht als Ganzes optimal. Für die globale Optimierung der Aufträge soll eine Lösung gefunden werden. Ziel ist eine möglichst wirkungsvolle Optimierung in möglichst kurzer Zeit.
Resultate
Um die Qualität des Ressourcen-Belegungsplans messbar und damit optimierbar zu machen, wurde eine Metrik definiert. Sie wurde modifizier- und erweiterbar ausgestaltet. Die in die Gesamtbewertung des Belegungsplans einfliessenden, aktuell 17 Teilbewertungen können einerseits durch das Einstellen von Gewichtungsfaktoren und Parametern beeinflusst werden, andererseits können der Metrik neue Teilbewertungen zugefügt werden.
Für die eigentliche Optimierung wurden Methoden evaluiert, implementiert und mit realen Bestelldaten getestet. Für den Test evaluiert wurden zwei Metaheuristiken, die für die Problemstellung als geeignet gelten. Die erste getestete Methode, der "Genetic Algorithm", hat sich für den vorliegenden Fall, mit einem stark eingeschränkten Lösungsraum, als nicht geeignet erwiesen. Die zweite getestete Methode, die "Ant Colony Optimization", hat sich als sehr gut geeignet herausgestellt und gute Resultate erzielt. Die Methode ist zudem auch gut geeignet für den kontinuierlichen Betrieb mit während der Optimierung neu eintreffenden Bestellungen.
Für die erweiterbare Metrik und die Optimierung wurde eine in der Programmiersprache Java programmierte Bibliothek erstellt, die sowohl für die erstmalige Belegung wie auch für die globale Optimierung verwendet werden kann.
Fazit
Mit Tests konnte nachgewiesen werden, dass sich die zuerst sequenziell erstellte Ressourcenbelegung mit der globalen Optimierung verbessern lässt. Die implementierte Methode ist somit für die beabsichtigte Anwendung geeignet und die programmierte Optimierungs-Bibliothek kann in der Dispositionslösung eingesetzt werden.
Auszug aus generiertem Fahrzeug-Belegungsplan (anonymisiert)