JP2016194430A - Route search device, route search method and route search program, and recording medium - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a route search device with which it is possible to reach any transit point efficiently, even when an accident or trouble abruptly occurs between the current position and a transit point.SOLUTION: The route search device acquires position data indicating the current position of a vehicle, acquires point data indicating a plurality of transit point A and transit point B to which the vehicle is expected to move, and searches, on the basis of each position data and point data, for a plurality of routes, mutually different in the sequence of movement to each transit point, that are the routes on which the vehicle can move via the transit point A and the transit point B. Thereafter, the route search device determines, on the basis of each of the searched routes, a branch point J1 that is a branch point between the current position and each transit point and through which it is possible to reach any transit point from the current position. Then, when the distance between the current position and the branch pint J1 is less than or equal to a prescribed threshold distance, the route search device searches for a route along which the vehicle reaches the transit point A and the transit point B through the branch point J1.SELECTED DRAWING: Figure 3

Description

  The present application belongs to a technical field of a route search device, a route search method, a route search program, and a recording medium, and more specifically, a route search device and a route search method for searching for a route that guides the movement of a moving object, and the route The present invention belongs to the technical field of a search device program and a recording medium on which the program is recorded.

  In recent years, navigation devices that are mounted on vehicles and guide the movement of the vehicles have become widespread. In the guidance, when the destination and departure location (or current location) of the movement are input, a guidance route from the departure location or the current location to the destination is set and used for the guidance. As prior art documents regarding the setting of such a guide route, for example, Patent Document 1 and Patent Document 2 below can be cited.

  At this time, the following Patent Document 1 specifies a plurality of waypoints, searches for a plurality of routes having different route orders, determines whether the searched route matches a preset condition, and further satisfies the condition. It is described that it is corrected to fit, and a plurality of routes including a waypoint are searched. Further, the technique described in Patent Document 2 below is configured to search for a route that can efficiently visit a transit point from the current location to the destination.

JP 2005-233632 A JP-A-9-101168

  Here, the techniques described in Patent Document 1 and Patent Document 2 are techniques for searching for a route including a plurality of waypoints, and in particular, the order of going around the waypoints differs from that in Patent Document 1. Searching for multiple routes is described.

  However, in the technique described in Patent Document 1, for example, when a user's schedule is changed during the guidance and it becomes necessary to go to the second waypoint first, or the first waypoint or the second waypoint There is a problem that it is not possible to cope with the case where the user is wondering whether to go first.

  Further, the technique described in Patent Document 2 has a problem that if a route is re-searched when a sudden traffic jam or the like occurs during guidance, there is a possibility that the route may be inefficiently warped. At this time, it is a common technique to search for the optimal route taking into account so-called traffic jam information, but the traffic conditions often change from moment to moment, so the optimum guidance route is searched at that time. Is difficult.

  Therefore, the present application has been made in view of the above-described problems, and an example of the problem is, for example, even if an accidental injury or the like suddenly occurs between the current position and the waypoint. Route search apparatus and route search method capable of efficiently reaching any via point even when the order of arrival at each via point is not determined, and program for the route search device and It is to provide a recording medium on which a program is recorded.

  In order to solve the above-mentioned problem, the invention according to claim 1 is characterized in that position information acquisition means for acquiring current position information indicating the current position of a moving body and point information acquisition for acquiring point information about a plurality of points. Means, a possible route searching means for searching for a plurality of movable routes passing through the plurality of points based on the current position information and the point information, and a current position and the points based on the plurality of movable routes. A determination unit that determines a branch point that is between a plurality of points and can reach any of the plurality of points; and a distance between the current position and the determined branch point is the movement Branch point route determining means for determining a branch point passage route for reaching each point through the branch point when the distance is equal to or less than a preset threshold distance due to body movement.

  In order to solve the above-mentioned problem, the invention according to claim 5 is the current position information indicating the current position of the moving body in the route searching method executed in the route searching apparatus for searching for the route along which the moving body moves. A location information acquisition step of acquiring location information, a location information acquisition step of acquiring location information about a plurality of locations, and searching for a plurality of movable routes passing through the locations based on the current location information and the location information Based on the possible route search step and the plurality of movable routes, a branch point that is between the current position and the plurality of points and can reach any of the plurality of points is determined. When the distance between the determination step and the current position and the determined branch point is less than or equal to a preset threshold distance due to the movement of the moving body, the point is reached through the branch point Includes a branch point path determining step of determining the branching point passage path because, the.

  In order to solve the above-described problem, the invention described in claim 6 causes a computer to function as the route search device described in any one of claims 1 to 4.

  In order to solve the above-described problems, the invention according to claim 7 records the route search program according to claim 6 so as to be readable by the computer.

