Method and apparatus of vehicle navigation system for detecting and avoiding city with crowded streets
First Claim
1. A method for selecting a route for user navigation from a first location to a second location in an electronic navigation device, said route including a plurality links corresponding to a plurality of road levels, wherein links at higher road levels comprise combinations of links at lower road levels and wherein said links at said higher road levels inherit costs from said combinations of links at said lower road levels, the method comprising:
- electronically loading a map from a memory;
electronically retrieving road-level information based on position information of roads and delays;
identifying a plurality of routes, each route comprising links at a higher road level and at least some of said routes including a larger number of potential delays;
electronically assigning crowded penalty costs for crowded links, said assigning comprising,comparing a length of a first link at a lower road level to a predetermined length;
marking said first link as a marked link if said length of the first link is less than the predetermined length;
identifying a link as a crowded link if said link comprises a predetermined number of consecutive marked links; and
assigning a crowded penalty cost for said crowded link;
electronically assigning penalty cost for one or more links at a lower road level;
when links at said higher road level include said one or more links at said lower road level having any type of cost, accounting for said cost in a penalty list associated with said links at said higher road level;
when one of said routes includes said links at said higher road level with said penalty list, accounting for said costs in said penalty list during a calculation of a total penalty cost of said one route; and
selecting a final route from said plurality of routes with a relatively lower total penalty cost.
2 Assignments
0 Petitions
Accused Products
Abstract
A system for comparing various routes, identifying delays among the routes, and selecting a more desirable route, even if the desirable route is not the shortest distance, is described. In one embodiment, the more desirable route is the faster route. In one embodiment, the more desirable route is a route with fewer in-route delays. In one embodiment, the system loads a map from a memory and retrieves road level information based on position information of roads and delays. The roads in the map are described at various levels of detail, wherein lower levels contain more detail and relatively higher levels that contain less detail. One embodiment includes detecting a route having links with a substantially larger number of delays and adding an additional penalty cost for the links at higher levels based on penalties computed from the links at lower level road levels. If a current road level is not the highest, one embodiment include adding the additional penalty cost into a “penalty list” of a higher level link having the links of a current road level in order to detect the higher links with a large number of delays while calculating route at a higher level. When calculating a route (or portion of a route) at a higher road level, an additional penalty cost is added to the higher level links if based on the penalty list.
13 Citations
10 Claims
-
1. A method for selecting a route for user navigation from a first location to a second location in an electronic navigation device, said route including a plurality links corresponding to a plurality of road levels, wherein links at higher road levels comprise combinations of links at lower road levels and wherein said links at said higher road levels inherit costs from said combinations of links at said lower road levels, the method comprising:
-
electronically loading a map from a memory; electronically retrieving road-level information based on position information of roads and delays; identifying a plurality of routes, each route comprising links at a higher road level and at least some of said routes including a larger number of potential delays; electronically assigning crowded penalty costs for crowded links, said assigning comprising, comparing a length of a first link at a lower road level to a predetermined length; marking said first link as a marked link if said length of the first link is less than the predetermined length; identifying a link as a crowded link if said link comprises a predetermined number of consecutive marked links; and assigning a crowded penalty cost for said crowded link; electronically assigning penalty cost for one or more links at a lower road level; when links at said higher road level include said one or more links at said lower road level having any type of cost, accounting for said cost in a penalty list associated with said links at said higher road level; when one of said routes includes said links at said higher road level with said penalty list, accounting for said costs in said penalty list during a calculation of a total penalty cost of said one route; and selecting a final route from said plurality of routes with a relatively lower total penalty cost. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. An apparatus for selecting a route for user navigation from a first location to a second location, said route including a plurality links corresponding to a plurality of road levels, wherein links at higher road levels comprise combinations of links at lower road levels and wherein said links at said higher road levels inherit costs from said combinations of links at said lower road levels, comprising:
-
a storage system that stores a map; a processor that identifies routes on said map, each route comprising links at a higher road level, at least some of said routes including a number of delays, the processor additionally calculating a cost for each route, said calculating including, accounting in a cost list of a link at a higher road level costs of links at said low road level when said links at said lower road level are included in said link at said higher road level, said processor selecting a final route from said routes, said final route selected at least in part on said cost lists of said links at said higher road level of said final route being smaller than costs lists associated with other routes, and said processor associating a cost with crowded links, said associating comprising comparing a length of a link with a predetermined length, marking the link when the predetermined length is longer, determining a link at said higher road level is a crowded link if a number of consecutive marked links at said lower road level in said link at said higher level is larger than a predetermined value; and a display that displays said final route selected by the processor. - View Dependent Claims (9, 10)
-
Specification