JPH09280880A - Route calculation device and route calculation method - Google Patents

Abstract

(57) Abstract: To provide a route calculation device capable of easily calculating a plurality of routes having a difference as much as possible. SOLUTION: A plurality of time zones are stored in a use table for each link constituting road map data, and when a calculation start link is determined (step S1), a plurality of time zones specified in the use table are acquired. Then (step S2), the statistical link cost information related to each of the acquired time zones is referred to from the memory contents, and a plurality of routes from the calculation start link to the destination set by the user is calculated. Yes (step S5).

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a route calculating apparatus and method for calculating a plurality of routes from any link constituting route network data of a route providing area to any other link in the same area. It is about.

[0002]

2. Description of the Related Art Conventionally, a vehicle-mounted navigation device that has been developed for displaying the position and orientation of a vehicle on a screen to facilitate traveling of the vehicle has been widely used. The in-vehicle navigation device includes a display, various sensors or GPS.
A vehicle equipped with a receiver (hereinafter referred to as "various sensors, etc."), a road map memory, a computer, etc., based on the position data input from the various sensors and the relationship with the road stored in the road map memory. The position is detected and this vehicle position is displayed on the display together with the road map.

By the way, in such an in-vehicle navigation device, not only the display of the vehicle position and the road map but also various traffic information can be provided to the driver or passenger (hereinafter collectively referred to as "user"). By doing so, a more comfortable driving environment can be provided to the user. Therefore, in order to provide the traffic information to the vehicle-mounted navigation device, it is possible to provide the traffic information to the vehicle-mounted navigation device mounted on the vehicle through the road beacons and communication lines (car phone lines, etc.) installed in various places on the road. Has been done. When receiving the traffic information, the vehicle-mounted navigation device displays the traffic information on the display screen or outputs the sound. Thereby, the latest traffic information can be provided to the user.

On the other hand, in order to select a traveling route from the starting point to the destination, the route from the vehicle's current position (which is regarded as the starting point) to the destination is automatically determined by a computer in response to the user's setting input of the destination. A method of performing a numerical calculation has been proposed (see Japanese Patent Laid-Open No. 5-53504). In this method, the roads or lanes to be calculated are expressed as a series of vectors (this vector is called a "link"), a link close to the starting point (or destination) may be used as the calculation start link, and the destination (or starting point may be The link close to (good) is used as the calculation end link, the road map data stored in the road map memory between them is read out and moved to the work area, and the tree of links starting from the calculation start link is searched in the work area, and the shortest This is a method of obtaining a tree of link costs, successively connecting the link costs of the routes forming this tree, and selecting the route that reaches the calculation end link.

Since the link cost of each link fluctuates from moment to moment depending on traffic conditions on the road, traffic restrictions due to road construction, the presence of accidents, etc., road beacons and communication lines (automobiles) installed at various places on the road. It is currently under consideration to provide the latest link cost information to the vehicle via a telephone line or the like). According to this ground system, the latest link cost information including road congestion, traffic restrictions, and accident information is prepared on the ground system side, and the link cost information is transmitted to the vehicle through a road beacon or a mobile phone. This can assist the vehicle in calculating an optimal route and travel time.

[0006]

However, when the in-vehicle navigation devices of a plurality of vehicles each calculate the optimum route, the link cost information acquired through the road beacon and the link cost of each vehicle are as follows: Since there is no big difference depending on the device, it is expected that multiple vehicles going to the same direction will calculate the same route, only a specific route will be congested, and the destination cannot be reached in the shortest time. It

Therefore, it is desirable for the vehicle-mounted navigation device to calculate a plurality of routes that are as different as possible in order to reach the same destination, and let the user select and select the plurality of routes. In order to solve such a problem, the shortest cost between an arbitrary point on the network and the end point is calculated, and the partial route from the start point is calculated based on the sum of the accumulated cost from the start point and the shortest cost of the remaining routes. , A method of expanding a plurality of routes according to analysis conditions has been proposed (see Japanese Patent Laid-Open No. 5-46590). According to this proposal, it is possible to eliminate a route that largely detours, but it is difficult to obtain a plurality of routes that differ as much as possible because only a large number of routes that are almost the same as the shortest route are obtained.

An object of the present invention is to provide a route calculation device and method which can easily calculate a plurality of routes. Another object of the present invention is to provide a route calculation device and method that can easily calculate a plurality of routes that differ as much as possible.

[0009]

A route calculation device of the present invention statistically collects a road map memory in which road map data is stored and past traffic information associated with each link statistically for each predetermined time element. Traffic information memory that stores the statistical link cost information obtained by processing, for each link that constitutes the road map data, a usage table in which multiple time zones are specified, and a calculation start link is specified, A plurality of time zones specified in this usage table are acquired for the calculation start link, and statistical link cost information relating to each of the acquired time zones or the time zone after each acquired time zone is stored in the traffic information memory. Refer to each of the contents, and based on these statistical link cost information, multiple links from the calculation start link to the destination set by the user Those having a route calculation means for calculating a road, and output means for outputting one or all of the calculated route by the route calculating means (claim 1).

