Navigation apparatus and navigation method

0001Related fields include a navigation apparatus and a navigation method.

0002Document <patcit id="pcit0001" dnum="US5933100A"><text>US 5,933,100</text></patcit> discloses an automobile navigation system with dynamic traffic data. A central database is provided which includes travel time information for each street segment and transition between street segments in the map database. Based on the travel time information in the database, a route from a current location to a desired destination can be planned in order to have a minim travel time.

0003In a conventional navigation system, for example, traffic information such as traffic congestion information is received from a road traffic information communication system and the stored information is used for searching for a shortest route (refer to, for example, Japanese Unexamined Patent Application Publication No. <patcit id="pcit0002" dnum="JP2002148067A"><text>2002-148067</text></patcit>).

0004According to the aforementioned navigation system, traffic information data received from a road traffic information communication system is only for limited roads. Thus it is difficult to search for a most suitable route without storing accurate traffic information data relevant to every road.

0005In general, various kinds of useful traffic information data exist other than traffic information data from the road traffic information communication system, for example, travel history data from a probe car (hereinafter referred to as probe data) and road traffic sensor census data.

0006In order to resolve such issues as described above, it is an object of the present invention to provide a navigation system and a navigation method to execute a merge processing for various kinds of traffic information data in accordance with established data precision priorities.

0007This object is solved by a navigation apparatus as set out in claim 1, and alternatively by a navigation method as set out in claim 5.

0008Advantageous developments are defined in the dependent claims.

0009For example, various exemplary embodiments of the invention provide a navigation apparatus comprises a receiving means (22) for receiving current traffic information data, wherein the merge means may execute the merge processing even with the current data.

0010Various exemplary embodiments of the invention provide a navigation apparatus comprises an arithmetic means (340) for calculating time difference between a travel time according to the stored data and that according to the current data and a priority setting means (350) for setting priorities of the stored data based on the calculated time difference as the specified priorities, wherein the merge means executes the merge processing in accordance with priorities established by the priority setting means. In this manner, the merge processing is executed in accordance with the priorities based on the calculated time difference between current data and each stored data. Because stored data which is less different from current data may be preferentially merged, available area for obtaining traffic information data may be expanded while data may be transferred for a high-quality route search.

0011Various exemplary embodiments of the invention provide a navigation apparatus, wherein the merge means executes the merge processing by overwriting low-priority stored data with high-priority stored data.

0012Various exemplary embodiments of the invention provide a navigation apparatus, wherein the merge means merges data for every predetermined area. In this manner, priorities are established for each predetermined area so that it is possible to merge data in view of regional characteristics. Thus available area for obtaining traffic information data may be expanded while data may be transferred for a high-quality route search in view of regional characteristics.

0013Various exemplary embodiments of the invention provide a navigation apparatus, wherein the priority setting means may set priorities for each predetermined period of time.

0014Various exemplary embodiments of the invention provide a navigation apparatus, wherein the traffic information data includes travel history data for a plurality of links which indicate roads on map data, and comprises an adjacency condition detection means for detecting adjacency relationships among the plurality of links, and a replace means for replacing a link number allocated for a link which has no adjacency relationship with other links with at least one link number allocated for a link which has a relationship with adjacent links based on the detection by the adjacency condition detection means.

0015In this manner, an incorrect link number allocated for a link which has no relationship with adjacent links may be accurately corrected with at least one link number allocated for a link which has a relationship with adjacent links. Therefore, after the processing, a reliable route may be searched and traffic information may be correctly displayed with using the dependable travel history data.

0016Various exemplary embodiments of the invention provide a navigation method, wherein various kinds of traffic information data used in the past are stored and the each stored data is merged in accordance with priorities established for each stored data. In this manner, each stored data may be applicably merged in accordance with established priorities. Thus available area for obtaining traffic information data may be expanded while data may be transferred for a high-quality route search.

0017Exemplary implementations will now be described with reference to the accompanying drawings, wherein:

0018<figref idref="f0001">Fig. 1</figref> is a block diagram showing an example of the navigation apparatus according to a first embodiment of the present invention;

0019<figref idref="f0001">Fig. 2</figref> is a flowchart showing a program executed by a server of the exclusive information communication system in <figref idref="f0001">Fig. 1</figref>;

0020<figref idref="f0002">Fig. 3</figref> is a detailed flowchart showing a routine of the priority setting processing in <figref idref="f0001">Fig. 2</figref>;

0021<figref idref="f0003">Fig. 4</figref> is a detailed flowchart showing a routine of the merge processing in <figref idref="f0001">Fig. 2</figref>;

0022<figref idref="f0004">Fig. 5</figref> is a block diagram showing an example of the navigation apparatus according to a second embodiment of the present invention;

0023<figref idref="f0004">Fig. 6</figref> is a flowchart showing a program executed by a controller in <figref idref="f0004">Fig. 5</figref>;

0024<figref idref="f0005">Fig. 7</figref> is a part of a detailed flowchart showing a routine of travel history data correction processing in <figref idref="f0004">Fig. 6</figref>;

0025<figref idref="f0006">Fig. 8</figref> is a part of a detailed flowchart showing a routine of travel history data correction processing in <figref idref="f0004">Fig. 6</figref>;

