JP6614977B2 - Navigation device and route search method - Google Patents

Description

  The present invention relates to a navigation device and a route search method, and is particularly suitable for use in a navigation device and a route search method configured to search for a route to a destination in consideration of the presence or absence of an ETC lane at a toll gate. is there.

  Currently, ETC lanes are provided at many tollgates on toll roads. Thus, a vehicle equipped with an ETC on-board device can pass through the ETC lane, pass through the toll gate non-stop, or perform automatic payment of the toll. Further, when a specific discount condition (for example, day of the week, time zone, etc.) is met, an ETC discount can be applied. In recent years, in view of the widespread use of such ETC, a technique has been devised that enables route guidance considering the use of ETC.

  For example, in Patent Document 1 below, in a navigation system, the presence or absence of an ETC lane is stored for each toll gate, and information corresponding to the presence or absence of an ETC lane at the toll gate (for example, the ETC lane is at the toll gate to be passed from now on). There is disclosed a technology that can provide a user with whether or not there is a gate position of an ETC lane or the like. Patent Document 1 below discloses a technique for calculating a route to a destination with priority given to a toll gate having an ETC lane over a toll gate having no ETC lane. As a result, it is possible to provide the user with a route that does not need to stop at the toll booth and pay the toll directly.

JP 2001-296130 A

  However, most navigation apparatuses do not have a function of searching for a route with priority given to a toll booth with an ETC lane as disclosed in Patent Document 1. For this reason, in such a navigation apparatus, the toll gate closest to the current location is used as a toll gate candidate for a toll road entrance, and a route using the toll road is searched from this toll gate. However, when there is no ETC lane at the toll gate, there has been a problem that the ETC discount cannot be applied. This is because the ETC discount can be applied only when entering the toll road from the ETC lane.

  The present invention has been made to solve such a problem, and even when there is no ETC lane at a toll gate that is a candidate for a toll road entrance, an ETC discount can be applied. Thus, it aims at making it possible to search the route to the destination.

  In order to solve the above-described problems, in the present invention, for the first toll gate that is a candidate for the entrance to the toll road, the presence or absence of an ETC lane is determined, and it is determined that there is no ETC lane at the first toll gate. In this case, after the first toll gate, the presence or absence of the ETC lane is determined for each toll gate until a second toll gate having an ETC lane is first detected. If it is determined that there is no ETC lane at the first toll gate, after searching for a route using the toll road from the first toll gate, and once leaving the toll road at the second toll gate The route to use the toll road is searched again from the second toll gate.

  According to the present invention configured as described above, when the toll road is used from the first toll gate having no ETC lane, the second toll gate having the ETC lane is guided to enter the toll road again. be able to. Accordingly, when the user reenters the toll road at the second toll gate, the application condition for the ETC discount is satisfied, and the ETC discount can be applied to the section after the second toll gate. Therefore, according to the present invention, a route to a destination is searched so that ETC discount can be applied even when there is no ETC lane at a toll booth that is a candidate for a toll road entrance. be able to.