It is a block diagram which shows the schematic structure of the route search apparatus which concerns on embodiment. It is a block diagram which shows schematic structure of the navigation apparatus concerning 1st Example. It is a figure which shows an example of the road used as the object of the route search which concerns on 1st Example. It is a flowchart which shows the route search process which concerns on 1st Example. It is a flowchart which shows the branch point determination process which concerns on 1st Example. It is a figure explaining the branch point determination process which concerns on 1st Example, (a) is a figure which illustrates extraction of the node in the said branch point determination process, (b) is a branch point candidate in the said branch point determination process (C) is a figure which illustrates the determination of the said branch point candidate. It is a flowchart which shows the route search process which concerns on 2nd Example, (a) is a flowchart which shows the whole said route search process, (b) is a flowchart which shows the branch point determination process which concerns on 2nd Example. . It is a figure explaining the branch point determination process which concerns on 2nd Example, (a) is a figure which shows the 1st example of the said branch point determination process, (b) is a 2nd example of the said branch point determination process. (C) is a figure which shows the example of the said branch point candidate. It is a flowchart which shows the route search process which concerns on 3rd Example.

  Next, the form for implementing this application is demonstrated using FIG. FIG. 1 is a block diagram illustrating a schematic configuration of the route search apparatus according to the embodiment.

  As shown in FIG. 1, the route search apparatus S according to the embodiment includes a position information acquisition unit 1, a point information acquisition unit 2, a possible route search unit 3, a determination unit 4, and a branch point route determination unit 5. , And is configured.

  In this configuration, the position information acquisition unit 1 acquires current position information indicating the current position of the moving body.

  On the other hand, the point information acquisition means 2 acquires point information about a plurality of points.

  Then, the possible route searching means 3 searches for a plurality of movable routes passing through a plurality of points based on the current position information and the point information.

  Accordingly, the determination unit 4 determines a branch point that is between the current position and the plurality of points and can reach any of the plurality of points based on the plurality of movable routes. .

  The branch point route determination means 5 reaches each point through the branch point when the distance between the current position and the branch point becomes equal to or less than a preset threshold distance due to the movement of the moving body. A branch point passage route is determined.

  As described above, according to the operation of the route search device S according to the embodiment, the point that can reach any point through the branch point from the current position of the moving body based on a plurality of movable routes. A branch point is determined, and when the distance between the current position and the branch point is equal to or less than the threshold distance, a branch point passing route for reaching each point through the branch point is searched. Therefore, a branch point that can reach any point is determined, and when the distance to the branch point is equal to or less than the threshold distance, a branch point passing route is searched. For example, a sudden jump occurs between the current position and each point. Even if a movement injury occurs, it is possible to reach any point efficiently. Even when the order of arrival at each point during movement is not determined, it is possible to reach any point efficiently by passing through the branch point passage route.

  Next, specific examples corresponding to the above-described embodiment will be described with reference to FIGS. In addition, each Example demonstrated below is an Example at the time of applying embodiment to the route search process in the navigation apparatus which moves with a vehicle or a bicycle. At this time, the vehicle or the bicycle corresponds to an example of the moving body according to the embodiment.

