RACE: Automatisches Algorithmentuning für Metaheuristiken

Tourenplanung und Reihenfolgeplanung liegt im zentralen Interesse der wissenschaftlichen Community in den letzten 50 Jahren. Das liegt daran, dass die Probleme bei diesen Anwendungen sehr komplex und schwierig zu lösen sind. In den letzten Jahren wurde eine große Anzahl an unterschiedlichen Lösungsmethoden entwickelt. Dabei wurde insbesondere die Entwicklung von Metaheuristiken vorangetrieben. Darüberhinaus repräsentiert die Verteilung von Gütern im Besonderen auf der Strasse einen wichtigen Wirtschaftszweig. Grundsätzlich werden in jeder Lieferkette Güter zwischen Unternehmen oder von Unternehmen zu Endkunden transportiert. Daher haben Firmen in der letzten Zeit festgestellt, dass sie diesen Prozess automatisieren können, und durch den Einsatz von Softwaresystemen eine Unterstützung für diesen Prozess bekommen. Es erweckt den Eindruck, als ob sich wissenschaftliche Interessen und die Interessen von Unternehmen überdecken würden. Dieser erste Eindruck bewahrheitet sich allerdings nicht. Im Gegenteil, der Grad der Automationsunterstützung in der Industrie überdeckt sich nicht mit den Möglichkeiten, die die Wissenschaft bietet. Die meisten Werkzeuge, die in der Industrie verwendet werden basieren auf sehr einfachen Optimierungstechniken. Die Gründe dafür sind mehrfach: Erstens, es kann nicht erwartet werden, dass immer die neuesten Forschungsergebnisse gleich in der Praxis umgesetzt werden. Dabei muss eine gewisse zeitliche Verschiebung akzeptiert werden. Zweitens, je ausgereifter die Optimierungstechniken sind, desto spezieller sind sie für ein Problem maßgeschneidert und können nur für das spezielle Problem sinnvoll eingesetzt werden. Obwohl diese Werkzeuge geeignet wären, um spezielle Probleme besser zu lösen als die einfachen (bereits überholten) Lösungswerkzeuge, sind sie mangels Flexibilität nur sehr eingeschränkt einsetzbar. Mit diesem Projekt wollen wir neuartige Forschungsergebnisse in die Industrie bringen, indem wir eine Softwareklassenbibliothek für Tourenplanungsprobleme entwickeln, die von Praktikern, Beratern und angewandten Forschungsinstitutionen verwendet werden kann. Die zentrale Forschungsfragestellung ist die Entwicklung von Algorithmen, mit denen ein automatisches Parametertuning für Metasuchverfahren durchgeführt werden kann. Die Ergebnisalgorithmen sollen auch in die entwickelte Softwareklassenbibliothek integriert werden. Um auch statistisch gesicherte Aussagen über die Qualität der Lösungen, die mit diesem Framework erzeugt wurden, zu bekommen, werden Algorithmen für statistische Auswertungen in das Framework integriert. Das zentrale Ziel des Projektes ist die Entwicklung einer umfassenden Softwareklassenbibliothek, um Standardtourenplanungsprobleme und reale Tourenplanungsprobleme zu lösen. Im Detail verfolgen wir die nachfolgenden drei Zielsetzungen: 1. Entwicklung eines prototypischen Software Frameworks um verschiedenste reale Touenplanungsprobleme zu lösen. In diesem Framework sollen vor allem Konzepte der variablen Nachbarschaftssuche umgesetzt werden. 2. Entwicklung neuartiger effizienter Methoden, um Metaheuristiken und hybride Verfahren effizient und automatisch zu parametrieren und tunen. 3. Integration von state of the art statistischen Methoden, um die Lösungsgüte der generierten und parameteroptimierten Verfahren zu bewerten. Mit diesem Projekt sollen Forschungsergebnisse in einem angewandten Forschungsprototyp übergeführt werden. Die Ergebnissoftware kann für Machbarkeitsstudien, Potentialanalysen aber auch in der Lehre für fortgeschrittene Studenten verwendet werden. Auf Basis von Ergebnissen von durchgeführten Machbarkeitsstudien mit diesem Softwareframework können neue Brückenschlagsprogramm-Projekte initiiert werden.

