JPH02172000A - Shortest route searching device - Google Patents

Abstract

PURPOSE:To search a shortest route at high speed by controlling a search order so that the number of search nodes or search branches to be searched from each direction can be almost balanced in the process of the bidirectional search. CONSTITUTION:When a search start position and search end position are designated by a position input means, the shortest route is successively searched from the both directions of the search start position and search end position by a bidirectional searching means. The search order in the process of the bidirectional search is controlled by a search order control means so that the number of the nodes or branches to be searched can be made equal in the both directions. The search is advanced and the shortest route is determined out of the routes, for which the number of the search branches or search nodes is made coincident from the both directions. Then, the shortest route is displayed by a display means. Thus, in route data, for which the density of the node or branch is different, the number of the nodes or branches to be developed until the shortest route is discovered can be made minimum and accordingly, a shortest route search time can be shortened.

Description

[Detailed description of the invention] [Industrial application field]

The present invention relates to a device that automatically searches for the shortest route from a search start position to a search end position in a network. For example, it is applied to a navigation device that searches a road map for the shortest route from the current location of a moving body to the destination location to which it is going.

[Prior art]

Many in-vehicle navigation devices that search for the shortest route from the current location of a moving object to a destination location and display the route have been developed and released to the public. What is required of these devices is, when a node pair of a search start position and a search end position is specified, to quickly search for and display the shortest route between the node pair. BACKGROUND ART Shortest route search methods have been needed and researched in the fields of network management and electrical circuits. For example, there are a label determination method, a matrix method, a dynamic programming method, etc. Among these, the fixed method for labels has been extensively studied because it has good search efficiency and is suitable for digital calculations. Among them, the potential method, Dijkstra method, Nicolhun method, etc. are known as typical solutions, and recently, improvements such as the heap method and packet method have been used as efficient methods for updating the state file during search. An algorithm has been published.

[Problem to be solved by the invention]

However, since the label determination method described above is a method of sequentially extending the search branch with the shortest path distance from the search start position, the most advanced node is conceptually at a position equidistant from the search start position. Therefore, the search expands concentrically around the search start position, and the search ends when the search end position is on the circle. Therefore, there is a low probability that the shortest route exists inside the semicircle on the opposite side of the search end position from the search start position, and searching in that semicircular area becomes a useless search. On the other hand, the Nikolhun method targets the problem of finding the shortest path between one search start position and one search end position. The Nicolhun method performs a search similar to the label confirmation method from both directions, from the search start position to the search end position. Therefore, the search is expanded concentrically with equal radius around the search start position and the search end position, and the search ends when the circles from both directions intersect. Therefore, the search area is approximately 1/2 that of the label determination method that searches from one direction. However, in the Nicollan method as well, semicircular areas on the far side of each search are searched, centering on the search start position and the search end position, and the range in which the existence probability of the shortest path is low is determined by ;l. I'm searching in vain. Therefore, it takes a long time to search, which is insufficient to ensure the response time required of an in-vehicle navigation device. Furthermore, the search order from both directions is alternately switched so that the two circles centered on the search start position and the search end position have equal radii. However, since the search time is determined by the number of nodes to be searched, if the node densities are different, searching equidistantly from both directions may not always result in the smallest number of nodes to be searched. In this way, it cannot be said that the most efficient search is performed even with the Nicollan method. Furthermore, when the vehicle is moving along the shortest route and deviates from the shortest route for some reason, there may be cases where it is desired to find and display the shortest route again towards the same destination position. However, if the shortest route between the new current position and the new destination position is found again, the efficiency of the route search is not good and there is still a problem in terms of operation speed.

[Means to solve the problem]

