A decomposition-based iterative optimization algorithm for traveling salesman problem with drone

Yurek, E. E., & Ozmutlu, H. C. · 2018

citation-level

Diese Arbeit wird für eine iterative Zerlegung des TSP-D in Lkw-Routing und Zuweisung und anschließende Optimierung der Drohnenroute zitiert. Sie ist eine Referenz, wenn jemand eine Zerlegung sucht, die nahe an der exakten Lösung bleibt. Die Methode wurde zur Prüfung dieser Karte nicht neu implementiert.

Stufe eins wählt die Lkw-Route und die Kunden, die an die Drohne gehen. Stufe zwei fixiert diese Entscheidungen und optimiert die Drohnenseite mit einem gemischt-ganzzahligen Programm. Die Autoren berichten, dass gleichverteilte Instanzen mit etwa einem Dutzend Kunden in kurzer durchschnittlicher Zeit gelöst wurden, und schlagen eine optimierungsbasierte Heuristik für größere Fälle vor.

Die gelösten Größen gelten für ihren Instanztyp. Der Algorithmus sollte nicht als einsatzbereit für einen Tagesplan mit mehreren hundert Kunden gelesen werden. Detaillierte Energie und Flugverbotsgeometrie sind nicht das Hauptziel.