According to the present invention, first, in the usage table,
A plurality of time zones are recorded for each link that constitutes road map data. When the calculation start link is determined, a plurality of time zones specified in the usage table are acquired, and statistical link cost information related to each acquired time zone is referred to from the stored contents of the traffic information memory, and the calculation start is started. It is possible to calculate a plurality of routes from the link to the destination set by the user.

The plurality of time zones to be recorded in the utilization table may be, for example, time zones in which a plurality of time zones are selected at random from a time zone divided in one day or with a certain promise and recorded. It is better to spread these hours as little as possible throughout the day. A plurality of time zones corresponding to one link may be different time zones for different seasons, months, days of the week, and weekdays / holidays, and are the same regardless of seasons, months, days of the week, and weekdays / holidays. It may be a time zone.

The route calculation device of the present invention comprises a road map memory in which road map data is stored, a communication means for acquiring the latest link cost information from the outside, and latest link cost information acquired by the communication means. And a traffic information memory that stores statistical link cost information obtained by statistically processing the past traffic information associated with each link for each predetermined time element, and for each link that constitutes road map data. , When a usage table in which a plurality of time zones are specified and a calculation start link are specified, a plurality of time zones specified in this usage table are acquired for the calculation start link, and the acquired time zones or respectively The statistical link cost information or the latest link cost information relating to the time period after the acquired time period is changed from the stored contents of the traffic information memory. The route calculation means for calculating a plurality of routes from the calculation start link to the destination set by the user based on these statistical link cost information or the latest link cost information, and the route calculation means. And an output means for outputting any or all of the calculated routes (claim 2).

According to the present invention, when calculating routes, a plurality of routes can be provided by using the travel time based on the latest link cost information from the outside.
A route calculation device according to the present invention is the route calculation device according to claim 1 or 2, wherein when a plurality of routes are calculated by the route calculation means, a difference between the routes is checked, and only the routes having a large difference from each other are checked. The route is selected and the selected route is displayed (claim 3).

This is because it is meaningless to provide a plurality of routes to the user if they are similar routes. The route calculation device of the present invention is the route calculation device according to claim 1, wherein the route travel time is calculated by referring to the statistical link cost information along the route calculated by the route calculation means. It further comprises means, and the output means also outputs the route travel time (claim 4).

When the travel time is provided to the user together with the route, the travel time based on the statistical link cost information can be provided, so that the travel time with high reliability based on the past performance can be provided. it can. A route calculation device according to the present invention is the route calculation device according to claim 1,
By referring to the communication means for obtaining the latest link cost information from the outside and the statistical link cost information along with the route calculated by the route calculation means and the latest link cost information obtained through the communication means, It further has travel time calculation means for calculating travel time, and the output means also outputs route travel time (claim 5).

When the travel time is provided to the user together with the route, the travel time based on the latest link cost information from the outside can be provided, so that the travel time in consideration of the current situation can be provided. A route calculation device of the present invention is the route calculation device according to claim 2, wherein the statistical link cost information and the latest link cost information along the route calculated by the route calculation means are referred to,
It further has travel time calculating means for calculating the route travel time, and the output means also outputs the route travel time (claim 6).

When the travel time is provided to the user together with the route, the travel time can be provided based on the latest link cost information from the outside, so that the travel time can be provided in consideration of the current situation. A route calculation device according to the present invention is the route calculation device according to claim 4, wherein the route travel time calculated by the travel time calculation means is multiplied by a fixed number (1 + b) (b is a positive real number). A route maximum travel time calculating means for calculating time is further provided, and the output means also outputs the route maximum travel time (claim 7).

The route calculation device of the present invention is defined by claim 5 or 6.
The route calculation device described in claim 1, wherein the route maximum travel time calculating unit calculates a maximum route travel time by multiplying the route travel time calculated by the travel time calculating unit by a fixed number (1 + a) (a is a positive real number). Further, the output means also outputs the maximum travel time of the route (claim 8). According to these inventions, the maximum travel time estimated more than usual is displayed, so that it is possible to indicate to the user that the maximum travel time is required.

Further, the route calculation method of the present invention is described in claim 1.
Alternatively, it is a route calculation method according to the same invention as the route calculation device according to claim 2 (claims 9 and 10).

[0020]

Embodiments of the present invention will be described below in detail with reference to the accompanying drawings. FIG. 1 is a schematic diagram of a system for providing traffic information to a vehicle-mounted navigation device to which the route calculation device of the present invention is applied. This traffic information providing system includes a road beacon A installed on each road in the traffic information providing area and the road beacon A.
And an information center C connected via a communication line (public line or dedicated line) B.