It is a block diagram which shows the function structural example of the navigation apparatus which concerns on one Embodiment of this invention. It is a flowchart which shows an example of the process by the route search apparatus which concerns on one Embodiment of this invention. It is a figure which shows an example of the path | route to the destination searched by a route search part. It is a figure which shows an example of the notification screen by a notification part. It is a figure which shows an example of the notification screen by a notification part.

  Hereinafter, an embodiment of the present invention will be described with reference to the drawings. FIG. 1 is a block diagram illustrating a functional configuration example of a navigation device 100 according to an embodiment of the present invention.

  As shown in FIG. 1, the navigation device 100 of this embodiment includes a map data storage unit 11, a vehicle position detection device 12, a touch panel 13, a display 14, and a speaker 15. In addition, the navigation device 100 has, as its functional configuration, a destination setting unit 101, an ETC lane presence / absence determination unit 102, a toll / free determination unit 103, a route search unit 104, a route guidance unit 105, a notification unit 106, and a selection reception unit 107. It has. The destination setting unit 101, the ETC lane presence / absence determining unit 102, the pay / free determination unit 103, the route searching unit 104, and the selection receiving unit 107 constitute a route searching device 100A.

  Each of the functional blocks 101 to 107 can be configured by any of hardware, DSP (Digital Signal Processor), and software. For example, when configured by software, each of the functional blocks 101 to 107 is actually configured by including a CPU, RAM, ROM, etc. of a computer, and a program stored in a recording medium such as RAM, ROM, hard disk, or semiconductor memory. Is realized by operating.

  The map data storage unit 11 stores map data. The map data includes node information, road link information, facility data, place name data, and the like. The facility data includes toll gate data indicating the presence or absence of an ETC lane for each toll gate on the toll road and toll data for each section of the toll road. The road link information includes the link cost of each link.

  The own vehicle position detection device 12 detects the current position of the vehicle. The own vehicle position detection device 12 includes, for example, a GPS (Global Positioning System) and an autonomous navigation unit.

  The touch panel 13 is an example of an operation unit for performing various operations (for example, a destination setting operation). The touch panel 13 is provided so as to overlap the surface of the display 14.

  The display 14 displays various display screens (for example, various notification screens (see FIGS. 4 and 5)). As the display 14, for example, a liquid crystal display, an organic EL display, or the like is used.

  The destination setting unit 101 sets a destination. For example, the destination setting unit 101 displays a destination setting screen (not shown) on the display 14 and sets a point selected by the user by operating the touch panel 13 from the destination setting screen as a destination.

  The ETC lane presence / absence determination unit 102 is stored in the map data storage unit 11 for the first toll gate when the route search unit 104 identifies the first toll gate that is a candidate for a toll road entrance. The presence or absence of an ETC lane is determined based on toll gate data. Here, if the ETC lane presence / absence determination unit 102 determines that there is no ETC lane at the first toll gate, the first toll gate and the second toll gate having an ETC lane are first detected until the first toll gate is detected. Based on the toll gate data stored in the map data storage unit 11, the presence or absence of an ETC lane is determined for each toll gate. On the other hand, when it is determined that there is an ETC lane at the first toll gate, the ETC lane presence / absence determination unit 102 does not determine the presence or absence of an ETC lane for subsequent toll gates.

  When the ETC lane presence / absence determination unit 102 determines that there is no ETC lane at the first toll gate, the pay / free determination unit 103 first determines the ETC lane from the first toll gate by the ETC lane presence / absence determination unit 102. It is determined whether or not the section to the second toll gate determined to be a toll section based on the charge data stored in the map data storage unit 11.

  For example, if the section from the first toll gate to the second toll gate does not include any toll section, the toll / free determination section 103 determines that the section is a free section. On the other hand, when the section from the first toll gate to the second toll gate includes one or more toll sections, the toll / free determination unit 103 determines that the section is a toll section.

  The notification unit 106 displays a predetermined notification screen (see FIG. 4) on the display 14 when the pay / free determination unit 103 determines that the section from the first toll gate to the second toll gate is a toll section. By displaying, ETC discount is not applicable unless you use the toll road from the second toll gate, and you entered the second toll gate using the toll road from the first toll gate The user is notified of the charge difference and the time difference between the case and the use of the toll road from the second toll gate. This notification screen allows the user to select either a route that re-enters from the second toll gate using the toll road from the first toll gate or a route that uses the toll road from the second toll gate. It has the operation button.

  In the present embodiment, the notification unit 106 notifies the user when the pay / free determination unit 103 determines that the section from the first toll gate to the second toll gate is a free section. In this case, the user may be notified that the ETC discount is not applicable unless the toll road is reentered at the second tollgate.

  The selection receiving unit 107 is displayed on the notification screen notified by the notification unit 106 when the pay / free determination unit 103 determines that the section from the first toll gate to the second toll gate is a toll section. The user selects whether or not to use the toll road from the first toll gate through the operation of the operating button.

  The route search unit 104 searches for a route from the current position of the vehicle detected by the vehicle position detection device 12 to the destination set by the destination setting unit 101. Here, the route search unit 104 can use a general route search method. For example, the route search unit 104 follows the link connected to the current tip node (initially, the node at the current position of the vehicle) and extends the search branch to the node to which the link is connected. Here, when a plurality of links are connected to the current tip node, the search branch is extended to each node one ahead of each link, and the link costs are accumulated. The route search unit 104 repeats this until the destination set by the destination setting unit 101, and in the process, appropriately excludes a route having a high link cost from candidates, thereby providing an optimum route (a route having the lowest link cost). Explore.

  At this time, the route search unit 104 identifies the toll gate searched as a candidate for the entrance of the toll road (when the node to which the search branch is extended corresponds to the toll gate node) as the first toll gate. In addition, when the ETC lane presence / absence determination unit 102 determines that there is no ETC lane at the first toll gate, the route search unit 104 determines that there is an ETC lane at the beginning after the first toll gate. The toll gate determined by the unit 102 is identified as the second toll gate.

  Then, when the ETC lane presence / absence determination unit 102 determines that there is no ETC lane at the first toll gate, the route search unit 104 causes the toll / free determination unit 103 to change the first toll gate from the first toll gate. If it is determined that the section is a free section, use the toll road from the first toll gate, exit the toll road at the second toll gate, and then pay again from the second toll gate Search for routes using roads.

  On the other hand, the route search unit 104 determines that the ETC lane presence / absence determination unit 102 determines that there is no ETC lane at the first toll gate, and the toll / free determination unit 103 changes the first toll gate from the first toll gate to the second toll gate. When it is determined that the section is a toll section, when the selection receiving unit 107 receives a selection to use the toll road from the first toll gate, the second toll road is used from the first toll gate using the toll road. After leaving the toll road at the toll booth, the route to use the toll road is searched again from the second toll booth.

  On the contrary, the route search unit 104 determines that the ETC lane presence / absence determination unit 102 determines that there is no ETC lane at the first toll gate, and the pay / free determination unit 103 determines from the first toll gate to the second toll gate. If it is determined that the section is a toll section and the selection accepting unit 107 accepts a selection not to use the toll road from the first toll gate, the second toll gate uses the general road to Search for a route using the toll road from the toll booth.

  The route guidance unit 105 guides the route searched by the route search unit 104 to the destination set by the destination setting unit 101. Specifically, when the route guidance unit 105 provides route guidance, a route guidance screen is displayed on the display 14 and a route guidance voice is output from the speaker 15.

