JP7156355B2 - Route guidance method and route guidance system - Google Patents

Description

The present invention relates to a route guidance method and a route guidance system.

Conventionally, there has been proposed a vehicle route guidance device that searches for an optimum route from a departure point to a destination so as to avoid traffic congestion (see Patent Document 1). The vehicle route guidance device described in Patent Document 1 calculates the ratio of the number of traffic jam links to the total number of links for which traffic information is provided for each area obtained by dividing a road map into a mesh, and according to the calculated ratio, to correct the link cost of roads not covered by traffic information in the area. After that, the route from the starting point to the destination is searched so as to minimize the cost.

JP-A-10-38597

However, in the vehicle route guidance device described in Patent Document 1, since the route search performed after the link cost of the non-target road is corrected is performed for the road links on the road map, the search requires a certain amount of time. There is

SUMMARY OF THE INVENTION In view of the above problems, it is an object of the present invention to provide a route guidance method and a route guidance system capable of increasing the speed of route search from a starting point to a destination on a road map.

According to one aspect of the present invention, when guiding a route from a starting point to a destination on a road map, the road map is divided into a plurality of mesh cells, based on ease of passage depending on the traffic capacity in a plurality of cells. Then, for a plurality of cells, a mesh route composed of cells connecting the cell to which the departure point belongs to the cell to which the destination belongs is searched. Then, a route guidance method and a route guidance system characterized by searching for a route composed of road links connecting a starting point to a destination are provided, targeting the road links in the searched mesh route.

According to the present invention, it is possible to provide a route guidance method and a route guidance system capable of increasing the speed of route search from a starting point to a destination on a road map.

1 is a block diagram showing an example of a route guidance system according to an embodiment of the invention; FIG. 1 is a schematic diagram showing an example of dividing a road link map into a plurality of cells according to an embodiment of the present invention; FIG. FIG. 4 is a schematic diagram showing an example of a mesh map according to an embodiment of the invention; FIG. 4 is a schematic diagram showing an example of transit cost change processing according to the embodiment of the present invention; FIG. 4 is a schematic diagram showing an example of transit cost change processing according to the embodiment of the present invention; FIG. 4 is a schematic diagram showing an example of transit cost change processing according to the embodiment of the present invention; 7A to 7D are schematic diagrams sequentially showing an example of route search processing according to an embodiment of the present invention. 8A and 8B are schematic diagrams respectively showing examples of route guidance screens according to the embodiment of the present invention. It is a flow chart which shows an example of the route guidance method concerning the embodiment of the present invention. 4 is a flowchart showing an example of mesh map creation processing according to the embodiment of the present invention; 4 is a flow chart showing an example of processing for changing a transit cost according to the degree of congestion of a cell according to the embodiment of the present invention; 6 is a flowchart showing an example of mesh route search processing according to the embodiment of the present invention. FIG. 13A is a graph showing the relationship between the number of road links per cell boundary distance and the coefficient according to the first modification, and FIG. FIG. 13C is a graph showing the relationship between the magnitude of the spatial deviation of the congestion degree in the cell and the coefficient of the deviation of the congestion degree according to the third modification. 14A and 14B are schematic diagrams showing examples of mesh maps having different mesh sizes according to the fourth modification. FIG. 14 is a schematic diagram showing an example of a mesh map according to a fifth modified example; 16A to 16D are schematic diagrams sequentially showing an example of mesh route search processing according to the sixth modification.

Embodiments of the present invention will be described below with reference to the drawings. In the following description of the drawings, the same or similar parts are labeled with the same or similar reference numerals. However, it should be noted that the drawings are schematic, and the relationship between thickness and planar dimension, the ratio of thickness, etc. are different from the actual ones. In addition, it goes without saying that there are portions with different dimensional relationships and ratios between the drawings. Further, the embodiments shown below are examples of devices and methods for embodying the technical idea of the present invention. etc. are not limited to the following. Various modifications can be made to the technical idea of the present invention within the technical scope defined by the claims.

<Configuration of route guidance system>
As shown in FIG. 1, the route guidance system according to the embodiment of the present invention includes a traffic management center 1, a traffic information collection device 2, and vehicles V1, V2, V3, . is an integer.). The number of vehicles V1 to Vn is not particularly limited. The traffic information collecting device 2 is, for example, a vehicle sensor installed on the road, and collects road traffic information such as the number of vehicles passing the road per unit time. The traffic information collecting device 2 transmits the collected road traffic information to the traffic management center 1 and the vehicles V1 to Vn.

A vehicle V<b>1 is equipped with a vehicle-side communication device 10 , an in-vehicle device 11 , a map information storage device 12 and a display device 13 . The vehicle-side communication device 10, the in-vehicle device 11, the map information storage device 12, and the display device 13 can be configured by, for example, a navigation device. The vehicle-side communication device 10 receives road traffic information from the traffic information collection device 2 and transmits/receives various types of information to/from the traffic management center 1 . The map information storage device 12 is a memory such as a semiconductor storage device, a magnetic storage device, or an optical storage device, and stores road map information.

The in-vehicle device 11 can be composed of, for example, a microcomputer including a central processing unit (CPU), storage devices (registers, cache memory, main storage device), etc., or a processor equivalent to a microcomputer. The in-vehicle device 11 includes a destination setting section 21 , a vehicle information acquisition section 22 and a display control section 23 . The destination setting unit 21 sets the destination of the vehicle V1 on the road map stored in the map information storage device 12 based on information input by the passenger. Information input by the occupant is input via a user interface such as a touch panel of the display device 13 or a switch in the passenger compartment. Information on the destination set by the destination setting unit 21 is transmitted to the traffic control center 1 via the vehicle-side communication device 10 .

The vehicle information acquisition unit 22 acquires vehicle information including the current position of the vehicle V1 and the running state of the vehicle V1. The current position of vehicle V1 can be obtained from, for example, a global positioning system (GPS). The running state of the vehicle V1 is, for example, the vehicle speed, which can be detected by a vehicle speed sensor attached to the vehicle V1. The vehicle information acquired by the vehicle information acquisition unit 22 is transmitted to the traffic control center 1 via the vehicle-side communication device 10 . Note that the vehicle information acquisition unit 22 sets a departure point on the road map stored in the map information storage device 12 at a position different from the current location of the vehicle V1 based on information input by the occupant and the like. The ground may be included in the vehicle information.