0026<figref idref="f0006">Figs. 9(a) and (b)</figref> are diagrams showing a contrast between before and after a correction by a link number replacing processing in step 1251 for travel times and link numbers;

0027<figref idref="f0007">Figs. 10(a) and (b)</figref> are diagrams showing a contrast between before and after a correction by a link number replacing processing in step 1262 for travel times and link numbers;

0028<figref idref="f0007">Figs. 11 (a) and (b)</figref> are diagrams showing a contrast between before and after a correction by a link number replacing processing in step 1264 for travel times and link numbers; and

0029<figref idref="f0007">Figs. 12(a) and (b)</figref> are diagrams showing a contrast between before and after a correction by a link number replacing processing in step 1271 for travel times and link numbers.

0030<figref idref="f0001">Fig. 1</figref> is a diagram showing an exemplary vehicle navigation system according to the first embodiment of the present invention. The vehicle navigation system 10 is provided with a current position detection unit 11, and a GPS receiver that receives radio waves sent from an artificial satellite of a satellite navigation system (also known as GPS) and detects a current position of the vehicle as well as a present day and time is employed as the current position detection unit 11.

0031In addition, the navigation system 10 is provided with an input unit 12 and the input unit 12 is a portable remote controller, the operation of which send required information through transmission to a receiving section (not shown) of a controller 13 (described later). Note that instead of using the above remote controller as the input unit 12, a touch panel provided along a display screen in a liquid crystal display panel of an output unit 16 (described later) may be employed as the input unit 12.

0032Furthermore, the navigation system 10 is provided with the controller 13, a memory 14, a radio communication unit 15, and the output unit 16. The controller 13 is connected with, for example, a CPU, a RAM, and a ROM other than the receiving sections described above via bus lines.

0033The controller 13 may execute various processing required for route guidance of the vehicle and map display processing based upon detection output of the current position detection unit 11, operation output of the input unit 12, output of the memory 14, output of the radio communication unit 15 and output of an exclusive information communication system 20 (described later).

0034The memory 14 consists of a hard disk, and map data and traffic information data are stored in the memory 14 as a database that is readable by the controller 13. The radio communication unit 15 receives road traffic information from the exclusive information communication system 20 and also outputs the data to the controller 13.

0035The exclusive information communication system 20 installed in an exclusive information center may execute wireless communication with, for example, the radio communication unit 15, a road traffic information communication system installed in a road traffic information center (hereinafter also referred to as VICS (registered trademark) 30), and the probe car 40.

0036Furthermore, the exclusive information communication system 20 may be provided with a server 21, a radio communication unit 22, and a memory 23. The server 21 executes a server program according to flowcharts in <figref idref="f0001 f0002 f0003">Fig. 2 to 4</figref>. During execution of the server program, the server 21 may communicate with the radio communication unit 15, VICS 30, and the probe car 40 via the radio communication unit 22. Note that the server program may be written in advance on a ROM of the server 21 and readable by the server 21.

0037Accumulated probe data, VICS data, road traffic census data, road width interpolation data, and link travel times based on such each data may be stored in a database of the memory 23 as statistical data.

0038The output unit 16 consists of a display device. Based upon control by the controller 13, the output unit 16 may display information required for the vehicle. Note that the output unit 13 is installed in an instrument panel on an anterior wall of the vehicle and displays information on a display panel such as a liquid crystal panel.

0039In the present embodiment structured as above, while the exclusive information communication system 20 is in active, the server 21 may initiate the server program according to the flowchart in <figref idref="f0001">Fig. 2</figref>.

0040First, in step 100, an area setting processing is executed. During the processing, map data stored in the memory 14 is divided into predetermined regions, for example; prefectual regions.

0041Next, in step 200, a time period setting processing is executed. During the processing, stored data is merged in accordance with priorities of the stored data (described later) so that period of time may be set in view of the priorities. For example, period of time may be set on a 24-hour basis.

0042After that, a routine of the priority setting processing 300 is executed as described in <figref idref="f0002">Fig. 3</figref>. First, in step 310, a stored data obtaining processing is executed. During the processing, data at a current time for each target area which is set in step 100 may be obtained from a database of the memory 23, for example, accumulated probe data, VICS data, and road traffic census data.

0043Next, in step 320, a current data obtaining processing is executed. During the processing, the radio communication unit 22 may receive current probe data corresponding to the current time from the probe car 40 and input it on the server 21 while the radio communication unit 22 may also receive current VICS data from the VICS 30 and input it on the server 21.

0044Subsequently, in step 330, a current data setting processing is executed. During the processing, compound data between current probe data obtained in step 320 and current VICS data for links whose data are not included in the current probe data may be set as current data.

0045As used herein, the term "link" refers to, for example, a road or portion of a road. For example, according to one type of road data, each road may consist of a plurality of componential units called links. Each link may be separated and defined by, for example, an intersection, an intersection having more than three roads, a curve, and/or a point at which the road type changes.

0046Next in step 340, according to an identical link, time difference may be calculated between link travel time of stored probe data corresponding to the current time and that of current data which has been set in step 330. After each time difference for each link is calculated, the average value of the calculated time differences (hereinafter referred to as average time difference) may be further calculated for target areas set in step 100. In a similar manner, average time difference between accumulated VICS data and the current data, and average time difference between road traffic census data and the current data may be calculated.

