(57)【要約】【課題】複数のユーザの移動計画に応じた適切な移動経路及び移動手段を提示することができるようにする。【解決手段】最適化部５６は、ユーザの位置に関する情報とユーザの目的地に関する情報との組み合わせ、複数の車両の各々の位置に関する情報、及び道路ネットワークデータに基づいて、リンク需要ｙｌｔとリンク台数ｖｌｔと１台あたりの乗車人数Ｃとを用いて表されたコスト関数ｃｌｔとリンク需要ｙｌｔとから求められる目的関数を、ラウンドトリップａｉｌｔを用いて定められた制約条件を満たした上で最適化するように、リンク需要ｙｌｔとリンク台数ｖｌｔとラウンドトリップａｉｌｔとを推定する。そして、経路算出部５８は、推定されたリンク需要ｙｌｔとリンク台数ｖｌｔとラウンドトリップａｉｌｔとに基づいて、複数のユーザの各々に対する移動経路及び移動手段を算出する。【選択図】図５
2017142177.tif 000002
【特許請求の範囲】
【請求項１】
複数のユーザの各々についての、前記ユーザの位置に関する情報と前記ユーザの目的地に関する情報との組み合わせ、複数の車両の各々の位置に関する情報、及び道路ネットワークデータに基づいて、リンクと時刻との組み合わせの各々についての、時刻ｔにリンクｌを通過するユーザの数を表すリンク需要ｙｌｔと、時刻ｔにリンクｌを通過する車両の数を表すリンク台数ｖｌｔと、１台あたりの乗車人数Ｃとを用いて表されたコスト関数ｃｌｔと前記リンク需要ｙｌｔとから求められる目的関数を、ユーザｉが時刻ｔにリンクｌを通過することを表すラウンドトリップａｉｌｔを用いて定められた制約条件を満たした上で最適化するように、前記リンク需要ｙｌｔと、前記リンク台数ｖｌｔと、前記ラウンドトリップａｉｌｔとを推定する推定手段と、
前記推定手段によって推定された前記リンク需要ｙｌｔと、前記リンク台数ｖｌｔと、前記ラウンドトリップａｉｌｔとに基づいて、前記複数のユーザの各々に対する移動経路及び移動手段を算出する算出手段と、
を含む情報処理装置。
【請求項２】
前記推定手段は、以下の式に示す前記コスト関数ｃｌｔと前記リンク需要ｙｌｔとから求められる目的関数を最適化するように、前記リンク需要ｙｌｔと、前記リンク台数ｖｌｔと、前記ラウンドトリップａｉｌｔとを推定する
請求項１に記載の情報処理装置。
【数１】
2017142177.tif 000019
ただし、ｄｌは、リンクｌの距離である。
【請求項３】
前記制約条件は、前記ラウンドトリップａｉｌｔと前記リンク需要ｙｌｔとを用いて表された需要制約を含む請求項１又は請求項２に記載の情報処理装置。
【請求項４】
前記制約条件は、更に、
前記ユーザｉの各々についての目的地の数Ｄｉを用いて表された目的地制約、
前記リンク台数ｖｌｔと前記リンク需要ｙｌｔとを用いて表された運転手制約、
時刻ｔにおいて場所を表すノードｋに存在する車両の台数ｘｋｔを用いて表された台数制約、
時刻ｔにおいて場所を表すノードｋに存在するユーザの数ｚｋｔを用いて表された人数制約、
前記リンク台数ｖｌｔと前記車両の台数ｘｋｔとを用いて表された車両フロー制約、
前記リンク需要ｙｌｔと前記ユーザの数ｚｋｔとを用いて表された人フロー制約、
及び前記車両の台数ｘｋｔとノードｋに存在する駐車場容量ｌｋとを用いて表された駐車場容量制約の少なくとも１つの制約を含む請求項３に記載の情報処理装置。
【請求項５】
請求項１〜請求項４の何れか１項に記載の情報処理装置によって算出された前記ユーザの各々に対する移動経路及び移動手段に関する情報を取得する通信手段と、
前記通信手段によって取得された前記移動経路及び前記移動手段に関する情報を提示する提示手段と、
を含む情報端末。
【請求項６】
請求項１〜請求項４の何れか１項に記載の情報処理装置と、
請求項５に記載の情報端末とを含む情報提示システム。
【請求項７】
コンピュータを、
複数のユーザの各々についての、前記ユーザの位置に関する情報と前記ユーザの目的地に関する情報との組み合わせ、複数の車両の各々の位置に関する情報、及び道路ネットワークデータに基づいて、リンクと時刻との組み合わせの各々についての、時刻ｔにリンクｌを通過するユーザの数を表すリンク需要ｙｌｔと、時刻ｔにリンクｌを通過する車両の数を表すリンク台数ｖｌｔと、１台あたりの乗車人数Ｃとを用いて表されたコスト関数ｃｌｔと前記リンク需要ｙｌｔとから求められる目的関数を、ユーザｉが時刻ｔにリンクｌを通過することを表すラウンドトリップａｉｌｔを用いて定められた制約条件を満たした上で最適化するように、前記リンク需要ｙｌｔと、前記リンク台数ｖｌｔと、前記ラウンドトリップａｉｌｔとを推定する推定手段、及び
前記推定手段によって推定された前記リンク需要ｙｌｔと、前記リンク台数ｖｌｔと、前記ラウンドトリップａｉｌｔとに基づいて、前記複数のユーザの各々に対する移動経路及び移動手段を算出する算出手段
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報端末、情報提示システム、及びプログラムに関する。
【背景技術】
【０００２】
従来より、車両のライドシェアリングを利用するユーザのＯＤ（出発地（Ｏｒｉｇｉｎ）と目的地（Ｄｅｓｔｉｎａｔｉｏｎ））が与えられた場合に、ユーザ全員をピックアップすることが可能な車両の最適経路を計算する技術が知られている（例えば、非特許文献１〜２を参照。）。
【０００３】
また、人であるユーザの１移動と車両の移動とのマッチングに関する技術が知られている（例えば、特許文献１〜６を参照。）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００３−２８１２３８号公報
【特許文献２】特開２００４−３０２９４１号公報
【特許文献３】特開２０１５−３５０４４号公報
【特許文献４】特開２００９−２１１５２６号公報
【特許文献５】特開２００９−１８１５３０号公報
【特許文献６】特開２００９−１２２８５６号公報
【非特許文献】
【０００５】
【非特許文献１】内村、「公共交通サービスにおけるＤｉａｌ−ａ−Ｒｉｄｅ問題」、１９９８
【非特許文献２】Cheng，“Mechanisms for Arranging Ride Sharing and Fare Splitting for Last-Mile Travel Demands”，２０１４
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、上記非特許文献１〜２に記載されている技術では、車両の移動経路のみを最適化しているため、人であるユーザの移動を最適化することはできない。また、ユーザと車両とを同時に最適化しようとすると、組み合わせ爆発のため現実的な時間で計算することができない、という問題があった。
【０００７】
また、上記特許文献１〜６に記載されている技術では、ユーザの１移動のみを対象としているため、ユーザの１日の移動全体を調整・最適化することができず、車両の稼働率やユーザのコストを最適化することができない、という問題があった。
【０００８】
本発明は、上記の事情に鑑みてなされたもので、複数のユーザの移動計画に応じた適切な移動経路及び移動手段を提示することができる情報処理装置、情報端末、情報提示システム、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために、第１の発明の情報処理装置は、複数のユーザの各々についての、前記ユーザの位置に関する情報と前記ユーザの目的地に関する情報との組み合わせ、複数の車両の各々の位置に関する情報、及び道路ネットワークデータに基づいて、リンクと時刻との組み合わせの各々についての、時刻ｔにリンクｌを通過するユーザの数を表すリンク需要ｙｌｔと、時刻ｔにリンクｌを通過する車両の数を表すリンク台数ｖｌｔと、１台あたりの乗車人数Ｃとを用いて表されたコスト関数ｃｌｔと前記リンク需要ｙｌｔとから求められる目的関数を、ユーザｉが時刻ｔにリンクｌを通過することを表すラウンドトリップａｉｌｔを用いて定められた制約条件を満たした上で最適化するように、前記リンク需要ｙｌｔと、前記リンク台数ｖｌｔと、前記ラウンドトリップａｉｌｔとを推定する推定手段と、前記推定手段によって推定された前記リンク需要ｙｌｔと、前記リンク台数ｖｌｔと、前記ラウンドトリップａｉｌｔとに基づいて、前記複数のユーザの各々に対する移動経路及び移動手段を算出する算出手段と、を含んで構成されている。
【００１０】
第２の発明に係るプログラムは、コンピュータを、複数のユーザの各々についての、前記ユーザの位置に関する情報と前記ユーザの目的地に関する情報との組み合わせ、複数の車両の各々の位置に関する情報、及び道路ネットワークデータに基づいて、リンクと時刻との組み合わせの各々についての、時刻ｔにリンクｌを通過するユーザの数を表すリンク需要ｙｌｔと、時刻ｔにリンクｌを通過する車両の数を表すリンク台数ｖｌｔと、１台あたりの乗車人数Ｃとを用いて表されたコスト関数ｃｌｔと前記リンク需要ｙｌｔとから求められる目的関数を、ユーザｉが時刻ｔにリンクｌを通過することを表すラウンドトリップａｉｌｔを用いて定められた制約条件を満たした上で最適化するように、前記リンク需要ｙｌｔと、前記リンク台数ｖｌｔと、前記ラウンドトリップａｉｌｔとを推定する推定手段、及び
前記推定手段によって推定された前記リンク需要ｙｌｔと、前記リンク台数ｖｌｔと、前記ラウンドトリップａｉｌｔとに基づいて、前記複数のユーザの各々に対する移動経路及び移動手段を算出する算出手段として機能させるためのプログラムである。
【００１１】
第１の発明及び第２の発明によれば、推定手段によって、複数のユーザの各々についての、前記ユーザの位置に関する情報と前記ユーザの目的地に関する情報との組み合わせ、複数の車両の各々の位置に関する情報、及び道路ネットワークデータに基づいて、リンクと時刻との組み合わせの各々についての、時刻ｔにリンクｌを通過するユーザの数を表すリンク需要ｙｌｔと、時刻ｔにリンクｌを通過する車両の数を表すリンク台数ｖｌｔと、１台あたりの乗車人数Ｃとを用いて表されたコスト関数ｃｌｔと前記リンク需要ｙｌｔとから求められる目的関数を、ユーザｉが時刻ｔにリンクｌを通過することを表すラウンドトリップａｉｌｔを用いて定められた制約条件を満たした上で最適化するように、前記リンク需要ｙｌｔと、前記リンク台数ｖｌｔと、前記ラウンドトリップａｉｌｔとを推定する。
【００１２】
そして、算出手段によって、前記推定手段によって推定された前記リンク需要ｙｌｔと、前記リンク台数ｖｌｔと、前記ラウンドトリップａｉｌｔとに基づいて、前記複数のユーザの各々に対する移動経路及び移動手段を算出する。
【００１３】
このように、複数のユーザの各々についての、ユーザの位置に関する情報とユーザの目的地に関する情報との組み合わせ、複数の車両の各々の位置に関する情報、及び道路ネットワークデータに基づいて、リンク需要ｙｌｔとリンク台数ｖｌｔと１台あたりの乗車人数Ｃとを用いて表されたコスト関数ｃｌｔとリンク需要ｙｌｔとから求められる目的関数を、ラウンドトリップａｉｌｔを用いて定められた制約条件を満たした上で最適化するように、リンク需要ｙｌｔとリンク台数ｖｌｔとラウンドトリップａｉｌｔとを推定し、推定されたリンク需要ｙｌｔとリンク台数ｖｌｔとラウンドトリップａｉｌｔとに基づいて、複数のユーザの各々に対する移動経路及び移動手段を算出することにより、複数のユーザの移動計画に応じた適切な移動経路及び移動手段を提示することができる。
【００１４】
第１の発明及び第２の発明の前記推定手段は、以下の式に示す前記コスト関数ｃｌｔと前記リンク需要ｙｌｔとから求められる目的関数を最適化するように、前記リンク需要ｙｌｔと、前記リンク台数ｖｌｔと、前記ラウンドトリップａｉｌｔとを推定するようにすることができる。
【００１５】
【数１】
2017142177.tif 000003
【００１６】
ただし、ｄｌは、リンクｌの距離である。
【００１７】
第１の発明及び第２の発明の前記制約条件は、前記ラウンドトリップａｉｌｔと前記リンク需要ｙｌｔとを用いて表された需要制約を含むようにすることができる。
【００１８】
また、前記制約条件は、更に、前記ユーザｉの各々についての目的地の数Ｄｉを用いて表された目的地制約、前記リンク台数ｖｌｔと前記リンク需要ｙｌｔとを用いて表された運転手制約、時刻ｔにおいて場所を表すノードｋに存在する車両の台数ｘｋｔを用いて表された台数制約、時刻ｔにおいて場所を表すノードｋに存在するユーザの数ｚｋｔを用いて表された人数制約、前記リンク台数ｖｌｔと前記車両の台数ｘｋｔとを用いて表された車両フロー制約、前記リンク需要ｙｌｔと前記ユーザの数ｚｋｔとを用いて表された人フロー制約、及び前記車両の台数ｘｋｔとノードｋに存在する駐車場容量ｌｋとを用いて表された駐車場容量制約の少なくとも１つの制約をようにすることができる。
【００１９】
第３の発明に係る情報端末は、上記の情報処理装置によって算出された前記ユーザの各々に対する移動経路及び移動手段に関する情報を取得する通信手段と、前記通信手段によって取得された前記移動経路及び前記移動手段に関する情報を提示する提示手段と、を含んで構成されている。
【００２０】
第４の発明に係る情報提示システムは、上記の情報処理装置と、上記の情報端末とを含んで構成されている。
【００２１】
なお、本発明のプログラムを記憶する記憶媒体は、特に限定されず、ハードディスクであってもよいし、ＲＯＭであってもよい。また、ＣＤ−ＲＯＭやＤＶＤディスク、光磁気ディスクやＩＣカードであってもよい。更にまた、該プログラムを、ネットワークに接続されたサーバ等からダウンロードするようにしてもよい。
【発明の効果】
【００２２】
以上説明したように、本発明の情報処理装置、情報端末、情報提示システム、及びプログラムによれば、複数のユーザの各々についての、ユーザの位置に関する情報とユーザの目的地に関する情報との組み合わせ、複数の車両の各々の位置に関する情報、及び道路ネットワークデータに基づいて、リンク需要ｙｌｔとリンク台数ｖｌｔと１台あたりの乗車人数Ｃとを用いて表されたコスト関数ｃｌｔとリンク需要ｙｌｔとから求められる目的関数を、ラウンドトリップａｉｌｔを用いて定められた制約条件を満たした上で最適化するように、リンク需要ｙｌｔとリンク台数ｖｌｔとラウンドトリップａｉｌｔとを推定し、推定されたリンク需要ｙｌｔとリンク台数ｖｌｔとラウンドトリップａｉｌｔとに基づいて、複数のユーザの各々に対する移動経路及び移動手段を算出することにより、複数のユーザの移動計画に応じた適切な移動経路及び移動手段を提示することができる、という効果が得られる。
【図面の簡単な説明】
【００２３】
【図１】本発明の実施の形態の概要を説明するための説明図である。
【図２】本発明の実施の形態の概要を説明するための説明図である。
【図３】本発明の実施の形態の概要を説明するための説明図である。
【図４】本発明の実施の形態の概要を説明するための説明図である。
【図５】本発明の実施の形態に係る情報提示システムの機能的構成を示すブロック図である。
【図６】コスト関数を説明するための説明図である。
【図７】本発明の実施の形態における最適化処理ルーチンの内容を示すフローチャートである。
【発明を実施するための形態】
【００２４】
＜概要＞
従来技術では、車両側の最適経路の探索のみが行われ、人を表すユーザ側の最適経路の誘導は行われておらず、ユーザの移動の最適化ができないといった問題があった。しかし、ユーザの移動の最適化を行う場合には最適化のための計算量が増大する。例えば、Ｋを場所数、Ｔをユーザの１日の移動回数、Ｎをユーザの数とすると、最適化に必要な計算量は以下の式（１）で表される。
【００２５】
【数２】
2017142177.tif 000004
【００２６】
上記式（１）に示すように、ユーザの移動を最適化するためには、最適化のための計算量が増大し、現実的な時間で計算出来ないという問題があった。
【００２７】
そこで、本発明の実施の形態では、図１に示すように、道路を表すリンク上の車両の台数とユーザの人数のみで利得が決まるモデルを設定する。そして、人を表すユーザと車両の双方の経路を探索する。本発明の実施の形態で用いるモデルでは、最適化の利得計算時にユーザと個々の車両とを区別をしなくて良い。また、本発明の実施の形態のモデルを用いることにより、図２に示すように、最適化問題が単峰の線形制約最適化問題になり、勾配法で解くことができる。これにより、人であるユーザと車両との双方の移動が最適化され、かつ最適化のための計算量が少なくて済む。
【００２８】
本発明の実施の形態では、ユーザ及び車両の移動を、カーシェア・ライドシェアゲームとして定式化する。具体的には、ユーザ同士の相乗り及び車両のシェアを行い、車両の稼働率を最大化させ、ユーザの移動計画のコーディネートを行う。
【００２９】
ユーザの移動コストは１日の移動経路で決まる。また、カーシェア・ライドシェアゲームでは、例えば、ユーザの移動回数、ユーザが車両に乗れるか乗れないか、車両の奪い合い、車両の偏在等が、ゲームの構成要素となる。
【００３０】
図３に、本発明の実施の形態におけるカーシェア・ライドシェアゲームを説明するための図を示す。図３では、各場所をノードとして表し、場所間を繋ぐ道路を表すリンクをノード間のエッジとして表す。例えば、図３に示すように、ユーザａとユーザｂとがノード０に位置し、ノード１に車両が存在する確率ｐがｐ＝０．７とし、リンクの距離ｄは全てｄ＝１とする。また、ユーザの移動コストを、徒歩が２、遠回りが１．８、便乗が１．３とすると、図４に示すような期待コストが得られる。ユーザの移動をコントロールしない場合、囚人のジレンマが発生し、ユーザａ及びユーザｂ共に「直行」を選択する。もしユーザａとユーザｂとを交互に遠回りさせることができれば、平均的な移動コストは１．８５に減少し、かつ車両の稼働率が向上する。ユーザの移動をコントロールするためには、金銭的なインセンティブや、車両の存在情報のコントロールでユーザの誘導は可能である。
【００３１】
以下、本発明の実施の形態を詳細に説明する。本実施の形態では、ユーザの位置に関する情報とユーザの目的地に関する情報とに基づいて、ユーザの移動経路及び移動手段を最適化し、最適化によって得られた結果に応じた情報をユーザに対して提示する情報提示システムに本発明を適用した場合を例に説明する。
【００３２】
＜情報提示システムのシステム構成＞
図５に示すように、本発明の実施の形態に係る情報提示システム１０は、複数の情報端末１２と、複数の車載装置１３と、複数の情報端末１２及び複数の車載装置１３から送信された情報を受信して、複数のユーザの各々に対して情報を提供するサーバ１４とを備えている。複数の情報端末１２と複数の車載装置１３とサーバ１４とは、例えばインターネットなどのネットワーク１６を介して接続されている。なお、サーバ１４は、情報処理装置の一例である。ユーザは情報端末１２を携帯し、車載装置１３は車両に搭載されている。
【００３３】
情報端末１２は、ユーザによって入力された現在地に関する情報及び目的地に関する情報を受け付ける入力部２０と、入力部２０によって受け付けた現在地に関する情報及び目的地に関する情報をユーザＩＤと共にサーバ１４へ送信すると共に、ユーザＩＤを含む移動経路及び移動手段の提示要求をサーバ１４へ送信し、移動経路及び移動手段を受信する通信部２２と、受信した移動経路及び移動手段をユーザに提示する提示部２４とを備えている。ユーザＩＤは、情報端末１２に予め設定されている。なお、本実施の形態では、ユーザが情報端末１２を携帯している場合を例に説明する。
【００３４】
例えば、ユーザＩＤをｉとすると、各ユーザｉは、１日の移動予定を検索するため、現在地に関する情報と目的地に関する情報Ｄｉとを情報端末１２へ入力する。そして、情報端末１２の入力部２０は現在地に関する情報と目的地に関する情報Ｄｉを受け付け、通信部２２は、現在地に関する情報及び目的地に関する情報をユーザＩＤと共にサーバ１４へ送信する。本実施の形態では、場所をノードで表すため、目的地は１箇所以上のノードで表される。
【００３５】
車載装置１３は、車両の位置に関する情報を取得するＧＰＳ３０と、ＧＰＳ３０によって取得された車両の位置に関する情報を車両ＩＤと共にサーバ１４へ逐次送信する通信部３２とを備えている。また車両ＩＤは、車載装置１３に予め設定されている。
【００３６】
サーバ１４は、ＣＰＵ、後述する最適化処理ルーチンを実現するためのプログラム等を記憶したＲＯＭ、データを一時的に記憶するＲＡＭ、記憶手段としてのメモリ、ネットワークインタフェース等を含むサーバで構成されており、機能的には、通信部４０、位置データベース４２、道路ネットワークデータベース４４、初期化部４６、リンク人数設定部４８、リンクコスト設定部５０、社会コスト設定部５２、制約条件設定部５４、最適化部５６、及び経路算出部５８を含んだ構成で表すことができる。最適化部５６は推定手段の一例であり、経路算出部５８は算出手段の一例である。
【００３７】
通信部４０は、情報端末１２から送信されたユーザＩＤ、現在地に関する情報、及び目的地に関する情報を受信し、位置データベース４２に格納するように制御する。また、通信部４０は、車載装置１３から送信された車両ＩＤ及び位置に関する情報を受信し、位置データベース４２に格納するように制御する。
【００３８】
また、通信部４０は、情報端末１２から送信された提示要求を受信すると、初期化部４６へ出力し、経路算出部５８により出力されたユーザの移動経路及び移動手段を、当該情報端末１２へ送信する。
【００３９】
位置データベース４２には、通信部４０によって受信した複数のユーザの各々についての、現在地に関する情報と目的地に関する情報との組み合わせが格納される。また、位置データベース４２には、通信部４０によって受信した複数の車両の各々の位置に関する情報が格納される。具体的には、通信部４０によって受信したユーザＩＤ、現在地に関する情報、及び目的地に関する情報が対応付けられて格納される。また、通信部４０によって受信した車両ＩＤ及び位置に関する情報が対応付けられて格納される。
【００４０】
道路ネットワークデータベース４４には、道路ネットワークデータが記憶されている。ここで、道路ネットワークデータとは、道路地図及び道路環境を示す道路情報を表すデータである。
【００４１】
次に、本発明の実施の形態におけるモデルの定式化について説明する。
【００４２】
本実施の形態では、場所をノードｋ、道路をリンクｌと表し、ノードとリンクとの接続関係を表す有向グラフを定義する。また、プレイヤであるユーザの数Ｎと車両台数Ｍと１日の長さＴとを定義する。
【００４３】
また、本発明の実施の形態におけるカーシェア・ライドシェアゲームのゲーム変数を以下のように定義する。
【００４４】
（１）ｉ：ユーザＩＤを表す番号。
（２）ａ：ユーザｉが時刻ｔからｔ＋１にかけて、リンクｌを通過すれば１であり、リンクｌを通過しなければ０であるラウンドトリップａｉｌｔを要素として持つラウンドトリップ行列である。各ユーザｉを行に、リンクｌ及び時刻ｔの組み合わせを表すｌｔを列にした行列となる。
（３）ｙ：時刻ｔからｔ＋１にかけてリンクｌを通過するユーザの数ｙｌｔを要素として持つリンク需要ベクトルである。
（４）ｖ：時刻ｔからｔ＋１にかけてリンクｌを通過するリンク台数ｖｌｔを要素として持つリンク台数ベクトルである。
（５）ｚ：時刻ｔにノードｋにいるユーザの数ｚｋｔを要素として持つノード人数ベクトルである。
（６）ｘ：時刻ｔにノードｋにいる車両台数ｘｋｔを要素として持つノード台数ベクトルである。
【００４５】
以下、時刻ｔ＝１...Ｔにかけて、上記（１）〜（６）の変数が変化する。
【００４６】
初期化部４６は、通信部４０によって出力された提示要求を受け付けると、ラウンドトリップ行列ａ，リンク需要ベクトルｙ，リンク台数ベクトルｖ，ノード人数ベクトルｚ，ノード台数ベクトルｘの初期値を設定する。
【００４７】
具体的には、初期化部４６は、道路ネットワークデータベース４４に格納された道路ネットワークに基づいて、場所をノードｋとし、道路をリンクｌとした有向グラフを設定する。
【００４８】
そして、初期化部４６は、設定された有向グラフと、位置データベース４２に格納されたユーザＩＤ、現在地に関する情報、及び目的地に関する情報とに基づいて、ユーザの初期位置に関するｔ＝０のノード人数ベクトルｚを設定する。また、初期化部４６は、設定された有向グラフと、位置データベース４２に格納された車両ＩＤ及び位置に関する情報に基づいて、車両の初期位置に関するｔ＝０のノード台数ベクトルｘを設定する。その他の変数の初期値の設定方法はどのようであってもよい。
【００４９】
リンク人数設定部４８は、初期化部４６によって初期値が設定されたラウンドトリップ行列ａとリンク需要ベクトルｙとの間の関係を設定する。本実施の形態では、ラウンドトリップ行列ａとリンク需要ベクトルｙとの間の関係を表す需要制約を、以下の式（２）に示すように定義する。需要制約は、ラウンドトリップａｉｌｔを要素にもつラウンドトリップ行列ａとリンク需要ｙｌｔを要素にもつリンク需要行列ｙとを用いて表される。
【００５０】
【数３】
2017142177.tif 000005
【００５１】
なお、上記式（２）は、リンクと時刻との組み合わせｌｔの各々について、時刻ｔにリンクｌを通過する人数を数えるとｙｌｔになることを表している。また、１Ｎは長さＮの全要素が１のベクトルである。
【００５２】
リンクコスト設定部５０は、リンク人数設定部４８によって設定されたリンク需要ベクトルｙと、初期化部４６によって初期値が設定されたリンク台数ベクトルｖとに基づいて、時刻ｔからｔ＋１にかけてリンクｌを通過するユーザのコストを設定する。本発明の実施の形態では、ユーザのコストを計算するためのコスト関数を、以下の式（３）に示すように定義する。
【００５３】
【数４】
2017142177.tif 000006
【００５４】
上記式（３）におけるＣは車両の定員であり定数であり、ｄｌはリンクｌの距離である。上記式（３）に示すように、コスト関数ｃｌｔは、リンクと時刻との組み合わせの各々についての、時刻ｔにリンクｌを通過するユーザの数を表すリンク需要ｙｌｔと、時刻ｔにリンクｌを通過する車両の数を表すリンク台数ｖｌｔと、１台あたりの乗車人数Ｃとを用いて表される。また、上記式（３）に示すように、車両にユーザが乗りきれる場合と、ユーザが多すぎて車両からあふれる場合とでユーザコストが異なる。
【００５５】
図６に、本実施の形態で用いるコスト関数をグラフで表したものを示す。図６（Ａ）は、横軸にリンク需要ベクトルｙの要素であるリンク需要ｙｌｔをとり、縦軸にコスト関数の値ｃｌｔをとったものである。また、図６（Ｂ）は、横軸にリンク台数ベクトルｖの要素であるリンク台数ｖｌｔをとり、縦軸にコスト関数の値ｃｌｔをとったものである。図６（Ａ）及び（Ｂ）に示すように、リンク需要ｙｌｔがＣｖｌｔよりも大きい場合と、リンク需要ｙｌｔがＣｖｌｔ以下の場合とで異なることがわかる。
【００５６】
社会コスト設定部５２は、リンクコスト設定部５０によって設定されたコスト関数と、リンク人数設定部４８によって設定されたリンク需要ベクトルｙとに基づいて、リンクと時刻との組み合わせｌｔの全てについての、全てのユーザｉのコストの総和を、社会コストを表す目的関数として設定する。本実施の形態では、社会コストを表す目的関数を、以下の式（４）に示すように定義する。社会コストを表す目的関数は、コスト関数ｃｌｔから得られる値を要素としてもつコスト行列ｃ（ｖ，ｙ）と、リンク需要ｙｌｔを要素としてもつリンク需要行列ｙとから求められる。
【００５７】
【数５】
2017142177.tif 000007
【００５８】
上記式（４）に示すように、社会コストを表す目的関数は、コスト行列ｃ（ｖ，ｙ）とリンク需要ベクトルｙとの積であるため、リンクと時刻との組み合わせｌｔの各々のコスト関数ｃｌｔから得られる値の和となる。
【００５９】
制約条件設定部５４は、複数の制約条件を設定する。本発明の実施の形態では、目的地制約、運転手制約、台数制約、人数制約、車両フロー制約、人フロー制約、及び駐車場容量制約を設定する場合を例に説明する。
【００６０】
目的地制約は、ユーザｉの各々についての目的地の数Ｄｉを用いて表される。例えば、ユーザｉの目的地をｋ＝１とした場合、ユーザｉはノードｋ＝１に繋がるリンクの何れかを少なくとも１回以上通過する。また、目的地が３つである場合、それらの目的地に繋がるリンクの何れかを少なくとも３回以上通過する。よって、本実施の形態では、以下の式（５）に示すように目的地制約を定義する。
【００６１】
【数６】
2017142177.tif 000008
【００６２】
上記式（５）において、Ｇはユーザｉを行に、リンクと時刻との組み合わせｌｔを列にした行列であり、ユーザｉが通過すべきリンクｌに対応した要素が１、ユーザｉが通過すべきでないリンクｌに対応した要素が０である。また、Ｄは長さＮのベクトルであり、ｉ番目の要素はユーザｉの目的地数｜Ｄｉ｜である。なお、上記式（５）の右辺と左辺は行列であるが、行列内の対応する各要素が上記式（５）に示す大小関係を満たすことを表している。
【００６３】
運転手制約は、リンク台数ｖｌｔとリンク需要ｙｌｔとを用いて表される。車両の移動には運転手が必要であるため、あるリンクを移動する車両台数はユーザの数以下となる。よって、本実施の形態では、以下の式（６）に示すように運転手制約を定義する。
【００６４】
【数７】
2017142177.tif 000009
【００６５】
なお、上記式（６）の右辺と左辺はベクトルであるが、ベクトル内の対応する各要素が上記式（５）に示す大小関係を満たすことを表している。
【００６６】
台数制約は、時刻ｔにおいて場所を表すノードｋに存在する車両の台数ｘｋｔを用いて表される。各時刻の車両台数は一定であるため、本実施の形態では、以下の式（７）に示すように台数制約を定義する。
【００６７】
【数８】
2017142177.tif 000010
【００６８】
ただし、ｌｋｔは、長さがノードと時刻との組み合わせｋｔの総数であり、かつ全要素が１のベクトルである。また、Ｍは車両の台数である。
【００６９】
人数制約は、時刻ｔにおいて場所を表すノードｋに存在するユーザの数ｚｋｔを用いて表される。各時刻のユーザの数は一定であるため、本実施の形態では、以下の式（８）に示すように台数制約を定義する。
【００７０】
【数９】
2017142177.tif 000011
【００７１】
ただし、Ｎはユーザの数である。
【００７２】
車フロー制約は、リンク台数ｖｌｔと車両の台数ｘｋｔとを用いて表される。各時刻のノードの車両台数は、「ノードにおける前の時刻の車両台数＋ノードへの流入台数−ノードからの流出台数」である。よって、本実施の形態では、以下の式（９）に示すように台数制約を定義する。
【００７３】
【数１０】
2017142177.tif 000012
【００７４】
ここで、リンク数をＬとすると、上記式（９）におけるΓは、Ｌ＊（Ｔ−１）行、Ｋ＊（Ｔ−１）列の行列であり、ΛはＫ＊Ｔ行、Ｋ＊（Ｔ−１）列の行列である。
【００７５】
また、ある１つの列を表すノードと時刻との組み合わせｋｔについては、以下の式（１０）に示すように、時刻ｔからｔ＋１に遷移するときのノードｋのフロー制約によって制約される。
【００７６】
【数１１】
2017142177.tif 000013
【００７７】
上記式（１０）において、ｌｉｎはノードｋに流入するリンクを表し、ｌoutはノードｋから流出するリンクを表す。ノードｋに対し、ｌｉｎ，ｌoutは複数ある。また、ノードと時刻との組み合わせｋｔの各々に対し、上記式（１０）により制約される。また、Ｋ＊（Ｔ−１）個の全ての列によって、Ｋ個の全ノードのＴ−１回の全遷移が表される。
【００７８】
人フロー制約は、リンク需要ｙｌｔとユーザの数ｚｋｔとを用いて表される。各時刻のノードの車両台数は、「ノードにおける前の時刻のユーザの数＋ノードへ流入するユーザの数−ノードから流出するユーザの数」である。車両と同様に、ユーザの数にも以下の式（１１）に示す制約が成り立つ。
【００７９】
【数１２】
2017142177.tif 000014
【００８０】
上記式（１１）におけるΘは、Ｌ＊（Ｔ−１）行、Ｋ＊（Ｔ−１）列の行列であり、ΦはＫ＊Ｔ行、Ｋ＊（Ｔ−１）列の行列である。
【００８１】
ここで、ある１つの列を表すノードと時刻との組み合わせｋｔについては、以下の式（１２）に示すように、時刻ｔからｔ＋１に遷移するときのノードｋの以下のフロー制約によって制約される。
【００８２】
【数１３】
2017142177.tif 000015
【００８３】
上記式（１０）と同様に、上記式（１２）において、ｌｉｎはノードｋに流入するリンクを表し、ｌoutはノードｋから流出するリンクを表す。ノードｋに対し、ｌｉｎ，ｌoutは複数ある。また、ノードと時刻との組み合わせｋｔの各々に対し、上記式（１２）により制約される。また、Ｋ＊（Ｔ−１）個の全ての列によって、Ｋ個の全ノードのＴ−１回の全遷移が表される。
【００８４】
駐車場容量制約は、車両の台数ｘｋｔとノードｋに存在する駐車場容量ｌｋを要素としてもつ駐車場容量ベクトルｌとを用いて表される。本実施の形態では、以下の式（１３）に示すように駐車場容量制約を定義する。
【００８５】
【数１４】
2017142177.tif 000016
【００８６】
以上説明した、社会コストを表す目的関数及び各制約条件をまとめると、以下に示すようになる。
【００８７】
【数１５】
2017142177.tif 000017
【００８８】
なお、上記式（１３）の左辺はベクトルであるが、ベクトル内の対応する各要素が０以上であることを表している。
【００８９】
最適化部５６は、上記式（１２）に示した社会コストを表す目的関数を、上記式（１３）〜（１９）に示す制約条件を満たした上で最適化するように、リンクと時刻との組み合わせｌｔの各々についてのリンク需要ｙｌｔと、リンクと時刻との組み合わせｌｔの各々についてのリンク台数ｖｌｔと、リンクと時刻との組み合わせｌｔの各々についてのラウンドトリップａｉｌｔとを推定する。
【００９０】
具体的には、最適化部５６は、上記式（１３）〜（１９）に示す制約条件と、初期化部４６によって設定された各変数の初期値とに基づいて、もっとも社会コストが低くなる、都市にとって最適な交通と各ユーザの１日のラウンドトリップａｉｌｔを最適解として求める。
【００９１】
最適化部５６によって、各ユーザｉに対し、リンクと時刻との組み合わせｌｔの各々についてのラウンドトリップａｉｌｔが推定され、ラウンドトリップａｉｌｔにより、ユーザの移動経路及び移動手段が確率的に推定される。
【００９２】
なお、最適化部５６は、線形制約つき最適問題を扱えるアルゴリズムを用いて最適化を行う。例えば、最適化部５６は、内点法アルゴリズムを用いて最適化を行うことができる。内点法アルゴリズムを用いるものとしては、例えば、Ｍａｔｌａｂのｆｍｉｎｃｏｎ関数を利用することができる。
【００９３】
経路算出部５８は、最適化部５６によって推定された、リンクと時刻との組み合わせｌｔの各々についてのリンク需要ｙｌｔと、リンクと時刻との組み合わせｌｔの各々についてのリンク台数ｖｌｔと、リンクと時刻との組み合わせｌｔの各々についてのラウンドトリップａｉｌｔとに基づいて、複数のユーザの各々に対する移動経路及び移動手段を算出する。
【００９４】
具体的には、経路算出部５８は、最適化部５６によって推定されたラウンドトリップａｉｌｔに基づいて、各ユーザに対し１日の移動経路及び移動手段を算出する。例えば、経路算出部５８は、ラウンドトリップａｉｌｔに基づいて、特定のリンクと特定の時刻との組み合わせｌｔが共通するユーザ同士を、同一の車両に同乗させて移動する移動経路及び移動手段を算出する。そして、経路算出部５８は、移動経路及び移動手段を、通信部４０により情報端末１２へ送信する。
【００９５】
情報端末１２の通信部２２は、通信部４０により送信された移動経路及び移動手段を取得する。情報端末１２の提示部２４は、通信部２２によって取得された移動経路及び移動手段を、ユーザに提示する。
【００９６】
＜情報提示システムの作用＞
次に、情報提示システム１０の作用について説明する。
【００９７】
まず、複数の情報端末１２が、逐次、ユーザＩＤ、現在地の情報、及び目的地の情報を、サーバ１４へ送信し、サーバ１４は、受信したユーザＩＤ、現在地の情報、及び目的地の情報を、位置データベース４２に蓄積する。
【００９８】
また、複数の車載装置１３が、逐次、車両ＩＤ及び位置に関する情報を、サーバ１４へ送信し、サーバ１４は、受信した車両ＩＤ及び位置に関する情報を、位置データベース４２に蓄積する。
【００９９】
また、情報端末１２が、ユーザＩＤを含む提示要求をサーバ１４へ送信し、サーバ１４の通信部４０が提示要求を受信すると、サーバ１４は図７に示す最適化処理ルーチンを実行する。
【０１００】
まず、ステップＳ１００において、初期化部４６は、道路ネットワークデータベース４４に格納された道路ネットワークに基づいて、場所をノードｋとし、道路をリンクｌとした有向グラフを設定する。そして、初期化部４６は、位置データベース４２に格納された複数のユーザの各々についての、現在地に関する情報と目的地に関する情報との組み合わせと、位置データベース４２に格納された複数の車両の各々の位置に関する情報とに基づいて、ラウンドトリップ行列ａ，リンク需要ベクトルｙ，リンク台数ベクトルｖ，ノード人数ベクトルｚ，及びノード台数ベクトルｘの初期値を設定する。
【０１０１】
次のステップＳ１０２において、リンク人数設定部４８は、上記ステップＳ１００で初期値が設定されたラウンドトリップ行列ａとリンク需要ベクトルｙとの間の関係を表す需要制約を、上記式（２）に示すように設定する。
【０１０２】
そして、ステップＳ１０４において、リンクコスト設定部５０は、上記ステップＳ１０２で設定されたリンク需要ベクトルｙと、上記ステップＳ１００で初期値が設定されたリンク台数ベクトルｖとに基づいて、ユーザのコストを計算するためのコスト関数を、上記式（３）に示すように設定する。
【０１０３】
ステップＳ１０６において、社会コスト設定部５２は、上記ステップＳ１０４で設定されたコスト関数と、上記ステップＳ１０２で設定されたリンク需要ベクトルｙとに基づいて、社会コストを表す目的関数を、上記式（４）に示すように設定する。
【０１０４】
そして、ステップＳ１０８において、制約条件設定部５４は、目的地制約、運転手制約、台数制約、人数制約、車両フロー制約、人フロー制約、及び駐車場容量制約を、上記式（５）〜（１３）に示すように設定する
【０１０５】
ステップＳ１１０において、最適化部５６は、上記ステップＳ１０６で設定された社会コストを表す目的関数を、上記ステップＳ１０８で設定された制約条件を満たした上で最適化するように、リンク需要ｙｌｔと、リンク台数ｖｌｔと、ラウンドトリップａｉｌｔとを推定する。
【０１０６】
ステップＳ１１２において、経路算出部５８は、上記ステップＳ１１０で推定されたリンク需要ｙｌｔと、リンク台数ｖｌｔと、ラウンドトリップａｉｌｔとに基づいて、複数のユーザの各々に対する移動経路及び移動手段を算出する。
【０１０７】
そして、ステップＳ１１４において、通信部４０によって、上記ステップＳ１１２で算出された複数のユーザの各々に対する移動経路及び移動手段を、各情報端末１２へ送信する。
【０１０８】
情報端末１２の通信部２２は、サーバ１４より送信された移動経路及び移動手段を受け付け、提示部２４へ出力する。そして、提示部２４は、通信部２２により出力された移動経路及び移動手段をユーザに提示する。
【０１０９】
以上説明したように、本発明の実施の形態に係る情報提示システムによれば、複数のユーザの各々についての、ユーザの位置に関する情報とユーザの目的地に関する情報との組み合わせ、複数の車両の各々の位置に関する情報、及び道路ネットワークデータに基づいて、リンク需要ｙｌｔとリンク台数ｖｌｔと１台あたりの乗車人数Ｃとを用いて表されたコスト関数ｃｌｔとリンク需要ｙｌｔとから求められる目的関数を、ラウンドトリップａｉｌｔを用いて定められた制約条件を満たした上で最適化するように、リンク需要ｙｌｔとリンク台数ｖｌｔとラウンドトリップａｉｌｔとを推定し、推定されたリンク需要ｙｌｔとリンク台数ｖｌｔとラウンドトリップａｉｌｔとに基づいて、複数のユーザの各々に対する移動経路及び移動手段を算出することにより、複数のユーザの移動計画に応じた適切な移動経路及び移動手段を提示することができる。
【０１１０】
また、ユーザの移動と車両の移動との双方を最適化することができる。また、組み合わせによる計算量の爆発を回避して、複数のユーザの移動と車両の移動とを最適化することができる。
【０１１１】
なお、上記実施の形態では、ユーザの移動手段として、徒歩及び車両を考慮したが、その他の移動手段を考慮してもよい。車両以外の移動手段を考慮する場合には、別途コスト関数を定義する。例えば、車両以外の移動手段として鉄道が含まれる場合、以下の式に示すようにコスト関数を定義することができる。
【０１１２】
【数１６】
2017142177.tif 000018
【０１１３】
上記式において、「ｆａｒｅ」は運賃を表し、「ｗａｉｔ」は待ち時間を表す。
【０１１４】
また、上記実施の形態では、複数の制約条件として、目的地制約、運転手制約、台数制約、人数制約、車両フロー制約、人フロー制約、及び駐車場容量制約を設定する場合を例に説明したがこれに限定されるものではない。問題に応じて、制約条件は追加又は削除が可能である。
【０１１５】
また、サーバ１４による最適化結果を用いて、ユーザに移動経路及び移動手段を提示する場合を例に説明したが、これに限定されるものではなく、最適化結果を用いて、移動経路及び移動手段を提示する以外の処理を行ってもよい。
【０１１６】
また、最適化処理を実行する装置が、サーバ１４として実装される場合を例に説明したが、これに限定されるものではなく、情報端末上に、最適化処理を実行する装置が実装されるようにしてもよい。
【符号の説明】
【０１１７】
１０   情報提示システム
１２   情報端末
１３   車載装置
１４   サーバ
１６   ネットワーク
２０   入力部
２２   通信部
２４   提示部
３２   通信部
４０   通信部
４２   位置データベース
４４   道路ネットワークデータベース
４６   初期化部
４８   リンク人数設定部
５０   リンクコスト設定部
５２   社会コスト設定部
５４   制約条件設定部
５６   最適化部
５８   経路算出部
【図１】
2017142177.tif 000020
【図２】
2017142177.tif 000021
【図３】
2017142177.tif 000022
【図４】
2017142177.tif 000023
【図５】
2017142177.tif 000024
【図６】
2017142177.tif 000025
【図７】
2017142177.tif 000026