As shown in FIG. 1(a), the first invention includes a route data storage means, a position input move, a bidirectional search move, and a search order m+.
It is composed of a control means, a shortest route determining means, and a display means. The route data storage means is a means for storing route data, such as a road map, a circuit, etc., which is composed of nodes and branches and is the target of the shortest route search. The position input hand is a means for inputting a search start position and a search end position. For example, it is a means for inputting the current position and destination position of a mobile object on a map. The bidirectional search hand is a means of searching for the shortest route by sequentially searching for nodes or branches using route data from both directions of the search start position and the search end position input by the position input hand. The shortest route is defined as the route that minimizes the overall evaluation value of route length, required time, cost, etc., as well as the failure of these factors. Then, searching from each direction, for example, selects nodes or branches in order from the one with the smallest evaluation value,
It is executed as a procedure to expand the search network. The search order control means is means for controlling the search order based on the bidirectional search moves. The search order is such that the number of search nodes or search branches sequentially searched from each direction is approximately balanced in the bidirectional search process. That is, the speed of progress of the search is controlled so as to be balanced in the bidirectional search. The shortest route determining means is a means for determining the shortest route from a search start position to a search end position from among routes to which search nodes or search branches are connected in both directions. for example,
In the search process, when the node for which the shortest route to the search start position has been determined and the node for which the shortest route to the search end position has been determined match first, the route on which that node exists is determined to be the shortest route. The display means is means for displaying the shortest route. For example, it is a means for displaying a road map, and also for displaying on the road map the current position which is the search start position, the destination position which is the search end position, and the shortest route connecting the two positions. The second invention, as shown in FIG. The route data storage means, position input hand, bidirectional search hand, shortest route determination means, and display means have the same configuration as in the first invention. The search area limiting means limits the search area by the bidirectional search move. The search area is limited to an ellipse in which the search start position and the search end position are near the focal point and the line segment connecting these two positions is a long sleeve, or an internal area of a shape approximated to the ellipse. The focal position and the eccentricity for specifying the elliptical shape may be changed depending on the distance between the search start position and the search end position. That is, depending on the positional relationship between the search start position and the search end position, an area where there is a high probability that the shortest path exists may be widened, and an area where there is a low probability that the shortest path exists may be narrowed. In addition, for boat fishing, in addition to the inside of the ellipse mentioned above, the area where there is a high probability of the existence of the shortest route is set inside the ellipse, and the area where there is a low probability of the existence of the shortest route is set outside the ellipse. It is fine as long as it is inside the shape. Therefore, the search area is surrounded by the interior of the ellipse, the interior of an ellipse-like curve, the interior of a rectangle inscribed or circumscribed by the ellipse, and two parabolas facing each other whose focal points are the search start position and search end position. It may also be an area where the area is closed. The third invention is comprised of a route data storage means, a position input move, a bidirectional search move, a degenerate search means, a shortest route determination means, and a display means, as shown in FIG. 51(C). Position input hand, bidirectional search hand, shortest route determination means,
The display means has the same configuration as the first invention. The route data record tα hand stores node and branch information and rank data indicating the priority of the branches. Further, the degenerate search means is a means for restricting search nodes or search branches that are sequentially searched by their rank data. This grade includes, for example, road width, number of lanes, expressways, national highways, etc.
This indicates the priority of branches, which are distinguished by road class such as prefectural, municipal, and village roads. Therefore, restricting the grade of options according to predetermined conditions means that, for example, when one route is being searched along a wide national highway, narrow side streets connected to that national highway will not be searched. excluded,
This means that branches connected to that side road will not be searched any further, increasing the search speed. Further, the fourth invention provides the above-mentioned first invention, as shown in FIG. 1(d).
In the invention to the third invention, a search start position determining means, a second shortest route determining means, a one-way searching means, and a third shortest route determining hand are further added. This fourth invention is effective for searches after the second time when the search end position remains unchanged and the search start position changes. The search start position determining means is means for determining whether the search start position is on the already determined shortest route or within the search area from the search end position. The second shortest route determining means is means for determining the shortest route from the search start position to the search end position based on the search result data from the search end position when the determination result of the search start position determination means is positive. The unidirectional search means is a means for searching for the shortest route by sequentially searching nodes or branches only from the search start position when the determination result of the search start position determination means is negative. That is,
The search results from the search end position have already been obtained from previous searches, so they are used. The third shortest route determining means is means for determining the shortest route from among the routes connected to the search nodes or search branches from the one-way search that are included in the search result data. That is, as the unidirectional search progresses, the node or search branch is connected from the search end position. However, in this case, the route that is connected first is not necessarily the shortest route, so the route with the lowest evaluation value is determined as the shortest route from among several connected routes. .

[Effect]

In the first invention, when a search start position and a search end position are designated by a position input hand, a search is sequentially performed in both directions between the search start position and the search end position using a bidirectional search hand. The search order control means controls the search order in the bidirectional search process so that the number of nodes or branches to be searched is equal. Then, the shortest route determining means determines the shortest route from among the routes in which search branches or search nodes match from both directions as the search progresses, and the display means displays the shortest route. Further, in the second invention, in the bidirectional search process, the search area limiting means replaces the search order control means of the first invention.
The nodes or branches to be searched are limited to an area such as an ellipse where there is a high probability that the predetermined shortest path exists. Further, in the third invention, the search node or search branch to be searched is further limited by the branch rank data in the bidirectional search process by the degenerate search means replacing the search order control means of the first invention. Further, in the fourth invention, in the second and subsequent searches, when the search start position determining means determines that the search start position is on the already determined shortest route or within the search area from the search end position, By the second shortest route determining means,
The shortest route from the search start position to the search end position is immediately determined based on the search result data from the search end position. Further, if the search start position determining means determines that the search start position is not on the shortest path that has already been determined or within the search area from the search end position, the one-way search means sequentially searches only from the search start position. The shortest path is searched. Then, when the third shortest route determining means determines that the search progresses and the search node or search branch from the one-way search is connected to the search node or search branch of the search result data, the connected route The shortest route is determined from among them.

【Example】

