JP2013181775A - 移動体合流支援装置、移動体合流支援システム、および移動体合流経路決定方法 - Google Patents

Abstract

【課題】異なる地点から共通の目的地へ向かう複数の移動体が合流することによって総移動コストを少なくできるような経路を、少ない計算量で探索できる移動体合流支援装置を提供する。
【解決手段】複数の移動体同士が合流するための経路である合流経路を決定する移動体合流支援装置であって、前記移動体が出発地から目的地へ移動する際の予定経路を取得し、前記移動体が合流地点に向かって前記予定経路から離脱する地点を離脱地点候補として、二つの移動体についての離脱地点候補の対を順次選択し、前記離脱地点候補の対ごとに、前記移動体同士が合流する地点を合流地点候補として決定する。また、前記各移動体が前記離脱地点候補にて予定経路を離脱し、前記合流地点候補にて合流した場合の各移動体の移動コストの合計値を算出し、前記移動コストの合計値に基づいて、前記移動体同士が合流するための合流経路を決定する。
【選択図】図３

Description

本発明は、移動体合流支援装置、移動体合流支援システム、および移動体合流経路決定方法に関する。

自動車での輸送効率を上げる試みとして、別々に目的地へ向かっている複数の人員や貨物を集約して輸送するという考え方がある。複数の車両による輸送を行う場合、時間と経路がほぼ同一であれば、移動中の車両を合流させ、乗員や貨物を載せ替えることで、より少ない台数で移動することができる。

これと関連する技術に、隊列走行に関する技術がある。隊列走行とは、コンピュータ制御によって複数の車両を短い車間距離で走行させる技術である。同じ経路を走行する複数の車両を集約して隊列走行をさせることにより、空気抵抗の軽減や、スロットル制御の自動化による燃費の改善が期待されている。

目的地へ向かっている複数の乗員や貨物を集約させる技術として、特許文献１には、それぞれ目的地へ向かう複数の車両を、双方の車両の中間地点で合流させる技術が記載されている。合流地点にて乗員や貨物の載せ替えを行い、もしくは隊列走行を開始することで、輸送コストを節約することができる。

また、特許文献２には、相乗り募集者が有する車両に相乗り希望者が同乗する形態において、両者の現在位置および目的地、および車両の燃料残量から、相乗り希望者のピックアップが可能かを判定する技術が記載されている。当該技術によると、燃料消費の増加が一定の範囲に収まる地点にいる相乗り希望者を抽出し、合流を行うことができる。

特開２００４−２９４０６８号公報 特開２０１０−６７０６１号公報

特許文献１に記載の技術は、合流のための走行距離を最小限にしつつ乗員や貨物を合流させる技術である。しかし、当該技術は、地理的条件のみによって合流地点を決定するため、所要時間や待ち時間の増加など、合流による利便性の悪化を考慮していないという問題がある。

たとえば、積載容量がいっぱいになるまで貨物を一地点に集約させれば、より少ない燃料消費で移動できるが、目的地への所要時間が長くなる。このように、同じ目的地に向かって別々に移動している乗員や貨物を合流させることを考えたとき、燃費や積載効率が最良となる経路と、利用者の利便性を考慮した経路が必ずしも一致しないという問題がある。

また、特許文献２に記載の技術は、合流することを前提として、燃料消費量の増加が一定の範囲に収まるような対象者を探すものであるため、それぞれが単独走行するよりも合流したほうが全体のコストが低下するかといった判断を行うことができない。すなわち、
場合によっては合流することによって全体のコストが上昇する可能性があるという問題がある。

これらの問題を解決するためには、経路ごとに合流の効果を判断したうえで、合流の効果が適切に現れる合流経路を決定する必要がある。

一方、複数の車両を合流させる場合、利用できる合流地点を全て抽出し、合流の効果を総当たりで検証すれば、最良の合流地点を決定することができる。しかし、経路が複雑な場合、あるいは移動体が増えた場合、計算量が爆発的に増大するという別の問題がある。上記に記載した従来技術は、いずれもこの問題を解決することができない。

このように、従来技術では、別々に共通の目的地へ向かう複数の移動体があった場合、少ない計算量で、合流の効果が適切に現れる合流経路を探すことができなかった。

本発明は上記の課題を考慮してなされたものであり、異なる地点から共通の目的地へ向かう複数の移動体が合流することによって総移動コストを少なくできるような経路を、少ない計算量で探索できる移動体合流支援装置を提供することを目的とする。

上記目的を達成するために、本発明に係る移動体合流支援装置では、以下の手段により合流の判断および合流経路の決定を行う。

本発明に係る移動体合流支援装置は、異なる地点から出発し、同一の目的地へ移動する複数の移動体同士が合流するための経路である合流経路を決定する移動体合流支援装置であって、前記移動体が出発地から目的地へ移動する際の予定された経路である予定経路を取得する予定経路取得手段と、前記移動体が移動できる経路網を記憶する経路網記憶手段と、前記移動体が合流地点に向かって前記予定経路から離脱する地点を離脱地点候補として、二つの移動体についての離脱地点候補の対を順次選択し、前記離脱地点候補の対ごとに、前記移動体同士が合流する地点の候補である合流地点候補を決定する合流地点候補決定手段と、前記各移動体が前記離脱地点候補にて予定経路を離脱し、前記合流地点候補にて合流した場合の各移動体の出発地から目的地までの移動コストの合計値を算出し、前記移動コストの合計値に基づいて、前記移動体同士が合流するための合流経路を決定する合流経路決定手段と、を有する。

