HybridMOOP: Kundenorientierte Mehrzieloptimierung

Kundenorientierte logistische Problemstellungen kommen in vielen wichtigen Bereichen unseres täglichen Lebens vor. Sie reichen von der öffentlichen Verkehrslinienplanung bis hin zur operativen Einsatzplanung von Außendienstmitarbeitern in einer Firma. Vielen dieser Probleme ist gemeinsam, dass es neben einer kostenorientierten Zielfunktion auch eine kundenorientierte Zielfunktion gibt. Diese beiden Ziele sind so gut wie immer widersprüchlich: Geringere Kosten führen zu niedrigerer Servicequalität und umgekehrt. Die jeweiligen Entscheidungsträger sehen sich so vor die Aufgabe gestellt den verschiedenen Zielen unterschiedliche Gewichte zuzuordnen, die ihre jeweiligen Präferenzen abbilden. Einer auf Basis dieser Präferenzen gefundenen Kompromisslösung mangelt es jedoch an wertvoller Zusatzinformation. Diese bezieht sich auf die Wechselbeziehung zwischen Kosten und Servicequalität: Wäre eine höhere Servicequalität mit nur geringem zusätzlichen Kostenaufwand erreichbar? Eine Möglichkeit dieses Problem zu umgehen besteht in der Anwendung von Mehrzieloptimierungsverfahren, die nicht nur eine Kompromisslösung sondern ein ganzes Bündel an "gleich guten" Kompromisslösungen generieren. Sie ermöglichen so dem Entscheidungsträger aus diesem Bündel von Lösungen die passende auszuwählen. Im Bereich der kombinatorischen Mehrzieloptimierung wurde bereits an den unterschiedlichsten Lösungsverfahren gearbeitet. Während exakte Verfahren, die das tatsächlich beste Set an Kompromisslösungen generieren, nach wir vor nur relativ kleine Probleminstanzen lösen können, können effiziente heuristische Verfahren in kurzer Zeit gute aber möglicherweise suboptimale Lösungen berechnen. Besonders die Klasse der so genannten Metaheuristiken hat sich besonders bewährt, gemessen an der umfangreiche Literatur auf diesem Gebiet. Im Bereich der Einzieloptimierung haben sich Kombinationen von heuristischen und exakten Suchverfahren, so genannte hybride Verfahren, als besonders erfolgreich erwiesen. Hybride Methoden wurden im Bereich der kombinatorischen Mehrzieloptimierung bisher kaum erforscht. Diese Tatsache stellt die grundsätzliche Motivation für dieses Forschungsprojekt dar und definiert auch gleichzeitig sein Ziel: Die Entwicklung von hybriden Suchverfahren für logistische Problemstellungen mit mehrfacher Zielsetzung, wobei wir uns, in einem ersten Schritt, auf kundenorientierte logistische Problemstellungen beschränken. Wir befassen uns mit einer Reihe von wichtigen kundenorientierten Problemstellungen: Public Service Location (das Gebiet der Standortplanung repräsentierend), Underground Railway Line Design (als Repräsentant für Netzwerkdesignprobleme), School Bus Routing (den Personentransport repräsentierend) und Service Technician Routing and Scheduling (als Repräsentant für Tourenplanung mit Fahrernebenbedingungen). All diesen Problemstellungen ist gemeinsam, dass Servicequalität in Form von Erreichbarkeit modelliert werden kann. Im Public Service Location bezeichnet Erreichbarkeit eine möglichst kurze Geh-/Fahrdistanz von potenziellen Kunden zu der öffentlichen Einrichtung. Im Underground Railway Line Design definiert sich Erreichbarkeit als möglichst kurze Gehdistanz zu und von den U-Bahnstationen. Im School Bus Routing entspricht die Erreichbarkeit der Gehdistanz von und zu den Bushaltestellen. Im Service Technician Routing and Scheduling bezieht sich schließlich Erreichbarkeit auf möglichst kurze Fahrzeiten von den aktuellen Positionen der Service Techniker zu potenziellen Nofallkunden. Der Erfolg von hybriden Methoden auf dem Gebiet der Einzieloptimierung führt uns zur Definition von drei vielversprechenden wissenschaftlichen Ansätzen im Bereich der Mehrzieloptimierung. Erstens schlagen wir Multi- Objective Large Neighborhood Search vor. Es basiert auf Large Neighborhood Search, einer sehr erfolgreichen Einzieloptimierungsmethode. Wir planen Ideen des Very Large Neighborhood Search, einer rezenten hybriden Methode, und des Multi-Directional Neighborhood Search, einer neuen Mehrzielmetaheuristik zu kombinieren und zu integrieren. Zweitens werden wir das Baumsuchverfahren Beam Search für den Bereich der Mehrzieloptimierung erweitern. Bei der Anwendung von Beam Search wird an jedem Level des Baums lediglich eine bestimmte Knotenanzahl betrachtet. Jüngste Fortschritte im Bereich der Mehrziel-Branch-and-Bound und Branch-and-Cut Methoden legen diese Erweiterung als vielversprechende Richtung für künftige Forschung nahe. Drittens schlagen wir Multi-Objective Heuristic Column Generation vor. Hier planen wir zwischen der Generierung neuer Spalten in viel versprechenden Bereichen des Suchraums und ihrer Verwandlung in Sets von Kompromisslösungen zu iterieren. Im Rahmen dieses Projektes werden somit drei innovative Lösungsverfahren entwickelt und an kundenorientierten logistischen Problemstellungen getestet. Ihre Stärken sowie ihre Schwächen werden sorgfältig analysiert und generelle Richtlinien, unter welchen Umständen und für welche Problemklasse die verschiedenen Methoden am besten passen, abgeleitet.