Based on the route guidance information received from the traffic management center 1 via the vehicle-side communication device 10, the display control unit 23 displays a recommended route from the departure point to the destination, such as the current position of the vehicle V1. It controls the display device 13 . As the display device 13, for example, an output device such as a display can be used. Instead of the display device 13, a voice output device (not shown) may be used to present the recommended route and the like to the occupant by voice. It is assumed that the other vehicles V2 to Vn also have the same configuration as the vehicle V1.

The traffic control center 1 includes a center-side communication device 30, a route guidance device 31, a map information storage device 32, and a mesh map creation device . Note that the traffic management center 1 may not have the mesh map creation device 34 . The center-side communication device 30 receives road traffic information from the traffic information collection device 2, and transmits and receives various information to and from the vehicles V1 to Vn.

The map information storage device 32 is a memory such as a semiconductor storage device, a magnetic storage device, or an optical storage device, and has a road link map storage section 51 and a mesh map storage section 52 . The road link map storage unit 51 stores a road link map indicating connection relationships of road links on the road map. A road link is a road section divided between nodes such as intersections on a road map. The road link map includes attribute information such as position coordinates on the road map, road standard, link length, lane width, number of lanes and construction status for each road link.

The mesh map storage unit 52 stores a mesh map that divides the road link map into a plurality of cells in a mesh shape and manages the road link map in mesh units (cell units). The mesh map is previously stored in the mesh map storage unit 52, but it can also be created by the mesh map creation device 34 during route search.

FIG. 2 shows the road link map stored in the road link map storage unit 51 as a plurality of cells A _ij (i=1 to n; j=1) managed by the mesh map stored in the mesh map storage unit 52. ~m: n, m is a positive integer of 2 or more.The case of n=m=4 is illustrated in FIGS. 2 to 6.). The mesh map describes connection relationships between a plurality of road links R0 forming a road link map and a plurality of cells _Aij .

FIG. 3 schematically shows the basic configuration of a mesh map. At the center of each cell A _ij managed by the mesh map is a mesh node N _ij indicated by a white circle (i=1 to n; j=1 to m: n, m is a positive integer of 2 or more. FIG. 3, 4 and 6 exemplify the case of n=m=4.) is set. Each mesh node _Nij is connected by a mesh link L indicated by a line segment.

A mesh link L represents a connection relationship of road links between adjacent cells _Aij . If there is a road link across adjacent cells A _ij , it is defined that there is a connection relationship between them, and a mesh link L is set. On the other hand, when there is no road link across the adjacent cells _Aij , it is defined that there is no connection relationship between the cells _Aij , and the mesh link L is not set. The mesh link L shown in FIG. 3 corresponds to the road link R0 forming the road link map shown in FIG. For example, since the cell A ₁₁ shown in FIG. 2 does not have a road link R0 between the adjacent cells A ₁₂ and A ₂₁ , the mesh node N ₁₁ and the adjacent mesh node N ₁₂ are shown in FIG. , N ₂₁ is not set.

Furthermore, the mesh link L is given a passage cost between adjacent cells _Aij (hereinafter referred to as "inter-cell cost"). The inter-cell cost quantifies the degree of traversability that depends on traffic capacity between adjacent cells A _ij . The ease of passage between cells A _ij , which depends on the traffic capacity, is an index that expresses the ease of passage of a vehicle when _moving between cells A _ij . etc., can be taken into consideration. The higher the easiness of passage between the cells A _ij , the easier it is to pass between the cells A _ij , and the smaller the inter-cell cost is set. Conversely, the lower the easiness of passage between the cells A _ij , the more difficult it is to pass between the cells A _ij , and the higher the inter-cell cost is set. For example, the greater the total value of the traffic capacity of road links between adjacent cells A _ij , the higher the easiness of passage between cells A _ij is defined, and the smaller the inter-cell cost is set. Note that the traffic capacity of a road link can be obtained based on the geometry of the road link, road attributes, and the like.

In FIG. 3, the thickness of the mesh link L is changed according to the inter-cell cost so that it can be intuitively understood. That is, the thicker the mesh link L, the smaller the inter-cell cost given to that mesh link L. For example, since the number of _{road links R0} between the cell A ₃₁ shown in FIG. , the mesh link L of is set relatively thick. _On the other hand, since the number of road links R0 between the cell A ₁₄ shown _in FIG. A mesh link L between N ₁₃ and N ₁₄ and between mesh nodes N ₁₄ and N ₂₄ is set relatively thin.

Also, the mesh node N _ij indicates the connection relationship of road links belonging to the cell A _ij . FIG. 3 exemplifies the case where mesh nodes N _ij are set in all cells A _{ij .} Mesh node N _ij is set to A _ij . On the other hand, when there is no road link belonging to the cell _Aij , it is defined that there is no connection relationship, and the mesh node _Nij is not set to the cell _Aij . The mesh node _Nij shown in FIG. 4 corresponds to the road link R0 that forms the road link map shown in FIG. For example, since there is no road link R0 belonging to cell A11 shown in FIG. ₂ , no mesh node is set in cell _A11 as shown in FIG.

The mesh node N _ij is assigned a transit cost within the cell A _ij (hereinafter referred to as “intra-cell cost”). The intra-cell cost quantifies the degree of traversability that depends on the traffic capacity within the cell _Aij . _Passability , which depends on the traffic capacity within the cell _Aij , is an index that expresses the ease of passage for vehicles within the cell _Aij . can be determined by taking into account The higher the easiness of passage within the cell A _ij , the easier it is to pass through the cell A _ij , and the intra-cell cost is set to be small. Conversely, the lower the easiness of passage within the cell A _ij , the more difficult it is to pass through the cell A _ij , and the higher the intra-cell cost is set. For example, the greater the total value of the traffic capacity of the road links within the cell _Aij , the higher the easiness of passage within the cell _Aij is defined, and the smaller the intra-cell cost is set.

In FIG. 4, the size of the mesh node _Nij is changed according to the intra-cell cost for easy understanding. That is, the larger the mesh node _Nij , the smaller the intra-cell cost given to that mesh node _Nij . For example, since the density of road links R0 belonging to cells _A31 and _A32 shown in FIG. 2 is relatively high and the total value of traffic capacity is relatively large, mesh nodes _N31 , _N32 is set relatively large. On the other hand, the density of road links _R0 belonging to cells _A24 , _A33 , _A34 , _A43 , and A44 shown in FIG. 2 is relatively low, and the total value of traffic capacity is relatively small. As shown, mesh nodes _N24 , _N33 , _N34 , _N43 and _N44 are set relatively small.