移動コストとは、燃料消費量や移動時間、待ち時間など、移動によって発生する損失のうち少なくともいずれか一つを表す値、もしくは複数の要素を組み合わせて計算することができる値である。

本発明に係る移動体合流支援装置は、各移動体に対して、各移動体の本来の走行経路から離脱する地点の候補と、合流する地点の候補の組を決定する。そして、複数の離脱地点候補および合流地点候補に対し、当該地点を用いて合流を行った場合の全移動体の総移動コストを算出し、コストが改善される地点を正式な合流地点として決定する。最適な合流経路を探索したい場合、全ての地点を用いて総当たりで経路を作成して検証を行う必要があるが、このように構成することにより、計算量を抑え、なおかつ最適に近い合流経路を得ることができるようになる。

また、前記合流地点候補決定手段は、前記各移動体の離脱地点候補同士を結んだ経路上の地点を合流地点候補として決定することを特徴としてもよく、前記合流地点候補決定手段は、前記各移動体のうち一つについて、前記離脱地点候補を前記合流地点候補として決定することを特徴としてもよい。

合流の方法には、各移動体が本来の移動経路を共に離脱し、合流地点に向けて互いに進行する方法と、片方の移動体のみが本来の移動経路を離脱し、もう片方に向けて進行する方法が考えられる。本発明に係る移動体合流支援装置では、どちらか、あるいは両方の方式を用いて合流経路を決定することができる。

また、前記合流地点候補決定手段は、選択された前記離脱地点候補に対して、前記移動体同士が合流すると仮定した地点である合流仮定地点を設定し、前記合流仮定地点で前記各移動体が合流することによって改善される移動コストの改善度を表す評価値を算出し、前記評価値が最大となる地点を、前記離脱地点候補の対に対する合流地点候補として決定することを特徴としてもよい。

移動体の合流経路の決定は、移動体が本来の移動経路から離脱する地点と、移動体同士が合流する地点を定めることによって行うことができる。しかし、合流によって移動コストがどの程度削減できるかは、全ての離脱地点および合流地点の組み合わせについてコスト計算を行わないと求められない。そこで、選択された離脱地点候補の組に対して、仮の合流地点を設定し、評価値が最大、つまり最も移動コストの改善が予想される地点を合流地点候補とする。評価値の算出は、例えば移動距離や所要時間のみを用いるなど、移動コストの算出と比較して単純な要素を用いて行う。そのため、総当たりによって移動コストの計算を行う場合と比較すると、全体の計算量を削減することができるという利点がある。

前記合流地点候補決定手段は、前記各移動体が離脱地点候補から前記予定経路によって目的地まで移動するための距離または時間の合計から、前記各移動体が離脱地点候補から合流仮定地点を経由して目的地まで移動するための距離または時間の合計を減じたものを前記評価値とすることを特徴としてもよく、前記合流地点候補決定手段は、前記各移動体が離脱地点候補から前記予定経路によって目的地まで移動するための距離または時間の合計を、前記各移動体が離脱地点候補から合流仮定地点を経由して目的地まで移動するための距離または時間の合計で除したものを前記評価値とすることを特徴としてもよい。

評価値の定義方法の一つに、合流を行う場合と行わない場合の、離脱地点から目的地までの距離または時間の差もしくは比を用いる方法がある。この方法によると、評価値が大きい合流地点候補ほど、実際の移動コストの減少が期待できる合流地点候補となる。

また、前記合流地点候補決定手段は、前記各移動体の離脱地点候補間の最短経路上に合流仮定地点を設定し、前記合流仮定地点から目的地までの距離または移動時間が小さいほど、前記評価値が大きくなるよう計算を行うことを特徴としてもよい。

この方法によると、離脱地点候補を結ぶ最短経路上の地点のうち、目的地に最も近い地点または最も早く到達できる地点が合流地点候補となるため、合流後の移動コストが最小限になるであろう合流地点候補を求めることができる。

また、前記合流地点候補決定手段は、前記各移動体が合流仮定地点から目的地まで移動するための距離または時間の合計を、前記各移動体が前記離脱地点候補から合流仮定地点まで移動するための距離または時間の合計で除したものを前記評価値とすることを特徴としてもよい。

すなわち、離脱地点から合流地点までの距離または時間と、合流地点から目的地までの距離または時間の比を算出し、評価値とする。合流してから目的地までの距離または時間に対して、予定経路を離脱してから合流するまでの距離または時間の割合が小さいほど、
実際の移動コストの減少が期待できる合流地点候補となる。

また、前記合流経路決定手段は、前記評価値が大きい順に、前記離脱地点候補の対および合流地点候補を用いて前記合計値を算出し、所定の算出回数をもって処理を終了することを特徴としてもよい。

