Wie komplex ist die Mathematik hinter der Tourenoptimierung?
- 2 August 2022
- 3 mins
Das Forschungsgebiet der Tourenoptimierung gehört zum mathematischen Teilgebiet der Operations Research und insbesondere zur kombinatorischen Optimierung. Dieser Zweig der Mathematik konstruiert aus einer großen Menge von Elementen (Gegenstände, Orte etc.) die optimale und den vorherrschenden Nebenbedingungen entsprechende Teilmenge.
Eines der grundlegenden Probleme der Tourenoptimierung ist das 1832 erstmals beschriebene „Problem des Handlungsreisenden“: Es geht darum, die optimale Art und Weise zu finden, um N Punkte zu besuchen und dabei die vom Handlungsreisenden zurückgelegte Strecke so kurz wie möglich zu gestalten. Formal läuft dies darauf hinaus, unter geringstem Kostenaufwand in einem vollständigen Graphen einen Hamiltonkreis zu identifizieren, der jeden Punkt nur einmal durchläuft. Dieses Problem gilt als NP-vollständig [1], was bedeutet, dass es im Voraus keinen Algorithmus gibt, der es zeitnah im Sinne der Computerkomplexität (d. h. in Polynomialzeit) lösen kann.
Im allgemeineren Fall mit K Fahrzeugen wird dieses Problem als Vehicle Routing Problem oder Tourenplanung bezeichnet und wurde 1959 erstmals von Dantzig und Ramser in die Literatur eingeführt [2]. Diese Verallgemeinerung kann als Optimierungsproblem auf zwei Ebenen betrachtet werden:
- Ein Problem der Zuweisung von Aufgaben an Fahrzeuge
- Ein Problem vom Typ „Handlungsreisender“ für jedes Fahrzeug
Der Lösungsweg gestaltet sich umso komplexer, wenn beide Ebenen gleichzeitig gelöst werden müssen.
Um sich den stark kombinatorischen Aspekt dieses Problems vor Augen zu führen, kann man die Anzahl der möglichen Touren in Abhängigkeit von der Anzahl der zu besuchenden Punkte errechnen:
Bei drei Punkten gibt es sechs mögliche Touren.
Bei 10 Punkten gibt es bereits 3.628.800 Möglichkeiten. Und bei 60 Punkten gibt es so viele Möglichkeiten, wie es Atome im beobachtbaren Universum gibt:
In der Logistikbranche können derartige Problemstellungen mitunter Tausende von zu besuchenden Punkten und Hunderte von Fahrern umfassen. Diese Unmengen an kombinatorischen Gestaltungswegen machen eine erschöpfende manuelle Erkundung der Lösungen nahezu unmöglich. Genau hier kommt die Mathematik ins Spiel. Neue Algorithmen sollen in wenigen Minuten lösen, wofür selbst der leistungsfähigste Rechner Jahrhunderte benötigen würde: aus allen möglichen Lösungen die beste zu finden.
Zur Lösung dieser Problematik kristallisieren sich zwei entscheidende Ansätze heraus:
- Exakte Algorithmen: Mit genügend Zeit und bei Problemen von überschaubarer Größe können exakte Algorithmen die optimale Lösung des Problems finden und diese auch beweisen. Dazu gehören: dynamische Programmierung, ganzzahlige lineare Programmierung etc.
- Approximationsalgorithmen: Diese können zufriedenstellende Lösungen für ein Problem konstruieren (potenziell optimal, aber ohne Möglichkeit, dies zu beweisen). Dazu gehören: Greedy-Algorithmen, Metaheuristiken (genetische Algorithmen, GRASP etc.) [3].
Bei beiden Ansätzen besteht die grundlegende Idee darin, nicht alle Lösungen des Problems zu erforschen, sondern intelligente, auf der Problemstruktur basierende Entscheidungen zu treffen. Beim Problem des Handlungsreisenden findet sich beispielsweise die beste Wahl des nächsten zu besuchenden Punktes aller Wahrscheinlichkeit nach unter den am nächsten liegenden Punkten, und nicht unter denen, die am weitesten entfernt sind. Diese Art der Argumentation begrenzt den Suchradius und konvergiert schnell zu optimierten oder sogar optimalen Lösungen.
Jahrzehntelang haben Forscher daran gearbeitet, Lösungen für komplexere und realitätsnähere Versionen des theoretischen Problems der Tourenplanung bereitzustellen: begrenzte Ladekapazitäten, einzuhaltende Zeitfenster, Abfahrten von mehreren Lagern etc. Diese zusätzlichen Einschränkungen gestalten das Problem mitunter jedoch so komplex, dass sich schon das Finden von grundlegend auf alle Einschränkungen eingehenden Touren als Herausforderung erweist – bevor überhaupt von Optimierung die Rede sein kann.
Durch die Einbeziehung der theoretischen und technischen Fortschritte konnten zahlreiche Softwarelösungen mit integrierter Tourenoptimierung entwickelt werden, die die Transportbranche unterstützen und die Leistungsfähigkeit der Lieferkette verbessern.
Die Quanteninformatik könnte für derartige Berechnungen in den nächsten Jahren noch weitere bahnbrechende Durchbrüche bereithalten: Jüngste Veröffentlichungen befassen sich bereits mit dieser Problematik und versuchen, das Problem des Handlungsreisenden ein für alle Mal zu lösen [4]. Tatsächlich könnte das Quantencomputing schnelle Lösungen für Probleme erbringen, die für die „klassische“ Informatik unerreichbar sind, und auf diese Weise dazu beitragen, die Optimierung der Supply Chain ein weiteres Mal zu revolutionieren.
Lösung zur kontinuierlichen Tourenoptimierung
[1] C. H. Papadimitriou. The Euclidean travelling salesman problem is NP-complete. Theoretical Computer Science vol. 4, issue 3, 1977.
[2] G. B. Dantzig, J. H. Ramser. The Truck Dispatching Problem. Management Science vol. 6, no. 1, 1959.
[3] P. Siarry. Métaheuristiques: Recuits simulé, recherche avec tabous, recherche à voisinages variables, méthodes GRASP, algorithmes évolutionnaires, fourmis artificielles, essaims particulaires et autres méthodes d’optimisation. Editions Eyrolles, 2014.
[4] K. Srinivasan, S. Satyajit, B. K. Behera & P. K. Panigrahi. Efficient quantum algorithm for solving travelling salesman problem: An IBM quantum experience. 2018.