0047Subsequently, in step 350, a priority setting processing is executed. During the processing, based on the average time differences in step 340 which are calculated for areas set in step 100, priorities for accumulated road traffic census data, VICS data, and probe data may be established.

0048For example, according to the current time, if average time difference of road traffic census data, that of VICS data, and that of probe data are ranked in descending order of amount of time difference, priorities are also established in proportion to the order. In the present embodiment, a variable "n" = 1 for road traffic census data, "n" = 2 for accumulated VICS data, and "n" = 3 for stored probe data.

0049Next, a routine of the merge processing 400 is executed as described in <figref idref="f0003">Fig. 4</figref>. First, stored database is initialized in step 410. During the operation, road width interpolation data at a desired time (for example, eight o'clock) for a target area may be read out from a database of the memory 14.

0050As used herein, "road width interpolation data" is data that represents an estimated time required to travel a link. The time required to travel the link is estimated based on the type of road the link represents (e.g., local road, expressway, etc.). Thus, according to this example, road width interpolation data at the desired time of eight o'clock would indicate, that based on the width of the road, it will take 11 minutes to travel the link at eight o'clock.

0051Subsequently, when variable "n" is set as 1 in step 420, data whose priority is equal to the variable "n" may be extracted from accumulated data in step 430. During the operation, among accumulated road traffic census data corresponding to "n" = 1 for the target area, only data at the target time (for example, eight o'clock) may be read out from the database of the memory 14.

0052Next, in step 431, the read out data is merged. According to this example, road width interpolation data read out in step 410 may be overwritten with road traffic census data read out in step 430. If, for example, a link includes no road traffic census data but only road width interpolation data, the road width interpolation data may be used for that link.

0053Then it is determined whether "n" = "N" in step 432. "N" denotes a number of types for target accumulated data. In this example, "N" = 3 because there are three types such as road traffic census data, accumulated VICS data, and stored probe data. At this stage, "n" = 1 as described above. The variable "n" differs from "N" so that "NO" is selected in step 432.

0054Subsequently, the variable "n" is updated to "n = n + 1 = 2" in step 433. In step 430, among accumulated VICS data corresponding to "n" = 2 for the target area, data at the target time (for example, eight o'clock) may be read out from the database of the memory 14.

0055When returning to step 431, the read out data is merged. According to this example, accumulated data, which includes the merged road traffic census data from the previous step 431, may be overwritten with VICS data read out in step 430. If a link includes no accumulated VICS data but only accumulated data (which includes merged road traffic census data), the road traffic census data may be used for that link.

0056Then it is determined whether "n" = "N" in step 432. At this stage, "n" = 2 as described above. The variable "n" differs from "N" so that "NO" is selected in step 432.

0057Subsequently, the variable "n" is updated to "n = n + 1 = 3" in step 433. In step 430, among accumulated probe data corresponding to "n" = 3 for the target area, data at the target time (for example, eight o'clock) may be read out from the database of the memory 14.

0058When returning to step 431, the read out data is merged. For example, accumulated data, which includes merged VICS data and merged traffic census data from previous step 431, may be overwritten with probe data read out in step 430. If a link includes no accumulated probe data but only accumulated data, the VICS data may be used for that link.

0059Then it is determined whether "n" = "N" in step 432. At this stage, "n" = 3 as described above. Thus, "YES" is selected in step 432.

0060Next, in step 440, it is determined whether all necessary data is merged relevant to all target areas set in step 100 and also relevant to each time in a period of time set in step 200. If the merge processing for all desired areas and times has not been completed yet, "NO" is selected in step 440 and a routine of the merge processing 400 is executed again. The routine of the merge processing 400 is repeated until "YES" is selected in step 440.

0061As described above, when a plurality of types of data exist redundantly, average time difference between current data and stored data is calculated according to each accumulated data, and higher-priority is established for stored data which has bigger difference. Then each stored data is merged in order of the priorities. Accordingly, because usable stored data may be preferentially merged, available area for obtaining traffic information data may be expanded while data may be transferred for a high-quality route search. In addition, priorities are established for each predetermined area, so that it is possible to provide applicable search database in view of regional characteristics.

0062In step 440 as described above, "YES" is selected when the merge processing for all target areas and times has been terminated. Subsequently data necessary for searching for a route is transferred in step 500 in <figref idref="f0001">Fig. 2</figref>. In accordance with the operation, the radio communication unit 22 may send merged data as data necessary for searching for a route to the controller 13 via the radio communication unit 15 and the data may be stored in the database of the memory 14.

0063Once a series of processing has been terminated as described above, it is possible to search for a guidance route based on accumulated data necessary for search in the database of the memory 14. Therefore the route may be searched within a wider target area even in view of highly accurate forecast on traffic congestion.

0064Note that the present invention is not limited to the details of the embodiments described above, but various modifications are possible without departing from the scope of the present invention. <ol id="ol0001"><li>1) In step 350 as described above, priorities are set based on average time differences obtained in step 340. However, priorities may be also established for each accumulated data in advance.</li><li>2) In step 330 as described above, when current probe data and current VICS data exist redundantly, current probe data is applied for current data. However, current data may be created by weighting both of current probe data and current VICS data and averaging both of them.</li><li>3) In step 431 as described above, a merge processing is executed by overwriting accumulated data in a database. However, it is also possible to set each specified ratio for each type of stored data in order of the priorities and execute the merge processing by multiplying each stored data by each specified ratio and averaging the calculation results.</li><li>4) In step 100 through 400, the exclusive communication information system 20 executes various kinds of processing for accumulated data and transfers them to the navigation system 10. However, the navigation system 10 may directly obtain the data and execute the same operations in step 100 through 400 for the data instead.</li></ol>