評価値順、すなわち移動コストの削減が期待できる順に移動コストの合計を算出する処理を行うことで、途中で算出処理を中断した場合であっても、最適に近い合流地点を得られるという効果がある。

また、前記合流経路決定手段は、各移動体が定められた予定経路に従って目的地まで移動する場合の距離または時間と比較して、合流地点候補で合流した場合の各移動体の移動距離または時間が一定の割合以上増加する場合、当該合流地点候補を除外して前記合計値を算出することを特徴としてもよい。

個々の移動体について、本来の経路よりも一定の割合以上距離または時間が増加する場合は、他の要素が改善する場合であっても、該当する合流地点を用いて合流を行わないよう判断することができる。この「一定の割合」を大きくすれば、個々の移動体の利便性を犠牲にしてでも乗員や貨物の集約を優先することができ、小さくすれば、コストを優先することができる。

また、前記合流地点候補決定手段は、各移動体の組に対して合流地点候補を決定し、前記合流経路決定手段は、前記各移動体が合流した場合の経路である合流経路を決定し、決定された合流経路が変化しなくなるまで、決定した前記合流経路を新しい予定経路として、前記合流地点候補の決定および前記各移動体の合流経路の決定を繰り返して実行することを特徴としてもよい。

三台以上の移動体がある場合は、合流地点候補決定手段が行う処理および合流経路決定手段が行う処理を繰り返して実行する。これにより、最も移動コストが削減される合流経路の算出処理を二台ずつ順次行えるため、全体最適に近い合流経路を求めることができる。移動体が三台以上あり、総当たりによる経路の探索を行う場合、計算量が指数関数的に多くなるが、この方法によると比較的短時間で探索を行うことができる。

また、前記経路網記憶手段は、移動体が移動することができる経路の情報を重みつきグラフにより保持することを特徴としてもよい。

重みとは、移動体が当該道路を走行する際に必要となる移動コストのうち、所要時間や距離などによって表すことができる。このように構成することにより、経路を移動する際のコストの計算を正確に行うことができる。また、メンテナンスや情報の更新が容易になるという利点がある。

また、本発明に係る移動体合流支援システムは、前記移動体合流支援装置と、予定された経路に従って出発地から目的地へ移動する複数の移動体と、からなる移動体合流支援システムであって、前記移動体が、前記移動体合流支援装置へ現在位置情報および目的地に係る情報を送信し、前記移動体合流支援装置が、決定した合流経路を前記移動体に送信することを特徴とする。

このように構成することにより、移動体合流支援装置は全ての移動体の現在位置と目的地を把握することができるため、合流を行う移動体を決定したうえで、当該移動体に決定した合流経路を送信することができる。

本発明によれば、異なる地点から共通の目的地へ向かう複数の移動体が合流することによって総移動コストを少なくできるような経路を、少ない計算量で探索できる移動体合流支援装置を提供することができる。

複数台の車両の合流について説明する図である。 車両が合流する二種類の方法について説明する図である。 第一の実施形態に係る移動体合流支援装置の機能構成図である。 第一の実施形態に係る離脱および合流地点候補の決定方法を説明する図である。 第一の実施形態に係る双合流方式の処理フローチャートである。 第一の実施形態に係る双合流方式による合流地点情報の例である。 第一の実施形態に係る片合流方式の処理フローチャートである。 第一の実施形態に係る片合流方式による合流地点情報の例である。 第一の実施形態に係る合流地点候補から走行経路を決定する処理のフローチャートである。 適用例に係る道路網情報である。 適用例に係る合流地点情報の例である。

（第一の実施形態）
<概要>
第一の実施形態に係る移動体合流支援装置（以下、合流支援装置）は、車両から目的地へ向かうための経路情報を受信し、合流する車両および合流を行うための経路（以下、合流経路）を決定したのちに、車両に対して合流経路情報を送信する機能を持つ。

まず、車両の合流について簡単に説明する。図１は、複数の車両が目的地に向かって走行する様子を表した図である。車両１は座標（０，０）から、車両２は座標（０，２）から、車両３は座標（３，０）からそれぞれ目的地である座標（４，４）へ走行する。このとき、各車両が単独で目的地を目指すと、車両１は８マス、車両２は６マス、車両３は５マス分の走行距離が必要である。これに対し、車両１の走行ルートを破線のように設定し、車両２と車両３の走行ルートを点線のように設定すると、座標（１，２）で車両２が、座標（３，２）で車両３が合流することができる。合流地点で荷物を集積させ、車両２と３の運行を終了させると、車両の延べ走行距離は車両１が８マス、車両２が１マス、車両３が２マスの合計１１マスとなり、単独で走行する場合（８＋６＋５＝１９マス）と比較して８マス分の総移動コストが節約できる。本実施形態に係る合流支援装置は、このように車両同士が合流すべきであるか否かと、合流する場合の各車両の経路を決定するためのものである。