The on-road beacon A may be either a radio wave beacon or an optical beacon. Instead of the on-road beacon A, for example, a communication device or a transmission device used for an automobile / cellular phone network or an FM multiplex broadcasting network is used. You may apply. The information center C stores link traffic information corresponding to a relatively coarse first route network having a link connecting major intersections in the traffic information providing area as a constituent unit. This link traffic information corresponds to each link with the latest traffic information that changes from moment to moment acquired by, for example, a vehicle detector, a camera, a helicopter navigating over the sky, or a traffic information collecting vehicle actually traveling on the road. It was created and created.

The link traffic information includes, for example, a travel time, which is a time required for a vehicle to travel on a road corresponding to a link, a content corresponding to a congestion degree, or a congestion length. For example, when a traffic jam occurs, the travel time or the traffic length is relatively long, and the traffic congestion degree is relatively increased. When the traffic jam is resolved, the travel time or the traffic congestion length is relatively short, and the traffic congestion degree is relatively high. Be made smaller. Further, when an accident or the like makes the vehicle impassable, the travel time is infinite. The same applies when there are traffic restrictions. The link traffic information is given to the on-road beacon A via the communication line B at regular intervals (for example, 5 minutes). Each of the divided fixed times is called a "time zone". For example, if it is divided every 5 minutes, there are 288 time zones per day.

When the link traffic information is given via the communication line B, the road beacon A transmits the link traffic information to the vehicle. FIG. 2 is a block diagram showing an electrical configuration of a vehicle-mounted navigation device mounted on a vehicle. The vehicle-mounted navigation device 1 is provided with an azimuth sensor 5 that detects the amount of change in the direction of the vehicle and a distance sensor 6 that detects the amount of movement of the vehicle. As the direction sensor 5, for example, an optical fiber gyro, a vibration gyro, a gyro such as a gas rate gyro, or a geomagnetic sensor can be applied. Further, as the distance sensor 6, for example, a rotation speed sensor that detects the rotation speed of the tire wheel or the rotor can be applied. The direction sensor 5 and the distance sensor 6
Each output of the above is given to the vehicle position detection unit 14 in the vehicle-mounted navigation device body 1.

The vehicle position detector 14 obtains the traveling direction of the vehicle based on the output of the direction sensor 5, and
The traveling distance of the vehicle is obtained based on the output of the distance sensor 6. Precise initial position data of the vehicle is given to the vehicle position detection unit 14 by the user before the vehicle starts, and the vehicle position detection unit 14 receives the preset initial position data and the The current position of the vehicle is detected based on the accumulation of the traveling direction and the traveling distance. The detection of the current position of the vehicle is repeated at regular intervals (for example, 1 second).

Instead of the direction sensor 5, the distance sensor 6 and the vehicle position detector 14, or the direction sensor 5,
Along with the distance sensor 6 and the vehicle position detector 14, a GPS (Global Posioning System) that navigates in an orbit around the earth.
) A GPS receiver that detects the current position of the vehicle based on the propagation delay time of GPS radio waves transmitted from the satellite may be adopted.

The vehicle position detector 14 also corrects the detected current position of the vehicle by so-called map matching processing (see, for example, Japanese Patent Laid-Open No. 63-148115). That is, the degree of similarity between the traveling locus of the vehicle detected based on the outputs of the azimuth sensor 5 and the distance sensor 6 and the road stored in the on-vehicle map dedicated disk D is collated, and according to the result. The traveling path of the vehicle is corrected on the road.

The current position data of the vehicle corrected by the map matching process is given to the controller 16. The controller 16 is a control center of the vehicle-mounted navigation device body 1 and includes a CPU 161, an SRAM 162, and a DRAM 163. Controller 16
When the current position data of the vehicle is given from the vehicle position detection unit 14, reads out the road map data for display from the vehicle-mounted map dedicated disk D via the memory control unit 11 and the CD drive 2. The read road map data for display and the present location data thus read are given to the display controller 12. When the display road map data and the current position data are given, the display control unit 12 superimposes a car mark representing the current position of the vehicle on the road map to display a liquid crystal display device, a plasma display device or C.
It is displayed on the display 3 configured by RT. Also,
The guidance information along the route is provided by voice through the speaker M.

In addition to the display road map data, the on-vehicle map dedicated disk D stores route calculation road map data, a correspondence table, and a usage table. The road map data for route calculation divides the road map (including highway national roads, motorways, other national roads, prefectural roads, city roads of ordinance-designated cities, and other living roads) into meshes, and each mesh A relatively fine second route network consisting of a combination of nodes corresponding to intersections of roads and links that are vectors connecting each node is used as a highway / national road map, general road map, and detailed map. It is divided into three layers and stored for each time zone. The stored contents are associated with the fixed link cost, the statistical link cost T _S (t) for each time zone, the link length for each link, the coordinates of the start point node and the end point node of the link, and the like. .