Im RACE-Projekt haben wir uns mit einem praktischen Problem beschäftigt: dem Tunen von Metaheuristiken für Tourenplanungsprobleme mit mehreren Fahrzeugen. Wir fanden, dass Tunen nicht einfach ein isolierter, optionaler Schritt auf dem Weg hin zu besseren Lösungen für schwierige Probleme ist, vielmehr beleuchtet es die Probleme selbst und erlaubt zusätzlich einen tiefen Einblick in die Wechselwirkung zwischen dem Problem und seiner Lösung. Um zu verstehen, wie es dazu kommen konnte, möchten wir zunächst kurz auf die Problemstellung eingehen:Das Problem der Flottendisposition ist schwierig, facettenreich und vielfältig: Schwierig, weil meist mehrere harte Probleme verschränkt werden, z.B., die beste Reihenfolge für den Besuch verteilter Kunden zu finden, und unterschiedliche Pakete in verfügbare Laderäume hinein zu puzzeln. Die vielen Facetten beinhalten u.a. die Besuchszeiten der Kunden, die Arbeitszeiten der Fahrer und die Ladebeschränkungen der Fahrzeuge. Die Vielfalt reicht von groß bis klein, von bunt bis eintönig, von praktisch bis akademisch, und von augenblicklich-schnell über Kaffeepausen-lang bis über-Nacht-erschöpfend-genau.Metaheuristische Methoden ist ein komplizierter Name für einen sehr gemischten Werkzeugkasten: Methoden reichen von globalen Strategien, über operationale Prinzipien bis hin zu taktischen Manövern. Da könnte es die Regel geben fange klein an, und vergrößere schrittweise (VNS), oder handle, messe, adaptiere (ALNS). Ein Manöver könnte aus chirurgischen Eingriffen bestehen (k-opt), oder einfach: dreinschlagen und wieder aufbauen. Ratschläge reichen von Abkühlen (SA), bis zu einer harmonischen Balance zwischen Sammeln und Zerstreuen).Natürlich kann man die vielen, harten Flottendispositionsprobleme nicht einfach mit einem Sack voller Lösungsansätze erschlagen: Da braucht es schon Entwickler und Forscher, die eine maßgeschneiderte Methode zusammenzimmern und dann polieren bis sie glänzt. Wobei es in der Praxis zwischen Rohbau und Feinschliff nicht immer klar unterschieden werden kann. Wir haben ganz auf der Seite der kleinen Maßnahmen angefangen bevor uns klar wurde, dass das Nachzeichnen aller Möglichkeiten faszinierende Ergebnisse abgibt: Die Lösungsmethode durchleuchten dann einen bestimmten Blickwinkel auf die Probleminstanz. Eine andere Methode kann dann einen anderen Winkel abbilden. Es funktioniert aber auch umgekehrt, weil die Ergebnisse vieler Probleme die Funktionsweise der Methode auf einer breiteren Leinwand nachzeichnen.Leider bekommt man durch das Ausspielen von Problemen und Lösungen keine gestochen scharfen Bilder, weil die Lösungsmethoden rauschen und die Probleme voller minutiöser Detailstrukturen sind.Wir glauben, dass wir das Glück hatten, auf eine Methode für brauchbare und interessante Bilder zu stoßen, aber wir haben damit erst die aller ersten Schritte machen können. Als nächstes nehmen wir uns vor, eine systematische Karte der Probleme zu zeichnen. Unsere Methode sollte uns zur bestmöglichen Beschreibungen leiten können. Und dann können wir mit dieser Beschreibung die Entwicklung neuer Methoden in Angriff nehmen, die auf die neuen Einsichten abgestimmt sind.Es gibt viel zu tun, aber RACE hat uns auf einen großartigen Weg geleitet und uns weitere ungeahnte Dimensionen eröffnet, die bearbeitet werden müssen!