車両の合流には、二種類の考え方がある。図２を参照しながら、各方式について説明する。図２は、２台の車両が個別に目的地へ向かう場合の最短経路を実線で示した図である。なお、実施形態の説明において用いる最短経路という言葉は、必ずしも距離が最も短い経路を意味するのではなく、距離や時間などを移動コストとして換算し、当該移動コストが一番少ない経路を意味する。図２（ａ）は、車両１と車両２が、互いのルートを変更して合流する方式を表している。この方法をとる場合、２台がそれぞれ本来のルートから外れる地点（以下、離脱地点と称する）と、２台が合流する地点（以下、合流地点と称する）とを決定する必要がある。実施形態の説明において、図２（ａ）の方式を双合流方式と呼ぶ。

図２（ｂ）は、片方の車両が本来のルートを離脱し、もう片方の車両のルートへ向かう方式を表している。この方式では、車両２はルートを変更する必要が無い。この方式をとる場合、車両１の離脱地点と２台の合流地点を決定する必要がある。実施形態の説明において、図２（ｂ）の方式を片合流方式と呼ぶ。

以上に示した二つの方式は、どちらか片方が用いられてもよいし、両方を用いて処理を行ったのち、総コストがより改善するものをどちらか選択してもよい。

<システム構成>
図３は、本実施形態に係る合流支援装置の構成を表した図である。それぞれの構成要素を説明する。道路網情報１０は、車両が走行できる道路網が記憶されたデータである。道路網情報はノードとリンクで定義され、ノードが交差点やインターチェンジを、リンクが道路を表す。また、リンクには車両がノード間を移動する際の移動コストのうち、距離や所要時間など、リンクと直接関連付けられるものが定義されている。

合流地点候補決定部１１は、各車両が出発地から目的地まで走行するための本来の経路である予定経路情報を取得し、各車両が合流して目的地に至るための経路の候補を決定する手段である。具体的には、取得した車両の予定経路情報、および保持している道路網情報１０から、各車両が合流のために本来の経路を離脱する地点である離脱地点の候補と、各車両が合流する地点である合流地点の候補を抽出する。詳細な動作については後述する。

コスト算出部１２は、合流地点候補決定部１１が抽出した離脱地点候補および合流地点候補を採用した場合の全体の総移動コストを算出する手段である。各車両が合流した場合の、出発地から目的地までの移動コストを車両ごとに算出し、合流によってどの程度総移動コストが低減するかを計算する。詳細な動作については後述する。

走行経路決定部１３は、コスト算出部１２が算出した総移動コスト値をもとに、実際の離脱地点および合流地点を決定する、すなわち各移動体が合流を行った場合の経路情報である合流経路情報を決定する手段である。走行経路決定部１３が合流経路情報を出力し、出力された情報は各車両へ無線などの通信手段を介して伝達される。

合流地点情報１４は、合流地点候補決定部１１によって作成される、各車両の離脱地点候補、および合流地点候補の組が記録されるリストである。記録されたデータはコスト算出部１２による総移動コスト計算に使用される。

<双合流方式を用いた離脱地点候補・合流地点候補の抽出>
具体的な処理方法を、双合流方式から順に説明する。図４は、各車両の経路を説明した図であり、図５は、本発明に係る合流支援装置の、双合流方式における処理フローチャートを示した図である。

まず、合流地点候補決定部１１は、目的地が同一である複数の車両を抽出し、各車両の予定経路情報を取得する（Ｓ１１）。図４の例では、ノード１にいる車両１と、ノード５にいる車両２について、目的地であるノード１０までの予定経路（実線）が取得される。車両１は、ノード２，３，１１，１０という経路で目的地に至り、車両２は、ノード７，８，１０という経路で目的地に至る。

次に、合流地点候補決定部１１は、各車両の離脱地点候補・合流地点候補を決定する。具体的には、ある車両が有している予定経路上の各ノード（離脱地点候補１と称する）と
、他の車両が有している予定経路上の各ノード（離脱地点候補２と称する）との組み合わせを順次選択し（Ｓ１２）、離脱地点候補１と離脱地点候補２を連絡する最短経路を求める（Ｓ１３）。なお、最短経路とは、距離や時間などの要素から移動コストを算出し、当該移動コストが最も少なくなる経路であることを前述したが、ステップＳ１３の処理では、他の移動コストの算出で使用する要素と異なる要素を用いてもよい。

次に、当該最短経路上に存在するノードのうち、スコアが最も大きくなる地点を合流地点候補として選択し、離脱地点候補とともに合流地点情報１４へ追加する（Ｓ１４）。スコアとは、本発明における評価値であり、選択中の離脱地点候補に対して、選ぼうとしている合流地点候補にどの程度の妥当性があるか、すなわち予想される移動コスト削減量を数値化したものである。選択した合流地点を使用して車両が合流した場合、総移動コストがどの程度減少するかは、経路を決定した後でなければわからないため、選択中の離脱地点候補に対して、どこを合流地点候補とするのが適当であるか判断するための値が本実施形態におけるスコアである。

スコアの計算方法について、二種類を例示する。
第一の計算方法は、合流地点から目的地までの距離または時間の合計を、離脱地点から合流地点までの距離または時間の合計で除した値をスコアとする方法である。すなわち、合流後の距離または時間に対し、合流前の距離または時間が最少となるような地点を選択する。第一の計算方法を用いた場合、スコアが大きい合流地点候補ほど、移動コストの削減が期待できる。