The present invention will be described below based on specific examples. FIG. 2 shows the configuration of an in-vehicle navigation device 10 according to an embodiment of the present invention. In this embodiment, the search start position is specified as the current position, and the search end position is specified as the target position. In the figure, a computer 20 is a device that accesses a data storage medium 21 and executes shortest route search calculations and the like. Is the computer 20 a dedicated microprocessor?
Alternatively, it may be configured with a general-purpose personal computer, and the storage medium 21 may be configured with a floppy disk, hard disk, RAM disk, or the like. The storage medium 21 stores a map database and a search program, and forms a search data file that records search process data and search result data. The in-vehicle navigation device IO also includes a receiving means 50 for receiving the current position of the vehicle. The receiving means 50
is composed of an on-vehicle antenna 51 and a receiver 52, and receives point code data representing the current position from a transmitting means 60 installed outside the vehicle, and sends the data to the computer 20 over a line 8.
4. The transmitting means 60 is composed of a transmitting antenna 61 and a transmitter 62, and is generally installed on the roadside, and is a means for transmitting point code data of the installed position. In addition to the above method, the current position can be determined by estimating the direction and travel distance using a known vehicle-mounted sensor, or by positioning the current position by receiving positioning data from a communication satellite. It's okay. The in-vehicle navigation system+jf110 has a display means 40 composed of a CRT display 41 or an X'YZ monitor. The display means 40 is
Displays a map of several streets, vehicle symbols, and the shortest route between the current location and the destination location. Also, display hand R
40 is further equipped with a panel switch 43 and a touch switch 44 provided on the screen, through which operator nA control commands can be input in place of the control console 30. for example,
The destination position can be input by directly specifying a point corresponding to the destination position on the map on the screen by operating the switch. In addition, the operator can also use panel switch 4.
Various commands can be generated by alternately combining the operating procedures of 3 and the touch switch 44. Display means 40
is connected to the control console 30 and computer 20 via a changeover switch 45. The control console 30 controls the screen of the display means 40, is connected to the computer 20 via a line 81, and outputs command data to the computer 20. The computer 20 sends a video signal, for example, an RGB signal, to the display means 40 via a line 83, and a 1° switch circuit 71 for displaying a map or the like on the screen generates an on/off signal in conjunction with an engine key switch 72. line 82
The signal is output to the computer 20 via. When the computer 20 receives this ON signal, it resets the re-search flag to O in order to remember that the route search has not been executed even once. When the power of this device is turned on, a map centered on the current location inputted in a method described later is displayed on the display means 40. The operator then operates the switches 4 of the control console 30 or display means 40 as described above.
3. Operate 44 to specify the target position. The target position data obtained by this designation is input to the computer 20 and stored in the storage medium 21. Further, when a vehicle passes by a transmitting means 60 installed on the roadside while driving on a street in a given area, data indicating the current position transmitted by the transmitter 62 is received by the receiver 52 and sent to the computer. 20 inputs this data from the receiver 481152 and records it as current position data and stores it in the α medium 21. A map may be constructed mainly around nodes or around branches (links). The map database, which is constructed 1114 around nodes, is composed of the following information. (1) Code number of the node that defines the street (2) Go straight;
Traffic flags that stipulate traffic rules 111 such as right and left turns (3) Link traffic current i1r such as vehicle type regulations and time zone regulations
! (4) Link attribute values such as link distance, travel time, or speed (5) Link attribute values such as road type and road class (6) X% and Y coordinates of nodes, as well as administrative district boundaries and ports , rivers, facilities, railways and their names, coordinates, etc. are included. This stored map database is used when navigating a given geographical area. When the vehicle moves from point to point, computer 20 can call up an appropriate map and display it on CRT display 41. An in-vehicle navigation device equipped with dead reckoning can estimate the trajectory of the vehicle and overwrite this on the map being displayed. Furthermore, the shortest route obtained by a route search algorithm described later can be overwritten on the displayed map. The shortest route obtained by the route search algorithm is stored in the search data file of the storage medium 21 as a sequence of node numbers forming the route. Search result data at the time when the route search is completed is stored in the storage medium 21 as a transient search data file. The search data file is composed of a current file that expands search branches, and a node file output that expands search nodes. The following data is expanded to the current file. (1) Arrangement of search branches that are opened sequentially at the start of route search (2) Flag indicating whether the search branch has been opened or not yet opened (3) Route cost to the search branch. For example, the route distance or travel time (4) The sequence of search branches with the previous node number (1) that continues on the shortest route to the search branch has the route cost of (3) as the attribute value, and the route cost is the minimum It is used to extract search branches that become . The flag (2) is a set of search branches for which the shortest path has been determined (permanent technique), and branches for which the shortest path has not yet been determined but are in the process of searching for the next node using the search branch (active technique). used to distinguish between sets of If the current file composed of the above data has a data structure based on the heap method or the packet method, the set of branches to be opened next can be limited, and the branch with the minimum evaluation value can be extracted efficiently. This current file has one of the search branches as a Lou code unit, and the size of the file increases as the search progresses. This current file is composed of two subfiles that are expanded during the search process from the current position and the target position. Further, the node file is used to distinguish and store nodes under search (active nodes), nodes for which the shortest path has been determined (permanent nodes), and nodes whose search branch has not yet been extended (dormant nodes). This node file is also expanded by searching from the current position and searching from the destination position.
It is divided into two subfiles. Also, the node file used for searching from the target position contains 2 files at the end of the search.
Search result data used in the search process after the number of times is stored. Next, the shortest route search procedure will be explained according to a flowchart showing the processing procedure of the computer 20. As shown in FIG. 3, programs are broadly classified into three types. The first is the main program that controls the screen display, input of the target position, and current position, and monitors the whole thing.The second is the main program that refreshes the CRT display 41 and controls the control console 30.
The third is a program for inputting operation data etc. from the computer, and the third is a program for executing the shortest route search. Of these, the second program interoperates with the main program and the third shortest route search program each time refresh or data input occurs, and the third shortest route search program executes the shortest route search when the current position is input. The program is configured to interoperate with the main program each time a request occurs. The main program responds to all information processed by the computer, calculating and formatting the necessary data. For example, it calculates and processes map data to be displayed and selected on the CRT display 4I, command data for the current position and destination position, point codes indicating the current position and destination position and search mode to be given to the shortest route search program. Furthermore, the re-search flag is reset to 0 every time the target position is updated. Next, the shortest route search procedure will be explained. In FIG. 4, in step 100, it is determined whether or not this is the first search by checking the re-search flag. If the re-search flag is in a reset state of 0, it means that this is the first search, and the search execution program is executed in step 102, and after the search is executed, the re-search is performed to indicate that the first search has already been completed. The flag is set to 1 and the shortest path is updated in step 104. If it is not the first search, the process moves to step 106, where it is determined whether the current position is on the shortest route that has already been found, and if it is on the shortest route, the shortest route is updated. The program will be terminated without doing so. That is, it is sufficient to simply update the current position on the map. If the current position is not on the shortest route, the process moves to step 102 and a re-search for the shortest route is executed. Then, the main program is executed based on the search results of this program, and the shortest route found is
displayed on the display 41. Next, the search execution procedure executed in step 102 will be explained. In FIG. 5, in step 200, it is determined whether or not this is the first search by comparing the re-search flag. If it is determined that this is the first search, step 20
The process moves to step 204, where the initial search execution program is executed, and if it is determined that it is not the first search, the process moves to step 204, where the re-search execution program is executed. After the search is executed, it is determined in step 206 whether the search is successful or not. If the search is successful, the process ends. If the search is not successful, a search using equal nodes is executed in step 208. That is, in the search at steps 202 and 204, the search area is limited to an elliptical area, so there may be a case where a route connecting the current position and the destination position does not exist in the elliptical area. An unrestricted bidirectional equinodal search is performed. Next, the initial search procedure executed in step 202 will be explained. Before explaining the processing procedure in detail, the search concept will be explained next. The initial search procedure includes a method of searching from both the current position and the destination position (bidirectional search), a search method of restricting the search area to the inside of an ellipse (elliptic search), a method of searching from both directions of the current position and the target position (elliptic search), a method of searching from both directions of the current position and the target position (elliptic search), and a method of searching for nodes or A search method that balances the number of branches (equal node search), route length for evaluating the shortest route, required time, cost, etc., or an evaluation value that comprehensively evaluates these (hereinafter referred to as
This evaluation value is referred to as "cost")) and is executed using the AND conditions of a method of searching in descending order of cost (equal cost search) and a search method of limiting search branches according to their ranks (degenerate search). When performing bidirectional search, equal node search, and equal cost search, the search area conceptually expands as the search progresses around the current position [0 and the destination position idD, as shown in Figure 8. It becomes a circle with equal radius. When the two circles intersect and a permanent node extending from both directions is first connected, the path along which that node exists becomes the shortest path connecting the current position and the destination position. Further, elliptical search is a search method in which the search area is limited to the inside of an ellipse whose focal points are in principle the current position and the target position, and whose major axis is the axis connecting the focal points. Then, we convert the elliptic search into the above bidirectional search, equinode search,
When combined with equal cost search, as shown in Figure 9,
It becomes an exploration model. By limiting the search area to the inside of such an ellipse, a search branch can be directed in the direction X away from the destination position 1ftD in a search from the current position tffo, and in the direction Y away from the current position O in a search from the destination position. Area A where deployment is restricted and there is little possibility of the shortest path existing.
, B is restricted. Therefore, high-speed search becomes possible. Furthermore, the shape of the ellipse can be controlled parametrically by changing the ratio F (0<F<1) of the major axis and minor axis. F
When P is increased, it approaches a circle, and when P is decreased, it becomes an elongated ellipse. When the current position and the target position are the focal point, if the distance between the current position and the target position, that is, the distance (2C) of the focal point 110 is short, the roughness of the network becomes relatively large, and the shortest path within the ellipse is may not be included. To avoid this problem, when the distance between the current position O and the destination position (OD-to-OD distance) is short, it approximates a circle, and when it is long, it is formed into an elongated ellipse to increase search efficiency. On the other hand, if you get closer to a circle, the separation rate will become smaller and the shortest path in the backward direction may be cut, so offset the distance between the focal points so that the focal point is 17 points outside the current position and the target position. The ellipse is larger than the distance between the two. That is, let C0 be the offset, and let C=C+CG be the distance C between the new focal point and the center of the ellipse. F is changed parametrically depending on the length of the OD distance. In other words, when C is small, F is made large, and as C becomes large, F is made small and the ellipse e is elongated. In the example, a threshold value of C+ < Cz < Cs is set, and C<CI
Then +? =F,, if C1≦C<C2, then F= F2,
If C3≦c<C3 then r= r', If C3<C then r'
= r', as a step function. However, F, -1
'4 is 1 >F+>Fi>l? 3>L>O is a constant. In the degenerate search, while searching, search branches are sequentially raised to roads with equal or higher road classes, cutting out road techniques with low priority, and searching is performed using a degenerate road network. As a result, for example, when a search is being executed along a wide national highway, etc., the search branch is prevented from extending, such as on a narrow side road connected to the national highway, and an efficient search is performed. . Road classes can be set arbitrarily; for example, the classes may be set in the order of municipal roads, prefectural roads, national roads, and expressways. In addition, the size of roads, design traffic capacity,
Classes can also be set based on design speeds and differences between toll roads and 11 toll roads. If degeneracy is performed based on the road grade, the network will become coarser as the grade increases, which may cause route breaks, so in order to avoid road cuts,
Connections are allowed up to a grade one rank lower than the previous search branch. In the end, if all the above searches are executed, an extremely efficient search will be executed, and the concept of the search is based on the first
As shown in the figure. Next, the initial search procedure will be explained in detail according to FIG. 6, and each symbol and term will be defined as follows. S: Node number of the current position, its coordinates (XS,, YS,) T: Node number of the destination position, its coordinates (XT,, YT,) i: Any active node number: *Active node that has just been generated The number of active nodes is as defined before, although the shortest path is not yet determined,
A search branch (active technique) extends from a permanent node and refers to a node that is currently open. m: Number of any permanent node As defined earlier, a permanent node is a node for which the shortest path to an S node or a T node is determined. Also, the search from the current position is S search, the search from the destination position is T search, and the permanent node by S search is S permanent node, T
A permanent node obtained by searching is called a T-permanent node. j: Number of any connected node A connected node is a node whose active node or permanent node in the S search or T search matches the active node or permanent node in the other party's T search or S search. V: General node number 5 (v
): Means the minimum cost at the current point in the search from the S node to the V node, and this is called the node cost. SP(m): The two-to-one cost of a permanent node l is called a permanent node cost. Further, as defined earlier, cost is an evaluation value of the shortest route including distance, required time, etc., and the route with the minimum cost is the shortest route. Therefore, the cost is a parameter for expanding the search branch, and there are concepts such as the cost to the node, the cost of the search branch, and the cost of the route. T(v): Means the minimum cost at the current point in time of the search from the v node to the T node, and this is called the node cost. ST(m): The two-to-one cost of permanent node m is called permanent node cost. R(j): Means the cost of the route on which connection node j exists at the current time of the search (the route from the current position to the destination position), and this is called the route cost. U: The number of the minimum connected node for the route cost (RU) at the current point in the search Regardless of S search or T search, on the route from the S node to the T node, the T node side is called the front, and the Among the two nodes, the node closer to the T node is called the forward node with respect to other nodes. Also, conversely, S
The node side is called the backward node, and the node near the S node is called the backward node with respect to other nodes. P(i): Number of the nearest backward permanent node on the shortest path connected to active node i at the current time of the search Q(i): Number of the nearest backward permanent node on the shortest path connected to active node 1 at the current time of the search Number α of the nearest forward permanent node: This is the minimum value among the node costs of the active nodes of the S search at the current time of the search, and this value is called the search cost. This search cost becomes a parameter for selecting a permanent node from active nodes in the S search. β: Refers to the minimum value among the node costs of active nodes in T search at the current time of the search, and this value is called the search cost. This search cost becomes a parameter for selecting a permanent node from among active nodes in T search. dm, i: Means the cost of the search edge between permanent node m and active node 1, and this is called search edge cost. a, b: major axis, minor axis of ellipse, a=C/1-P',
b= aPC: Distance between the center of the ellipse and the focal point CII CI C-: Threshold, O<CI<C2< C
3F1-, Fi, Fs, F4: constant, 1 >F+>Fz
>Us>Pa>F: Ratio of major axis to minor axis of ellipse I'=b/a
If C≦C1, pp. If CI<C≦C3 then P = P 2 If Ci<C≦C5 then I? = F. If C's<C, I'=F. ×. , yo: Center coordinates of the ellipse θ: Inclination of the ellipse θ=5in xl+yl' Coordinates of active node i f(x, y): Inside/outside determination function of the ellipse ((YT@-YS,)/2C f (X, y> If ≧0, (X, y) is inside the ellipse. If f (X, y) < O, (X, y) is outside the ellipse. A'5 (V): Back node P (v) and AT(v): Refers to the road class of the search branch between node V, and the higher the class, the higher the class. AT(v): Refers to the road class of the search branch between node V and forward node 0(v), and the higher the class, the higher the class. Next, the search procedure will be explained according to the flowchart of FIG. 6. In step 300, initialization of the search data file is executed. That is, the S node and the T node are set as the first active nodes in the search data file. node file, and the node cost of those nodes is 5(i)=0
゜T(i)=O, the backward node and the forward node are I'(
i)=S, Ω(i) −T. Next, in step 302, each parameter of the ellipse is calculated from the coordinates of the S node and the T node according to the above definition, and an ellipse function is determined. Next, in step 304, search costs α and β are initialized to O. That is, the minimum value of the node cost of the active node is O at present. Next, the process moves to step 306, and the number of S permanent nodes is T
It is determined whether the number is equal to or less than the permanent number of nodes. If the number of S permanent nodes is less than or equal to the number of T permanent nodes, step 30
The S search of steps 8-322 is performed, otherwise the T-node search of steps 332-346 is performed. Equinode search is executed by the process of step 306. That is, at the current time of the search, permanent nodes are expanded alternately in the S search and the T search so that the number of permanent nodes is balanced. In the case of S search, in step 308, the node whose node cost 5(1) takes the minimum value with the search cotos α or more is selected from all the active nodes of S search, and that node is selected as the permanent node m. be done. Next, the process moves to step 310, and it is determined whether the permanent node m exists within the ellipse. If it does not exist, the permanent node m is discarded, and the process returns to step 306, where the next search is started. Processing is executed. If it is determined that the permanent node m exists within the ellipse, the process moves to step 312, where the grade fS (m) of the backward search branch of the permanent node m is determined as the grade of the backward search branch one step further back. It is determined whether or not it is greater than or equal to 1s(1'(m))-n. If the determination result is NO, the permanent node m is discarded, the process returns to step 306, and the next search process is executed. That is, this means that a search branch with a lower rank that is more than n in rank than the rank of the backward search branch one position behind is not selected, and the selection of search branches is restricted. This step performs a degenerate search. Step 314 is executed when the ellipse search condition of step 310 and the degenerate search condition of step 312 are satisfied, the selected node is a valid permanent node m, and its node cost S (m) is a permanent node - Tocost SP (
m) is registered in the node file. Next, in step 316, the map database is searched for search branches connected to the permanent node m, and all active nodes k to be connected next are determined. When the active node k is expanded to the current file for the first time in the next step 318, the value obtained by adding the expanded search branch cost to its permanent node cost, that is, S
P (m)+dm,k is registered as the node cost S (k) for the active node. In addition, if the expanded active node k is an active node that has already been expanded into the current file, the registered node cost S
(k) and SP (01) +dm, k are compared, and if SP (m > +dm, k is smaller, it means that a path with lower cost to the active node has been found) In that case, the node cost S (k) for that active node is its value SP (
m) → dm, re-registered to k. Also, the node I'(k) subsequent to the active node is re-registered to m. The above processing is executed for all newly expanded active nodes k. Next, in step 322, it is determined whether there is any active node or permanent node in the UT search among all the newly expanded active nodes. If not, it means that no connected node has occurred, and the process returns to step 306 to execute the next search process. If it is determined in step 306 that the number of S permanent nodes is not less than or equal to the number of T permanent nodes, the T search in steps 332 to 346 is executed in exactly the same way as the S search. By the way, the above processing contents are illustrated in Figure ¥J11. In the first execution cycle, the decision in step 306 is YIES, the S node is selected as the permanent node in step 308, and the decision in steps 310 and 312 is Y.
IES, permanent node cost 5P in step 314
(S)=O is determined. Note that since the initial setting is Js<S)=6s(1'(S))=n, step 3 is executed in the first execution cycle.
The determination of 10 naturally becomes Y[iS. As shown in FIG. 11(a), in step 316, the search branch connected to node S is selected, and 1 to 4 are determined as active nodes to be expanded next. Then, in step 318, since there are no active nodes that have already been deployed, node costs S (k) are determined for the four new active nodes. Since the permanent node cost SP (S) is O, the node cost 5 (k) is equal to the search branch cost ds, k.
. Also, the downstream node P (k) of each active node is registered as an S node. Also, in step 320, the search cost α is updated to the minimum value among all the sword costs 5(i) at that time. Also, in step 322, as shown in the isio diagram (b), among the active nodes, a node that matches the active node of the T search, that is, the node T (currently only the T node is expanded) is selected. If there is, then that node, for example, the node, is determined to be the connecting node, and a route has been constructed, so that it is determined in steps 324 and subsequent steps whether or not that route really becomes the shortest route. The processing will be described later. The explanation will continue regarding the case where no connected node occurs in the first execution cycle. In the second execution cycle, T search is performed, and by similar processing, the search state is as follows at the end of execution of step 346.
The result is as shown in FIG. 11(C). The third execution cycle is S search, step 30
In step 8, among the currently active nodes i (i.e., k, . If the node exists within the ellipse, since is (S) is initialized to n, the search branch , is selected regardless of its grade, so in step 314, the permanent node m1 becomes the node. , and its node cost S(m
, ) is also registered in the node file as a permanent node cost SP<mI). Next, in step 316, the active nodes L, ka connected to the permanent node 1TII are expanded, as shown in FIG. 11(d). Among these, the active node is a new active node, so in step 318, the search branch cost dm, the permanent node cost of the permanent node m) SP(mI) of the search branch It is registered in the current file as a node cost of 5 (ks). On the other hand, since the active node 2 is an active node that has already been expanded, the currently registered node cost 5 (kz>), the search branch cost of the newly obtained search branch L1゜'
If mlT'IO+permanent node cost of permanent node ff11)SP(mI) is smaller, node cost 5(ki) is replaced by P1 to that value. Also, the node i'(k,) after 2 to the active node is rewritten from node S to node l. In other words, to go from node S to active node 2, the cost is lower to take a route that passes through permanent node 11+1 and search branch 1.1° than to pass through search branches 1 and 2, and that route is the shortest. It becomes a route. The search network at that time becomes as shown in FIG. 11(e), and in step 320 all active nodes (J,
ks, L, ks), the node cost S (
The minimum value of k), for example 5 (ks), becomes the new value of the search cost α. In this way, as the search is executed many times, the result becomes as shown in Fig. 11 (), where the search branch within the ellipse has a magnitude n greater than that of the search branch one position behind or in front of it. Permanent nodes are generated one after another with lower-grade choices exceeding
When it becomes ES, it means that a connection node has been generated. Next, the procedure for searching for the shortest route after a connected node is generated will be explained. When a connected node is generated for the first time, the connected node is also an active node in the S search and the T search, as shown in FIG. The node cost 5 (Jl) for the node and the node cost T (J
The route cost R(L) is calculated by the sum of R(L) and R(L). and the minimum value I at step 326 in the first execution cycle
JR becomes its route cost 1-R (Jl), and in step 328 it is determined whether the minimum value MR is less than or equal to the search cost α plus the search cost β. If the condition is established at the first appearing connection node J+, it is limited to an equal sign, and the node cost) S(''+) is the search cost α plus the node cost T(Jl).
is equal to the search cost β. This means that in the next and subsequent searches, the connected node "1" will always be made a permanent node in the S search and the T search. That is, this route is the first route in which the S search and T search are connected at a permanent node, and becomes the minimum cost route. Therefore, in step 330, the path on which the connected node exists is determined to be the minimum cost path. On the other hand, if the determination in step 328 is NO, in the subsequent search, a connected node may be generated on another route before the connected node j, is made a permanent node, or a downstream node I of the connected node J, '(jI) or forward no 1'o(
jI) may be stale, ie, the least cost path may be changed. Therefore, it is necessary to proceed to step 306 and continue the next search. Also, as the search progresses, steps 324 and subsequent steps are executed each time a connected node occurs. In step 324, the route cost R('') is calculated for the generated connection node.
is calculated. Then, in step 326, among all the connected nodes J that have occurred so far, the route cost R('')
The node with the minimum value MR is set as the node U, and the minimum value MR is selected. Note that when focusing on a certain route, the first connected node on that route is always the active node of S search and T search, and as the search progresses, that connected node becomes a permanent node of S search or It becomes a permanent node of T search,
Finally, it becomes a permanent node in both searches. When this node becomes a permanent node, cost R('')<α+β is always satisfied. However, even if the condition of cost R(j)<α+β is satisfied, the node cannot be said to be a permanent node in both searches.
Since the route cost of a route in which a connected node appears for the first time in subsequent searches always exceeds the current α+β, a minimum cost route is not discovered from these routes. Therefore, the minimum cost route exists among the already connected routes with R(j)<α+β. Therefore, all connected nodes
The minimum value MR of path cost t-R(j) for M
The route that satisfies R≦α+β becomes the minimum cost route, that is, the shortest route. Any node V on the above shortest path is the backward node P(V) in the S search, and the forward node 0 in the T search.
Since (v) has been clarified, the shortest possible time is to search backward nodes one by one from the connected node U to the S node, and search forward nodes one by one to the T node for the T search. All nodes on the route can be known. Next, the procedure for re-searching when the current position changes without changing the target position will be explained with reference to FIG. In step 400, it is determined whether the S node corresponding to the new current position matches the T permanent node of the search result data. If they match, it means that the S node exists in the previous T search area, and the process moves to step 434, where the shortest path to the T node is found by sequentially tracing forward nodes 0(v) based on the search result data. You can ask for it. Also, if the S node does not exist in the T search area,
Processing from step 401 onwards is executed. In step 401, initial settings similar to step 300 are performed. However, the search result data from the target position is not deleted. Further, in step 402, an elliptic function focusing on the new current position and the unchanged target position is calculated, and in step 404, the search cost α is initialized to 0. Also, the search cost β is saved as the final value of the previous T search. Then, the S search in steps 406 to 420 is executed. This S search is similar to the S search in steps 308 to 322 in FIG. However, in step 420, it is determined whether the active node k resulting from the S search is a T permanent node stored as search result data in the node file. If the determination result is NO, the process returns to step 406 and the S search is continued. If the determination result is YES, the process moves to step 422 and steps 422 to 42G are executed. This process is similar to steps 324-328 and is 5. If the determination at step 426 is YIES, then at step 42G the number of occurrences of a route that satisfies the condition at step 426 is counted. Then, in the next step 430, it is determined whether the number of occurrences Z is greater than or equal to a predetermined number of times W, and the process returns to step 406 and the S search is executed until the number of occurrences Z is greater than or equal to the predetermined number of times. That is, since the connected node j is a T permanent node, the node cost T(j) is smaller than the search cost β. Therefore, even if the connection node J satisfies the condition of step 426 for the first time, the node cost S (j) is not necessarily equal to the minimum value, that is, the search cost α. Therefore, there is a possibility that a connection node J will occur in the subsequent search for S, and a route will occur where the route cotos R(j) takes a value smaller than 1. Therefore, the conditions of step 426 are changed up to a predetermined number of times W? It is necessary to detect a route that yields 1j4 and set the route for which the route cost )R('') takes the minimum value as the shortest route. That is, it is assumed that the connection of the shortest route will be completed within the predetermined number of times W, and even if the S search is continued beyond the predetermined number of times W, there is little possibility that the shortest route will be discovered. In the above embodiment, it is determined whether the active node of the S search in step 420 matches the permanent node of the T search, but the search result data is the data of the search final state including the active node of the T search, and the S search After a connected node whose active node matches the permanent node or active node of the T search is detected, the T search and the S search are simultaneously executed until the condition of step 426 is satisfied.
28 and step 430 are no longer necessary, and the shortest path will be found the first time step 426 is satisfied. However, the T search is a search that continues from the search cost β. In addition, in the bidirectional equinode search in step 208 of FIG. 5, when a search is performed in combination with an elliptical search or a degenerate search, the route connecting the current position and the destination position disappears due to network limitation or degeneracy. Used for interpolation when the shortest path cannot be found. If you only search for equal nodes, the range is not limited, so you will not lose the shortest route, and you will always be able to find the shortest route. Bidirectional equinodal search reduces search time compared to bidirectional equicost search when the road network has sparse density. This is because the number of nodes searched when performing a bidirectional equal-node search is smaller than that during a bidirectional equal-cost search. The proof is that when the node density on the S search side and that on the T search side are constant within their respective search ranges, the number of nodes is found as the search surface 'hI This can be shown by taking the difference between the number of nodes searched when performing a search and that of a two-way equal cost search, and using Schwartz's inequality, the difference is always negative. The search results obtained by the above embodiment device are shown below. A search was performed by selecting a plurality of S-node and T-node pairs on a map database with approximately 2,800 street nodes and approximately 4,200 links in a given area. Compared to the search results using the conventional unidirectional search label determination method, the time required for both equivalent node searches was up to about 5 times shorter, and when elliptical search was added, the time was reduced up to about 50 times. Furthermore, when performing a degenerate search, the time was reduced by several times that of an ellipse search. In the second and subsequent searches, the time was more than doubled compared to searches that did not use the first search result data. Note that, instead of using an ellipse, the search 11a may be limited to a rectangle that includes the current position and the target position, or an area surrounded by two parabolas with the current position and the target position as focal points. Then, depending on the length of the distance between the current position and the destination position: d, these shapes are parametrically determined as follows: 1. lj ul+
You may do so. In addition to setting road classes, network degeneration may be achieved by adding penalty costs to link attribute values such as distance and travel time. For example, by adding a penalty to right and left turns and adding them to the distance and travel time, the route in the right and left turns becomes difficult to pass, and the search proceeds in the direction of going straight, and a similar effect can be obtained by degenerating. . In addition to the shortest route search using a road map as described above, the present invention can also be applied to any device that searches for a route with a minimum arbitrary evaluation value in an arbitrary network.