0065Hereinafter, a second embodiment of the present invention will be described. In the first embodiment of the invention, accumulated probe data, that is, travel history data is applied for data necessary for searching for a route. However, such travel history data is not always very reliable relevant to all routes. For example, if stored route data is not for a route actually taken in the past, the travel history data may be unreliable. Thus, it is not recommended to use such unreliable travel history data for searching for a route, displaying traffic information, and so on.

0066In order to resolve such issues as described above, it is an object of the present invention in the second embodiment to provide a travel history data correction apparatus and a correction method for accurately correcting travel history data.

0067Hereinafter, the second embodiment of the present invention will be described with reference to the drawings. <figref idref="f0004">Fig. 5</figref> is a diagram showing an example of a vehicle navigation system according to the second embodiment of the present invention. The vehicle navigation system 10 is provided with the current position detection unit 11, and a GPS receiver that receives radio waves sent from an artificial satellite of a satellite navigation system (also known as GPS) and detects a current position of the vehicle as well as a present day and time is employed as the current position detection unit 11.

0068In addition, the navigation system 10 is provided with the input unit 12 and the input unit 12 is a portable remote controller, the operation of which send required information through transmission to a receiving section (not shown) of the controller 13 (described later). Note that instead of using the above remote controller as the input unit 12, a touch panel provided along a display screen in a liquid crystal display panel of an output unit 16 (described later) may be employed as the input unit 12.

0069Furthermore, the navigation system 10 is provided with the controller 13, a memory 114, a radio communication unit 15, and the output unit 16. The controller 13 is connected with, for example, a CPU, a RAM, and a ROM other than the receiving sections described above via bus lines.

0070The controller 13 executes a program according to the flowchart in <figref idref="f0004">Fig. 6</figref>. During execution of the program, the controller 13 may execute various kinds of processing required for route guidance of the vehicle and map display processing based upon detection output of the current position detection unit 11, operation output of the input unit 12, output of the memory 14, output of the radio communication unit 15 and output of the exclusive information communication system 20 (described later).

0071The memory 14 consists of a hard disk, and map data and travel history data are stored in the memory 14 as a database that is readable by the controller 13. Note that such travel history data may include link numbers allocated for links as well as passing times at the links along a vehicle travel route.

0072The radio communication unit 15 receives road traffic information from the exclusive information communication system 20 and outputs it to the controller 13. Furthermore, the exclusive information communication system 20 transfers various kinds of traffic information data which are received from a road traffic information communication system installed in a road traffic information center (hereinafter also referred to as VICS (registered trademark) 30).

0073The output unit 16 consists of a display device. Based upon control by the controller 13, the output unit 16 may display information required for the vehicle. Note that the output unit 16 is installed in an instrument panel on an anterior wall of the vehicle and displays on a display panel such as a liquid crystal panel.

0074In the present embodiment structured as above, while the navigation system 10 is in active, the controller 13 initiates the program according to the flowchart in <figref idref="f0004">Fig. 6</figref>.

0075First, in step 1100, travel history data is read out as described in <figref idref="f0004">Fig. 6</figref>. Link numbers allocated for links as well as passing times at the links along a vehicle travel route may be read out from a database of the memory 114. Next, in step 1200, travel history data is corrected. The travel history data may be corrected, for example, according to the exemplary method of correcting travel history data shown in <figref idref="f0005">Figs. 7</figref> and <figref idref="f0006">8</figref>.

0076In step 1300, it is determined whether all of the travel history data is corrected. If not all of the travel history data has been corrected, operation returns to step 110. If all of the travel history data has been corrected, operation continues to step 1400.

0077In step 1400, the corrected travel history data is stored. For example, the travel history may be stored in a database of the memory 114. Then, operation of the method ends.

0078Next, a routine of travel history data correcting processing 1200 is executed as described in <figref idref="f0005">Fig. 7</figref> and <figref idref="f0006">8</figref>. First, a first link number is obtained in step 1210. More specifically, a link number at the earliest time among travel history data read out in step 1100 is obtained as the first link number (Na).

0079Subsequently, a second link number is obtained in step 1220, that is, a link number which continuously appears after the first link number (Na) is obtained as the second link number (Nb) among the travel history data.

0080Then in step 1230, it is determined whether there is a link number which further continuously appears after the second link number (Nb) obtained in step 1220 among the travel history data. If such following link number is found, "YES" is selected in step 1220. The link number which continuously appears after the second link number (Nb) is set as the third link number (Nc) in step 1231. In step 1231, the link number that continuously appears after the second link number Nb is set as the third link number Nc.

