JP2014059221A - Route notification device and navigation device - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a route notification device which is improved in convenience and a navigation device.SOLUTION: In route notification processing, a plurality of routes from a departure place to a destination are generated on the basis of map data, the departure place of a self-vehicle, and the destination (S160). As for each of the plurality of routes, multiplicity α indicating the degree of coincidence with a representative route is derived (S190). When the multiplicity α is less than a regulated ratio Th (S200: NO), the pertinent route is defined as a residual route. Thus, when there exists any residual route (S240: YES), a new representative route is set from among the residual routes, and as for each of the residual routes, the multiplicity α is repeatedly derived, and a group is determined as for each residual route. When there does not exist any residual route (S240: NO), the representative route in each group is notified as a specific route (S250).

Description

  The present invention relates to a route notification device that notifies a route from a departure place to a destination, and a navigation device that includes the route notification device.

  2. Description of the Related Art Conventionally, a navigation device that searches for a route from a departure point to a set destination based on map data and performs route guidance to the destination according to a route detected as a result of the search is known. (For example, refer to Patent Document 1).

  In this type of navigation apparatus, it is common to search for a route from a departure place to a destination using the Dijkstra method. This route search by the Dijkstra method is based on a combination of links connecting nodes (that is, a node having the shortest travel distance and travel time) so that the travel distance and travel time from the starting point to the destination are minimized. And the link connection order), and one route is detected in one search.

JP 2002-202137 A

By the way, depending on the user of the navigation apparatus, there is a case where it is desired to select an optimum route according to the purpose of movement of the user from a plurality of routes.
However, in the conventional navigation device, when a plurality of routes are to be detected, it is necessary to execute a route search a plurality of times while changing the search conditions. In addition, a plurality of routes detected as a result of searching by changing the search condition in this way may have a small difference in each route.

  For this reason, even if the navigation device is configured to present each route detected by a plurality of route searches and execute route guidance according to the route selected by the user, the navigation device presents it. There is a possibility that the route desired by the user of the navigation device does not exist among the plurality of routes.

  For example, if a plurality of routes presented by the navigation device are clearly different from each other (for example, a plurality of waypoints (ie, nodes) are clearly different), the user can respond to his / her purpose. Easy to select the best route. However, the plurality of routes detected by the conventional navigation device are routes that differ only in a very small part of the whole from the starting point to the destination, that is, out of all waypoints (nodes) in each route. It is likely that most transit points are the same. Therefore, among the plurality of routes detected by the navigation device, there is a problem that it is difficult to select an optimum route according to the user's own purpose and the usability of the navigation device is poor.

  That is, in the conventional navigation device, there is a possibility that even if a plurality of routes are searched, a route with little difference may be presented, and there is a problem that convenience for the user of the navigation device is low.

  Therefore, an object of the present invention is to provide a route notification device and a navigation device that can improve convenience over conventional navigation devices.

  In the route notification device of the present invention made to achieve the above object, the map data acquisition means acquires map data, the departure place acquisition means acquires the departure place, and the destination acquisition means includes the destination. To get.

  Further, based on the map data acquired by the map data acquisition means, the route detection means detects a plurality of routes from the departure place acquired by the departure place acquisition means to the destination acquired by the destination acquisition means. Then, the specific route detecting means is a route that is a plurality of representative routes among the plurality of routes detected by the route detecting means, and each difference is equal to or higher than a specified ratio that is a predetermined ratio. When each is detected as a specific route, the route notification means notifies the detected specific route.

  Each of the plurality of specific routes detected by such a route notification device has a difference greater than or equal to a specified ratio. If you specify the waypoints and roads on each route as a target to determine whether this difference is more than the specified percentage, routes that differ greatly from the starting point to the destination Can be detected as

Therefore, according to the route notification device of the present invention, a route with a large difference can be notified, and the route notification device can be convenient for the user.
In other words, it is possible to provide a route notification device that is more convenient than conventional techniques.

  Further, the specific route detection means in the route notification device of the present invention uses one route as a representative route among a plurality of routes, and the duplication degree derivation means determines a representative route for each of the routes detected by the route detection means. Deriving the degree of overlap representing the degree of coincidence, each route having a degree of overlap less than the specified percentage is set as the remaining route, and the derivation repeating unit newly sets a representative route from the remaining routes, For each, the degree of overlap may be derived repeatedly (claim 2).