第二の計算方法は、合流地点から目的地までの距離または時間の逆数をスコアとする方法である。すなわち、ある離脱地点がある場合、合流地点が目的地に近い、もしくは早く到達できるほどスコアが大きくなる。第二の計算方法を用いた場合、スコアが大きい合流地点候補ほど合流後の移動コストがかからないことが期待できる。

以上に例示したスコアの計算方法は、いずれか片方が用いられてもよいし、両方が用いられてもよい。離脱地点候補の組が他にある場合は、全ての組み合わせについて同様の処理を繰り返す。

図４に示した道路網に対して、第一の計算方法を用いて処理を行った場合、合流地点情報１４の内容は図６のようになる。なお、説明の便宜上、図４の道路網の各リンクを移動する際の移動コストは全て１とし、合流後は、合流した側が運行を終了すると仮定する。また、リンクが分岐していないノードは処理対象外とし、道路網情報に定義された移動コスト以外は使用しないものとする。図５の処理を完了させると、車両１と車両２に対して、ノード４、ノード６、ノード９の３つの合流地点候補が抽出される。スコアは、ノード４で合流する場合、合流地点から目的地までの移動コストが３、離脱地点から合流地点までの合計移動コストが２であるため、３／２＝１．５となる。同様に、ノード６で合流する場合は２／２＝１、ノード９で合流する場合は、ノード２で離脱する場合が１／４＝０．２５、ノード３で離脱する場合が１／３＝０．３３…となる。スコアが大きいほど、合流のための移動コストが少ないことを意味するため、総移動コストの改善が期待できる。実際に総移動コストが改善しているかは、全ての離脱地点候補および合流地点候補が抽出されてから検証される。

<片合流方式を用いた離脱地点候補・合流地点候補の抽出>
次に、片合流方式を用いて離脱地点候補および合流地点候補を抽出する方法を説明する。各車両の経路は図４と同様である。図７は、片合流方式の処理フローチャートを示した図である。

処理を開始すると、合流地点候補決定部１１は、目的地が同一の車両を抽出し、各車両の予定経路情報を取得する（Ｓ２１）。ステップＳ２１の処理は、双合流方式（ステップＳ１１）と同様である。

次に、合流地点候補決定部１１は、各車両について離脱地点候補を選択する。具体的には、対象車両の予定経路上の各ノードを順次選択し、離脱地点候補とする（Ｓ２２）。そして、他の車両が有している予定経路上の各ノードを順次選択し、合流地点候補とする（Ｓ２３）。そして、離脱地点候補と合流地点候補とを連絡する、距離または時間が最短となる経路を求める（Ｓ２４）。

次に、選択された合流地点候補にて合流した場合のスコアを算出する（Ｓ２５）。スコアの計算方法は、ステップＳ１４にて述べた方法を使用することができる。合流地点候補のノードが他にある場合は、他のノードを合流地点候補とし、同様の処理を繰り返す。そして、一つの離脱地点候補に対し、スコアが最も良い合流地点候補を一つ決定し、離脱地点候補とともに合流地点情報１４へ追加する（Ｓ２６）。離脱地点候補が他にある場合は、他のノードを離脱地点候補として選択し、同様の処理を繰り返す。

図４の道路網に対してこの処理を行った場合、合流地点情報１４の内容は図８のようになる。図８の処理結果によると、車両１と車両２は、車両１が離脱する場合は、ノード７、ノード８の２つの合流地点候補が抽出される。ノード７で合流する場合、合流地点から目的地までの移動コストが２、離脱地点から合流地点までの移動コストが２であるため、スコアは２／２＝１となる。同様に、ノード８で合流する場合は、ノード２で離脱した場合が１／４＝０．２５、ノード３で離脱した場合が１／３＝０．３３…となる。車両２が離脱する場合、ノード２、ノード３の２つの合流地点候補が抽出される。ノード２で合流する場合、スコアは３／２＝１．５となる。同様に、ノード３で合流する場合は２／２＝１となる。

なお、合流地点情報１４は、双合流方式と片合流方式のどちらか片方を実行して作成してもよいし、両方を実行して作成してもよい。両方を実行することで、より精度の高い判定が可能になる。

ここまでの処理を終えると、合流地点情報１４には、２台の車両について離脱地点候補と合流地点候補のペアが、スコアとともに記録される。同一の目的地へ向かう車両が３台以上ある場合、２台ずつの組み合わせが作成される。

<合流地点の決定方法>
次に、作成した合流地点情報１４を用いて、最終的に合流地点および各車両の走行経路を決定する方法について説明する。図９は、合流地点候補決定部１１が合流地点情報１４を作成した後、コスト算出部１２および走行経路決定部１３が行う処理のフローチャートである。