0081Next, in step 1240, it is determined whether there is an adjacency relationship between the link corresponding to the first link number (Na) (hereinafter referred to as the first link (La)) and the link corresponding to the second link number (Nb) (hereinafter referred to as the second link (Lb)). If such adjacency relationship is detected between the first link and the second link, what that means is that both links are connected with each other on map data.

0082As described above, in case that both of the first link (La) and the second link (Lb) connect with each other on map data stored in the memory 114, it is said that there is an adjacency relationship between the two links so that "YES" is selected in step 1240. Then the link number is reset in step 1241. More specifically, the second link number "Nb" is set as the first link number "Na", and the processing in step 1220 is executed as described above.

0083If the first link (La) is not connected with the second link (Lb) on map data, it is said that there is no adjacency relationship between the two links so that "NO" is selected in step 1240. Next, it is determined whether there is an adjacency relationship between the first link (La) and the link corresponding to the third link number (Nc) (hereinafter referred to as the third link (Lc)) on map data in step 1250.

0084As described above, in case that both of the first link (La) and the third link (Lc) connect with each other on map data, it is determined that there is an adjacency relationship between the two links. Therefore "YES" is selected in step 1250 and a link number replacing processing is executed in step 1251.

0085For example in <figref idref="f0006">Fig. 9(a)</figref>, travel history data may include "1"s as the first link numbers (Na) at traveling time 10:00:00 and 10:00:01, "98"s as the second link numbers (Nb) at 10:00:02, 10:00:03, and 10:00:04, and "2"s as the third link numbers (Nc) at 10:00:05 and 10:00:06.

0086In this example, the first link (La) is not connected with the second link (Lb) on map data because the first link number (Na) is "1" and the second link number (Nb) is "98". That is, it is determined that there is no adjacency relationship between the two links. In addition, the first link (La) is connected with the third link (Lc) on map data because the first link number (Na) is "1" and the third link number (Nc) is "2". What that means is that there is an adjacency relationship between the two links.

0087When the processing of step 1251 is executed with acceptance on such travel history data, the each second link number (Nb) at travel time 10:00:02 and 10:00:03 is replaced with the first link number (Na), that is, "1" as described in <figref idref="f0006">Fig. 9(b)</figref>. Furthermore, the second link number (Nb) at 10:00:04 is replaced with the third link number (Nc), that is "2" as shown in <figref idref="f0006">Fig. 9(b)</figref>.

0088By executing such replacing processing, even if an incorrect link number is allocated for a link which has no relationship with adjacent links (previous/following links), it may be accurately corrected with a link number allocated for a link adjacent to the link in question.

0089Subsequently, the first link number is reset in step 1252. More specifically, the third link number (Nc) is set as the first link number (Na), and the processing in step 1220 is executed as described above.

0090If the first link (La) is not connected with the third link (Lc) on map data, there is no adjacency relationship between the two links, so that "NO" is selected in step 1250. Then it is determined whether there is a link which has adjacency relationship with both of the first link (La) and the second link (Lb) on map data in step 1260 (<figref idref="f0006">Fig. 8</figref>). Hereinafter the link is referred to as a common link (Lab).

0091If the common link (Lab) exists on map data, "YES" is selected in step 1260, and it is determined whether there is only one travel time including the first link number "Na" in step 1261. If more than one travel time including the first link number (Na) exist, "NO" is selected in step 1261 and the link number is replaced in step 1262.

0092For example in <figref idref="f0007">Fig. 10(a)</figref>, travel history data may include "1"s as the first link numbers (Na) at traveling time 10:00:00, 10:00:01, and 10:00:02, "3"s as the second link numbers (Nb) at 10:00:03 and 10:00:04, and "4"s as the third link numbers (Nc) at 10:00:05 and 10:00:06.

0093In this example, the first link number (Na) is "1" and the second link number (Nb) is "3". Thus there is a common link (Lab) including link number "2" on map data and further the common link (Lab) has adjacency relationship with both of the first link (La) and the second link (Lb). In addition, in this example, more than one travel time including the first link number (Na) exist.

0094When the processing of step 1262 is executed with acceptance on such travel history data, the first link number (Na) at travel time 10:00:02 is replaced with the link number allocated for the common link (Lab), that is, "2" as described in <figref idref="f0007">Fig. 10(b)</figref>.

0095By executing such replacing processing, even if a link number is missing, a link number allocated for a common link "Lab" may be appropriately applied.

0096Subsequently, the first link number is reset in step 1263. More specifically, the second link number (Nb) is set as the first link number (Na), and the processing in step 1220 is executed as described above.

0097Furthermore, if only one travel time including the first link number (Na) exists, "YES" is selected in step 1261, and the link number is replaced in step 1264.

0098For example in <figref idref="f0007">Fig. 11 (a)</figref>, travel history data may include link number "1"s at traveling time 10:00:00 and 10:00:01, "2" at 10:00:02, "3" as the first link number (Na) at 10:00:03, "5"s as the second link numbers (Nb) at 10:00:04 and 10:00:05, and further "6" as the third link number (Nc) at 10:00:06.

0099In this example, the first link number (Na) is "3" and the second link number (Nb) is "5". Thus it is determined that there is a common link (Lab) including link number "4" on map data and the common link (Lab) has adjacency relationship with both of the first link (La) and the second link (Lb). In addition, in the example, only one travel time including the first link number (Na) exists.