In this case, it is preferable that the specific route detecting means in the present invention detects each representative route set by the redundancy degree deriving means and the derivation repeating means as the specific route.
In other words, according to the route notification device of the present invention, each route in which the degree of coincidence (redundancy) is reliably less than the specified ratio can be detected as the specific route.

  Further, in the route notification device of the present invention, the map data may include at least a node representing a specific point on the road, a link connecting each node, and a unit cost assigned to each link.

  When using such map data, the route detection means in the present invention, the first cost calculation means performs a cost calculation for each link group that is each combination of links from the departure point to each node, For each link aggregate, a link group that minimizes the cost calculation result is stored in the storage unit for each node, and the second cost calculation means is a combination of links from the destination to each node. In addition, the cost calculation is executed, and at least the link aggregate that minimizes the result of the cost calculation is stored in the storage unit for each node.

  In addition, the route detection means in the present invention, based on the link group stored in the storage unit and the link aggregate, each link combination represented by the link group and the link aggregate for the same node, You may detect as each route from the departure place to the destination.

  That is, in the route notification device of the present invention, when the optimum route from the departure point to the destination and the optimum route from the destination to the departure point are derived, the optimum route to each node (that is, the link group, And link aggregates) are stored in the storage unit. Then, the route from the departure point to the destination is stored by connecting the optimum route from the departure point to each node and the optimum route from the destination to each node stored in the storage unit for each corresponding node. Generate multiple.

By generating routes by such a method, a plurality of routes that can be assumed as routes from the departure point to the destination can be reliably detected.
In particular, by generating a plurality of routes by such a method, a plurality of routes can be detected with a small amount of processing compared to a case where the Dijkstra method is executed a plurality of times (for example, three times) or more. That is, according to the route notification device of the present invention, the time required to detect a plurality of routes can be shortened.

  However, the link group and link aggregate mentioned here are the start point and end point of each link constituting the link combination in addition to the combination of links connected from the starting point or destination to each node. Each node may be included. Further, the cost calculation referred to here is an operation in which the calculation result is smaller as the route is more optimal. As the cost calculation, for each combination of links connecting the nodes up to the target node, a sum may be derived for one type of unit cost, or weighted addition for at least two types of unit costs. It may be derived by doing, or may be derived by weighted averaging.

  In the route notification device of the present invention, the unit cost includes the length of the road represented as each link, the length of time required to move from one end of the road to the other end, the degree of congestion on the road, the road It may be at least one of the amount of money required when moving and the amount of energy consumed when moving the road from one end to the other end (Claim 4).

  By specifying the unit cost in the route notification device of the present invention as described above, a specific route can be detected from various viewpoints according to the needs of the user. As a result, the route notification device of the present invention can be more convenient for the user.

  By the way, the present invention provides one specific route among a plurality of specific routes notified by the route notification device according to any one of claims 1 to 4 and the route notification means of the route notification device. It may be made as a navigation device provided with route guidance means for executing route guidance.

  According to such a navigation device, route guidance can be executed for one specific route. The route guidance mentioned here is to display the specific route for one of the specific routes or to output the specific route by voice.

  The specific route to be route guidance is preferably one specific route designated by the user of the navigation device among a plurality of specific routes.

1 is a block diagram showing a schematic configuration of a navigation device to which the present invention is applied. It is a flowchart which shows the process sequence of a route alerting | reporting process. It is a flowchart which shows the process sequence of 1st cost calculation. It is explanatory drawing for demonstrating the processing content of a 1st cost calculation. It is explanatory drawing for demonstrating the processing content of a 2nd cost calculation. It is a flowchart which shows the process sequence of route production | generation. It is explanatory drawing for demonstrating the processing content of a route production | generation. It is explanatory drawing for demonstrating the processing content of a route alerting | reporting process. It is explanatory drawing for demonstrating the processing content of a route alerting | reporting process. It is explanatory drawing for demonstrating the processing content of a route alerting | reporting process.

Embodiments of the present invention will be described below with reference to the drawings.
<About the navigation device>
FIG. 1 is a block diagram showing a schematic configuration of a navigation apparatus to which the present invention is applied.

