Home F e e d b a c k K o n t a k t

Multi-Stopover
 

Last Publications
Home

Service Paths Multi-Stopover Mobile Nets Traffic Optimization Disaster Management Navigation Collision Avoidance
Navigation 1 Navigation 2 Navigation 3 Navigation 4 Navigation 5

 

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 )

 

AGB Impressum

Send mail to  info@os-consultancy.de with questions or comments about this web site.
Last modified: Feb 2014