The route guidance device 31 shown in FIG. 1 is a controller having a route guidance function. The route guidance device 31 can be composed of, for example, a microcomputer including a CPU and a memory device (register, cache memory, main memory device), etc., or a processor equivalent to a microcomputer. The route guidance device 31 includes a traffic demand prediction unit 41 , a traffic volume prediction unit 42 and a route search unit 43 . The traffic demand prediction unit 41 predicts the current and future traffic demand that will occur in a predetermined area in a predetermined time zone based on road traffic information and the like received from the traffic information collection device 2 via the center-side communication device 30. do. The traffic volume prediction unit 42 predicts the traffic demand predicted by the traffic demand prediction unit 41, and the departure points, destinations, and driving conditions of the vehicles V1 to Vn received from the vehicles V1 to Vn via the center-side communication device 30. Based on this, the traffic volume of each road link in the current and future predetermined time periods is predicted.

The traffic volume prediction unit 42 further calculates (predicts) the degree of congestion of each road link based on the predicted traffic volume of each road link. The degree of congestion is an index that indicates the degree of congestion or congestion on a road link. The higher the congestion degree, the more congested or congested the road link. The degree of congestion may be calculated, for example, as a ratio of the traffic volume to the traffic capacity of the road link. Alternatively, the average speed of vehicles on a road link, the number of passing vehicles, or the like may be used as the degree of congestion. For example, when the ratio of the traffic volume to the traffic capacity of a road link is used as the degree of congestion, if the degree of congestion exceeds a predetermined threshold, it is determined that there is congestion, and if the degree of congestion is less than or equal to the predetermined threshold, it is determined that there is no congestion. good.

The traffic volume prediction unit 42 calculates, for each cell _Aij , a representative value of the degree of congestion of the road links within the cell _Aij , based on the degree of congestion of each road link. As the representative value of the degree of congestion, for example, a simple average value of the degree of congestion of the road links in the cell _Aij , a weighted average value weighted by the length of the road link, or a maximum value can be used.

In FIG. 5, the degree of congestion (representative value) for each cell _Aij is indicated in three levels by shades of colors (hatching). Dark colored cells A ₃₁ and A ₃₂ indicate relatively high levels of congestion. In other words, the cells A ₃₁ and A ₃₂ are heavily congested or heavily congested, making it extremely difficult to pass. Light colored cells A ₁₃ and A ₂₂ indicate that the degree of congestion is relatively moderate. In other words, cells A ₁₃ and A ₂₂ are moderately congested and the passability is moderate. Cells _A11 , _A12 , _A14 , _A21 , _A23 , _A24 , _A33 , _A34 , _A41 , _A42 , _A43 , and _A44 without coloring have relatively low congestion levels. show. That is, cells _A11 , _A12 , _A14 , _A21 , _A23 , _A24 , _A33 , _A34 , _A41 , _A42 , _A43 , and _A44 are not congested and are easy to pass through. indicates that The degree of congestion for each cell _Aij calculated by the traffic prediction unit 42 may be transmitted to the vehicles V1 to Vn via the center-side communication device 30 as part of the route guidance information.

The traffic prediction unit 42 corrects the intra-cell cost for each cell _Aij stored in the mesh map storage unit 52 based on the calculated degree of congestion (representative value) for each cell _Aij . For example, as shown in FIG. 5, the intra-cell costs of cells A ₃₁ and A ₃₂ with relatively high congestion levels are significantly increased. This makes the mesh nodes N ₃₁ and N ₃₂ shown in FIG. 4 significantly smaller as shown in FIG. In addition, as shown in FIG. 5, the intra-cell costs of the cells A ₁₃ and A ₂₂ with medium congestion levels are increased to medium levels. As a result, the mesh nodes N ₁₃ and N ₂₂ shown in FIG. 4 are moderately small as shown in FIG. Also, as shown _in FIG. ₅ , the cells A11, _A12 , _A14 , A21, A23, A24, A33, A34, _A41 , _A42 , _A43 , _A43 , A43, _A43 , _A43 , _A43 , A ₄₄ does not modify the intra-cell cost, and mesh nodes N ₁₁ , N ₁₂ , N ₁₄ , N ₂₁ , N ₂₃ , N ₂₄ , N ₃₃ , N ₃₄ , N ₄₁ , N ₄₂ , The magnitudes of N ₄₃ and N ₄₄ are maintained as shown in FIG.

The route search unit 43 uses the information on the departure points and destinations of the vehicles V1 to Vn received from the vehicles V1 to Vn via the center-side communication device 30, the mesh map stored in the mesh map storage unit 52, and the like. , a route from the starting point to the destination is searched for each of the vehicles V1 to Vn. A route search unit 43 is a first search unit that searches for a mesh route composed of cells A _ij connecting a cell A _ij to which a starting point belongs to a cell A _ij to which a destination belongs, targeting a plurality of cells A _ij . 44, and a second search unit 45 that searches for a route composed of road links connecting a starting point to a destination, targeting the road links in the searched mesh route.

For example, as shown in FIG. 7A, if a road map contains cells A _ij (i=1 to n; j=1 to m: n, m is a positive integer equal to or greater than 2. In FIGS. 7A to 7D, n=4 , m=8). As indicated by the shades of colors (hatching) in FIG. 7A, the degree of congestion is calculated stepwise (in four steps) for each cell _Aij . Cell A ₂₃ has the highest degree of congestion and is in a state of congestion. Cells A ₁₂ , A ₁₃ , A ₁₄ , A ₁₅ , A ₂₂ , A ₂₄ , A ₂₅ , A ₃₁ , A ₃₂ and A ₃₃ around cell A ₂₃ have the second highest congestion. Cells A ₂₁ , A ₃₄ , A ₃₅ , A ₄₁ , A ₄₄ and A ₄₇ have the third highest degree of congestion. Cells A ₁₁ , A ₁₆ , A ₁₇ , A ₁₈ , A ₂₆ , A ₂₇ , A ₃₆ , A ₃₇ , A ₃₈ , A ₄₂ , A ₄₃ , A ₄₅ , A ₄₆ , and A ₄₈ have the lowest congestion degree, is not occurring. Assume that the traffic volume prediction unit 42 corrects the intra-cell cost of each cell _Aij using this congestion degree.