The navigation device 10 is mounted on a car and used to guide a route from a departure point to a destination to passengers of the host vehicle.
The navigation device 10 includes a position detection device 21, an information communication device 22, a display device 23, a voice output device 24, an input reception device 25, a storage device 26, a navigation electronic control device (hereinafter referred to as a navigation ECU). 40).

  Among these, the position detection device 21 detects the current position of the host vehicle and the direction of the traveling direction, and includes at least a known GPS receiver 31, gyro sensor 32, and geomagnetic sensor 33. The information communication device 22 is a device (for example, a VICS (registered trademark) receiver, a wireless telephone device, or the like) that transmits and receives information via dedicated wireless communication or a public communication network. It receives traffic information including at least the start position and end position of traffic jams, traffic regulation information related to traffic regulation for roads, and the like.

  Further, the display device 23 is a device (for example, a liquid crystal display) that displays an image in accordance with a control signal from the navigation ECU 40. The voice output device 24 is a device (so-called speaker) that converts a control signal from the navigation ECU 40 into voice and outputs the voice. The input reception device 25 is a device (for example, a touch panel integrated with the display device 23, a key provided around the display device 23, a microphone, or the like) that receives various instructions from the occupant.

  The storage device 26 is configured as a rewritable nonvolatile storage device (for example, a hard disk drive or a flash memory). The storage device 26 stores map data MD in advance.

  Among these, the map data MD includes node data relating to nodes representing specific points on the road (for example, intersections and branching points), link data relating to links representing roads connecting the nodes, and links to each link. Various data such as cost data relating to unit costs allocated in advance, road data, terrain data, mark data, intersection data, facility data, guidance voice data, voice recognition data, and the like are included.

  Node data includes node IDs, which are identification numbers assigned to each node, the coordinates of each node, the link IDs of all links connected to the node, and node characteristics such as node types (types such as intersections and junctions). It is data including at least information. The link data includes a link ID that is an identification number assigned to each link, a node ID of each node to which the start and end of each link are connected, a link length that represents a distance from the start to the end of the road corresponding to each link, Includes at least information such as the road type (for example, expressway, toll road, general road) corresponding to each link, road width, number of lanes, legal speed limit, road gradient, etc. corresponding to each link It is data.

  Note that the cost data includes the link length, the road type, the time length required to move from the start point to the end point of each link, the amount of money required to move each link, and the like as unit costs. Further, the link length and the road type in the cost data may be shared with the link data.

  Furthermore, the cost data of the present embodiment includes the distance that can be traveled by the fuel per unit capacity determined in advance for each vehicle type in which the navigation device 10 is mounted (or the consumption required to travel the unit distance). The amount of fuel) may be included as a unit cost.

  The navigation ECU 40 performs processing according to the ROM 41 that stores data and programs that need to retain the stored contents even when the power is turned off, the RAM 42 that temporarily stores the data, and the programs stored in the ROM 41 or the RAM 42. A known microcomputer including at least a CPU 43 to be executed is mainly configured.

In such a navigation ECU 40, the current position of the host vehicle and the direction of the traveling direction are derived by a known method based on an output signal from the position detection device 21. Further, the navigation ECU 40 detects a plurality of routes from the departure point to the destination based on the map data stored in the storage device 26, and follows the route selected from the plurality of routes to the destination. A route notification process for performing route guidance is executed.
<About route notification processing>
Next, route notification processing executed by the navigation ECU 40 will be described.

FIG. 2 is a flowchart showing a processing procedure of route notification processing.
This route notification process is started when electric power is supplied to the navigation ECU 40 (in this embodiment, when the ignition switch is turned on).

  When the route notification process is started, first, based on the output signal from the position detection device 21, the current position and traveling direction of the own vehicle are derived, and the derived current position of the own vehicle is determined as the own vehicle. (S110). Then, based on the information input via the input reception apparatus 25, the destination of the own vehicle is set and the set destination is acquired (S120).

  Furthermore, based on the map data MD stored in the storage device 26, the map data MD in a range including at least the range from the departure point of the host vehicle to the destination of the host vehicle is acquired (S130).