コスト算出部１２は、記録された合流地点情報のレコードを、スコアが良い順に順次選択し（Ｓ３０）、以下の処理を行う。
まず、各車両について、出発地から目的地までの予定経路の走査を開始する（Ｓ３１）。経由地点のノードが、合流地点情報１４に記録された離脱地点候補に達した場合（Ｓ３２）、離脱地点候補から合流地点候補までの、距離または時間が最短となる経路を取得する（Ｓ３３）。
次に、合流地点から目的地までの走行経路を決定する。このとき、他の車両を処理した際に決定された走行経路が既にある場合は当該経路を採用（すなわち他車と合流することを意味する）し、無い場合は目的地までの距離または時間が最短となる経路を走行経路と
して決定する（Ｓ３４）。

次に、個々の移動体について、決定した走行経路と予定経路を比較し、移動距離または時間の増加が許容範囲以内であるか確認を行う（Ｓ３５）。許容範囲とは、たとえば「予定経路に対して距離または時間の増加が２０％以内」などとすることができる。つまり、合流することによって走行距離または所要時間が一定以上増加しないように、事前に設定された許容範囲を参照して確認を行う。許容範囲を逸脱する場合、処理対象の合流地点候補を無視する。
ステップＳ３２にて、離脱地点候補を最後まで発見できなかった場合（Ｓ４１）、予定経路を走行経路として決定する（Ｓ４２）。

次に、このようにして決定した走行経路に対し、現在位置から目的地までの、複数車両の移動コストの合計である総移動コストを計算する。この結果が、既に計算された総移動コスト（初期値は予定経路の移動コストの合計）を下回っていた場合（Ｓ３６）、当該経路を一時的に記憶する（Ｓ３７）。以上の、ステップＳ３１からＳ３７までの処理が車両ごとに実行される。また、他の合流地点情報がある場合、Ｓ３０からの処理が再度行われ、他の合流地点情報を用いたほうが総移動コストが低くなる場合、そちらの経路がステップＳ３７によって採用される。最終的に最も総移動コストが低い経路が、走行経路決定部１３によって合流経路として決定される。

以上に説明した処理を行うことで、運行中のそれぞれの車両について、他車両と合流したほうが総移動コストが低くなるか、単独で目的地まで運行した方が総移動コストが低くなるかを決定することができる。

なお、図９に示した処理は、全車両の経路が収束するまで複数回行われてもよい。他の車両同士が合流することで、自車両の最適な経路が変更となる可能性があるが、処理を複数回行うことにより、各車両の経路をより最適な経路に収束させることができる。複数回の処理を行う場合は、各車両の走行経路が変化しなくなるまで、決定した合流経路を予定経路に置き換えて処理を繰り返してもよいし、任意の回数を実行した後に処理を終了してもよい。

任意の車両について任意の地点で合流を行う場合、対象の車両が多いほど経路の組み合わせは指数関数的に増える。本実施形態では、二台ずつの合流を複数回繰り返して行い、それぞれの合流経路はスコアによって少ない計算量で算出されたものであるため、計算量を削減することができる。また、合流地点情報１４はスコアが良い順に検証するため、全体最適に近い経路を短時間で得ることが期待できる。

また、移動体の合流によって移動コストを削減しようとした場合、改善するコストと悪化するコストの両方が発生するため、既存の技術では、両者のバランスが良い合流地点を探索することが難しかった。これに対し本実施形態では、距離または時間の増加が一定範囲以上である場合、合流を行わないという判断ができるため、コストの削減と利用者の利便性とを両立させることができる。

（第二の実施形態）
第二の実施形態は、合流地点候補を決定する際のスコア算出において、合流することによって変化する距離または時間を用いる形態である。システム構成、および処理フローチャートは第一の実施形態と同様である。

第二の実施形態では、スコアの計算に、第一の実施形態で用いた第一および第二の計算方法の他、異なる二種類の計算方法を用いる。以下、それぞれの計算方法を説明する。
第三の計算方法は、離脱地点から目的地までの本来の経路による距離または時間の合計を、離脱地点と合流地点を経由して目的地へ向かった場合の距離または時間の合計で除した値をスコアとする方法である。すなわち、離脱地点から目的地間の、合流しない場合の距離または時間を、合流した場合の距離または時間で割ったものがスコアとなる。第三の計算方法を用いた場合、スコアが大きい合流地点候補ほど実際の距離または時間の削減率が高いため、総移動コストの削減が期待できる合流地点候補となる。

第四の計算方法は、離脱地点から目的地までの本来の経路による距離または時間の合計から、離脱地点と合流地点を経由して目的地へ向かった場合の距離または時間の合計を減じた値をスコアとする方法である。すなわち、離脱地点から目的地間の、合流しない場合の距離または時間から、合流した場合の距離または時間を引いたものがスコアとなる。第四の計算方法を用いた場合も、スコアが大きい合流地点候補ほど実際の距離または時間の削減量が大きいため、総移動コストの削減が期待できる合流地点候補となる。

第二の実施形態によると、選択された離脱地点候補に対応する合流地点候補を決定する際、実際に減少する距離または時間を用いるため、算出されたスコアと、合流による総移動コストの削減量との間に強い相関が期待できる。