【Effect of the invention】

The first aspect of the invention is that in the bidirectional search process by the bidirectional search z (mi means), the search order is controlled so that the number of search nodes or search branches sequentially searched from each direction is approximately balanced. In route data with different branch densities,
The number of nodes or branches expanded before the shortest path is found can be minimized. Therefore, the shortest route search time can be shortened. The second invention also provides a search node or a search branch to be searched in the bidirectional search process as an ellipse or an ellipse thereof, with the search start position and search end position near the focal point and a line segment connecting these two positions as the long axis. Since the search area is limited to those existing in the internal region of the shape approximated by
The area where there is a high probability that the shortest path exists becomes the search area,
Since areas with a low probability of the existence of the shortest route are excluded from the search area, extremely efficient searching is possible and the shortest route search time is shortened. Further, in the third invention, the search nodes or search branches to be searched in the bidirectional search process are limited based on the grade data indicating the priority of the branches, so that the route search is executed along a route with a high grade. This prevents route searches to branches of low class that are connected to branches of high class and which have a high possibility of being connected to high class branches, making it possible to perform searches with extremely high efficiency and shorten the shortest route search time. Further, in the fourth invention, when the search end position is the same as the previous search, if the search start position is on the shortest route or within the search area, the search end position is changed from the already found search end position. The shortest route from the search start position to the search end position is determined based on the search result data, and if the search start position does not exist on the shortest route or within the search area, nodes or branches are sequentially searched only from the search start position. The shortest route is determined from among the routes connected to the search node or search branch included in the search result data from the one-way search. The second and subsequent route searches when the destination position remains unchanged can be performed efficiently, and the shortest route search time can therefore be shortened.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing the configuration of the present invention.
FIG. 2 is a configuration diagram showing an in-vehicle navigation device according to a specific embodiment of the present invention, FIGS. 3 to 7 are flowcharts showing processing procedures of the device according to the embodiment, and FIG.
Figures 1 through 11 are explanatory diagrams showing the search procedure. 10 In-vehicle navigation system δ 20-Computer active node m

