RACE – Automatisches Algorithmen-Tuning 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.