Maschinelles Lernen in BPC für Tourenplanungsprobleme

Die Planung und Durchführungen von Lieferungen stellt einen wesentlichen Teil der Kosten im Bereich der Distributionslogistik dar und es besteht ein großes Interesse Optimierungspotentiale in diesem Bereich bestmöglich auszuschöpfen. Daher gehören Tourenplanungsprobleme auch zu den zentralen Fragestellungen des Operations Research (OR). Der Einsatz von Optimierungverfahren zur Tourenplanung verspricht großes Potential zur Kosteneinsparung durch die höhere Qualität der Planungsergebnisse als auch durch Automatisierung und Beschleunigung des Planungsprozesses. Es existieren zahlreiche Varianten von Tourenplanungsproblemen, angelehnt an die unterschiedlichen realen Anfordernisse denen sich Transportdienstleister gegenübersehen. In den meisten Tourenplanungsproblemen gilt es, für eine gegebene Flotte von Fahrzeugen die kostengünstigsten Routen zu finden, um eine gegebene Menge von Aufträgen unter Berücksichtigung verschiedener Restriktionen zu erledigen. Die leistungsfähigsten exakten Algorithmen zur Tourenplanung 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 sukzessive neue Routen bzw. Schichten generieren. Das geplante Vorhaben soll neue Erkenntnisse zur Nutzung von maschinellem Lernen (ML) in BCP zur Lösung von Tourenplanungsproblemen hervorbringen. Die Kernfrage ist, auf welche Weise ML in OR-Algorithmen eingesetzt werden kann, denn Optimierungsprobleme unterscheiden sich stark von den meisten Problemen, die aktuell durch ML gelöst.

Das Projekt lieferte neue Erkenntnisse zur Integration von überwachtem Lernen in Optimierungsalgorithmen des Operations Research zur Lösung von Tourenplanungsproblemen. Insbesondere wurde gezeigt, dass sich überwachtes Lernen auch in exakten Optimierungsalgorithmen einsetzen lässt. Dabei war eine sorgfältige Auswahl der Lernziele entscheidend. Oftmals war nicht von vornherein klar, was gelernt werden konnte und wie sich das Gelernte auf den übergeordneten Algorithmus auswirkt. Es hat sich als sinnvoll erwiesen, zunächst den Algorithmus mit perfekt gelerntem Wissen zu testen, um das Verbesserungspotenzial zu ermitteln. Wenn selbst mit perfektem Lernen nur marginale Verbesserungen erzielt werden können, wird ein reales Lernverfahren erst recht keine signifikante Verbesserung bringen. Hinsichtlich der Lernverfahren hat sich gezeigt, dass traditionelle Ansätze, wie Wälder aus Entscheidungsbäumen, ebenso gute Ergebnisse wie neuronale Netze erzielen können - und das bei deutlich geringerem Aufwand. Einige der untersuchten Komponenten von Branch-Cut-and-Price konnten durch die Integration von maschinellem Lernen nicht signifikant verbessert werden. So brachte beispielsweise eine Masterarbeit zum Thema Auswahl von Schnittebenen keine signifikante Verbesserung der Laufzeit. Erfolge konnten hingegen i) beim Lernen komplexer Parametrisierungen, wie beispielsweise beim Konfigurieren einer elementaren Nachbarschaft, und ii) beim Lösen des Subproblems erzielt werden, beispielsweise beim Erstellen reduzierter Netzwerke oder bei der Entscheidung über gute und schlechte Label in der dynamischen Programmierung.