The statistical link cost T _S (t) is created in advance and is the link traffic information for each time zone provided in the traffic information providing area in the past certain period through the road beacon A. A value that is averaged and stored for each one or a plurality of combinations of seasons, months, days of the week, weekdays / holidays (these are referred to as time elements), and written in the vehicle-mounted map dedicated disk D. Is.

The method of creating the statistical link cost T _S (t) will be described in detail. It can be considered that the past link traffic information is collected by using, for example, a traffic information facsimile service. In addition to the traffic information facsimile service, a traffic information providing service by radio broadcasting or a cable television (CATV) providing service provided by the Road Traffic Information Center can be used.

The case of using the traffic information facsimile service will be described in detail. The traffic information facsimile service is to provide traffic information such as traffic jam information, travel time, and no-traffic zone shown on a map by a facsimile. is there. The creator classifies the traffic information provided by facsimile by time zone, season, month, day of the week, weekday / holiday, and statistically organizes it. For example, when traffic congestion information is used as an example of traffic information, the traffic congestion information is statistically processed, and the result is organized as statistical traffic congestion information data.

In addition to the road map data, the map-dedicated disk D also has a correspondence table showing a correspondence relationship between the links associated with the traffic information transmitted from the road beacon A and the links of the road map data. It is stored (see FIG. 4). This correspondence can be classified as follows because the link associated with the traffic information transmitted from the on-road beacon A is generally a constituent unit of the route network that is coarser than the link of the road map data. FIG. 3 (a)
The case where the link L _Ka transmitted from the road beacon A and the link L _Na of the road map data have a one-to-one correspondence is shown. In FIG. 3B, one link L _Kb transmitted from the road beacon A is linked to a plurality of road map data links L _Nb1 , L _Nb2 ,
_.. , L _Nbi are included, FIG. 3C shows a case where there is a link L _N of road map data that does not correspond well to the link L _K transmitted from the road beacon A.
Of these, the correspondence table represents the correspondence relationship in the cases of FIGS. 3A and 3B, and FIG. 4 shows specific examples of the correspondence table. Since there is no direct correspondence in the case of FIG. 3C, the description of the correspondence table is omitted in this embodiment.

The utilization table records the number of the effective time zone Z _k in association with the link of the road map data.

[0034]

[Table 1]

The effective time zone Z _k is selected from a plurality of “time zones” divided per day. The effective time zone Z _k is the link cost of the calculation start link.
The statistical link cost T _S (t) of _k is adopted, and the route is searched for the link connected from it. For example, since the time zones such as numbers 2, 9, 14, and 32 are recorded for the 251st link, the number 2 is set as the statistical link cost T _S (t) of the calculation start link in the route search.
The statistical link cost T _S (t) in the time zone of is used to perform route search for the link connected to it, and the statistical link cost T _S (t) in the time zone of number 9 is used to route for the link connected from The search is performed, the statistical link cost T _S (t) in the time zone of number 14 is adopted, the route is searched for the link connected to it, and so on.

A remote controller key (hereinafter simply referred to as “remote control key”) 4 for inputting a destination and various calculation conditions is connected to the controller 16 via an input control section 13. The remote control key 4 includes, for example, a "joystick / set key" for scrolling a map, setting a position, and selecting a menu, a "map key" for displaying a road map screen centered on a car mark indicating the current location, a road map "Scale key" for enlarging or reducing the display scale, "Rotation key" for selecting whether to display the traveling direction of the vehicle at the top or the north of the map at the top, and whether to display the traveling path of the vehicle "Track key" to switch, menu screen such as "route key", "destination setting", "route setting" that can input the route calculation instruction signal with one touch when you want to calculate the shortest time route from the current location to the destination "Menu key" to be displayed, when operating the menu 1
Various keys (none of which are shown) such as a "return key" for returning to the previous screen are provided.

The controller 16 allows the user to use the remote control key 4 to determine the destination and various calculation conditions (whether to give priority to the toll road, whether to give priority to the use of the ferry, or whether to pass through the transit point, Etc.) is input, the input destination data and the like are stored in the SRAM 162, and the route calculation road map data is read from the on-vehicle map dedicated disk D and detected by the destination and vehicle position detection unit 14. The shortest time route between the links respectively close to the current location is calculated by using, for example, the Dijkstra method or the potential method. The calculated shortest time route is displayed on the display 3
For example, a broken line is superimposed and displayed on the road map displayed in FIG.