Subsequently, for each node, a cost calculation is executed for each route (route) from the departure place, and a link combination (hereinafter referred to as a link group) that minimizes the cost calculation result is stored for each node. Cost calculation is executed (S140).
<About the first and second cost calculation>
Here, FIG. 3 is a flowchart showing a processing procedure of the first cost calculation.

  As shown in FIG. 3, in the first cost calculation, first, the result of the cost calculation for each node is initialized (in this embodiment, the result (value) of the cost calculation is infinite) (S410). Subsequently, the cost calculation is performed on each node adjacent to the node that is the starting point of the cost calculation (hereinafter referred to as the calculation starting node, here the node corresponding to the departure point) via one link (S420). .

  In the cost calculation, the result (value) of the cost calculation is as the optimal route (for example, the distance is the shortest in terms of travel distance and the travel time is short in terms of travel time). Is calculated to be smaller. In the specific cost calculation in the present embodiment, a sum is derived for one type of unit cost for each combination of links connecting the nodes up to each node. However, the cost calculation is not limited to derivation of the sum for one type of unit cost, but may be weighted addition or weighted average for at least two types of unit costs.

  The unit cost used in this cost calculation is the length of the road represented as each link, the length of time required to move from one end of the road to the other end, the degree of congestion on the road, and the road And at least one of the amount of energy required for moving the road from one end to the other end. Of these, the amount of energy consumed when moving from one end to the other on the road includes the distance that can be traveled by fuel per unit capacity or the amount of fuel that is required to travel a unit distance. It is a waste. In addition, among the plurality of types of unit costs, the degree of congestion on the road represented as each link is determined by a well-known method based on the congestion information acquired through the information communication device 22.

  Subsequently, the result of the cost calculation for each node in S420 is associated with the corresponding link and stored in the RAM 42, and the calculation start node is changed to a calculated node (S430).

  Then, among all the nodes, a node having the minimum cost calculation result for each node (hereinafter, “cost minimum node”) is set as a new calculation start node (S440). It is determined whether or not the new calculation start node is a node corresponding to the end point (here, the destination) (S450). If the calculation start node is a node corresponding to the end point as a result of the determination (S450). : YES), the first cost calculation is terminated.

  On the other hand, as a result of the determination in S450, if the calculation start node is not a node corresponding to the end point (S450: NO), cost calculation is performed on all nodes adjacent to the calculation start node via one link. (S460). Specifically, in S460 of the present embodiment, for each node to which individual links extending from the calculation start node are connected, the result of cost calculation for the calculation start node (in this embodiment, the sum of unit costs) By adding the unit costs assigned to the links to which the respective nodes are connected as terminations, the result of the cost calculation for each node is derived.

  Subsequently, for each node, among the cost calculation results derived to date, the cost calculation result having the minimum value and the link combination corresponding to the cost calculation result having the minimum value (i.e., At least one of the link connection order through which the node is reached and the node connection order is stored in the RAM 42 as a link group (S470).

  Then, the calculation start node is set (changed) to the calculated node (S480), and the process returns to S440. In S440, the minimum cost node is set as a new calculation start node among the nodes that have not been changed to the calculated nodes. Thereafter, the steps from S450 to S480 are repeated.

Here, FIG. 4 is an explanatory diagram illustrating the processing content of the first cost calculation.
Here, as shown in FIG. 4A, the node corresponding to the destination (S: in the figure: hereinafter referred to as the departure node) to the node corresponding to the destination (in the figure: G, hereinafter referred to as the destination). A situation is assumed in which there are a plurality of nodes (hereinafter referred to as “routed nodes”) (hereinafter, referred to as “routed nodes”) that can be route points (passing points) between the nodes (hereinafter referred to as “route nodes”). In FIG. 4, a line connecting the nodes represents a link, and a numerical value described with respect to the line represents a unit cost (here, distance). In addition, numerical values and symbols (that is, numerical values and symbols with an underline) written for the node represent the result of the cost calculation.

  When the first cost calculation is executed under such an assumption, first, in S410, as shown in FIG. 4B, the result of the cost calculation for the destination node G and the transit nodes 1 to 4 is initialized. (In this embodiment, it is infinite).

  In S420, as shown in FIG. 4C, the departure node S is set as the calculation start node (in FIG. 4, a colored node represents the calculation start node). The cost calculation is performed on each node connected via one link (in FIG. 4, via node 1, via node 2, and via node 3). As a result, the result of the cost calculation for the relay node 1 is “7”, the result of the cost calculation for the relay node 2 is “9”, and the result of the cost calculation for the relay node 3 is “14”.

  Further, after changing the departure node S to a calculated node (in FIG. 4, the shaded nodes represent calculated nodes), as shown in FIG. Among each node, the transit node 1 having the smallest cost calculation result is set as a new calculation start node. In S460, a cost calculation is executed for each node (via node 2 and via node 4 in FIG. 4) connected to the via node 1 via one link. As a result, the result of the cost calculation for the relay node 2 is “17”, and the result of the cost calculation for the relay node 4 is “22”.

  At this time, the result (“9”) of the cost calculation executed using the previous departure node S as the calculation start node is smaller than the result (“17”) of the cost calculation for the transit node 2. Therefore, in S470, the link group corresponding to the cost calculation result (“9”) executed using the previous departure node S as the calculation start node (ie, the cost calculation result having the minimum value, and the link calculation result) Save the combination.

  Subsequently, in S480, the transit node 1 is changed to a calculated node. Then, in S440, as shown in FIG. 4E, the transit node 2 having the smallest cost calculation result among the nodes is set as a new calculation start node. In S460, a cost calculation is performed for each node (via node 3 and via node 4 in FIG. 4) connected to via node 2 via one link. As a result, the result of the cost calculation for the relay node 3 is “11”, and the result of the cost calculation for the relay node 4 is “21”. Since the cost calculation results for these nodes have the smallest value among the cost calculation results for the node, a link group corresponding to the cost calculation results is stored in S470.

  Further, in S480, the transit node 2 is changed to a calculated node. Then, in S440, as shown in FIG. 4F, the node 3 having the smallest cost calculation result among the nodes is set as a new calculation start node. In S460, a cost calculation is performed on a node (the destination node G in FIG. 4) connected to the transit node 3 via one link. As a result, the result of the cost calculation for the destination node G is “20”. Since the cost calculation result for the destination node G has the smallest value among the cost calculation results for the node, a link group corresponding to the cost calculation result is stored in S470.

  In step S480, the relay node 3 is changed to a calculated node. Thereafter, in S440, the node having the smallest cost calculation result among the nodes is the destination node G. For this reason, the first cost calculation ends.

  Thus, when the first cost calculation is finished, for each node, the result of the cost calculation that minimizes the value and the link combination that minimizes the result of the cost calculation (that is, the route to reach the node) At least one of the link connection order and the node connection order is stored in the RAM 42.

  Here, returning to the description of the route notification processing, for each node, the cost calculation is calculated for each route (route) from the destination, and the link combination that minimizes the result of the cost calculation is stored for each node. The second cost calculation is executed (S150).

  This second cost calculation differs from the previous first cost calculation in the starting point for starting the calculation and the ending point for ending the calculation. Specifically, in the second cost calculation, the starting point at which the calculation is started is the destination of the own vehicle, and the end point at which the calculation is ended is the departure point of the own vehicle.

  Therefore, for the second cost calculation, the starting point for starting the calculation described in the explanation for the first cost calculation (that is, the description for FIG. 3) is the destination of the own vehicle, the end point for ending the calculation is Detailed description will be omitted as it is read as the departure place. Furthermore, in the second cost calculation, the link group in the first cost calculation is referred to as a link aggregate.

FIG. 5 is an explanatory diagram illustrating the processing contents of the second cost calculation.
Here, as shown in FIG. 5A, a situation is assumed in which there are via-nodes 1 to 4 between the departure node S and the destination node G, as in FIG. 4. In FIG. 5, as in FIG. 4, a line connecting nodes represents a link, and a numerical value described with respect to the line represents a unit cost (here, distance). In addition, numerical values and symbols (that is, numerical values and symbols with an underline) written for the node represent the result of the cost calculation. Further, in FIG. 5, the colored nodes represent calculation start nodes, and the shaded nodes represent calculated nodes.

  Under this assumption, when the second cost calculation is executed, first, as shown in FIG. 5B, the result of the cost calculation for the departure node S and the transit nodes 1 to 4 is initialized (this book). In the embodiment, it is infinite).

  Then, as shown in FIG. 5C, each node connected to the destination node G through one link with the destination node G as the computation origin node (in FIG. 5, via nodes 3 and 3). Perform cost calculation for node 4). As a result, the result of the cost calculation for the relay node 4 is “6”, and the result of the cost calculation for the relay node 3 is “9”.

  Further, after changing the destination node G to a calculated node, as shown in FIG. 5 (D), a transit node 4 having the smallest cost calculation result is set as a new calculation start node in each node. Set as. A cost calculation is performed for each node (via node 1 and node 2 in FIG. 5) connected to the via node 4 via one link. As a result, the result of the cost calculation for the transit node 1 is “21”, and the result of the cost calculation for the transit node 2 is “18”.

  Subsequently, after changing the transit node 4 to the calculated node, as shown in FIG. 5E, the transit node 3 having the minimum cost computation result is set as a new computation origin node in each node. Then, the cost calculation is executed for each node (via node 2 and departure node S in FIG. 5) connected to the transit node 3 via one link. As a result, the result of the cost calculation for the transit node 2 is “11”, and the result of the cost calculation for the departure node S is “23”. Since the cost calculation results for these nodes have the smallest value among the cost calculation results for the node, a link aggregate corresponding to the cost calculation results is stored.

  Further, after changing the transit node 3 to the calculated node, as shown in FIG. 5 (F), the transit node 2 having the smallest cost computation result is set as the next computation origin node. Then, the cost calculation is executed for each node (in FIG. 5, the departure node S and the transit node 1) connected to the transit node 2 via one link. As a result, the result of the cost calculation for the departure node S is “20”, and the result of the cost calculation for the transit node 1 is “21”.

  Since the cost calculation results for these nodes have the smallest value among the cost calculation results for the node, a link aggregate corresponding to the cost calculation results is stored. Note that the link aggregate for the transit node 1 may be stored both when the transit node 2 is used as the computation start node and when the transit node 4 is used as the computation start node.

  Then, after changing the transit node 2 to the calculated node, the node having the smallest cost calculation result among the nodes is the departure node S. For this reason, the second cost calculation ends.

