JP2005009978A - Minimum-time route searching method - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a minimum-time route searching method which can search a minimum-time route with precision and at a high speed. <P>SOLUTION: In the minimum-time route searching process, a departure time at a departure place in a departure time obtaining step (S101) is obtained, and the distances in minimum-time route and a straight line and an estimated arrival time at the destination are calculated based on the departure time in an estimated arrival time calculating step (S105). In addition, in a departure place starting point route searching step (S103), a minimum-time route from the departure place as a starting point to the destination is searched based on data about approximate time required to access road links by time and the departure time, and at the same time and parallel to this a minimum-time route from the destination as a starting point to the departure place based on data about approximate time required to access road links by time and the estimated arrival time is searched in a destination starting point route searching step (S107). <P>COPYRIGHT: (C)2005,JPO&NCIPI

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a route search method from a departure point to a destination, and more particularly to a shortest time route search method for searching a shortest time route that can be reached from a departure point to a destination in the shortest time.
[0002]
[Prior art]
2. Description of the Related Art Conventionally, a so-called car navigation apparatus that detects the current location of a car, searches for a route from the current location to a destination designated by a user, and performs route guidance has been put into practical use. An ordinary car navigation system has a road database that is a set of data obtained by dividing an actual road network as a short-distance road segment (hereinafter referred to as “road link”) of about 10 m to several tens m. The route from the present location to the destination is searched based on the road database.
[0003]
In such a road database, the length of the road link, the legal maximum speed, the type of general road / highway, and the like are usually stored in association with each road link. Therefore, when a route is searched from the road database, a cost value is defined based on data related to each road link, and a route having the smallest cost value is searched as an optimum route. In other words, the “cost value” here is a value that serves as a scale used to evaluate “optimum” when obtaining an optimal solution.
[0004]
As a specific example, a route with the minimum cost is searched for using the length of each road link as a “cost value”. As a result, a route having the shortest route distance to the destination is eventually obtained as a search result. As another example, the value obtained by dividing the length of each road link by the legal speed of the link, that is, the time required to pass through the road link (estimated required time) is set as the “cost value” as the minimum cost. As a result, a route that can reach the destination in the shortest time, that is, a so-called shortest time route is obtained.
[0005]
In general, a user of a car navigation apparatus desires to search for a route that can reach a destination in the shortest time. However, in the example of the shortest time route search as described above, since it is calculated using the value of the legal maximum speed, for example, it cannot be said that the actual required time is accurately represented.
[0006]
Therefore, it is also considered to install a traffic flow measurement sensor on the road, detect the actual average speed, and calculate the required time for the road link based on the detected value. When calculating the time, the estimated required time for each road link is calculated, and the estimated required time is the cost value for each road link. There has been proposed a method for calculating the required time by summing the two. This method is called a time slice total method (for example, Patent Document 1 below).
[0007]
[Patent Document 1]
Japanese Patent Laid-Open No. 11-39587 (page 4, paragraph number 0005)
[Problems to be solved by the invention]
However, in the method of installing a traffic flow measurement sensor on the road, detecting the actual average speed, and calculating the required time of the road link based on the detected value, when calculating the required time of the route, The time at which the point passes is different. Therefore, there is a technical problem that the time required for road links at each point varies depending on the passage time (for example, the time required for the same road link varies greatly between morning and evening rush hours and other times).
[0008]
In addition, the time slice total method is effective when a route is given in advance, but in the case of a route search in which a starting point and a destination are given and the shortest time route between them is obtained, When sequentially searching for and connecting road links that are candidate routes from the departure place, the required time of the corresponding link is extracted from the estimated time required data by time and added, so the final route There is a technical problem that it takes time to search.
[0009]
In other words, in the route search, the search is carried out while holding several candidate routes that can be generally optimized. However, the route search is unilaterally started from the starting point toward the destination. If the search to the destination is not completed for all route candidates, the optimum route cannot be determined. In this method, the search process is continued until the route to be searched reaches one point as the destination, so the load of the search process is heavy.
[0010]
On the other hand, if the cost of each road is invariable with respect to time, the route search starts from the departure point and the destination at the same time, and when the end points of the two search routes coincide, A method of completing the route search can be adopted. In such a route search method, when the route search from both the starting point / destination reaches the same road, both the searched routes are connected along the road to complete the route. Compared with a method in which the search does not end until reaching a specific point as a safe destination, the load of the search process can be greatly reduced.
[0011]
However, even in such a method of starting a route search from the starting point and the destination at the same time, time-dependent required time data that changes depending on the time of passing the road link is used as a cost value for the route search. In this case, if the arrival time cannot be set in advance, the cost value in the route search from the destination side cannot be specified, and the technical problem that the search cannot be performed from the destination side remains.
[0012]
The present invention has been made to solve the above-described problems, and an object of the present invention is to provide a shortest time path search method capable of searching a shortest time path accurately and at high speed.
[0013]
[Means for solving the problems and functions and effects of the invention]
In order to achieve the above object, in the shortest time route searching method according to claim 1, from the departure place to the destination, the estimated time required for passing through each road link is recorded for each time. In the shortest time route searching method for searching for the shortest time route, based on the departure time acquisition step of acquiring the departure time leaving the departure place, the linear distance from the departure place to the destination, and the departure time, An estimated arrival time calculating step for calculating an estimated arrival time for arriving at the destination after leaving the departure place, and the time required time data for each road link and the departure time based on the departure time. A starting point starting point route searching step for searching a starting point starting point shortest time route toward the destination, and the starting point starting point route searching step substantially in parallel. A destination starting point route searching step for searching a destination starting point shortest time route from the destination to the departure point based on the time required time data of each road link and the estimated estimated arrival time; It is a technical feature to include.
[0014]
In claim 1, the departure time to depart from the departure place is acquired by the departure time acquisition step, and the departure point is departed based on the straight line distance from the departure place to the destination and the departure time by the estimated arrival time calculation step. Calculate the estimated arrival time to arrive at the destination. In addition, the departure origin starting point route search step almost simultaneously with the search of the departure origin starting point shortest time route from the departure point to the destination based on the time required time data of each road link and the departure time. The destination starting point route searching step searches for the destination starting point shortest time route from the destination to the departure point based on the time required time data of each road link and the estimated estimated arrival time. As a result, the estimated arrival time to the destination is calculated first, so that the time-dependent required time depends on the time, and the route search starting from the departure point is almost the same as the starting point. Route search can be performed. That is, even if the time-dependent time-dependent data for each road link is used, it is possible to search for the route from the departure point and the destination at the same time. It is possible to search for a time path. Therefore, the shortest time path can be searched accurately and at high speed.
[0015]
Here, “searching for the shortest starting point route from the starting point to the destination based on the time required time data of each road link and the starting time” is, for example, 1) to (3).
[0016]
(1) For the first road link on the route in the vicinity of the departure place, the estimated required time of the road link at the departure time is extracted from the time required time data and used as a cost value. (2) For the next road link, the estimated required time at the time obtained by adding the required time of the previous road link obtained in (1) to the departure time is extracted from the time required time data, and the estimated required time of the link Is the cost value. (3) The route search is repeated toward the destination in the process (2), and the cost values are accumulated. As a result, the integrated cost value becomes the total cost value at that point of the route.
[0017]
Further, “searching for the shortest time route from the destination to the departure point based on the time required time data of each road link and the estimated arrival time” is, for example, It is embodied by the following (4) to (6).
[0018]
(4) For the first road link in the route near the destination, the estimated required time of the road link at the estimated arrival time is extracted from the time-specific required time data and used as a cost value. (5) For the next road link, the estimated required time at the time obtained by subtracting the required time of the previous road link obtained in (4) from the estimated estimated arrival time is extracted from the time-based required time data and estimated for the link. Let the required time be the cost value. (6) The route search is repeated in the direction of the destination in the process (5), and the cost values are accumulated. As a result, the integrated cost value becomes the total cost value at that point of the route.
[0019]
In the route search, several route candidates are always searched (routes that travel to different roads at each intersection are candidates), but among the route candidates, the accumulated cost at that point in the middle of the search Leave a few candidates with small values and delete the other candidates. The narrowing down of route candidates is similar to the conventional route search method. Eventually, for several route candidates, if the search route from the starting point (the shortest starting time route from the starting point) and the searching route from the destination (the shortest time route from the starting point) are combined, the total cost value Is the shortest time path.
[0020]
Further, in the shortest time route search method according to claim 2, in claim 1, the approximate estimated arrival time calculation step is performed from the departure place to the destination instead of a straight line distance from the departure place to the destination. The shortest path distance is a technical feature.
[0021]
In the invention of claim 2, the estimated arrival time calculation step uses the shortest route distance from the departure point to the destination instead of the straight line distance from the departure point to the destination. The estimated estimated arrival time can be calculated more accurately (with higher accuracy) than calculated based on the distance. In the shortest distance route search, since the distance of each road link is constant regardless of the time, the route search can be performed simultaneously from the starting point and the destination by the conventional technique.
[0022]
Furthermore, in the shortest time route search method according to claim 3, the expected time of arrival at the destination is calculated based on the shortest time route from the starting point and the shortest time route from the destination. A technical feature is to further include a step of recalculating the estimated arrival time.
[0023]
In the invention of claim 3, the estimated estimated arrival time is an approximate value based on the straight distance between the departure point and the destination or the distance of the shortest distance route. Based on the time route and the shortest time route from the destination, for example, the time required for each road link is extracted again from the time required time data and added, so the estimated time to arrive at the destination is accurately estimated. be able to.
[0024]
DETAILED DESCRIPTION OF THE INVENTION
Embodiments according to the shortest time route searching method of the present invention will be described below with reference to the drawings.
[First Embodiment]
First, as a first embodiment, an example in which the shortest time route searching method of the present invention is applied to a control process of a navigation device will be described with reference to FIGS. FIG. 1 is a block diagram illustrating a configuration example of the navigation device 10 according to the first embodiment.
[0025]
<Configuration of Navigation Device 10>
As shown in FIG. 1, a navigation device 10 includes a CPU 12 that executes various programs, a program memory 14 that stores programs to be executed by the CPU 12, a vehicle speed sensor 30 as a sensor for detecting the current location of the vehicle, a GPS sensor 32, a gyro sensor 34, a communication device 36 and an antenna 38 for communicating with the outside, a road database 22 in which an actual road network is recorded as a set of short road piece (road link) data (road link data), each road link A cost database 20 in which data (cost data) of cost values (required time for each road link) is recorded is provided. For example, the CPU 12 is realized by a microcomputer, and the program memory 14 is realized by a semiconductor memory device.
[0026]
The road link data recorded in the road database 22 displays a map on the display 40 in addition to the route search, or specifies the current location on the map of the vehicle based on the sensor signal obtained by the GPS sensor 32 or the like. It is also used to
[0027]
In FIG. 1, the road database 22 and the cost database 20 are configured separately, but may be configured as a single database physically or logically. It is also preferable that the cost data is configured to be able to receive and update the latest data from an external information center (not shown) via the communication device 36 and the antenna 38.
[0028]
In the program memory 14, a route search program 14a for performing a route search (in FIG. 1, "program" is abbreviated as "PGM". The same applies hereinafter), a current location specifying program 14b, and route guidance processing. In addition to the route guidance program 14c to be executed and the above, although not shown, other programs such as a program for setting a destination are also stored.
[0029]
The current location specifying program 14b specifies the approximate current location of the vehicle based on the sensor data from the GPS sensor 32, extracts the road link data around the specified current location from the road database 22, the vehicle speed sensor 30, the gyro The road immediately before the vehicle is estimated from the data of the sensor 34, and the estimated trajectory immediately before the vehicle is compared with the road shape represented by the road map data extracted from the road database 22, and the road where the vehicle is currently located It has a function to specify the position on the map. The position of the vehicle on the road map data specified in this way is acquired as the current location of the vehicle. The current location is usually specified as a value of east longitude north within the navigation device 10. Various programs may be stored not in the program memory but in an information recording device such as a hard disk or an information recording medium such as a DVD.
[0030]
<Explanation of road link data / cost data>
Next, the road link data stored in the road database 22 and the cost data stored in the cost database 20 will be described with reference to FIGS. FIG. 2 is a diagram schematically showing the connection relationship (road network) of road link data, and the straight lines indicated by R1, R2, R3, R4, and R5 each represent a road link. Here, the symbols from R1 to R5 are the road link ID numbers (numbers for identifying individual road links) shown in FIG. In addition, C1, C2, C3 and C4 in the figure represent connection points of the road links, that is, intersections.
[0031]
The road link data is stored in the road database 22 with a data structure as shown in FIG. For example, the road link with the ID number R1 has a distance of 40 (m), the start point intersection is represented as C1, and the end point intersection is represented as C2. The start point and end point are given for convenience. The road link R1 is connected to the road link represented by R2 and R4 at the start intersection C1, and is connected to the road link represented by R2 at the end intersection C2. As shown in FIG. 3A, the same applies to the road link with ID number R2, road link R3, road link R4, road link R5, distance, start point intersection, end point intersection, start point connection road link, Data of end connection road links are recorded respectively. That is, the road link connection relationship shown in FIG. 2 is databased in the road database 22 as chart information shown in FIG.
[0032]
On the other hand, data as shown in FIG. 3B is recorded in the cost database 20. That is, the time required for passing through each road link (required time) is converted into data for each time in the forward direction and the reverse direction. Here, the forward direction of the link is a direction that advances from the start point of the link to the end point, and the reverse direction of the link is a direction that advances from the end point of the link to the start point. In FIG. 3B, as an example, the current time required time, the required time 15 minutes after the current time, similarly the required time after 30 minutes, 45 minutes, and 60 minutes, Although it is expressed for each elapsed time from the current time on the basis of the time, it is needless to say that each expression is equivalent to that expressed for each time. Further, although the data of each road link is identified by the link ID and direction (forward / reverse), for example, the forward direction of the link R1 may be identified by an expression with an intersection number such as C1C2 and the reverse direction is C2C1. (See FIGS. 11 to 15 and FIGS. 17 to 19).
[0033]
Here, an example of calculating the required time for a route when the intersection C1 shown in FIG. 2 is the departure point and the intersection C4 is the destination will be described.
First, the route from the intersection C1 to the intersection C4 includes a route passing through the road link R1 and R2 (route 1), a route passing through the road link R3 (route 2), and a route passing through the road link R4 and R5 (route 3). ) Three routes are possible.
[0034]
The required time of route 1 (R1 and R2) is calculated from the chart shown in FIG. 3B as the required time for passing the road link R1 in the forward direction from the intersection C1, which is the departure point, at the current time. 17 minutes, which is the value of the “current time” column in the “order” row, is extracted. Then, it is found that the arrival time at the intersection C2 is 17 minutes after the current time. Therefore, the next required time for the road link R2 is extracted from the chart shown in FIG. 3B as 11 minutes which is the value of the column “15 minutes later” in the row “R2-order”. Therefore, in the case of the route 1 to the intersection C4 which is the destination, the required time is calculated as 17 + 11 = 28 minutes.
[0035]
The required time for the route 2 (R3) is calculated as 35 minutes by extracting the required time for the road link R3 at the current time from the chart shown in FIG. The required time of the route 3 is the value of the “current time” column in the “R4-order” row from the chart shown in FIG. 3B as the required time of the road link R4 connected to the intersection C1 as the departure place. 16 minutes are extracted. Then, since the arrival time at the intersection C3, which is the starting point of the next road link R5, will be 16 minutes later, the required time at the road link R5 is the line "R5-order" from the chart shown in FIG. 7 minutes, which is the value in the column “after 15 minutes”, is extracted. Therefore, the required time in the route 3 is calculated as 16 + 7 = 23 minutes.
[0036]
Thus, the required time to the destination can be calculated using the required time data for each road link from the departure point to the destination. If the route from the departure point to the destination is short, the required time can be calculated by accumulating the required time along the route from the departure point to the destination as in the previous example. If the route becomes a relatively long distance, the efficiency of the search process becomes poor only by route search from the departure point to the destination. This is because it is necessary to perform processing until the searched route arrives at one point called the destination.
[0037]
Therefore, in general, when the cost value does not depend on the time and is constant, the search is performed from the departure point and the destination almost simultaneously, and the route search from the departure point to the destination is performed when the end points of the two search routes coincide. By using the method that is completed, the route search can be performed efficiently. However, if the cost value changes depending on the time of passing the road link (hereinafter “time-varying”), the arrival time at the destination is unknown at the start of the route search, so the time-varying cost value The conventional method cannot be used as it is for the route search from the destination. Therefore, in the present embodiment, the route search from the destination can be performed even by using the time-varying cost value by the shortest time route search process described later.
[0038]
<Description of route search processing>
First, the outline of route search and the structure of road link data, which are the basis of the shortest time route search processing, will be described with reference to FIG.
[0039]
As shown in FIG. 4, road link data is classified into a plurality of layers and stored in the road database 22.
For example, from a detailed map data layer including narrow road links (narrow street road links) to a wide area map data layer consisting only of main trunk road links such as intercity roads and expressways, and intermediate road links between them. It is classified into each layer such as a mid-range diagram data layer. The road data included in each layer is further divided into predetermined areas. That is, the detailed map data is divided into narrow areas, and the wide area map data is divided into wide areas as a single piece of data. FIG. 4 schematically shows these.
[0040]
The code a shown in FIG. 4 indicates a detailed map data layer, the code b indicates an intermediate area data layer, and the code c indicates a wide area data layer. The detailed map data layer a is divided into detailed road data A, detailed road data B, etc., for each specific area and for each road data. Similarly, the intermediate area data layer b is divided and stored as intermediate area road data A and intermediate area road data B. In addition, in the road data of each data layer, the intersection existing in each of the data layers is referred to as a layer connection intersection and distinguished from the intersection existing only in that layer. It has been converted into data. In FIG. 4, the layers are exemplified as a three-layer structure, but are not limited to three layers, and may be, for example, two layers, four layers, five layers, or ten layers or more.
[0041]
In the route search according to the present embodiment, first, the detailed road data of the detailed map data layer a including the departure point is specified from the road database 22, and the route from the departure point to all the intersections in the detailed road data a is determined. Search is performed, data of the next layer (b: intermediate region map data layer in FIG. 4) is extracted from the road database from the layer connection intersection, and routes to all intersections are further searched. Such processing is repeated up to the highest layer (c: wide area map data layer in FIG. 4). Do the same from the destination. However, from the destination side, the operation is performed up to one level before the highest layer (b: intermediate region diagram data layer in FIG. 4). Then, a process for connecting the route that started the search from the departure point (the departure point origin route) and the route that started the search from the destination (the destination point origin route) is performed, and a plurality of route candidates are obtained. The route with the lowest cost is extracted and the route search is completed.
[0042]
Here, a specific example will be described with reference to FIG. As shown in FIG. 4, the departure point d is included in an area called detailed road data A in the detailed map data layer a, and the destination e is included in an area called detailed road data B in the detailed map data layer a. Since the detailed road data A and the detailed road data B are different data areas, the detailed road data area A searches for a route from the departure point d to the layer connection intersection, and the detailed road data B from the destination to the layer connection intersection. Search for a route. For example, in the detailed road data A, a route to the layer connection intersection f is searched, and in the detailed road data B, a route to the layer connection intersection g is searched.
[0043]
As shown in FIG. 4, the layer connection intersection f belongs to the intermediate area road data A in the intermediate area diagram data layer b which is the next layer layer, and the layer connection intersection g belongs to the intermediate area road data B. Also in the intermediate zone map data layer b, the layer connection intersection f which is the end point of the route searched from the departure point and the layer connection intersection g which is the end point of the route searched from the destination belong to road data of different regions, respectively. The route from the end point to the layer connection intersection to the wide area map data layer which is a higher layer is searched.
[0044]
In the next intermediate zone map data layer b, the route from the layer connection intersection f to the upper layer is searched as a layer connection intersection h to the layer connection intersection h, and the layer connection intersection from the layer connection intersection g to the upper layer is used as the layer connection intersection. A route to the connection intersection j is searched. Next, in the wide area map data layer which is the highest layer, the route from the connection intersection h to j from the destination side is searched. Then, the route search is completed by connecting the starting point origin route and the destination starting point route.
[0045]
In the example described above, an example in which one route is searched from the departure point d to one layer connection intersection f is shown, but in each road data, a route to a plurality of layer connection intersections is searched. The routes to all the intersections are continued because it is not known which route has the lowest cost until the starting point destination route and the destination starting point route are connected and the costs of both are added.
[0046]
Thus, the route search from the destination can be performed by the conventional method as described above when the cost value does not change with time, but is applied when the cost value is time-varying. I can't.
Therefore, in the shortest time route search processing according to the present embodiment, first, a straight line distance between the departure point and the destination is calculated, and an approximate destination arrival time is calculated from that value, or the shortest distance route between the departure point and the destination. Is obtained first, and a value obtained by dividing the distance by a preset average speed is obtained as an estimated estimated arrival time to the destination. Then, based on the estimated estimated arrival time, the time required for the road link connected to the destination is obtained from the time required time data. The value obtained by subtracting the required time obtained from the estimated arrival time at the destination is used as the time for obtaining the time required for the next road link from the time-specific time data. By repeating this, the shortest time path from the destination can be searched.
[0047]
Next, the flow of the shortest time distance route processing will be described based on the flowcharts shown in FIGS. 5 and 6 and the explanatory diagrams shown in FIGS. Note that although steps S101 to S107 shown in FIG. 5 are illustrated as sequential processing over time, “steps S101 and S103” and “steps S105 and S107” shown in FIG. Please note that it is executed. These processes are started when the destination is input by the user, the current location of the vehicle is detected by the navigation device 10, and the detected current location is set as the departure location in the route search.
[0048]
As shown in FIG. 5, in the shortest time distance route processing according to the present embodiment, processing for setting the departure time in step S101 is performed. As the departure time, either the current time obtained from the clock of the navigation device 10 or the time input by the user is used. This step S101 corresponds to a “departure time acquisition step” described in the claims.
[0049]
Subsequently, in step S103, a process of setting node costs for all nodes (intersections) from the departure place to the highest level is performed. The node cost refers to a cost that minimizes the cost value required to reach the node from the starting point or the destination, and “node name = XX” outside the route map frame shown in FIGS. (Nearest via node name) "format.
[0050]
For example, in the search example on the departure side shown in FIG. 7A, since node B is connected to node A as the most recently routed node, the node cost is 5 and is expressed as “B = 5 (AB)”. Since E has a minimum cost for a route from node A to node E via node B (the most recently routed node), the node cost is 12 and is expressed as “E = 12 (BE)”. Since node A is the departure place, the node cost is 0 (zero) and “A = 0”.
[0051]
The process in step S103 is shown in FIG. 6 based on the time required time data (FIG. 3B) for each road link stored in the cost database 20 and the departure time set in step S101. This is performed by the node cost setting process, and the time required for each road link for each layer is calculated (see FIGS. 7A, 8 and 9). Details of this processing will be described later with reference to FIG. This step S103 corresponds to a “departure starting point route searching step” described in the claims.
[0052]
On the other hand, in step S105, a process for calculating and setting the estimated arrival time of the destination is performed in parallel with the processes in steps S101 and S103. Specifically, the required time is calculated based on the shortest distance route obtained for each layer and a preset traveling speed.
[0053]
For example, as shown in FIG. 16, the shortest distance route belonging to the level 1 layer is a general road, the total distance is 60 km (= 40000 m + 20000 m), and the shortest distance route belonging to the level 2 layer is a highway. When the total distance is 100 km (= 100000 m), if the average traveling speed of a general road is 30 km / h and the average traveling speed of a highway is 100 km / h, 60/30 + 100/100 = 3 hours ( Time required) is calculated. Thereby, for example, when the departure time (departure time) is 10 am, the estimated time to arrive at the destination I (estimated arrival time) is 1 pm (13:00).
[0054]
The shortest distance route may be a straight line distance on the map. Thereby, since it is not necessary to perform a process of searching for the shortest distance route from the departure point to the destination, the accuracy of the estimated approximate arrival time that can be calculated is reduced, but a faster calculation process is possible.
[0055]
Subsequently, in step S107, a process for setting node costs for all nodes from the arrival point (destination) to the previous highest level is performed. This process is the same as step S103 described above based on the time required time data (FIG. 3B) for each road link stored in the cost database 20 described above and the estimated arrival time set in step S105. In addition, the time required for each road link for each layer is calculated by the node cost setting process shown in FIG. 6 (see FIG. 7B). Details of this processing will be described later with reference to FIG. This step S107 corresponds to a “destination starting point route searching step” described in the claims.
[0056]
When all node costs are set in step S103 and step S107, a process for calculating a minimum cost path and determining a shortest time path is performed in step S109.
For example, in the search example shown in FIG. 10, a road network belonging to the level 1 layer on the destination side can be connected to a road network belonging to the level 2 layer at nodes K and L. The cost when connecting at node K is 12 + 29 = 41. On the other hand, the cost when connected by the node L is 10 + 38 = 48. Therefore, the route connected by the node K having a small total cost is determined as the shortest time route.
[0057]
Here, the contents of the node cost setting process performed in step S103 will be described with reference to FIG. 6 and FIGS. The node cost setting process shown in FIG. 6 corresponds to a “departure starting point route searching step” described in the claims.
[0058]
As shown in FIG. 6, in the node cost setting process, first, a process of initializing a start node cost is performed in step S201. The start node cost is “node A” in the road network connected to the departure place (node A) shown in FIG. 11A. The node cost of node A is 0 (zero) and the departure time is determined in this step. 10:00 is set.
[0059]
Next, in step S203, a process for selecting an indeterminate node with the smallest node cost is performed. In the search example shown in FIG. 11A, since there is only one indeterminate node, node A is inevitably selected.
[0060]
In subsequent step S205, processing for acquiring the time cost of the link connected to the selected node is performed. Specifically, referring to the cost data table, the scheduled time to reach a node that is not in the return direction with respect to the selected node selected in step S203 is calculated. For example, in the search example shown in FIG. 11A, since the nodes not connected in the return direction connected to the selected node A are the nodes B, C, and D, the respective costs at the time 10:00 for these nodes Is obtained by referring to the cost data table shown in FIG. Thereby, as shown in FIG. 12, the link costs AB = 5, AC = 7, and AD = 6 to the nodes B, C, and D at the time 10:00 leaving the selected node A are obtained.
[0061]
In subsequent step S207, node cost setting processing on the connection link end side of the selected node is performed. In the search example shown in FIG. 11A, the link cost to the connected link terminal node obtained in step S205 is added to the node cost of node A, and B = 5 with nodes B, C, and D as undetermined nodes. (AB), C = 7 (AC), and D = 6 (AD) are set.
[0062]
In step S209, the selected node is set as a node (confirmed node) whose cost has been confirmed. In the search example shown in FIG. 11A, the selected node A selected in step S203 is a confirmed node with a cost value of zero.
[0063]
In step S211, a process for determining whether or not the costs of all the nodes in the same layer are fixed is performed. If the costs of all nodes have been determined (Yes in S211), the process proceeds to step S213, and if the costs of all nodes have not been determined (No in S211), step S203 is performed. The process is returned to and the process of selecting the node with the lowest node cost among the unconfirmed nodes is performed.
[0064]
In the search example shown in FIG. 11A, the unconfirmed nodes are nodes B, C, and D, and therefore, node B with the lowest node cost is selected next, and that node B becomes the selected node. . In step S205, since the node not connected in the return direction connected to the selected node B is the node E, the cost at this time to the node E is obtained by referring to the cost data table shown in FIG. To do. In step S207, the estimated time of arrival at the node E is calculated. As a result, as shown in FIG. 13, it can be seen that the cost to the node E and the estimated arrival time at the time 10:05 leaving the selected node B are 10:11 with BE = 6. Then, node E is set as an undetermined node, and E = 11 (BE) is set. Subsequently, in step S209, the selected node becomes a confirmed node with a node cost of 5.
[0065]
Similarly, D having the lowest node cost is selected next from unconfirmed nodes C, D, and E, and the node D becomes the selected node. Then, in step S205, the nodes not connected in the return direction that are connected to the selected node D are the nodes C and E. Therefore, the costs for the nodes C and E at the corresponding time are shown in FIG. 11B. Get each by referring to the data table. In step S207, the scheduled time of arrival at the nodes C and E is calculated. As a result, as shown in FIG. 14, the cost and arrival time to node C at time 10:06 leaving the selected node D are 10:09 with DC = 3, and the cost and arrival time to node E It can be seen that DE = 16 is 10:22.
[0066]
Here, it can be seen that the node cost of the node C is not smaller than C = 7 (AC) calculated in the previous step, so the node cost of C = 9 (DC) and the node D and the node The path connecting C is discarded without being adopted. Further, since it can be seen that the node cost of the node E is not smaller than E = 11 (BE) calculated in the previous step, the node cost of E = 22 (DE) and the node D and the node E The path that connects to is also discarded without being adopted. If the calculated node cost is smaller than the calculated node cost, the calculated node cost is replaced with a newly calculated one and updated as the minimum node cost. In step S209, the selected node D is set as a node (determined node) for which the node cost is determined.
[0067]
Similarly, when the node C is selected as the unconfirmed node with the lowest cost, the cost at the current time of the node E as a node not connected in the return direction connected to the selected node C is shown in the cost data table shown in FIG. , The estimated time of arrival at the node E is calculated. As a result, as shown in FIG. 15, it is understood that the cost to node E and the estimated arrival time at time 10:07 leaving the selected node C are 10:12 with CE = 5.
[0068]
Here, it can be seen that the node cost of the node E is not smaller than E = 11 (BE) calculated by this step the previous time, so the node cost of E = 12 (CE) and the nodes C and The path connecting E is discarded without being adopted. The selected node C is set as a confirmed node in step S209.
[0069]
In this way, in the route example shown in FIG. 11A, when all the nodes are set as confirmed nodes (see FIG. 7A), the costs of all the nodes are confirmed in step S211. Since the determination is made (Yes in S211), the process proceeds to step S213.
[0070]
In step S213, a determination process is performed to determine whether or not the layer upgrade process has been completed. If it is determined that the layer upgrade process has been completed (Yes in S213), the cost setting for all the nodes from the departure point to the highest level has been completed, so this node cost setting process ends. Then, the process returns to the shortest time route search process shown in FIG. On the other hand, if it cannot be determined that the layer upgrading process has been completed (No in S213), the process proceeds to step S215 to perform a process of upgrading the layer to a higher level. For example, since the route example shown in FIG. 11A belongs to the level 1 layer, the node cost setting target layer is upgraded to level 2 which is the higher level. Thereby, the node cost is set, for example, for a route example belonging to the level 2 layer as shown in FIG. 9, and the above-described step S <b> 203 until the cost value determined for all the nodes D to L is set. Each process by ~ S211 is performed.
[0071]
Subsequently, the contents of the node cost setting process performed in step S107 will be described with reference to FIG. 6 and FIGS. The node cost setting process shown in FIG. 6 corresponds to a “destination starting point route searching step” described in the claims. The node cost setting process performed in step S107 is the same as that described above except that the node cost is set so that the shortest time path can be searched based on the estimated time of arrival at the destination I (estimated arrival time). This is almost the same as the node cost setting process performed in step S103.
[0072]
As shown in FIG. 6, in the node cost setting process, first, the process of initializing the start node cost is performed in step S201. Therefore, in the road network connected to the destination (node I) shown in FIG. In addition, the estimated arrival time 13:00 set in step S105 and the node cost 0 (zero) are set.
[0073]
Next, in step S203, a process for selecting an indeterminate node with the smallest node cost is performed. In the search example shown in FIG. 17, since there is only one indeterminate node, node I is inevitably selected.
[0074]
In subsequent step S205, processing for obtaining the time cost of the link connected to the selected node is performed. Since the nodes not connected in the return direction connected to the selected node I are the nodes K, J, and L, the costs at these times to these nodes are acquired with reference to the cost data table shown in FIG. As a result, the link costs KI = 12, JI = 13, and LI = 10 from the nodes K, J, and L at the time of 13:00 arriving at the selected node I are obtained.
[0075]
In subsequent step S207, node cost setting processing on the connection link end side of the selected node is performed. The link cost to the connection link terminal side node obtained in step S205 is added to the node cost of the node I, and K = 12 (IK), J = 13 (IJ), where the nodes K, J, and L are undetermined nodes. Set L = 10 (IL). In step S209, the selected node I becomes a confirmed node having a cost value of 0. When the node I becomes a confirmed node, the determination process in step S211 is performed, and then the process is performed again in step S203.
[0076]
As shown in FIG. 18, the node L is selected as the unconfirmed node with the smallest node cost in step S203, and the node J that is not in the return direction connected to the selected node L is selected in step S205. The estimated time of departure from the node J is calculated with reference to the cost data table shown in FIG. Accordingly, it is understood that the cost from the node J and the estimated departure time at 12:50 arriving at the selected node L are 12:46 with JL = 4.
[0077]
However, as shown in FIG. 18, it can be seen that J = 14 (LJ) of this node J is not smaller than the already calculated J = 13 (IJ), so that the node cost of J = 14 (LJ) and The path connecting the node L and the node J is discarded without being adopted. If the calculated node cost is smaller than the calculated node cost, it is replaced with the newly calculated one and updated as the minimum node cost in step S103 described above. This is the same as the node cost setting process.
[0078]
In step S209, the selected node L becomes a confirmed node having the cost value 10. When the node L becomes a definite node, the determination process in step S211 is performed, and then the process is performed again in step S203. Similarly, after step S205, step S207, and step S209, as shown in FIG. 19, the node K becomes a confirmed node of K = 12 (IK), and is processed again by step S203.
[0079]
Finally, node J is selected as the unconfirmed node with the lowest cost in step S203, but a node that is not in the return direction connected to the selected node J cannot be selected in subsequent step S205, so steps S207 and S209 are selected. Thus, the selected node J becomes a confirmed node with the cost value 13.
[0080]
In this way, in the route examples shown in FIGS. 17 to 19, when all the nodes are set as the confirmed nodes (see FIG. 7B), the costs of all the nodes are confirmed in step S211. Since it is determined (Yes in S211), the process proceeds to step S213, and when the cost setting for all the nodes from the destination to the previous highest level is completed, the present node cost setting process is terminated. The processing is returned to the shortest time route search processing shown in FIG.
[0081]
Thus, the shortest time route from the departure point to the destination can be searched by the shortest time route search processing shown in FIG. 5 and the node cost setting processing shown in FIG. In addition, based on the shortest time path searched in this way, a process (estimated arrival time recalculation step) for calculating an estimated time of arrival at the destination is added after step S109, so that the destination is The estimated time of arrival can be accurately estimated.
[0082]
As described above, according to the navigation device 10 according to the first embodiment, the departure time to depart from the departure place is acquired by the departure time acquisition step (S101) by the shortest time route search process executed by the CPU 12, and the rough estimate is obtained. Based on the shortest route distance and straight line distance from the departure point to the destination, and the departure time, an estimated arrival time that arrives at the destination after departing from the departure point is calculated in the estimated arrival time calculation step (S105). Also, from the departure point starting point route search step (S103, S201, S203, S205, S207, S209, S211, S213, S215), from the departure point to the destination based on the required time data for each road link and the departure time. Each road link is substantially simultaneously with the search for the shortest time starting point for the starting point to the destination by the destination starting point route searching step (S107, S201, S203, S205, S207, S209, S211, S213, S215). Based on the time required time data and the estimated estimated arrival time, the destination starting point shortest time route from the destination to the departure point is searched.
[0083]
As a result, the estimated arrival time to the destination is calculated first, so that the time-dependent required time depends on the time, and the route search starting from the departure point is almost the same as the starting point. Route search can be performed. That is, even if the time-dependent time-dependent data for each road link is used, it is possible to search for the route from the departure point and the destination at the same time. It is possible to search for a time path. Therefore, the shortest time path can be searched accurately and at high speed.
[0084]
[Second Embodiment]
In the first embodiment described above, the processing mode performed by the navigation device 10 (FIG. 1) has been adopted, but the second embodiment communicates with the navigation device 62 mounted on the vehicle as shown in FIG. In the system constituted by the center device 60 that performs the above, the present location and the destination are received from the in-vehicle navigation device 62, the route search is performed by the center device 60, and the searched result is transmitted to the in-vehicle navigation device 62. The present invention is applied to a so-called communication type navigation system.
[0085]
FIG. 7 shows a center device 60 that performs processing by receiving a current location and a destination from an in-vehicle navigation device 62 via a base station 72 and a communication network 70 by wireless communication. In the center device 60, those having the same functions as those of the device or program in the first embodiment are given the same reference numerals as those in FIG.
[0086]
That is, when the center device 60 receives the current position and destination from the navigation device 62 via the communication device 36 ′ controlled by the communication control program 14d stored in the program memory 14 ′, the CPU 12 ′ causes the route search program 14a. By searching for the shortest time route using the road database 22 ′ and the cost database 20 ′, the searched route is returned to the navigation device 62. The route search process itself is the same as that in the first embodiment.
[0087]
By configuring the communication type navigation system in this way, it is possible to centrally manage the time-dependent data (stored in the cost database 20 ′) of each road link, and to provide other traffic information Cost data can be updated quickly based on traffic information from the facility. Thereby, the accuracy of the route search estimated as the shortest time during the route search can be improved.
[Brief description of the drawings]
FIG. 1 is a block diagram illustrating a configuration example of a navigation device according to a first embodiment of the present invention.
FIG. 2 is an explanatory diagram schematically showing an example of a road link.
FIG. 3A is a chart showing an example of a data structure of road link data, and FIG. 3B is a chart showing an example of a data structure of cost data (time-dependent time data).
FIG. 4 is an explanatory diagram showing an example of a layer structure of road link data constituting a road database and an outline of route search;
FIG. 5 is a flowchart showing a flow of a shortest time route search process according to the first embodiment.
6 is a flowchart showing a flow of node cost setting processing (S103, S107) shown in FIG.
7A and 7B are explanatory diagrams showing a search example in a road network belonging to the level 1 layer. FIG. 7A is a search example of a road network connected to a departure place (node A), and FIG. A search example of a road network connected to the ground (node I) is shown.
FIG. 8 is an explanatory diagram showing an example of connecting a level 1 layer and a level 2 layer, and a road network (routes A to E) belonging to the level 1 layer and a road network (route D) belonging to the level 2 layer; To H) are connected by nodes D and E.
FIG. 9 is an explanatory diagram showing a search example in a road network belonging to a level 2 layer.
FIG. 10 is an explanatory diagram showing an example of connecting a level 1 layer and a level 2 layer, and a road network (routes I to L) belonging to a level 1 layer and a road network (route D) belonging to a level 2 layer; ~ L) are connected by nodes K and L.
11A is an explanatory diagram showing a search example in a road network belonging to a level 1 layer connected to a departure place (node A), and FIG. 11B is a road in FIG. 11A. It is an example of the cost data table corresponding to a network.
FIG. 12 is an explanatory diagram that supplements the description of the processing contents in steps S201, S203, and S205 of the search example performed on the road network shown in FIG. 11A, in which the unconfirmed node is “A” and the selected node is This is the case for “A”.
FIG. 13 is an explanatory diagram supplementing the description of the processing contents in steps S203 and S205 of the search example performed on the road network shown in FIG. 11A, in which the confirmed node is “A” and the unconfirmed node is “B”. , C, D ”, and the selected node is“ B ”.
FIG. 14 is an explanatory diagram supplementing the description of the processing contents of steps S203 and S205 in the search example performed on the road network shown in FIG. 11A, with the confirmed nodes “A, B” and the unconfirmed nodes This is a case where “C, D, E” and the selected node are “D”.
FIG. 15 is an explanatory diagram supplementing the description of the processing contents of steps S203 and S205 of the search example performed on the road network shown in FIG. 11A, with the confirmation nodes “A, B, D” and unconfirmed This is a case where the nodes are “C, E” and the selected node is “C”.
FIG. 16 is an explanatory diagram for explaining the concept of the shortest distance route from a departure point (node A) to a destination (node I);
FIG. 17 is an explanatory diagram that supplements the description of the processing contents in steps S201, S203, and S205 of a search example performed on a road network belonging to a level 1 layer connected to a destination (node) I, and is unconfirmed This is a case where the node is “I” and the selected node is “I”.
FIG. 18 is an explanatory diagram supplementing the description of the processing contents in steps S203 and S205 of the search example performed for the road network belonging to the level 1 layer connected to the destination (node) I. I ”, the unconfirmed node is“ J, K, L ”, and the selected node is“ L ”.
FIG. 19 is an explanatory diagram supplementing the description of the processing contents in steps S203 and S205 of the search example performed for the road network belonging to the level 1 layer connected to the destination (node) I. This is a case where “I, L”, the unconfirmed node is “J, K”, and the selected node is “K”.
FIG. 20 is a block diagram showing a configuration example of a communication type navigation system according to a second embodiment of the present invention.
[Explanation of symbols]
10, 62 Navigation device
12, 12 'CPU
14, 14 'Program memory
14a, 14a 'route search program
14b Current location identification program
14c Route guidance program
14d Communication control program
20, 20 'cost database
22, 22 'road database
30 Vehicle speed sensor
32 GPS sensor
34 Gyro sensor
36, 36 'communication device
40 display
60 Center equipment
70 Communication network
72 base station
C1-C4 intersection
R1-R5 road links
d, A From
e, I Destination
f, g, h, j Layer connection intersection
A to E, I to L Nodes belonging to level 1 layer
DH, K, L Nodes belonging to level 2 layers
S101 (Departure time acquisition step)
S105 (estimated estimated arrival time calculation step)
S103, S201, S203, S205, S207, S209, S211, S213, S215 (starting origin route search step)
S103, S201, S203, S205, S207, S209, S211, S213, S215 (destination origin route search step)

Claims (3)

In the shortest time route search method for searching for the shortest time route from the departure place to the destination using the time required time data that records the estimated time required for passing each road link by time,
A departure time obtaining step for obtaining a departure time leaving the departure place;
An estimated estimated arrival time calculating step for calculating an estimated arrival time that departs from the departure location and arrives at the destination based on the straight distance from the departure location to the destination and the departure time;
A starting point starting point route searching step for searching a starting point starting point shortest time route from the starting point to the destination based on the time required time data of each road link and the starting time;
Almost simultaneously with the starting point origin route search step, based on the time required time data of each road link and the estimated arrival time, the shortest destination starting point from the destination to the starting point Destination origin route search step for searching time route;
The shortest time route search method characterized by including. 2. The shortest time according to claim 1, wherein the approximate estimated arrival time calculating step uses a shortest route distance from the departure place to the destination instead of a straight line distance from the departure place to the destination. Route search method. The predicted arrival time recalculation step of calculating an expected time of arrival at the destination based on the shortest time route from the starting point and the shortest time route from the destination point. The described shortest time route search method.

Images