Here, the potential method is the following method. That is, the link close to the departure place (may be the destination) is the calculation start link, the link closest to the destination (may be the departure place) is the calculation end link, and the calculation is performed based on the various calculation conditions input by the user. Search for all links in a given map area starting from the starting link. At this time, the statistical link cost T _S (t) or the travel time predicted value T _P (t) (described later) of each link is sequentially added,
The process of discarding the route that is not the shortest and leaving only the route that realizes the shortest route is repeated. As a result, a tree of routes consisting of only the shortest route is finally obtained, so that the shortest time route can be obtained by tracing the route from the calculation end link to the calculation start link in reverse.

A beacon receiver 7 is also connected to the controller 16. When the vehicle enters the transmission area of the road beacon A (see FIG. 1) and the latest series of link traffic information transmitted from the road beacon A is received by the beacon receiver 7, the CPU 161 links the link. The traffic information is given to the SRAM 162 and held therein. CPU1
In 61, when the shortest time route is calculated by the above method, if the link traffic information is held in the SRAM 162, the statistical link cost T _S (t) included in the route calculation road map data is Predicted link cost T considering the link cost (hereinafter referred to as "real-time link cost") obtained using the link traffic information.
_P (t) is obtained and a plurality of routes are calculated based on this predicted link cost T _P (t). When the link traffic information is not stored in the SRAM 162, the statistical link cost T
Calculate multiple routes using _S (t) as is.

FIGS. 5 to 8 are flowcharts for explaining the calculation processing of a plurality of routes in the vehicle-mounted navigation device 1. The user operates the remote control key 4 to input a destination or a waypoint (hereinafter, typically referred to as “destination”) before or during traveling. Controller 1
6 uses the link closest to the current location detected by the vehicle position detector 14 as the calculation start link and the link closest to the destination as the calculation end link (step S1 in FIG. 5).

Next, referring to the current time, the departure time zone Z ₀ to which the current time belongs is specified (step S2). Then, referring to the above-mentioned usage table, the time zones after the departure time zone Z ₀ to which the current time belongs, which correspond to the calculation start link, are sequentially checked (step S3), and the hit time zone, that is, the effective time zone Z _k. Are specified (step S4).

Then, the controller 16 causes the calculation start phosphorus.
Search for all links in the specified map area starting from
You. In this search, first, the statistical link cost T
_SExplain how to calculate multiple routes using (t) as it is.
Link traffic information is stored in SRAM 162.
And the link obtained using the link traffic information
Predicted link cost considering the real-time link cost of
To T_P(t) is calculated, and this predicted link cost T _Pbased on (t)
A method of calculating a plurality of routes will be described below. <Statistical link cost T_SUsing (t) as it is,
Method of calculating road> In this method,
Link costs vary depending on the link.
Statistics link cost T belonging to_Susing (t)
You.

More specifically, of the effective time zones Z _k , the earliest effective time zone Z ₁ is first selected, and the link cost of the calculation start link is calculated as the statistical link cost T _S (of the effective time zone Z ₁ ). t). Next, regarding the links following this calculation start link, it is considered that the vehicle will arrive at the effective time zone that is later than the effective time zone Z _{1 of the} calculation start link by the link cost of the calculation start link, that is, the vehicle. The time zone is determined and the statistical link cost T _S (t) belonging to the valid time zone is used as the link cost.

For links connected to this, the link costs are similarly added, and the statistical link cost T _S (t) in the time zone in which the vehicle is supposed to reach the link is used as the link cost. The route is searched for by using (step S5). It should be noted that instead of using the statistical link cost T _S (t) in the time zone in which the vehicle is likely to reach the link as the link cost, the calculation start link is uniformly applied to all links in the predetermined map area. statistics link cost T _S effective time zone Z ₁ and the same time band Z ₁ of (t) may be used as a link cost. <Real-time link cost and statistical link cost T
Method to calculate multiple routes by using _S (t) ＞ If the route is calculated by using the real-time link cost as it is, the instantaneous fluctuation of the real-time link cost will be too severe. Therefore, the predicted link cost T _P (t) is obtained by using the exponential smoothing method in which the statistical link cost T _S (t) is added, and the predicted link cost T _P (t) is used as the link cost within the predetermined map area. To search the route.

In this exponential smoothing method, when the route calculation target link and the link obtained from the outside have a one-to-one correspondence as shown in FIG. 3 (a), the link obtained from the outside is The corresponding statistical link cost T _S (t) is stored in SRAM
162, and the statistical link cost T _S (t)
The error prediction value e _t required to correct the error is obtained. Although the initial value of the error prediction value e _t is set to 0, the instantaneous fluctuation of the real-time link cost is too severe, and considering the purpose of smoothing and using this, the predicted link cost T _P (t) of It is necessary to absorb instantaneous fluctuations. Therefore, a weighted average is taken as the error prediction value e _t in consideration of the error prediction value e _t-1 adopted based on the real-time link cost of the same link obtained from the outside.