(1) First Example First, a first example according to the embodiment will be described with reference to FIGS. 2 is a block diagram illustrating a schematic configuration of the navigation device according to the first embodiment, and FIG. 3 is a diagram illustrating an example of a road that is a target of a route search according to the first embodiment. 4 is a flowchart showing a route search process according to the first embodiment, FIG. 5 is a flowchart showing a branch point determination process according to the first embodiment, and FIG. 6 is a branch point according to the first embodiment. It is a figure explaining a determination process. At this time, in FIG. 2, the same member numbers as the respective constituent members in the route search apparatus S are used for the respective constituent members in the examples corresponding to the respective constituent members in the route search apparatus S according to the embodiment shown in FIG. 1. ing.

  As shown in FIG. 2, the navigation device NV according to the first embodiment includes a CPU, a RAM (Random Access Memory), a ROM (Read Only Memory), and the like, and includes an example of the route search device S according to the embodiment and the present application. A processing unit S and an HDD (Hard Disc Drive) or SSD (Solid State Drive) corresponding to an example of the “data acquisition unit”, an example of the “determination unit”, and an example of the “extraction unit” according to the present application. An interface 11 for connecting the navigation device NV and a network such as the Internet (not shown) to control mutual data exchange, position data indicating the current position of the vehicle on which the navigation device NV is mounted, etc. Sensor 12 that outputs a signal, an operation button, a remote control, a touch panel, etc. An operation unit 13 corresponds to an example of the stage ", a display 14 including a liquid crystal display or the like, and is composed of.

  In this configuration, the recording unit 10 includes navigation data including map data D, voice data, and the like used for guidance processing (including route search processing according to a first embodiment described later) in the navigation device NV, and the guidance. A program or the like for executing processing is recorded in a nonvolatile manner. In addition, the sensor 12 detects the current position using, for example, a method of receiving navigation radio waves from a GPS (Global Positioning System) navigation satellite (not shown) or an autonomous method using an output from an acceleration sensor (not shown), The position data indicating the current position is generated and output to the processing unit S. Thereby, the processing unit S is based on the user's operation performed in the operation unit 13, and the traffic information that indicates the location data, the map data D, and the like, and the occurrence status of the traffic jam acquired from the outside via the interface 11. The guidance processing according to the first embodiment is comprehensively controlled using road information and road information. At this time, a map or the like to be presented to the user in the guidance process is displayed on the display 14 under the control of the processing unit S.

  Next, more specifically, the processing unit S acquires the position information acquisition unit 1 corresponding to an example of the position information acquisition unit 1 according to the embodiment and the point information acquisition corresponding to an example of the point information acquisition unit 2 according to the embodiment. Unit 2, the possible route search unit 3 corresponding to an example of the possible route search unit 3 according to the embodiment, the example of the determination unit 4 according to the embodiment, and the example of the “branch point determination unit” according to the present application. The determination unit 4 and a branch point route determination unit 5 corresponding to an example of the branch point route determination unit 5 according to the embodiment are configured. At this time, the position information acquisition unit 1, the point information acquisition unit 2, the possible route search unit 3, the determination unit 4, and the branch point route determination unit 5 are each hardware such as the CPU constituting the processing unit S. It may be realized by a wear logic circuit, or may be realized by software when the CPU or the like reads and executes a program corresponding to a route search process according to a first embodiment described later. Good.

  Then, the position information acquisition unit 1 acquires the position data from the sensor 12 as the route search process according to the first embodiment. On the other hand, the point information acquisition unit 2 acquires route point data indicating a plurality of route points where the vehicle on which the navigation device NV is mounted is scheduled to move, for example, from the map data D or via the network. At this time, it is preferable that the waypoint data is acquired from the map data D or the like corresponding to the waypoint designation operation by the user in the operation unit 13. Then, the possible route search unit 3 searches for a plurality of routes along which the vehicle moves via the plurality of waypoints based on the position data and the waypoint data. At this time, with respect to each route, the order of passing through the respective transit points is made different from each other.

  Accordingly, the determination unit 4 is a branch point (intersection) on the route between the current position of the vehicle and each waypoint based on the route searched by the possible route search unit 3, and the branch from the current position. A branch point that passes through the point and can reach any waypoint is determined. When the distance between the current position and the determined branch point is equal to or less than a predetermined threshold distance, the branch point route determination unit 5 is configured to reach each waypoint through the branch point. Determine the route.

  Next, the principle of the route search process according to the first embodiment will be described with reference to FIG.

That is, as illustrated in FIG. 3, it is assumed that there is a vehicle equipped with the navigation device NV at the current position C indicated by the current position mark of the upward triangle. In FIG. 3, the vehicle existing at the current position C is scheduled to pass through the transit point A and the transit point B by the subsequent movement, but it is arbitrary whether the transit point A or the transit point B is routed first. Suppose that Then, as the road on which the vehicle can move to the post, there is a road _{R CA,} roads _{R CB,} roads _{R CJ1,} roads _{R BJ1,} roads _{R AJ1} and road _{R AB} illustrated in FIG. At this time, the road _{R CA,} roads _{R AB} and road _{R AJ1} has crossed over land A, roads _{R CB,} roads _{R BJ1} and road _{R AB} has crossed over land B, further road _{R CJ1,} road _{R AJ1} and road _{R BJ1} intersect at an intersection J1.

At this time, as illustrated in FIG. 3, the route A and the route B should be reached, but if the arrival order is arbitrary, the route that the vehicle should travel is the route A and the route B There can be more than one. In such a case, in order to shorten the moving distance or travel time as a whole For example, as through in the order of route point A⇒ waypoint B, and moved on the road R _CA toward the first waypoint A . Then, after a certain amount of progress on the road _RCA toward the waypoint A, a movement obstacle such as an accident occurs in front of the road _RCA , and further movement on the road _RCA becomes impossible. As such a vehicle, there is no choice but to return to the original place and proceed on the road R _CJ1 or the road R _CB , resulting in a delay in reaching the transit point A or the transit point B.

Therefore, in the route search process according to the first embodiment, when the route passes through the route point A and the route point B illustrated in FIG. 3, roads that can reach both the route point A and the route point B until the middle of the movement. Advancing and searching for a subsequent route at a branch point on the way based on the road condition at that time, the occurrence of traffic jams, and the like. More specifically, in the case illustrated in FIG. 3, first, the vehicle is guided to move from the current position C to the intersection J1 which is a branch point to the waypoint A and the waypoint B, and then, according to the road condition and the like, It guides to proceed either road _{R AJ1} or road _{R BJ1.}

  Next, the route search process according to the first embodiment will be described more specifically with reference to FIGS. Note that the vehicle on which the navigation device NV is mounted in the route search process described below is present at the current position C illustrated on the left in FIG. 6A, and then the transit point illustrated in FIG. 6A. It shall move via both A and waypoint B. Even in this case, it is assumed that route A or route B is routed first.

