JP5928893B2

JP5928893B2 - Route search device, route guide device, route search program, and route guide program

Info

Publication number: JP5928893B2
Application number: JP2012175647A
Authority: JP
Inventors: 大介谷▲崎▼
Original assignee: Aisin AW Co Ltd
Current assignee: Aisin AW Co Ltd
Priority date: 2012-08-08
Filing date: 2012-08-08
Publication date: 2016-06-01
Anticipated expiration: 2032-08-08
Also published as: JP2014035234A

Description

本発明は、経路探索装置、経路案内装置、経路探索プログラム及び経路案内プログラムに係り、例えば、経路探索装置が経路案内装置から出発地と目的地を取得して目的地までの走行経路の探索を行い、経路案内装置が経路探索装置から送信した目的地までの走行経路を受信して案内を行うナビゲーションシステムに関する。 The present invention relates to a route search device, a route guidance device, a route search program, and a route guidance program. For example, the route search device acquires a departure point and a destination from the route guidance device and searches for a travel route to the destination. The present invention relates to a navigation system that performs guidance by receiving a travel route to a destination transmitted from a route search device by a route guidance device.

車両や装置の現在位置や目的地までの経路を案内するナビゲーション装置が広く普及している。このナビゲーション装置では、地図データを保存しておき、走行経路の探索や探索した走行経路の案内の全てを行うようになっている。
一方、出発地から目的地までのルート探索をセンターサーバ側で行い、探索された走行経路を車載ナビゲーション装置に送信し、車載ナビゲーション装置では受信した走行経路の案内を行うことで、経路探索と経路案内とを別装置で行う技術が提案されている。
このように経路探索をセンターサーバで行うことにより、最新の情報による高速で質の高い経路探索が可能になるが、経路案内を行う車両が走行経路を外れた場合、ナビゲーション装置はセンターサーバに対してリルートを要求し、センターサーバは再度目的地までの走行経路を探索するか、又は、送付済みの走行経路上に戻るルートを探索してナビゲーション装置に送信する必要がある。
そして、センターサーバにおいて要求を受信してからリルートを行うと、ナビゲーション装置とセンターサーバ間における認証や通信などで時間を要してしまい新しい案内ルートの提供が遅れてしまうという問題がある。 Navigation devices that guide the current position of a vehicle or device or a route to a destination are widely used. In this navigation device, map data is stored, and a search for a travel route and guidance for the searched travel route are all performed.
On the other hand, the route search from the departure point to the destination is performed on the center server side, the searched travel route is transmitted to the in-vehicle navigation device, and the in-vehicle navigation device guides the received travel route, so that the route search and the route are performed. Techniques have been proposed for performing guidance with a separate device.
By performing the route search with the center server in this way, a high-speed and high-quality route search based on the latest information becomes possible. However, when the vehicle performing the route guidance deviates from the travel route, the navigation device The center server needs to search for a travel route to the destination again, or search for a route that returns to the travel route that has been sent and transmit it to the navigation device.
When the reroute is performed after receiving the request at the center server, there is a problem that it takes time for authentication and communication between the navigation device and the center server, and the provision of a new guidance route is delayed.

そこで、特許文献１では、センタで経路探索を行った際に、探索した走行経路上に存在する各分岐点から目的地までの代替経路を予め探索しておき、探索した走行経路と代替経路をナビゲーション装置に送信し、ナビゲーション装置では走行経路から外れた場合には代替経路の案内を行う技術について記載されている。
この特許文献１の方法によれば、走行経路から外れたとしても即座に新しい案内経路（代替経路）による案内を行うことが可能である。 Therefore, in Patent Document 1, when a route search is performed at the center, an alternative route from each branch point to the destination existing on the searched travel route is searched in advance, and the searched travel route and the alternative route are determined. A technique is described that transmits to a navigation device and guides an alternative route when the navigation device deviates from the travel route.
According to the method of this patent document 1, even if it deviates from a driving | running route, it is possible to perform guidance by a new guidance route (alternative route) immediately.

しかし、出発地から目的地までが離れれば離れる程に代替経路が多くなるという課題がある。
このためナビゲーション装置では、代替経路の案内を行うことは可能だが、保存すべきデータ量が多くなるという問題がある。
一方、センターサーバでは、代替経路を含めた経路探索に時間を要してしまうという問題がある。
さらに、ナビゲーション装置、センターサーバ双方の課題として、データ量が多くなり、送受信に時間を要するという問題もある。 However, there is a problem that as the distance from the departure point to the destination increases, the number of alternative routes increases.
For this reason, the navigation device can provide guidance for alternative routes, but there is a problem that the amount of data to be stored increases.
On the other hand, the center server has a problem that it takes time to search for a route including an alternative route.
Furthermore, as a problem for both the navigation device and the center server, there is a problem that the amount of data increases and time is required for transmission and reception.

特開２０１２−００２５７２号公報JP 2012-002572 A

本発明は、目的地までの走行経路と復帰ルートとを効率的に検索し提供することを第１の目的とする。
また、目的地までの走行経路と復帰ルートとを効率的に取得して案内を行うことを第２の目的とする。 The first object of the present invention is to efficiently search and provide a travel route to a destination and a return route.
A second object is to efficiently obtain the travel route to the destination and the return route for guidance.

（１）請求項１に記載の発明では、目的地までの走行ルートを探索する経路探索装置と、前記経路探索装置で探索された走行ルートを案内する経路案内装置で構成されるナビゲーションシステムにおける経路探索装置であって、前記経路案内装置から出発地と目的地を取得する取得手段と、前記取得した出発地から目的地までの走行ルートを探索する経路探索手段と、前記探索した走行ルートから退出可能な退出可能道路を特定する道路特定手段と、前記走行ルート上で、前記特定した退出可能道路よりも前記目的地側に復帰点を設定する復帰点設定手段と、前記特定した退出可能道路の前記走行ルートとの交差点から、前記設定した復帰点までの復帰ルートを探索する復帰経路探索手段と、前記経路案内装置から、復帰ルートの要求を受け付ける要求受付手段と、前記経路案内装置に、前記探索した走行ルートを送信するとともに、前記復帰ルートの要求を受け付けた場合に、前記探索した所定数の復帰ルートを送信する経路送信手段と、を具備し、前記経路送信手段は、前記経路案内装置が復帰ルートの要求をしてから、復帰ルートの受信を完了するまでに車両が走行すると想定される距離Ｌよりも大きい距離Ｌｓを基準にして決められた前記所定数の復帰ルートを送信する、ことを特徴とする経路探索装置を提供する。
（２）請求項２に記載の発明では、前記経路送信手段は、前記経路案内装置に送信済みの復帰ルートに対応する前記退出可能道路のうち最も目的地側の退出可能道路から、前記距離Ｌｓまでの間に存在する退出可能道路に対して探索された復帰ルートを送信する、ことを特徴とする請求項１に記載の経路探索装置を提供する。
（３）請求項３に記載の発明では、前記復帰点設定手段は、前記特定した退出可能道路よりも前記目的地側に存在し、前記走行ルートに進入可能な道路と前記走行ルートとの交差点を復帰点として設定する、ことを特徴とする請求項１、又は請求項２に記載の経路探索装置を提供する。
（４）請求項４に記載の発明では、前記道路特定手段は、前記経路送信手段で送信済みの復帰ルートに対応する前記退出可能道路のうち最も目的地側の退出可能道路の先に存在する、前記所定数本目の退出可能道路を特定し、前記復帰点設定手段は、前記道路特定手段で特定した前記所定数の退出可能道路のうち最も目的地側の退出可能道路から、更に所定数本目の退出可能道路と、前記走行ルートとの交差点を前記復帰点に設定する、ことを特徴とする請求項１から請求項３のうちの何れか１の請求項に記載の経路探索装置を提供する。
（５）請求項５に記載の発明では、目的地までの走行ルートを探索する請求項１から請求項４のうちの何れか１の請求項に記載された経路探索装置と、前記経路探索装置で探索された走行ルートを案内する経路案内装置で構成されるナビゲーションシステムにおける経路案内装置であって、前記経路探索装置に、出発地と目的地とを送信する送信手段と、前記経路探索装置に、復帰ルートの要求をする復帰ルート要求手段と、前記経路探索装置から、前記走行ルートと前記復帰ルートを受信する経路受信手段と、現在位置を検出する現在位置検出手段と、前記検出した現在位置に対応して、前記受信した走行ルートを案内する案内手段とを備え、前記案内手段は、前記現在位置が前記走行ルートから外れた場合に、前記復帰ルートに切り換えて案内をする、ことを特徴とする経路案内装置を提供する。
（６）請求項６に記載の発明では、前記復帰ルート要求手段は、前記受信済みの復帰ルートで未通過の復帰ルートの数が前記所定数未満となった場合に、復帰ルートの要求をする、ことを特徴とする請求項５に記載の経路案内装置を提供する。
（７）請求項７に記載の発明では、目的地までの走行ルートを探索する経路探索装置と、前記経路探索装置で探索された走行ルートを案内する経路案内装置で構成されるナビゲーションシステムにおける経路探索装置用の経路探索プログラムであって、前記経路案内装置から出発地と目的地を取得する取得機能と、前記取得した出発地から目的地までの走行ルートを探索する経路探索機能と、前記探索した走行ルートから退出可能な退出可能道路を特定する道路特定機能と、前記走行ルート上で、前記特定した退出可能道路よりも前記目的地側に復帰点を設定する復帰点設定機能と、前記特定した退出可能道路の前記走行ルートとの交差点から、前記設定した復帰点までの復帰ルートを探索する復帰経路探索機能と、前記経路案内装置から、復帰ルートの要求を受け付ける要求受付機能と、前記経路案内装置に、前記探索した走行ルートを送信するとともに、前記復帰ルートの要求を受け付けた場合に、前記探索した所定数の復帰ルートを送信する経路送信機能と、をコンピュータに実現させ、前記経路送信機能は、前記経路案内装置が復帰ルートの要求をしてから、復帰ルートの受信を完了するまでに車両が走行すると想定される距離Ｌよりも大きい距離Ｌｓを基準にして決められた前記所定数の復帰ルートを送信する、ことを特徴とする経路探索プログラムを提供する。
（８）請求項８に記載の発明では、目的地までの走行ルートを探索する請求項１から請求項４のうちの何れか１の請求項に記載された経路探索装置と、前記経路探索装置で探索された走行ルートを案内する経路案内装置で構成されるナビゲーションシステムにおける経路案内装置用の経路案内プログラムであって、前記経路探索装置に、出発地と目的地とを送信する送信機能と、前記経路探索装置に、復帰ルートの要求をする復帰ルート要求機能と、前記経路探索装置から、前記走行ルートと前記復帰ルートを受信する経路受信機能と、現在位置を検出する現在位置検出機能と、前記検出した現在位置に対応して、前記受信した走行ルートを案内する案内機能と、をコンピュータに実現させ、前記案内機能は、前記現在位置が前記走行ルートから外れた場合に、前記復帰ルートに切り換えて案内をする、ことを特徴とする経路案内プログラムを提供する。 (1) In the invention described in claim 1, a route in a navigation system including a route search device that searches for a travel route to a destination and a route guide device that guides the travel route searched by the route search device. A search device, an acquisition means for acquiring a departure place and a destination from the route guidance device, a route search means for searching a travel route from the acquired departure place to the destination, and exiting from the searched travel route Road identifying means for identifying possible exitable roads, return point setting means for setting a return point on the travel route closer to the destination side than the identified exitable roads, and for the identified exitable roads Return route search means for searching for a return route from the intersection with the travel route to the set return point, and a return route request from the route guidance device. Request receiving means, and route transmitting means for transmitting the searched travel route to the route guidance device and transmitting the predetermined number of searched return routes when the return route request is received. The route transmitting means is based on a distance Ls that is greater than the distance L that the vehicle is supposed to travel from when the route guidance device requests a return route until the return route is received. There is provided a route search apparatus characterized by transmitting the predetermined number of return routes determined .
( 2 ) In the invention according to claim 2 , the route transmitting means is configured to provide the distance Ls from the exitable road closest to the destination among the exitable roads corresponding to the return route that has been transmitted to the route guidance device. transmitting the return route which is searched against exit possible road that exists until, providing a route search device according to claim 1, characterized in that.
( 3 ) In the invention according to claim 3 , the return point setting means is located at the destination side of the identified exitable road, and an intersection between the road that can enter the travel route and the travel route. the set as return point, to provide a route search device according to claim 1 or claim 2, characterized in that.
(4) In the invention of claim 4, the road specifying means is present in most of the destination side exit possible road ahead of the exit possible road corresponding to the sent return route in the route transmission means The predetermined number of exitable roads are identified, and the return point setting means further determines a predetermined number of exitable roads from the most exitable road among the predetermined number of exitable roads identified by the road identifying means. The route search device according to any one of claims 1 to 3 , wherein an intersection between the exitable road and the travel route is set as the return point. .
( 5 ) In the invention according to claim 5 , the route search device according to any one of claims 1 to 4 for searching for a travel route to the destination, and the route search device A route guidance device in a navigation system configured with a route guidance device that guides the travel route searched for in the transmission system, a transmission means for transmitting a departure point and a destination to the route search device, and a route search device Return route request means for requesting a return route; route receiving means for receiving the travel route and the return route from the route search device; current position detection means for detecting a current position; and the detected current position Corresponding to the received travel route, and the guide device switches to the return route when the current position deviates from the travel route. The guiding Te, providing route guidance device, characterized in that.
( 6 ) In the invention according to claim 6 , the return route request means requests a return route when the number of return routes that have not passed in the received return route becomes less than the predetermined number. The route guidance device according to claim 5 is provided.
( 7 ) In the invention according to claim 7 , a route in a navigation system comprising a route search device that searches for a travel route to a destination and a route guide device that guides the travel route searched by the route search device. A route search program for a search device, an acquisition function for acquiring a departure point and a destination from the route guidance device, a route search function for searching for a travel route from the acquired departure point to the destination, and the search A road identifying function for identifying a releasable road that can be retreated from the travel route, a return point setting function for setting a retreat point on the destination side of the identified retreatable road on the travel route, and the identification A return route search function for searching for a return route from the intersection of the exitable road with the travel route to the set return point, and the route guidance device A request reception function for receiving a return route request, and a route for transmitting the searched travel route to the route guidance device and transmitting the predetermined number of searched return routes when the return route request is received. The transmission function is realized by a computer, and the route transmission function is more than the distance L that the vehicle is supposed to travel from when the route guidance device requests a return route until the return route is received. A route search program characterized by transmitting the predetermined number of return routes determined based on a large distance Ls is provided.
( 8 ) In the invention according to claim 8 , the route search device according to any one of claims 1 to 4 for searching for a travel route to the destination, and the route search device. A route guidance program for a route guidance device in a navigation system configured with a route guidance device that guides the travel route searched for in the transmission system, and a transmission function for transmitting a departure place and a destination to the route search device; A return route request function for requesting a return route to the route search device; a route reception function for receiving the travel route and the return route from the route search device; a current position detection function for detecting a current position; In response to the detected current position, the computer realizes a guidance function for guiding the received travel route, wherein the current position is determined by the travel route. If deviated from the guidance is switched to the return route, providing a route guidance program, characterized in that.