0100When the processing of step 1264 is executed with acceptance on such travel history data, the link number at travel time 10:00:01 is replaced with link number "2" which continuously appears after the link number in question among the travel history data as described in <figref idref="f0007">Fig. 11 (b)</figref>. Then the link number at travel time 10:00:02 is replaced with link number "3" which continuously appears after the link number in question among the travel history data as described in <figref idref="f0007">Fig. 11 (b)</figref>. Furthermore, the link number at travel time 10:00:03 is replaced with link number "4" which continuously appears after the link number in question among the travel history data as described in <figref idref="f0007">Fig. 11 (b)</figref>.

0101By executing such replacing processing, even if a link number is missing, a link number allocated for a link which is adjacent to the missing link may be appropriately used.

0102Subsequently, the first link number is reset in step 1265. More specifically, the second link number (Nb) is set as the first link number (Na), and the processing in step 1220 is executed as described above.

0103If the common link (Lab) does not exist on map data, "NO" is selected in step 1260, and it is determined whether there is a link which has adjacency relationship with both of the first link (La) and the third link (Lc) on map data in step 1270. Hereinafter the link is referred to as a common link (Lac).

0104If such common link "Lac" exists, "YES" is selected in step 1270, and the link number is replaced in step 1271.

0105For example in <figref idref="f0007">Fig. 12(a)</figref>, travel history data may include "1"s as the first link numbers (Na) at traveling time 10:00:00 and 10:00:01, "98"s as the second link numbers (Nb) at 10:00:02 and 10:00:03, and "3"s as the third link numbers (Nc) at 10:00:04, 10:00:05, and 10:00:06.

0106In this example, the first link number (Na) is "1" and the third link number (Nc) is "3". Thus it is determined that there is a common link (Lac) including link number "2" on map data and further the common link (Lac) has adjacency relationship with both of the first link (La) and the third link (Lc).

0107When the processing of step 1271 is executed with acceptance on such travel history data, the link numbers at travel time 10:00:02 and 10:00:03 are replaced with the link number allocated for the common link (Lac), that is, "2" for each as described in <figref idref="f0007">Fig. 12(b)</figref>.

0108By executing such replacing processing, even if an incorrect link number is allocated for a link which has no relationship with adjacent links, it may be accurately corrected with a link number for a link adjacent to the link in question.

0109Subsequently, the first link number is reset in step 1272. More specifically, the third link number (Nc) is set as the first link number (Na), and the processing in step 1220 is executed as described above.

0110If the common link (Lac) does not exist on map data, "NO" is selected in step 1270, and it is determined whether there is an adjacency relationship between the second link (Lb) and the third link (Lc) in step 1280.

0111If the second link (Lb) is not connected with the third link (Lc) on map data, "NO" is selected in step 1280 because there is no adjacency relationship between the two links. Then the link number is reset in step 1281, that is, the third link number (Nc) is set as the second link number (Nb) while a link number which continuously appearing after the replaced second link number (Nb) is set as the third link number (Nc) among travel history data. After that, it is again determined whether there is an adjacency relationship between the second link (Lb) corresponding to the second link number (Nb) and the third link (Lc) corresponding to the third link number (Nc) as set in step 1280.

0112If there is an adjacency relationship between the second link (Lb) and the third link (Lc), "YES" is selected in step 1280 and the first link number is reset in step 1282. More specifically, the third link number (Nc) is set as the first link number (Na), and the processing in step 1220 is executed as described above.

0113If there is no link number which continuously appears after the second link number (Nb) and further if the second link (Lb) is adjacent to a destination for the travel history data, "NO" is selected in step 1230 (<figref idref="f0005">Fig. 7</figref>), and a routine of travel history data correcting processing 1200 is terminated.

0114After that, it is determined whether all travel history data is corrected in step 1300 (<figref idref="f0004">Fig. 6</figref>). If correcting processing for all travel history data has not been terminated yet, "NO" is selected and then the processing in step 1100 and the routine of travel history data correcting processing 1200 are executed. The processing in step 1100 and the routine of travel history data correcting processing 1200 are repeated until the correcting processing for all travel history data has been completed.

0115When the correcting processing for all travel history data has been completed, "YES" is selected in step 1300. Subsequently, in step 1400, the corrected travel history data is stored. The travel history data corrected in the routine of travel history data correcting processing 1200 is stored in a database of the memory 114.

0116Then the controller 13 searches for a guidance route based on a request for display by the input unit 12. During the guidance route searching processing, the controller 13 executes, for example, route search, traffic information display, and so on, based on the corrected travel history data which is stored in the database of the memory 114. Therefore, after the correction, a reliable route may be searched and traffic information may be correctly displayed with using the dependable travel history data.

0117Note that the second embodiment of the present invention is not limited to the details described above, but various modifications are possible without departing from the spirit and the scope of the present invention. <ol id="ol0002" compact="compact"><li>1) A link number replacing processing is not particularly limited to the way as described in step 1251. If the first link (La) is not connected with the second link (Lb) on map data, in other words, there is no adjacency relationship between the two links, but if the first link (La) has an adjacency relationship with the third link (Lc); that is, provided that there is an incorrect link number between adjacency related two links with each other, it may be possible to replace half of the second link numbers (Nb) which are close to the first link (La) with the first link number (Na) for each and to replace the other half of the second link numbers with the third link number (Nc) for each.</li></ol>