As described above, when the second cost calculation is terminated, for each node, the cost calculation result that minimizes the cost calculation result and the link combination that minimizes the cost calculation result (that is, the node reaches the node). At least one of the connection order of the links and the connection order of the nodes that have passed through the process is stored in the RAM 42 as a link aggregate.
<About route generation>
Here, it returns to description of a route alerting | reporting process (namely, FIG. 2). In the route notification process, route generation for generating a plurality of routes from the departure place to the destination is executed (S160).

Here, FIG. 6 is a flowchart showing a route generation processing procedure, and FIG. 7 is an explanatory diagram for explaining the processing content of route generation.
As shown in FIG. 6, in the route generation of the present embodiment, first, the link group stored in the first cost calculation is expanded (S610). For example, as shown in FIG. 7A, the link group developed in S610 is based on the connection order of the links (nodes) from the departure point to each node and the result of the cost calculation to the corresponding node. It is represented.

  Subsequently, the link aggregate stored in the second cost calculation is expanded (S620). For example, as shown in FIG. 7B, the link aggregate developed in S620 includes the connection order of links (nodes) from the destination to each node, and the result of the cost calculation to the corresponding node. It is represented by

  Further, based on the developed link group and link aggregate, each combination of links to the same node is integrated, and each integrated link combination is detected as each route from the departure point to the destination ( S630). In S630 in the present embodiment, for example, as shown in FIG. 7C, the route from the departure node S to the destination node G, detected by the first cost calculation or the second cost calculation, is One. Furthermore, the combination of the links from the departure node to each of the transit node 1, the transit node 3 and the transit node 4 stored in the first cost computation, and the transit node 1 and transit node stored in the second cost computation 3 and the link combinations from the destination nodes up to the respective via nodes 4 are connected to each corresponding node to be one of the routes.