More specifically, the prediction link cost
To T_PWhen (t) is obtained, the predicted link cost T_P(t)
And the statistical link cost T of the link obtained from the outside
_SFind the difference from (t). Then held in memory
The predicted link cost T of the previous point of the same link _P(t−
1) read out, statistical link cost T of this link_S(t)
And the error prediction value e_t-1Then, the following equation (1)
Thus, a new error prediction value e_tTo update.

E _t = α (T _P (t) −T _S (t)) + (1−α) e _t−1 (1) However, in the formula (1), α (0 <α < 1) is a smoothing index, and if it is close to 0, the past error prediction value e _t-1
If the value is close to 1, the current predicted link cost T _P (t) is weighted. For example, α = 0.8. Using the error prediction value e _t thus obtained, the predicted link cost T _P (t) corresponding to the route calculation target link is calculated as in the following equation (2).

T _P (t) = e _t + T _S (t) (2) In the above description, attention was paid to the difference between the predicted link cost and the statistical link cost. You may pay attention to the ratio with the link cost. In this case, the equation (3) (4), respectively as follows (the initial value of e _t is 1).

E _t = α (T _P (t) / T _S (t)) + (1−α) e _t-1 (3) T _P (t) = e _t · T _S (t) (4) In addition, as shown in FIG. 3 (b), when the link is included as a part of the link obtained from the outside,
Predicted link cost T _P (t) based on equation (2) or equation (4)
After the above is calculated, the calculation of the following formula (5) is performed to calculate the predicted link cost T _P (t) corresponding to the route calculation target link. However, in the following equation (5), d _Ni represents the link length of the link _i , and d _K represents the link length of the link obtained from the outside.

(D _Ni / d _K ) × T _P (t) → T _P (t) (5) Predicted link cost T calculated by the equation (2), the equation (4), or the equation (5). _P (t) is held in non-volatile memory.
As described above, since the error prediction value e _t is obtained in order to absorb the instantaneous fluctuation of the real-time link cost, the prediction link cost T obtained by using the error prediction value e _t.
P (t) is a value that reflects the current traffic conditions and suppresses extreme fluctuations in the actual traffic conditions. Therefore, the route in the predetermined map area is searched using the predicted link cost T _P (t) (step S5).

When the route search is completed, the route from the calculation end link to the calculation start link is traced in reverse, and the route L
₁ is specified and stored (step S6). Furthermore, of the effective time zones Z _k hit in the use table, the effective time zone Z ₂ having the next shortest time is selected, and a plurality of routes are calculated using the <statistical link cost T _S (t) as it is. Method> or <method of calculating a plurality of routes by using both the real-time link cost and the statistical link cost T _S (t)>, and the route L ₂ is specified and stored. By repeating this, the effective time zone Z _n (n = 1,2,3, ...
.., m), a plurality of routes L _n (n = 1,2,3, ..., m) are identified. After checking all valid time zones Z _k ,
From step S7 to step S11 (FIG. 6), a plurality of stored routes L _n (n = 1,2,3, ..., M) are sequentially taken out and the difference rate D is checked.

This difference rate D means that each route L _n (n =
1,2,3, ..., m), two arbitrary routes L _i , L _j are extracted, and link costs (for example, statistical link cost T _S (t)) of these are summed up and the route travel time T _i , T _j
Is obtained, and the route travel time T _ij of the overlapping portion of the routes L _i and L _j is further obtained. By using these, it is a function represented by D _ij = 1-2T _ij / (T _i + T _j ). This difference rate D _ij is compared with a threshold value (step S12), and if the difference rate D _ij is smaller than the threshold value (step S13), the route having the longer route travel time is deleted and the process proceeds to step S11. Return and repeat the process for another route. In this way, the difference rate D _ij
Only a route whose value is larger than the threshold value is selected (step S14). All stored routes L _n (n = 1,2,3, ..., m)
When the process is completed (step S15), the process proceeds to step S21 (FIG. 7).

Although the difference D is calculated based on the route travel times T _i , T _j , and T _ij in the above description, it may be calculated based on the route distance. Instead of calculating the difference rate D, the absolute difference (T _i + T _j ) / 2−T _ij may be calculated and compared with the threshold value. After step S21, the link travel time is calculated for the links constituting each selected route (which will be referred to as route L _p ). In calculating this link travel time, the time at which the vehicle is expected to reach the link is determined and the link travel time is calculated. Add costs (this idea is the same as for route search).

First, for one route, the process proceeds in order from the calculation start link (step S22). It is checked whether the predicted link cost T _P (t) has been obtained for the link (step S23). If not obtained, the statistical link cost T _S (t) is adopted and set as the normal travel time (step S24). further,
The normal travel time is multiplied by (1 + b) to obtain the maximum travel time (step S25). The maximum travel time is calculated in order to indicate to the user that the travel time is estimated to be larger than usual. b is reduced as the reliability of the statistical link cost T _S (t) is higher, and is increased as the reliability of the statistical link cost T _S (t) is lower. Usually b
= 0.1 to 0.2.