請求項１〜請求項４、請求項７記載の発明によれば、目的地までの走行経路と復帰ルートとを効率的に検索し経路案内装置に提供することができる。
請求項５、請求項６、請求項８記載の発明によれば、目的地までの走行経路と復帰ルートとを効率的に取得して案内を行うことができる。 According to the inventions of claims 1 to 4 and claim 7 , it is possible to efficiently search the travel route and the return route to the destination and provide them to the route guidance device.
According to the inventions of claims 5 , 6 , and 8 , the travel route to the destination and the return route can be efficiently obtained and guidance can be provided.

センターサーバで探索した走行ルートＭと、リルート候補道路と、復帰ルートについて表した説明図である。It is explanatory drawing showing the driving | running route M searched with the center server, the reroute candidate road, and the return route. 走行経路の案内を行うナビゲーション装置の構成図である。It is a block diagram of the navigation apparatus which guides a driving route. 走行ルートＭと復帰ルートの探索を行うセンターサーバの構成図である。It is a block diagram of a center server that searches for a travel route M and a return route. 一般道路における復帰ルートの要求タイミングと、復帰ルート探索の関係を表したものである。It shows the relationship between return route request timing on a general road and return route search. 高速道路における復帰ルートの要求タイミングと、復帰ルート探索の関係を表したものである。This shows the relationship between the return route request timing on the expressway and the return route search. 経路探索処理と経路案内処理の内容について表したフローチャートの一部である。It is a part of the flowchart showing the content of the route search process and the route guidance process. 経路探索処理と経路案内処理の内容について表したフローチャートの他の部分である。It is the other part of the flowchart showing the content of the route search process and the route guidance process.

以下、本発明のセンターサーバ及びナビゲーション装置における好適な実施の形態について、図１から図７を参照して詳細に説明する。
（１）実施形態の概要
図１は、センターサーバで探索した走行経路（走行ルートＭ）と、車両が走行ルートＭから外れる可能性があるリルート候補道路と、復帰ルートについて表したものである。
センターサーバでは、図１に示すように、ナビゲーション装置から受信した出発地から目的地までの走行経路（走行ルートＭ）を探索する。この探索の際に、車両が走行ルートＭから外れる可能性がある道路、すなわち、リルートが必要になる可能性がある道路（リルート候補道路Ａ１〜Ｊ１）を検索し、走行ルートＭ上に任意の復帰ポイントＲ１（復帰点として機能）を設定する。
そして、各リルート候補道路Ａ１〜Ｊ１から復帰ポイントＲ１までの復帰ルートを探索（復帰ルート探索）し、走行ルートＭと復帰ルートをナビゲーション装置に送信する。
この復帰ルート探索では、走行ルートＭ上の全リルート候補道路に対して一度に行うのではなく、車両の現在位置（最初は出発地）から、所定本数α（例えば、１０本）のリルート候補道路Ａ１〜Ｊ１に対して行う。 Hereinafter, preferred embodiments of the center server and the navigation device of the present invention will be described in detail with reference to FIGS.
(1) Outline of Embodiment FIG. 1 shows a travel route (travel route M) searched by the center server, a reroute candidate road where the vehicle may deviate from the travel route M, and a return route.
As shown in FIG. 1, the center server searches for a travel route (travel route M) from the departure place to the destination received from the navigation device. In this search, a road on which the vehicle may deviate from the travel route M, that is, a road that may require a reroute (reroute candidate roads A1 to J1) is searched, and an arbitrary route on the travel route M is searched. A return point R1 (function as a return point) is set.
Then, a return route from each of the reroute candidate roads A1 to J1 to the return point R1 is searched (return route search), and the travel route M and the return route are transmitted to the navigation device.
This return route search is not performed on all the reroute candidate roads on the travel route M at once, but a predetermined number α (for example, 10) of reroute candidate roads from the current position of the vehicle (initially the starting place). Perform for A1 to J1.

ナビゲーション装置では、センターサーバから受信した走行ルートＭと復帰ルートを記憶しておき、画面表示した地図情報上に走行ルートＭを表示すると共に、車両の現在位置Ｎを表示することで案内をし、更に、装置によっては音声による走行ルートＭの案内を行う。
そして、車両が走行ルートＭから外れてリルート候補道路、例えば、図１に示すようにＣ１に進入した場合には、進入したリルート候補道路Ｃ１に対応する復帰ルートｃ１（点線で表示）と、その復帰ルートｃ１の復帰ポイントＲ１から先の走行ルートＭとを結合したルートに切り換えて案内を継続する。 The navigation device stores the travel route M and return route received from the center server, displays the travel route M on the map information displayed on the screen, and displays the current position N of the vehicle for guidance. Further, depending on the device, guidance of the travel route M is performed by voice.
When the vehicle departs from the travel route M and enters a reroute candidate road, for example, C1 as shown in FIG. 1, a return route c1 (indicated by a dotted line) corresponding to the entered reroute candidate road C1 and its The guidance is continued by switching from the return point R1 of the return route c1 to the route combined with the previous travel route M.

車両が走行ルートＭ通りに走行し、進行方向で一番近い復帰ポイント（図１の場合、Ｒ１）までのリルート候補道路（復帰ルート）の数が所定数α未満になった場合、ナビゲーション装置はセンターサーバに次の復帰ルート探索を要求する。
センターサーバでは、復帰ルート探索の要求を受信すると、送信済みの復帰ルートａ１〜ｊ１以降の、α本のリルート候補道路Ａ２〜Ｊ２（図示せず）に対して新たな復帰ポイントＲ２（図示せず）までの復帰ルート探索を行い、探索した復帰ルート（ａ２〜ｊ２）をナビゲーション装置に送信する。 When the vehicle travels along the driving route M and the number of reroute candidate roads (return routes) to the closest return point (R1 in the case of FIG. 1) in the traveling direction is less than a predetermined number α, the navigation device Request the next return route search from the center server.
When the center server receives the return route search request, the center server adds a new return point R2 (not shown) to the α reroute candidate roads A2 to J2 (not shown) after the already sent return routes a1 to j1. ) Is searched, and the searched return route (a2 to j2) is transmitted to the navigation device.

センターサーバが復帰ルート探索を行うリルート候補道路の数αは、ナビゲーション装置が復帰ルート探索要求をしてから復帰ルートの受信を完了するまでの時間（タイムラグ）Ｔの間に、受信済みの全復帰ルートを通過してしまわない本数αが決められている。
これによりナビゲーション装置は、自車位置の先に存在する直近のリルート候補道路Ａ１〜Ｊ１に対する復帰ルートが常に記憶している状態となり、復帰ルートの案内を直ちに開始することができる。 The number α of reroute candidate roads on which the center server searches for a return route is the total return that has been received during the time (time lag) T from when the navigation device makes a return route search request until reception of the return route is completed. The number α that does not pass through the route is determined.
Thereby, the navigation device is in a state where the return route for the latest reroute candidate roads A1 to J1 existing ahead of the vehicle position is always stored, and the return route guidance can be started immediately.