The first search unit 44 reads out the mesh map stored in the mesh map storage unit 52, and uses a route search algorithm such as the Dijkstra method based on the inter-cell cost and the intra-cell cost of each cell _Aij . As shown in FIG. 7B, cells A ₃₁ , A ₄₁ , A ₄₂ , A ₄₃ , A ₄₄ , A ₄₅ , A ₄₆ , and A connecting cell A ₃₁ to which origin O belongs to cell A ₁₇ to which destination D belongs are connected. ₃₆ , A ₃₇ , A ₂₇ and A ₁₇ are searched for the mesh route R1. Specifically, among arbitrary mesh routes connecting the cell A ₃₁ to which the origin O belongs to the cell A ₁₇ to which the destination D belongs, the mesh route that minimizes the sum of the inter-cell cost and the intra-cell cost is selected. be. That is, the mesh route R1 shown in FIG. 7B includes cells A ₃₁ , A ₄₁ , A ₄₂ , A ₄₃ , A ₄₄ , A ₄₅ , A ₄₆ , A ₃₆ , A ₃₇ , A ₂₇ , A ₁₇ and the inter-cell cost between adjacent cells A ₃₁ and A ₄₁ , between cells A ₄₁ and A ₄₂ , between cells A ₄₂ and A ₄₃ and between cells A ₄₃ and A ₄₄ within mesh route R1. between cells A ₄₄ and A ₄₅ between cells A ₄₅ and A ₄₆ between cells A ₄₆ and A ₃₆ between cells A ₃₆ and A ₃₇ between cells A ₃₇ and A ₂₇ between cells A ₂₇ , A ₁₇ is selected because it has the smallest sum with the respective inter-cell costs.

7A and 7B exemplified the case of searching for the mesh route R1 using the intra-cell cost corrected by adding the degree of congestion. It is also possible to search for the mesh route R1 using the unmodified intra-cell cost before modification.

It should be noted that there may be cases where the mesh route R1 cannot be searched so as to avoid congested areas (for example, when the departure point, congested areas, and destinations are aligned on a single main road) due to factors such as the density of road links. is assumed. With regard to this, even if the intra-cell cost of the cell _Aij at the congested location is greatly corrected according to the degree of congestion, if only the mesh route R1 can be taken, the first search unit Even if there is, search for the mesh route R1. Therefore, the inconvenience of not being able to search for the mesh route R1 does not occur.

The second search unit 45 extracts road links R0 belonging to the mesh route R1 searched by the first search unit 44, as shown in FIG. 7C. As shown in FIG. 7D, the second search unit 45 uses a route search algorithm such as the Dijkstra method for the extracted road links R0, and uses a route search algorithm such as the Dijkstra method to construct the road links R0 connecting the departure point O and the destination D. A route (link route) R2 is searched for. Information on the link route R2 searched by the second search unit 45 is transmitted to the vehicles V1 to Vn as route guidance information.

In the vehicle V1 shown in FIG. 1, the display control unit 23 displays the display screen of the display device 13 as shown in FIG. , a road map segmented by cells _Aij is displayed. In FIG. 8A, for example, the current location O and the road links around the current location O are displayed in the same manner as a normal navigation device. Further, the display control unit 23 causes the display screen of the display device 13 to display the degree of congestion for each cell _Aij by color coding, shading, or the like.

Here, in a normal navigation device, information on traffic congestion/congestion points is displayed by color-coding for each road link. Hard to grasp. On the other hand, according to the embodiment of the present invention, by indicating the degree of congestion in units of cells A _ij by color coding, shading, etc., it becomes easier for passengers to recognize the distribution of congestion in a wide range in units of cells A _ij . , it becomes easier to easily recall the course of the outline.

Furthermore, if the link route R2 in FIG. 7D is found, the display device 13 displays the link route R2 from the current location O to the destination D as a recommended route, as shown in FIG. 8B. As shown in FIG. 8B, by superimposing the congestion degree of each cell A _ij on the display, the passenger can intuitively know that the link route R2 has been searched while avoiding the highly congested cell A _ij . can be understood. Therefore, it is possible to increase the convincingness and acceptability of the recommended route for the passenger. Further, when no traffic jam/congestion occurs, the display device 13 displays the intra-cell cost instead of the congestion degree for each cell _Aij , so that the passenger can see the road distribution for each cell _Aij . It is also possible to intuitively understand the state of

<route guidance method>
Next, an example of a route guidance method according to an embodiment of the present invention will be described with reference to the flowchart of FIG.

In step S<b>10 , the traffic demand prediction unit 41 acquires the current traffic demand in a predetermined area from road traffic information and the like collected by the traffic information collection device 2 . In step S<b>11 , the traffic demand prediction unit 41 predicts future traffic demand in a predetermined area based on road traffic information and the like collected by the traffic information collecting device 2 .

In step S<b>12 , the traffic volume prediction unit 42 , based on the current traffic demand obtained by the traffic demand prediction unit 41 and the future traffic demand predicted by the traffic demand prediction unit 41 , Identify when congestion occurs. In step S13, the traffic volume prediction unit 42 corrects the intra-cell cost of the cell A _ij containing the specified congestion/congestion location among the plurality of cells A _ij of the mesh map stored in the mesh map storage unit 52. do.

The subsequent steps S14 to S16 are performed for all the vehicles V1 to Vn managed by the traffic management center 1 one by one. In step S<b>14 , the route search unit 43 acquires the position information of the departure point and the destination of the vehicle V<b>1 received via the center-side communication device 30 , for example, with the vehicle V<b>1 as the processing object.

In step S15, the route search unit 43 uses the mesh map stored in the mesh map storage unit 52 based on the positional information of the departure point and the destination of the vehicle V1 so as to avoid congestion. Search for a route from your starting point to your destination. Note that the route search is performed in the same way even when there is no traffic jam or congestion in the target area.

In step S<b>16 , route guidance information including information on the route searched by the route search unit 43 is transmitted to the vehicle V<b>1 via the center-side communication device 30 . On the vehicle V1 side, a recommended route or the like is displayed on the road map on the display screen of the display device 13 based on the route guidance information.

In step S17, it is determined whether or not the processes of steps S14 to S16 have been performed for all vehicles V1 to Vn to be managed. If it is determined that all vehicles V1 to Vn have been processed, the process is completed. On the other hand, if it is determined that all the vehicles V1 to Vn have not been processed, the processing of steps S14 to S16 is repeated for the remaining vehicles.

Next, an example of a method of creating a mesh map stored in the mesh map storage unit 52 shown in FIG. 1 will be described with reference to the flowchart of FIG.

In step S20, using the road link map stored in the road link map storage unit 51, the mesh map creation device 34 lays out cells _Aij of a predetermined mesh size on the road link map to create a road link map. Partition into a plurality of cells _Aij .

