| |
Asymmetr. Traveling Salesman Problem (ATSP) und
Multi-Stopover Problem (AMSP)
A) Optimale Lösung in Echteit für Anzahl der Orte <
11
Die derzeit schnellsten Verfahren zur optimalen Lösung des ATSP und AMSP,
bei denen nicht ,wie bei dem herkömmlichen symmetrischen Problemen TSP und
MSP, ungerichtete Kanten (Strassen), sondern gerichtete Kanten (die sind
ja erst praxisrelevant) zu beachten sind, liegen O&S Consultancy vor
und wurden prototypisch mit Simulation auf der
CEAS2009 von Dr. P.H. Richter
(Autor der Verfahren) vorgestellt! Die Schnelligkeit wird
durch neu entwickelte Wege-Algorithmen erreicht, die zudem Abbiegerestriktionen
beachten. Die "Kombinatorische Explosion" (exponentiell
ansteigenden Anzahl der zu berechnenden Permutationen) kommt somit für
Problemumfänge <11 (Anzahl Zwischenziele) überhaupt nicht zur Auswirkung (Bild unten).
Der entwickelte Algorithmus A0 dient offensichtlich insbesondere allen
zivilen und militärischen Routingverfahren, wo Mehr-Ziel-Wege oder
Mehr-Ziel-Rundreisen (UAVs, Kampfjets, ...) in Echtzeit
(Änderungsberechnung während des Fluges) erforderlich sind. Ein entsprechender
approximativer Algorithmus, der Routen in Echtzeit bis 250 Ziele (Zwischenziele)
'near-optimal' ermittelt , ist ausgetestet und wird in Kürze vorgestellt.
B) Neues approxim. Verfahren
A-TSP über die approxim. Lösung des Steiner-Problems -
Lösung in Echteit für Anzahl der Orte < 350,
|V(G)|= 5.000, |E(G)|= 19.716
Visualisierungsprogramm der O & S Consultancy:
Test im Vergleich zur optimalen Lösung, hier mit 10 Rundreisezielen auf einem
kleinen Zufallsgraphen
( Random-Graphgenerator der O&S Consultancy )
|