（２）実施形態の詳細
本実施形態では、経路探索装置として機能するセンターサーバ１００と、経路案内装置として機能するナビゲーション装置によりナビゲーションシステムが構成される。
そして、出発地から目的地までの走行経路（走行ルートＭ）の探索をセンターサーバ１００が行い、出発地、目的地の設定と、センターサーバ１００で探索された走行ルートＭの案内をナビゲーション装置１が行う。
図２は、本実施形態において、走行経路の案内を行うナビゲーション装置１の構成図である。
ナビゲーション装置１は、図２に示すように、現在位置検出装置１０、情報処理制御装置２０、入出力装置４０及び情報記憶装置５０とを備えている。
現在位置検出装置１０は、方位センサ１２、距離センサ１３、ＧＰＳ受信装置１４を備え、それぞれ以下のように構成されている。
方位センサ１２は、基準角度（絶対方位）に対して、相対的に変化した角度を検出する手段であり、本実施形態では、角速度を利用して角度の変化を検出するジャイロセンサを使用している。なお、ハンドルの回転部に取り付けた光学的な回転センサや回転型の抵抗ボリューム或いは車輪部に取り付ける角度センサでもよい。また、方位センサ１２として、例えば、磁石に基づいてＮ方向の検出から、車両がいずれの方向に位置するかを検出する地磁気センサであり、絶対方位を検出する手段であってもよい。 (2) Details of Embodiment In this embodiment, a navigation system is configured by the center server 100 that functions as a route search device and the navigation device that functions as a route guidance device.
Then, the center server 100 searches for a travel route (travel route M) from the departure point to the destination, and the navigation device 1 provides the setting of the departure point and the destination and guidance of the travel route M searched by the center server 100. Do.
FIG. 2 is a configuration diagram of the navigation device 1 that guides a travel route in the present embodiment.
As shown in FIG. 2, the navigation device 1 includes a current position detection device 10, an information processing control device 20, an input / output device 40, and an information storage device 50.
The current position detection device 10 includes an azimuth sensor 12, a distance sensor 13, and a GPS reception device 14, and is configured as follows.
The azimuth sensor 12 is a means for detecting an angle that has changed relative to a reference angle (absolute azimuth). In this embodiment, a gyro sensor that detects a change in angle using an angular velocity is used. Yes. Note that an optical rotation sensor attached to the rotating part of the handle, a rotary resistance volume, or an angle sensor attached to the wheel part may be used. Further, the direction sensor 12 may be, for example, a geomagnetic sensor that detects in which direction the vehicle is located from detection in the N direction based on a magnet, and may be a means for detecting an absolute direction.

距離センサ１３は、車両の移動距離を計測できる手段であり、例えば、車輪の回転を検出して計数するものや、加速度を検出して２回積分するものを使用する。
ＧＰＳ（グローバル・ポジショニング・システム）受信装置１４は、人工衛星からの信号を受信する装置であり、信号の発信時刻、受信装置の位置情報、受信装置の移動速度、受信装置の進行方向など様々な情報を得ることができる。 The distance sensor 13 is a means that can measure the moving distance of the vehicle, and for example, a sensor that detects and counts the rotation of a wheel or a sensor that detects acceleration and integrates it twice.
The GPS (Global Positioning System) receiver 14 is a device that receives a signal from an artificial satellite, and includes various signals such as signal transmission time, position information of the receiver, moving speed of the receiver, and traveling direction of the receiver. Information can be obtained.

情報処理制御装置２０は、現在位置検出装置１０、入出力装置４０から入力される情報及び情報記憶装置５０に格納された情報に基づいて演算及び制御を行うとともに、演算結果をディスプレイ４２やスピーカ４３等の出力手段に出力するように制御する手段である。 The information processing control device 20 performs calculation and control based on information input from the current position detection device 10 and the input / output device 40 and information stored in the information storage device 50, and displays the calculation result on the display 42 and the speaker 43. It is a means to control to output to the output means.

この情報処理制御装置２０は、以下のように構成されている。
中央処理装置（ＣＰＵ）２１は、ナビゲーション装置１全体の総括的な演算及び制御を行う。
ＲＯＭ２２には、ナビゲーション機能に関する各種プログラムが格納されている。このナビゲーション機能としては、例えば、現在地を取得したり、出発地や目的地の入力を受け付けてセンターサーバ１００に経路探索を要求したり、センターサーバ１００から受信した目的地までの走行ルートＭ（走行経路）や、走行ルートＭから外れた場合の復帰ルートを画面表示や音声により案内したりする等がある。
ＲＯＭ２２には、またナビゲーション装置１を特定する装置ＩＤが記憶されている。この装置ＩＤは、センターサーバと通信により経路探索の要求や、復帰ルート探索の要求をする際に他のデータと共に、通信インターフェイス２５を介して送信される。
なお、これらのナビゲーション機能に関するプログラムや装置ＩＤについては、ＲＯＭ２２ではなく、所定のサーバからダウンロードすることで一時的にＲＡＭ２４に格納し、また、情報記憶装置５０のプログラム格納領域に保存するようにしてもよい。
ＣＰＵ２１は、ＲＯＭ２２等に格納されている各種プログラムを実行することで、ナビゲーション機能が実現される。 The information processing control device 20 is configured as follows.
The central processing unit (CPU) 21 performs overall calculation and control of the entire navigation device 1.
The ROM 22 stores various programs related to the navigation function. As the navigation function, for example, the present location is acquired, the input of the departure place and the destination is received and the center server 100 is requested to search for a route, or the travel route M (running to the destination received from the center server 100) Route), and a return route when the route deviates from the travel route M is displayed on the screen or by voice.
The ROM 22 also stores a device ID that identifies the navigation device 1. This device ID is transmitted through the communication interface 25 together with other data when a route search request or a return route search request is made by communication with the center server.
Note that the programs and device IDs related to these navigation functions are temporarily stored in the RAM 24 by downloading from a predetermined server instead of the ROM 22, and also stored in the program storage area of the information storage device 50. Also good.
The CPU 21 implements a navigation function by executing various programs stored in the ROM 22 or the like.

センサ入力インターフェイス２３は、現在位置検出装置１０からの情報を受け取る手段である。
ＲＡＭ２４は、入力装置４１により入力された目的地の情報等のユーザが入力した情報を記憶すると共に、利用者の入力情報に基づいてＣＰＵ２１により演算された結果や、経路探索された結果、または情報記憶装置５０から読み込まれた地図情報を格納するための記憶手段である。
例えば、入力装置４１からユーザにより入力され、センターサーバ１００に送信するための出発地と目的地、車両現在位置を出発地とする場合に現在位置検出装置１０で検出した現在位置、センターサーバ１００から受信した出発地から目的地までの走行ルートＭ、復帰ルートａｎ〜ｊｎ、リルート候補道路Ａｎ〜Ｊｎ、その他の情報が一時記憶される。
また、情報記憶装置５０に地図データファイル５１を備えていない場合にセンターサーバ１００から受信する地図データがＲＡＭ２４に記憶される場合もある。更に、地図データファイル５１を備えるが、より詳細な地図データや更新された地図データをセンターサーバ１００から受信する場合の地図データがＲＡＭ２４に記憶される場合もある。 The sensor input interface 23 is a means for receiving information from the current position detection device 10.
The RAM 24 stores information input by the user, such as destination information input by the input device 41, and results calculated by the CPU 21, based on user input information, route search results, or information It is a storage means for storing the map information read from the storage device 50.
For example, a starting point and a destination that are input by the user from the input device 41 and transmitted to the center server 100, and a current position detected by the current position detecting device 10 when the vehicle current position is the starting point, from the center server 100 The received travel route M from the departure point to the destination, the return route an to jn, the reroute candidate roads An to Jn, and other information are temporarily stored.
In addition, when the map data file 51 is not provided in the information storage device 50, the map data received from the center server 100 may be stored in the RAM 24. Furthermore, although the map data file 51 is provided, the map data when more detailed map data or updated map data is received from the center server 100 may be stored in the RAM 24.

通信インターフェイス２５は、伝送路４５を介して各種情報を入出力するための手段である。具体的には、伝送路４５を介して、ＧＰＳ受信装置１４、入力装置４１、情報記憶装置５０が接続される。
この通信インターフェイス２５は、さらに、インターネット等の各種ネットワークや各種通信手段を介して外部装置との通信を行う。本実施形態では、通信インターフェイス２５により、センターサーバ１００との通信が行われるようになっている。 The communication interface 25 is means for inputting / outputting various information via the transmission path 45. Specifically, the GPS receiver 14, the input device 41, and the information storage device 50 are connected via the transmission path 45.
The communication interface 25 further communicates with an external device via various networks such as the Internet and various communication means. In the present embodiment, communication with the center server 100 is performed by the communication interface 25.

時計２８は、例えば、水晶振動子などを用いて構成されており、時刻を刻んだり、発振によってナビゲーション装置１の各部の動作タイミングを提供したりする。
その他、ＣＰＵ２１で処理されたベクトル情報を画像情報に処理するための画像処理専用の画像プロセッサ、画像プロセッサで処理された画像情報を格納する画像メモリ、情報記憶装置５０から読み込まれた音声情報を処理しスピーカ４３に出力する音声処理専用の音声プロセッサを配設するようにしてもよい。 The timepiece 28 is configured by using, for example, a crystal resonator, and clocks time or provides operation timing of each part of the navigation device 1 by oscillation.
In addition, an image processor dedicated to image processing for processing vector information processed by the CPU 21 into image information, an image memory for storing image information processed by the image processor, and audio information read from the information storage device 50 are processed. However, a voice processor dedicated to voice processing to be output to the speaker 43 may be provided.

入出力装置４０は、利用者により目的地、探索条件等のデータを入力する入力装置４１、画像を表示するディスプレイ４２、音声を出力するスピーカ４３より構成される。
入力装置４１は、例えば、タッチパネル、タッチスイッチ、ジョイスティック、キースイッチ等で構成される。入力装置４１のユーザ操作により出発地や目的地が入力されたりする。
ディスプレイ４２には、現在位置検出装置１０で検出された現在位置周辺の地図が表示されると共に、当該地図上にセンターサーバ１００から受信した走行ルートＭや現在位置マークＮが表示される。 The input / output device 40 includes an input device 41 for inputting data such as a destination and search conditions by a user, a display 42 for displaying an image, and a speaker 43 for outputting sound.
The input device 41 includes, for example, a touch panel, a touch switch, a joystick, a key switch, and the like. A departure point and a destination are input by a user operation of the input device 41.
On the display 42, a map around the current position detected by the current position detection device 10 is displayed, and the travel route M and the current position mark N received from the center server 100 are displayed on the map.

情報記憶装置５０は、伝送路４５を介して情報処理制御装置２０に接続される。
情報記憶装置５０は、地図データファイル５１、その他のデータファイル５２（例えば、走行経路を音声により案内する場合の音声データ等）を格納している。
この情報記憶装置５０は、一般的には、光学的記憶媒体であるＤＶＤ−ＲＯＭ、ＣＤ−ＲＯＭや磁気的記憶媒体であるハードディスクなどで構成されるが、光磁気ディスク、各種半導体メモリなどの各種情報記憶媒体で構成してもよい。
なお、書き換えが必要な情報については、書き換え可能なハードディスク、フラッシュメモリなどで構成し、その他の固定的な情報についてはＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭなどのＲＯＭを使用するようにしてもよい。 The information storage device 50 is connected to the information processing control device 20 via the transmission path 45.
The information storage device 50 stores a map data file 51 and other data files 52 (for example, voice data when a travel route is guided by voice).
The information storage device 50 is generally composed of an optical storage medium such as a DVD-ROM, a CD-ROM, or a magnetic storage medium such as a hard disk, but various types such as a magneto-optical disk and various semiconductor memories. You may comprise with an information storage medium.
Information that needs to be rewritten may be constituted by a rewritable hard disk or flash memory, and other fixed information may be a ROM such as a CD-ROM or DVD-ROM.