As the road on which the vehicle can travel in the case of illustrated in FIG. 6, unlike the case illustrated in FIG. 3, the road _{R CA,} roads _{R CB,} roads _{R CJ2,} roads _{R BJ2,} roads _{R AJ2,} roads _{R J1J2,} road _{R BJ1,} there is a road _{R AJ1} and road _{R AB.} In addition, road R _CA , road R _AB , road R _AJ1 and road R _AJ2 intersect at transit point A, and road R _CB , road R _AB , road R _BJ1 and road R _BJ2 intersect at transit point B cage, roads _{R J1J2,} roads _{R AJ1} and road _{R BJ1} has intersect at an intersection J1, roads _{R J1J2,} roads _{R AJ2,} roads _{R BJ2} and road _{R CJ2} intersect at an intersection J2.

  As shown in the flowchart corresponding to FIG. 4, the route search process according to the first embodiment is started based on an instruction operation in the operation unit 13, for example. When the route search process is started, the processing unit S first sets the waypoint A and the waypoint B by, for example, acquiring position information indicating the position of each waypoint (step S1). . At this time, the position information and the like are temporarily recorded in the recording unit 10 after being acquired by the point information acquisition unit 2. Next, the processing unit S acquires the current position of the vehicle (step S2). The position data indicating the current position at this time is acquired from the sensor 12 by the position information acquisition unit 1.

  Next, the possible route search unit 3 and the determination unit 4 of the processing unit S determine the branch point of the road that can reach both the route point A and the route point B using the map data D or the like ( Step S3). The branch point data indicating the determined branch point is temporarily recorded in the recording unit 10. Step S3 will be described in detail later.

Thereafter, the processing unit S searches for a route from the current position C to the determined branch point (step S4). Thereafter, the processing unit S monitors whether or not the determined branch point has been approached to a preset threshold distance (step S5, step S5; NO). Specifically, for example, the threshold distance is based on node data as map data D constituting each road, and the node immediately preceding the node corresponding to the branch point and the node corresponding to the branch point It is preferable that the distance is between. In addition, when the branch point is, for example, a long single road, and there is no node between the branch point,
(A) Empirical values such as “distance from the position 20 seconds before reaching the branch point to the branch point” and “500 meters to the branch point” are used.
(B) The user of the navigation device NV uses the operation unit 13 to set an arbitrary value such as “distance to the branch point in ○ second” or “the branch point to ○ meter”, or
(C) When approaching the curve in the above-mentioned straight road, it is determined that it is near a branch point
It is conceivable to set the threshold distance by such a method.

  Then, when it is detected that the vehicle has approached the branch point up to the threshold distance (step S5; YES), the processing unit S provides, for example, information indicating the traffic congestion status at that time, road information, and the like via the interface 11. Obtain (step S6). Thereafter, the branch point route determination unit 5 of the processing unit S re-establishes a route from the front branch point via the waypoint A and the waypoint B based on the information indicating the traffic congestion acquired in step S6 and the map data D. Alternatively, a plurality of searches are performed (step S7). Thereafter, the processing unit S extracts a route having the lowest movement cost for moving via the waypoint A or the like from each of the searched new routes (routes that pass through the branch points). Information indicating the extracted route is presented (output) using, for example, the display 14 (step S8). Thereafter, the processing unit S starts guiding the vehicle using the route selected by the user's operation in the operation unit 13 based on the information indicating the presented route as a guide route.

  Here, the “movement cost” refers to the difficulty in selecting (adopting) the route (road) that has the movement cost when the vehicle is guided along the guidance route. The higher the travel cost, the less likely it is to be selected as a guide route (in other words, the lower the travel cost, the easier it is to select the guide route). Specifically, the travel cost is an index obtained by, for example, quantifying the distance to the point to be reached, the required time, the toll, and the like for the route and normalizing them.

  Next, the branch point determination process in step S3 will be specifically described with reference to FIGS.

Specifically, the determination unit 4 of the processing unit S as the branch point determination process of the step S3, first, as shown in FIG. 5, for the node included in the map data D, based on the current position C of the vehicle, All nodes on the route within the preset range are detected (step S30). In this step S30, for example, the route point A and the route point B to be reached are included, and the route point closest to the current position C of the vehicle (for example, the route point A in the case of the road illustrated on the left in FIG. 6A) It is preferable that a straight line distance to the current position C is a radius, and a circle centered on the current position C is within the preset range. In addition to this, as the above-mentioned preset range, for example, it is conceivable to have a fan-shaped range that expands to the left and right with respect to the traveling direction of the vehicle and has a radius of the linear distance. Then, as the nodes extracted in step S30 in the case illustrated in FIG. 6A, for example, the node N ₁ , the node N ₂ , the node N ₅ , the node N ₃ and the node illustrated on the right in FIG. the N _4. In this case, the node N ₁ corresponds to the transit point A, the node N ₂ corresponds to the transit point B, the node N ₅ corresponds to the current position C, the node N ₃ corresponds to the intersection J1, and the node N ₄ Corresponds to the intersection J2.

  Next, the determination unit 4 initializes a parameter n indicating the number of the node N (step S31). The initial value of the parameter n is “1”, and the maximum value is the number of nodes extracted in step S30 (5 in the case illustrated in FIG. 6).