Predicted link cost T for the link
_{If P} (t) has been obtained, the predicted link cost T _P (t) is adopted as the normal travel time (step S2).
6). Further, the normal travel time is multiplied by (1 + a) to be the maximum travel time (step S27). a is made smaller as the reliability of the predicted link cost T _P (t) is higher,
The predicted link cost T _P (t) is increased as the reliability is lower. Usually, it is set to about a = 0.1 to 0.2.

When the processing is completed for all the links forming one route L _P (step S28), the process proceeds to step S31 (FIG. 8). In step S31, the normal travel times for the route L _p are summed up and set as the route travel time (step S31). In addition, the maximum travel times are summed up and set as the maximum travel time of the route (step S3)
2).

The above-mentioned predicted link cost T_P(t)
In addition to the method of obtaining travel time as a subject,
Strike T_PIgnoring (t), the statistical link cost T_S(t)
It is also possible to calculate the travel time based on only the time. Other sutras
Road L_pAlso, for step S21 and subsequent steps,
Route L_pIs completed (step S3)
3), the obtained route L_PWhether the number exceeds the fixed number c
It is determined (step S34). Exceeds a certain number c
If there is, then c routes (this
To route L_QIs selected) (step S3)
6). All routes L unless the number of c exceeds a certain number_P
To route L _QIs finally selected as (step S35).

Then, the finally selected route L _Q is displayed (step S37). This display shows the route L selected last
May be displayed all at once the _Q, by displaying any one path L _Q, it may be switched to another path L _Q If there is a user request. Also, the route travel time,
The maximum travel time of the route is also displayed (step S38). Of course, in the case of this display, it is desirable to change the display method depending on whether it is the mere route travel time or the maximum route travel time.

Then, guide instruction information corresponding to the route is created. As the contents of the guidance instruction information corresponding to this route, there are various conventionally known ones such as a direction to a destination, a linear distance to the destination, a route distance along the route, and an intersection schematic diagram. Any or all of this information is provided to the user. As a method of providing, characters or arrows may be displayed on the display 3, or voice may be guided from the speaker M.

Although the embodiments of the present invention have been described above, the present invention is not limited to the above embodiments. For example, in the above-described embodiment, the in-vehicle navigation device calculates a plurality of routes. However, Information Center C
It is also possible to use a terrestrial system such as to calculate a plurality of routes and provide them to each vehicle through the beacon A on the road. Alternatively, the user can calculate a plurality of routes using a personal computer installed in an office or the like. You can go.

Other various design changes can be made within the scope of the present invention.

[0062]

As described above, according to the invention of claim 1 or 9, the use table is used to acquire a plurality of time zones specified in the use table, and the acquired time zones are respectively acquired. Using the related statistical link cost information, multiple routes from the calculation start link to the destination etc.
It can be calculated easily. The user can travel by arbitrarily selecting any one of these plural routes.

According to the second or tenth aspect of the invention, the latest link cost information from the outside is acquired, and based on the statistical link cost information or the latest link cost information, the current traffic situation is used. Multiple paths can be obtained. According to the invention as set forth in claim 3, it is possible to obtain a plurality of routes having a difference as much as possible.

According to the invention of claim 4, it is possible to provide a highly reliable travel time based on the past record. According to the invention described in claim 5 or 6, it is possible to provide the travel time reflecting the actual traffic condition based on the latest link cost information from the outside. Claim 7
Alternatively, according to the invention described in 8, it is possible to indicate to the user that it takes a maximum of this time by displaying the maximum travel time estimated more than usual.

[Brief description of drawings]

FIG. 1 is a schematic diagram of a system for providing traffic information to a vehicle-mounted navigation device using a route calculation device of the present invention.

FIG. 2 is a block diagram showing an electrical configuration of a vehicle-mounted navigation device mounted on a vehicle.

FIG. 3 Link L obtained from the outside_KaAnd link L_NaWith
FIG. 3 (a) is a diagram showing a correspondence relationship, which is obtained from outside.
Link L_KaAnd link L_NaIf and correspond one-to-one,
Figure 3 (b) shows one external link L_KbMore than
Link L_Nb1, L_Nb2・ ・ ・ ・ ・ ・ L_NbiIs included
3C, the link L obtained from the outside _KNiu
Link L that does not correspond_NIndicates the presence of.

FIG. 4 is a diagram showing a correspondence table showing a correspondence relation between a link obtained from the outside and the link.

FIG. 5 is a flowchart for explaining a process of calculating a plurality of routes in the vehicle-mounted navigation device.

FIG. 6 is a flowchart for explaining a process of calculating a plurality of routes in the vehicle-mounted navigation device (continuation of FIG. 5).

FIG. 7 is a flowchart for explaining a process of calculating a plurality of routes in the vehicle-mounted navigation device (continuation of FIG. 6).