地図データファイル５１には、ナビゲーションにおける地図表示、経路探索、経路案内に必要な各種データとして、地図データ、道路データ、目的地データ、案内地点データ、詳細目的地データ、その他のデータが記憶されている。
地図データとしては、全国道路地図、各地域の道路地図または住宅地図等が記憶されている。道路地図は、主要幹線道路、高速道路、細街路等の各道路と地上目標物（施設等）から構成される。住宅地図は、地上建造物等の外形を表す図形及び、道路名称等が表示される市街図である。細街路とは、例えば、国道、県道以下の道幅が所定値以下の比較的狭い道路である。
地図データは、車両現在位置やユーザに指定された地点を含む、所定縮尺による一定範囲の地図がディスプレイ４２に表示される。この地図上には、車両の現在位置や指定された地点が表示される。
道路データは、各道路の位置と種類及び車線数及び各道路間の接続関係等の道路に関するデータで、ノード情報とリンク情報で構成される。この道路データは、経路探索やマップマッチングに使用されると共に、探索した走行経路を地図データ上に重ねて表示する場合にも使用される。 The map data file 51 stores map data, road data, destination data, guidance point data, detailed destination data, and other data as various data necessary for map display, route search, and route guidance in navigation. Yes.
As map data, a national road map, a road map of each region, a house map, or the like is stored. The road map is composed of roads such as main arterial roads, expressways, narrow streets, and ground targets (facility etc.). A house map is a city map in which a figure representing an outer shape of a ground building, a road name, and the like are displayed. The narrow street is, for example, a relatively narrow road having a road width equal to or less than a predetermined value below a national road or prefectural road.
As for the map data, a map of a predetermined range including a current vehicle position and a point designated by the user is displayed on the display 42 at a predetermined scale. On this map, the current position of the vehicle and the designated point are displayed.
The road data is data regarding roads such as the position and type of each road, the number of lanes, and the connection relationship between the roads, and is composed of node information and link information. The road data is used for route search and map matching, and is also used when the searched travel route is displayed over the map data.

なお、本実施形態のナビゲーション装置１では、目的地までの走行経路についてはセンターサーバ１００から走行ルートＭを受信するので、経路探索に必要なデータを情報記憶装置５０の保存対象外とすることも可能である。
この場合でも、センターサーバ１００に走行経路の探索を要求しないで、現在位置周辺の地図と現在位置マークＮを画面表示したりする必要から、地図データやマップマッチング用の道路データについては保存される。
ただし、現在地をセンターサーバ１００に送信し周辺の地図データを受信して画面表示する場合には、地図データや道路データも情報記憶装置５０の保存対象外としてもよい。 In the navigation device 1 of the present embodiment, the travel route M from the center server 100 is received for the travel route to the destination, and therefore data necessary for the route search may be excluded from the storage target of the information storage device 50. Is possible.
Even in this case, map data and road data for map matching are saved because it is necessary to display the map around the current position and the current position mark N without requesting the center server 100 to search for a travel route. .
However, when the current location is transmitted to the center server 100 and the surrounding map data is received and displayed on the screen, the map data and the road data may not be stored in the information storage device 50.

図３は、走行ルートＭと復帰ルートの探索を行うセンターサーバ１００の構成を表したものである。
センターサーバ１００は、図３に示されるように、ＣＰＵ１０１、ＲＯＭ１０２、ＲＡＭ１０３、通信インターフェイス１０４、大容量の情報記憶装置１０５、その他の装置を備えたコンピュータシステムにより構成されている。
ＣＰＵ１０１は、センターサーバ１００全体の総括的な演算及び制御を行う。センターサーバ１００のＣＰＵ１０１は、ナビゲーション装置１のＣＰＵ２１に比べて、複数のナビゲーション装置１を対象にした経路探索や復帰ルート探索を可能にするため、より高速処理が可能なＣＰＵが使用される。また、複数のナビゲーション装置１からの要求に対応するため並列処理が行われる。 FIG. 3 shows the configuration of the center server 100 that searches for the travel route M and the return route.
As shown in FIG. 3, the center server 100 includes a computer system including a CPU 101, a ROM 102, a RAM 103, a communication interface 104, a large-capacity information storage device 105, and other devices.
The CPU 101 performs overall calculation and control of the center server 100 as a whole. The CPU 101 of the center server 100 uses a CPU that can perform higher-speed processing than the CPU 21 of the navigation device 1 in order to enable route search and return route search for a plurality of navigation devices 1. Further, parallel processing is performed in order to respond to requests from the plurality of navigation devices 1.

ＲＯＭ１０２には、目的地までの走行ルートＭや復帰ルートを探索してナビゲーション装置１に提供するナビゲーションプログラム等のナビゲーション機能に関する各種プログラムが格納されている。なお、これらのナビゲーション機能に関するプログラムについては、ＲＯＭ１０２ではなく、情報記憶装置１０５のプログラム格納領域に保存するようにしてもよい。
ＣＰＵ１０１は、ナビゲーションプログラム等の各種プログラムに従い処理を実行する。 The ROM 102 stores various programs related to a navigation function such as a navigation program that searches the travel route M to the destination and the return route and provides the navigation device 1 with the search. Note that these programs related to the navigation function may be stored in the program storage area of the information storage device 105 instead of the ROM 102.
The CPU 101 executes processing according to various programs such as a navigation program.

ＲＡＭ１０３は、図示しない入力装置から入力された情報を一時記憶すると共に、ナビゲーション装置１から送信された出発地と目的地、目的地まで経路探索した走行ルートＭ、走行ルートＭ上のリルート候補道路、リルート候補道路に対する復帰ポイントＲ、探索して送信済みの復帰ルートを、各ナビゲーション装置の装置ＩＤ毎に保存する。 The RAM 103 temporarily stores information input from an input device (not shown), the departure point and the destination transmitted from the navigation device 1, the travel route M searched for the route to the destination, the reroute candidate road on the travel route M, The return point R for the reroute candidate road and the return route that has been searched and transmitted are stored for each device ID of each navigation device.

通信インターフェイス１０４は、外部装置との間で各種情報の送受信を行うための通信手段として機能する。
例えば、通信インターフェイス１０４を介して、ナビゲーション装置１との間で、装置ＩＤ、出発地、目的地を受信して、探索した目的地までの走行ルートＭや復帰ルートを送信したり、復帰ルート探索の要求を受信して新たな復帰ルートを送信したりする。
また、通信インターフェイス１０４を介して、交通情報センタ等の各種外部装置と接続することで各地の渋滞情報、事故情報、工事情報、気象情報等を取得したり、また、後述する地図情報や道路情報の最新情報を取得する。 The communication interface 104 functions as a communication unit for transmitting / receiving various types of information to / from an external device.
For example, a device ID, a departure point, and a destination are received from the navigation device 1 via the communication interface 104, and a travel route M and a return route to the searched destination are transmitted, or a return route search is performed. Or a new return route is transmitted.
In addition, traffic information, accident information, construction information, weather information, etc. can be obtained by connecting to various external devices such as a traffic information center via the communication interface 104, and map information and road information described later. Get the latest information on.

情報記憶装置１０５は、地図データファイル、その他のデータファイル（例えば、渋滞情報）を格納している。
この情報記憶装置１０５は、一般的には、光学的記憶媒体であるＤＶＤ−ＲＯＭ、ＣＤ−ＲＯＭや磁気的記憶媒体であるハードディスクなどで構成されるが、光磁気ディスク、各種半導体メモリなどの各種情報記憶媒体で構成してもよい。
なお、書き換えが必要な情報については、書き換え可能なハードディスク、フラッシュメモリなどで構成し、その他の固定的な情報についてはＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭなどのＲＯＭを使用するようにしてもよい。 The information storage device 105 stores a map data file and other data files (for example, traffic jam information).
The information storage device 105 is generally composed of a DVD-ROM or CD-ROM that is an optical storage medium, a hard disk that is a magnetic storage medium, or the like. You may comprise with an information storage medium.
Information that needs to be rewritten may be constituted by a rewritable hard disk or flash memory, and other fixed information may be a ROM such as a CD-ROM or DVD-ROM.

地図データファイルには、ナビゲーションにおける地図表示、経路探索、経路案内に必要な各種データとして、地図データ、道路データ、目的地データ、案内地点データ、詳細目的地データ、その他のデータが記憶されている。
地図データとしては、全国道路地図、各地域の道路地図または住宅地図等が記憶されている。道路地図は、主要幹線道路、高速道路、細街路等の各道路と地上目標物（施設等）から構成される。
道路データは、各道路の位置と種類及び車線数及び各道路間の接続関係等の道路に関するデータで、ノード情報とリンク情報で構成される。この道路データは、走行ルートＭの探索や、走行ルートＭ上のリルート候補道路や復帰ポイントの決定、各リルート候補道路から復帰ポイントまでの復帰ルート探索に使用される。 The map data file stores map data, road data, destination data, guidance point data, detailed destination data, and other data as various data necessary for map display, route search, and route guidance in navigation. .
As map data, a national road map, a road map of each region, a house map, or the like is stored. The road map is composed of roads such as main arterial roads, expressways, narrow streets, and ground targets (facility etc.).
The road data is data regarding roads such as the position and type of each road, the number of lanes, and the connection relationship between the roads, and is composed of node information and link information. This road data is used for searching the travel route M, determining reroute candidate roads and return points on the travel route M, and searching return routes from each reroute candidate road to the return point.

これら、地図データファイルとして保存される各種データは、常に最新のデータに更新されると共に、ナビゲーション装置１が保存している地図データファイル５１よりも詳細な情報が保存されるようになっている。
また、上述したように、地図データファイル５１を備えていない、又は簡易データだけ備えているナビゲーション装置１に対して、センターサーバ１００は、探索した走行ルートＭや復帰ルートに加えて、走行ルートＭ周辺の地図データも送信する。 These various data stored as the map data file are always updated to the latest data, and more detailed information is stored than the map data file 51 stored in the navigation device 1.
Further, as described above, for the navigation device 1 that does not include the map data file 51 or includes only simple data, the center server 100 adds the travel route M in addition to the travel route M and the return route that have been searched. The surrounding map data is also transmitted.

このように構成されたセンターサーバ１００における、走行ルートＭに対して探索する復帰ルートの数や、探索のタイミングについて一般道の場合と高速道路の場合に分けて説明する。
（３)一般道の場合
（ａ)対象となるリルート候補道路
一般道の場合、探索した走行ルートＭ沿いに、退出可能な道路が対象となる。
但し、交差点内道路、計画道路などのリルート禁止道路は対象外とする
交差点内道路は、実際の道路ではなく、経路探索用の道路データとして交差点内に設定した道路である。
計画道路は、計画中の道路で未だ存在しない道路である。
なお、走行ルートＭから進入禁止の道路は、退出可能な道路ではないので対象外である。 The number of return routes to be searched for the travel route M and the search timing in the center server 100 configured as described above will be described separately for ordinary roads and highways.
(3) In the case of a general road (a) The target reroute candidate road In the case of a general road, a road that can be withdrawn along the searched travel route M is a target.
However, reroute-prohibited roads such as in-intersection roads and planned roads are excluded. In-intersection roads are not actual roads but roads set in the intersection as road data for route search.
The planned road is a road that has not yet been planned.
Note that roads that are prohibited from entering from the travel route M are not eligible because they are not releasable roads.