Thereafter, the process proceeds to S170 of the route notification process.
In S170, one route is set as a representative route among a plurality of routes generated by route generation. In S170 of the present embodiment, a route with the smallest cost calculation result among a plurality of routes is set as a representative route.

  Subsequently, one route is extracted from a plurality of routes (S180). Hereinafter, the route extracted in S180 is referred to as a target route. In S180 of this embodiment, the representative route itself set in S170 is also extracted as a target route.

A degree of overlap α representing the degree of coincidence between the representative route and the target route is derived (S190).
The degree of overlap α in the present embodiment is derived from the following equation (1).
Overlap degree α = cost calculation result for overlapping link / cost calculation result for the representative route (1)
The “result of cost calculation for overlapping links” mentioned here is the result of cost calculation for “overlapping links”. The “overlapping link” means each of the same links in the combination of the links configuring the representative route set in S170 and the combination of the links configuring the target route set in S180. is there.

  It is determined whether or not the degree of redundancy α derived in this way is equal to or greater than a predefined ratio (for example, 75% in this embodiment) Th (S200). As a result of the determination in S200, if the degree of overlap α is equal to or greater than the specified ratio Th (S200: YES), grouping that specifies that the target route belongs to the same group as the representative route is executed (S210).

  On the other hand, if the degree of overlap α is less than the prescribed ratio Th (S200: NO), the group of the target route is held undetermined assuming that the target route does not belong to the same group as the representative route (S220). Hereinafter, a route whose group has not been determined is referred to as a remaining route.

  Subsequently, it is determined whether or not the degree of overlap α with the current representative route is derived for all routes (S230). As a result of the determination, if the redundancy α is not derived for all routes (S230: NO), the process returns to S180, a new target route is extracted, and S180 to S230 are repeated.

  On the other hand, if the degree of overlap α is derived for all routes as a result of the determination in S230 (S230: YES), it is determined whether there is a remaining route (S240). If the result of determination in S240 is that there is a remaining route (S240: YES), the process returns to S170, and a new representative route is set from the remaining routes. In S180, a new target route is extracted from the remaining routes, the degree of overlap α is derived (S190), and the steps up to S240 are repeated. That is, in S170 to S240 of the present embodiment, the degree of overlap α is derived for each remaining route, and the group to which each remaining route belongs is determined.

  As a result of the determination in S240, if there is no remaining route (S240: NO), that is, if groups have been determined for all routes, the representative route in each group is reported as a specific route (S250). ).

  Note that the specific route notification in the present embodiment may display each specific route on the display device 23, or may output the contents of each specific route from the voice output device 24 by voice. Further, in S250 of the present embodiment, information on routes belonging to the same group as the specific route is also notified.

Subsequently, according to the instruction input via the input reception device 25, it is determined whether or not one specific route is designated from a plurality of notified specific routes (S260).
As a result of the determination in S260, if one specific route is not designated (S260: NO), the process returns to S250 and waits until one specific route is designated. When one specific route is designated (S260: YES), a well-known route guidance process for guiding a route from the departure point to the destination is executed according to the designated specific route (S270). In the route notification process of the present embodiment, this route guidance process is continued until the host vehicle reaches the destination or the power supply of the navigation device 10 is cut off.
<Operation example>
Next, an operation example of the navigation device 10 will be described.

  Here, as an operation example, as a rough route from the departure point S to the destination G, a route via the transit point 1 and the transit point 6, a route via the transit point 2 and the transit point 11, and a transit point 3 , And a route that passes through the waypoint 12 exist, and there are a plurality of variations in the route that have some differences in the waypoints. Here, FIG. 8 schematically shows map data in a situation assumed as an operation example. Circled numbers and symbols indicate nodes corresponding to a departure point, a transit point, and a destination. A line connecting the links represents each link. Furthermore, in FIG. 8, the numbers given to each link represent the unit cost of each link.