0118In this manner, for example in <figref idref="f0006">Fig. 9(a)</figref>, if odd number of second link numbers (Nb) exist in one group, it is possible to replace the middle link number in the group (which corresponds to the travel time 10:00:03) with the first link number (Na). <ul id="ul0001" list-style="none" compact="compact"><li>2) A link number replacing processing is not particularly limited to the way as described in step 1262. If there is no adjacency relationship either between the first link (La) and the second link (Lb) or between the first link (La) and the third link (Lc) on map data, and if a common link (Lab) which is adjacent to both of the first link (La) and the second link (Lb) exists, and further if more than one travel history data including the first link number (Na) exist; that is, provided that a necessary link number allocated for a common link (Lab) is missing between the first link number (Na) and the second link number (Nb), it is possible to replace the link number which should be allocated for the common link (Lab) with the link number at the last travel time relevant to the first link (La) .</li><li>3) In step 1264, if the first link (La) and the second link (Lb) are not adjacent, the first link (La) and the third link (Lc) are not adjacent, a common link (Lab) which is adjacent to both of the first link (La) and the second link (Lb) exists, and if only one travel history data including the first link number (Na) exists, a link number that appears before the first link number with a plurality of travel history data may be referenced and used to assign the missing link numbers. For example, as shown in <figref idref="f0007">Figs. 11(a) and 11(b)</figref>, a necessary link number "4" for a common link (Lab) is missing between the first link number "3" and the second link number "5", and there is only one travel history data for the first link "3" (i.e., 10:00:03). The link which appears before the first link and which has more than one travel history data, may have the link number for the last travel history data increased, and the first link adjusted accordingly. Thus, as shown in <figref idref="f0007">Figs. 11 (a) and 11 (b)</figref>, the link number "1" is the first link that appears before the first link number "3" having more than one travel history data, 10:00:01 and 10:00:02. The last travel history data is for link number "1" is increased to link number "2" and the remaining links "2" and the first link "3" are each increased by one accordingly.</li><li>4) A link number replacing processing is not particularly limited to the way as described in step 1271. If there is no adjacency relationship either between the first link (La) and the second link (Lb) or between the first link (La) and the third link (Lc) on map data, and if there is no common link (Lab) which is adjacent to both of the first link (La) and the second link (Lb), and further if a common link (Lac) which is adjacent to both of the first link (La) and the third link (Lc) is found; that is, provided that a necessary link number allocated for a common link (Lac) is missing between the first link number (Na) and the third link number (Nc) and an incorrect link number exists instead, it is possible to replace the second link number (Nb) with the link number allocated for the common link (Lac).</li></ul>

0119For example, as shown in <figref idref="f0007">Fig. 12(a)</figref>, if a first link number "1" and a second link number "98" are not adjacent, a first link number "1" and a third link number "3" are not adjacent, and a common link number "2" is found which is adjacent to both the first and the third link, the second link number "98" may be replaced with the common link number "2". Accordingly, as shown in <figref idref="f0007">Fig. 12(b)</figref>, the non-adjacent link number "98" may be replaced with the adjacent link number "2" and each of the first link "1", the replaced second link "2" and the third link "3" will be correctly adjacent and in order.

0120The travel history data correction apparatus related to the second embodiment of the invention, comprising; a storage means for storing vehicle travel data taken in the past as travel history data associated with a plurality of link numbers; an adjacency condition detection means (1240, 1250) for detecting adjacency relationships among the plurality of link numbers, and a replace means (1251, 1262, 1264, 1271)for replacing a link number allocated for a link which has no relationship with adjacent links with at least one link number allocated for a link which has a relationship with adjacent links based on the detection by the adjacency condition detection means.

0121By executing such replacing processing, an incorrect link number allocated for a link which has no relationship with adjacent links may be accurately corrected with at least one link number allocated for a link which has a relationship with adjacent links. Therefore, after the correction, a reliable route may be searched and traffic information may be correctly displayed with using the dependable travel history data.

0122Further the travel history data correction apparatus related to the second embodiment of the invention comprising a current position detection means (11) for detecting a current position, wherein the storage means may store a link number corresponding to the current position as travel history data.

0123Further the travel history data correction apparatus according to the second embodiment of the invention, wherein that the storage means may store vehicle travel data taken in the past as travel history data associated with a plurality of link numbers as well as times to pass through the links, and then the replace means may, if there is a link which has no relationship with adjacent links, replace the link number with at least one link number allocated for a link which has a relationship with adjacent links based on a time to pass through the link.

0124Further the travel history data correction apparatus related to the second embodiment of the invention, comprising: a storage means (14) for storing vehicle travel data taken in the past as travel history data associated with a plurality of link numbers; a first adjacency condition detection means (1240) for detecting on the travel history data whether there is an adjacency relationship between a first link (La) which is allocated a first link number (Na) and a second link (Lb) which continuously appears after the first link number and which is allocated at least one second link number (Nb); a second adjacency condition detection means (1250) for detecting on the travel history data whether there is an adjacency relationship between the first link and a third link (Lc) which continuously appears after the second link number and which is allocated a third link number (Nc); and a replace means (1251) for replacing, if the first adjacency condition detection means detects no relationship but the second adjacency condition detection means detects a relationship, the second link number with at least one first link number and/or third link number.

