(57)【要約】【課題】最適な経路を探索することができる新たな技術的手段を備えた経路探索装置を提供する。【解決手段】出発地から目的地まで一人又は複数人の利用者が交通手段を利用して移動する際の経路を探索する経路探索装置である。出発地から目的地まで、公共交通機関を利用する経路を取得する。取得する前記経路について、出発地から目的地まで移動するために必要な料金を、前記利用者の人数を考慮して算出する。【選択図】      図１
2011059785.tif 000002
【特許請求の範囲】
【請求項１】
出発地から目的地まで一人又は複数人の利用者が交通手段を利用して移動する際の経路を探索する経路探索装置であって、
前記出発地から前記目的地まで、前記交通手段として公共交通機関を利用する経路を取得する経路取得部と、
前記経路取得部が取得する前記経路について、前記出発地から前記目的地まで移動するために必要な料金を、前記利用者の人数を考慮して算出する算出部と、を備えたことを特徴とする経路探索装置。
【請求項２】
前記経路取得部は、前記交通手段として前記公共交通機関を利用する経路の他に、前記交通手段として公共交通機関を利用することなく自動車を利用する経路を含む、複数種類の経路を取得し、
前記算出部は、前記経路取得部が取得する前記複数種類の経路それぞれについて、前記必要な料金を、前記利用者の人数を考慮して算出する請求項１に記載の経路探索装置。
【請求項３】
前記算出部は、前記必要な料金を、前記利用者の属性を考慮して算出する請求項１又は２に記載の経路探索装置。
【請求項４】
前記経路取得部が前記自動車を利用する経路を取得すると、前記算出部は、当該経路に関する前記必要な料金を、前記出発地から前記目的地まで移動するために必要となる自動車の台数を考慮して算出する請求項２に記載の経路探索装置。
【請求項５】
前記算出部は、必要とする自動車の台数を、前記利用者の人数を考慮して求める請求項４に記載の経路探索装置。
【請求項６】
前記算出部は、前記必要な料金を、前記利用者全員の総料金として、又は、前記利用者一人当たりの料金として算出する請求項１〜５のいずれか一項に記載の経路探索装置。
【請求項７】
前記算出部の算出結果に基づいて、前記必要な料金が最も安い経路を選択する経路選択部を、更に備えている請求項１〜６のいずれか一項に記載の経路探索装置。
【請求項８】
出発地から目的地まで一人又は複数人の利用者が交通手段を利用して移動する際の経路を探索する経路探索方法であって、
前記出発地から前記目的地まで、前記交通手段として公共交通機関を利用する経路を取得し、
取得する前記経路について、前記出発地から前記目的地まで移動するために必要な料金を、前記利用者の人数を考慮して算出することを特徴とする経路探索方法。
【請求項９】
出発地から目的地まで一人又は複数人の利用者が交通手段を利用して移動する際の経路を探索する処理を、コンピュータに実行させるためのコンピュータプログラムであって、  前記出発地から前記目的地まで、前記交通手段として公共交通機関を利用する経路を取得するステップと、
取得する前記経路について、前記出発地から前記目的地まで移動するために必要な料金を、前記利用者の人数を考慮して算出するステップと、を含むことを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、出発地から目的地までの経路を探索する経路探索装置、経路探索方法及びコンピュータプログラムに関する。
【背景技術】
【０００２】
出発地から目的地までの経路を探索する経路探索装置は、既に周知であり、この経路探索装置は、出発地から目的地までの最適経路を所定の探索ロジックを用いて探索し、探索結果である最適経路を、ディスプレイを介して画像により案内することができる。
かかる最適経路の探索手法として、例えば、出発地から目的地まで移動する際に必要となる料金が最小となる経路を算出する方法がある。この探索ロジックとしては、例えばダイクストラ法やポテンシャル法がある。
【０００３】
従来の経路探索装置として、例えば特許文献１に記載の車載用ナビゲーション装置があり、この装置は、自動車が出発地から目的地まで移動する際の燃料消費が最小となる経路を探索することができる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平７−５５４８４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
特許文献１に記載の経路探索装置によれば、出発地から目的地までの自動車の燃料消費が最小となる経路を探索することができるので、燃料消費の観点から経済的となる経路を案内することができる。
しかし、燃料消費が最小であることと、出発地から目的地までの移動の際に必要となる料金が最小となることとは必ずしも等価ではない。例えば燃料消費が多少増えても有料道路の使用率を変更すると、必要となる料金は変動することが予想される。
【０００６】
また、出発地や目的地によっては、自動車で移動するよりも鉄道等の公共交通機関を利用する方が、必要な料金が安くなる場合や、これとは反対に、自動車を利用する方が公共交通機関を利用する場合よりも安くなることもある。さらには、利用する人数により必要な料金が変わる場合もある。
また、従来の経路探索では、出発地から目的地まで移動するために必要な料金は、一人分しか求められていない。このため、利用者が複数人である場合には、経路探索で求められた一人分の料金に、利用者の人数をわざわざ乗算して求める必要があった。
【０００７】
そこで、本発明は、最適な経路を探索することができる新たな技術的手段を備えた経路探索装置、経路探索方法及びコンピュータプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
（１）本発明は、出発地から目的地まで一人又は複数人の利用者が交通手段を利用して移動する際の経路を探索する経路探索装置であって、前記出発地から前記目的地まで、前記交通手段として公共交通機関を利用する経路を取得する経路取得部と、前記経路取得部が取得する前記経路について前記出発地から前記目的地まで移動するために必要な料金を、前記利用者の人数を考慮して算出する算出部とを備えたことを特徴とする。
【０００９】
本発明によれば、経路取得部は、出発地から目的地まで公共交通機関を利用する経路を取得し、算出部は、この経路について出発地から目的地まで移動するために必要な料金を、利用者の人数を考慮して算出するので、利用者が複数人となった場合であっても、そのために必要な料金をまとめて算出することが可能となる。
【００１０】
（２）また、前記経路取得部は、前記交通手段として前記公共交通機関を利用する経路の他に、前記交通手段として公共交通機関を利用することなく自動車を利用する経路を含む、複数種類の経路を取得し、前記算出部は、前記経路取得部が取得する前記複数種類の経路それぞれについて、前記必要な料金を、前記利用者の人数を考慮して算出するのが好ましい。
この場合、経路取得部は、出発地から目的地まで、公共交通機関を利用する経路と、公共交通機関を利用することなく自動車を利用する経路とを少なくとも含む複数種類の経路を取得する。そして、算出部は、経路取得部が取得する前記複数種類の経路それぞれについて、出発地から目的地まで移動するために必要な料金を、利用者の人数を考慮して算出するので、例えば、前記必要な料金に関して、利用者が一人の場合では、公共交通機関を利用する経路を採用すると有利であるが、利用者が複数人となった場合では、自動車を利用する経路を採用する方が有利となる場合があれば、その有利となる経路を探索することが可能となる。
【００１１】
（３）また、前記算出部は、前記必要な料金を、前記利用者の属性を考慮して算出する構成とすることができる。前記利用者の属性とは、大人又は小人の区別であり、従来では一人の大人に必要な料金しか求めることができなかったが、前記構成によれば、利用者の人数の他に、当該利用者の属性も含めて考慮することで、必要な料金を算出することができる。
【００１２】
（４）また、前記経路取得部が前記自動車を利用する経路も取得する場合において、前記算出部は、当該経路に関する前記必要な料金を、前記出発地から前記目的地まで移動するために必要となる自動車の台数を考慮して算出する構成とすればよい。
この場合、利用者が出発地から目的地まで移動するために必要となる自動車の台数が異なれば、必要な料金も異なるが、前記構成によれば、このような場合にも対応して必要な料金を算出することができる。
（５）また、この場合において、利用者の人数が、一台の自動車の定員を超えている場合、複数台の自動車が必要となることから、前記算出部は、必要とする自動車の台数を、前記利用者の人数を考慮して求めればよい。
【００１３】
（６）また、前記各経路探索装置において、前記算出部は、前記必要な料金を、前記利用者全員の総料金として、又は、前記利用者一人当たりの料金として算出するのが好ましい。
この場合、必要な料金を、利用者全員の総料金として算出すれば、全員分の料金をまとめて求めることができ、また、必要な料金を、利用者一人当たりの料金として算出すれば、一人ずつの負担金額を求めることができる。
【００１４】
（７）また、前記各経路探索装置は、前記算出部の算出結果に基づいて、前記必要な料金が最も安い経路を選択する経路選択部を、更に備えているのが好ましい。
この場合、交通手段の選択の他に利用人数も含めて必要な料金が最も安くなる経路を、探索することが可能となる。
【００１５】
（８）また、本発明は、出発地から目的地まで一人又は複数人の利用者が交通手段を利用して移動する際の経路を探索する経路探索方法であって、前記出発地から前記目的地まで、前記交通手段として公共交通機関を利用する経路を取得し、取得する前記経路について、前記出発地から前記目的地まで移動するために必要な料金を、前記利用者の人数を考慮して算出することを特徴とする。
【００１６】
この経路探索方法、及び、次のコンピュータプログラムは、前記（１）の経路探索装置と同様の作用効果を奏することができる。
【００１７】
(９)また、本発明は、出発地から目的地まで一人又は複数人の利用者が交通手段を利用して移動する際の経路を探索する処理を、コンピュータに実行させるためのコンピュータプログラムであって、前記出発地から前記目的地まで、前記交通手段として公共交通機関を利用する経路を取得するステップと、取得する前記経路について、前記出発地から前記目的地まで移動するために必要な料金を、前記利用者の人数を考慮して算出するステップとを含むことを特徴とする。
【発明の効果】
【００１８】
本発明によれば、利用者が複数人となった場合であっても、そのために必要な料金をまとめて算出することが可能となるので、従来のように経路探索で求められた一人分の料金に、利用者の人数をわざわざ乗算して求める必要がなくなり、適した経路を簡単に知ることが可能となる。
【図面の簡単な説明】
【００１９】
【図１】経路探索装置を構成するためのハードウエアを示しているブロック図である。
【図２】経路探索装置の機能ブロック図である。
【図３】ディスプレイにおける入力画面を示している。
【図４】経路探索装置によって実行される経路探索方法を説明するフロー図である。
【図５】リンク探索の処理を説明するフロー図である。
【図６】５種類の全経路を示している説明図である。
【図７】計算結果データベースに蓄積されている必要な料金の情報の説明図である。
【発明を実施するための形態】
【００２０】
図１は、本発明の経路探索装置を構成するためのハードウエアを示しているブロック図である。本発明の経路探索装置は、任意の出発地から任意の目的地までの経路を、所定の探索ロジックを用いた演算に基づいて探索し、ディスプレイを介して画像により案内することができるものである。特に本発明の経路探索装置は、出発地から目的地まで一人又は複数人の利用者が交通手段を利用して移動する際の経路を探索するものである。
【００２１】
なお、前記交通手段としては、公共交通機関及び自家用の自動車があり、このうちの公共交通機関には、空路（飛行機）、鉄道、路線バス等が含まれる。
また、本発明の説明において、利用者とは、出発地から目的地まで交通手段を利用して移動する（旅行する）者を意味し、作業者とは、本発明の経路探索装置を用いて経路を探索する作業を行う者を意味する。当然、利用者に作業者が含まれていてもよい。
【００２２】
以下、本実施形態の経路探索装置を、経路探索サービスを管理する管理者側が所有する管理者側コンピュータ１の機能によって構成した場合として説明する。
【００２３】
作業者が所有する前記パーソナルコンピュータ１１は、ＨＤＤやメモリ等よりなり各種のコンピュータプログラムを記憶している記憶装置１２と、この記憶装置１２から各種のコンピュータプログラムを読み出して実行するＣＰＵを含む演算装置１３と、管理者側コンピュータ１とインターネットを介して通信するための通信インターフェース１４と、演算装置１３による処理結果を画像により表示するディスプレイ１５と、キーボード及びマウス等から成る入力装置１６とを有している。
【００２４】
管理者側コンピュータ１は、ＨＤＤやメモリ等よりなり各種のコンピュータプログラムを記憶している記憶装置２と、この記憶装置２から各種のコンピュータプログラムを読み出して実行するＣＰＵを含む演算装置３と、前記パーソナルコンピュータ１１と通信可能とするための通信インターフェース４とを備えている。さらに、管理者側コンピュータ１は、後述する各種のデータベースから情報を読み出したり、当該データベースに情報を蓄積したりするためのネットワークインターフェース５を備えている。
【００２５】
なお、前記データベースとしては、図２に示しているように、地図データベース４１、料金データベース４２、設定データベース４３、駐車場データベース４４及び計算結果データベース５０がある。これらデータベースは、管理者側コンピュータ１が記憶装置２内に備えていてもよいが、ネットワークを介して、管理者側コンピュータ１と繋がっている他の装置が備えていてもよい。なお、図２は、本発明の経路探索装置の機能ブロック図である。
【００２６】
図２に示している経路探索機能部２１は、図１の管理者側コンピュータ１が備えている前記コンピュータプログラムによって実行される機能のうちの１つであり、この経路探索機能部２１は、パーソナルコンピュータ１１が有する入力装置１６からの入力情報に基づいて、出発地から目的地までの経路を探索する処理を実行する。この経路探索機能部２１は、図２に示しているように、その機能部として経路取得部３１、算出部３２及び経路選択部３３を有している。
【００２７】
また、図２に示しているマンマシン機能部２２は、管理者側コンピュータ１が備えている前記コンピュータプログラムによって実行される機能のうちの１つであり、作業者が前記入力装置１６（図１参照）を用いてパーソナルコンピュータ１１に各種の入力情報（図３参照）を入力すると、このマンマシン機能部２２は、前記経路探索機能部２１に経路探索の処理を実行させる機能を備えている。
図３は、パーソナルコンピュータ１１が有するディスプレイ１５における入力画面を示している。入力装置１６のキーボード及びマウスの操作によって、入力情報として、出発地の名称、目的地の名称、利用者の属性とその各人数等の情報が入力される。利用者の属性とは、大人と小人（子供）との区別を示すものである。
【００２８】
前記経路取得部３１は、入力された出発地から入力された目的地までの経路を、前記データベースに基づいて取得する機能を有している。具体的には、経路取得部３１は、交通手段として公共交通機関を利用する経路を少なくとも取得する。なお、以下の実施形態では、経路取得部３１は、交通手段として公共交通機関を利用する経路と、交通手段として公共交通機関を利用することなく自動車を利用する経路とを少なくとも含む、複数種類の経路を取得する。この機能の具体例については後に説明する。
【００２９】
前記算出部３２は、後述するリンクコストを求める機能を有している他に、経路取得部３１が取得する複数種類の経路それぞれについて、前記出発地から前記目的地まで移動するために必要な料金（総料金）を、利用者の人数を考慮して算出する機能を有している。つまり、後に説明する実施形態では５種類の経路が取得されるので、これら５種類の経路毎に、利用者の人数を考慮して必要な料金を算出する。
【００３０】
前記経路選択部３３は、算出部３２が算出した結果に基づいて、（後述する料金優先の場合には、）出発地から目的地まで移動するために必要な料金が安い順に経路を選択して、その順に上から並べる機能を有している。そして、この経路選択部３３による順位付けの結果は、パーソナルコンピュータ１１のディスプレイ１５に表示される。
後の実施形態では、５種類の経路毎に利用者の人数を考慮して必要な料金が算出されているので、この必要な料金が安い順に、５種類の経路が並び替えられる。
また、経路選択部３３は、算出部３２が算出した結果に基づいて、（後述する時間優先の場合には、）出発地から目的地まで移動するために必要な総所要時間が短い順に経路を選択して、その順に上から並べる機能を有している。そして、この経路選択部３３による順位付けの結果は、パーソナルコンピュータ１１のディスプレイ１５に表示される。
後の実施形態では、５種類の経路について総所要時間が算出されているので、この総所要時間が短い順に、５種類の経路が並び替えられる。
【００３１】
各種の前記データベースについて説明する。交通手段を利用して移動するための経路ネットワークを構成するために、道路地図及び公共交通機関の路線図等がメッシュ状に分割されていて、前記地図データベース４１は、メッシュを構成するノードとリンクにより構成されたリンクの情報（以下、リンク情報という）を蓄積している。なお、ノードは、自動車が走行する道路の場合、有料道路の料金所、交差点や屈曲点等を特定するための座標位置であり、公共交通機関の場合、利用者が乗り降りする場所（鉄道の場合では駅）を特定するための座標位置である。そして、各ノードを繋いだものがリンクである。このリンク情報には、リンク番号、リンクの始点及び終点のノードのアドレス、リンクの距離、リンクを通過する所要時間、道路の場合では制限速度等の道路の種別が含まれている。
【００３２】
前記料金データベース４２は、地図データベース４１に蓄積されている各リンクに対応つけられて、当該各リンクを通過する場合の料金についての情報を蓄積している。この料金は、例えば、有料道路を利用してリンクを通行するために必要となる料金や、公共交通機関を利用してリンクを通過する場合に必要となる料金である。また、この料金についての情報は、利用者の属性毎に蓄積されていて、また、一人あたりの情報として蓄積されている。
前記設定データベース４３は、自動車を利用する場合のために、自動車の燃料消費率、燃料単価の情報を蓄積している。燃料消費率は、燃料の単位量当たりの走行可能距離である。また、燃料消費率は、車種毎によって、及び、道路の種別によって（通過するリンクに応じて）、異なる値が設定されている。
前記駐車場データベース４４は、各地の駐車場と、当該駐車場を利用した場合の料金（例えば平均的な料金）とについての情報が蓄積されている。
【００３３】
〔経路探索処理の具体的な説明〕
図４は、前記経路探索装置によって実行される経路探索方法を説明するフロー図である。図４のステップＳ１において、経路計算要求の受付処理が、経路探索装置（マンマシン機能部２２）によって実行される。すなわち、パーソナルコンピュータ１１が有するディスプレイ１５に、図３に示している情報入力画面が表示される。作業者が入力装置１６を用いて、経路探索のための入力情報を入力する。
本実施形態では、必須の入力情報として、出発地は「東京駅」であり、目的地は「大阪駅」であり、利用者の属性及び人数は、「大人」が「２」名と「小人」が「２」名との合計「４」名である情報が、作業者によって入力される。また、入力情報として、出発日は「５」月「６」日であり、出発時刻は「１０」時「００」分である情報が入力される。
【００３４】
また、任意の入力情報として、後に説明する経由地設定がある。この経由地設定は、出発地から目的地までの間に、経由地を任意に設定することができる。また、条件設定として、必要となる料金が多少高くなっても目的地への到着時間の短縮を優先させる時間優先と、到着時間の短縮よりも必要となる料金を優先させる料金優先とを、作業者は選択することができる。時間優先は、必要な料金よりも所要時間（旅行時間）を重視して経路を探索する場合に選択され、料金優先は、所要時間よりも必要な料金を重視して経路を探索する場合に選択される。なお、この項目について情報が入力されない場合は、条件設定として、料金優先が自動的に選択される。
また、他の条件設定として、自動車を利用する場合に、例えば目的地において有料駐車場が必要であると、その設定を行うことができる。また、自動車を利用する場合に、燃料消費率が様々となることから、車種の設定を行うこともできる。
【００３５】
このようにしてマンマシン機能部２２によって入力情報が経路探索装置に入力されると、経路探索機能部２１は、複数種類の交通機関それぞれを利用した場合での、出発地から目的地までの経路（この経路を、全経路という）の探索処理を開始する（図４のステップＳ２）。本実施形態では、（１）少なくとも一部に空路を用いる場合、（２）少なくとも一部に新幹線を用いる場合、（３）少なくとも一部に特急電車を用いる場合、（４）少なくとも一部に路線バスを用いる場合、及び、（５）全経路で自動車を用いる場合のそれぞれについて、全経路の探索、当該全経路に必要となる料金の算出処理、及び、当該全経路に必要な総所要時間の算出処理を実行する。
このために、開始終了リンクの設定（ステップＳ３）、リンク探索（ステップＳ４）及び計算結果の生成（ステップＳ５）が、繰り返し実行されることになる。
【００３６】
前記開始終了リンクの設定（ステップＳ３）は、入力された出発地から目的地へと向かう始点となる退出リンク、及び、入力された目的地へと到達する終点となる進入リンクを設定する。退出リンクは、出発地に最も近いリンクであり、経路探索するための開始リンクとなる。進入リンクは、目的地に最も近いリンクであり、経路探索するための終了リンクとなる。
経路取得部３１は、出発地と目的地とに基づいて、前記地図データベース４１を参照して前記リンク情報を読み出し、対応する退出リンク及び進入リンクを抽出する。
【００３７】
退出リンク及び進入リンクが抽出されると、リンク探索（ステップＳ４）が実行される。図５は、このリンク探索の処理を説明するフロー図である。図６は、リンク探索が繰り返し実行されることで探索された５種類の全経路を示している説明図である。
経路取得部３１は、図５に示している探索ロジックに基づいて、前記退出リンクから前記進入リンクまでの間にあるリンク（以下、接続リンクという）を地図データベース４１から取得し、当該退出リンクから当該進入リンクまでの全経路を、複数作成する。なお、以下の処理は、特に断らない限り、経路取得部３１によって実現される。
【００３８】
（１）１種類目の経路探索（図５（Ａ）のステップＳ２１）として、空路を用いる場合を説明する。
経路取得部３１は、地図データベース４１を参照して、出発地に最寄りの空港として羽田空港、目的地に最寄りの空港として伊丹空港を、経由地点として抽出する（図５（Ａ）のＳ２２）。この場合、図６において、東京駅から羽田空港までが第１区間、羽田空港から伊丹空港までが空路となる第２区間、伊丹空港から大阪駅までが第３区間となり、区間数が３となる。
なお、入力情報として経由地が選択されていれば、当該経由地が用いられる。すなわち、図３において、経由地設定として任意の経由地が作業者によって設定されていると、経路取得部３１は、設定された任意の経由地を考慮して処理を実行する。例えば、出発地と空港との間で、任意の経由地が一つ設定されていると、東京駅から当該任意の経由地点までを第１区間、当該任意の経由地から空港までを第２区間として追加し、合計の区間数を４として探索処理を行う。以下では、任意の経由地が設定されていない場合として説明する。
【００３９】
経路取得部３１は、区間毎の経路（以下、部分経路という）の探索として、各区間で、後述するリンクコストの累計が最も小さくなる経路を選択する処理を実行し、この処理を全ての区間について繰り返し実行する（Ｓ２３）。
前記第１区間の部分経路の探索を例示する（図５（Ｂ）のステップＳ３１）。
経路取得部３１は、地図データベース４１を参照して、退出リンクから経由地までの部分経路の探索を行うが、その途中にある接続リンクの情報を抽出する（Ｓ３２）。あるリンクから複数の接続リンクが枝分かれする場合は、例えば、当該枝の接続リンクそれぞれからさらに経由地へ向かって探索を続け、経由地までの全ての接続リンクの探索を次々と実行し、複数の部分経路の候補を探索する。
【００４０】
そして、算出部３２は、候補となった複数の部分経路それぞれに関して、当該部分経路に含まれている接続リンク毎のリンクコストを積算する。
このために、算出部３２は、接続リンク毎のリンクコストを、当該接続リンクに必要な料金と当該接続リンクの所要時間との重み付け和を示す次の式（１）により求める。
「リンクコスト＝係数ａ×接続リンクに必要な料金＋係数ｂ×接続リンクの所要時間」  ・・・  式（１）
このように接続リンク毎のリンクコストを求め、これらを積算することにより、候補となった複数の部分経路それぞれのリンクコストの累計が求められる（Ｓ３３）。
【００４１】
前記条件設定（図３参照）として料金優先が選択されている場合を説明する。
料金優先が選択されている場合、前記式（１）に関して、必要な料金の重み付け係数ａが１に設定され、所要時間の重み付け係数ｂが０に設定される。
さらに、この積算処理（Ｓ３３）は、前記入力情報として入力された利用者の属性（大人又は小人の区別）、及び、前記入力情報として入力された利用者の人数を考慮して実行される。本実施形態では、利用者の属性に大人と小人とが含まれていて、それぞれの人数は大人が２名と小人が２名であり、合計４名である。
【００４２】
そこで、算出部３２は、前記式（１）に関して、前記係数ａを１とし前記係数ｂを０とし、さらに、料金データベース４２及び地図データベース４１から、大人と子供それぞれの接続リンク毎の必要な料金及び接続リンク毎の所要時間を抽出する。そして、これらに基づいて、算出部３２は、候補となった部分経路それぞれに含まれている接続リンク毎のリンクコストを、大人２名と小人２名との合計として算出し、さらに、この部分経路に含まれている複数の接続リンクのリンクコストを積算して累計する。
【００４３】
このようにして、第１区間で候補となった複数の部分経路それぞれに含まれている接続リンク毎のリンクコストが、利用者の属性及びその人数、及び、重み付け和を示す前記の式（１）により求められ、算出部３２によってリンクコストが累計されると、経路取得部３１は、候補となった複数の部分経路の中から、前記算出部３２の積算結果に基づいて、リンクコストの累計が最小となる部分経路を、当該第１区間の部分経路として求める（図５（Ｂ）のステップＳ３４）。
【００４４】
さらに、このようにして求められた第１区間の部分経路で必要となる料金（区間料金）を、算出部３２が、当該部分経路に含まれる接続リンク毎の料金を積算することで求める。なお、本実施形態では、前記式（１）における料金の重み付け係数ａが１に設定され、所要時間の重み付け係数ｂが０に設定されていることから、第１区間の部分経路で必要となる区間料金は、当該部分経路について積算されたリンクコストの累計と同じとなる。このようにして、第１区間において、出発地から経由地まで、求められた部分経路に沿って移動するために必要な区間料金が、利用者の人数（合計４名）を考慮して算出されることになる。
また、求められた第１区間の部分経路で必要となる所要時間（所要区間時間）を、算出部３２が、地図データベース４１を参照して、当該部分経路に含まれる接続リンク毎の所要時間を積算することで求めることができる（図５（Ｂ）のステップＳ３５）。
【００４５】
以上の第１区間の部分経路の探索で行った処理を、残りの区間の部分経路（第２区間及び第３区間）についても実行する（Ｓ２３）。なお、第２区間は羽田空港から伊丹空港までの空路であり、この区間の部分経路は、経路取得部３１によって地図データベース４１に基づいて容易に取得され、この区間で必要となる区間料金、及び、この区間で必要となる所要時間は、算出部３２によって容易に求められる。
【００４６】
このようにして、全ての区間の部分経路が探索されることにより、１種類目である空路を用いた場合であって、出発地から目的地までの全経路でリンクコストが最小となる経路が探索されたことになる（図５（Ａ）のステップＳ２４）。
そして、算出部３２が、このリンクコストが最小となった全経路で必要となる総料金を、各区間の部分経路で算出された必要な前記区間料金を総和することにより、求めることができる（図４のステップＳ５）。さらに、算出部３２が、リンクコストが最小となった全経路で必要となる総所要時間を、各区間の部分経路で算出された必要な前記所要区間時間を総和することにより、求めることができる（図４のステップＳ５）。
【００４７】
このステップＳ５での計算結果を図７に示している。つまり、（１）空路を利用した場合、利用者４名の必要な総料金の合計は４２，４８０円となる。そして、出発地から目的地までの総所要時間は２時間５２分となる。
このように、出発地から目的地までのリンクコストが最小となる全経路が一つ確定すると、当該全経路で必要となる総料金及び総所要時間を求めることができる（図４のステップＳ５）。
なお、前記式（１）の係数ａ及び係数ｂに関して、「１」及び「０」が設定される以外として、係数ａ及び係数ｂの双方が０より大きい値であって、係数ａが係数ｂよりも大きく設定されていてもよい。この場合であっても、前記式（１）において、必要な料金の方が、重み付け度合いが高いと言える。
【００４８】
次に、図４のステップＳ６で「Ｎｏ」の判定が、経路取得部３１によってなされ、２種類目の経路探索として、（２）新幹線を用いる場合の経路探索が開始される（図５（Ａ）のステップＳ２１）。
経路取得部３１は、地図データベース４１を参照して、目的地に最寄りの新幹線の駅として新大阪駅（図６参照）を、経由地点として抽出する（Ｓ２２）。この場合、東京駅から新大阪駅までが第１区間、新大阪駅から大阪駅までが第２区間となり、区間数が２となる。なお、入力情報（前記経由地設定）として任意の経由地が選択されていれば、当該経由地が用いられる。
そして、経路取得部３１は、区間毎の経路（部分経路）の探索として、各区間でリンクコストの累計が最も小さくなる経路を選択する処理を実行し、この処理を全ての区間について繰り返し実行する（Ｓ２３）。
【００４９】
各区間の経路（部分経路）の探索は、前記経路（１）の場合と同様である（図５参照）。なお、第１区間は、東京駅から新大阪駅までの新幹線によるものであり、この区間の部分経路は、経路取得部３１によって地図データベース４１に基づいて簡単に取得され、この区間のリンクコストは、算出部３２によって簡単に求められる。
このようにして、全ての区間の部分経路が探索されることにより、２種類目である新幹線を用いた場合であって、出発地から目的地までの全経路で必要となるリンクコストが最小となる経路が探索されたことになる（Ｓ２４）。
【００５０】
そして、算出部３２が、このリンクコストが最小となった全経路で必要となる総料金を、各区間の部分経路で算出された必要な前記区間料金を総和することにより、求めることができる（図４のステップＳ５）。さらに、算出部３２が、リンクコストが最小となった全経路で必要となる総所要時間を、各区間の部分経路で算出された必要な前記所要区間時間を総和することにより、求めることができる（図４のステップＳ５）。
【００５１】
このステップＳ５での計算結果を図７に示している。つまり、（２）新幹線を利用した場合、利用者４名の必要な料金の合計は４２，５００円となる。そして、出発地から目的地までの総所要時間は２時間４２分となる。
【００５２】
同様に、（３）３種類目の経路探索（図５（Ａ）のＳ２１）として、特急電車を用いる場合、及び、（４）４種類目の経路探索（図５（Ａ）のＳ２１）として、高速バスを用いる場合（本実施形態では高速バスとなる）についても、経路の探索が実行され、それぞれの場合について、全経路で必要となるリンクコストが最小となる経路が探索される（Ｓ２４）。そして、このリンクコストが最小となった全経路で必要となる総料金、及び、当該全経路で必要となる総所要時間を、前記経路（１）及び経路（２）の場合と同様にして、算出部３２が求める（図４のステップＳ５）。
【００５３】
そして、（３）特急電車及び（４）高速バスを利用した場合について、ステップＳ５での計算結果を図７に示している。
このように、出発地から目的地までの最小リンクコストとなる全経路が一つ確定すると、当該全経路で必要となる総料金及び総所要時間を求めることができる（図４のステップＳ５）。また、この場合においても、入力情報（前記経由地設定）として任意の経由地が選択されていれば、当該経由地が用いられる。
【００５４】
最後に、（５）５種類目の経路探索（図５（Ａ）のＳ２１）として、自動車を用いる場合の経路探索を説明する。
なお、この場合においても、図３において、入力情報として任意の経由地が作業者によって設定されていると、経路取得部３１は、設定された地点を経由地点として処理を実行する。例えば経由地が一つ設定されていると、東京駅からこの経由地までを第１区間、この経由地から大阪駅までを第２区間として、区間数を２として探索処理を行う。しかし、以下では、経由地が設定されていない場合として説明する。
【００５５】
経由地が設定されていないので、経路取得部３１は、退出リンク（出発地）から進入リンク（目的地）までの全経路の探索として、リンクコストの累計が最も小さくなる経路を選択する処理を実行する。
すなわち、経路取得部３１は、地図データベース４１を参照して、退出リンク（出発地）から進入リンク（目的地）までの全経路の探索を行うが、その途中にある接続リンクの情報を抽出する（図５（Ｂ）のＳ３２）。あるリンクから複数の接続リンクが枝分かれする場合は、例えば、当該枝の接続リンクそれぞれからさらに目的地へ向かって探索を続け、目的地までの全ての接続リンクの探索を次々と実行し、複数の全経路の候補を探索する。
【００５６】
そして、算出部３２は、候補となった複数の全経路それぞれにおいて、当該全経路に含まれている接続リンク毎のリンクコストを積算する。
このために、算出部３２は、接続リンク毎のリンクコストを、当該接続リンクに必要な料金と当該接続リンクの所要時間との重み付け和を示す前記式（１）により求める。
この式（１）により接続リンク毎のリンクコストを求め、これらを積算することにより、候補となった複数の全経路それぞれのリンクコストの累計が求められる（Ｓ３３）。
なお、条件設定（Ｓ４１）として、料金優先が選択されているため、前記式（１）に関して、必要な料金の重み付け係数ａが１に設定され、所要時間の重み付け係数ｂが０に設定される。
【００５７】
ここで、前記式（１）を用いたリンクコストを求める処理（Ｓ３３）は、前記入力情報として入力された利用者の人数を考慮して実行される。本実施形態では、利用者の人数は大人が２名と小人が２名との合計４名であるが、この４名は１台の自動車により移動可能であるため、すなわち、利用者の人数が、１台の自動車の定員以下であるため、自動車１台によるリンクコストの積算を行う。この結果、前記式（１）における接続リンクに必要な料金は、利用者の人数が考慮されて求められた自動車の必要台数（１台）に基づく値が採用される。
【００５８】
なお、仮に利用者の人数が、１台の自動車の定員を超えている場合は、算出部３２は、複数台の自動車を用いると判断し、自動車の必要台数分についてのリンクコストの積算を行う。なお、自動車の必要台数は、（利用者の人数）を（自動車の定員）で除算し、その答えを切り上げた値となる。
【００５９】
そして、前記式（１）中の接続リンクに必要な料金としては、先ず、燃料料金がある。前記のとおり図５（Ｂ）のＳ３２で、接続リンクの情報が抽出されると、算出部３２は、当該接続リンクで必要な燃料料金を求める。すなわち、地図データベース４１に蓄積されている各接続リンクの距離と、前記設定データベース４３に蓄積されている自動車の燃料消費率と燃料単価の情報とに基づいて、算出部３２は、候補となった全経路それぞれに含まれている接続リンク毎で必要な燃料料金を算出する。
さらに、付加される必要な料金としては、有料道路の料金がある。接続リンクが有料道路上にある場合、当該有料道路を通行することで必要となる料金である。前記のとおり図５（Ｂ）のＳ３２で、接続リンクの情報が抽出されると、算出部３２は、当該接続リンクで必要な有料道路の料金を求める。すなわち、前記料金データベース４２に蓄積されていて各接続リンクに対応する有料道路の料金の情報に基づいて、算出部３２は、有料道路の料金を算出する。
【００６０】
また、図３の条件設定で、自動車を用いて目的地に到着すると、有料駐車場を利用することが設定されている場合、付加される必要な料金として駐車場の料金がある。そこで、目的地に到着する最終の接続リンクには、駐車場の料金も含める必要があることから、算出部３２は駐車場の料金を求める。このために、各地の駐車場と当該駐車場を利用した場合の料金とについての情報が蓄積されている前記駐車場データベース４４から、算出部３２は、目的地周辺での駐車場料金を抽出する。
【００６１】
以上のように、算出部３２は、前記式（１）に関して、前記係数ａを１とし前記係数ｂを０とし、さらに、各データベースに基づいて、自動車１台の接続リンク毎の必要な料金及び接続リンク毎の所要時間を取得する。そして、これらに基づいて、算出部３２は、候補となった全経路それぞれに含まれている接続リンク毎のリンクコストを、大人２名と小人２名が乗車可能な自動車１台として算出し、さらに、この全経路に含まれている複数の接続リンクのリンクコストを積算して累計する。
【００６２】
このようにして、候補となった複数の全経路それぞれに含まれている接続リンク毎のリンクコストが、利用者の人数（自動車の台数）、及び、重み付け和を示す前記の式（１）により求められ、算出部３２によってこのリンクコストが積算されると、経路取得部３１は、候補となった複数の全経路の中から、前記算出部３２の積算結果に基づいて、リンクコストの累計が最小となる全経路を求める（図５（Ｂ）のステップＳ３４）。
【００６３】
このようにして、５種類目である自動車を用いた場合であって、出発地から目的地までの全経路でリンクコストが最小となる経路が探索されたことになる（図５（Ａ）のＳ２４）。
さらに、このようにして求められた全経路で必要となる総料金を、算出部３２が、当該全経路に含まれる接続リンク毎の料金を積算することで求める（図４のステップＳ５）。なお、本実施形態では、前記式（１）における料金の重み付け係数ａが１に設定され、所要時間の重み付け係数ｂが０に設定されていることから、全経路で必要となる総料金は、当該全経路について積算されたリンクコストの合計と同じとなる。
また、求められた全経路で必要となる総所要時間を、算出部３２が、地図データベース４１を参照して、当該全経路に含まれる接続リンク毎の所要時間を積算することで求めることができる（図４のステップＳ５）。
このように、出発地（退出リンク）から目的地（進入リンク）まで移動するために必要な総料金が算出されるが、この算出は、利用者の人数（合計４名）を考慮することで必要となる自動車の台数に基づいて実行される。
【００６４】
このステップＳ５での計算結果を図７に示している。利用者の人数が４人であっても、（５）自動車を利用した場合では、自動車１台についての積算が前記のとおり実行されている。このため、燃料費、有料道路料金及び駐車場料金は、自動車１台についての料金であり、合計として１５，３５０円となる。
そして、出発地から目的地までの総所要時間は６時間１５分となる。
このように、出発地から目的地までの最小リンクコストとなる全経路が一つ確定すると、当該全経路で必要となる総料金及び総所要時間を求めることができる（図４のステップＳ５）。
【００６５】
以上より、経路取得部３１は、出発地から目的地まで、交通手段として公共交通機関を利用する経路（前記（１）〜（４）の場合）と、交通手段として公共交通機関を利用することなく自動車を利用する経路（前記（５）の場合）とを含む、複数種類（５種類）の経路を取得したことになる。
【００６６】
そして、前記経路（１）〜（５）それぞれについて、算出部３２による全経路におけるリンクコストの合計、及び、出発地から目的地まで移動するために必要な料金の合計（総料金）の情報、総所要時間の情報が（図７参照）、図２の計算結果データベース５０に蓄積される。
（１）〜（５）全ての種類の経路探索が完了したので、経路取得部３１によって、図４のステップＳ６の「Ｙｅｓ」の判定がなされ、最適経路の選択処理が実行される（ステップＳ７）。
【００６７】
前記条件設定（図３参照）として、料金優先が作業者によって選択されているので、このステップＳ７では、算出部３２が算出した結果（前記計算結果データベース５０）に基づいて、経路選択部３３が、全経路におけるリンクコストの合計が小さい順番、すなわち、出発地から目的地まで移動するために必要な総料金が安い順番に、経路を並び替える。この結果、最も上位の経路、すなわち、出発地から目的地まで移動するために必要な料金が最も安い経路が、経路選択部３３によって選択されたことになる。
本実施形態では、（５）である公共交通機関を利用することなく自動車を利用する場合が、最も安い経路となり、以下、（４）高速バス、（３）特急電車、（１）空路、及び、（２）新幹線の順に、順位付けられる。
【００６８】
そして、この経路選択部３３による順位付けの結果、及び、交通手段毎の、必要な総料金、その詳細としての図７の積算結果及び総所要時間が、マンマシン機能部２２によって、パーソナルコンピュータ１１のディスプレイ１５に表示される。このように、本実施形態の経路探索装置によれば、交通手段の選択の他に利用人数も含めて必要な料金が最も安くなる総経路が探索され、当該総経路を案内することが可能となる。
【００６９】
また、前記実施形態の算出部２３によれば、出発地から目的地まで移動するために必要な料金を、利用者全員の総料金として算出した。この場合、全員分の必要な料金を、まとめて求めることができる。しかし、算出部２３は、これ以外として、必要な料金を、利用者一人当たりの料金として算出してもよい。なお、双方を算出してもよい。
すなわち、本実施形態の（１）空路を利用する場合では、大人一人当たりの料金として１４，１４０円を算出し、小人一人当たりの料金として７，１００円を算出し、また、（５）自動車を利用する場合では、合計１５，３５０円を利用者の人数で除算した結果、つまり、３，８３８円（四捨五入）を算出し、利用者一人当たりの料金を、ディスプレイ１５に表示させてもよい。このように、必要な料金を利用者一人当たりの料金として算出すれば、一人ずつの負担料金を求めることができる。
【００７０】
次に、図３の条件設定において、時間優先が選択された場合のリンク探索（図４のステップＳ４）を説明する。
この場合であっても、重み付け和を示す前記式（１）により、接続リンク毎のリンクコストを求めるが、時間優先が選択されているので、前記式（１）において、料金の重み付け係数ａが０に設定され、所要時間の重み付け係数が１に設定される。
なお、前記係数ａ及び係数ｂに関して、「０」及び「１」が設定される以外として、係数ａ及び係数ｂの双方が０より大きい値であって、係数ｂが係数ａよりも大きく設定されていてもよい。この場合であっても、前記式（１）において、所要時間の方が、重み付け度合いが高いと言える。
【００７１】
この係数の設定により、料金優先が選択された前記の場合と同様にして、出発地から目的地まで、交通手段として公共交通機関を利用する経路（前記（１）〜（４））を求める場合のそれぞれにおいて、区間毎で候補となった複数の部分経路それぞれに含まれている接続リンク毎のリンクコストが、重み付け和を示す前記の式（１）により求められ、前記算出部３２によってリンクコストが積算される。
そして、経路取得部３１は、区間毎で候補となった複数の部分経路の中から、前記算出部３２の積算結果に基づいて、リンクコストの累計が最小となる経路を、当該区間の部分経路として求める（図５（Ｂ）のステップＳ３４）。さらに、全ての区間の部分経路についても同様にして求められ、この結果、出発地から目的地までの全経路でリンクコストが最小となる経路が探索される。
【００７２】
また、料金優先が選択された前記の場合と同様にして、交通手段として公共交通機関を利用することなく自動車を利用する経路（前記（５））を求める場合において、候補となった複数の全経路それぞれに含まれている接続リンク毎のリンクコストが、重み付け和を示す前記の式（１）により求められ、前記算出部３２によってリンクコストが積算される。
そして、経路取得部３１は、候補となった複数の全経路の中から、前記算出部３２の積算結果に基づいて、リンクコストの累計が最小となる全経路を求める（図５（Ｂ）のステップＳ３４）。
【００７３】
以上より、経路取得部３１は、出発地から目的地まで、交通手段として公共交通機関を利用する経路（前記（１）〜（４）の場合）と、交通手段として公共交通機関を利用することなく自動車を利用する経路（前記（５）の場合）とを含む、複数種類（５種類）の経路を取得したことになる。この結果は、図７に示すものと同じである。
【００７４】
そして、前記条件設定（図３参照）として、時間優先が選択されているので、このステップＳ７では、算出部３２が算出した結果に基づいて、経路選択部３３が、全経路におけるリンクコストの合計が小さい順番、すなわち、出発地から目的地まで移動するために必要な総所要時間が短い順番に、経路を並び替える。この結果、最も上位の経路、すなわち、出発地から目的地まで移動するために必要な時間が最も短い経路が、経路選択部３３によって選択されたこととなる。
本実施形態では、（２）新幹線を利用する場合が、必要な時間が最も短い経路となり、以下、（１）空路、（５）自動車、（４）高速バス、及び、（３）特急電車の順に、順位付けられる。
【００７５】
そして、この経路選択部３３による順位付けの結果、及び、交通手段毎の、必要な総所要時間、総料金、及び、その詳細としての図７の積算結果が、マンマシン機能部２２によって、パーソナルコンピュータ１１のディスプレイ１５に表示される。
このように、本実施形態の経路探索装置によれば、時間優先が選択されると、総所要時間が最も短くなる経路が探索され、当該経路を案内することが可能となる。
以上が、時間優先が選択されている場合の経路探索である。
【００７６】
本発明によれば、出発地から目的地まで移動するために必要な料金を、利用者の人数を考慮して算出するので、利用者が複数人となった場合であっても、そのために必要な料金をまとめて算出することが可能となる。
さらに、従来では、一人の大人ぶんの必要な料金しか求めることができないため、利用者が子供である場合に、必要な料金を求めることができなかったが、前記実施形態によれば、利用者が大人であるか小人であるかを考慮して算出するので、利用者が小人のみである場合であっても、料金を求めることができ、また、利用者に大人と小人との両方が含まれている場合であっても、一度にまとめて総料金を求めることが可能となる。
【００７７】
そして、本実施形態によれば、経路取得部３１が取得する複数種類の経路それぞれについて、算出部３２は、出発地から目的地まで移動するために必要な料金を、利用者の人数を考慮して算出している。この結果、図７に示しているように、前記必要な料金に関して、仮に利用者が１人の場合では、（４）高速バスを利用する経路採用すると有利である。しかし、本実施形態のように利用者が４名となると、（５）自動車を利用する経路を採用する方が有利となる。そこで、本発明の経路検索装置によれば、この有利となる（５）の経路を探索することが可能となり、当該有利となる情報を案内することができる。
【００７８】
なお、今回開示した実施形態は、本発明の例示であって制限的なものではない。本発明の範囲は、特許請求の範囲によって示され、特許請求の範囲とその構成と均等な意味、及び、範囲内での全ての変更が含まれる。
例えば、経路取得部３１によって取得される、出発地から目的地まで経路として、公共交通機関を利用すると共に自家用の自動車も利用する経路が含まれていてもよい。
また、利用者が利用する交通手段は例示したもの以外であってもよく、経路取得部３１が取得する複数の経路の中に、例えば、途中でレンタカーを利用する場合が含まれていてもよい。このために、地図データベース４１等との他に、レンタカー情報を蓄積しているレンタカーデータベースが設けられていてもよい。
さらに、前記実施形態では、経路探索装置は、経路探索サービスを管理する管理者側が所有する管理者側コンピュータ１の機能によって構成された場合を説明したが、これ以外として、当該管理者側コンピュータ１の機能と、この管理者側コンピュータ１とインターネットを介して通信可能である家庭用のパーソナルコンピュータ１１の機能とによって構成されていてもよい。
【００７９】
また、前記実施形態では、経路選択部３３は、出発地から目的地まで移動するために必要な料金が安い順に経路を選択して、その順に上から並べる場合を説明したが、前記必要な料金が最も安い経路を選択する形態であってもよく、この場合、経路選択部３３による選択結果が、パーソナルコンピュータ１１のディスプレイ１５に表示される。
また、経路選択部３３が、出発地から目的地まで移動するために必要な総所要時間が短い順に経路を選択して、その順に上から並べる場合を説明したが、前記必要な総所要時間が最も短い経路を選択する形態であってもよく、この場合、経路選択部３３による選択結果が、パーソナルコンピュータ１１のディスプレイ１５に表示される。
【００８０】
また、あるリンクから複数の接続リンクが枝分かれする場合の、他の探索ロジックとして、ポテンシャル法以外にダイクストラ法があり、経路取得部３１が、地図データベース４１に基づいて、枝分かれする接続リンクの情報を抽出し（図５（Ｂ）のＳ３２）、算出部３２が、料金データベース４２に基づいて、当該各枝の接続リンクのリンクコストを抽出してその大小を比較し、当該リンクコストが最も小さい枝の接続リンクを経路取得部３１が選んで、目的地（又は経由地）に向かって探索を続けてもよい。なお、この場合の前記「各枝の接続リンクのリンクコスト」は、退出リンクから当該枝の接続リンクまで各接続リンクのリンクコストを積算した総和である。そして、この探索ロジックを繰り返し行い目的地（進入リンク）に到達すれば、最も必要な料金が少ない経路となる。
【符号の説明】
【００８１】
１：管理者側コンピュータ、  １１：パーソナルコンピュータ、  ３１：経路取得部、  ３２：算出部、  ３３：経路選択部、  ４１：地図データベース、  ４２：料金データベース、  ４３：設定データベース、  ４４：駐車場データベース、  ５０：計算結果データベース
【図１】
2011059785.tif 000003
【図２】
2011059785.tif 000004
【図３】
2011059785.tif 000005
【図４】
2011059785.tif 000006
【図５】
2011059785.tif 000007
【図６】
2011059785.tif 000008
【図７】
2011059785.tif 000009