Under such circumstances, when the route notification process is executed, the following plurality of routes 1 to 9 are detected as a result of S160.
Route 1 Departure point S, waypoints 1, 4, 6, destination G
Route 2 Departure point S, waypoints 1, 4, 5, 6, destination G
Route 3 Departure point S, waypoints 1, 5, 6, destination G
Route 4 Departure point S, waypoints 2, 7, 11, destination G
Route 5 Departure point S, waypoints 2, 7, 8, 11, destination G
Route 6 Departure point S, waypoints 3, 10, 12 and destination G
Route 7 Departure point S, waypoints 3, 9, 12, destination G
Route 8 Departure point S, waypoints 2, 8, 11 and destination G
Route 9 Departure point S, waypoints 3, 9, 10, 12, destination G
In the route notification process, the route 1 having the minimum cost calculation result is set as the representative route among the routes 1 to 9. Then, the degree of overlap α between this representative route (that is, route 1) and each other route is derived. Although the degree of overlap α with respect to the routes 2 and 3 is equal to or higher than the prescribed ratio Th, the degree of overlap α with the routes 4 to 9 is less than the prescribed ratio Th.

  As a result of executing the cycle from S170 to S230 in the route notification process to all routes, as shown in FIG. 9A, routes 1 to 3 are classified into the same group as route 1. To do. On the other hand, for the routes 4 to 9, the groups to which the routes 4 to 9 belong are in an undetermined state as remaining routes.

  Thereafter, the route from S170 to S230 is executed as a new representative route, with the route 4 having the smallest cost calculation result among the remaining routes as a new representative route. , 8 are classified into the same group as the route 4. However, for routes 6, 7, and 9, the groups to which these routes belong are in an undetermined state as remaining routes.

  Furthermore, when the route from S170 to S230 is executed for all the remaining routes as a new representative route with the route 6 having the smallest cost calculation result among the remaining routes, FIG. ), The routes 6, 7, and 9 are classified into the same group as the route 6. Therefore, the group to which each route belongs is determined for all routes. In FIG. 9B, each shaded route represents a representative route.

  In the route notification process, the representative route of each group is set and notified as a specific route among all the routes for which groups are determined in this way (S250). For example, as shown in FIG. 10, this notification is displayed on the display device 23 in such a manner that each specific route can be distinguished from other routes (that is, a representative route belonging to the same group). In FIG. 10, the specific route is represented by a bold line (solid line, broken line).

Thereafter, one specific route is selected according to the information input via the input receiving device 25, and route guidance is executed for the selected specific route.
[Effect of the embodiment]
As described above, according to the navigation device 10 of the present embodiment, each route in which the degree of coincidence (redundancy α) is reliably less than the specified ratio Th can be detected as a specific route.

  Since the specific routes detected in this way are greatly different from each other, the navigation device 10 allows the user of the navigation device 10 to easily select a route according to the user's own purpose. it can. In other words, for example, it is possible to provide a navigation device with improved convenience as compared with the technique described in Patent Document 1 (Japanese Patent Laid-Open No. 2002-202137).

  Furthermore, in the navigation apparatus 10, the combination of the links constituting the link group stored in the first cost calculation and the combination of the links constituting the link aggregate stored in the second cost calculation are connected for each same node. By doing so, a plurality of routes are generated (detected).

  Therefore, in the route notification process, a plurality of routes that can be assumed as routes from the departure point to the destination can be reliably detected by generating a plurality of routes by such a method.

  In particular, by generating a plurality of routes by such a method, a plurality of routes can be detected with a small amount of processing compared to a case where the Dijkstra method is executed a plurality of times (for example, three times) or more. That is, according to the navigation device 10, it is possible to reduce the time required to detect a plurality of routes.

  In addition, as a cost calculation in route generation (S140 and S150 in route notification processing), when a sum is derived for one type of unit cost for each combination of links connecting each node up to each node, a plurality of routes Can be generated in terms of unit cost.

  That is, if the unit cost in this case is the link length, a plurality of routes can be generated according to the travel distance from the departure place to the destination, and if the unit cost is the time length, the plurality of routes can be created. It can be generated according to the travel time from to the destination. Furthermore, if the unit cost is the amount of money required to move the link, multiple routes can be generated according to the cost required from the departure point to the destination, and the unit cost is defined as the degree of congestion on the road. A plurality of routes can be generated according to the amount of traffic jam from the departure point to the destination. Furthermore, if the unit cost is the amount of energy consumed when moving from one end of the road to the other, the amount of energy required from the starting point to the destination (for example, fuel consumption) Can be generated accordingly.

  If the cost calculation in route generation (S140 and S150 in route notification processing) is weighted addition or weighted average for at least two types of unit costs, a plurality of routes combining various viewpoints can be generated. it can.

As a result, according to the navigation device 10, one route can be selected from a plurality of routes generated from various viewpoints, and the navigation device 10 is more convenient for the user. be able to.
[Other Embodiments]
As mentioned above, although embodiment of this invention was described, this invention is not limited to the said embodiment, In the range which does not deviate from the summary of this invention, it is possible to implement in various aspects.

  For example, in the route notification process of the above-described embodiment, in the route generation (S160), the combination of the links constituting the link group and the combination of the links constituting the link aggregate are connected to the same node. Although a plurality of routes including routes having a large difference are generated, the method of generating the plurality of routes is not limited to this. That is, as a method for generating a plurality of routes, any detection method may be used as long as a plurality of routes having a large difference (that is, the difference is equal to or greater than the specified ratio Th) can be detected.

  Further, in S170 in the route notification process of the above embodiment, the route having the minimum cost calculation result is set as the representative route among the plurality of routes, but the reference to be set as the representative route is limited to this. It is not a thing. That is, a route with the maximum cost calculation result may be used as a representative route, and a route with a cost calculation result having an intermediate value may be used as the representative route.

  Further, in S250 in the route notification process of the above embodiment, the route other than the specific route is also notified among the detected plurality of routes. However, the manner of notification is not limited to this, and the specific route is not limited to this. Other routes may not be notified. In this case, for example, in S210 of the route notification process, a prohibition flag that prohibits notification in S250 may be set for a target route having a degree of overlap α less than the specified ratio Th.