[Example of Processing by Route Searching Device 100A]
FIG. 2 is a flowchart showing an example of processing by the route search apparatus 100A according to an embodiment of the present invention. The process shown in FIG. 2 starts when, for example, the destination setting unit 101 sets a destination and the user instructs execution of the route search process.

  First, the route search unit 104 extends the search branch from the current tip node to the next node (step S202). Here, when a plurality of links are connected to the current tip node, the search branch is extended to each node one ahead of each link, and the link costs are accumulated. Then, the route search unit 104 determines whether there is a toll road entrance node among the extended search destination nodes (step S204). Here, when the route search unit 104 determines that there is no node at the entrance of the toll road (step S204: No), the route search unit 104 executes the processing after step S202 again.

  On the other hand, when the route search unit 104 determines that there is a node at the entrance of the toll road (step S204: Yes), the ETC lane presence / absence determination unit 102 determines the presence / absence of an ETC lane for the node at the entrance of the toll road. (Step S206). If the ETC lane presence / absence determining unit 102 determines that there is an ETC lane at the entrance node of the toll road (step S206: Yes), the route search device 100A advances the process to step S220.

  On the other hand, when the ETC lane presence / absence determination unit 102 determines that there is no ETC lane at the entrance node of the toll road (step S206: No), the route search unit 104 sequentially extends the search branch on the toll road and While searching for a node, each time a toll gate node is searched, the ETC lane presence / absence determining unit 102 determines whether there is an ETC lane, so that the toll gate node first determined to have an ETC lane Is identified as the node of the second toll gate (step S208).

  Then, the toll / free determination unit 103 determines the section from the toll road entry node (first toll gate node) identified in step S204 to the second toll gate node identified in step S208. Then, it is determined whether or not it is a toll section (step S210). Here, when the toll / free determination unit 103 determines that the section from the toll road entrance node to the second toll gate node is not a toll section (step S210: No), the route search unit 104 The exit of No. 2 toll booth is set as a transit point (step S216). As a result, a route for temporarily leaving the toll road is searched at the second toll gate. Then, the route search device 100A advances the process to step S220.

  On the other hand, when the pay / free determination unit 103 determines that the section from the first toll gate node to the second toll gate node is a toll section (step S210: Yes), the notification section 106 performs a predetermined process. By displaying the notification screen (see Fig. 4) on the display 14, if the toll road is not used from the second toll gate, the ETC discount is not applicable, and the toll road is used from the first toll gate Then, the user is notified of the charge difference and the time difference between the case of reentering from the second toll booth and the case of using the toll road from the second toll booth. (Step S212).

  And it is judged whether selection reception part 107 received selection which uses a toll road from the 1st toll gate through operation of the operation button currently displayed on the notice screen notified by notice part 106 (Step). S214). Here, when the selection receiving unit 107 determines that the selection using the toll road has been received from the first toll gate (step S214: Yes), the route search unit 104 uses the exit of the second toll gate as a waypoint. Setting is made (step S216). As a result, a route for temporarily leaving the toll road is searched at the second toll gate. Then, the route search device 100A advances the process to step S220.

  On the other hand, when the selection receiving unit 107 determines that a selection not using the toll road has been received from the first toll gate (step S214: No), the section of the toll road from the first toll gate to the second toll gate is determined. The link cost is increased (step S218). As a result, the route using the general road to the second toll gate is preferentially searched. Then, the route search device 100A advances the process to step S220.

  In step S220, the route search unit 104 extends the search branch from the current tip node to the next node. Then, the route search unit 104 determines whether or not the search for the route to the destination has been completed (step S222). Here, when the route search unit 104 determines that the search for the route to the destination has not been completed (step S222: No), the route search unit 104 executes the processing after step S220 again.

  On the other hand, when the route search unit 104 determines that the search for the route to the destination is completed (step S222: Yes), the route search device 100A ends the series of processes shown in FIG.