8 is a flowchart for explaining a process of calculating a plurality of routes in the vehicle-mounted navigation device (sequel to FIG. 7).

[Explanation of symbols]

 A Road beacon B Communication line C Information center D In-vehicle map dedicated disc 1 In-vehicle navigation device 2 CD drive 3 Display 4 Remote control key 5 Direction sensor 6 Distance sensor 7 Beacon receiver 11 Memory control unit 12 Display control unit 13 Input processing unit 14 Vehicle Position detection unit 16 Controller 161 CPU 162 SRAM 163 DRAM 18 Voice control unit

Claims (10)

[Claims] 1. A road map memory storing road map data, and statistical link cost information obtained by statistically processing past traffic information associated with each link for each predetermined time element. When the stored traffic information memory and the usage table in which multiple time zones are specified for each link that makes up the road map data and the calculation start link are specified, the usage start table is specified for this calculation start link. Acquiring a plurality of time zones, the statistical link cost information relating to each of the acquired time zones or the time zones after the respective acquired time zones are respectively referred to from the stored contents of the traffic information memory, and these statistical link cost information are obtained. Route calculation means for calculating a plurality of routes from the calculation start link to the destination set by the user based on An output unit that outputs any or all of the routes calculated by the unit. 2. A road map memory in which road map data is stored, communication means for acquiring the latest link cost information from the outside, latest link cost information acquired by the communication means, and correspondence with each link. The traffic information memory that stores the statistical link cost information obtained by statistically processing the obtained past traffic information for each predetermined time element, and multiple time zones for each link that constitutes road map data When the specified usage table and the calculation start link are specified, multiple time zones specified in this usage table are acquired for the calculation start link, and the acquired time zone or the time after each acquired time zone The statistical link cost information or the latest link cost information related to the time zone of the Either the route calculation means for calculating a plurality of routes from the calculation start link to the destination set by the user based on the total link cost information or the latest link cost information, or the route calculated by the route calculation means Or a output unit for outputting all of them. 3. When a plurality of routes are calculated by the route calculating means, the selecting means further comprises a selecting means for checking a difference between the routes and selecting only a path having a large difference from each other, and the output means is selected by the selecting means. 3. The route calculation device according to claim 1, wherein the route calculation unit outputs the determined route. 4. A travel time calculation unit for calculating a route travel time by referring to statistical link cost information along the route calculated by the route calculation unit, wherein the output unit calculates the route travel time. The route calculation device according to claim 1, wherein the route calculation device outputs the route. 5. A communication means for acquiring the latest link cost information from the outside, statistical link cost information along the route calculated by the route calculation means, and latest link cost information obtained through the communication means. The route calculation device according to claim 1, further comprising: a travel time calculation unit that calculates a route travel time, with reference to the output unit. 6. A travel time calculation unit for calculating a route travel time with reference to statistical link cost information and the latest link cost information along the route calculated by the route calculation unit, further comprising: The route calculation device according to claim 2, wherein the output means also outputs the route travel time. 7. A route maximum travel time calculating means for calculating a route maximum travel time by multiplying the route travel time calculated by the travel time calculating means by a fixed number (1 + b) (b is a positive real number), 5. The route calculation device according to claim 4, wherein the output means also outputs the maximum travel time of the route. 8. A route maximum travel time calculating means for calculating the route maximum travel time by multiplying the route travel time calculated by the travel time calculating means by a fixed number (1 + a) (a is a positive real number), 7. The route calculation device according to claim 5, wherein the output means also outputs the maximum travel time of the route. 9. A road map memory storing road map data, and statistical link cost information obtained by statistically processing past traffic information associated with each link for each predetermined time element. The calculation start link is specified using the stored traffic information memory and the use table in which multiple time zones are specified for each link that constitutes the road map data, and the calculation start link is specified in this use table. A plurality of time zones are acquired, and the statistical link cost information relating to the acquired time zones or the time zones after the acquired time zones are respectively referred to from the stored contents of the traffic information memory, and the statistical link cost information is obtained. Route calculation characterized by calculating a plurality of routes from the calculation start link to the destination set by the user based on Method. 10. A road map memory in which road map data is stored, communication means for acquiring the latest link cost information from the outside, latest link cost information acquired by the communication means, and correspondence with each link. The traffic information memory that stores the statistical link cost information obtained by statistically processing the obtained past traffic information for each predetermined time element, and multiple time zones for each link that constitutes road map data The calculation start link is specified using the specified usage table, and multiple time zones specified in this usage table are acquired for the calculation start link, and the time zone acquired respectively or after each time zone acquired Refer to the statistical link cost information or the latest link cost information related to the time zone from the stored contents of the traffic information memory, respectively, A method of calculating a plurality of routes from the calculation start link to a destination set by a user based on the statistical link cost information or the latest link cost information.