Path and decision unit 4, which starting from the node N ₄ movement cost is indicated by a route (e.g., FIG. 6 (b) thick on the left solid line having the minimum of the path to move the route point A⇒ stopover B from node Nn and R1), starting from the node N ₄ as indicated by a broken line in the path of movement cost is minimized (e.g., FIG. 6 (b) of the route that travels through locations B⇒ stopover a from the node Nn route R2) and Are searched (step S32). Then, the determination unit 4 determines whether or not the difference in the movement cost between the two routes searched at that time (the route R1 and the route R2 in the case of FIG. 6B) is equal to or less than a preset threshold cost. Is determined (step S33). At this time, specifically, for example, quoting the example shown in FIG.
(D) 0.5 <Movement cost of route R1 / Movement cost of route R2 <2 (that is, a node for which the difference between the movement costs of route R1 and route R2 is more than doubled will be described later) Excluded from the candidates), or
(E) Let the user manually set the difference in the required time as the movement cost, and if the absolute value of the required time difference as the movement cost between the route R1 and the route R2 is within the difference set by the user, As a candidate for a branch point described later,
Such a method can be considered. If it is determined in step S33 that the difference in travel cost between the two routes searched at that time is larger than the threshold cost (step S33; NO), the determination unit 4 proceeds to step S36 described later. On the other hand, if it is determined in step S33 that the difference in travel cost between the two routes is equal to or less than the threshold cost (step S33; YES), the determination unit 4 adds the travel costs for the two routes. Then, the total movement cost Cn for the node Nn is calculated, and the value is temporarily recorded in the recording unit 10 (step S34). Thereafter, the determination unit 4 sets the node Nn that is the starting point of the two routes as a branch point candidate (step S35). Information about the branch point candidates in step S35 is also temporarily recorded in the recording unit 10. If illustrated in FIG. 6 is also a node N ₄ which is the starting point of the route R1 and route R2 becomes a candidate for the branch point (see FIG. 6 (b) right hatching).

  Next, the determination unit 4 determines whether or not the value of the parameter n at that time has reached the maximum value (step S36). If the value has not reached the maximum value (step S36; NO), the parameter n Is incremented by 1 (step S38), the process returns to step S32 and the above-described processing is repeated. On the other hand, in the determination of step S36, when the value of the parameter n at that time is the maximum value (step S36; YES), the determination unit 4 calculates the sum calculated in step S34 for each node Nn. The node Nn having the smallest total movement cost Cn is extracted from the movement costs Cn, and this node Nn is set as a new branch point (step S37), and then the process proceeds to step S4.

In the case illustrated in FIG. 6 by the branch point determination processing described with reference to FIG. 5 above, the intersection J1 corresponding to the node N ₃ having the minimum total movement cost C ₃ is determined as the branch point. (See FIG. 6 (c)-).

  As described above, according to the route search process according to the first embodiment, a plurality of routes (see the route R1 and the route R2 described in FIG. 6) having different orders through the route point A and the route point B. Based on the current position C of the vehicle, the branch point that can reach the waypoint A and the waypoint B through the branch point is determined, and the distance between the current position C and the branch point is equal to or less than the threshold distance. When it becomes, the route for reaching the waypoint A and the waypoint B through the branch point is searched. Therefore, the branch point that can reach the stop point A and the stop point B is determined, and when the distance to the stop point is equal to or less than the threshold distance, the route that passes the branch point is searched again. Even if a sudden accident or the like occurs, the route point A and the route point B can be efficiently reached. In addition, even when the route order of the route point A and the route point B is not determined, the route point A and the route point B can be efficiently reached.

  Further, there is a difference in movement cost between the nodes Nn corresponding to the respective routes within the predetermined range with the current position C as a reference, and the routes reaching the transit point A and the transit point B through the node Nn. A node Nn that is equal to or lower than a predetermined threshold cost is determined as a branch point candidate. When a plurality of candidates are determined, a candidate having the smallest total movement cost Cn is determined as a branch point. Therefore, for the node Nn within the predetermined range, the branch point is determined using the movement cost of the route passing through the node Nn, so that an appropriate branch point can be determined with a smaller processing amount.

  Furthermore, when a plurality of routes passing through the branch point are searched, the route with the lowest movement cost for each route is determined as the vehicle guide route (see step S7 and step S8 in FIG. 4). The most appropriate guide route can be set when actually moving.

  When setting the optimum guide route, route information indicating each of a plurality of routes passing through the branch point is displayed on, for example, the display 14 and presented to the user, and a subsequent guide route is selected by the user's selection operation. You may comprise. In this case, since one of the routes is selected as the guide route based on the presented route information, the guide route that reaches the waypoint A and the waypoint B can be selected according to the preference of the user.