In step S21, the mesh map creation device 34 assigns an ID (i, j) to each cell _Aij . Here, assuming a cell A _ij of a two-dimensional structure system, a case of assigning a two-dimensional index (i, j) will be exemplified. Since the shape and structure of the cell A _ij are arbitrary, the method of assigning the ID may be suitable for the form of the cell A _ij .

In step S22, the mesh map generator 34 extracts road links belonging to each cell _Aij . In step S23, the mesh map creation device 34 provides each road link with information indicating that the extracted road link belongs to the cell _Aij .

In step S24, the mesh map creation device 34 determines, for the (i, j)th cell among the plurality of cells _Aij , the road standard, the road link length, the road The traffic capacity of each road link in the (i, j)-th cell is calculated with reference to attribute information such as width and number of lanes. Furthermore, the mesh map creation device 34 calculates the total traffic capacity of each road link.

In step S25, the mesh map creation device 34 sets the intra-cell cost of the (i, j)-th cell based on the calculated total traffic capacity of the road links in the (i, j)-th cell. , attached to the mesh nodes. The mesh map creation device 34 sets the intra-cell cost to be smaller as the total value of traffic capacity is larger.

In step S26, the mesh map creation device 34 determines whether or not the processes of steps S25 and S26 have been performed for all cells _Aij . If it is determined that all cells _Aij have not been processed, the processing of steps S25 and S26 is repeated for the remaining cells. On the other hand, if it is determined in step S26 that all cells _Aij have been processed, the process proceeds to step S27.

In step S27, the mesh map creation device 34 generates the (i, j)-th cell and the (i-1, j)-th, (i, j-1)-th, (i, j-1)-th cells adjacent to the (i, j)-th cell. Focusing on four boundaries with four (i, j+1)-th and (i+1, j)-th cells, road links crossing the four boundaries are extracted. The mesh map creation device 34 refers to attribute information such as the road standard, road link length, road width, and number of lanes of the extracted road links to calculate the traffic capacity of each road link. Furthermore, the mesh map creation device 34 calculates the total value of the traffic capacity of road links for each of the four boundaries.

In step S28, the mesh map creation device 34, based on the total value of the traffic capacity for each of the four boundaries, between the (i, j)-th cell and the (i-1, j)-th cell, (i ,j)th cell and (i,j−1)th cell, between (i,j)th cell and (i,j+1)th cell, (i,j)th cell and the (i+1, j)-th cell, respectively, and assign the corresponding mesh link L with the inter-cell cost. The mesh map creation device 34 sets the inter-cell cost to be smaller as the total traffic capacity is larger.

In step S29, the mesh map creation device 34 determines whether or not the processes of steps S27 and S28 have been performed for all cells _Aij . If it is determined that the processing has been performed for all cells _Aij , the processing is completed. On the other hand, if it is determined that the processing has not been performed for all cells _Aij , the processing of steps S27 and S28 is repeated for the remaining cells. As a result, a mesh map including information on intra-cell costs within all cells A _ij and inter-cell costs between all cells A _ij is generated and stored in the mesh map storage unit 52 .

Next, referring to the flowchart of FIG. 11, the process of specifying the congestion/congestion location in step S12 of the flowchart of FIG. 9 and the processing of changing the intra-cell cost of the cell containing the congestion/congestion location in step S13 An example will be explained.

In step S<b>31 , the traffic volume prediction unit 42 calculates the degree of congestion of each road link based on the current and future traffic volume of each road link predicted by the traffic volume prediction unit 42 . As the degree of congestion of each road link, the ratio of the traffic volume to the traffic capacity of the road link may be employed, or the average speed of vehicles traveling on the road link, the number of passing vehicles, or the like may be substituted.

In step S32, the traffic prediction unit 42 calculates a representative value of the degree of congestion for each cell _Aij based on the degree of congestion of road links in the cell _Aij calculated in step S31. As the representative value of the degree of congestion, for example, a simple average value, a weighted average value weighted by road link length, a maximum value, or the like can be used.

In step S33, the traffic volume prediction unit 42 multiplies the intra-cell cost given to the mesh node _Nij in step S25 of FIG. , modifies all intra-cell costs. Assume that the coefficient takes a value of 1 or more. When the degree of congestion is relatively high, the modified intra-cell cost increases from the value before modification by setting the coefficient relatively large. When the degree of congestion is relatively low, a small coefficient is set so that the corrected intra-cell cost is close to the value before correction. If there is no congestion and the degree of congestion is less than the predetermined threshold, the coefficient is set to 1 and the value of the intra-cell cost before correction is maintained.

In step S34, the traffic prediction unit 42 determines whether or not the intra-cell cost is corrected for all cells _Aij . If it is determined that the intra-cell costs have been corrected for all cells _Aij , the process is completed. On the other hand, if it is determined that the intra-cell costs have not been corrected for all cells _Aij , the processing of steps S31 to S33 is repeated for the remaining cells.

Next, an example of the route search process for avoiding traffic jams/congested areas in step S15 of the flowchart of FIG. 9 will be described with reference to the flowchart of FIG.

In step S41, the first search unit 44 refers to the mesh map stored in the mesh map storage unit 52 based on the positional information of the departure point and destination of the vehicle V1, and generates a plurality of meshes as shown in FIG. 7A. Among the cells A _ij , the cell A ₃₁ to which the origin O belongs and the cell A ₁₇ to which the destination D belongs are specified respectively.

In step S42, the first search unit 44 uses a route search algorithm such as the Dijkstra method based on the intra-cell costs and the inter-cell costs of the plurality of cells A _ij to target the plurality of cells A _ij . Search for mesh route R1 as shown in 7B. The mesh route R1 is composed of cells A31, _A41 , _A42 , _A43 , _A44 , _A45 , _A46 , _A36 , A _connecting the cell _A31 to which the origin O belongs to the cell _A17 to which the destination belongs. ₃₇ , A ₂₇ and A ₁₇ .

In step S43, the second search unit 45 extracts road links R0 belonging to each cell _Aij included in the mesh route R1, as shown in FIG. 7C. In step S44, the second search unit 45 uses a route search algorithm such as the Dijkstra method for the road link R0 extracted in step S43 to obtain a route from the departure point O to the destination D, as shown in FIG. 7D. A link route R2 composed of a road link R0 connecting to

The route guidance program according to the embodiment of the present invention can cause a computer such as the route guidance device 31 constituting the route guidance system to execute a series of processes of the route guidance method shown in FIG. A route guidance program according to the embodiment of the present invention can be stored, for example, in the storage device of the route guidance device 31 or the like.