（ｂ）事前復帰ルート探索道路数
１回の復帰ルート探索で対象とするリルート候補道路の数αは、次のようにして決められている。
すなわち、１００ｍ間隔で十字路があり、ナビゲーション装置１が復帰ルート探索を要求してから復帰ルートの受信を完了するまでの時間Ｔに３０秒かかり、車両が車速５０ｋｍ／ｈで走行するものと仮定する。
以上の仮定によれば、復帰ルート探索を行う間に車両は距離Ｌ＝４１７ｍ移動することになるので、この距離Ｌよりも大きな距離Ｌｓ以内に存在する交差点を対象とする。本実施形態では、Ｌ＝４１７ｍなので、Ｌｓ以内の交差点として、最低でも４１７／１００＝４.１７以上の交差点、すなわち、５つの交差点を対象とする。
そして、各交差点は十字路を想定して２本ずつのリルート候補道路があると仮定し、α＝５×２＝１０本となる。 (B) Number of Prior Return Route Search Roads The number α of reroute candidate roads targeted for one return route search is determined as follows.
That is, it is assumed that there are crossroads at intervals of 100 m, it takes 30 seconds for the time T from when the navigation device 1 requests return route search to completion of reception of the return route, and the vehicle travels at a vehicle speed of 50 km / h. .
According to the above assumption, the vehicle moves a distance L = 417 m while performing a return route search. Therefore, an intersection existing within a distance Ls larger than the distance L is targeted. In this embodiment, since L = 417 m, intersections within 417/100 = 4.17 or more, that is, five intersections are targeted as intersections within Ls.
Then, assuming that each intersection has two reroute candidate roads assuming a crossroad, α = 5 × 2 = 10.

但し、リルート候補道路単位でα＝１０としたが、Ｔ字路の場合もあるので、交差点数β＝５単位でリルート候補道路を決定するようにしてもよい。
また、１０本は１例であり、検索時間の遅れや一度に送信するデータ量の増加を考慮した上で、より多くのリルート候補道路数α（例えば、α＝１４、２０等）、又は、交差点数β（例えば、β＝７、１０）を採用するようにしてもよい。 However, although α = 10 for each reroute candidate road, there may be a T-junction, so the reroute candidate road may be determined by the number of intersections β = 5.
In addition, 10 is an example, and in consideration of a delay in search time and an increase in the amount of data to be transmitted at a time, more reroute candidate roads α (for example, α = 14, 20, etc.), or The number of intersections β (for example, β = 7, 10) may be adopted.

（ｃ）復帰ポイントＲの設定
各リルート候補道路に所定距離だけ進んだ地点を出発地として復帰ルート探索をする場合の目的地となる点が復帰ポイントＲで、走行ルートＭ上に設定される。
但し、走行ルートＭに進入可能な道路と走行ルートＭとの交差点が対象となる。
なお、復帰ポイントＲは、必ずしも交差点でなくてもよく、当該交差点よりも目的地側のノードを復帰ポイントＲとすることも可能である。 (C) Setting of Return Point R A return point R is set as a destination point when a return route search is performed using a point that has traveled a predetermined distance on each reroute candidate road as a departure point.
However, an intersection between a road that can enter the travel route M and the travel route M is a target.
Note that the return point R does not necessarily have to be an intersection, and a node closer to the destination than the intersection can be used as the return point R.

今回の復帰ルート探索における復帰ポイントＲとしては、次回の復帰ルート探索の対象となるα個のリルート候補道路のうち、目的地に一番近いリルート候補道路と走行ルートＭとの交差点が設定される。
すなわち、交差点数βとすると、既に復帰ルートが受信済みである交差点数が（β−１）、今回対象となる交差点数がβ、次回対象となる交差点数がβとなるので、β＝５とすると車両現在位置から目的地側１４個目の交差点が、今回の復帰ルート探索における復帰ポイントに設定される。
なお、走行ルートＭ上において、車両現在位置から２β−１個先の交差点よりも手前に高速道路の入口が有る場合には、高速道路入口を復帰ポイントに設定する。
また、車両が目的地に近づいて、車両現在位置から目的地までの間に２β−１個の交差点が存在しない場合には、目的地を復帰ポイントに設定する。 As the return point R in the current return route search, an intersection between the reroute candidate road closest to the destination and the travel route M among the α reroute candidate roads to be searched for the next return route is set. .
That is, if the number of intersections is β, the number of intersections that have already received the return route is (β−1), the number of intersections targeted this time is β, and the number of intersections targeted next time is β, so β = 5 Then, the 14th intersection on the destination side from the current vehicle position is set as the return point in the current return route search.
In addition, on the travel route M, when there is an entrance to the highway before the intersection 2β−1 ahead of the current vehicle position, the expressway entrance is set as a return point.
When the vehicle approaches the destination and there are no 2β−1 intersections between the current vehicle position and the destination, the destination is set as a return point.

（ｄ）復帰ルート探索のタイミング
ナビゲーション装置１がセンターサーバ１００に復帰ルート探索の要求をするタイミングは次の通りでる。
すなわち、ナビゲーション装置１は、車両現在位置から目的地側の（未通過の）リルート候補道路、又は復帰ルートの数がα未満となった時点で、復帰ルート探索の要求をする。実際には、目的地から手前側にα本目の復帰ルートに対応するリルート候補道路の交差点通過と同時に、復帰ルート探索の要求がなされる。 (D) Return Route Search Timing The timing at which the navigation device 1 requests the center server 100 for return route search is as follows.
In other words, the navigation device 1 makes a return route search request when the number of reroute candidate roads (unpassed) on the destination side from the current vehicle position or the number of return routes becomes less than α. Actually, a return route search request is made simultaneously with passing the intersection of the reroute candidate road corresponding to the αth return route from the destination to the near side.

図４は、一般道路における復帰ルートの要求タイミングと、復帰ルート探索の関係を表したものである。
図４では、探索した走行ルートＭを直線で表し、リルート候補道路を走行ルートＭからの矢印で表している。
ナビゲーション装置１は、図４（ａ)に示されるように、車両の現在位置Ｎの先に、リルート候補道路Ａ１〜Ｊ１に対する復帰ルートをセンターサーバ１００から受信済みであるものとする。
この場合の各リルート候補道路Ａ１〜Ｊ１に対する復帰ポイントＲ１は、次の通りである。すなわち、最も目的地側のリルート候補道路Ｉ１（Ｊ１）の先に存在するα個（＝１０個）のリルート候補道路のうち、最も目的地側のリルート候補道路と走行ルートＭとの交差点が復帰ポイントＲ１に設定されている。
そして、センターサーバ１００では、各リルート候補道路Ａ１〜Ｊ１から復帰ポイントＲ１までの復帰ルートａ１〜ｊ１を探索し、ナビゲーション装置１に送信済みとなっている。 FIG. 4 shows the relationship between return route request timing on a general road and return route search.
In FIG. 4, the searched traveling route M is represented by a straight line, and the reroute candidate road is represented by an arrow from the traveling route M.
As shown in FIG. 4A, the navigation device 1 has received the return route for the reroute candidate roads A1 to J1 from the center server 100 ahead of the current position N of the vehicle.
The return points R1 for the reroute candidate roads A1 to J1 in this case are as follows. That is, of the α (= 10) reroute candidate roads existing ahead of the reroute candidate road I1 (J1) closest to the destination, the intersection of the reroute candidate road closest to the destination and the travel route M is restored. It is set at point R1.
The center server 100 searches for the return routes a1 to j1 from the reroute candidate roads A1 to J1 to the return point R1, and has already been transmitted to the navigation device 1.

そして車両が走行ルートＭを走行し、図４（ｂ）に示されるように、現在位置Ｎがリルート候補道路Ａ１（Ｂ１）を通過すると、未通過のリルート候補道路（残りの復帰ルート）の数がα（＝１０）未満となるので、ナビゲーション装置１からセンターサーバ１００に復帰ルート探索が要求される。
センターサーバ１００では、復帰ルート探索要求を受信すると、既に復帰ルート探索済みのリルート候補道路Ａ１〜Ｊ１以降に存在する、α個のリルート候補道路を今回のリルート候補道路Ａ２〜Ｊ２とする。
また、今回の復帰ルート探索における復帰ポイントＲ２として、次回の復帰ルート探索の対象となり、目的地に一番近いリルート候補道路の交差点が設定される。
そして、センターサーバ１００は、今回の復帰ルート探索において、各リルート候補道路Ａ２〜Ｊ２に対応する復帰ポイントＲ２までの各復帰ルートａ２〜ｊ２を探索して、ナビゲーション装置１に送信する。 Then, when the vehicle travels on the travel route M and the current position N passes through the reroute candidate road A1 (B1) as shown in FIG. 4B, the number of reroute candidate roads (remaining return routes) that have not passed. Is less than α (= 10), the return route search is requested from the navigation device 1 to the center server 100.
When receiving the return route search request, the center server 100 sets α reroute candidate roads existing after the reroute candidate roads A1 to J1 that have already been searched for the return route as the current reroute candidate roads A2 to J2.
Further, as the return point R2 in the current return route search, the intersection of the reroute candidate road that is the target of the next return route search and is closest to the destination is set.
Then, the center server 100 searches each return route a2 to j2 up to the return point R2 corresponding to each reroute candidate road A2 to J2 in the current return route search, and transmits it to the navigation device 1.

以下同様にして、現在位置Ｎがリルート候補道路Ａ２（Ｂ２）を通過すると、ナビゲーション装置１からセンターサーバ１００に復帰ルート探索の要求がだされ、図４（ｃ）に示されるように、リルート候補道路Ａ３〜Ｊ３を対象として復帰ポイントＲ３までの復帰ルートａ３〜ｊ３が探索され、ナビゲーション装置１に送信される。 Similarly, when the current position N passes the reroute candidate road A2 (B2), a request for return route search is issued from the navigation apparatus 1 to the center server 100, and as shown in FIG. Return routes a3 to j3 to the return point R3 are searched for the roads A3 to J3, and transmitted to the navigation device 1.

（４）高速道路の場合
（ａ)対象となるリルート候補道路
高速道路の場合も一般道路と同様に、走行ルートＭ沿いから退出可能な道路が対象となり、リルート禁止道路は対象外となる。
但し、高速道路の場合、リルート禁止道路には交差点内道路が含まれず、サービスエリアやパーキングエリア内の道路が含まれる。 (4) In the case of an expressway (a) The target reroute candidate road As in the case of a general road, the target reroute candidate road is a road that can exit from the route along the travel route M, and the reroute prohibited road is excluded.
However, in the case of an expressway, the reroute prohibited road does not include the road in the intersection, but includes the road in the service area and the parking area.

