|
Das (asymmetrische) Multi-Service-Path-Problem
-
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.
|
Send mail to
info@os-consultancy.de with
questions or comments about this web site.
|