Point of interest search along a route with return

Details Point of interest search along a route with return Point of interest search along a route with return

G - Physics

01

C

G01C 21/34 (2006.01)

Patent

CA 2757148

A system in accordance with the present invention includes a GPS module, user in-terface module, database and routing engine. The routing module identifies all POIs that can be reached from the route with a cost less than some threshold distance, m. This identification can be carried out, for example by performing an exploration using Dijkstra's algorithm. The routing en-gine then (or simultaneously) performs a reverse exploration on nodes in the planned route to locate POIs from which the route can be reached with a cost of less than a second threshold cost, n. This process can be performed, for example, by using a reverse Dijkstra exploration, exploring back-wards in cost for n cost (e.g., miles or minutes) from the route along the directed graph to determine which POIs lie within a cost of n. POIs identified as being reachable from the route with a cost of less than m, and from which the route is reachable with a cost less than n are then further filtered to identify a subset of the POIs for which the sum of the time or distance from the route to the POI and the time or distance from the POI back to the route is less than a threshold time or distance, t.

La présente invention porte sur un système qui comprend un module GPS, un module d'interface utilisateur, une base de données et un moteur de routage. Le module de routage identifie tous les points d'intérêt (POI) qui peuvent être atteints à partir de la route, à un coût inférieur à une certaine distance seuil m. Cette identification peut être effectuée, par exemple, par mise en uvre d'une exploration faisant appel à un algorithme de Dijkstra. Le moteur de routage va ensuite (ou simultanément) effectuer une exploration inverse portant sur les nuds de la route planifiée pour localiser des POI à partir desquels la route peut être atteinte à un coût inférieur à un second coût seuil n. Ce processus peut être effectué, par exemple, par utilisation d'une exploration inverse de Dijkstra, exploration en retour du coût, pour le coût n (par exemple des miles ou des minutes) à partir de la route le long du graphique dirigé, pour déterminer les POI qui se trouvent dans la limite d'un coût n. Les POI identifiés comme pouvant être atteints à partir de la route à un coût inférieur à m, et à partir desquels il est possible d'atteindre la route à un coût inférieur à n, sont ensuite filtrés davantage pour identifier un sous-ensemble de POI, pour lesquels la somme du temps ou de la distance de la route au POI, et le temps ou la distance du POI en retour vers la route, est inférieure à un temps ou une distance seuil t.

Affiliated with

Also associated with

Rating

Point of interest search along a route with return does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Point of interest search along a route with return, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Point of interest search along a route with return will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFCA-PAI-O-1601546