As described above, according to the embodiment of the present invention, when performing a route search from the departure point O to the destination D, based on the passability of each of a plurality of cells A _ij that divide the road map, A mesh route R1 composed of cells connecting the cell to which the origin O belongs to the cell to which the destination D belongs is searched for a plurality of cells _Aij . In other words, if a certain road link is a congested/congested area, there is a high possibility that the surrounding road links are also congested/congested areas. On the other hand, since the road mesh route R1 is searched in units of a plurality of cells A _ij before performing a route search as a target of road links, road links with a high possibility of congestion/congestion are identified in units of a plurality of cells A _ij . can be avoided together.

Then, a route (link route) R2 composed of road links connecting the starting point O to the destination D is searched for the road links in the searched mesh route R1. As a result, it is possible to collectively exclude road links outside the mesh route R1 that are highly likely to be congested or congested, and then perform a route search targeting the road links. Therefore, compared to the case where the route search from the departure point O to the destination D is performed from the beginning by targeting the road links, the calculation load for searching for the road links that are likely to be congested/congested places is reduced. can be reduced, and the speed of route search can be increased. In particular, it is effective when performing route search with a high information load using probe information and big data.

Furthermore, by searching the mesh route R1 based on the inter-cell costs of the plurality of cells A _ij in addition to the _intra -cell costs of the plurality of cells A _ij , the mesh Compared to the case of searching for the route R1, the information used for avoiding traffic jams/congested places is increased, so searching for a route that is easier to avoid traffic jams/congested places in line with the actual traffic jams/congested places. can be done. Furthermore, by correcting the intra-cell costs of a plurality of cells A _ij according to the degree of congestion of the road links in the cells A _ij , it is possible to search for a route taking into consideration the congestion/congestion situation of each cell A _ij . can.

(First modification)
In the embodiment of the present invention, in steps S27 and S28 of FIG. 10, when setting inter-cell costs for a plurality of cells A _ij , the total value of the traffic capacity of road links crossing the boundaries between adjacent cells A _ij is calculated as follows: A case has been exemplified in which the inter-cell cost is set according to the calculated total traffic capacity. On the other hand, in the first modification, when setting the inter-cell cost, in addition to the traffic capacity of the road links that cross the boundary between adjacent cells, the number of road links that cross the boundary between adjacent cells A case of also considering

For example, assuming a cell of 20 km square, if there is one wide road link with a large traffic capacity in the center of the boundary line between adjacent cells, from the end of the boundary line between adjacent cells to this road link Travel up to 10km is required. On the other hand, if two road links with half the traffic capacity exist at a predetermined interval on the boundary line between cells, the distance required to reach these road links is short and it is easy to pass. It is thought that the However, if the number of road links is too large and there are many narrow road links, it is conceivable that the ease of passage will be reduced due to the decrease in vehicle speed and the like. In other words, it is thought that if there are a certain number of road links that straddle the boundary between adjacent cells, the easiness of passage is high, and if there are too few or too many road links, the easiness of passage will be reduced.

Therefore, in the first modification, a factor is set according to the number of road links per boundary distance between adjacent cells, as shown in FIG. 13A, so as to reflect this situation in the inter-cell cost. do. This coefficient is set to a high value (i.e., a high passage cost) regardless of whether the number of road links per cell boundary distance is large or small. shows that it is easy. In a first variant, the inter-cell cost is modified by multiplying the total traffic capacity of the road links by the factor shown in FIG. 13A. That is, the cell-to-cell cost C1 can be obtained by the formula ( ₁ ), where the cell _- to _- cell cost is _C1 , the coefficient shown in FIG. 13A is f1, and the traffic capacity of the road link across the adjacent cells is CL. .
C ₁ =f ₁ ×ΣC _L (1)

According to the first modified example, by evaluating the inter-cell cost based on the traffic capacity of the road link that straddles between cells and the number density of the road link, more realistic route guidance becomes possible.

(Second modification)
In the embodiment of the present invention, in steps S24 and S25 of FIG. 10, when setting the intra-cell cost of the cell _Aij , the total value of the traffic capacity of the road links belonging to the cell _Aij is calculated, and the calculated traffic capacity The case where the intra-cell cost is set according to the total value of is exemplified. On the other hand, in the second modified example, when setting the intra-cell cost, in addition to the traffic capacity of the road links belonging to the cell, the number of road links belonging to the cell itself is also considered.

For example, assuming a cell of 20 km square, if two road links with large traffic capacity cross each other in the center of the cell, the distance from the center position of each side of the cell to this road link A maximum of 10 km travel is required, but if there are four road links with half the traffic capacity intersecting at a predetermined interval in a U-shape, it is difficult to reach these road links. It is conceivable that the distance required for That is, it is considered that it is easier to pass through a cell if there are a certain number of road links in the cell. However, in a situation where narrow road links are stretched, it is conceivable that the speed will not increase due to intersections and the like, and the ease of passage will decrease. Therefore, it is considered that the road links in the cell are easy to pass when there is a certain area density, but it becomes difficult to pass when the road link density is too low or too high.

Therefore, in the second modification, a coefficient is set according to the road link density (the number of road links per area) in the cell, as shown in FIG. 13B, so that this situation is reflected in the intra-cell cost. This coefficient is set to a high value (passage cost increases) regardless of whether the road link density is high or low, and indicates that an appropriate road link density between them is easy to pass.

In the second modification, the intra-cell cost is corrected by multiplying the total traffic capacity of the road link by the coefficient shown in FIG. 13B. That is, the intra-cell cost C ₂ can be obtained by Equation (2), where C ₂ is the intra-cell cost, f ₂ is the coefficient shown in FIG. 13B, and C _L is the traffic capacity of the road link in the cell.
C ₂ =f ₂ ×ΣC _L (2)

According to the second modification, by evaluating the intra-cell cost based on the traffic capacity and road link density of the road links within the cell, more realistic route guidance becomes possible.

(Third modification)
In the embodiment of the present invention, when correcting the _intra -cell cost in steps S31 to S33 of FIG. A case of correcting the cost is exemplified. On the other hand, in the third modified example, a case is illustrated in which the spatial bias of congested links within a cell is considered when correcting the intra-cell cost.

If the congestion has a large spatial bias, it is conceivable that the congestion is concentrated in a location, and other locations in the cell are less crowded and easier to pass through. On the other hand, when there is little spatial bias in congestion, it is conceivable that the congestion spreads throughout the cell and the ease of passage is low throughout the cell.

