本発明は、出発地から目的地までを結ぶ経路を自動探索し、コストが最も小さくなる誘導経路を案内する誘導経路案内機能を備えたナビゲーション装置に関するものである。 The present invention relates to a navigation device having a guidance route guidance function for automatically searching for a route connecting from a departure point to a destination and guiding a guidance route with the lowest cost.
従来、目的地までの誘導経路を案内する誘導経路案内機能を備えたナビゲーション装置（経路探索装置）では、特許文献１に開示された経路探索装置のように、誘導経路を探索するにあたり、中継地点等にてＵターンする経路が含まれない誘導経路を案内する経路探索装置が広く知られている。 Conventionally, in a navigation device (route search device) having a guide route guidance function for guiding a guide route to a destination, as in the route search device disclosed in Patent Document 1, a relay point is used for searching for a guide route. A route search device that guides a guidance route that does not include a U-turn route is widely known.
例えば、現在地（出発地）から複数の目的地（経由地、通過地点などの中継地）がある状態では、図５に示すように、各経由地（通過地点ともいう）までの経路、具体的には、出発地から経由地１までの第１経路、経由地１から経由地２までの第２経路、経由地２から経由地３までの第３経路、経由地３から経由地４までの第４経路、経由地４から経由地５までの第５経路、経由地５から目的地までの第６経路、の各経路がスムーズに接続するように経路探索が行われる。ここで「スムーズに接続する」とは、それぞれの経路間を「Ｕターン」させることなく自車両が走行可能であることを意味する。このように、経由地を挟んで複数の経路から誘導経路が構成される場合であっても、各経路を繋ぐ箇所（各経路を接続する地点、経由地付近）にてＵターンを発生させないようにしているため、ユーザ（運転者）が走行しやすい誘導経路を案内する（提供する）ことができるようになっている。 For example, in the state where there are a plurality of destinations (routes such as waypoints and passing points) from the current location (departure point), as shown in FIG. 5, the route to each waypoint (also called a passing point), specifically The first route from the departure point to the transit point 1, the second route from the transit point 1 to the transit point 2, the third route from the transit point 2 to the transit point 3, and the transit point 3 to the transit point 4 The route search is performed so that the fourth route, the fifth route from the waypoint 4 to the waypoint 5, and the sixth route from the waypoint 5 to the destination are smoothly connected. Here, “smoothly connect” means that the host vehicle can travel without making a “U-turn” between the respective routes. In this way, even when a guidance route is composed of a plurality of routes across a transit point, a U-turn should not be generated at a place connecting the routes (points connecting the routes, in the vicinity of the transit point). Therefore, it is possible to guide (provide) a guidance route that is easy for the user (driver) to travel.
しかしながら、上記特許文献１に開示されたように、各経路を繋ぐ箇所にてＵターンを発生させる経路を誘導経路としては案内しないようにするナビゲーション装置（以下、「従来のナビゲーション装置」という）では、以下のような問題が発生する。 However, as disclosed in the above-mentioned Patent Document 1, in a navigation device (hereinafter referred to as “conventional navigation device”) that does not guide a route that generates a U-turn at a place connecting the routes as a guide route. The following problems occur.
例えば、図６に示すような、従来のナビゲーション装置により自車両ＡＡに対する誘導経路が案内されている地図画面において、経由地Ｐを通過して目的地に向かう誘導経路として、「ルート４→ルート５→経由地Ｐ→・・・→目的地」が案内されている場合について考える。 For example, as shown in FIG. 6, on a map screen in which a guidance route to the host vehicle AA is guided by a conventional navigation device, a route “route 4 → route 5” is assumed as a guidance route that passes through the waypoint P to the destination. Consider the case where “→ route P →... → destination” is guided.
ここで、図７（ａ）に示すように、自車両ＡＡが案内されている誘導経路から外れてしまったとする（この場合は、ルート４に入らなかったとする）と、上記従来のナビゲーション装置において誘導経路が再探索される。 Here, as shown in FIG. 7 (a), if the host vehicle AA deviates from the guided route (in this case, it does not enter the route 4), The guidance route is re-searched.
そして、上記従来のナビゲーション装置では、経由地Ｐを通過するとともに、経由地Ｐにおいて自車両ＡＡをＵターンさせない経路が新たな誘導経路として決定されることとなるため、図７（ｂ）に示すように、「ルート１→ルート２→ルート３→ルート４→ルート５→経由地Ｐ→・・・→目的地」という誘導経路が案内される。 In the conventional navigation device, a route that passes through the transit point P and does not make a U-turn of the host vehicle AA at the transit point P is determined as a new guidance route. In this way, the guidance route “Route 1 → Route 2 → Route 3 → Route 4 → Route 5 → Route P →... → Destination” is guided.
このように、経由地を挟んで各経路がスムーズに接続するように経路探索を行う場合には、図７（ｂ）に示すように、案内される誘導経路が遠回りとなる経路となる可能性があるため、ユーザにとって好ましくないという問題がある。なお、図８（ａ）では、図７（ｂ）で示した再探索した後に案内される誘導経路についての概要を示している。 In this way, when route search is performed so that each route is smoothly connected across the waypoint, as shown in FIG. 7B, the guided route to be guided may become a detour route. Therefore, there is a problem that it is not preferable for the user. FIG. 8A shows an outline of the guidance route guided after the re-search shown in FIG. 7B.
また、各経路を繋ぐ箇所をスムーズに接続させる点を考慮しないで第１経路について再探索を行うようにすると、図８（ｂ）に示すように、経由地１においてＵターンが発生することがある。すなわち、案内する誘導経路の質（以下、「ルート品位」という）は、ユーザにとってベストなものであるとはいいがたいものであった。言い換えれば、ユーザにとってのベストな誘導経路が案内されている（提供されている）とはいえないものであった。 Further, if a re-search is performed for the first route without considering the point where the points connecting the routes are smoothly connected, a U-turn may occur at the waypoint 1 as shown in FIG. is there. That is, the quality of the guidance route to be guided (hereinafter referred to as “route quality”) is not the best for the user. In other words, the best guidance route for the user is not guided (provided).
そこで、経由地１におけるＵターンの発生を回避するために、経由地１でスムーズに接続させながら、第２経路についても探索すると、図８（ｃ）に示すように、経由地１周辺（第１経路および第２経路まで）におけるルート品位は担保することができるが、この場合には、第２経路も再探索することとなるため、新たに誘導経路として決定した第２経路と、その先の第３経路とがスムーズに接続しない不具合が発生する可能性が考えられる。 Therefore, in order to avoid the occurrence of a U-turn at the stop 1, when searching for the second route while smoothly connecting at the stop 1, as shown in FIG. The route quality in the first route and the second route) can be ensured. In this case, however, the second route is also searched again. There is a possibility that a problem that the third route is not smoothly connected occurs.
さらに、この点を解決しようとして、第３経路についても再探索するようにしていくと、結果的には、図８（ｄ）に示すように、全ての経路を再探索する必要も生じ得ることとなるため、誘導経路の再探索に係る処理時間や誘導経路の再探索に係る処理負担が多大なものとなってしまう。 Furthermore, if the third route is re-searched in an attempt to solve this point, it may be necessary to re-search all routes as shown in FIG. 8D. Therefore, the processing time related to the re-search for the guidance route and the processing burden related to the re-search for the guidance route become large.
本発明は、上記課題を解決することを目的とし、経由地を挟んで複数の経路から構成された誘導経路を再探索する場合において、これら各経路がスムーズに接続された誘導経路を案内することを可能にするとともに、ルート品位を担保することのできるナビゲーション装置を提供することを目的とする。 The present invention aims to solve the above-described problems, and in re-searching a guidance route composed of a plurality of routes across a waypoint, guides a guidance route in which these routes are smoothly connected. An object of the present invention is to provide a navigation device capable of ensuring the route quality.
上記の目的を達成するために、本発明のナビゲーション装置は、出発地から目的地までの経路の途上にある経由地を少なくとも設定することが可能であって、前記出発地から前記目的地までの経路において、前記出発地から最も近い第１経由地、次に近い第２経由地、・・・、最も遠い第Ｎ経由地（Ｎには自然数が入る）が設定される場合には、前記出発地から前記第１経由地までを第１経路として、この第１経由地から前記第２経由地までを第２経路として、・・・、第Ｎ−１経由地から前記第Ｎ経由地までを第Ｎ経路、この第Ｎ経路から前記目的地までの経路を第Ｎ＋１経路として、これら各経路についてのコスト最小ルートを探索するとともに、これら複数の経路を繋げて誘導経路を決定する誘導経路探索部と、前記誘導経路探索部により決定された前記誘導経路を案内する誘導経路案内部と、を備えたナビゲーション装置であって、前記誘導経路探索部は、自車両が前記第Ｎ経路において、前記誘導経路案内部により案内されている誘導経路から外れた場合、当該第Ｎ経路における第Ｎ経由地までのコスト最小ルートを探索するともに、このコスト最小ルートを通って前記第Ｎ経由地を通過した前記自車両が当該第Ｎ経由地にてＵターンをせずに辿る経路上であって、前記第Ｎ＋１経路において合流することの可能な合流点までのルートを探索し、この探索結果に基づいて、前記自車両が外れた地点から前記第Ｎ＋１経路に合流するまでの新たな誘導経路を決定する、ことを特徴としている。 In order to achieve the above object, the navigation device of the present invention can set at least a waypoint on the route from the departure place to the destination, and is provided between the departure place and the destination. In the route, when the first waypoint closest to the departure point, the second route point next to the next point,..., The furthest Nth route (N is a natural number) is set. The first route from the ground to the first route, the second route from the first route to the second route, ..., from the N-1 route to the Nth route An N-th route, a route from the N-th route to the destination as an N + 1-th route is searched for a minimum cost route for each of these routes, and a guide route search unit that determines a guide route by connecting these multiple routes And the guidance route search unit A guidance route guidance unit for guiding the determined guidance route, wherein the guidance route search unit is configured such that the vehicle is guided by the guidance route guidance unit in the Nth route. When the vehicle deviates from the guidance route, a search is made for a minimum cost route to the Nth route point on the Nth route, and the own vehicle that has passed through the Nth route point through the minimum cost route passes the Nth route. A route on the ground without making a U-turn and searching for a route to a junction where the N + 1-th route can join, and based on the search result, a point where the host vehicle has come off A new guidance route from the first to the N + 1th route is determined.
さらに、上記構成において、前記誘導経路探索部は、前記合流点を探索する場合、前記コスト最小ルートを通って前記第Ｎ経由地を通過した前記自車両が当該第Ｎ経由地にてＵターンをせずに辿る経路上から、前記第Ｎ＋１経路に最も早期に合流することの可能な地点を合流点として決定する、ことを特徴としている。 Further, in the above configuration, when the guidance route search unit searches for the junction, the host vehicle that has passed through the Nth route through the minimum cost route makes a U-turn at the Nth route. A point that can join the N + 1th route at the earliest point is determined as a joining point from a route that is not followed.
さらに、上記構成において、前記誘導経路探索部により探索される経路が記憶された地図データを記憶する地図データ記憶部をさらに備え、この地図データ記憶部に記憶される前記地図データは、主要な道路のみが記憶された第１階層と、この主要な道路に合流する中規模の道路までが記憶された第２階層と、この中規模な道路に合流する微細な道路までが記憶された第３階層と、の複数の階層から構成されているとともに、前記誘導経路探索部は、前記第Ｎ経路において、前記自車両が当該誘導経路から外れた場合には、前記地図データにおける階層を切替えることにより前記合流点を探索することが可能である、ことを特徴としている。 Further, in the above configuration, the map data storage unit further stores map data in which the route searched by the guidance route search unit is stored, and the map data stored in the map data storage unit is a main road. The first hierarchy in which only the first road is stored, the second hierarchy in which up to the medium-sized road that merges with the main road is stored, and the third hierarchy in which the minute road that merges with the middle-scale road is stored. And the guidance route search unit switches the hierarchy in the map data when the host vehicle deviates from the guidance route on the Nth route. It is possible to search for a junction.
本発明によれば、経由地を挟んで複数の経路から構成された誘導経路を再探索する場合において、これら各経路がスムーズに接続された誘導経路を案内することを可能にするとともに、ルート品位を担保することのできるナビゲーション装置を提供することができる。 According to the present invention, when re-searching for a guidance route composed of a plurality of routes across a waypoint, it is possible to guide a guidance route in which each of these routes is smoothly connected, and route quality. It is possible to provide a navigation device that can guarantee the above.
次に、本発明の実施形態について図面を参照して詳細に説明する。図１は、本発明の位一実施形態であるナビゲーション装置１００の構成例を示すブロック図である。図１において、ＤＶＤ−ＲＯＭ２００は、ＤＶＤ−ＲＯＭ等の記録媒体であり、地図表示や経路探索等に必要な各種の地図データを記憶している。 Next, embodiments of the present invention will be described in detail with reference to the drawings. FIG. 1 is a block diagram illustrating a configuration example of a navigation device 100 according to a preferred embodiment of the present invention. In FIG. 1, a DVD-ROM 200 is a recording medium such as a DVD-ROM, and stores various types of map data necessary for map display, route search, and the like.
ＤＶＤ−ＲＯＭ２００に記録された地図データは、道路網の情報量の差異に基づいて３つのレベルに階層化された構造をしている。３つのレベルに階層化された地図データには、細街路から高速道路まで全ての道路を格納したレベル０といわれる道路メッシュ、主に市道以上の道路を格納しているレベル１といわれる道路メッシュ、高速道路や有料道路といった道路を格納しているレベル２といわれる道路メッシュがそれぞれ区別されて格納されている。この場合、レベルが上がるにつれて、道路網の情報量が少なく粗い地図データとなっている。各レベルの地図データには、地図表示に必要な描画ユニットのデータの他に、マップマッチングや経路探索等の各種の処理に必要な道路ユニットのデータが含まれている。 The map data recorded on the DVD-ROM 200 has a structure hierarchized into three levels based on the difference in the information amount of the road network. The map data layered in three levels includes a road mesh called level 0 that stores all roads from narrow streets to expressways, and a road mesh called level 1 that mainly stores roads above city roads. Road meshes called level 2 storing roads such as expressways and toll roads are stored separately. In this case, as the level increases, the amount of information on the road network is small and the map data is rough. The map data at each level includes road unit data necessary for various processes such as map matching and route search, in addition to drawing unit data necessary for map display.
道路ユニットは、道路を細かく分割して複数のベクトルのつながりで表したときの個々のベクトルに相当する道路リンクに関するリンク情報と、個々の道路リンクの両端点に相当するノードに関するノード情報とを含んでいる。ノード情報には、ノードを一意に特定するノードＩＤ、ノードの位置（経緯度）、ノードに接続される道路リンク（リンクＩＤ）および、複数の道路リンクの端点に相当するノード（分岐点）であるか否かを示すフラグの両端に接続されるノード（ノードＩＤ）、リンクコスト、道路種別（一般道路または高速道路）および道路属性などが含まれる。なお、ここでは、地図データを記憶する記憶媒体としてＤＶＤ−ＲＯＭ２００を用いているが、ＣＤ−ＲＯＭ、ハードディスク、半導体メモリ等の他の記憶媒体を用いてもよい。 The road unit includes link information on road links corresponding to individual vectors when the road is divided into a plurality of vectors and node information on nodes corresponding to both end points of each road link. It is out. The node information includes a node ID that uniquely identifies the node, a node position (latitude and longitude), a road link (link ID) connected to the node, and a node (branch point) corresponding to the end points of a plurality of road links. A node (node ID), link cost, road type (general road or highway), road attribute, and the like connected to both ends of a flag indicating whether or not there is included. Here, the DVD-ROM 200 is used as a storage medium for storing the map data, but other storage media such as a CD-ROM, a hard disk, and a semiconductor memory may be used.
車両位置検出部１０は、車両の現在位置を所定間隔に検出するものであり、自立航法センサ、ＧＰＳ受信機、位置計算用ＣＰＵ等で構成されている。
自立航法センサは、所定走行距離ごとに１個のパルスを出力して車両の移動距離を検出する車速センサ（距離センサ）と、車両の回転角度（移動方位）を検出する振動ジャイロ等の角速度センサ（相対方位センサ）とを含む。自立航法センサは、これらの車速センサおよび角速度センサによって車両の相対位置および方位を検出する。
位置計算用ＣＰＵは、自立航法センサから出力される自車両の相対的な位置および方位のデータに基づいて、絶対的な自車位置（推定車両位置）および車両方位を計算する。
また、ＧＰＳ受信機は、複数のＧＰＳ衛星から送られてくる電波をＧＰＳアンテナで受信して、３次元測位処理あるいは２次元測位処理を行って車両の絶対位置および方位を計算する（なお、車両位置は、現時点における自車位置と１サンプリング時間ΔＴ前の自車位置とに基づいて計算する）。The vehicle position detection unit 10 detects the current position of the vehicle at predetermined intervals, and includes a self-contained navigation sensor, a GPS receiver, a position calculation CPU, and the like.
The self-contained navigation sensor includes a vehicle speed sensor (distance sensor) that outputs a single pulse for each predetermined travel distance to detect the moving distance of the vehicle, and an angular velocity sensor such as a vibration gyro that detects the rotation angle (moving direction) of the vehicle. (Relative orientation sensor). The self-contained navigation sensor detects the relative position and direction of the vehicle using these vehicle speed sensor and angular velocity sensor.
The position calculation CPU calculates the absolute own vehicle position (estimated vehicle position) and vehicle direction based on the relative position and direction data of the own vehicle output from the self-contained navigation sensor.
The GPS receiver receives radio waves transmitted from a plurality of GPS satellites with a GPS antenna and performs a three-dimensional positioning process or a two-dimensional positioning process to calculate the absolute position and direction of the vehicle (in addition, the vehicle The position is calculated on the basis of the current vehicle position and the current vehicle position one sampling time ΔT before).
ＤＶＤ−ＲＯＭ制御部２０は、ＤＶＤ−ＲＯＭ２００から地図データの読み出しを制御する。
地図データ記憶部３０は、ＤＶＤ−ＲＯＭ制御部２０の制御によってＤＶＤ−ＲＯＭ２００から読み出された地図データを一時的に格納する。すなわち、ＤＶＤ−ＲＯＭ制御部２０は、車両位置検出部１０から自車両の現在位置（車両現在位置）の情報を入力し、その車両現在位置を含む所定範囲の地図データの読み出し指示を出力することにより、地図表示や誘導経路の探索に必要な地図データをＤＶＤ−ＲＯＭ２００から読み出して地図データ記憶部３０に格納する。The DVD-ROM control unit 20 controls reading of map data from the DVD-ROM 200.
The map data storage unit 30 temporarily stores map data read from the DVD-ROM 200 under the control of the DVD-ROM control unit 20. That is, the DVD-ROM control unit 20 inputs information on the current position (vehicle current position) of the host vehicle from the vehicle position detection unit 10 and outputs an instruction to read out a predetermined range of map data including the vehicle current position. Thus, the map data necessary for map display and guidance route search is read from the DVD-ROM 200 and stored in the map data storage unit 30.
操作部３００は、リモコン、タッチパネルまたは操作スイッチ等であり、ユーザがナビゲーション装置１００に対して各種の情報（例えば、経路誘導の目的地や経由地）を設定したり、各種の操作（例えば、メニュー選択操作、地図の拡大／縮小操作、手動地図スクロール、数値入力など）を行ったりするためのものである。 The operation unit 300 is a remote controller, a touch panel, an operation switch, or the like, and the user sets various information (for example, a route guidance destination or waypoint) to the navigation device 100 or performs various operations (for example, a menu). Selection operation, map enlargement / reduction operation, manual map scrolling, numeric input, etc.).
目的地設定部４０は、ディスプレイ４００に表示されている目的地設定用の操作画面において、ユーザによる操作部３００の操作を介して指定された地点を目的地として設定する。そして、目的地設定部４０は、設定した目的地を示す目的地情報を誘導経路探索部５０に出力する。 The destination setting unit 40 sets, as a destination, a point designated through an operation of the operation unit 300 by the user on the destination setting operation screen displayed on the display 400. Then, the destination setting unit 40 outputs destination information indicating the set destination to the guidance route search unit 50.
誘導経路探索部５０は、地図データ記憶部３０に記憶されている地図データに基づいて、車両位置検出部１０により検出された自車位置（出発地）から、目的地設定部４０により設定された目的地に至る様々な経路上のリンクコストを順次加算し、リンクコストの合計が最も小さい経路を誘導経路として探索する。 The guide route search unit 50 is set by the destination setting unit 40 based on the map data stored in the map data storage unit 30 from the vehicle position (departure point) detected by the vehicle position detection unit 10. The link costs on the various routes to the destination are sequentially added, and the route having the smallest link cost is searched for as a guide route.
誘導経路メモリ６０は、誘導経路探索部５０により誘導経路が探索された場合、その探索された誘導経路のデータ（現在位置から目的地に至るまでのノードの集合）を誘導経路情報として一時的に格納する。 When the guide route search unit 50 searches for a guide route, the guide route memory 60 temporarily uses the searched guide route data (a set of nodes from the current position to the destination) as guide route information. Store.
地図表示制御部７０は、車両位置検出部１０により検出された自車両の位置情報（自車位置情報）と、地図データ記憶部３０に記憶されている地図データとに基づいて、自車位置周辺の地図画像データを生成する。そして、地図表示制御部７０は、生成した地図画像データをディスプレイ４００に出力することにより、自車位置周辺の地図画像をディスプレイ４００に表示させる。 The map display control unit 70 is based on the position information of the own vehicle (own vehicle position information) detected by the vehicle position detection unit 10 and the map data stored in the map data storage unit 30. Generate map image data. Then, the map display control unit 70 outputs the generated map image data to the display 400, thereby causing the display 400 to display a map image around the vehicle position.
誘導経路案内部８０は、誘導経路探索部５０により誘導経路が探索された場合、車両位置検出部１０により検出された自車位置情報と、地図データ記憶部３０に記憶されている地図データと、誘導経路メモリ６０に格納された誘導経路情報とに基づいて誘導経路案内を行う。具体的には、誘導経路案内部８０は、ディスプレイ４００に対して、地図表示制御部７０により生成された地図画像に重ねて誘導経路を他の道路とは異なる色で太く表示することにより、誘導経路の目的地までの走行案内を行う。また、誘導経路案内部８０は、誘導経路上に存在する経路案内すべき分岐点（案内分岐点）に自車両が近づくたびに、当該案内分岐点に関する経路案内を行う。 When the guidance route search unit 50 searches for the guidance route, the guidance route guidance unit 80 detects the vehicle position information detected by the vehicle position detection unit 10, the map data stored in the map data storage unit 30, and Guide route guidance is performed based on the guide route information stored in the guide route memory 60. Specifically, the guidance route guide unit 80 displays the guidance route thickly in a color different from other roads on the map 400 generated by the map display control unit 70 on the display 400, thereby guiding the guidance route. Travel guidance to the destination of the route. Moreover, whenever the own vehicle approaches the branch point (guidance branch point) that should be route guidance existing on the guidance route, the guidance route guide unit 80 performs route guidance regarding the guidance branch point.
図２は、ナビゲーション装置１００において誘導経路が案内されている状態（ディスプレイ４００にて誘導経路案内が行われている状態）であって、自車両（以下、「自車両ＡＡ」という）が誘導経路から外れてしまった場合に、当該ナビゲーション装置１００（主には、誘導経路探索部５０）において行われる処理について説明するフローチャートである。 FIG. 2 is a state in which a guidance route is being guided in the navigation device 100 (a state in which guidance route guidance is being performed on the display 400), and the host vehicle (hereinafter referred to as “own vehicle AA”) is a guidance route. 7 is a flowchart for explaining processing performed in the navigation device 100 (mainly, the guidance route search unit 50) when it is off the map.
本実施形態のナビゲーション装置１００では、車両位置検出部１０による自車両ＡＡの車両現在位置に基づいて、自車両ＡＡが案内されている誘導経路上にあるか否か（案内されている誘導経路上を自車両ＡＡが走行しているか否か）を判定することができるようになっている。 In the navigation device 100 of this embodiment, based on the current vehicle position of the host vehicle AA by the vehicle position detection unit 10, whether or not the host vehicle AA is on the guided route (on the guided route). It is possible to determine whether or not the host vehicle AA is traveling.
（ステップＳ１）
まず、ナビゲーション装置１００では、自車両ＡＡの車両現在位置が案内中の誘導経路に有るか否かが判定される。これにより、例えば、誘導経路とは別の道路に迷い込んでしまった等、自車両ＡＡが誘導経路から外れてしまったか否かが判定されることとなる。
このとき、誘導経路から外れていないと判定された場合（つまり、案内中の誘導経路を走行していると判定された場合）には、処理を終了し、誘導経路から外れたと判定された場合には、ステップＳ２に処理を移す。(Step S1)
First, in the navigation apparatus 100, it is determined whether or not the current vehicle position of the host vehicle AA is on the guidance route being guided. As a result, for example, it is determined whether or not the host vehicle AA has deviated from the guidance route, such as having strayed to a road different from the guidance route.
At this time, when it is determined that the vehicle does not deviate from the guidance route (that is, when it is determined that the vehicle is traveling along the guidance route being guided), the processing is terminated and it is determined that the vehicle has deviated from the guidance route. In step S2, the process proceeds to step S2.
（ステップＳ２）
次に、ナビゲーション装置１００では、誘導経路探索部５０が、現在の経路（例えば、「第Ｎ経路（Ｎは自然数が入る）」）における経由地（通過地点または目的地）までのコスト最小ルートを探索する。(Step S2)
Next, in the navigation device 100, the guidance route search unit 50 determines the minimum cost route to the waypoint (passage point or destination) in the current route (for example, “Nth route (N is a natural number)”). Explore.
（ステップＳ３）
次に、ナビゲーション装置１００では、誘導経路探索部５０が、上記ステップＳ２において探索したコスト最小ルートで経由地に到達した場合に、この経由地から次の経路（「第Ｎ＋１経路」）に入るに際して「Ｕターン」が発生するか否かを判定する。すなわち、新たに探索した「第Ｎ経路」の経由地までのコスト最小ルートでは、「第Ｎ経路」→「第Ｎ＋１経路」と走行するにあたり、Ｕターンを発生させてしまうか否かが判定される。
このとき、経由地で「Ｕターン」が発生しないと判定された場合には、ステップＳ６に処理を移し、経由地で「Ｕターン」が発生すると判定された場合には、ステップＳ４に処理を移す。(Step S3)
Next, in the navigation device 100, when the guidance route search unit 50 reaches the transit point using the minimum cost route searched in step S <b> 2, when entering the next route (“N + 1th route”) from this transit point. It is determined whether or not a “U-turn” occurs. That is, it is determined whether or not a U-turn is generated when traveling from the “Nth route” to the “N + 1th route” in the least cost route to the waypoint of the “Nth route” newly searched. The
At this time, if it is determined that the “U-turn” does not occur at the waypoint, the process proceeds to step S6. If it is determined that the “U-turn” occurs at the waypoint, the process proceeds to step S4. Move.
なお、Ｕターンの有無を判定する地点は、経由地付近までも含めるものであってもよい。 In addition, the point which determines the presence or absence of a U-turn may include even the vicinity of a transit point.
（ステップＳ４）
次に、ナビゲーション装置１００では、誘導経路探索部５０が、「第Ｎ＋１経路」の主に前半部分の経路を再探索する。具体的には、自車両ＡＡが「第Ｎ経路」の経由地にてＵターンをすることなく走行（通過）した場合の経路から、「第Ｎ＋１経路」の途中において接続させることの可能な合流点（合流地点）までを含む経路を探索する。すなわち、「第Ｎ＋１経路」の前半部分を変更させることにより、「第Ｎ経路」と「第Ｎ＋１経路」とのスムーズな接続を確保するとともに、当初の「第Ｎ＋１経路」に復帰させる誘導経路が再探索されることとなる。(Step S4)
Next, in the navigation apparatus 100, the guidance route search unit 50 re-searches mainly the route in the first half of the “N + 1th route”. Specifically, a merge that can be connected in the middle of the “N + 1st route” from the route when the host vehicle AA travels (passes) without making a U-turn at the “Nth route” route. A route including a point (a merging point) is searched. That is, by changing the first half of the “N + 1th route”, a smooth connection between the “Nth route” and the “N + 1th route” is ensured, and a guidance route for returning to the original “N + 1th route” is provided. It will be searched again.
また、本ステップＳ４では、再探索されたコスト最小ルートを辿って自車両ＡＡが「第Ｎ経路」の経由地にてＵターンをすることなく走行（通過）した場合の経路から、「第Ｎ＋１経路」に最も早く（早期に）復帰することのできる合流点を優先して決定するものとしている。例えば、複数の合流点が見つかった場合には、最も早い段階で「第Ｎ＋１経路」に戻すことのできる経路が再探索の結果として決定されることになる。 Further, in this step S4, from the route when the host vehicle AA travels (passes) without making a U-turn at the waypoint of the “Nth route” following the re-searched minimum cost route, “N + 1” is obtained. The merging point that can return to the “route” the earliest (early) is preferentially determined. For example, when a plurality of merging points are found, a route that can be returned to the “N + 1th route” at the earliest stage is determined as a result of the re-search.
なお、上述したように、複数の合流点が見つかった場合において、最も早く「第Ｎ＋１経路」に復帰させる合流点であっても、その合流点に辿り着くまでのルートが複雑化するような場合には、例えば、最も単純なルートを辿ることにより到着する合流点を優先して決定するようにしてもよい。 As described above, when a plurality of merging points are found, even when the merging point is the earliest return to the “N + 1th path”, the route to reach the merging point is complicated. For example, the arrival point may be determined with priority by following the simplest route.
ここで、上記合流点の探索は、レベル０、レベル１、レベル２の３つのレベルに階層化された地図データを切り替えることにより、早期に合流点を見つけることが可能である。例えば、当初の「第Ｎ＋１経路」がレベル２の地図データにある道路（高速道路や有料道路といった道路）のみであれば、レベル１の地図データに切り替えることにより、この「第Ｎ＋１経路」の途中において接続可能な道路として該当する道路を探索する。そして、該当する道路が見つかった場合には、この接続する地点を合流点として決定する。レベル１の地図データでも合流点を見つけられない場合には、レベル０の地図データに切り替えることにより、この「第Ｎ＋１経路」の途中において接続可能な道路として該当する道路を探索する。そして、該当する道路が見つかった場合には、この接続する地点を合流点として決定する。 Here, the search for the junction point can find the junction point at an early stage by switching the map data hierarchized into three levels of level 0, level 1, and level 2. For example, if the original “N + 1st route” is only a road (a road such as a highway or a toll road) in the level 2 map data, switching to the level 1 map data will result in the middle of this “N + 1th route”. The corresponding road is searched as a connectable road. When a corresponding road is found, the connecting point is determined as a junction. If a junction point cannot be found even with level 1 map data, the corresponding road is searched as a connectable road in the middle of the “N + 1th route” by switching to level 0 map data. When a corresponding road is found, the connecting point is determined as a junction.
このように、再探索された「第Ｎ経路」の結果に基づいて、「第Ｎ＋１経路」についても、その一部（主には前半部分）を再探索することにより、「第Ｎ＋１経路」の途中から当初の誘導経路に復帰させることを可能なものとしている。 As described above, by re-searching a part (mainly the first half part) of the “N + 1st route” based on the re-searched result of the “Nth route”, It is possible to return to the original guidance route from the middle.
なお、詳細には図示しないが、上述した手法により、「第Ｎ＋１経路」における合流点が見つけられない場合には、「第Ｎ＋２経路」について、本ステップＳ４で説明した処理を実行するようにすれば、自車両ＡＡが誘導経路から外れてしまった場合において、各経路の接続をスムーズにすることができるとともに、できるだけ早期の段階で、当初の誘導経路に復帰させることが可能となる。したがって、新たに案内される誘導経路のルート品位を担保することができる。 Although not shown in detail, if the merging point in the “N + 1th path” cannot be found by the above-described method, the process described in step S4 is performed for the “N + 2th path”. For example, in the case where the host vehicle AA has deviated from the guidance route, it is possible to smoothly connect the routes, and to return to the original guidance route at the earliest possible stage. Therefore, the route quality of the newly guided guidance route can be secured.
（ステップＳ５）
次に、ナビゲーション装置１００では、誘導経路探索部５０が、上記ステップＳ２における「第Ｎ経路」の経由地までのコスト最小ルートと、上記ステップＳ４において探索した「第Ｎ経路」の経由地にてＵターンをすることなく走行（通過）した場合の経路から、「第Ｎ＋１経路」における合流点までのルートと、を新たな誘導経路として決定する。すなわち、この場合には、「第Ｎ経路」および「第Ｎ＋１経路」の途中までが新たな誘導経路に変更されることとなる。さらに、新たな誘導経路では、「第Ｎ経路」から「第Ｎ＋１経路」を移動するに際して「Ｕターン」も発生しないこととなる。(Step S5)
Next, in the navigation apparatus 100, the guidance route search unit 50 uses the minimum cost route to the “Nth route” route in step S2 and the “Nth route” route searched in step S4. The route from the route when traveling (passing) without making a U-turn to the junction at the “N + 1th route” is determined as a new guidance route. That is, in this case, the middle of the “Nth route” and the “N + 1th route” is changed to a new guidance route. Further, in the new guidance route, the “U-turn” does not occur when moving from the “Nth route” to the “N + 1th route”.
そして、本ステップＳ５において決定した誘導経路（「第Ｎ経路」→「第Ｎ＋１経路」）は、誘導経路案内部８０によりディスプレイ４００において、新たな誘導経路として案内されることとなる。 Then, the guidance route determined in step S5 (“Nth route” → “N + 1th route”) is guided as a new guidance route on the display 400 by the guidance route guidance unit 80.
上記ステップＳ３の判定が肯定された場合には、自車両ＡＡが「第Ｎ経路」から「第Ｎ＋１経路」を走行するに際して、Ｕターンが発生することとなるため、上記ステップＳ４において次の経路である「第Ｎ＋１経路」の再探索を行うようにしている。これにより、「第Ｎ経路」における経由地でＵターンして「第Ｎ＋１経路」に移動させるような誘導経路が案内させてしまうことを回避することができるようになっている。 If the determination in step S3 is affirmative, a U-turn will occur when the host vehicle AA travels from the “Nth route” to the “N + 1th route”. Therefore, in step S4, the next route The “N + 1st route” is searched again. As a result, it is possible to avoid guiding a guidance route that makes a U-turn at the waypoint in the “Nth route” and moves to the “N + 1th route”.
（ステップＳ６）
次に、ナビゲーション装置１００では、誘導経路探索部５０が、上記ステップＳ２における「第Ｎ経路」の経由地までのコスト最小ルート、を新たな誘導経路として決定する。すなわち、この場合には、「第Ｎ経路」から「第Ｎ＋１経路」に移動するに際して「Ｕターン」が発生しないため、「第Ｎ経路」のみ新たな誘導経路に変更されることとなる。(Step S6)
Next, in the navigation apparatus 100, the guidance route search unit 50 determines the minimum cost route to the waypoint of the “Nth route” in step S2 as a new guidance route. That is, in this case, since the “U-turn” does not occur when moving from the “Nth route” to the “N + 1th route”, only the “Nth route” is changed to a new guide route.
そして、本ステップＳ６において決定した誘導経路（「第Ｎ経路」）は、誘導経路案内部８０によりディスプレイ４００において、新たな誘導経路として案内されることとなる。 Then, the guidance route (“Nth route”) determined in step S6 is guided as a new guidance route on the display 400 by the guidance route guidance unit 80.
このように、本実施形態のナビゲーション装置１００では、誘導経路を再探索する場合、経由地（中継地、通過地点、または目的地）までの最小単位の経路において、この経由地までのコスト最小ルートを再探索する。これに加えて、再探索されたコスト最小ルートが、次の経路にスムーズに接続するための合流点（経由地付近でＵターンすることなく接続できる合流点）、および、合流点までの経路を、次の経路上において探索する。これにより、再探索の後に案内する新たな誘導経路について、各経路の接続をスムーズにすることができるとともに、ルート品位を担保することができる。 As described above, in the navigation device 100 according to the present embodiment, when re-searching for the guidance route, the minimum cost route to the waypoint in the route of the smallest unit to the waypoint (relay point, passage point, or destination). Search again. In addition to this, the re-searched minimum cost route is a merging point for smoothly connecting to the next route (a merging point that can be connected without making a U-turn near the waypoint), and a route to the merging point. Search on the next route. Thereby, about the new guidance route guided after re-searching, while being able to connect each route smoothly, route quality can be secured.
以上のように構成された本実施形態のナビゲーション装置１００によれば、図３（ａ）に示すように、当初案内されていた誘導経路（第１経路および第２経路）において、例えば、図３（ｂ）に示すように、第１経路の途中で自車両ＡＡが第１経路から外れてしまった場合には、第１経路におけるコスト最小ルートの探索だけではなく、第１経路の経由地１（通過地点１）をそのまま通過して（Ｕターンすることなく通過して）、第２経路の途中において合流させるルートが探索される。 According to the navigation device 100 of the present embodiment configured as described above, as shown in FIG. 3A, in the guidance route (first route and second route) that was initially guided, for example, FIG. As shown in (b), when the host vehicle AA has deviated from the first route in the middle of the first route, not only the search for the minimum cost route in the first route but also the waypoint 1 of the first route. Passing through (passing point 1) as it is (passing without making a U-turn), a route to be joined in the middle of the second route is searched.
ここで、従来のナビゲーション装置（従来技術）であれば、第１経路におけるコスト最小ルートの探索だけを行うことにより、図３（ｃ）に示すように、経由地１において、自車両ＡＡがＵターンをしなければならない誘導経路が案内される可能性も考えられる。すなわち、従来のナビゲーション装置では、再探索の結果として、第１経路から第２経路に必ずしもスムーズに接続する誘導経路が案内されないこともあり得る。 Here, in the case of the conventional navigation device (conventional technology), only the search for the minimum cost route in the first route is performed, and as shown in FIG. There is a possibility that a guidance route that must be turned is guided. That is, in the conventional navigation device, as a result of the re-search, a guidance route that smoothly connects from the first route to the second route may not be guided.
これに対して、本実施形態のナビゲーション装置１００では、第１経路におけるコスト最小ルートの探索を行うだけではなく、第２経路についてもその経路の一部が探索され得るものであるため、図３（ｄ）に示すように、再探索の結果として、第１経路から第２経路（第２経路の途中）にスムーズに接続する誘導経路が案内されることとなる。このように、本実施形態のナビゲーション装置１００によれば、上述したような従来のナビゲーション装置における問題点を解決することができる。 On the other hand, in the navigation device 100 of the present embodiment, not only the search for the minimum cost route in the first route but also a part of the route for the second route can be searched. As shown in (d), as a result of the re-search, a guidance route that smoothly connects from the first route to the second route (in the middle of the second route) is guided. Thus, according to the navigation apparatus 100 of this embodiment, the problem in the conventional navigation apparatus as mentioned above can be solved.
また、本実施形態のナビゲーション装置１００によれば、第１経路において自車両ＡＡが案内されている誘導経路から外れてしまった場合（図３（ｂ）参照）であっても、まずは、図４（ａ）に示すように、当該第１経路における経由地１までの残りの区間についてはコスト最小ルートが探索される。さらに、図４（ｂ）に示すように、この経由地１にてＵターンすることなく移動して第２経路に復帰させることのできる合流点までの経路についても探索される。 Further, according to the navigation device 100 of the present embodiment, even if the host vehicle AA deviates from the guided route on the first route (see FIG. 3B), first, FIG. As shown in (a), the minimum cost route is searched for the remaining section of the first route to the waypoint 1. Further, as shown in FIG. 4 (b), a route to the junction where it can move without making a U-turn at this waypoint 1 and return to the second route is also searched.
これにより、再探索した後に案内する誘導経路について、各経路をスムーズに接続させた誘導経路を案内することができるとともに、この誘導経路のルート品位を担保することができる。 As a result, for the guidance route to be guided after re-searching, it is possible to guide the guidance route in which the routes are smoothly connected, and to guarantee the route quality of the guidance route.
また、本実施形態のナビゲーション装置１００によれば、図４（ａ）に示すように、第１経路における経由地１までのコスト最小ルートを辿ると、この経由地１でＵターンが発生することとなってしまう場合には、この経由地１から第２経路における合流点までの新たな経路を探索することにより、経由地１を通過した自車両ＡＡが合流点にて第２経路に復帰することができるため、第２経路の全てを再探索する必要が無い。すなわち、第１経路だけでなく第２経路の全てまでも再探索することにより生じる処理負担を軽減させることができる。さらに、第２経路に合流点が見つかった場合には、第３経路以降については全く変更する必要がないため、第３経路以降の経路の再探索を行う必要が無い。すなわち、第１経路を再探索したことにより、全ての経路を再探索しなければならなくなるといった事態の発生を防止することができる。 Further, according to the navigation device 100 of the present embodiment, as shown in FIG. 4A, when the minimum cost route to the waypoint 1 in the first route is traced, a U-turn occurs at this waypoint 1. In this case, by searching for a new route from the waypoint 1 to the joining point in the second route, the host vehicle AA that has passed through the waypoint 1 returns to the second route at the joining point. Therefore, it is not necessary to search again all of the second route. That is, it is possible to reduce the processing load caused by re-searching not only the first route but also all of the second route. Furthermore, when a confluence is found on the second route, there is no need to change the route after the third route, so there is no need to re-search the route after the third route. That is, it is possible to prevent the occurrence of a situation where all the routes have to be re-searched by re-searching the first route.
（その他の実施形態についての言及）
上記実施形態は、本発明を限定するものではなく、要旨を変更しない範囲で様々な形態に変更することができる。(References to other embodiments)
The said embodiment does not limit this invention and can be changed into various forms in the range which does not change a summary.
なお、上記実施形態における経由地（中継地）は、何らかの建造物が存在しているものに限られず、地図上における点（座標点）であってもよい。 In addition, the waypoint (relay point) in the said embodiment is not restricted to a certain building, but may be a point (coordinate point) on a map.
また、上記実施形態では、上記ステップＳ４において、「第Ｎ＋１経路」における合流点を見つけるにあたり、地図データをレベル２→レベル１→レベル０に切り替える場合を例にとって説明したが、これに限られない。例えば、上記合流点を見つけるにあたり、地図データをレベル０→レベル１→レベル２に切り替えるようにしてもよい。
また、地図データについても、レベル０、レベル１、レベル２という３つの階層に限られるものではなく、さらに細分化した地図データを設けるものとしてもよい。In the above embodiment, the case where the map data is switched from level 2 to level 1 to level 0 in the step S4 in order to find the junction point in the “N + 1th route” has been described as an example. However, the present invention is not limited to this. . For example, the map data may be switched from level 0 to level 1 to level 2 in finding the junction.
Further, the map data is not limited to the three hierarchies of level 0, level 1, and level 2, and further subdivided map data may be provided.
１０ 車両位置検出部
２０ ＤＶＤ−ＲＯＭ制御部
３０ 地図データ記憶部
４０ 目的地設定部
５０ 誘導経路探索部
６０ 誘導経路メモリ
７０ 地図表示制御部
８０ 誘導経路案内部
１００ ナビゲーション装置
２００ ＤＶＤ−ＲＯＭ
３００ 操作部
４００ ディスプレイ
ＡＡ 自車両
DESCRIPTION OF SYMBOLS 10 Vehicle position detection part 20 DVD-ROM control part 30 Map data memory | storage part 40 Destination setting part 50 Guidance route search part 60 Guidance route memory 70 Map display control part 80 Guidance route guide part 100 Navigation apparatus 200 DVD-ROM
300 Operation part 400 Display AA Own vehicle
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2016052769AJP6612159B2 (en) | 2016-03-16 | 2016-03-16 | Navigation device |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2016052769AJP6612159B2 (en) | 2016-03-16 | 2016-03-16 | Navigation device |
| Publication Number | Publication Date |
|---|---|
| JP2017166994Atrue JP2017166994A (en) | 2017-09-21 |
| JP6612159B2 JP6612159B2 (en) | 2019-11-27 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2016052769AActiveJP6612159B2 (en) | 2016-03-16 | 2016-03-16 | Navigation device |
| Country | Link |
|---|---|
| JP (1) | JP6612159B2 (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2021189150A (en)* | 2020-06-05 | 2021-12-13 | 株式会社アイシン | Guidance system and guidance program |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0668389A (en)* | 1992-08-19 | 1994-03-11 | Aisin Aw Co Ltd | Navigation device for vehicle |
| JP2000337908A (en)* | 1999-05-28 | 2000-12-08 | Clarion Co Ltd | Navigation equipment and method, and recording medium stored with software for navigation |
| JP2009264749A (en)* | 2008-04-21 | 2009-11-12 | Pioneer Electronic Corp | Apparatus, method, and program for route search and storage medium |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0668389A (en)* | 1992-08-19 | 1994-03-11 | Aisin Aw Co Ltd | Navigation device for vehicle |
| JP2000337908A (en)* | 1999-05-28 | 2000-12-08 | Clarion Co Ltd | Navigation equipment and method, and recording medium stored with software for navigation |
| JP2009264749A (en)* | 2008-04-21 | 2009-11-12 | Pioneer Electronic Corp | Apparatus, method, and program for route search and storage medium |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2021189150A (en)* | 2020-06-05 | 2021-12-13 | 株式会社アイシン | Guidance system and guidance program |
| Publication number | Publication date |
|---|---|
| JP6612159B2 (en) | 2019-11-27 |
| Publication | Publication Date | Title |
|---|---|---|
| JP4808050B2 (en) | Navigation device and multi-path fusion method | |
| US8670922B2 (en) | Guiding route generation device and guiding route generation method | |
| JP5590950B2 (en) | Navigation device and guided route search method | |
| JP2013096713A (en) | Navigation device | |
| JP2006200978A (en) | Guide route generation device and guide route generation method | |
| JP2011027610A (en) | Navigation device and guide route searching method | |
| JP2008139174A (en) | Route search device | |
| JP2007285998A (en) | Navigation apparatus and method of producing alternative route | |
| JP4863919B2 (en) | Map information processing device | |
| JP4372526B2 (en) | Navigation device and guidance method for surrounding facilities | |
| JP4651511B2 (en) | Navigation device and vehicle position determination method | |
| JP2006242787A (en) | Guide route creating device, car navigation system, and guide route creating method | |
| JP4817992B2 (en) | Navigation device and U-turn information providing method | |
| JP2011043336A (en) | Navigation system | |
| JP6612159B2 (en) | Navigation device | |
| JP4637262B2 (en) | Route guidance device | |
| JP4322163B2 (en) | Navigation device and intersection enlarged view display method | |
| CN101636635A (en) | navigation device | |
| JP4240360B2 (en) | Navigation device | |
| JP4393403B2 (en) | Route guidance device and route guidance method | |
| JP4640774B2 (en) | Navigation device and control method for search for detour route | |
| JP4145756B2 (en) | NAVIGATION DEVICE, NAVIGATION METHOD, PROGRAM THEREOF, AND RECORDING MEDIUM CONTAINING THE PROGRAM | |
| JP2009156851A (en) | Navigator | |
| JP5064891B2 (en) | Car navigation system | |
| JP2007085897A (en) | Route display system and map indication method |
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination | Free format text:JAPANESE INTERMEDIATE CODE: A621 Effective date:20180906 | |
| A977 | Report on retrieval | Free format text:JAPANESE INTERMEDIATE CODE: A971007 Effective date:20190724 | |
| A131 | Notification of reasons for refusal | Free format text:JAPANESE INTERMEDIATE CODE: A131 Effective date:20190730 | |
| A521 | Request for written amendment filed | Free format text:JAPANESE INTERMEDIATE CODE: A523 Effective date:20190913 | |
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) | Free format text:JAPANESE INTERMEDIATE CODE: A01 Effective date:20191029 | |
| A61 | First payment of annual fees (during grant procedure) | Free format text:JAPANESE INTERMEDIATE CODE: A61 Effective date:20191030 | |
| R150 | Certificate of patent or registration of utility model | Ref document number:6612159 Country of ref document:JP Free format text:JAPANESE INTERMEDIATE CODE: R150 |