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

Service Paths
 

Last Publications
Home

Service Paths Multi-Stopover Mobile Nets Traffic Optimization Disaster Management Navigation Collision Avoidance

Das (asymmetrische) Multi-Service-Path-Problem -
Design und Prototyping eines effizienten deterministischen Lösungs-Verfahrens

 

Problem:
Bestimme einen kürzesten oder schnellsten Weg von Start s nach Ziel t so dass je Service der Menge S eine Zweigstelle angetroffen wird!
 

Die effiziente Lösung des NP-harten Multi-Service Path Problems MSVP wird für Navigations-System-Hersteller ständig attraktiver angesichts der stetig wachsenden Nutzer (Taxis, Dienstleister, Touristen, ...), die eine Tour von Start s nach Ziel t nicht nur über mehrere bekannte Orte eindeutiger Koordinaten suchen (Multi-Stopoover-Problem MSVP) sondern über unbekannte Orte gewünschter Services S= {Tankstelle, Geldautomat, Briefkasten, Drogerie, Apotheke, Kaufhalle, ...} in der Nähe.

  entwickelte einen Prototyp zur Lösung des Problems basierend auf zwei konnkurrierenden deterministischen Näherungs-Verfahren. MSVP-1 und MSVP-2 und  ein optimales Verfahren MSVP-0.. Wie die Performance-Analyse zeigt ist MSVP-2 genauer aber langsamer als MSVP-1. Auf Grund des geringen Overheads ist dennoch MSVP-0 bis |S|= 6 (hier 4 Locationen je Servive in der näheren Umgebung) echtzeitfähig ( £  2 sec nominelle Zeit). Danch beginnt allerdings die Zeit-Unzumutbarkeit von MSVP-0 durch die "kombinatorische Explosion" der Berechnungszeit. Somit kommen je nach Bevorzugung der Kriterien Zeit oder Genauigkeit alle drei Methoden für Navigations-Apps in Betracht.

Beispiele

*   Ein Kurierdienst darf seine Zustellung an einer der Zweigstellen von Firmen der Menge S abliefern und nicht unbeding an deren Hauptsitz.
 

*   Ein Käufer möchte bei zehn  Firmen S= {1, 2,...,10}  (jeweils mehrere Zweigstellen je Firma) persönlich ein Angebote einholen.
Wie fährt er von Start s= 293 nach Ziel t= 275 unter Beachtung von Abbiegerestriktionen, damit er auf kürzestem / schnellstem Weg je Firma eine Zweigstelle ansteuern kann? Siehe Screenshot.

 

AGB Impressum

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