0125By executing such replacing processing, an incorrect link number allocated for a link which has no relationship with adjacent links may be accurately corrected with at least one previous and/or following link number. Therefore, after the processing, a reliable route may be searched and traffic information may be correctly displayed with using the dependable travel history data.

0126Furthermore, the travel history data correction apparatus according to the second embodiment of the invention wherein the second adjacency condition detection means detects whether there is an adjacency relationship between the first link and the third link, comprises, a first common link detection means (1260) for detecting whether there is a first common link (Lab) which connects with both of the first link and the second link, and another replace means (1262, 1264) for replacing a link number at a last time for the first link with a link number allocated for the first common link if both of the first adjacency condition detection means and the second adjacency condition detection means detect no relationship and further if the first common link is detected .

0127By executing such replacing processing, even if a link number is missing, a link number allocated for a common link may be appropriately used.

0128Additionally, the travel history data correction apparatus related to the second embodiment of the invention includes a number of data detection means for detecting whether there is only one travel history data including the first link number and a storage means for storing vehicle travel history as travel history data in relationship to a plurality of link numbers and travel times. If a first link (La) and a second link (Lb) are not adjacent, the first link (La) and the third link (Lc) are not adjacent, a common link (Lab) which is adjacent to those of the first link (La) and the second link (Lb) exists, and only one travel history data including the first link number (La) exists, the controller 13 may reference a link number that appears before the first link number and has a plurality of travel times (travel history data, to assign missing link numbers). For example, as shown in <figref idref="f0007">Figs. 11(a) and 11(b)</figref>, a necessary link number "4" for a common link (Lab) is missing between the first link number "3" and the second link number "5", and there is only one travel history data for the first link "3" (i.e., 10:00:03). The controller may increase the link number for the last travel history data of a link which appears before the first link and which has more than one travel history data, and may adjust the following link numbers accordingly. Thus, as shown in <figref idref="f0007">Figs. 11(a) and 11(b)</figref>, the link number "1" is the first link that appears before the link number "3" having more than one travel history data, 10:00:01 and 10:00:02. The last travel history data is for link number "1" is increased to link number "2" and the remaining links "2" and the first link "3" are each increased by one accordingly.

0129By executing such replacing processing, even if a link number is missing, a link number adjacent to the missing link number may be appropriately used.

0130Further the travel history data correction apparatus related to the second embodiment of the invention, wherein the second adjacency condition detection means detects whether there is an adjacency relationship between the first link and the third link, the first common link detection means detects whether there is a first common link which connects with both of the first link and the second link, a second common link detection means (1270) detects whether there is a second common link (Lac) which connects with both of the first link and the third link, and a replace means (1271) replaces a link number for the second link with a link number allocated for the second common link, provided that no relationship is found by both of the first detection and the second detection, that no common link is detected by the first common link detection, and further that a common link is found by the second common link detection.

0131By executing such replacing processing, an incorrect link number allocated for a link which has no relationship with adjacent links may be accurately corrected with a link number allocated for a link adjacent to the link in question.

0132In addition, a travel history data correction method related to the second embodiment of the invention, wherein that vehicle travel data taken in the past is stored as travel history data associated with a plurality of link numbers, and if there is a link which has no relationship with adjacent links, the link number is replaced with at least one link number allocated for a link which has a relationship with adjacent links in view of adjacency relationships among the plurality of link numbers.

0133By executing such replacing processing, an incorrect link number allocated for a link which has no relationship with adjacent links may be accurately corrected with at least one link number allocated for a link which has a relationship with adjacent links.

0134In addition, a travel history data correction method related to the second embodiment of the invention, wherein that vehicle travel data taken in the past is stored as travel history data associated with a plurality of link numbers, detects that there is no adjacency relationship between the first link (La) including the first link number (Na) and the second link (Lb) including at least one second link number (Nb) which appears right after the first link number, further detects that there is an adjacency relationship between the first link and the third link (Lc) including the third link number (Nc) which appears right after the second link number, and replaces the second link number with at least one first link number and/or third link number on travel history data.

0135By executing such replacing processing, an incorrect link number allocated for a link which has no relationship with adjacent links may be accurately corrected with at least one previous and/or following link number.

0136Note that the reference numerals within the parentheses of the above respective means show the corresponding relation with concrete means described in the second embodiment.

0137While various features have been described in conjunction with the exemplary embodiments outlined above, various alternatives, modifications, variations, and/or improvements of those features may be possible. Accordingly, the exemplary implementations of the invention, as set forth above, are intended to be illustrative. Various changes may be made without departing from the scope of the invention.

0138As described above, a navigation apparatus and a navigation method execute a merge processing for various kinds of traffic information data in accordance with established data precision priorities. The apparatus and method calculate average time difference between accumulated data and current data relevant to a predetermined area, set priorities for accumulated data based on the calculated average time difference, and then merge the accumulated data for the area in accordance with established priorities for the area.