（ｂ）事前復帰ルート探索道路数
次のインターチェンジ（ＩＣ）、または、ジャンクション（ＪＣＴ）の走行ルートＭ以外の道路で、原則としてα＝１であるが、
ＩＣやＪＣＴが１ｋｍ以内で連続する場合は、最初のＩＣ、ＪＣＴから１ｋｍ以内に存在するＩＣやＪＣＴの走行ルートＭ以外の道路も対象とする。 (B) Number of roads to be searched for in advance return route For roads other than the driving route M of the next interchange (IC) or junction (JCT), α = 1 in principle.
When the IC or JCT continues within 1 km, roads other than the driving route M of the IC or JCT existing within 1 km from the first IC or JCT are also targeted.

（ｃ）復帰ポイントＲの設定
高速道路の場合には、全てのリルート候補道路に対して目的地が復帰ポイントＲに設定される。これにより、復帰ルート探索では、各リルート候補道路から目的地までの全ルート探索が実行される。 (C) Setting of Return Point R In the case of an expressway, the destination is set as the return point R for all reroute candidate roads. Thereby, in the return route search, the entire route search from each reroute candidate road to the destination is executed.

但し、走行ルートＭの途中に高速道路区間が存在している場合で、高速道路の出口から目的地までの一般道路上にリルート候補道路が存在する場合には、高速道路出口以降のリルート候補道路と走行ルートＭとの交差点を復帰ポイントＲに設定するようにしてもよい。例えば、高速道路の出口から数えてα個目のリルート候補道路の交差点、又はβ個めの交差点を復帰ポイントにする。 However, if there is an expressway section in the middle of the driving route M, and there is a reroute candidate road on a general road from the expressway exit to the destination, the reroute candidate road after the expressway exit And the intersection with the travel route M may be set as the return point R. For example, the return point is the intersection of the αth reroute candidate road counted from the exit of the expressway or the βth intersection.

（ｄ）復帰ルート探索のタイミング
車両の現在位置が、次のＩＣやＪＣＴの手前γｋｍとなった時点でナビゲーション装置１からセンターサーバ１００に復帰ルート探索要求をだす。
例えば、一般道の場合と同様にナビゲーション装置１が復帰ルート探索を要求してから復帰ルートの受信を完了するまでの時間Ｔに３０秒かかり、車両が車速１００ｋｍ／ｈで走行する場合を想定すると、時間Ｔ＝３０秒の間に車両は８３３ｍ移動するので、γ＝１ｋｍとなる。 (D) Return Route Search Timing When the current position of the vehicle is γ km before the next IC or JCT, a request for return route search is issued from the navigation device 1 to the center server 100.
For example, as in the case of a general road, it is assumed that the time T from when the navigation device 1 requests a return route search to the completion of reception of the return route takes 30 seconds and the vehicle travels at a vehicle speed of 100 km / h. Since the vehicle moves 833 m during the time T = 30 seconds, γ = 1 km.

図５は、高速道路における復帰ルートの要求タイミングと、復帰ルート探索の関係を表したものである。
図５においても探索した走行ルートＭを直線で表し、リルート候補道路（ＩＣやＪＣＴ）を走行ルートＭからの矢印で表している。
ナビゲーション装置１は、図５に示されるように、車両の現在位置Ｎが、復帰ルートを受信していない次のＩＣ等の手前１ｋｍに到達すると、センターサーバ１００に復帰ルート探索を要求する。
センターサーバ１００は、最初のリルート候補道路を含め１ｋｍ以内に存在するＩＣやＪＣＴを今回のリルート候補道路とし、復帰ポイントＲ＝目的地までの経路探索を行い、ナビゲーション装置１に送信する。 FIG. 5 shows the relationship between return route request timing on a highway and return route search.
In FIG. 5, the searched traveling route M is represented by a straight line, and the reroute candidate road (IC or JCT) is represented by an arrow from the traveling route M.
As shown in FIG. 5, the navigation device 1 requests the center server 100 to search for a return route when the current position N of the vehicle reaches 1 km before the next IC or the like that has not received the return route.
The center server 100 uses the IC or JCT existing within 1 km including the first reroute candidate road as the current reroute candidate road, performs a route search to the return point R = the destination, and transmits it to the navigation device 1.

次に、以上のように構成されたセンターサーバ１００とナビゲーション装置１における経路探索と経路案内処理について説明する。
図６、７は経路探索処理と経路案内処理の内容について表したフローチャートである。
ナビゲーション装置のＣＰＵ２１は、出発地と目的地を取得する（ステップ１０）。出発地と目的地は、ユーザが入力装置４１から入力した出発地、目的地を取得する。但し、ユーザ入力が現在値を指定した場合、又は、出発地の入力がない場合、ＣＰＵ２１は、現在位置検出装置１０で検出した車両の現在位置を出発地として取得する。
ＣＰＵ２１は、取得した出発地、目的地を、自装置の装置ＩＤと共にセンターサーバ１００に送信することで、目的地までの走行ルートＭの探索要求と、最初の復帰ルート探索要求（復帰ルートの要求）をする（ステップ１１）。 Next, route search and route guidance processing in the center server 100 and the navigation device 1 configured as described above will be described.
6 and 7 are flowcharts showing the contents of route search processing and route guidance processing.
The CPU 21 of the navigation device acquires the departure place and the destination (step 10). As the departure point and destination, the departure point and destination input by the user from the input device 41 are acquired. However, when the current value is specified by the user input or when there is no departure place input, the CPU 21 acquires the current position of the vehicle detected by the current position detection device 10 as the departure place.
The CPU 21 transmits the acquired starting point and destination together with the device ID of the own device to the center server 100, so that the search request for the travel route M to the destination and the first return route search request (return route request) (Step 11).

センターサーバ１００のＣＰＵ１０１は、ナビゲーション装置１から装置ＩＤ、出発地、目的地を受信すると、ＲＡＭ１０３に装置ＩＤを検索キーとする領域を確保し、当該領域に出発地と目的地を記憶する（ステップ５０）。
以後、センターサーバ１００では、装置ＩＤに基づいてナビゲーション装置１を特定し、当該ナビゲーション装置１に対する復帰ルート探索を行う。 When the CPU 101 of the center server 100 receives the device ID, the departure place, and the destination from the navigation device 1, the CPU 101 secures an area using the apparatus ID as a search key in the RAM 103 and stores the departure place and the destination in the area (step). 50).
Thereafter, the center server 100 identifies the navigation device 1 based on the device ID, and performs a return route search for the navigation device 1.

次にＣＰＵ１０１は、出発地から目的地までの走行ルートＭを探索する（ステップ５１）。
そして、最初の復帰ルート探索要求に基づいて復帰ルート探索を行う。すなわち、ＣＰＵ１０１は、探索した走行ルートＭ上に、出発地から最初の復帰ポイントＲ１を決定する（ステップ５２）。本実施形態における最初の復帰ポイントＲ１は、全リルート候補道路のうち、出発地から数えて２α（＝２０）本めのリルート候補道路と走行ルートＭとの交差点である。 Next, the CPU 101 searches for a travel route M from the departure place to the destination (step 51).
Then, a return route search is performed based on the first return route search request. That is, the CPU 101 determines the first return point R1 from the departure place on the searched traveling route M (step 52). The first return point R1 in the present embodiment is an intersection of the 2α (= 20) reroute candidate road and the travel route M counted from the departure place among all the reroute candidate roads.

次に、ＣＰＵ１０１は、復帰ルート探索の対象となるリルート候補道路Ａ１〜Ｊ１を決定する（ステップ５３）。このリルート候補道路Ａ１〜Ｊ１は、出発地から数えてα（＝１０）本のリルート候補道路が対象となる。
そして、ＣＰＵ１０１、各リルート候補道路Ａ１〜Ｊ１から復帰ポイントＲ１までの各復帰ルートａ１〜ｊ１を探索し、当該探索要求を受信した装置ＩＤに対してＲＡＭ１０３に確保されている領域に保存する（ステップ５４）。
ＣＰＵ１０１は、探索した走行ルートＭと復帰ルートａ１〜ｊ１を、装置ＩＤに対応するナビゲーション装置１（車載機）に配信する（ステップ５５）。なお、ＣＰＵ１０１は、復帰ルートａ１〜ｊ１に対応するリルート候補道路Ａ１〜Ｊ１を併せてナビゲーション装置１に送信するようにしてもよい。 Next, the CPU 101 determines reroute candidate roads A1 to J1 to be searched for a return route (step 53). The reroute candidate roads A1 to J1 are targeted for α (= 10) reroute candidate roads counted from the departure place.
Then, the CPU 101 searches for each return route a1 to j1 from each of the reroute candidate roads A1 to J1 to the return point R1, and stores it in an area secured in the RAM 103 for the device ID that has received the search request (step 54).
The CPU 101 distributes the searched traveling route M and return routes a1 to j1 to the navigation device 1 (onboard device) corresponding to the device ID (step 55). The CPU 101 may transmit the reroute candidate roads A1 to J1 corresponding to the return routes a1 to j1 to the navigation device 1 together.

一方、ナビゲーション装置１では、センターサーバ１００から配信される走行ルートＭと復帰ルートａ１〜ｊ１を受信すると、ＲＡＭ２４の所定領域に保存する（ステップ１２）。 On the other hand, when the navigation device 1 receives the travel route M and the return routes a1 to j1 distributed from the center server 100, the navigation device 1 stores them in a predetermined area of the RAM 24 (step 12).

なお、本実施形態のナビゲーション装置１は、地図データファイル５１を備えているため、センターサーバ１００からは地図データを受信することはないが、地図データファイル５１を備えないナビゲーション装置１の場合には、走行ルートＭ及び復帰ルートａ１〜ｊ１周辺の地図データも受信する。
この場合、地図データファイル５１を備えないナビゲーション装置１は、ステップ１１において、装置ＩＤ等をセンターサーバ１００に送信する際に、経路周辺の地図データを要求する。地図データの要求は、自装置の構成として地図データファイルを有しないことを示すデータを送信する。
そしてセンターサーバ１００は、地図データ要求も併せて受信すると、ＲＡＭ１０３の装置ＩＤに対応する領域に地図データの送付が必要であることを示すフラグを立て、以降の復帰ルート探索要求が来る毎に探索した復帰ルートを送信する毎に、フラグが立っているか確認し、立っていれば周辺の地図データを送信する。この場合、復帰ルートａ１〜ｊ１と周辺地図データの送信と同様に、走行ルートＭ周辺の地図データについても分割して送信するようにしてもよい。 In addition, since the navigation apparatus 1 of this embodiment is provided with the map data file 51, it does not receive map data from the center server 100, but in the case of the navigation apparatus 1 that does not include the map data file 51. The map data around the travel route M and the return routes a1 to j1 are also received.
In this case, the navigation device 1 that does not include the map data file 51 requests map data around the route when transmitting the device ID or the like to the center server 100 in step 11. In response to the request for map data, data indicating that the apparatus does not have a map data file is transmitted.
When the center server 100 also receives the map data request, the center server 100 sets a flag indicating that the map data needs to be sent in the area corresponding to the device ID of the RAM 103, and searches each time a subsequent return route search request comes. Each time the return route is sent, it is checked whether the flag is set, and if it is set, the surrounding map data is sent. In this case, similarly to the transmission of the return routes a1 to j1 and the surrounding map data, the map data around the traveling route M may be divided and transmitted.

