経路探索装置、方法及びプログラム
【課題】経路探索において、時間を含む全コストを金額換算して最適な経路を探索するとともに、金額換算時の時間単価を割引率と休憩許容時間に基づいて変動させることにより、ユーザや状況に最も適合した経路を提供すること。
【解決手段】目的地等の探索条件を受け付ける条件受付手段２０と、休憩許容時間の設定を受け付ける許容値設定手段４０と、出発地と目的地の直線距離を計算する直線距離計算手段３０と、前記直線距離、前記休憩許容時間及び割引データから、休憩許容時間を所要時間に含んで割引がある場合と、休憩なし割引なしの場合の各トータルコストが略均衡する時間単価を計算する単価計算手段５０と、前記休憩許容時間までの休憩を組み込むことで割引の適用を受ける経路を含む各経路についてそのコストを前記時間単価を用いて金額に換算して比較することにより最適経路を探索計算する経路計算手段６０と、を有する。
【解決手段】目的地等の探索条件を受け付ける条件受付手段２０と、休憩許容時間の設定を受け付ける許容値設定手段４０と、出発地と目的地の直線距離を計算する直線距離計算手段３０と、前記直線距離、前記休憩許容時間及び割引データから、休憩許容時間を所要時間に含んで割引がある場合と、休憩なし割引なしの場合の各トータルコストが略均衡する時間単価を計算する単価計算手段５０と、前記休憩許容時間までの休憩を組み込むことで割引の適用を受ける経路を含む各経路についてそのコストを前記時間単価を用いて金額に換算して比較することにより最適経路を探索計算する経路計算手段６０と、を有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータを用いた経路探索に関する。
【背景技術】
【０００２】
インターネット等におけるウェブサービスや、カーナビゲーション装置等の分野で、指定された出発地と目的地から最適な経路を計算する、いわゆる経路探索の技術がある。経路探索は、道路のネットワーク構造を表すネットワークデータを基に、ダイクストラ法やＡ＊（Ａスター）法などのアルゴリズムを使って、考えられる複数の候補を作成し比較選択することで最適な経路を求めるものである。昨今、高速道路等の有料道路では時間帯に応じた割引サービス（例えばＥＴＣ割引）が実施されているが、これらの割引を考慮した経路探索の技術も提案されている。
【０００３】
例えば、割引時間帯直前の場合、どこかで休憩して時刻を待つという選択肢が考えられる。この点、入力された出発時刻に基づいて経路を探索し、有料道路の割引時間帯とそこを通りそうな時間帯が近い場合に、休憩時間やそのためのサービスエリア等の情報を知らせる提案が複数存在する（例えば、特許文献１、２及び３参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００７−１１４００８号公報
【特許文献２】特開２００７−１７８２２０号公報
【特許文献３】特開２００８−１５７７３２号公報
【特許文献４】特開２００１−２６４０９７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上記のように行程に休憩を組み込んで割引時間帯を待つことの是非は、ユーザや時と場合により一律でないが、従来の技術では、休憩を組み込む事の可否判断基準の設定や調整が、割引という金額的利益と、非金額的要素である休憩との利益衡量に関るため、事実上困難であった。特に、ダイクストラ法やＡ＊法は、道路区間を表すリンクに設定された通過所要時間等のコストに基づいて原則的に最短経路を求めるものであるため、休憩等の停止を条件に入れて最短以外の経路を探索する際、細かい条件設定を行うのは難しいという課題があった。特に特許文献３の技術では、出発地、目的地、出発時刻に加え、運転手の休憩間隔等の詳細な設定入力が必須で煩雑という問題もあった。
【０００６】
また、ネットワークのリンクコストに基づいて複数の経路を生成し、そこに高速道路や人件費等の非リンクコストを加えてトータルコストを求める提案では（特許文献４参照）、リンクコストに基づく経路に高速道路料金等の費用の要素を加えることが出来るが、複数の経路を求める必要があるため、計算時間がかかるという問題があるうえ、非リンクコストとして休憩時間を含めることは想定されておらず、上記の課題に関するものではなかった。
【０００７】
本発明は、上記の課題を解決するもので、その目的は、経路探索において、時間を含む全コストを金額換算して最適な経路を探索するとともに、金額換算時の時間単価を割引率と休憩許容時間に基づいて変動させることにより、ユーザや状況に最も適合した経路を提供することである。
【課題を解決するための手段】
【０００８】
上記の目的をふまえ、本発明の一態様は、コンピュータが、道路のネットワーク構造を表すネットワークデータと、有料道路の時間帯ごとの割引率を表す割引データと、に基づいて、最適な経路を提示する経路探索装置であって、出発地、目的地、出発時刻を含む探索条件の入力を受け付ける条件受付手段と、休憩許容時間の設定を受け付ける許容値設定手段と、前記出発地と前記目的地の直線距離を計算する直線距離計算手段と、前記直線距離、前記休憩許容時間及び前記割引データから、休憩許容時間を所要時間に含んで前記割引率の適用がある場合のトータルコストと、前記休憩許容時間を所要時間に含まず前記割引率の適用がない場合のトータルコストと、が略均衡する時間単価を計算する単価計算手段と、前記休憩許容時間までの休憩を組み込むことで前記割引率の適用を受ける経路を含む各経路についてそのコストを前記時間単価を用いて金額に換算して比較することにより最適経路を探索計算する経路計算手段と、探索計算で得た前記最適経路を出力する経路出力手段と、を有することを特徴とする。
【０００９】
上記態様を方法という見方で捉えた態様としては、コンピュータが、道路のネットワーク構造を表すネットワークデータと、有料道路の時間帯ごとの割引率を表す割引データと、に基づいて、最適な経路を提示する経路探索方法であって、出発地、目的地、出発時刻を含む探索条件の入力を受け付ける条件受付ステップと、休憩許容時間の設定を受け付ける許容値設定ステップと、前記出発地と前記目的地の直線距離を計算する直線距離計算ステップと、前記直線距離、前記休憩許容時間及び前記割引データから、休憩許容時間を所要時間に含んで前記割引率の適用がある場合のトータルコストと、前記休憩許容時間を所要時間に含まず前記割引率の適用がない場合のトータルコストと、が略均衡する時間単価を計算する単価計算ステップと、前記休憩許容時間までの休憩を組み込むことで前記割引率の適用を受ける経路を含む各経路についてそのコストを前記時間単価を用いて金額に換算して比較することにより最適経路を探索計算する経路計算ステップと、探索計算で得た前記最適経路を出力する経路出力ステップと、を前記コンピュータが実行することを特徴とする。
【００１０】
上記態様をコンピュータ・プログラムという見方で捉えた態様としては、コンピュータに、道路のネットワーク構造を表すネットワークデータと、有料道路の時間帯ごとの割引率を表す割引データと、に基づいて、最適な経路を提示させる経路探索プログラムであって、そのプログラムは前記コンピュータを制御することにより、出発地、目的地、出発時刻を含む探索条件の入力を受け付ける条件受付ステップと、休憩許容時間の設定を受け付ける許容値設定ステップと、前記出発地と前記目的地の直線距離を計算する直線距離計算ステップと、前記直線距離、前記休憩許容時間及び前記割引データから、休憩許容時間を所要時間に含んで前記割引率の適用がある場合のトータルコストと、前記休憩許容時間を所要時間に含まず前記割引率の適用がない場合のトータルコストと、が略均衡する時間単価を計算する単価計算ステップと、前記休憩許容時間までの休憩を組み込むことで前記割引率の適用を受ける経路を含む各経路についてそのコストを前記時間単価を用いて金額に換算して比較することにより最適経路を探索計算する経路計算ステップと、探索計算で得た前記最適経路を出力する経路出力ステップと、を実行させることを特徴とする。
【００１１】
このように、有料道路料金と時間を含む全てのコストを金額に換算して経路探索を行なうことにより、休憩で時間をずらして割引を受ける経路を選択肢に含めて、ユーザにとって所要時間と通行料金のバランスがとれた最適な経路を容易に探索することが可能になる。また、時間帯ごとの割引率と利用者の指定する休憩許容時間に基づいて、経路探索の基準となる時間単価を変動させることにより、与えられた条件、特に個別のユーザや状況に最も適合した経路を探索し提示することが可能になる。特に、休憩をとって割引を受ける場合と休憩も割引もない場合の各選択肢の各コストが略均衡する時間単価を用いることで、一方の選択肢に偏らないバランスの取れた経路選択が実現できる。
【００１２】
本発明の他の態様は、上記いずれかの態様において、前記単価計算手段（ステップ）は、基準となる所定の高速道路料金に、前記割引率を乗じ、前記休憩許容時間で除することにより、前記時間単価を計算することを特徴とする。
【００１３】
このように、高速道路料金に割引率を乗じ、休憩許容時間で除するという簡潔な計算で時間単価を計算することにより、車載ナビゲーション装置やポータブル情報機器のように演算能力が限定されている場合でも少ない負荷で迅速に処理結果が得られる。
【００１４】
なお、上記の各態様に対応する方法又はプログラムといった他のカテゴリや、以下に説明するさらに具体的な各態様も、本発明に含まれる。
【発明の効果】
【００１５】
以上のように、本発明によれば、経路探索において、時間を含む全コストを金額換算して最適な経路を探索するとともに、金額換算時の時間単価を割引率と休憩許容時間に基づいて変動させることにより、ユーザや状況に最も適合した経路を提供することが可能となる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施形態の構成を示す機能ブロック図。
【図２】本発明の実施形態における各情報（データ）を例示する図。
【図３】本発明の実施形態における処理手順を示すフローチャート。
【図４】本発明の実施形態における時間単価設定などの処理手順を示すフローチャート。
【図５】本発明の実施形態における時間単価計算の一例を示すグラフ。
【図６】本発明の実施形態における時間単価計算の他の例を示すグラフ。
【図７】本発明の実施形態における経路ごとの料金算出の処理手順を示すフローチャート。
【図８】本発明の実施形態における経路案内を例示する出力例。
【図９】本発明の実施形態における金額換算によるコスト計算を例示する出力例。
【図１０】本発明の実施形態における経路途中における金額換算によるコスト計算を例示する出力例。
【発明を実施するための形態】
【００１７】
次に、本発明を実施するための形態（「実施形態」と呼ぶ）について、図に沿って説明する。なお、背景技術や課題などで既に述べた内容と共通の前提事項については適宜省略する。
【００１８】
〔１．構成〕
本実施形態は、図１（構成図）に示すように、コンピュータが、道路のネットワーク構造を表すネットワークデータと、有料道路の時間帯ごとの割引率を表す割引データと、に基づいて、最適な経路を提示するウェブサーバとして実現した経路探索装置（以下「本装置」とも呼ぶ）１に関するものである。
【００１９】
まず、本装置１は（図１）、一般的なコンピュータの構成として、少なくとも、ＣＰＵなどの演算制御部５と、外部記憶装置（ＨＤＤ等）や主メモリ等の記憶装置６と、通信ネットワーク（インターネットや携帯電話網など）Ｎとの通信手段７（ＬＡＮアダプタなど）と、を有する。また、ユーザ端末Ｔ２は、パーソナルコンピュータや携帯電話端末装置などであり、搭載しているウェブブラウザなどで本装置１にアクセスする。
【００２０】
そして、本装置１では、記憶装置６に予め記憶（インストール）した図示しない所定のコンピュータ・プログラムが演算制御部５を制御することで、図１に示す各手段などの要素（２０，３０…など）を実現する。これら各要素のうち、情報の記憶手段は、記憶装置６において各種データベース（「ＤＢ」とも表す）やファイル、配列等の変数、システム設定値など任意の形式で実現できる。
【００２１】
記憶手段のうち、ネットワークデータ記憶手段６５は、道路のネットワーク構造を表すネットワークデータを予め記憶しているものである。道路のネットワーク構造は、道路区間を表すリンクを、道路の交差や分岐、屈曲点などを表すノード（結節点）で結合して表す。リンクは、道路区間を通行可能な方向ごとに、始点と終点で定義されるので、一方通行の道路区間には一本、双方向通行可能な道路区間には、互いに逆方向に二本設定される。
【００２２】
このようなネットワーク構造を表すネットワークデータは、図２（１）に例示するように、道路区間を表すリンクのリンクＩＤごとに、始点ノードＩＤと終点ノードＩＤ、通過所要時間などのコスト、道路種別などの情報を有する。
【００２３】
また、割引データ記憶手段５５は、有料道路の時間帯ごとの割引率を表す割引データを、図２（２）に例示するＥＴＣ割引料金テーブルなど適宜な形式で予め記憶している。図２（２）のＥＴＣ割引料金テーブルは、「曜日・時間帯」ごとにＥＴＣ利用時の割引率である「ＥＴＣ割引率」を対応付けたデータであり、画面表示用等に割引名称のような備考事項を加えてもよい。なお、記憶手段以外の各手段は、以下に説明する情報処理の機能・作用を実現・実行する処理手段である。
【００２４】
〔２．作用〕
上記のように構成した本装置１では、図３のフローチャートに示すように、まず、経路計算手段６０が経路計算用地図データとして、図２（１）に例示したようなネットワークデータをネットワークデータ記憶手段６５から所定のワークエリアに読み込む（ステップＳ１０）。続いて、条件受付手段２０が、ユーザ端末Ｔ２から通信ネットワークＮ経由で、出発地、目的地、出発時刻を含む探索条件の入力を受け付ける（ステップＳ２０）。出発時刻は、ユーザが明示的に指定操作をせずとも、経路探索結果を提供後、まもなく出発する前提で、数分後などの時刻を補充するように構成してもよい。
【００２５】
そして、直線距離計算手段３０が、前記出発地と前記目的地の直線距離を計算し、この直線距離をＡ＊法の初期値として設定し（ステップＳ３０）、この初期値である直線距離をもとに、Ａ＊法での下限推定値に対応するいわゆるヒューリスティック項目となるコスト（時間、距離、料金）を設定する（ステップＳ４０）。
【００２６】
〔２−１．時間単価の計算〕
ここで、経路計算では一般に候補となる複数の経路同士のコストを比較し、コストが最小の候補を最適経路とするが、この際のコストに料金すなわち本発明の金額換算を用いる場合（ステップＳ４５）、単価計算手段５０が、経路コストの金額換算に用いる時間単価を計算するが、この計算として具体的には、コストを金額に換算する距離単価や時間単価などを記憶しているテーブルを取得する（ステップＳ５０）。
【００２７】
このようにテーブルを取得する処理手順を図４のフローチャートに示す。すなわち、まず、距離を金額に換算する距離単価を設定する（ステップＳ５１）。距離単価は、燃料代（燃費）を想定したもので、例えば１０円／ｋｍなどである。
【００２８】
続いて、ユーザの設定や選択などに応じて、時間単価を変動値にしない場合は（ステップＳ５２：「ＮＯ」）、時間単価として予め用意された固定の初期値を設定するが（ステップＳ５３）、時間単価を変動値にする場合は（ステップＳ５２：「ＹＥＳ」）、許容値設定手段４０が、休憩許容時間すなわち休憩時間の許容値の設定を受け付け（ステップＳ５４）、単価計算手段５０が、割引データ記憶手段５５から読み出すＥＴＣ割引の時間帯に応じた内容（典型的には、割引率）に応じ、時間単価を計算して設定する（ステップＳ５５）。
【００２９】
ここで、「時間単価」は、前記直線距離、前記休憩許容時間と、出発地と目的から所定の地域内にあって経路に用いる可能性のある有料道路の前記割引データから、休憩許容時間を所要時間に含んで前記割引率の適用がある場合のトータルコストと、前記休憩許容時間を所要時間に含まず前記割引率の適用がない場合のトータルコストと、が略均衡する時間の単価であり、人件費単価に相当する。
【００３０】
〔２−２．時間単価をグラフで得る例〕
例えば、図５のグラフは、浜松の「中田島砂丘」から名古屋の「東山公園」への経路について、説明のため単純化し、東名高速道路を主に走行して走行距離１１５ｋｍ、通常の高速道路料金２６００円、走行時間７５分と想定する場合を例にとって、横軸の時間単価の場合に、縦軸のトータルコストがいくらになるかを表すものである。
【００３１】
なお、距離としては、本来は出発地と目的地間の直線距離を用いるが、ここでは説明を簡単にするため、ほぼ直線のルートで、走行距離がそのまま直線距離と等しかったと仮定する。また、平均時速についても、１ｋｍ／１分（時速６０ｋｍ）に統一するものとする。
【００３２】
また、ここでいうトータルコスト（「Ｃ」とする）は、
＜数式１＞
Ｃ＝（距離×距離単価）＋（時間×時間単価）＋高速道路料金
であり、このトータルコストとして、図５の太い実線は、休憩時間無しで割引も無しの通常コスト、細かい破線は休憩時間２０分を所要時間に含んで３０％割引の場合のコスト、粗い破線は休憩時間２０分を所要時間に含んで５０％割引の場合のコスト、（一点鎖線は参考までに休日割引で一律１０００円の場合のコスト）をそれぞれ示している。
【００３３】
このうち例えば、休憩して３０％割引のコスト（細かい破線）と、休憩も割引もなしの通常コスト（太い実線）が略均衡する点Ｂ１は、白抜きの丸印で示すが、そこから下方に向く矢印の示す時間単価は２０００円と２５００円の間を示している。同様に、通常コスト（太い実線）が、休憩して５０％割引のコスト（粗い破線）と、略均衡する点Ｂ２については、下方に向く矢印の示す時間単価は４０００円弱を示している。
【００３４】
これら均衡については、適宜な刻みでいろいろな時間単価を代入してそれぞれのトータルコストを実際に試算して順次比較したり、それらトータルコストに基づいて図５のようなグラフを実際に描画するなどして特定することができるが、次のような計算式を用いて簡潔に算出することもできる。
【００３５】
〔２−３．時間単価を簡易な計算で得る例〕
例えば、
ｄ：距離（＝所要分数）
ｇ：距離単価
ｊ：時間単価（分）
ｋ：高速道路通常料金
ｗ：割引率
ｒ：休憩許容時間
とする場合、「休憩許容時間を所要時間に含んで前記割引率の適用がある場合のトータルコストと、前記休憩許容時間を所要時間に含まず前記割引率の適用がない場合のトータルコストと、が略均衡」する状態は、上記数式１を両辺に配して
＜数式２＞
ｄｇ＋ｄｊ＋ｋ＝ｄｇ＋（ｄ＋ｒ）ｊ＋ｋ（１−ｗ）
と表すことができる。
【００３６】
この両辺から項ｄｇを消して各項を展開し、
＜数式３＞
ｄｊ＋ｋ＝ｄｊ＋ｒｊ＋ｋ−ｋｗ
項ｄｊと項ｋも両辺から消したうえ、右辺ｒｊを左辺へ移し両辺から負号を除けば、
＜数式４＞
ｒｊ＝ｋｗ
【００３７】
これは即ち、
＜数式５＞
休憩許容時間ｒ×時間単価ｊ＝高速道路通常料金ｋ×割引率ｗ
つまり、休憩許容時間分の人件費が、高速道路通常料金の割引分と均衡することを意味しており、さらに両辺をｒで除して、
＜数式６＞
ｊ＝ｋｗ／ｒ
即ち、
＜数式７＞
時間単価ｊ＝高速道路通常料金ｋ×割引率ｗ／休憩許容時間ｒ
【００３８】
これは、高速道路通常料金に割引率を乗じ、休憩許容時間で除するという簡潔な計算で時間単価を計算することにより、車載ナビゲーション装置やポータブル情報機器のように演算能力が限定されている場合でも少ない負荷で迅速に処理結果が得られることを意味する。
【００３９】
例えば、図５のグラフ（点Ｂ１）の条件とした高速道路通常料金ｋ＝２６００円、割引率ｗ＝０．３、休憩許容時間ｒ＝２０（分）を上記数式７に代入すれば、
＜数式８＞
時間単価ｊ＝２６００×０．３／２０ ＝３９円（１分あたり）
【００４０】
この時間単価（３９円／分）は、６０分あたりのいわば時給に直せば２３４０円となり、図５のグラフの点Ｂ１に略一致する。また、割引率ｗ＝０．５だと点Ｂ２に略一致する３９００円となる。なお、このように計算した時間単価は、そのまま用いる必要はなく、例えば残り経路のコストが小さく出る分には差し支えないＡ＊法の特性への配慮などの各種事情に応じ、適宜な刻みの単位で扱いやすいキリのよい数字（例えば、２２５０円、３８００円、４０００円など）に切り下げたり適宜な桁で四捨五入するなど丸めて用いればよい。
【００４１】
また、図６は、休憩許容時間を１０分に半減した他は図５と同条件とした場合のグラフであり、上記数式７で計算する時間単価は、点Ｂ３に対応するものが４６８０円、点Ｂ４に対応するものが７８００円となり、例えばこれらも４７００円、７７００円などに切り下げたり丸めて用いることができる。
【００４２】
〔２−４．経路の計算と出力〕
次に、経路計算手段６０が最適経路を探索計算し（図３：ステップＳ６０）、経路出力手段７０が、探索計算で得た前記最適経路を探索結果として取得し（ステップＳ７０）出力する（ステップＳ７５）。そして、本装置１では、経路計算手段６０が、最適経路の探索計算を行う際（経路逸脱等による再計算の場合を含む）、前記休憩許容時間（２０分、１０分など）までの休憩を組み込むことで前記割引率（３０％、５０％など）の適用を受ける経路を含む各経路について、そのコスト（時間、距離、料金）を前記時間単価を用いて金額に換算して比較することにより最適経路を探索計算する。
【００４３】
最適経路の探索計算では、より具体的には、図７のフローチャートに示すように、経路が有料道路を含む場合のうち（ステップＳ６１：「ＹＥＳ」）、そもそも想定される走行時間のままで割引があれば（ステップＳ６２：「ＹＥＳ」）、所定のＥＴＣ割引料金テーブル（図２（２））より料金を算出する（ステップＳ６７）。
【００４４】
一方、経路が有料道路を含むが（ステップＳ６１：「ＹＥＳ」）、想定される走行時間のままでは割引が適用されない場合は（ステップＳ６２：「ＮＯ」）、休憩許容時間内の休憩を組み込むことで走行時間をずらせば割引適用があるか判断する（ステップＳ６３）。そして、休憩許容時間内ずらして割引適用が有って（ステップＳ６３：「ＹＥＳ」）、かつ、経路内に休憩施設があれば（ステップＳ６４：「ＹＥＳ」）、有料道路の走行時刻を割引対象の時間帯に適合させるための休憩必要時間を算出しその休憩時間を所要時間に加算したうえ（ステップＳ６５）、所定のＥＴＣ割引料金テーブル（図２（２））より料金を算出する（ステップＳ６７）。
【００４５】
休憩許容時間ずらしても割引適用がない場合と（ステップＳ６３：「ＮＯ」）、休憩許容時間内ずらせば割引適用は有るが（ステップＳ６３：「ＹＥＳ」）経路内に休憩施設がない場合（ステップＳ６４：「ＮＯ」）は、従来の経路探索と同様な通常料金のテーブルを用いて道路料金を算出する（ステップＳ６６）。このような通常料金のテーブルについては、図示はしないが、従来に準じたものを用いればよい。また、休憩施設としては、有料道路上のいわゆるサービスエリア（ＳＡ）やパーキングエリア（ＰＡ）に限らず、有料道路以外の飲食店やコンビニエンスストア、ショッピングセンター、景勝スポットなどでもよい。
【００４６】
休憩施設に関する判断の具体的手法は自由であり、例えば、サービスエリア（ＳＡ）、パーキングエリア（ＰＡ）、ファミリーレストランなどの飲食店、「道の駅」のような一般道路休憩施設、コンビニエンスストア、ショッピングセンター、景勝スポットなどのＰＯＩ（施設情報）について、既存の施設情報データから判定する業種等が所定の種類であれば、一律に５分から６０分程度まで休憩可能とみなしてもよいし、それら施設情報ごとのデータに休憩の可否や想定休憩時間などの属性を適宜設けて利用してもよいし、そのような属性を各休憩施設の情報と対応付けた専用の情報記憶手段を設けてもよい。
【００４７】
〔２−５．休憩を考慮した経路探索の例〕
ここで、図５のグラフで前提としたのと同じ例（浜松の「中田島砂丘」→名古屋の「東山公園」、走行距離１１５ｋｍ、通常の高速道路料金２６００円、走行時間７５分、休憩許容時間２０分）について、休憩を考慮して経路を探索し案内する例を示す。例えば、出口料金所通過時刻を基準に割引の適用を判断する場合、１５：３０に出発してそのまま休憩無しで走行すると、図８（１）に示すように、通勤割引（図２（２））時間帯の１７時直前の１６：５９に名古屋ＩＣ（インターチェンジ）を出るので、高速料金は割引無しの通常料金で２６００円である。この休憩を含まない経路を「通常走行」や「休憩なし」と呼ぶこととする。
【００４８】
対して、図８（２）に示すように、同じ時刻（１５：３０）に出発しても途中の下り線東郷ＰＡ（パーキングエリア）あたりで１５分休憩（図中、枠囲み）を取れば、出口料金所（名古屋ＩＣ）で通勤割引時間帯の１７時を過ぎる（１７：１４）ので高速料金は５０％割引の１３００円となる（図中、下線部）。この休憩を含む経路を「休憩あり」と呼ぶこととする。
【００４９】
経路探索の計算においてこれら２つの候補「通常走行」と「休憩あり」のいずれを選択してユーザに対して案内すべきかを判断するためのコスト計算は、既に挙げた数式１にしたがって、図９に示す通りとなり、「休憩なし」と比べて「休憩あり」は、１５分余分に時間はかかるが、金額換算のトータルコストが８４５０円と３００円安いので、「休憩あり」（図９（２））を選択してユーザに案内することになる。
【００５０】
上記のようなコスト計算は、出発時に限らず、経路途中でユーザ操作などにしたがって行ってもよい。ここでは、経路計算アルゴリズムはＡ＊法のため、計算途中の各々の経路選択は
＜数式９＞
（ａ．ある地点まで実際にかかったコスト）＋（ｂ．目的地までの残りコスト）
が最小になるように判断する。ここで
＜数式１０＞
（ａ）ある地点まで実際にかかったコスト
＝出発地からある地点までの距離 × 距離単価
＋出発地からある地点までかかった時間 × 時間単価
＋そこまでの有料道路料金
となるが、ここで、有料道路上にいる場合の有料道路料金は、最も近い次に降りられるＩＣ（ここでは料金所の意）で計算する。また、
＜数式１１＞
（ｂ）目的までの残りコスト
＝目的地までの残り距離 × 距離単価
＋目的地までの残り時間予測値 × 時間単価
で、経路選択の判断は、より小さい値であればよいため、ここでいう残りコストは有料道路料金は含まない。
【００５１】
このような計算を、上記経路の途中１００ｋｍ地点の東名三好ＩＣで行った例は、図１０に示す通りとなる。この場合も、途中に休憩施設があればそこで休憩して出口料金所の通過時刻を進める「休憩あり」（図１０（２））は、「休憩なし」（図１０（１））と比べて、１５分余分に時間はかかるが、１００ｋｍ地点までの料金が安く（図１０（２）：２３５０円⇒１２００円）なって金額換算のトータルコストも安くなるので（図１０（２）：７３５０円⇒７２００円（下線部））、「休憩あり」（図１０（２））を選択してユーザに案内することになる。
【００５２】
なお、フェリー航路を使用する場合、経路がフェリー航路を表すリンクを含むときは、予め用意してある出航時刻などを表すフェリー情報データから待ち時間や所要時間を得て、それに基づいて待ち時間や所要時間のコストを経路のコストに加算する。そのうえで、コストの判定基準が時間・距離ではなく、これまで説明してきたように金額に換算したトータルコストの場合は、フェリーの該当する車種の料金を経路の金額に加算したうえ、他の経路との比較選択の対象とすればよい。
【００５３】
〔３．効果〕
以上のように、本実施形態では、有料道路料金と時間を含む全てのコストを金額に換算して経路探索を行なうことにより、休憩で時間をずらして割引を受ける経路を選択肢に含めて、ユーザにとって所要時間と通行料金のバランスがとれた最適な経路を容易に探索することが可能になる。また、時間帯ごとの割引率と利用者の指定する休憩許容時間に基づいて、経路探索の基準となる時間単価を変動させることにより、与えられた条件、特に個別のユーザや利用時の状況に最も適合した経路を探索し提示することが可能になる。
【００５４】
特に、休憩をとって割引を受ける場合と、休憩も割引もない場合の各選択肢の各コストが略均衡する時間単価を用いることで、一方の選択肢に偏らないバランスの取れた経路選択が実現できる。
【００５５】
〔４．他の実施形態〕
なお、上記各実施形態は例示に過ぎず、本発明は、以下に例示するものやそれ以外の他の実施態様も含むものである。例えば、本発明において、各手段などの要素は、コンピュータの演算制御部に限らず、ワイヤードロジック等に基づく電子回路や、今後登場する非ノイマン型等の情報処理機構で実現してもよい。また、各構成図、データの図、フローチャートの図などは例示に過ぎず、各要素の有無、その順序や具体的内容などは適宜変更可能である。
【００５６】
例えば、本装置を複数のサーバ装置で実現したり、各端末を含めて本発明のシステムとして把握したり、機能によっては外部のプラットフォーム等をＡＰＩ（アプリケーション・プログラム・インタフェース）やネットワークコンピューティングなどで呼び出して実現するなど、構成は柔軟に変更できる。また、上記実施形態は、通信ネットワークのクライアントサーバシステムを前提としたが、本発明はカーナビゲーション装置のようなスタンドアロンでもよい。
【００５７】
さらに、本発明は、パーソナルコンピュータやいわゆるスマートフォンなどに代表される各種コンピュータ類にインストールして用いるコンピュータ・プログラムとして実現することも可能であり、もちろん、有償無償を問わずそのようなプログラムをダウンロード提供するウェブサイトやサーバも本発明の態様に含まれる。
【符号の説明】
【００５８】
Ｔ２ ユーザ端末
１ 経路探索装置
５ 演算制御部
６ 記憶装置
７ 通信手段
２０ 条件受付手段
３０ 直線距離計算手段
４０ 許容値設定手段
５０ 単価計算手段
５５ 割引データ記憶手段
６０ 経路計算手段
６５ ネットワークデータ記憶手段
７０ 経路出力手段
【技術分野】
【０００１】
本発明は、コンピュータを用いた経路探索に関する。
【背景技術】
【０００２】
インターネット等におけるウェブサービスや、カーナビゲーション装置等の分野で、指定された出発地と目的地から最適な経路を計算する、いわゆる経路探索の技術がある。経路探索は、道路のネットワーク構造を表すネットワークデータを基に、ダイクストラ法やＡ＊（Ａスター）法などのアルゴリズムを使って、考えられる複数の候補を作成し比較選択することで最適な経路を求めるものである。昨今、高速道路等の有料道路では時間帯に応じた割引サービス（例えばＥＴＣ割引）が実施されているが、これらの割引を考慮した経路探索の技術も提案されている。
【０００３】
例えば、割引時間帯直前の場合、どこかで休憩して時刻を待つという選択肢が考えられる。この点、入力された出発時刻に基づいて経路を探索し、有料道路の割引時間帯とそこを通りそうな時間帯が近い場合に、休憩時間やそのためのサービスエリア等の情報を知らせる提案が複数存在する（例えば、特許文献１、２及び３参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００７−１１４００８号公報
【特許文献２】特開２００７−１７８２２０号公報
【特許文献３】特開２００８−１５７７３２号公報
【特許文献４】特開２００１−２６４０９７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上記のように行程に休憩を組み込んで割引時間帯を待つことの是非は、ユーザや時と場合により一律でないが、従来の技術では、休憩を組み込む事の可否判断基準の設定や調整が、割引という金額的利益と、非金額的要素である休憩との利益衡量に関るため、事実上困難であった。特に、ダイクストラ法やＡ＊法は、道路区間を表すリンクに設定された通過所要時間等のコストに基づいて原則的に最短経路を求めるものであるため、休憩等の停止を条件に入れて最短以外の経路を探索する際、細かい条件設定を行うのは難しいという課題があった。特に特許文献３の技術では、出発地、目的地、出発時刻に加え、運転手の休憩間隔等の詳細な設定入力が必須で煩雑という問題もあった。
【０００６】
また、ネットワークのリンクコストに基づいて複数の経路を生成し、そこに高速道路や人件費等の非リンクコストを加えてトータルコストを求める提案では（特許文献４参照）、リンクコストに基づく経路に高速道路料金等の費用の要素を加えることが出来るが、複数の経路を求める必要があるため、計算時間がかかるという問題があるうえ、非リンクコストとして休憩時間を含めることは想定されておらず、上記の課題に関するものではなかった。
【０００７】
本発明は、上記の課題を解決するもので、その目的は、経路探索において、時間を含む全コストを金額換算して最適な経路を探索するとともに、金額換算時の時間単価を割引率と休憩許容時間に基づいて変動させることにより、ユーザや状況に最も適合した経路を提供することである。
【課題を解決するための手段】
【０００８】
上記の目的をふまえ、本発明の一態様は、コンピュータが、道路のネットワーク構造を表すネットワークデータと、有料道路の時間帯ごとの割引率を表す割引データと、に基づいて、最適な経路を提示する経路探索装置であって、出発地、目的地、出発時刻を含む探索条件の入力を受け付ける条件受付手段と、休憩許容時間の設定を受け付ける許容値設定手段と、前記出発地と前記目的地の直線距離を計算する直線距離計算手段と、前記直線距離、前記休憩許容時間及び前記割引データから、休憩許容時間を所要時間に含んで前記割引率の適用がある場合のトータルコストと、前記休憩許容時間を所要時間に含まず前記割引率の適用がない場合のトータルコストと、が略均衡する時間単価を計算する単価計算手段と、前記休憩許容時間までの休憩を組み込むことで前記割引率の適用を受ける経路を含む各経路についてそのコストを前記時間単価を用いて金額に換算して比較することにより最適経路を探索計算する経路計算手段と、探索計算で得た前記最適経路を出力する経路出力手段と、を有することを特徴とする。
【０００９】
上記態様を方法という見方で捉えた態様としては、コンピュータが、道路のネットワーク構造を表すネットワークデータと、有料道路の時間帯ごとの割引率を表す割引データと、に基づいて、最適な経路を提示する経路探索方法であって、出発地、目的地、出発時刻を含む探索条件の入力を受け付ける条件受付ステップと、休憩許容時間の設定を受け付ける許容値設定ステップと、前記出発地と前記目的地の直線距離を計算する直線距離計算ステップと、前記直線距離、前記休憩許容時間及び前記割引データから、休憩許容時間を所要時間に含んで前記割引率の適用がある場合のトータルコストと、前記休憩許容時間を所要時間に含まず前記割引率の適用がない場合のトータルコストと、が略均衡する時間単価を計算する単価計算ステップと、前記休憩許容時間までの休憩を組み込むことで前記割引率の適用を受ける経路を含む各経路についてそのコストを前記時間単価を用いて金額に換算して比較することにより最適経路を探索計算する経路計算ステップと、探索計算で得た前記最適経路を出力する経路出力ステップと、を前記コンピュータが実行することを特徴とする。
【００１０】
上記態様をコンピュータ・プログラムという見方で捉えた態様としては、コンピュータに、道路のネットワーク構造を表すネットワークデータと、有料道路の時間帯ごとの割引率を表す割引データと、に基づいて、最適な経路を提示させる経路探索プログラムであって、そのプログラムは前記コンピュータを制御することにより、出発地、目的地、出発時刻を含む探索条件の入力を受け付ける条件受付ステップと、休憩許容時間の設定を受け付ける許容値設定ステップと、前記出発地と前記目的地の直線距離を計算する直線距離計算ステップと、前記直線距離、前記休憩許容時間及び前記割引データから、休憩許容時間を所要時間に含んで前記割引率の適用がある場合のトータルコストと、前記休憩許容時間を所要時間に含まず前記割引率の適用がない場合のトータルコストと、が略均衡する時間単価を計算する単価計算ステップと、前記休憩許容時間までの休憩を組み込むことで前記割引率の適用を受ける経路を含む各経路についてそのコストを前記時間単価を用いて金額に換算して比較することにより最適経路を探索計算する経路計算ステップと、探索計算で得た前記最適経路を出力する経路出力ステップと、を実行させることを特徴とする。
【００１１】
このように、有料道路料金と時間を含む全てのコストを金額に換算して経路探索を行なうことにより、休憩で時間をずらして割引を受ける経路を選択肢に含めて、ユーザにとって所要時間と通行料金のバランスがとれた最適な経路を容易に探索することが可能になる。また、時間帯ごとの割引率と利用者の指定する休憩許容時間に基づいて、経路探索の基準となる時間単価を変動させることにより、与えられた条件、特に個別のユーザや状況に最も適合した経路を探索し提示することが可能になる。特に、休憩をとって割引を受ける場合と休憩も割引もない場合の各選択肢の各コストが略均衡する時間単価を用いることで、一方の選択肢に偏らないバランスの取れた経路選択が実現できる。
【００１２】
本発明の他の態様は、上記いずれかの態様において、前記単価計算手段（ステップ）は、基準となる所定の高速道路料金に、前記割引率を乗じ、前記休憩許容時間で除することにより、前記時間単価を計算することを特徴とする。
【００１３】
このように、高速道路料金に割引率を乗じ、休憩許容時間で除するという簡潔な計算で時間単価を計算することにより、車載ナビゲーション装置やポータブル情報機器のように演算能力が限定されている場合でも少ない負荷で迅速に処理結果が得られる。
【００１４】
なお、上記の各態様に対応する方法又はプログラムといった他のカテゴリや、以下に説明するさらに具体的な各態様も、本発明に含まれる。
【発明の効果】
【００１５】
以上のように、本発明によれば、経路探索において、時間を含む全コストを金額換算して最適な経路を探索するとともに、金額換算時の時間単価を割引率と休憩許容時間に基づいて変動させることにより、ユーザや状況に最も適合した経路を提供することが可能となる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施形態の構成を示す機能ブロック図。
【図２】本発明の実施形態における各情報（データ）を例示する図。
【図３】本発明の実施形態における処理手順を示すフローチャート。
【図４】本発明の実施形態における時間単価設定などの処理手順を示すフローチャート。
【図５】本発明の実施形態における時間単価計算の一例を示すグラフ。
【図６】本発明の実施形態における時間単価計算の他の例を示すグラフ。
【図７】本発明の実施形態における経路ごとの料金算出の処理手順を示すフローチャート。
【図８】本発明の実施形態における経路案内を例示する出力例。
【図９】本発明の実施形態における金額換算によるコスト計算を例示する出力例。
【図１０】本発明の実施形態における経路途中における金額換算によるコスト計算を例示する出力例。
【発明を実施するための形態】
【００１７】
次に、本発明を実施するための形態（「実施形態」と呼ぶ）について、図に沿って説明する。なお、背景技術や課題などで既に述べた内容と共通の前提事項については適宜省略する。
【００１８】
〔１．構成〕
本実施形態は、図１（構成図）に示すように、コンピュータが、道路のネットワーク構造を表すネットワークデータと、有料道路の時間帯ごとの割引率を表す割引データと、に基づいて、最適な経路を提示するウェブサーバとして実現した経路探索装置（以下「本装置」とも呼ぶ）１に関するものである。
【００１９】
まず、本装置１は（図１）、一般的なコンピュータの構成として、少なくとも、ＣＰＵなどの演算制御部５と、外部記憶装置（ＨＤＤ等）や主メモリ等の記憶装置６と、通信ネットワーク（インターネットや携帯電話網など）Ｎとの通信手段７（ＬＡＮアダプタなど）と、を有する。また、ユーザ端末Ｔ２は、パーソナルコンピュータや携帯電話端末装置などであり、搭載しているウェブブラウザなどで本装置１にアクセスする。
【００２０】
そして、本装置１では、記憶装置６に予め記憶（インストール）した図示しない所定のコンピュータ・プログラムが演算制御部５を制御することで、図１に示す各手段などの要素（２０，３０…など）を実現する。これら各要素のうち、情報の記憶手段は、記憶装置６において各種データベース（「ＤＢ」とも表す）やファイル、配列等の変数、システム設定値など任意の形式で実現できる。
【００２１】
記憶手段のうち、ネットワークデータ記憶手段６５は、道路のネットワーク構造を表すネットワークデータを予め記憶しているものである。道路のネットワーク構造は、道路区間を表すリンクを、道路の交差や分岐、屈曲点などを表すノード（結節点）で結合して表す。リンクは、道路区間を通行可能な方向ごとに、始点と終点で定義されるので、一方通行の道路区間には一本、双方向通行可能な道路区間には、互いに逆方向に二本設定される。
【００２２】
このようなネットワーク構造を表すネットワークデータは、図２（１）に例示するように、道路区間を表すリンクのリンクＩＤごとに、始点ノードＩＤと終点ノードＩＤ、通過所要時間などのコスト、道路種別などの情報を有する。
【００２３】
また、割引データ記憶手段５５は、有料道路の時間帯ごとの割引率を表す割引データを、図２（２）に例示するＥＴＣ割引料金テーブルなど適宜な形式で予め記憶している。図２（２）のＥＴＣ割引料金テーブルは、「曜日・時間帯」ごとにＥＴＣ利用時の割引率である「ＥＴＣ割引率」を対応付けたデータであり、画面表示用等に割引名称のような備考事項を加えてもよい。なお、記憶手段以外の各手段は、以下に説明する情報処理の機能・作用を実現・実行する処理手段である。
【００２４】
〔２．作用〕
上記のように構成した本装置１では、図３のフローチャートに示すように、まず、経路計算手段６０が経路計算用地図データとして、図２（１）に例示したようなネットワークデータをネットワークデータ記憶手段６５から所定のワークエリアに読み込む（ステップＳ１０）。続いて、条件受付手段２０が、ユーザ端末Ｔ２から通信ネットワークＮ経由で、出発地、目的地、出発時刻を含む探索条件の入力を受け付ける（ステップＳ２０）。出発時刻は、ユーザが明示的に指定操作をせずとも、経路探索結果を提供後、まもなく出発する前提で、数分後などの時刻を補充するように構成してもよい。
【００２５】
そして、直線距離計算手段３０が、前記出発地と前記目的地の直線距離を計算し、この直線距離をＡ＊法の初期値として設定し（ステップＳ３０）、この初期値である直線距離をもとに、Ａ＊法での下限推定値に対応するいわゆるヒューリスティック項目となるコスト（時間、距離、料金）を設定する（ステップＳ４０）。
【００２６】
〔２−１．時間単価の計算〕
ここで、経路計算では一般に候補となる複数の経路同士のコストを比較し、コストが最小の候補を最適経路とするが、この際のコストに料金すなわち本発明の金額換算を用いる場合（ステップＳ４５）、単価計算手段５０が、経路コストの金額換算に用いる時間単価を計算するが、この計算として具体的には、コストを金額に換算する距離単価や時間単価などを記憶しているテーブルを取得する（ステップＳ５０）。
【００２７】
このようにテーブルを取得する処理手順を図４のフローチャートに示す。すなわち、まず、距離を金額に換算する距離単価を設定する（ステップＳ５１）。距離単価は、燃料代（燃費）を想定したもので、例えば１０円／ｋｍなどである。
【００２８】
続いて、ユーザの設定や選択などに応じて、時間単価を変動値にしない場合は（ステップＳ５２：「ＮＯ」）、時間単価として予め用意された固定の初期値を設定するが（ステップＳ５３）、時間単価を変動値にする場合は（ステップＳ５２：「ＹＥＳ」）、許容値設定手段４０が、休憩許容時間すなわち休憩時間の許容値の設定を受け付け（ステップＳ５４）、単価計算手段５０が、割引データ記憶手段５５から読み出すＥＴＣ割引の時間帯に応じた内容（典型的には、割引率）に応じ、時間単価を計算して設定する（ステップＳ５５）。
【００２９】
ここで、「時間単価」は、前記直線距離、前記休憩許容時間と、出発地と目的から所定の地域内にあって経路に用いる可能性のある有料道路の前記割引データから、休憩許容時間を所要時間に含んで前記割引率の適用がある場合のトータルコストと、前記休憩許容時間を所要時間に含まず前記割引率の適用がない場合のトータルコストと、が略均衡する時間の単価であり、人件費単価に相当する。
【００３０】
〔２−２．時間単価をグラフで得る例〕
例えば、図５のグラフは、浜松の「中田島砂丘」から名古屋の「東山公園」への経路について、説明のため単純化し、東名高速道路を主に走行して走行距離１１５ｋｍ、通常の高速道路料金２６００円、走行時間７５分と想定する場合を例にとって、横軸の時間単価の場合に、縦軸のトータルコストがいくらになるかを表すものである。
【００３１】
なお、距離としては、本来は出発地と目的地間の直線距離を用いるが、ここでは説明を簡単にするため、ほぼ直線のルートで、走行距離がそのまま直線距離と等しかったと仮定する。また、平均時速についても、１ｋｍ／１分（時速６０ｋｍ）に統一するものとする。
【００３２】
また、ここでいうトータルコスト（「Ｃ」とする）は、
＜数式１＞
Ｃ＝（距離×距離単価）＋（時間×時間単価）＋高速道路料金
であり、このトータルコストとして、図５の太い実線は、休憩時間無しで割引も無しの通常コスト、細かい破線は休憩時間２０分を所要時間に含んで３０％割引の場合のコスト、粗い破線は休憩時間２０分を所要時間に含んで５０％割引の場合のコスト、（一点鎖線は参考までに休日割引で一律１０００円の場合のコスト）をそれぞれ示している。
【００３３】
このうち例えば、休憩して３０％割引のコスト（細かい破線）と、休憩も割引もなしの通常コスト（太い実線）が略均衡する点Ｂ１は、白抜きの丸印で示すが、そこから下方に向く矢印の示す時間単価は２０００円と２５００円の間を示している。同様に、通常コスト（太い実線）が、休憩して５０％割引のコスト（粗い破線）と、略均衡する点Ｂ２については、下方に向く矢印の示す時間単価は４０００円弱を示している。
【００３４】
これら均衡については、適宜な刻みでいろいろな時間単価を代入してそれぞれのトータルコストを実際に試算して順次比較したり、それらトータルコストに基づいて図５のようなグラフを実際に描画するなどして特定することができるが、次のような計算式を用いて簡潔に算出することもできる。
【００３５】
〔２−３．時間単価を簡易な計算で得る例〕
例えば、
ｄ：距離（＝所要分数）
ｇ：距離単価
ｊ：時間単価（分）
ｋ：高速道路通常料金
ｗ：割引率
ｒ：休憩許容時間
とする場合、「休憩許容時間を所要時間に含んで前記割引率の適用がある場合のトータルコストと、前記休憩許容時間を所要時間に含まず前記割引率の適用がない場合のトータルコストと、が略均衡」する状態は、上記数式１を両辺に配して
＜数式２＞
ｄｇ＋ｄｊ＋ｋ＝ｄｇ＋（ｄ＋ｒ）ｊ＋ｋ（１−ｗ）
と表すことができる。
【００３６】
この両辺から項ｄｇを消して各項を展開し、
＜数式３＞
ｄｊ＋ｋ＝ｄｊ＋ｒｊ＋ｋ−ｋｗ
項ｄｊと項ｋも両辺から消したうえ、右辺ｒｊを左辺へ移し両辺から負号を除けば、
＜数式４＞
ｒｊ＝ｋｗ
【００３７】
これは即ち、
＜数式５＞
休憩許容時間ｒ×時間単価ｊ＝高速道路通常料金ｋ×割引率ｗ
つまり、休憩許容時間分の人件費が、高速道路通常料金の割引分と均衡することを意味しており、さらに両辺をｒで除して、
＜数式６＞
ｊ＝ｋｗ／ｒ
即ち、
＜数式７＞
時間単価ｊ＝高速道路通常料金ｋ×割引率ｗ／休憩許容時間ｒ
【００３８】
これは、高速道路通常料金に割引率を乗じ、休憩許容時間で除するという簡潔な計算で時間単価を計算することにより、車載ナビゲーション装置やポータブル情報機器のように演算能力が限定されている場合でも少ない負荷で迅速に処理結果が得られることを意味する。
【００３９】
例えば、図５のグラフ（点Ｂ１）の条件とした高速道路通常料金ｋ＝２６００円、割引率ｗ＝０．３、休憩許容時間ｒ＝２０（分）を上記数式７に代入すれば、
＜数式８＞
時間単価ｊ＝２６００×０．３／２０ ＝３９円（１分あたり）
【００４０】
この時間単価（３９円／分）は、６０分あたりのいわば時給に直せば２３４０円となり、図５のグラフの点Ｂ１に略一致する。また、割引率ｗ＝０．５だと点Ｂ２に略一致する３９００円となる。なお、このように計算した時間単価は、そのまま用いる必要はなく、例えば残り経路のコストが小さく出る分には差し支えないＡ＊法の特性への配慮などの各種事情に応じ、適宜な刻みの単位で扱いやすいキリのよい数字（例えば、２２５０円、３８００円、４０００円など）に切り下げたり適宜な桁で四捨五入するなど丸めて用いればよい。
【００４１】
また、図６は、休憩許容時間を１０分に半減した他は図５と同条件とした場合のグラフであり、上記数式７で計算する時間単価は、点Ｂ３に対応するものが４６８０円、点Ｂ４に対応するものが７８００円となり、例えばこれらも４７００円、７７００円などに切り下げたり丸めて用いることができる。
【００４２】
〔２−４．経路の計算と出力〕
次に、経路計算手段６０が最適経路を探索計算し（図３：ステップＳ６０）、経路出力手段７０が、探索計算で得た前記最適経路を探索結果として取得し（ステップＳ７０）出力する（ステップＳ７５）。そして、本装置１では、経路計算手段６０が、最適経路の探索計算を行う際（経路逸脱等による再計算の場合を含む）、前記休憩許容時間（２０分、１０分など）までの休憩を組み込むことで前記割引率（３０％、５０％など）の適用を受ける経路を含む各経路について、そのコスト（時間、距離、料金）を前記時間単価を用いて金額に換算して比較することにより最適経路を探索計算する。
【００４３】
最適経路の探索計算では、より具体的には、図７のフローチャートに示すように、経路が有料道路を含む場合のうち（ステップＳ６１：「ＹＥＳ」）、そもそも想定される走行時間のままで割引があれば（ステップＳ６２：「ＹＥＳ」）、所定のＥＴＣ割引料金テーブル（図２（２））より料金を算出する（ステップＳ６７）。
【００４４】
一方、経路が有料道路を含むが（ステップＳ６１：「ＹＥＳ」）、想定される走行時間のままでは割引が適用されない場合は（ステップＳ６２：「ＮＯ」）、休憩許容時間内の休憩を組み込むことで走行時間をずらせば割引適用があるか判断する（ステップＳ６３）。そして、休憩許容時間内ずらして割引適用が有って（ステップＳ６３：「ＹＥＳ」）、かつ、経路内に休憩施設があれば（ステップＳ６４：「ＹＥＳ」）、有料道路の走行時刻を割引対象の時間帯に適合させるための休憩必要時間を算出しその休憩時間を所要時間に加算したうえ（ステップＳ６５）、所定のＥＴＣ割引料金テーブル（図２（２））より料金を算出する（ステップＳ６７）。
【００４５】
休憩許容時間ずらしても割引適用がない場合と（ステップＳ６３：「ＮＯ」）、休憩許容時間内ずらせば割引適用は有るが（ステップＳ６３：「ＹＥＳ」）経路内に休憩施設がない場合（ステップＳ６４：「ＮＯ」）は、従来の経路探索と同様な通常料金のテーブルを用いて道路料金を算出する（ステップＳ６６）。このような通常料金のテーブルについては、図示はしないが、従来に準じたものを用いればよい。また、休憩施設としては、有料道路上のいわゆるサービスエリア（ＳＡ）やパーキングエリア（ＰＡ）に限らず、有料道路以外の飲食店やコンビニエンスストア、ショッピングセンター、景勝スポットなどでもよい。
【００４６】
休憩施設に関する判断の具体的手法は自由であり、例えば、サービスエリア（ＳＡ）、パーキングエリア（ＰＡ）、ファミリーレストランなどの飲食店、「道の駅」のような一般道路休憩施設、コンビニエンスストア、ショッピングセンター、景勝スポットなどのＰＯＩ（施設情報）について、既存の施設情報データから判定する業種等が所定の種類であれば、一律に５分から６０分程度まで休憩可能とみなしてもよいし、それら施設情報ごとのデータに休憩の可否や想定休憩時間などの属性を適宜設けて利用してもよいし、そのような属性を各休憩施設の情報と対応付けた専用の情報記憶手段を設けてもよい。
【００４７】
〔２−５．休憩を考慮した経路探索の例〕
ここで、図５のグラフで前提としたのと同じ例（浜松の「中田島砂丘」→名古屋の「東山公園」、走行距離１１５ｋｍ、通常の高速道路料金２６００円、走行時間７５分、休憩許容時間２０分）について、休憩を考慮して経路を探索し案内する例を示す。例えば、出口料金所通過時刻を基準に割引の適用を判断する場合、１５：３０に出発してそのまま休憩無しで走行すると、図８（１）に示すように、通勤割引（図２（２））時間帯の１７時直前の１６：５９に名古屋ＩＣ（インターチェンジ）を出るので、高速料金は割引無しの通常料金で２６００円である。この休憩を含まない経路を「通常走行」や「休憩なし」と呼ぶこととする。
【００４８】
対して、図８（２）に示すように、同じ時刻（１５：３０）に出発しても途中の下り線東郷ＰＡ（パーキングエリア）あたりで１５分休憩（図中、枠囲み）を取れば、出口料金所（名古屋ＩＣ）で通勤割引時間帯の１７時を過ぎる（１７：１４）ので高速料金は５０％割引の１３００円となる（図中、下線部）。この休憩を含む経路を「休憩あり」と呼ぶこととする。
【００４９】
経路探索の計算においてこれら２つの候補「通常走行」と「休憩あり」のいずれを選択してユーザに対して案内すべきかを判断するためのコスト計算は、既に挙げた数式１にしたがって、図９に示す通りとなり、「休憩なし」と比べて「休憩あり」は、１５分余分に時間はかかるが、金額換算のトータルコストが８４５０円と３００円安いので、「休憩あり」（図９（２））を選択してユーザに案内することになる。
【００５０】
上記のようなコスト計算は、出発時に限らず、経路途中でユーザ操作などにしたがって行ってもよい。ここでは、経路計算アルゴリズムはＡ＊法のため、計算途中の各々の経路選択は
＜数式９＞
（ａ．ある地点まで実際にかかったコスト）＋（ｂ．目的地までの残りコスト）
が最小になるように判断する。ここで
＜数式１０＞
（ａ）ある地点まで実際にかかったコスト
＝出発地からある地点までの距離 × 距離単価
＋出発地からある地点までかかった時間 × 時間単価
＋そこまでの有料道路料金
となるが、ここで、有料道路上にいる場合の有料道路料金は、最も近い次に降りられるＩＣ（ここでは料金所の意）で計算する。また、
＜数式１１＞
（ｂ）目的までの残りコスト
＝目的地までの残り距離 × 距離単価
＋目的地までの残り時間予測値 × 時間単価
で、経路選択の判断は、より小さい値であればよいため、ここでいう残りコストは有料道路料金は含まない。
【００５１】
このような計算を、上記経路の途中１００ｋｍ地点の東名三好ＩＣで行った例は、図１０に示す通りとなる。この場合も、途中に休憩施設があればそこで休憩して出口料金所の通過時刻を進める「休憩あり」（図１０（２））は、「休憩なし」（図１０（１））と比べて、１５分余分に時間はかかるが、１００ｋｍ地点までの料金が安く（図１０（２）：２３５０円⇒１２００円）なって金額換算のトータルコストも安くなるので（図１０（２）：７３５０円⇒７２００円（下線部））、「休憩あり」（図１０（２））を選択してユーザに案内することになる。
【００５２】
なお、フェリー航路を使用する場合、経路がフェリー航路を表すリンクを含むときは、予め用意してある出航時刻などを表すフェリー情報データから待ち時間や所要時間を得て、それに基づいて待ち時間や所要時間のコストを経路のコストに加算する。そのうえで、コストの判定基準が時間・距離ではなく、これまで説明してきたように金額に換算したトータルコストの場合は、フェリーの該当する車種の料金を経路の金額に加算したうえ、他の経路との比較選択の対象とすればよい。
【００５３】
〔３．効果〕
以上のように、本実施形態では、有料道路料金と時間を含む全てのコストを金額に換算して経路探索を行なうことにより、休憩で時間をずらして割引を受ける経路を選択肢に含めて、ユーザにとって所要時間と通行料金のバランスがとれた最適な経路を容易に探索することが可能になる。また、時間帯ごとの割引率と利用者の指定する休憩許容時間に基づいて、経路探索の基準となる時間単価を変動させることにより、与えられた条件、特に個別のユーザや利用時の状況に最も適合した経路を探索し提示することが可能になる。
【００５４】
特に、休憩をとって割引を受ける場合と、休憩も割引もない場合の各選択肢の各コストが略均衡する時間単価を用いることで、一方の選択肢に偏らないバランスの取れた経路選択が実現できる。
【００５５】
〔４．他の実施形態〕
なお、上記各実施形態は例示に過ぎず、本発明は、以下に例示するものやそれ以外の他の実施態様も含むものである。例えば、本発明において、各手段などの要素は、コンピュータの演算制御部に限らず、ワイヤードロジック等に基づく電子回路や、今後登場する非ノイマン型等の情報処理機構で実現してもよい。また、各構成図、データの図、フローチャートの図などは例示に過ぎず、各要素の有無、その順序や具体的内容などは適宜変更可能である。
【００５６】
例えば、本装置を複数のサーバ装置で実現したり、各端末を含めて本発明のシステムとして把握したり、機能によっては外部のプラットフォーム等をＡＰＩ（アプリケーション・プログラム・インタフェース）やネットワークコンピューティングなどで呼び出して実現するなど、構成は柔軟に変更できる。また、上記実施形態は、通信ネットワークのクライアントサーバシステムを前提としたが、本発明はカーナビゲーション装置のようなスタンドアロンでもよい。
【００５７】
さらに、本発明は、パーソナルコンピュータやいわゆるスマートフォンなどに代表される各種コンピュータ類にインストールして用いるコンピュータ・プログラムとして実現することも可能であり、もちろん、有償無償を問わずそのようなプログラムをダウンロード提供するウェブサイトやサーバも本発明の態様に含まれる。
【符号の説明】
【００５８】
Ｔ２ ユーザ端末
１ 経路探索装置
５ 演算制御部
６ 記憶装置
７ 通信手段
２０ 条件受付手段
３０ 直線距離計算手段
４０ 許容値設定手段
５０ 単価計算手段
５５ 割引データ記憶手段
６０ 経路計算手段
６５ ネットワークデータ記憶手段
７０ 経路出力手段
【特許請求の範囲】
【請求項１】
コンピュータが、道路のネットワーク構造を表すネットワークデータと、有料道路の時間帯ごとの割引率を表す割引データと、に基づいて、最適な経路を提示する経路探索装置であって、
出発地、目的地、出発時刻を含む探索条件の入力を受け付ける条件受付手段と、
休憩許容時間の設定を受け付ける許容値設定手段と、
前記出発地と前記目的地の直線距離を計算する直線距離計算手段と、
前記直線距離、前記休憩許容時間及び前記割引データから、休憩許容時間を所要時間に含んで前記割引率の適用がある場合のトータルコストと、前記休憩許容時間を所要時間に含まず前記割引率の適用がない場合のトータルコストと、が略均衡する時間単価を計算する単価計算手段と、
前記休憩許容時間までの休憩を組み込むことで前記割引率の適用を受ける経路を含む各経路についてそのコストを前記時間単価を用いて金額に換算して比較することにより最適経路を探索計算する経路計算手段と、
探索計算で得た前記最適経路を出力する経路出力手段と、
を有することを特徴とする経路探索装置。
【請求項２】
前記単価計算手段は、基準となる所定の高速道路料金に、前記割引率を乗じ、前記休憩許容時間で除することにより、前記時間単価を計算することを特徴とする請求項１記載の経路探索装置。
【請求項３】
コンピュータが、道路のネットワーク構造を表すネットワークデータと、有料道路の時間帯ごとの割引率を表す割引データと、に基づいて、最適な経路を提示する経路探索方法であって、
出発地、目的地、出発時刻を含む探索条件の入力を受け付ける条件受付ステップと、
休憩許容時間の設定を受け付ける許容値設定ステップと、
前記出発地と前記目的地の直線距離を計算する直線距離計算ステップと、
前記直線距離、前記休憩許容時間及び前記割引データから、休憩許容時間を所要時間に含んで前記割引率の適用がある場合のトータルコストと、前記休憩許容時間を所要時間に含まず前記割引率の適用がない場合のトータルコストと、が略均衡する時間単価を計算する単価計算ステップと、
前記休憩許容時間までの休憩を組み込むことで前記割引率の適用を受ける経路を含む各経路についてそのコストを前記時間単価を用いて金額に換算して比較することにより最適経路を探索計算する経路計算ステップと、
探索計算で得た前記最適経路を出力する経路出力ステップと、
を前記コンピュータが実行することを特徴とする経路探索方法。
【請求項４】
コンピュータに、道路のネットワーク構造を表すネットワークデータと、有料道路の時間帯ごとの割引率を表す割引データと、に基づいて、最適な経路を提示させる経路探索プログラムであって、
そのプログラムは前記コンピュータを制御することにより、
出発地、目的地、出発時刻を含む探索条件の入力を受け付ける条件受付ステップと、
休憩許容時間の設定を受け付ける許容値設定ステップと、
前記出発地と前記目的地の直線距離を計算する直線距離計算ステップと、
前記直線距離、前記休憩許容時間及び前記割引データから、休憩許容時間を所要時間に含んで前記割引率の適用がある場合のトータルコストと、前記休憩許容時間を所要時間に含まず前記割引率の適用がない場合のトータルコストと、が略均衡する時間単価を計算する単価計算ステップと、
前記休憩許容時間までの休憩を組み込むことで前記割引率の適用を受ける経路を含む各経路についてそのコストを前記時間単価を用いて金額に換算して比較することにより最適経路を探索計算する経路計算ステップと、
探索計算で得た前記最適経路を出力する経路出力ステップと、
を実行させることを特徴とする経路探索プログラム。
【請求項１】
コンピュータが、道路のネットワーク構造を表すネットワークデータと、有料道路の時間帯ごとの割引率を表す割引データと、に基づいて、最適な経路を提示する経路探索装置であって、
出発地、目的地、出発時刻を含む探索条件の入力を受け付ける条件受付手段と、
休憩許容時間の設定を受け付ける許容値設定手段と、
前記出発地と前記目的地の直線距離を計算する直線距離計算手段と、
前記直線距離、前記休憩許容時間及び前記割引データから、休憩許容時間を所要時間に含んで前記割引率の適用がある場合のトータルコストと、前記休憩許容時間を所要時間に含まず前記割引率の適用がない場合のトータルコストと、が略均衡する時間単価を計算する単価計算手段と、
前記休憩許容時間までの休憩を組み込むことで前記割引率の適用を受ける経路を含む各経路についてそのコストを前記時間単価を用いて金額に換算して比較することにより最適経路を探索計算する経路計算手段と、
探索計算で得た前記最適経路を出力する経路出力手段と、
を有することを特徴とする経路探索装置。
【請求項２】
前記単価計算手段は、基準となる所定の高速道路料金に、前記割引率を乗じ、前記休憩許容時間で除することにより、前記時間単価を計算することを特徴とする請求項１記載の経路探索装置。
【請求項３】
コンピュータが、道路のネットワーク構造を表すネットワークデータと、有料道路の時間帯ごとの割引率を表す割引データと、に基づいて、最適な経路を提示する経路探索方法であって、
出発地、目的地、出発時刻を含む探索条件の入力を受け付ける条件受付ステップと、
休憩許容時間の設定を受け付ける許容値設定ステップと、
前記出発地と前記目的地の直線距離を計算する直線距離計算ステップと、
前記直線距離、前記休憩許容時間及び前記割引データから、休憩許容時間を所要時間に含んで前記割引率の適用がある場合のトータルコストと、前記休憩許容時間を所要時間に含まず前記割引率の適用がない場合のトータルコストと、が略均衡する時間単価を計算する単価計算ステップと、
前記休憩許容時間までの休憩を組み込むことで前記割引率の適用を受ける経路を含む各経路についてそのコストを前記時間単価を用いて金額に換算して比較することにより最適経路を探索計算する経路計算ステップと、
探索計算で得た前記最適経路を出力する経路出力ステップと、
を前記コンピュータが実行することを特徴とする経路探索方法。
【請求項４】
コンピュータに、道路のネットワーク構造を表すネットワークデータと、有料道路の時間帯ごとの割引率を表す割引データと、に基づいて、最適な経路を提示させる経路探索プログラムであって、
そのプログラムは前記コンピュータを制御することにより、
出発地、目的地、出発時刻を含む探索条件の入力を受け付ける条件受付ステップと、
休憩許容時間の設定を受け付ける許容値設定ステップと、
前記出発地と前記目的地の直線距離を計算する直線距離計算ステップと、
前記直線距離、前記休憩許容時間及び前記割引データから、休憩許容時間を所要時間に含んで前記割引率の適用がある場合のトータルコストと、前記休憩許容時間を所要時間に含まず前記割引率の適用がない場合のトータルコストと、が略均衡する時間単価を計算する単価計算ステップと、
前記休憩許容時間までの休憩を組み込むことで前記割引率の適用を受ける経路を含む各経路についてそのコストを前記時間単価を用いて金額に換算して比較することにより最適経路を探索計算する経路計算ステップと、
探索計算で得た前記最適経路を出力する経路出力ステップと、
を実行させることを特徴とする経路探索プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１１−３３５０９（Ｐ２０１１−３３５０９Ａ）
【公開日】平成２３年２月１７日（２０１１．２．１７）
【国際特許分類】
【出願番号】特願２００９−１８１１４１（Ｐ２００９−１８１１４１）
【出願日】平成２１年８月４日（２００９．８．４）
【出願人】（５００２５７３００）ヤフー株式会社 (1,128)
【Ｆターム（参考）】
【公開日】平成２３年２月１７日（２０１１．２．１７）
【国際特許分類】
【出願日】平成２１年８月４日（２００９．８．４）
【出願人】（５００２５７３００）ヤフー株式会社 (1,128)
【Ｆターム（参考）】
[ Back to top ]