[Example of route to destination]
FIG. 3 is a diagram illustrating an example of a route to the destination searched by the route search unit 104. 3A to 3C, the toll gate A is the toll gate nearest to the current position of the vehicle and is the first toll gate that is a candidate for a toll road entrance. There is no ETC lane at the first toll gate. The toll gate B is a toll gate after the toll gate A, and is a second toll gate having an ETC lane first. The C toll gate is the toll gate nearest to the destination G.

  FIG. 3A shows an example of a route searched by the route search unit 104 when the section from the A toll station having no ETC lane to the B toll station having the ETC lane is a free section. In this case, as shown in FIG. 3 (a), the route search unit 104 uses the toll road from the A toll gate, exits the toll road at the B toll gate, and then from the B toll gate to the C toll gate. Search for the route using the toll road again. As a result, the ETC discount can be applied to the section from the B toll booth to the C toll booth.

  FIG. 3B shows a case where the section from the A toll booth without the ETC lane to the B toll booth with the ETC lane is a toll section, and the user makes a selection to use the toll road from the A toll gate. 4 shows an example of a route searched by the route search unit 104. In this case, as shown in FIG. 3 (b), the route search unit 104 uses the toll road from the A toll gate, exits the toll road at the B toll gate, and then from the B toll gate to the C toll gate. Search for the route using the toll road again. As a result, the ETC discount can be applied to the section from the B toll booth to the C toll booth.

  FIG. 3C shows a case where the section from the A toll booth without the ETC lane to the B toll booth with the ETC lane is a toll section, and the user makes a selection not to use the toll road from the A toll gate. 4 shows an example of a route searched by the route search unit 104. In this case, as shown in FIG. 3C, the route searching unit 104 searches for a route using the toll road from the B toll to the C toll using the general road to the B toll. Also in this case, the ETC discount can be applied to the section from the B toll booth to the C toll booth.

  In the example of FIG. 3, if there is an ETC lane at the A toll booth, the route search unit 104 searches for a route using the toll road from the A toll booth to the C toll booth. In this case, the ETC discount can be applied to the section from the A toll booth to the C toll booth.