（適用例）
第一の実施形態に係る合流支援装置を、実際の道路網を模したデータに適用した例を示す。図１０は、説明にて使用する道路網情報である。矢印は、各ノードから目的地への予定経路を示しており、数値がノード間の移動コストを示している。ハッチングした楕円は、車両の初期位置を示している。

予定経路を走行した場合、ノード９にいる車両１は、ノード１１，３，１を経由して目的地へ至る。また、ノード１４にいる車両２は、ノード７，６，４，２，１を経由して目的地へ至る。合流地点候補決定部１１が、片合流方式、および第一の計算方法を使用して合流地点情報１４を作成する場合を考える。図１１が、作成される合流地点情報１４の内容となる。車両１は、ノード９またはノード１１で予定経路を離脱し、ノード１４で車両２と合流することが考えられ、車両２は、ノード１４またはノード７で予定経路を離脱し、ノード１１で車両１と合流することが考えられる。それぞれのスコアは図１１に示した通りであり、Ｎｏ．１、Ｎｏ．２、Ｎｏ．４、Ｎｏ．３の順にスコアが良いことを示している。

次に、図１１の情報を用いて、コスト算出部１２が、スコア順に総移動コストの計算を行う。Ｎｏ．１を採用した場合、合流するまでの車両１の移動コストは８となり、目的地まで運行する車両２の移動コストは１４となるため、合計２２となる（合流後は、合流した側が運行を終了すると仮定し、予定経路に対するコスト増加の許容範囲は考慮しない）。同じく、Ｎｏ．２を採用した場合、車両１の移動コストは１２、車両２の移動コストは１４となるため、合計は２６となる。Ｎｏ．４を採用した場合、車両１の移動コストは１８、車両２の移動コストは１０となるため、合計は２８となる。Ｎｏ．３を採用した場合、車両１の移動コストは１８、車両２の移動コストは９となるため、合計は２７となる。すなわち、Ｎｏ．１を採用した場合が一番移動コストが低くなるため、走行経路決定部１３は、この経路を正式なルートとして決定し、車両１および車両２に対して合流する旨、および走行経路と合流地点の通知を行う。

以上、説明したように構成することにより、異なる地点から共通の目的地へ移動する複数の移動体が、合流によって同一経路を移動できるような経路を少ない計算量で探索することができる。これによって、乗合いや隊列走行の支援が容易になり、燃費や積載効率の向上に役立てることができる。また、離脱地点候補および合流地点候補に対して総当たり
による計算を行う必要がなく、比較的好適な合流経路を早期に得ることができる。

（変形例）
なお、以上の説明は本発明を説明する上での例示にすぎず、各実施形態は、本発明の趣旨を逸脱しない範囲で変形することができる。例えば、実施形態の説明では、合流後はどちらかの車両を乗り捨てることとし、合流した側の移動コストの計算を打ち切ったが、隊列走行によって目的地まで運行してもよい。この場合、隊列走行によって軽減される移動コストを考慮して総移動コストの計算を行うことができる。合流後の移動コストの軽減効果は、評価関数を用いて計算してもよい。

また、移動コストを計算する際は車両の待ち時間を考慮に加えてもよい。この場合、出発時刻と合流地点までの移動コストから待ち時間を算出し、移動コストに待ち時間を加えて計算をすることができる。このように、待ち時間や荷物の積み替え時間など、移動以外に係るコストを移動コストに加えて計算してもよい。

また、実施形態の説明においては、スコアが良い順に合流地点情報を選択して総移動コストの計算を行う例を挙げたが、スコアの順番を用いず、離脱地点候補および合流地点候補の全ての組み合わせに対して総移動コストの計算を行ってもよい。この場合であっても、総当たりで総移動コストの検証を行う場合と比較すると、全体の計算量を削減するという発明の目的を達成することができる。

また、実施形態の説明においては、道路網を重みつきグラフとして記憶したが、ノード同士の関係と、移動にともなうコストを定義することができれば、どのような形式であってもよい。

また、実施形態の説明においては、車両から予定経路についての情報を取得する形態を挙げたが、車両からは出発地および目的地についての情報のみを取得し、合流支援装置が、道路網情報１０を参照して予定経路情報を生成してもよい。同様に、車両に伝達される情報は、合流経路についての情報でなくても、離脱地点および合流地点の情報のみであってもよい。

１０ 道路網情報
１１ 合流地点候補決定部
１２ コスト算出部
１３ 走行経路決定部
１４ 合流地点情報

Claims (14)

1. 異なる地点から出発し、同一の目的地へ移動する複数の移動体同士が合流するための経路である合流経路を決定する移動体合流支援装置であって、
   前記移動体が出発地から目的地へ移動する際の予定された経路である予定経路を取得する予定経路取得手段と、
   前記移動体が移動できる経路網を記憶する経路網記憶手段と、
   前記移動体が合流地点に向かって前記予定経路から離脱する地点を離脱地点候補として、二つの移動体についての離脱地点候補の対を順次選択し、前記離脱地点候補の対ごとに、前記移動体同士が合流する地点の候補である合流地点候補を決定する合流地点候補決定手段と、
   前記各移動体が前記離脱地点候補にて予定経路を離脱し、前記合流地点候補にて合流した場合の各移動体の出発地から目的地までの移動コストの合計値を算出し、前記移動コストの合計値に基づいて、前記移動体同士が合流するための合流経路を決定する合流経路決定手段と、
   を有する移動体合流支援装置。