Therefore, in order to evaluate the spatial bias of congestion, as shown in FIG. 13C, when the bias is relatively small, the intra-cell cost is relatively increased, Set the congestion bias factor so that

In the third modification, the intra-cell cost is corrected by multiplying the non-congested intra-cell cost by the congestion degree coefficient and the congestion bias coefficient shown in FIG. 13C. That is, assuming that the intra _- cell cost is C ₃ , the non-congested intra-cell cost is C _{0 ,} the coefficient of congestion is f ₃ , and the congestion bias coefficient shown in FIG. (3).
C3= _C0 *f3* _{f4 ( 3} )

According to the third modification, by evaluating the congestion status of road links within a cell based on the degree of congestion within the cell as well as the spatial bias of the congestion, congestion and congestion can be avoided and reduced more effectively. Such route guidance becomes possible.

(Fourth modification)
In the embodiment of the present invention, the case where one mesh map is used is exemplified. Exploration takes time. In addition, when the distance from the starting point to the destination is as short as the mesh size, when both the starting point and the destination belong to one cell, or when the starting point and the destination are in adjacent cells It is assumed that the mesh route search does not function properly.

For example, FIGS. 14A and 14B show two mesh maps with different mesh sizes. The size of cell A1 in the mesh map shown in FIG. 14A is four times the size of cell A2 in the mesh map shown in FIG. 14B. As shown in FIG. 14A, when the starting point O and the destination D are located in the lower left and upper right corners of the mesh map, respectively, they are covered by 4×4 cells A1. On the other hand, if the starting point O and the destination D shown in FIG. 14A are at the same position and the cell A2 shown in FIG. is increased by a factor of 16 compared to the case of cell A1 shown in FIG. 14A, and the calculation time is increased accordingly.

Also, when the distance from the departure point O to the destination D is short as shown in FIG. 14B, applying the mesh map with the relatively large mesh size shown in FIG. Since the land O and the destination D are located respectively, it is impossible to search for an appropriate mesh route R1. Therefore, in the fourth modification, a plurality of mesh maps having different mesh sizes are stored in the mesh map storage unit 52 and selectively used according to the distance from the departure point O to the destination D. FIG.

The route search unit 43 selects the mesh size of the map to be applied according to the distance from the departure point to the destination of the vehicle to be route searched. The mesh size should be a size that divides the distance from the departure point to the destination by several (for example, 4×4 division as shown in FIG. 14A), depending on the intra-cell cost and inter-cell cost settings. It is one measure to be able to explore several mesh routes accordingly. Therefore, it is considered appropriate to apply a mesh map having a mesh size conforming to a size that divides the distance from the departure point to the destination by several. However, it is conceivable that there is a limit to the mesh size to be prepared. Therefore, it is preferable to selectively use a mesh map having a size close to dividing the distance from the departure point to the destination by several from among the mesh maps of prepared mesh sizes.

In addition, when the distance from the departure point to the destination is relatively large, if a mesh map with cells with relatively coarse meshes is applied among multiple mesh maps, a route that is far away from the congested area when congestion occurs. likely to explore. In that case, the overall effect of reducing or avoiding congestion/congestion will be greater.

According to the fourth modification, a plurality of mesh maps having mesh sizes different from each other are prepared, and the plurality of mesh maps are selectively used according to the distance from the departure point to the destination. Appropriately sized cells can be used. Furthermore, the closer the distance from the departure point to the destination is, the smaller the size of the plurality of cells is set, so that when the distance from the departure point to the destination is relatively short, the degree of freedom in route search is ensured. be able to. On the other hand, when the distance from the departure point to the destination is relatively long, it is possible to suppress an increase in calculation load due to an excessive number of cells to be searched.

(Fifth Modification)
In the embodiment of the present invention, as shown in FIG. 2, the road link map is divided into square cells _Aij of the same size. However, since the density of road links differs depending on the area, if only cells A _ij of the same size are used throughout the area, it is conceivable that many cells A _ij that do not include road links will be generated. Therefore, in the fifth modification, cells of different sizes are set in one mesh map in order to reduce the number of cells that do not include road links.

For example, as shown in FIG. 15, a mesh map having three sizes of cells A1 to A3 is used. In FIG. 15, the size of cell A1 is the largest, cell A2 is 1/4 the size of cell A1, and cell A3 is 1/4 the size of cell A2. The cells A1 to A3 are arranged according to the density of the number of road links forming the road map. That is, a relatively large-sized cell A1 is set in an area where the number density of road links is relatively low. A cell A2 with a relatively medium size is set in a region where the number density of road links is relatively medium. A relatively small-sized cell A3 is set in an area where the number density of road links is relatively high.

According to the fifth modified example, cells A1 to A3 of different sizes are set in one mesh map, and the cells corresponding to areas with a relatively high density of road links on the road map have road links. The cells A1-A3 are made different in size so that they are smaller than the cells corresponding to the relatively low density areas. As a result, especially in areas with a large density distribution of road links, areas with relatively low density of road links can be searched while securing the degree of freedom of mesh route search in areas with relatively high density of road links. It is possible to reduce the calculation load for searching for objects, and to speed up the route search. In the fifth modification, since the cells A1 to A3 have a non-structural structure, the descriptions of the IDs and connection relationships of the cells A1 to A3 are different from those in the embodiment of the present invention. A management method suitable for the structure should be applied.

Also, in the fifth modification, the cells A1 to A3 are square, but the shape of the cells A1 to A3 is not particularly limited. For example, it may be a rectangle formed by connecting a plurality of square cells A1 to A3. Furthermore, the shape of the cells A1 to A3 is not limited to rectangular, but may be triangular, rectangular, or hexagonal. Furthermore, it may be an irregular shaped cell along the boundary of a municipality, for example. In that case, it is also possible to use existing regional division data such as boundaries of municipalities.

(Sixth modification)
In the embodiment of the present invention, the mesh route R1 is searched only once, after which the road links belonging to the cell _Aij in the mesh route R1 are extracted, and from the extracted road links, the link route connecting the departure point and the destination is extracted. The case of searching for R2 is exemplified. On the other hand, in the sixth modification, a plurality of mesh maps of different sizes are stored in the mesh map storage unit 52, and a plurality of mesh maps are sequentially used to search for a mesh route in multiple stages. Illustrate.