[Example of notification screen]
FIG. 4 is a diagram illustrating an example of a notification screen by the notification unit 106. The notification screen 400 shown in FIG. 4 is displayed when the pay / free determination unit 103 determines that the section from the A toll gate (first toll gate) to the B toll gate (second toll gate) is a toll section ( That is, in FIG. 3B and FIG. 3C, the notification unit 106 displays the screen on the display 14. The notification screen 400 shows that the ETC discount is not applicable unless a toll road is used from the B toll gate. Further, the notification screen 400 shows a charge difference and a time difference between the case where the toll road is used from the A toll gate and the entrance to the B toll gate is entered again and the case where the toll road is used from the B toll gate.

  As shown in FIG. 4, the notification screen 400 is provided with a “from Tollgate A” button 402 and a “from Tollgate B” button 404. The “From Tollgate” button 402 is an operation button for causing the user to select a route to reenter from the second tollgate using the toll road from the first tollgate. The “From toll gate” button 404 is an operation button for causing the user to select a route using the toll road from the second toll gate.

  When the “From A Tollgate” button 402 is pressed on the notification screen 400 (that is, in the case of FIG. 3B), the selection accepting unit 107 accepts a selection to use the toll road from the first toll gate. Then, the route search unit 104 uses the toll road from the A toll gate, and once exits from the toll road at the B toll gate, then searches for a route using the toll road again from the B toll gate.

  On the other hand, when the “from toll booth” button 404 is pressed on the notification screen 400 (that is, in the case of FIG. 3C), the selection receiving unit 107 receives a selection from the A toll booth not using the toll road. Then, the route searching unit 104 searches for a route using the toll road from the B toll gate using the general road to the B toll gate.

  As described above, according to an embodiment of the present invention, when a toll road is used from the first toll gate having no ETC lane, the toll road is re-entered from the second toll gate having the ETC lane. Can be guided to. Accordingly, when the user reenters the toll road at the second toll gate, the application condition for the ETC discount is satisfied, and the ETC discount can be applied to the section after the second toll gate. Therefore, according to one embodiment of the present invention, even if there is no ETC lane at a toll gate that is a candidate for a toll road entrance, an ETC discount can be applied. The route can be searched.

  In the above embodiment, the notification unit 106 may perform notification regarding application of ETC discount in addition to the notification described in the embodiment (FIG. 4). For example, when a route search for reentering a toll road from the second toll gate without notifying the user is performed (for example, the section from the first toll gate to the second toll gate is a free section) If it is determined), simply presenting the outline of the searched route (relatively wide map screen) to the user, the route to re-enter the toll road at the second toll gate has been searched. The user may not be able to grasp.

  In this case, the notification unit 106 displays the notification screen 500 shown in FIG. 5 on the display 14 immediately before (or immediately after) the vehicle enters the A toll gate (first toll gate) while the vehicle is traveling. If you use the toll road from the A toll booth, you must leave the toll road at the B toll booth (second toll booth) and then use the toll road again from the B toll booth. The user may be notified that the ETC discount is not applicable. As a result, even if the user cannot grasp at the time of the route search that the toll road needs to be reentered at the second toll gate, immediately before or immediately after the vehicle enters the A toll gate. It becomes possible to grasp.

  In the above embodiment, as described with reference to FIG. 2, in addition to searching for a route to the destination while extending the search branch, a route that considers the application of ETC discount is searched. However, the present invention is not limited to this. For example, after temporarily searching for a temporary route to the destination, a route that considers the application of ETC discount may be searched using the temporary route as a reference.

  For example, if the searched temporary route does not include a toll road section, the temporary route is applied as it is as the main route. On the other hand, if the searched temporary route includes a section of a toll road, the toll gate set as the entrance of the section is set as the first toll gate, and the ETC lane is in the first toll gate. The ETC lane presence / absence determining unit 102 determines whether or not there is.

  Here, when the ETC lane presence / absence determination unit 102 determines that there is an ETC lane at the first toll gate, the temporary route is applied as it is as the main route. On the other hand, when the ETC lane presence / absence determination unit 102 determines that there is no ETC lane at the first toll gate, the toll gate in which the route search unit 104 first determines that there is an ETC lane after the first toll gate. Are identified as nodes of the second toll gate.

  When the section from the first toll gate to the second toll gate is determined as the free section by the toll / free determination section 103, the route search section 104 uses the toll road from the first toll gate. Then, the route that re-enters the toll road at the second tollgate is re-searched and determined as the main route.

  On the other hand, when the section from the first toll gate to the second toll gate is determined to be a toll section by the toll / free determination section 103, the notification section 106 displays a predetermined notification screen (see FIG. 4) on the display 14 To the route to reenter the toll road at the second toll gate using the toll road from the first toll gate or the second toll gate according to the user's selection on the notification screen The route using the toll road from the second toll gate is re-searched using the road, and this is determined as the main route.

  In the above embodiment, when the first toll gate to the second toll gate is a toll section, the route search unit 104 uses the toll road from the first toll gate according to the user's selection. Alternatively, a route using the toll road is searched from the second toll gate using a general road to the second toll gate. Instead, in the case of a toll section from the first toll gate to the second toll gate, the route search unit 104 automatically (that is, without allowing the user to select) a general road to the second toll gate. You may make it search for the path | route which uses a toll road from the said 2nd toll booth using.

  Alternatively, in the case of a toll section from the first toll gate to the second toll gate, the route search unit 104 searches for a route using the toll road from the first toll gate or a general road to the second toll gate. Whether to search for a route using the toll road from the second toll gate using the second toll may be automatically determined based on a predetermined condition. For example, if the route search unit 104 determines that a general road does not run parallel to the toll road from the first toll gate to the second toll gate, the route using the toll road from the first toll gate If it is determined that the general road is running parallel to the toll road up to the second toll gate, a route using the toll road may be searched from the second toll gate.

  In addition, each of the above-described embodiments is merely an example of implementation in carrying out the present invention, and the technical scope of the present invention should not be construed in a limited manner. That is, the present invention can be implemented in various forms without departing from the gist or the main features thereof.