また、地図データファイル５１を備えるナビゲーション装置１の場合についても、自装置の地図データファイル５１のバージョン情報を送信することで、センターサーバ１００から最新の地図データとの差分を受信することで、地図データファイル５１を更新するようにしてもよい。 In the case of the navigation apparatus 1 including the map data file 51, the map information file 51 of the own apparatus is transmitted to receive the difference from the latest map data from the center server 100 by transmitting the map information file 51. The data file 51 may be updated.

ナビゲーション装置１では、センターサーバ１００から受信した走行ルートＭと復帰ルートに従い、目的地到着まで走行経路の案内と、復帰ルート探索の要求を繰り返す（ステップ１３−１〜１３−２）。
すなわちナビゲーション装置１のＣＰＵ２１は、現在位置検出装置１０で検出した車両の現在位置周辺の地図をディスプレイ４２に表示すると共に、受信した走行ルートＭと現在位置マークＮを表示する。
そして、ＣＰＵ２１は、走行ルートＭを外れて車両がリルート候補道路に進入したか否かを監視する（ステップ１４）。
リルート候補道路に進入していなければ（ステップ１４；Ｎ）、ＣＰＵ２１は、ディスプレイ４２の表示や音声により走行ルートＭの案内を行う（ステップ１５）。 In the navigation device 1, according to the travel route M and the return route received from the center server 100, the travel route guidance and the return route search request are repeated until the destination arrives (steps 13-1 to 13-2).
That is, the CPU 21 of the navigation device 1 displays a map around the current position of the vehicle detected by the current position detection device 10 on the display 42 and also displays the received travel route M and current position mark N.
Then, the CPU 21 monitors whether the vehicle has departed from the travel route M and entered the reroute candidate road (step 14).
If the vehicle has not entered the reroute candidate road (step 14; N), the CPU 21 guides the travel route M by display or voice on the display 42 (step 15).

ＣＰＵ２１は、事前復帰ルート探索のタイミングになったか否かを判断する（ステップ１６）。
すなわちＣＰＵ２１は、図４、５で説明したように、一般道路であれば車両現在位置から目的地側の（未通過の）リルート候補道路、又は復帰ルートの数がα未満となったか否かを判断し、高速道路であれば次のＩＣやＪＣＴの手前γｋｍとなったか否かについて判断される。 The CPU 21 determines whether or not it is time to search for a prior return route (step 16).
That is, as described with reference to FIGS. 4 and 5, the CPU 21 determines whether or not the number of reroute candidate roads on the destination side (unpassed) from the current vehicle position or the number of return routes is less than α if it is a general road. If it is a highway, it is determined whether or not the next IC or JCT is γ km before the next IC.

そして、事前復帰ルート探索のタイミングでなければ（ステップ１６；Ｎ）、ＣＰＵ２１は、ステップ１４にもどり目的地までループを繰り返す。
事前復帰ルート探索のタイミングになった場合（ステップ１６；Ｙ）、ＣＰＵ２１は、装置ＩＤ、現在位置、復帰ルート要求を送信することで、その旨（次の復帰ルート探索タイミングであること）をセンターサーバ１００に通知する（ステップ１７）。 If it is not the timing for searching for the previous return route (step 16; N), the CPU 21 returns to step 14 and repeats the loop to the destination.
When it is time to search for a previous return route (step 16; Y), the CPU 21 sends a device ID, current position, and return route request to indicate that (the next return route search timing). The server 100 is notified (step 17).

一方、案内中の車両が走行ルートＭから外れてリルート候補道路（復帰ルート）に進入した場合（ステップ１４；Ｙ）、ナビゲーション装置１のＣＰＵ２１は、案内対象を走行ルートＭから進入した復帰ルートに切り換えてユーザに案内する（ステップ１８）。
そして、ＣＰＵ２１は、装置ＩＤ、現在位置、復帰ルート要求を送信することで、その旨（ルート外れであること）をセンターサーバ１００に通知する（ステップ１７）。
なお、ステップ１７において、次の復帰ルート探索タイミングであることの通知も、ルート外れであることの通知も同一のデータをセンターサーバ１００に送信するが、現在位置が走行ルートＭ上にあるか否かにより両者が区別されている。 On the other hand, when the guided vehicle deviates from the travel route M and enters the reroute candidate road (return route) (step 14; Y), the CPU 21 of the navigation device 1 changes the guidance target to the return route that has entered from the travel route M. Switch to guide the user (step 18).
Then, the CPU 21 transmits a device ID, a current position, and a return route request, thereby notifying the center server 100 of that fact (step 17).
In step 17, the same data is transmitted to the center server 100 for both the notification that it is the next return route search timing and the notification that the route is off, but whether the current position is on the travel route M or not. Both are distinguished by.

センターサーバ１００では、ナビゲーション装置１から復帰ルート要求等を受信すると、ＣＰＵ１０１が、受信した現在位置を装置ＩＤに対応するＲＡＭ１０３の領域に保存し（ステップ５６）、当該装置ＩＤに対する復帰ルート探索を行う。
すなわちＣＰＵ１０１は、受信したナビゲーション装置１の現在位置が、当該装置ＩＤに対応する走行ルートＭ上にあるか、送信済みのリルート候補道路（復帰ルート）上にあるか否かを判断することで走行ルートＭ外れか否かを判断する（ステップ５７）。 In the center server 100, when a return route request or the like is received from the navigation device 1, the CPU 101 stores the received current position in the area of the RAM 103 corresponding to the device ID (step 56), and performs a return route search for the device ID. .
That is, the CPU 101 travels by determining whether the received current position of the navigation device 1 is on the travel route M corresponding to the device ID or on the transmitted reroute candidate road (return route). It is determined whether or not the route M is off (step 57).

走行ルートＭ外れでない場合、すなわち、現在位置が走行ルートＭ上にある場合（ステップ５７；Ｎ）、ＣＰＵ１０１は、ＲＡＭ１０３に保存されている、ナビゲーション装置１に送信済みの復帰ルートと対応するリルート候補道路を当該装置ＩＤで確認し、走行ルートＭ上で、新しい復帰ポイントＲｎと、リルート候補道路Ａｎ〜Ｊｎを決定する（ステップ５８）。
一方、走行ルートＭ外れである場合、すなわち、現在位置が走行ルートＭ上になく送信済みの復帰ルート上にある場合（ステップ５７；Ｙ）、ＣＰＵ１０１は、車両が位置している復帰ルートと、当該復帰ルートに対する復帰ポイントＲｎから先の走行ルートＭとを結合したルートを新しいルートとし、この新しいルート上で、復帰ポイントＲｎと、リルート候補道路Ａｎ〜Ｊｎを決定する（ステップ５９）。 If it is not off the driving route M, that is, if the current position is on the driving route M (step 57; N), the CPU 101 stores a reroute candidate corresponding to the return route stored in the RAM 103 and transmitted to the navigation device 1. The road is confirmed by the device ID, and a new return point Rn and reroute candidate roads An to Jn are determined on the travel route M (step 58).
On the other hand, when it is out of the travel route M, that is, when the current position is not on the travel route M but on the transmitted return route (step 57; Y), the CPU 101 determines that the return route where the vehicle is located, A route obtained by combining the return point Rn for the return route and the previous travel route M is set as a new route, and the return point Rn and reroute candidate roads An to Jn are determined on the new route (step 59).

次にＣＰＵ１０１は、決定した各リルート候補道路Ａｎ〜Ｊｎから、復帰ポイントＲｎまでの復帰ルートａｎ〜ｊｎを探索し、ＲＡＭ１０３の当該装置ＩＤに対応する領域に保存する（ステップ６０）。
そしてＣＰＵ１０１は、探索した新たな復帰ルートａｎ〜ｊｎを、装置ＩＤに対応するナビゲーション装置１（車載機）に配信し（ステップ６１）、リターンする。 Next, the CPU 101 searches the determined reroute candidate roads An to Jn for return routes an to jn to the return point Rn, and stores them in the area corresponding to the device ID in the RAM 103 (step 60).
Then, the CPU 101 distributes the searched new return routes an to jn to the navigation device 1 (vehicle equipment) corresponding to the device ID (step 61), and returns.

ナビゲーション装置１では、センターサーバ１００から、新たな復帰ルート探索ａｎ〜ｊｎを受信すると、ＣＰＵ２１は、ＲＡＭ２４に保存し（ステップ１９）、目的地到着までステップ１４にもどりループを繰り返す。
なお、ナビゲーション装置１は、ステップ１７でセンターサーバ１００に復帰ルート要求等を通知してから、復帰ルートを受信するまでの間においても、車両の現在位置に対応した走行ルートＭ、又は復帰ルートの案内を継続している。 When the navigation device 1 receives new return route searches an to jn from the center server 100, the CPU 21 stores them in the RAM 24 (step 19) and returns to step 14 until the destination arrives and repeats the loop.
In addition, the navigation device 1 notifies the center server 100 of the return route request or the like in step 17 until the return route is received until the travel route M or the return route corresponding to the current position of the vehicle. The guidance is continued.

ナビゲーション装置１は、目的地に到着した場合に、走行経路（走行ルートＭ、復帰ルート）の案内を終了するが、目的地に到着したことを装置ＩＤと共にセンターサーバ１００に通知するようにしてもよい。
この場合センターサーバ１００は、ナビゲーション装置１から目的地到着の通知を受領した時点で、当該装置ＩＤに対してＲＡＭ１０３に保存していた走行ルートＭやリルート候補道路等のデータを消去する。
但し、センターサーバ１００は、目的地に最も近いリルート候補道路に対する復帰ルートをナビゲーション装置１に送信した時点で、当該ＩＤに対する保存データを削除することで、ナビゲーション装置１との間で目的地到着の通知の送受信をしないようにすることも可能である。 When the navigation device 1 arrives at the destination, the navigation device 1 ends the guidance of the travel route (travel route M, return route), but may notify the center server 100 together with the device ID that the destination has been reached. Good.
In this case, when the center server 100 receives the destination arrival notification from the navigation device 1, the center server 100 deletes data such as the travel route M and the reroute candidate road stored in the RAM 103 for the device ID.
However, when the center server 100 transmits the return route for the reroute candidate road closest to the destination to the navigation device 1, the center server 100 deletes the stored data for the ID so that the destination arrival with the navigation device 1 is reached. It is also possible not to send / receive notifications.

以上説明したように本実施形態のセンターサーバ１００によれば、目的地までの走行経路（走行ルートＭ）を探索するとともに、復帰ルート探索要求を受ける毎に、走行ルートＭから車両が外れた場合の復帰ルート探索を所定本数単位で行い、ナビゲーション装置１に送信する。
一方、ナビゲーション装置１では、センターサーバ１００から受信した走行ルートＭの案内を行い、車両が走行ルートＭから外れたら、ただちに受信済みの復帰ルートに切り換えて案内を行う。そして、走行ルートＭ上を走行中に未だ通過していない受信済みの復帰ルートが所定数以下となった場合、及び、車両が走行ルートＭから外れた場合に、センターサーバ１００に復帰ルート探索要求をする。 As described above, according to the center server 100 of the present embodiment, when a travel route (travel route M) to the destination is searched, and the vehicle departs from the travel route M every time a return route search request is received. The return route search is performed in units of a predetermined number and transmitted to the navigation device 1.
On the other hand, the navigation device 1 provides guidance for the travel route M received from the center server 100, and when the vehicle deviates from the travel route M, it immediately switches to the received return route for guidance. Then, when the number of received return routes that have not yet passed while traveling on the travel route M becomes less than a predetermined number, and when the vehicle deviates from the travel route M, a return route search request is sent to the center server 100. do.