(2) Second Example Next, a second example, which is another example according to the embodiment, will be described with reference to FIGS. FIG. 7 is a flowchart showing route search processing according to the second embodiment, and FIG. 8 is a diagram for explaining branch point determination processing according to the second embodiment.

  Further, the hardware configuration of the navigation apparatus according to the second embodiment is basically the same as the hardware configuration of the navigation apparatus NV according to the first embodiment. Therefore, in the second embodiment described below, the same components and processes as those of the navigation apparatus NV according to the first embodiment are denoted by the same member numbers and the same step numbers, and detailed description thereof is omitted.

  In a second example described below, a case where a branch point is determined by a method different from the branch point determination process according to the first example will be described as a branch point determination process in the route search process according to the embodiment.

  First, the entire route search process according to the second embodiment will be described with reference to FIG.

  As shown in the flowchart corresponding to FIG. 7A, the route search process according to the second example is started based on an instruction operation in the operation unit 13, for example, similarly to the route search process according to the first example. The And when the said route search process is started, the process part S will perform step S1 and step S2 similar to the route search process which concerns on 1st Example first.

  Next, the possible route search unit 3 and the determination unit 4 of the processing unit S determine the above branch points of the road that can reach both the route point A and the route point B as a process unique to the route search process according to the second embodiment. The determination is made using the map data D and the like (step S3-1). The branch point data indicating the determined branch point is temporarily recorded in the recording unit 10. Step S3-1 will be described in detail later.

  Thereafter, the processing unit S executes steps S4 to S8 similar to the route search processing according to the first embodiment, and starts guidance of the vehicle using the route selected by these processes as a guide route.

  Next, the branch point determination process in step S3-1 will be specifically described with reference to FIG. 7B and FIG.

  Specifically, as shown in FIG. 7B, the possible route search unit 3 of the processing unit S first determines the current position C for the current waypoint A and waypoint B as the branch point determination process in step S3-1. ⇒ Search all of the routes that pass through via A, pass through B, and the current location C, pass through B, and all the routes that pass through via A using the map data D etc. (step S40). The data indicating the search result is temporarily recorded in the recording unit 10. Next, the determination unit 4 of the processing unit S initializes each parameter used for the branch point determination process according to the second embodiment (step S41).

  Here, as the parameter used in the branch point determination process according to the second embodiment, first, a route via the current position C → route A A⇒route B (hereinafter, this route is appropriately referred to as “route Ra”). ) Indicating the parameter Ram. At this time, “m” indicates the numbers of a plurality of routes Ra that are different from each other except for the route point A → route point B, searched in step S40, the initial value is “1”, and the maximum value is This is the total number of routes Ra searched for via the current position C → route A → route B. In the following description, the maximum location is “M”.

  Next, as another parameter, there is a parameter Rbs indicating a route through the current position C⇒route B B⇒route A (hereinafter, this route is appropriately referred to as “route Rb”). At this time, “s” indicates the numbers of a plurality of routes Rb that are searched for in the above-described step S40, except for the route B → route A, and the initial value is “1”, and the maximum value is This is the total number of routes Rb searched for via the current position C → route B → route A. In the following description, the maximum location is “S”.

  Finally, there is a parameter Nmn indicating the node N on the route data corresponding to the route a. At this time, “m” has the same meaning as that related to the route a, and “n” indicates the number of the node N on the route a searched in step S40, and its initial value is “1”. The maximum value is the total number of nodes N on the route data corresponding to the route a. In the following description, the maximum location is “N”.

  In step S41, "m", "n", and "s" are initialized.

  Next, the determination unit 4 pays attention to the node Nmn on the m-th route Ra (step S42), and determines whether the node Nmn is also on the other route Rbs using the map data D or the like. (Step S43). If it is determined in step S43 that the node Nmn is not on the other route Rbs (step S43; NO), the determination unit 4 proceeds to step S48 described later. On the other hand, if it is determined in step S43 that the node Nmn is also on the other route Rbs (step S43; YES), the determination unit 4 next selects the route from the current position in the route Ram to the node Nmn and the current in the route Rbs. It is determined using the map data D or the like whether or not the route from the position to the node Nmn matches (step S44). If it is determined in step S44 that the route from the current position to the node Nmn does not match the route Rbs and the route Ram (step S44; NO), the determination unit 4 proceeds to step S48 described later. On the other hand, when the route from the current position to the node Nmn matches the route Rbs and the route Ram in the determination in step S44 (step S44; YES), the determination unit 4 next moves from the position of the node Nmn to the waypoint A. It is determined whether or not the difference between the travel cost of the route Ram and the travel cost of the route Rbs from the position of the node Nmn to the waypoint B is equal to or less than the threshold cost (step S45). If the difference between the movement cost of the route Ram and the movement cost of the route Rbs is greater than the threshold cost in the determination of step S45 (step S45; NO), the determination unit 4 proceeds to step S48 described later.

  On the other hand, in the determination of step S45, the difference between the movement cost of the route Ram from the position of the node Nmn to the waypoint A and the movement cost of the route Rbs from the position of the node Nmn to the waypoint B is less than the above threshold cost. If there is (step S45; YES), the determination unit 4 next calculates the total movement cost Cmn for the node Nmn by adding the movement costs for the path Ram and the path Rbs, and temporarily calculates the value. Recording is performed in the recording unit 10 (step S46). Thereafter, the determination unit 4 associates the route Ram and the route bs with the node Nmn that is the starting point of the two routes, and sets an intersection or the like corresponding to the node Nmn as a branch point candidate (step S47). . Information about the branch point candidates in step S47 is also temporarily recorded in the recording unit 10.

  Thereafter, the determination unit 4 confirms whether or not “m”, “n”, and “s” have reached their maximum values in the order of “s”, “n”, and “m” (steps S48 to S48). Step S50). If “s” does not reach the maximum value S (step S48; NO), the determination unit 4 increments the “s” by one (step S54), and returns to step S43 to perform the subsequent processing. repeat. If “n” does not reach the maximum value N (step S49; NO), the determination unit 4 increments the “n” by one and initializes “s” (step S53). Returning to S42, the subsequent processing is repeated. Further, when “m” does not reach the maximum value M (step S50; NO), the determination unit 4 increments the “m” by one and initializes the “s” and the “n” respectively ( Step S52), returning to the above step S42, the subsequent processing is repeated.

  By repeating the above steps S48 to S50 and steps S52 to S54, the above steps S42 to S47 for all the routes Rbs are repeated for all the nodes Nmn on one route Ram. The repetition of step S42 to step S47 for the one route Ram is further repeated for all the routes Ram.

  On the other hand, when all of the above “m”, “n”, and “s” are the maximum values (step S48: YES, step S49; YES and step S50; YES), the determination unit 4 determines that each node The node Nmn having the smallest total movement cost Cmn is extracted from the total movement cost Cmn calculated in the above step S46 for Nmn, and this node Nmn is set as a new branch point (step S51). The process proceeds to step S4.