2. 前記合流地点候補決定手段は、前記各移動体の離脱地点候補同士を結んだ経路上の地点を合流地点候補として決定する
   ことを特徴とする、請求項１に記載の移動体合流支援装置。
3. 前記合流地点候補決定手段は、前記各移動体のうち一つについて、前記離脱地点候補を前記合流地点候補として決定する
   ことを特徴とする、請求項１に記載の移動体合流支援装置。
4. 前記合流地点候補決定手段は、選択された前記離脱地点候補に対して、前記移動体同士が合流すると仮定した地点である合流仮定地点を設定し、前記合流仮定地点で前記各移動体が合流することによって改善される移動コストの改善度を表す評価値を算出し、前記評価値が最大となる地点を、前記離脱地点候補の対に対する合流地点候補として決定する
   ことを特徴とする、請求項２または３に記載の移動体合流支援装置。
5. 前記合流地点候補決定手段は、前記各移動体が離脱地点候補から前記予定経路によって目的地まで移動するための距離または時間の合計から、前記各移動体が離脱地点候補から合流仮定地点を経由して目的地まで移動するための距離または時間の合計を減じたものを前記評価値とする
   ことを特徴とする、請求項４に記載の移動体合流支援装置。
6. 前記合流地点候補決定手段は、前記各移動体が離脱地点候補から前記予定経路によって目的地まで移動するための距離または時間の合計を、前記各移動体が離脱地点候補から合流仮定地点を経由して目的地まで移動するための距離または時間の合計で除したものを前記評価値とする
   ことを特徴とする、請求項４に記載の移動体合流支援装置。
7. 前記合流地点候補決定手段は、前記各移動体の離脱地点候補間の最短経路上に合流仮定地点を設定し、前記合流仮定地点から目的地までの距離または移動時間が小さいほど、前記評価値が大きくなるよう計算を行う
   ことを特徴とする、請求項４に記載の移動体合流支援装置。
8. 前記合流地点候補決定手段は、前記各移動体が合流仮定地点から目的地まで移動するための距離または時間の合計を、前記各移動体が前記離脱地点候補から合流仮定地点まで移
   動するための距離または時間の合計で除したものを前記評価値とする
   ことを特徴とする、請求項４に記載の移動体合流支援装置。
9. 前記合流経路決定手段は、前記評価値が大きい順に、前記離脱地点候補の対および合流地点候補を用いて前記合計値を算出し、所定の算出回数をもって処理を終了する
   ことを特徴とする、請求項４から８のいずれかに記載の移動体合流支援装置。
10. 前記合流経路決定手段は、各移動体が定められた予定経路に従って目的地まで移動する場合の距離または時間と比較して、合流地点候補で合流した場合の各移動体の移動距離または時間が一定の割合以上増加する場合、当該合流地点候補を除外して前記合計値を算出する
    ことを特徴とする、請求項４から９のいずれかに記載の移動体合流支援装置。
11. 前記合流地点候補決定手段は、各移動体の組に対して合流地点候補を決定し、
    前記合流経路決定手段は、前記各移動体が合流した場合の経路である合流経路を決定し、
    決定された合流経路が変化しなくなるまで、決定した前記合流経路を新しい予定経路として、前記合流地点候補の決定および前記各移動体の合流経路の決定を繰り返して実行する
    ことを特徴とする、請求項１０に記載の移動体合流支援装置。
12. 前記経路網記憶手段は、移動体が移動することができる経路の情報を重みつきグラフにより保持する
    ことを特徴とする、請求項１から１１のいずれかに記載の移動体合流支援装置。
13. 請求項１から１２のいずれかに記載の移動体合流支援装置と、予定された経路に従って出発地から目的地へ移動する複数の移動体と、からなる移動体合流支援システムであって、
    前記移動体が、前記移動体合流支援装置へ現在位置情報および目的地に係る情報を送信し、
    前記移動体合流支援装置が、決定した合流経路を前記移動体に送信する
    ことを特徴とする、移動体合流支援システム。
14. 異なる地点から出発し、同一の目的地へ移動する複数の移動体同士が合流するための経路である合流経路を決定する移動体合流支援装置が行う移動体合流経路決定方法であって、
    前記移動体が出発地から目的地へ移動する際の予定された経路である予定経路を取得するステップと、
    前記移動体が合流地点に向かって前記予定経路から離脱する地点を離脱地点候補として順次選択するステップと、
    前記離脱地点候補ごとに、前記移動体同士が合流する地点の候補である合流地点候補を決定するステップと、
    前記離脱地点候補にて予定経路を離脱し、前記合流地点候補にて合流した場合の各移動体の出発地から目的地までの移動コストの合計値を算出し、前記移動コストの合計値に基づいて、複数の離脱地点候補および合流地点候補の中から、前記移動体同士が合流するための合流経路を決定するステップと、
    を含む
    ことを特徴とする、移動体合流経路決定方法。

Images