DESCRIPTION OF SYMBOLS 11 Map data memory | storage part 12 Own vehicle position detection apparatus 13 Touch panel 14 Display 15 Speaker 100 Navigation apparatus 100A Route search device 101 Destination setting part 102 ETC lane presence / absence determination part 103 Paid / free determination part 104 Route search part 105 Route guidance part 106 Notification unit 107 Selection reception unit

Claims (6)

A navigation device that searches and guides a route to a destination,
For the first toll gate, which is a candidate for a toll road entrance, the presence or absence of an ETC lane is determined, and if it is determined that there is no ETC lane at the first toll gate, An ETC lane presence / absence determining unit that determines the presence / absence of an ETC lane for each toll gate until a second toll gate having an ETC lane is first detected
When the ETC lane presence / absence determining unit determines that there is no ETC lane at the first toll gate, the toll road is used from the first toll gate, and from the toll road at the second toll gate. A navigation apparatus, comprising: a route search unit that searches for a first route that uses the toll road again from the second toll gate after exiting. A pay / free determination unit that determines whether the first toll to the second toll is a toll section of the toll road;
The route search unit
Instead of searching for the first route uniformly when the ETC lane presence / absence determining unit determines that there is no ETC lane at the first toll gate,
Said that the to the second tollgate from said first tollgate in the case where it is determined that ETC lane is not in the first tollgate by ETC lane determining unit is paid section of the toll road If it is further determined by the pay / free determination section, go to the second toll booth by using a general road without the use of the first tollgate and the toll road, the from the second tollgate The navigation device according to claim 1 , wherein a route selected by a user is searched for between a second route using a toll road and the first route . A pay / free determination unit that determines whether the first toll to the second toll is a toll section of the toll road;
The route search unit
Instead of searching for the first route uniformly when the ETC lane presence / absence determining unit determines that there is no ETC lane at the first toll gate,
Said that the to the second tollgate from said first tollgate in the case where it is determined that ETC lane is not in the first tollgate by ETC lane determining unit is paid section of the toll road If further determined by the toll / free determination unit, determine whether or not a general road is running along the toll road from the first toll gate to the second toll gate,
When it is determined that the general road is parallel to the toll road from the first toll gate to the second toll gate, the general road is not used without using the first toll gate and the toll road. Go to the second toll booth and search for a second route using the toll road from the second toll booth ,
When the open road on the toll road from the first tollgate to said second tollgate is determined not to run in parallel, to claim 1, characterized in that searching the first route The navigation device described. The route search unit
When searching for the first route, by setting the exit of the second toll gate as a transit point, the second toll gate once exits the toll road at the second toll gate. The navigation device according to any one of claims 1 to 3, wherein a route that uses the toll road is searched again. If the first route is used, ETC discount is applied unless the toll road is used again from the second toll gate after leaving the toll road at the second toll gate. The navigation device according to claim 3, further comprising a notification unit that notifies the user that the vehicle is outside immediately before or after the vehicle enters the first toll gate. A route search method by a navigation device that searches and guides a route to a destination,
When the ETC lane presence / absence determination unit of the navigation device determines the presence / absence of an ETC lane for the first toll gate, which is a candidate for a toll road entrance, and determines that there is no ETC lane at the first toll gate And after the first toll station, an ETC lane presence / absence determination step for determining the presence / absence of an ETC lane for each toll station until a second toll station having an ETC lane is detected for the first time;
When the route search unit of the navigation device determines that there is no ETC lane at the first toll gate by the ETC lane presence / absence determination unit, the toll road is used from the first toll gate, and the second toll And a route search step of searching for a route using the toll road again from the second toll gate after exiting the toll road at the toll gate.