When the branch point determination process described above with reference to FIG. 7B is executed, first, as illustrated in FIG. 8A, from the current position C (corresponding to the node Nmn), the waypoint A and in via route point B, and between all paths Rbs by focusing on each path Ram (indicated by the thick solid line in FIG. 8) (shown by the one-dot chain line in FIG. 8) including the node N ₁ and the node N ₂ If there is no matching section (see step S43; NO or step S44; NO in FIG. 7B), the individual branch point is not determined (see the right end in FIG. 8A).

On the other hand, as illustrated in FIG. 8B, when there is one matching section between any of the routes Ram and any of the routes Rbs (FIG. 7B, step S43; YES or same) step S44;.. YES reference indicated by the broken line in FIG. 8 (b)), an intersection J2 corresponding to the node _{N 4} corresponding to the interval is determined as a branching point (Fig. 8 (b) see the right end mark ●) .

Furthermore, as illustrated in FIG. 8C, when there are two or more matching sections between any of the routes Ram and any of the routes Rbs (FIG. 7B, step S43; YES or the same step) S44;.. YES reference indicated by the broken line in FIG. 8 (c)), the intersection J1 corresponding to an intersection J2 and node _{N 3} corresponding to the node _{N 4} corresponding to each section, separate candidate determination of branch points, respectively (See the right end ● mark in FIG. 8 (c)). Then, the node N having the smaller total movement cost Cmn is determined as the actual branch point.

  As described above, according to the route search process according to the second embodiment, a node that is common to the route Ram and the other route Rbs is different from the operational effect of the route search process according to the first embodiment. A node Nmn that is a part of the path Ram from the current position C to the node Nmn is determined as a candidate for a branch point (see the mark ● in FIG. 8). When a plurality of candidates are determined, the candidate having the smallest total movement cost Cmn for the route Ram passing through one candidate is determined as a branch point. Therefore, since the branch point is determined by considering the node Nmn corresponding to the route Ram and the like as the object of examination one by one, the branch point can be determined accurately.

  In step S40, instead of searching all the routes Ra and Rb, for example, it may be configured to extract only routes whose travel costs are equal to or less than a preset travel cost. Alternatively, a predetermined number of routes Ra and Rb may be extracted in order from the route with the lowest travel cost. In this way, the processing amount as the processing unit S can be reduced.