Claims (4)

[Claims] (1) A route data storage means that stores route data consisting of nodes and branches; a position input means that inputs a search start position and a search end position; In the bidirectional search process by the bidirectional search means, which searches for the shortest path by searching for branches, the search order is adjusted so that the number of search nodes or search branches sequentially searched from each direction is substantially balanced. In the bidirectional search process by the controlling search order control means and the bidirectional search means, search nodes or branches from both directions are connected.
A shortest route searching device having a shortest route determining means for determining the shortest route from a search start position to a search end position, and a display means for displaying the shortest route. (2) A route data storage means that stores route data consisting of nodes and branches, a position input hand that inputs a search start position and a search end position, and nodes sequentially from both directions of the search start position and the search end position. or a bidirectional search means for searching for the shortest path by searching for the shortest route; search area limiting means for limiting the search area to those existing within an ellipse whose long axis is a line segment connecting both positions, or a shape approximated to the ellipse; From among the paths to which the search nodes or search branches are connected,
A shortest route searching device having a shortest route determining means for determining the shortest route from a search start position to a search end position, and a display means for displaying the shortest route. (3) a route data storage means for storing route data consisting of node and branch information and grade data indicating the priority of the branches, a position input means for inputting a search start position and a search end position, and a search start a bidirectional search means that sequentially searches for nodes or branches in both directions from the position and the search end position to search for the shortest route; In the bidirectional search process by the degenerate search means that restricts based on the grade data of the edges included in the data, and the bidirectional search means, search nodes or branches from both directions are connected.
A shortest route searching device having a shortest route determining means for determining the shortest route from a search start position to a search end position, and a display means for displaying the shortest route. (4) If the search end position is the same as the previous search, a search to determine whether the search start position is on the shortest path that has already been determined or within the search area from the search end position. If the search start position is on the shortest route or within the search area, the start position determination means determines the distance from the search start position to the search end position using the search result data from the search end position that has already been found. a second shortest route determining means for determining the shortest route; and if the search start position does not exist on the shortest route or within the search area, the shortest route is searched by sequentially searching nodes or branches only from the search start position. a unidirectional search means for searching from a search start position to a search end position from among routes connected to search nodes or search branches included in the search result data from the unidirectional search; 4. The shortest route searching device according to claim 1, further comprising a third shortest route determining means for determining a route.