The first search unit 44 divides a plurality of mesh maps stored in the mesh map storage unit 52 into a plurality of cells (primary cells) A1 having a relatively large mesh size, as shown in FIG. 16A. extract the mesh map. As shown in FIG. 16B, the first search unit 44 searches for a mesh route (primary mesh route) R11 composed of cells A1 connecting the cell A1 to which the departure point O belongs to the cell A1 to which the destination D belongs. do.

Furthermore, the first search unit 44 extracts a mesh map divided by a plurality of cells (secondary cells) A2 having a relatively small mesh size from among the plurality of mesh maps stored in the mesh map storage unit 52. do. Then, the first searching unit 44 extracts the cell A2 of the position coordinates corresponding to the mesh route R11, as shown in FIG. 16C, from among the plurality of extracted cells A2 of the mesh map. Furthermore, based on the extracted inter-cell cost and intra-cell cost of the cell A2, the first search unit 44 searches from the cell A2 including the departure point O to the cell A2 including the destination D as shown in FIG. 16D. A mesh route (secondary mesh route) R12 composed of the connecting cell A2 is searched.

The second search unit 45 extracts road links within the mesh route R12 searched by the first search unit 44 . The second search unit 45 searches for a link route composed of road links connecting the starting point O to the destination D, targeting the extracted road links.

According to the sixth modification, after searching for the mesh route R11 composed of cells A1, the mesh route R11 is divided based on the easiness of passage for each of a plurality of cells A2 that are finer than the cell A1. Search for a mesh route R12 composed of In this manner, with respect to the same departure point O and destination D, the mesh routes R11 and R12 are searched in multiple stages while the sizes of the cells A1 and A2 are reduced, thereby reducing congestion and congestion. Road links with a high probability can be excluded step by step in units of cells A1 and A2. Therefore, compared to searching the mesh route only once, it is possible to exclude more road links that are likely to be congested or congested before starting the search for road links. , the time required for route search can be further reduced. In the sixth modification, the mesh routes R11 and R12 are searched in two steps, but mesh routes are searched in three or more steps using mesh maps of different mesh sizes. You may

(Other embodiments)
As described above, the present invention has been described by the embodiments and the first to sixth modifications, but the statements and drawings forming part of this disclosure should not be understood to limit the present invention. Various alternative embodiments, implementations and operational techniques will become apparent to those skilled in the art from this disclosure. Of course, the present invention includes various embodiments and the like that are not described here. Therefore, the technical scope of the present invention is defined only by the matters specifying the invention according to the valid scope of claims based on the above description.

1...Traffic control center 2...Traffic information collection device 10...Vehicle side communication device 11...In-vehicle device 12...Map information storage device 13...Display device 21...Destination setting Unit 22...Vehicle information acquisition unit 23...Display control unit 30...Center side communication device 31...Route guidance device 32...Map information storage device 33...Mesh map creation device 41. Traffic demand prediction unit 42...Traffic volume prediction unit 43...Route search unit 44...First search unit 45...Second search unit 51...Road link map storage unit 52. .Mesh map storage V1 to Vn...All vehicles

Claims (5)

A route guidance method for guiding a route from a starting point to a destination on a road map,
A route guidance device selects the plurality of cells from the cell to which the departure point belongs to the destination based on ease of passage depending on the traffic capacity in the plurality of cells obtained by dividing the road map into a mesh. a step of searching for a mesh route composed of the cells connecting to the cell to which the
a step in which the route guidance device searches for a route composed of the road links connecting the departure point to the destination, targeting the road links in the searched mesh route;
The route guidance method, wherein the step of searching for the mesh route sets the size of the plurality of cells to be smaller as the distance from the departure point to the destination is shorter. 2. The route guidance method according to claim 1, wherein the step of searching for the mesh route sets the sizes of all of the plurality of cells to be smaller as the distance from the departure point to the destination is shorter. A route guidance method for guiding a route from a starting point to a destination on a road map,
A route guidance device selects the plurality of cells from the cell to which the departure point belongs to the destination based on ease of passage depending on the traffic capacity in the plurality of cells obtained by dividing the road map into a mesh. a step of searching for a mesh route composed of the cells connecting to the cell to which the
a step in which the route guidance device searches for a route composed of the road links connecting the departure point to the destination, targeting the road links in the searched mesh route;
In the step of searching for the mesh route, after searching for the mesh route as a primary mesh route, the primary mesh route is divided into meshes that are finer than the cells, and the easiness of passage is determined for each of a plurality of secondary cells. Based on the above, a secondary mesh route composed of the secondary cells connecting the secondary cell to which the departure point belongs to the secondary cell to which the destination belongs, targeting the plurality of secondary cells , An intra-cell cost that quantifies the degree of ease of passage depending on the traffic capacity in the secondary cell is set for each of the secondary cells, and the intra-cell cost of each of the secondary cells that constitute the secondary mesh route is set. A route guidance method characterized by searching based on a total cost . A route guidance system for guiding a route from a starting point to a destination on a road map,
a memory for storing a mesh map composed of a plurality of cells obtained by dividing the road map into a mesh;
reading out the mesh map from the memory, and connecting the cell to which the departure point belongs to the cell to which the destination belongs, targeting the plurality of cells based on the easiness of passage in the plurality of cells; a microcomputer that searches for a mesh route made up of cells, and searches for a route made up of the road links connecting the departure point to the destination, targeting the road links in the searched mesh route. prepared,
A route guidance system, wherein when searching for the mesh route, the smaller the size of the plurality of cells is set, the closer the distance from the departure point to the destination is. A route guidance system for guiding a route from a starting point to a destination on a road map,
a memory for storing a mesh map composed of a plurality of cells obtained by dividing the road map into a mesh;
reading out the mesh map from the memory, and connecting the cell to which the departure point belongs to the cell to which the destination belongs, targeting the plurality of cells based on the easiness of passage in the plurality of cells; a microcomputer that searches for a mesh route made up of cells, and searches for a route made up of the road links connecting the departure point to the destination, targeting the road links in the searched mesh route. prepared,
After searching for the mesh route as a primary mesh route, the plurality of secondary cells are determined based on the ease of passage for each of a plurality of secondary cells obtained by dividing the primary mesh route into a finer mesh than the cells. , the secondary mesh route composed of the secondary cells connecting the secondary cell to which the departure point belongs to the secondary cell to which the destination belongs depends on the traffic capacity in the secondary cell setting an intra-cell cost that quantifies the degree of ease of passage to each of the secondary cells, and searching based on the total intra-cell cost of each of the secondary cells that constitute the secondary mesh route. A route guidance system characterized by:

Images