In S140 (first cost calculation) in the route notification process of the above embodiment and S150 (second cost calculation) in the route notification process, the link group and the link aggregate are stored in the RAM 42, respectively. A medium for storing these link groups and link aggregates is not limited to the RAM 42. That is, the link group and the link aggregate may be stored in the storage device 26 in S140 (first cost calculation) and S150 (second cost calculation).
[Correspondence between Embodiment and Claims]
Finally, the relationship between the description of the above embodiment and the description of the scope of claims will be described.

  S110 in the route notification process of the above embodiment corresponds to the departure point acquisition means of the present invention, S120 in the route notification process corresponds to the destination acquisition means of the present invention, and S130 in the route notification process corresponds to the present invention. It corresponds to map data acquisition means.

  In addition, S140 to S160 in the route notification process correspond to the route detection unit of the present invention, S170 to S240 in the route notification process correspond to the specific route detection unit of the present invention, and S250 in the route notification process corresponds to the present invention. It corresponds to the route notification means.

  Further, S170 to S190 in the route notification process corresponds to the duplication degree deriving unit of the present invention, and S170 to S220 and S240 in the route notification process correspond to the deriving repeating unit of the present invention.

  Further, S140 in the route notification process corresponds to the first cost calculation means of the present invention, and S150 in the route notification process corresponds to the second cost calculation means of the present invention. S270 in the route notification process corresponds to the route guidance means of the present invention.

  The function obtained by executing S110 to S250 in the route notification process corresponds to the route notification device of the present invention. The RAM 42 in the above embodiment corresponds to the storage unit of the present invention.

DESCRIPTION OF SYMBOLS 10 ... Navigation apparatus 21 ... Position detection apparatus 22 ... Information communication apparatus 23 ... Display apparatus 24 ... Audio | voice output apparatus 25 ... Input reception apparatus 26 ... Memory | storage device 31 ... GPS receiver 32 ... Gyro sensor 33 ... and geomagnetic sensor 40 ... Navigation ECU 41 ... ROM 42 ... RAM 43 ... CPU

Claims (5)

Map data acquisition means for acquiring map data;
A departure point acquisition means for acquiring a departure point;
A destination acquisition means for acquiring a destination;
Based on the map data acquired by the map data acquisition means, a route detection means for detecting a plurality of routes from the departure place acquired by the departure place acquisition means to the destination acquired by the destination acquisition means;
A specification for detecting, as a specific route, each of a plurality of typical routes detected by the route detection means and each of which is a plurality of representative routes and whose difference is equal to or greater than a predetermined ratio, which is a predetermined ratio Route detection means;
A route notification device comprising: route notification means for reporting a specific route detected by the specific route detection means. The specific route detecting means includes
A multiplicity deriving unit for deriving a multiplicity representing the degree of coincidence with the representative route for each of the routes detected by the route detecting unit, with one route being a representative route among the plurality of routes,
Derivation for repeatedly deriving the degree of duplication for each of the remaining routes by setting each of the routes having the degree of duplication less than the specified ratio as a residual route, newly setting the representative route from among the remaining routes. And repeating means,
2. The route notification device according to claim 1, wherein each of the representative routes set by the duplication degree deriving unit and the deriving repeating unit is detected as the specific route. The map data includes at least a node representing a specific point on the road, a link connecting the nodes, and a unit cost assigned to each link,
The route detection means includes
For each link group that is a combination of links from the starting point to each node, a cost calculation is performed, and at least the link group that minimizes the result of the cost calculation is stored in the storage unit for each node. First cost calculating means,
For each link aggregate that is a combination of links from the destination to each node, a cost calculation is performed, and at least the link aggregate that minimizes the result of the cost calculation is stored for each node. Second cost calculating means for storing
Based on the link group and the link aggregate stored in the storage unit by the first cost calculating means and the second cost calculating means, the link group and the link aggregate for the same node The route notification device according to claim 1 or 2, wherein each combination is detected as each route from the departure place to the destination. The unit cost is
The length of the road represented as each link, the length of time required to move from one end of the road to the other end, the degree of traffic congestion on the road, the amount required to move the road, and the road from one end The route notification device according to claim 3, wherein the route notification device is at least one of energy amounts consumed when moving to the other end. The route notification device according to any one of claims 1 to 4 and route guidance for one specific route among a plurality of specific routes notified by the route notification means of the route notification device. A navigation device comprising route guidance means.