Internationale Zeitschrift für Schwarmintelligenz und Evolutionsberechnung

Abstrakt

Ein immunologischer Algorithmus zur kombinatorischen Optimierung: das Kraftstoffverteilungsproblem als Fallstudie

Pavone M*, Costanza J und Cutello V

Zusammenfassung Routing-Probleme sind klassische kombinatorische Optimierungsaufgaben, die in zahlreichen industriellen und realen Szenarien Anwendung finden. Eine anspruchsvolle Variante des Routing-Problems ist das Kraftstoffverteilungsproblem (FDP), mit dem ein Transportunternehmen in seinem täglichen Betrieb konfrontiert ist. Die Haupttätigkeit eines Transportkraftstoffunternehmens besteht darin, alle seine Geschäfte, d. h. Tankstellen, entlang einer geografischen Karte aufzufüllen, mit dem Ziel, seine Gesamtkosten zu minimieren. In dieser Forschungsarbeit stellen wir eine hybride Heuristik vor, die auf der Metapher des Immunsystems zur Lösung des FDP basiert und im Wesentlichen darauf abzielt, eine Reihe von Routen zu finden, die für eine feste Anzahl von Fahrzeugen des Unternehmens so kurz wie möglich sind, um die verschiedenen eingegangenen Kundenanforderungen zu erfüllen. Insbesondere ist der vorgestellte immunologische Algorithmus vom Prinzip der klonalen Selektion inspiriert, dessen Hauptmerkmale Klonen, Hypermutation und Alterungsoperatoren sind. Ein solcher Algorithmus zeichnet sich außerdem dadurch aus, dass er (i) einen deterministischen Ansatz basierend auf dem Depth First Search (DFS)-Algorithmus hat – der im Schema der Zuweisung eines Scheitelpunkts zu einem Fahrzeug verwendet wird – und (ii) einen lokalen Suchoperator, der auf der Erkundung der Umgebung basiert. Der Algorithmus wurde an einer realen Dateninstanz mit 82 Knoten und 25 weiteren künstlichen Instanzen getestet, die aus dem DIMACS-Benchmark zur Graphfärbung entnommen wurden. Die in dieser Arbeit vorgestellten experimentellen Ergebnisse beweisen nicht nur die Robustheit und Effizienz des entwickelten Algorithmus, sondern zeigen auch die Güte der lokalen Suche und des auf dem DFS-Algorithmus basierenden Ansatzes. Beide Methoden helfen dem Algorithmus, den komplexen Suchraum besser zu erkunden.