これにより、ナビゲーション装置１は、車両が走行ルートＭから外れた場合でもタイムラグなく、直ちに復帰ルートに切り換えて案内を継続することができる。
そして、復帰ルート探索で探索する復帰ルート数（リルート候補道路数）αを、ナビゲーション装置１が次の復帰ルート探索を要求してから復帰ルートの受信を完了するまでの時間Ｔの間に車両が走行すると想定される距離Ｌよりも長い距離Ｌｓ分の数に設定している。このため、ナビゲーション装置１は常に前方に復帰ルートがある状態で走行ルートＭを案内することができ、ルートを外れた際に復帰ルートが無いために案内が中断してしまうということがない。
また、復帰ルートを所定本数αずつに分割してナビゲーション装置１に送信しているため、ナビゲーション装置１とセンターサーバ１００間でのデータの送受信量を少なくすることができる。 Thereby, even when the vehicle deviates from the travel route M, the navigation device 1 can immediately switch to the return route and continue the guidance without time lag.
Then, the number of return routes (number of reroute candidate roads) α to be searched for in the return route search is determined by the vehicle during the time T from when the navigation device 1 requests the next return route search until the return route reception is completed. It is set to the number of distances Ls longer than the distance L assumed to travel. For this reason, the navigation apparatus 1 can always guide the traveling route M with a return route ahead, and the guidance is not interrupted because there is no return route when the route deviates.
In addition, since the return route is divided into a predetermined number α and transmitted to the navigation device 1, the amount of data transmitted and received between the navigation device 1 and the center server 100 can be reduced.

以上、本発明のセンターサーバ１００とナビゲーション装置１における１実施形態について説明したが、本発明は説明した実施形態に限定されるものではなく、各請求項に記載した範囲において各種の変形を行うことが可能である。
例えば、説明した実施形態では、復帰ルート探索する復帰ルートの数をαに固定したが、目的地に一番近い送信済みの復帰ルートに対応するリルート候補道路からの距離Ｌｓ（上述の距離）を求め、この距離Ｌｓ内に存在するリルート候補道路を、今回の復帰ルート探索の対象としてもよい。
この場合の復帰ポイントとしては、目的地に一番近い送信済みの復帰ルートに対応するリルート候補道路から距離２Ｌｓの次、又は手前に存在するリルート候補道路と走行ルートＭとの交差点とする。
この変形例によれば、探索する復帰ルートの数は、走行する地域の道路状況によって変化し、交差点の少ない山間部等では少なくなり、交差点が多い都会では多くなる。 As mentioned above, although one embodiment in the center server 100 and the navigation apparatus 1 of the present invention has been described, the present invention is not limited to the described embodiment, and various modifications are made within the scope described in each claim. Is possible.
For example, in the embodiment described above, the number of return routes to be searched for return routes is fixed to α, but the distance Ls (the above-mentioned distance) from the reroute candidate road corresponding to the transmitted return route closest to the destination is set. The reroute candidate road existing within the distance Ls may be used as a target for the current return route search.
In this case, the return point is an intersection between the reroute candidate road and the travel route M that exists next to or in front of the distance 2Ls from the reroute candidate road corresponding to the transmitted return route closest to the destination.
According to this modification, the number of return routes to be searched varies depending on the road conditions in the traveling region, and decreases in mountainous areas where there are few intersections, and increases in cities where there are many intersections.

説明した実施形態では、時間Ｔ内に車両が走行する想定距離Ｌとして、一般道の場合に車速を５０ｋｍ／ｈを想定して決定したが、車速については、ナビゲーション装置１から復帰ルート探索要求時の車速を受信し、走行ルートＭの想定車速を修正するようにしてもよい。ナビゲーション装置１では、車速として、復帰ルート探索要求時の車速や、復帰ルート探索要求前のＷｋｍの平均車速を送信する。 In the embodiment described above, the vehicle speed is determined by assuming 50 km / h in the case of a general road as the assumed distance L that the vehicle travels within the time T. However, the vehicle speed is determined when the return route search is requested from the navigation device 1. The estimated vehicle speed of the travel route M may be corrected. The navigation device 1 transmits the vehicle speed at the time of the return route search request and the average vehicle speed of Wkm before the return route search request as the vehicle speed.

また説明した実施形態において、センターサーバ１００では、ナビゲーション装置１から復帰ルート探索要求がある毎に、次の復帰ルートを探索してナビゲーション装置に送信するようにした。これに対して、出発地と目的地を受信して走行ルートＭを探索した際に、前記復帰ルートを探索してＲＡＭ１０３に保存しておき、ナビゲーション装置１から復帰ルート探索要求を受信した場合に、ナビゲーション装置１を搭載した車両が走行ルートＭから外れていなければ、探索済みの復帰ルートを所定数だけナビゲーション装置１に送信するようにしてもよい。
なお、ナビゲーション装置１に最初に走行ルートＭを送信する際には、上述した実施形態と同様に所定本数（実施形態ではα）分だけ復帰ルート探索をし、走行ルートＭと復帰ルートをナビゲーション装置１に送信した後に、改めて残りの全復帰ルートの復帰ルート探索を行いＲＡＭ１０３に保存するようにしてもよい。 In the embodiment described above, the center server 100 searches for the next return route and transmits it to the navigation device every time there is a return route search request from the navigation device 1. On the other hand, when a departure route and a destination are received and a travel route M is searched, the return route is searched and stored in the RAM 103, and a return route search request is received from the navigation device 1. If the vehicle on which the navigation device 1 is mounted is not deviated from the travel route M, a predetermined number of return routes that have been searched may be transmitted to the navigation device 1.
When the travel route M is transmitted to the navigation device 1 for the first time, the return route search is performed by a predetermined number (α in the embodiment) as in the above-described embodiment, and the travel route M and the return route are determined as the navigation device. After the transmission to 1, the return route search for all the remaining return routes may be performed again and stored in the RAM 103.

また、説明した実施形態では、車両に搭載されるナビゲーション装置１を例に説明したが、ナビゲーション機能を搭載した携帯電話、ＰＤＡ、スマートフォン、ノート型パソコン等の各種端末装置をナビゲーション装置１として適用される場合には、当該装置のＩＤ毎に走行ルートＭと復帰ルートの探索、送信を行うようにしてもよい。 In the embodiment described above, the navigation device 1 mounted on a vehicle has been described as an example. However, various terminal devices such as a mobile phone, a PDA, a smartphone, and a laptop computer equipped with a navigation function are applied as the navigation device 1. In this case, the travel route M and the return route may be searched and transmitted for each ID of the device.

１ナビゲーション装置
１０現在位置検出装置
２０情報処理制御装置
２１ＣＰＵ
４０入出力装置
５０情報記憶装置
１００センターサーバ
１０１ＣＰＵ
１０３ＲＡＭ
１０４通信インターフェイス
１０５情報記憶装置 DESCRIPTION OF SYMBOLS 1 Navigation apparatus 10 Current position detection apparatus 20 Information processing control apparatus 21 CPU
40 I / O device 50 Information storage device 100 Center server 101 CPU
103 RAM
104 communication interface 105 information storage device

Claims

A route search device in a navigation system comprising a route search device that searches for a travel route to a destination, and a route guide device that guides the travel route searched by the route search device,
Obtaining means for obtaining a starting point and a destination from the route guidance device;
Route search means for searching for a travel route from the acquired starting point to the destination;
Road identification means for identifying a releasable road that can be retreated from the searched travel route;
On the travel route, return point setting means for setting a return point on the destination side with respect to the identified exitable road,
Return route search means for searching for a return route from the intersection of the identified exitable road with the travel route to the set return point;
Request accepting means for accepting a return route request from the route guidance device;
A route transmitting means for transmitting the searched travel route to the route guidance device and transmitting the predetermined number of searched return routes when a request for the return route is received ;
The route transmission means is determined based on a distance Ls that is greater than a distance L that the vehicle is supposed to travel from when the route guidance device requests a return route until the return route is received. Sending the predetermined number of return routes;
A route search apparatus characterized by that.

The route transmission means, from the most destination side exit can road of said exit possible road corresponding to the sent return route to the route guidance device, relative exit possible road that exists until the distance Ls Send the searched return route,
The route search device according to claim 1 , wherein:

The return point setting means sets an intersection between the road that is present on the destination side of the identified exitable road and that can enter the travel route and the travel route as a return point.
Route search device according to claim 1 or claim 2, characterized in that.

The road specifying means specifies the predetermined number of exitable roads that exist ahead of the destination-side exitable road among the exitable roads corresponding to the return route that has been transmitted by the route transmission means. ,
The return point setting means, most from the destination side of the exit possible road, and further exit possible road in the predetermined number of knots of exit possible road of the predetermined number specified in the road specification means, the intersection of said travel route Set the return point,
It route search device according to any one of claims of claims 1 to 3, characterized in.

The route search device according to any one of claims 1 to 4 for searching for a travel route to a destination, and a route guidance device for guiding the travel route searched by the route search device. A route guidance device in a navigation system comprising:
Transmitting means for transmitting a starting point and a destination to the route search device;
Return route request means for requesting a return route to the route search device;
Route receiving means for receiving the travel route and the return route from the route search device;
Current position detecting means for detecting the current position;
A guide means for guiding the received travel route corresponding to the detected current position;
The guide means, when the current position is out of the travel route, switches to the return route for guidance,
A route guidance apparatus characterized by that.

The return route request means requests a return route when the number of return routes that have not passed through the received return route is less than the predetermined number.
The route guidance device according to claim 5 .

A route search program for a route search device in a navigation system including a route search device that searches for a travel route to a destination and a route guide device that guides the travel route searched by the route search device,
An acquisition function for acquiring a departure point and a destination from the route guidance device;
A route search function for searching for a travel route from the acquired starting point to the destination;
A road identifying function for identifying a releasable road that can be retired from the travel route searched;
On the travel route, a return point setting function for setting a return point on the destination side from the identified exitable road,
A return route search function for searching for a return route from the intersection of the identified exitable road with the travel route to the set return point;
A request acceptance function for accepting a return route request from the route guidance device;
A route transmission function for transmitting the searched travel route to the route guidance device and transmitting the predetermined number of searched return routes when a request for the return route is received;
Is realized on a computer ,
The route transmission function is determined based on a distance Ls that is larger than the distance L that the vehicle is supposed to travel from when the route guidance device requests a return route until the return route is received. Sending the predetermined number of return routes;
A route search program characterized by that .

The route search device according to any one of claims 1 to 4 for searching for a travel route to a destination, and a route guidance device for guiding the travel route searched by the route search device. A route guidance program for a route guidance device in a navigation system comprising:
A transmission function for transmitting a starting point and a destination to the route search device;
A return route request function for requesting a return route to the route search device;
A route receiving function for receiving the travel route and the return route from the route search device;
A current position detection function for detecting the current position;
A guidance function for guiding the received travel route in correspondence with the detected current position;
Is realized on a computer,
The guidance function provides guidance by switching to the return route when the current position deviates from the travel route.
A route guidance program characterized by that.