Das Ziel des Projekts HybridMOOP war es neue hybride Methoden zur Lösung von schwierigen Mehrzielproblemen mit sowohl kunden- als auch kostenorientierten Zielen zu entwickeln. Methodisch lag der Fokus unserer Arbeit auf Methoden, die exakte Lösungsverfahren mit heuristischen Suchstrategien verbinden. Letztere können nicht das bewiesenermaßen optimale Set von Kompromiss- oder Tradeofflösungen für Mehrzielprobleme berechnen, aber eine gute Approximation desselben in viel kürzerer Laufzeit. Im Rahmen von HybridMOOP entwickelten wir zwei Lösungsverfahren, die auf eine große Auswahl von Problemen angewandt werden können, nicht nur auf solche, die kunden- und kostenorientierte Ziele besitzen. Darüber hinaus entwickelten wir auch zwei Methoden, die für den Umgang mit speziellen, komplizierten Aspekten, die in anwendungs-orientierten Problemsituation mit kundenorientieren Belangen auftreten, maßgeschneidert sind. Die erste Problemstellung, die behandelt wurde, ist das Schülerbus Routing und Scheduling Problem. Ziel ist es die Kosten, die Funktion der gesamten von den Bussen gefahrenen Strecke sind, zu minimieren und dabei Qualitätskriterien, wie die maximale Reisezeit der Schüler einzuhalten. Um die Kosten in einem akzeptablen Rahmen zu halten, sind Umstiege erlaubt. Die Anzahl der Umstiege ist in der zweiten Zielfunktion modelliert und soll ebenfalls minimiert werden. Natürlich führen mehr Umstiege zu günstigeren Lösungen und weniger Umstiege erhöhen die Kosten. Die zweite anwendungsorientierte Problemstellung betrifft das Routing und Scheduling von Heimkrankenpflegern. In diesem Zusammenhang bildet das kundenorientierte Ziel Präferenzen für bestimmte Pflegepersonen und Besuchszeiten ab. Je größer die Anstrengungen sind, die unternommen werden, um diese Präferenzen einzuhalten, umso teurer wird der Einsatzplan. Obwohl diese beiden kundenorientierten Problemstellungen strukturell sehr unterschiedlich sind, bedienen sich beide Methoden einer heuristischen Lösungsstrategie auf der Metaebene, die jeweils Komponenten enthält, die exakt gelöst werden. Die berechneten Lösungen erlauben eine detaillierte Tradeoffanalyse, die den Entscheidungsträgern wichtige Informationen über das Kompromissverhältnis der verschiedenen Ziele bietet und Fragen wie, ob eine höhere Servicequalität mit nur wenig zusätzlichem Aufwand erzielt werden kann, beantwortet.Der zweite Forschungsschwerpunkt lag auf der Entwicklung von neuen generischen Lösungsverfahren, deren Anwendbarkeit nicht auf Probleme mit kundenorientierten Zielen beschränkt ist. Zwei solche Methoden wurden entwickelt. Die erste ist ein heuristisches Verfahren, das auf einem exakten Paradigma aufbaut und das zweite ist ein exaktes Verfahren, das aber auch innerhalb beschränkter Laufzeit sehr gute Approximationen des optimalen Sets an Kompromisslösungen berechnet. Beide Verfahren funktionieren besser als vergleichbare existierende Methoden und können leicht an unterschiedlichste, schwierige Mehrzielprobleme angepasst werden.