(3) Third Example Next, a third example, which is still another example according to the embodiment, will be described with reference to FIG. FIG. 9 is a flowchart showing route search processing according to the third embodiment.

  Further, the hardware configuration of the navigation device according to the third embodiment is basically the same as the hardware configuration of the navigation device NV according to the first embodiment. Therefore, in the third embodiment described below, the same components and steps as those of the navigation apparatus NV according to the first embodiment are denoted by the same member numbers and step numbers, and detailed description thereof is omitted.

  In the third example described below, as an example corresponding to the route search processing according to the embodiment, there are a plurality of destinations instead of via points, and at which stage it is not determined which one is aimed, A case where a route is set by determining whether to go to the ground will be described.

  That is, the route search processing according to the third embodiment in the case corresponding to the first embodiment is similar to the route search processing according to the first embodiment as shown in the flowchart corresponding to FIG. 13 is started based on the instruction operation in FIG. Then, when the route search process is started, the processing unit S first sets the plurality of destinations by acquiring, for example, position information indicating the position of each destination (step S60). At this time, the position information and the like are temporarily recorded in the recording unit 10 after being acquired by the point information acquisition unit 2. Next, the processing unit S executes steps S2 to S6 similar to the route search process according to the first embodiment.

  Thereafter, the branch point route determination unit 5 of the processing unit S revises one or more routes from the front branch point to each destination based on the information indicating the occurrence of traffic jams acquired in step S6 and the map data D. Search is performed (step S61). Thereafter, the processing unit S extracts a route having the lowest movement cost for moving toward each destination from each of the searched new routes (routes via the branch points), and the extracted Information indicating the route is presented (output) using the display 14, for example (step S8). Thereafter, the processing unit S starts guiding the vehicle using the route selected by the operation in the operation unit 13 based on the information indicating the presented route as a guide route.

  In the case corresponding to the second embodiment, the route search process according to the third embodiment can be applied in the same manner as the case shown in FIG.

According to the route search processing according to the third embodiment described above, even when there are a plurality of destinations and it is not determined which destination to go to, the optimum route and the destination are efficiently searched. Can do.
(4) Modification Finally, a modification according to the embodiment will be described.

  First, as a first modification, in the route search processing according to each of the above embodiments, the scheduled arrival time to the determined branch point is designated by, for example, an operation in the operation unit 13, and further, before the designated scheduled arrival time. It may be configured to determine whether or not the vehicle can reach the branch point and to search for a different route (including the branch point) according to the determination result. According to this configuration, a route to the branch point can be searched flexibly and appropriately according to the movement state of the vehicle.

  As a second modification, programs corresponding to the flowcharts shown in FIGS. 4, 5, 7 and 9 are recorded on a recording medium such as an optical disk or a hard disk, or via a network such as the Internet. It is also possible to make the microcomputer or the like function as the processing unit S according to the embodiment by acquiring and reading it out to a general-purpose microcomputer or the like and executing it.

1 position information acquisition means (position information acquisition unit)
2 point information acquisition means (point information acquisition unit)
3 Possible route search means (possible route search part)
4 decision means (decision part)
5 branch point route determination means (branch point route determination unit)
10 recording unit D map data NV navigation device S route search device (processing unit)
A, B Via C Current location N ₁ , N ₂ , N ₃ , N ₄ , N ₅ Node R1, R2, Ram, Rbs Route

Claims (7)

Position information acquisition means for acquiring current position information indicating the current position of the moving body;
Point information acquisition means for acquiring point information about a plurality of points;
Based on the current position information and the point information, possible route search means for searching for a plurality of movable routes passing through the plurality of points;
A determination means for determining a branch point that is between the current position and the plurality of points and can reach any of the plurality of points based on the plurality of movable routes;
When the distance between the current position and the determined branch point is equal to or less than a preset threshold distance due to the movement of the mobile object, a branch point for reaching each point through the branch point A branch point route determining means for determining a passing route;
A route search apparatus comprising: The route search device according to claim 1,
Data acquisition means for acquiring route data including a node;
Extraction means for extracting candidate points that are candidates for the branch point from the nodal points in the route data;
Further comprising
The determining means includes a difference in a selected index indicating a difficulty of selection as a route between each of the plurality of movable routes passing through one candidate point and having different arrival order to the plurality of points. Among the candidate points on the route that is equal to or less than the set threshold index, the candidate point with the smallest total of the selected indicators of a plurality of routes having different arrival orders from the candidate point to the plurality of points, A route search apparatus that determines the branch point. The route search device according to claim 2,
The route search device, wherein the extraction means extracts the nodal point in the route data within a geographical range set in advance with the current position as a reference as the candidate point. In the route search device according to any one of claims 1 to 3,
Scheduled time information acquisition means for acquiring estimated arrival time information indicating the estimated arrival time at the branch point determined by the determination means;
Determining means for determining whether or not the mobile body can reach the branch point before the scheduled arrival time;
Further comprising
The route search device, wherein the branch point route determination unit determines different branch point passage routes according to a determination result by the determination unit. In a route search method executed in a route search device that searches for a route along which a moving body moves,
A position information acquisition step of acquiring current position information indicating a current position of the mobile body;
A point information acquisition step for acquiring point information for a plurality of points;
Based on the current position information and the point information, a possible route search step for searching for a plurality of movable routes passing through the plurality of points;
A determination step of determining a branch point that is between the current position and the plurality of points and can reach any of the plurality of points based on the plurality of movable routes;
When the distance between the current position and the determined branch point is equal to or less than a preset threshold distance due to the movement of the mobile object, a branch point for reaching each point through the branch point A branch point route determination step for determining a passage route;
The route search method characterized by including.   A route search program for causing a computer to function as the route search device according to any one of claims 1 to 4.   7. A recording medium in which the route search program according to claim 6 is recorded so as to be readable by the computer.