(57)【要約】【課題】欠損を含む観測値データから経路別交通量を推定する。【解決手段】入力された道路網データに基づいて、移動対象の出発地から目的地までの複数の経路を生成する経路生成手段と、前記経路生成手段により生成された前記複数の経路と、前記移動対象の交通量を各々観測する複数の観測地点とに基づいて、前記複数の経路の各々を通る移動対象が前記複数の観測地点の各々で観測されるか否かを表すルーチング行列を生成するルーチング行列生成手段と、前記ルーチング行列生成手段により生成された前記ルーチング行列と、複数の観測期間において前記複数の観測地点で各々観測された前記移動対象の交通量を示す第１の観測値データとに基づいて、前記複数の経路の各々における前記移動対象の交通量を推定する経路別交通量推定手段と、を有することを特徴とする。【選択図】図４
2019082757.tif 000002
【特許請求の範囲】
【請求項１】
入力された道路網データに基づいて、移動対象の出発地から目的地までの複数の経路を生成する経路生成手段と、
前記経路生成手段により生成された前記複数の経路と、前記移動対象の交通量を各々観測する複数の観測地点とに基づいて、前記複数の経路の各々を通る移動対象が前記複数の観測地点の各々で観測されるか否かを表すルーチング行列を生成するルーチング行列生成手段と、
前記ルーチング行列生成手段により生成された前記ルーチング行列と、複数の観測期間において前記複数の観測地点で各々観測された前記移動対象の交通量を示す第１の観測値データとに基づいて、前記複数の経路の各々における前記移動対象の交通量を推定する経路別交通量推定手段と、
を有することを特徴とする推定装置。
【請求項２】
前記経路別交通量推定手段は、
前記第１の観測値データに含まれる欠損値を除外した第２の観測値データを生成し、前記ルーチング行列と、前記第２の観測値データとに基づいて、前記複数の経路の各々における前記移動対象の交通量を推定する、ことを特徴とする請求項１に記載の推定装置。
【請求項３】
前記経路別交通量推定手段は、
更に、前記複数の観測期間の公約数を観測時間幅とし、
前記複数の観測期間の全体を前記観測時間幅で分割したものを単位時間として、
前記複数の観測期間の各々が１以上の単位時間から構成されるものとし、
単位時間毎の各経路の交通量を未知数として、
前記第２の観測値データの各々が、当該観測期間を構成する単位時間毎の、当該第２の観測値データの観測地点で観測可能な経路毎の交通量の総和で表されるものと仮定して前記未知数である単位時間毎の各経路の交通量を推定する、ことを特徴とする請求項２に記載の推定装置。
【請求項４】
前記経路生成手段は、
前記道路網データに含まれるノードのうち、所定の第１のノードが含まれる第１の集合と、所定の第２のノードが含まれる第２の集合とから各々出発地と目的地とを選択して、選択された前記出発地から前記目的地までの複数の経路を生成する、ことを特徴とする請求項１乃至３の何れか一項に記載の推定装置。
【請求項５】
前記経路生成手段は、
前記出発地から前記目的地までの最短経路の距離に対して所定の値を乗じた第１の距離と、前記複数の経路の各々の第２の距離とを比較し、前記第１の距離以上である第２の距離に対応する経路を前記複数の経路から除外する、ことを特徴とする請求項１乃至４の何れか一項に記載の推定装置。
【請求項６】
前記経路生成手段は、
前記複数の観測地点のいずれの観測地点でも観測されない経路を前記複数の経路から除外する、ことを特徴とする請求項１乃至５の何れか一項に記載の推定装置。
【請求項７】
入力された道路網データに基づいて、移動対象の出発地から目的地までの複数の経路を生成する経路生成手順と、
前記経路生成手順により生成された前記複数の経路と、前記移動対象の交通量を各々観測する複数の観測地点とに基づいて、前記複数の経路の各々を通る移動対象が前記複数の観測地点の各々で観測されるか否かを表すルーチング行列を生成するルーチング行列生成手順と、
前記ルーチング行列生成手順により生成された前記ルーチング行列と、複数の観測期間において前記複数の観測地点で各々観測された前記移動対象の交通量を示す第１の観測値データとに基づいて、前記複数の経路の各々における前記移動対象の交通量を推定する経路別交通量推定手順と、
をコンピュータが実行することを特徴とする推定方法。
【請求項８】
コンピュータを、請求項１乃至６の何れか一項に記載の推定装置における各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、推定装置、推定方法及びプログラムに関する。
【背景技術】
【０００２】
大規模なイベント等で起こり得る混雑に対応するため、マルチエージェントシミュレータ（ＭＡＳ：Multi-Agent Simulator）を用いた人流の把握や制御策の策定等が従来から行われている。より正確な人流の把握や効果的な制御策の策定等のためには、精度の高いシミュレーションが必要となる。このため、観測したデータを基に、その観測データを再現するパラメータを決定する技術が必要不可欠である。このようなパラメータとしては、例えば、移動経路の通過人数を示すパラメータが挙げられる。
【０００３】
ここで、例えば、複数の観測地点で観測された人数から移動経路別の通過人数を推定する技術に類似する課題を解く技術として、通信分野における交流トラヒック推定技術が知られている（例えば、特許文献１、非特許文献１）。交流トラヒック推定技術は、通信ネットワークにおいて、各ノードの発信トラヒック量及び着信トラヒック量と、各リンクのトラヒック量と、経路情報とから、各ノードペア間の通信量を推定する技術である。
【０００４】
交通の移動を推定する問題に対して交流トラヒック推定技術を適用する場合、通信と異なり交通の移動には移動時間が掛かるため、同一時間帯において複数の観測地点で同一人物を観測できないことがある。しかしながら、対象時間帯において交通量の定常性を仮定すれば、交通の移動を推定する問題においても、通信分野の交流トラヒック推定技術と同様の問題設定と見做すことができる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第５０６０５１３号公報
【非特許文献】
【０００６】
【非特許文献１】Zhang Y. et al, "Fast Accurate Computation of Large-Scale IP Traffic Matrices from Link Loads", SIGMETRICS '03, pp.206-217, 2003.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ところで、交流トラヒック推定技術では、例えば設計者が設計した経路のみでトラヒックが流れることを前提としている。一方で、交通の移動を推定するためには、移動する対象（例えば、人や車、バイク、自転車等）が選択する経路候補も推定する必要があるが、従来技術では、このような経路候補の推定をモデル化することができない。
【０００８】
また、精度の高いシミュレーションのためには、実際に交通量を観測したデータが必要となるが、例えば数取器等を用いて交通量を計測した場合、交通量を計測できなかった時間帯が存在することがある。すなわち、交通量を観測した観測値データに欠損がある場合がある。
【０００９】
本発明は、上記の点に鑑みてなされたものであって、欠損を含む観測値データから経路別交通量を推定することを目的とする。
【課題を解決するための手段】
【００１０】
そこで、本発明の実施の形態では、入力された道路網データに基づいて、移動対象の出発地から目的地までの複数の経路を生成する経路生成手段と、前記経路生成手段により生成された前記複数の経路と、前記移動対象の交通量を各々観測する複数の観測地点とに基づいて、前記複数の経路の各々を通る移動対象が前記複数の観測地点の各々で観測されるか否かを表すルーチング行列を生成するルーチング行列生成手段と、前記ルーチング行列生成手段により生成された前記ルーチング行列と、複数の観測期間において前記複数の観測地点で各々観測された前記移動対象の交通量を示す第１の観測値データとに基づいて、前記複数の経路の各々における前記移動対象の交通量を推定する経路別交通量推定手段と、を有することを特徴とする。
【発明の効果】
【００１１】
欠損を含む観測値データから経路別交通量を推定することができる。
【図面の簡単な説明】
【００１２】
【図１】本発明の実施の形態における経路別人数推定装置の構成の一例を示す図である。
【図２】観測値データの一例を示す図である。
【図３】本発明の実施の形態における経路別人数推定装置のハードウェア構成の一例を示す図である。
【図４】本発明の実施の形態における経路別人数推定装置の機能構成の一例を示す図である。
【図５】本発明の実施の形態における経路別人数推定装置が実行する処理の一例を示すフローチャートである。
【発明を実施するための形態】
【００１３】
以下、本発明の実施の形態について、図面を参照しながら説明する。以降では、経路別交通量の一例として経路別の人数を推定する経路別人数推定装置１０について説明する。ただし、経路別交通量は、経路別の人数に限られない。経路別交通量としては、例えば、経路別の車の台数、経路別のバイクの台数、経路別の自転車の台数、経路別の生物の個体数等であっても良い。したがって、本発明の実施の形態における経路別人数推定装置１０は、これらの経路別交通量を推定する場合についても同様に適用することができる。なお、経路を移動する人、車、バイク、自転車、生物等の移動対象は、「エージェント」と称されても良い。
【００１４】
＜経路別人数推定装置１０の構成＞
まず、本発明の実施の形態における経路別人数推定装置１０の構成について、図１を参照しながら説明する。図１は、本発明の実施の形態における経路別人数推定装置１０の構成の一例を示す図である。
【００１５】
図１に示す経路別人数推定装置１０は、エージェントが通過し得る経路の候補（以下、単に「経路候補」とも表す。）を生成した上で、観測値データ等から経路別の人数（以下、単に「経路別人数」とも表す。）を推定するコンピュータ又はコンピュータシステムである。図１に示す経路別人数推定装置１０には、経路別人数推定プログラム１００がインストールされている。経路別人数推定プログラム１００は、１つのプログラムであっても良いし、複数のプログラム又はモジュールで構成されるプログラム群であっても良い。
【００１６】
図１に示す経路別人数推定装置１０は、経路別人数推定プログラム１００が実行する処理によって、経路候補の生成と、経路別人数の推定とを行う。
【００１７】
＜変数の定義＞
ここで、本発明の実施の形態で用いる各変数を以下のように定義する。
【００１８】
・Ｘｔ，ｉ：経路別人数の推定値。
【００１９】
・ｔ：時刻を示すインデックス。ｔは、０≦ｔ≦Ｔとする。
【００２０】
・Ｔ：観測対象とした時間帯の最後の時刻。
【００２１】
・Ｒｉ：経路候補（エージェントが通過し得るノード列）。
【００２２】
・ｉ：経路候補のインデックス。ｉは、１≦ｉ≦Ｉとする。
【００２３】
・Ｉ：経路候補の個数。
【００２４】
・Ｙｔ，ｊ：観測地点別人数の観測値。
【００２５】
・Ｍｊ：観測地点（観測対象となるノード列）。
【００２６】
・ｊ：観測地点のインデックス。ｊは、１≦ｊ≦Ｊとする。
【００２７】
・Ｊ：観測地点の個数。
【００２８】
・Ａ：ルーチング行列。
【００２９】
ここで、観測地点別人数Ｙｔ，ｊを各要素とするＴ行Ｊ列の行列を観測値データＹと表す。観測値データＹとは、時間及び空間的に或る粒度で交通量を計測し、集計したデータのことである。観測値データＹを得る方法としては、例えば、国土交通省「平成27年度  全国道路・街路交通情勢調査  一般交通量調査結果の概要について」に開示されているように、道路を通過する車や人の数をカウントして交通量を測定する方法が挙げられる。
【００３０】
観測値データＹの一例を図２に示す。図２に示すように、観測値データＹは、観測時間帯（観測期間）ｔ＝０〜ｔ＝１の間に観測地点Ｍｊ（ｊ＝１，２，・・・，Ｊ）で観測された観測値Ｙ１，ｊ（ｊ＝１，２，・・・，Ｊ）を（１，ｊ）成分の要素とする。同様に、観測値データＹは、観測時間帯ｔ＝１〜ｔ＝２の間に観測地点Ｍｊ（ｊ＝１，２，・・・，Ｊ）で観測された観測値Ｙ２，ｊ（ｊ＝１，２，・・・，Ｊ）を（２，ｊ）成分の要素とする。以降も同様に、観測値データＹは、観測時間帯ｔ＝Ｔ−１〜ｔ＝Ｔの間に観測地点Ｍｊ（ｊ＝１，２，・・・，Ｊ）で観測された観測値ＹＴ，ｊ（ｊ＝１，２，・・・，Ｊ）を（Ｔ，ｊ）成分の要素とする。
【００３１】
観測値データＹに含まれる観測値Ｙｔ，ｊには欠損値が存在しても良い。言い換えれば、或る観測地点Ｍｊの或る観測時間帯で欠測が存在しても良い。欠損値である観測値Ｙｔ，ｊには、ＮＵＬＬが設定されていても良いし、予め決められた所定の値（例えば、欠損値であることを示す所定のコード値や観測値として取り得ない値等）が設定されていても良い。
【００３２】
なお、各観測時間の時間幅はそれぞれ異なっていても良い。例えば、観測時間ｔ＝０〜ｔ＝１の間の時間幅と、観測時間ｔ＝１〜ｔ＝２の間の時間幅とが異なっていても良い。また、観測地点Ｍｊ毎に異なる時間幅で観測されても良い。例えば、ｔ＝０からｔ＝Ｔまでの期間の間において、観測地点Ｍ１ではＴ回観測される一方で、観測地点Ｍ２ではＴ／２回観測される等である。言い換えれば、観測地点Ｍｊ毎に観測周期が異なっていても良い。この場合、観測の時間幅が揃っている観測地点Ｍｊ毎にまとめて（すなわち、観測周期が同一の観測地点Ｍｊ毎にまとめて）、複数の行列により観測値データＹを表現しても良い。
【００３３】
＜経路別人数推定装置１０のハードウェア構成＞
次に、本発明の実施の形態における経路別人数推定装置１０のハードウェア構成について、図３を参照しながら説明する。図３は、本発明の実施の形態における経路別人数推定装置１０のハードウェア構成の一例を示す図である。
【００３４】
図３に示す経路別人数推定装置１０は、入力装置１１と、表示装置１２と、外部Ｉ／Ｆ１３と、ＲＡＭ（Random Access Memory）１４と、ＲＯＭ（Read Only Memory）１５と、ＣＰＵ（Central Processing Unit）１６と、通信Ｉ／Ｆ１７と、補助記憶装置１８とを有する。これら各ハードウェアは、それぞれがバスＢを介して通信可能に接続されている。
【００３５】
入力装置１１は、例えばキーボードやマウス、タッチパネル等であり、ユーザが各種操作を入力するのに用いられる。表示装置１２は、例えばディスプレイ等であり、経路別人数推定装置１０の処理結果を表示する。なお、経路別人数推定装置１０は、入力装置１１及び表示装置１２の少なくとも一方を有していなくても良い。
【００３６】
外部Ｉ／Ｆ１３は、外部装置とのインタフェースである。外部装置には、記録媒体１３ａ等がある。経路別人数推定装置１０は、外部Ｉ／Ｆ１３を介して、記録媒体１３ａ等の読み取りや書き込みを行うことができる。記録媒体１３ａには、経路別人数推定プログラム１００等が記録されていても良い。
【００３７】
記録媒体１３ａには、例えば、フレキシブルディスク、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disk）、ＳＤメモリカード（Secure Digital memory card）、ＵＳＢ（Universal Serial Bus）メモリカード等がある。
【００３８】
ＲＡＭ１４は、プログラムやデータを一時保持する揮発性の半導体メモリである。ＲＯＭ１５は、電源を切ってもプログラムやデータを保持することができる不揮発性の半導体メモリである。ＲＯＭ１５には、例えば、ＯＳ設定やネットワーク設定等が格納されている。
【００３９】
ＣＰＵ１６は、ＲＯＭ１５や補助記憶装置１８等からプログラムやデータをＲＡＭ１４上に読み出して処理を実行する演算装置である。
【００４０】
通信Ｉ／Ｆ１７は、経路別人数推定装置１０を通信ネットワークに接続するためのインタフェースである。経路別人数推定プログラム１００は、通信Ｉ／Ｆ１７を介して、所定のサーバ装置等から取得（ダウンロード）されても良い。
【００４１】
補助記憶装置１８は、例えばＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）等であり、プログラムやデータを格納している不揮発性の記憶装置である。補助記憶装置１８に格納されているプログラムやデータには、例えば、ＯＳ、当該ＯＳ上において各種機能を実現するアプリケーションプログラム、経路別人数推定プログラム１００等がある。
【００４２】
本発明の実施の形態における経路別人数推定装置１０は、図３に示すハードウェア構成を有することにより、後述する各種処理を実現することができる。
【００４３】
＜経路別人数推定装置１０の機能構成＞
次に、本発明の実施の形態における経路別人数推定装置１０の機能構成について、図４を参照しながら説明する。図４は、本発明の実施の形態における経路別人数推定装置１０の機能構成の一例を示す図である。
【００４４】
図４に示す経路別人数推定装置１０は、経路候補生成部１１０と、ルーチング行列生成部１２０と、経路別人数推定部１３０とを有する。これら各部は、経路別人数推定プログラム１００がＣＰＵ１６に実行させる処理により実現される。
【００４５】
経路候補生成部１１０は、道路網データＧと、ノード集合Ｖ及びＵと、倍率αと、観測地点リストＭとを入力して、経路候補リストＲを生成する。経路候補リストＲは、経路候補Ｒｉのリストである。ただし、経路候補Ｒｉは、道路網データＧでリンクが存在するようなノード列である。
【００４６】
なお、経路候補生成部１１０は、ノード集合Ｖ及びＵと、倍率αと、観測地点リストＭとのうちの少なくとも１つが入力されなくても良い。すなわち、ノード集合Ｖ及びＵと、倍率αと、観測地点リストＭとは任意の入力データである。
【００４７】
道路網データＧは、対象とする道路網を表す有向グラフである。道路網データＧは、道路網に属するノード（例えば、交差点等）の集合をＮ、道路網に属するリンク（例えば、道路等）の集合をＥとして、Ｇ＝｛Ｎ，Ｅ｝と表される。
【００４８】
ノード集合Ｖ及びＵは、出発地（Ｏ）と目的地（Ｄ）との組合わせ（以降では、「ＯＤ組合せ」と表す。）を限定するためのノードの集合である。ＯＤ組合せとは、出発地となるノードと、目的地となるノードとの組み合わせである。
【００４９】
ノード集合Ｖ及びＵに含まれるノードとしては、ランドマークを示すノード（例えば人が発生又は消滅する可能性のあるノード）が挙げられる。具体的には、ノード集合Ｖとしては、例えば、駅を示すノードの集合が挙げられる。また、ノード集合Ｕとしては、例えば、イベント会場の入口を示すノードの集合が挙げられる。
【００５０】
倍率αは、経路候補Ｒｉの道のりの許容範囲を限定するための値である。倍率αの値は、例えば経路別人数推定装置１０のユーザ等により予め設定される。
【００５１】
観測地点リストＭは、どの観測地点Ｍｊでも観測されない経路候補Ｒｉを除外するための観測地点Ｍｊのリストである。
【００５２】
ルーチング行列生成部１２０は、経路候補リストＲと、観測地点リストＭとを入力して、ルーチング行列Ａを生成する。
【００５３】
経路別人数推定部１３０は、ルーチング行列Ａと、観測値データＹとを入力して、経路別人数Ｘを推定する。そして、経路別人数推定部１３０は、推定した経路別人数Ｘを出力する。経路別人数Ｘは、経路別の交通量を表す行列である。なお、経路別人数推定部１３０は、予め設定された任意の出力先に経路別人数Ｘを出力すれば良い。例えば、経路別人数推定部１３０は、経路別人数Ｘを表示装置１２に出力しても良いし、補助記憶装置１８や記録媒体１３ａ等に出力（保存）しても良いし、通信Ｉ／Ｆ１７を介してネットワーク上のサーバ装置等に出力（送信）しても良い。また、経路別人数推定部１３０は、経路別人数Ｘを他のプログラム（例えば、人流シミュレーションプログラム）に出力しても良い。
【００５４】
＜経路別人数推定装置１０が実行する処理＞
次に、本発明の実施の形態における経路別人数推定装置１０が実行する処理について、図５を参照しながら説明する。図５は、本発明の実施の形態における経路別人数推定装置が実行する処理の一例を示すフローチャートである。
【００５５】
ステップＳ１０１：経路候補生成部１１０は、全てのＯＤ組合せに対して以下の（１）〜（４）の手順を実行することで、経路候補リストＲを生成する。ノード集合Ｖ及びＵが入力されない場合、経路候補生成部１１０は、道路網データＧに含まれるノードからＯＤ組合せを作成する。一方で、ノード集合Ｖ及びＵが入力される場合、経路候補生成部１１０は、ノード集合Ｖに含まれるノードと、ノード集合Ｕに含まれるノードとからＯＤ組合せを作成する。ノード集合Ｖに含まれるノードと、ノード集合Ｕに含まれるノードとからＯＤ組合せを作成することは、ノード集合Ｖとノード集合Ｕとの完全２部グラフの各辺を選択することに相当する。
【００５６】
なお、道路網データＧに含まれるノードと、ノード集合Ｖに含まれるノードと、ノード集合Ｕに含まれるノードとは、いずれも出発地（Ｏ）にも目的地（Ｄ）にもなり得るものとする。すなわち、道路網データＧに含まれるノードＮ１とノードＮ２とついて、ＯＤ組合せは、ノードＮ１を出発地、ノードＮ２を目的地とした組み合わせと、ノードＮ２を出発地、ノードＮ１を目的地とした組み合わせとが存在する。ノード集合Ｖ及びＵについても同様に、ノード集合Ｖに含まれるノードＮ１と、ノード集合Ｕに含まれるノードＮ２とについて、ＯＤ組合せは、ノードＮ１を出発地、ノードＮ２を目的地とした組み合わせと、ノードＮ２を出発地、ノードＮ１を目的地とした組み合わせとが存在する。
【００５７】
（１）経路候補生成部１１０は、ＯＤ組合せに含まれる出発地（Ｏ）を示すノード（以降、「ノードＯ」と表す。）と、当該ＯＤ組合せに含まれる目的地を示すノード（以降、「ノードＤ」と表す。）との間の全経路を数え上げる。数え上げられた各経路が経路候補Ｒｉである。
【００５８】
ノードＯとノードＤとの間の全経路の数え上げは、例えばＧｒａｐｈｉｌｌｉｏｎを用いて行うことができる。Ｇｒａｐｈｉｌｌｉｏｎについては、例えば、ＥＲＡＴＯ  湊離散構造処理系プロジェクト（著），湊真一（編集）「超高速グラフ列挙アルゴリズム−〈フカシギの数え方〉が拓く，組合せ問題への新アプローチ」森北出版2015.に開示されている。
【００５９】
（２）経路候補生成部１１０は、最短経路探索アルゴリズムにより、ノードＯとノードＤとの間の最短経路を探索して、探索した最短経路の距離を算出する。これには、ＰｙｔｈｏｎのライブラリであるＮｅｔｗｏｒｋＸ等を用いることができる。
【００６０】
（３）次に、経路候補生成部１１０は、上記の（１）で得られた各経路候補Ｒｉの距離（経路候補距離ｄｉ）と、上記の（２）で得られた最短経路の距離（最短距離ｄｍｉｎ）とを比較する。そして、経路候補生成部１１０は、各経路候補Ｒｉのうち、経路候補距離ｄｉが最短距離ｄｍｉｎのα倍以上となっている経路候補Ｒｉを除外する。
【００６１】
（４）次に、経路候補生成部１１０は、上記（３）で得られた経路候補Ｒｉのうち、観測されない経路候補Ｒｉを除外する。経路候補Ｒｉが観測されるか否かは、観測地点リストＭを用いて判定することができる。
【００６２】
より具体的には、例えば、観測地点リストＭに含まれる観測地点ＭｊをＭｊ＝［Ｍｊ，１，Ｍｊ，２，・・・，Ｍｊ，ｎ］、経路候補ＲｉをＲｉ＝［Ｒｉ，１，Ｒｉ，２，・・・，Ｒｉ，ｋ］とする。ただし、ｎは観測地点Ｍｊに含まれるノード数、ｋは経路候補Ｒｉに含まれるノード数である。このとき、Ｒｉ，１，Ｒｉ，２，・・・，Ｒｉ，ｋのうちのいずれかのノードが、Ｍｊ，１，Ｍｊ，２，・・・，Ｍｊ，ｎのいずれかのノードと同一ノードである場合に、経路候補Ｒｉは観測されると判定される。一方で、Ｒｉ，１，Ｒｉ，２，・・・，Ｒｉ，ｋのうちのいずれのノードも、Ｍｊ，１，Ｍｊ，２，・・・，Ｍｊ，ｎのうちのいずれのノードとも同一ノードでない場合に、経路候補Ｒｉは観測されないと判定される。
【００６３】
特に、経路候補Ｒｉの先頭ノードＲｉ，１が、Ｍｊ，１，Ｍｊ，２，・・・，Ｍｊ，ｎのうちのいずれかのノードと同一ノードである場合は、経路候補Ｒｉの出発が観測される。同様に、経路候補Ｒｉの末尾ノードＲｉ，ｋが、Ｍｊ，１，Ｍｊ，２，・・・，Ｍｊ，ｎのうちのいずれかのノードと同一ノードである場合は、経路候補Ｒｉの到着が観測される。また、観測地点Ｍｊが経路候補Ｒｉの部分列である場合、経路候補Ｒｉの通過が観測される。
【００６４】
全てのＯＤ組合せに対して上記の（４）で得られた経路候補Ｒｉのリストが経路候補リストＲである。そして、経路候補生成部１１０は、得られた経路候補リストＲをルーチング行列生成部１２０に出力する。
【００６５】
なお、上述したように、ノード集合Ｖ及びＵと、倍率αと、観測地点リストＭとのうちの少なくとも１つは、経路候補生成部１１０に入力されなくても良い。ただし、道路網データＧの大きさによっては、経路候補リストＲに含まれる経路候補Ｒｉの数が膨大になる場合がある。このため、ノード集合Ｖ及びＵと、倍率αと、観測地点リストＭとのうちの少なくとも１つを用いて、経路候補Ｒｉを限定することが好ましい。
【００６６】
ステップＳ１０２：ルーチング行列生成部１２０は、経路候補リストＲ及び観測地点リストＭからルーチング行列Ａを生成する。ルーチング行列Ａの各要素をＡｊ，ｉとすれば、ルーチング行列Ａは、以下の式１により生成される。
【００６７】
【数１】
2019082757.tif 000003
つまり、経路候補Ｒｉが観測地点Ｍｊで観測されれば、ルーチング行列の（ｊ，ｉ）要素Ａｊ，ｉが１となり、そうでない場合はＡｊ，ｉが０となるようにルーチング行列Ａを生成する。
【００６８】
経路候補Ｒｉが観測地点Ｍｊで観測されるか否かは、例えば以下のようにして判定する。経路候補ＲｉをＲｉ＝［Ｒｉ，１，Ｒｉ，２，・・・，Ｒｉ，ｋ］とする。ただし、ｋは経路候補Ｒｉに含まれるノード数である。観測地点リストＭに含まれる観測地点ＭｊをＭｊ＝［Ｍｊ，１，Ｍｊ，２，・・・，Ｍｊ，ｎ］とする。ただし、ｎは観測地点Ｍｊに含まれるノード数とする。観測地点Ｍｊは、「出発」「到着」「通過」のいずれかの属性を持つ。属性が「出発」の場合、経路候補Ｒｉの先頭要素（先頭のノード）Ｒｉ，１が観測地点Ｍｊに含まれていれば観測されるとし、そうでなければ観測されないとする。属性が「到着」の場合、経路候補Ｒｉの末尾要素Ｒｉ，ｋが観測地点Ｍｊに含まれていれば観測されるとし、そうでなければ観測されないとする。属性が「通過」の場合、経路候補Ｒｉの少なくとも一部が観測地点Ｍｊに含まれていれば観測されるとし、そうでなければ観測されないとする。このように、観測地点リストＭには、「出発」「到着」「通過」のうちの少なくとも１つの属性の観測地点Ｍｊが含まれるものとして、各属性に応じて経路候補Ｒｉが観測地点Ｍｊで観測されるか否かを判定し、ルーチング行列の（ｊ，ｉ）要素Ａｊ，ｉの値を設定する。
【００６９】
このようにして生成されるルーチング行列Ａの各要素は、複数の経路の各々を通る移動対象（例えば、人、車、バイク、自転車等）が、複数の観測地点の各々で観測されるか否かを表すものとなる。つまり、Ａｊ，ｉは、経路候補Ｒｉを通る移動対象を観測地点Ｍｊで観測できるか否かを表す。これにより、経路候補Ｒｉを通る移動対象の数の推定に際し、観測値データＹの中のどの要素を考慮すれば良いかがルーチング行列Ａによって特定されることになる。
【００７０】
ステップＳ１０３：経路別人数推定部１３０は、以下の（１）〜（４）の手順を実行することで、ルーチング行列Ａ及び観測値データＹから経路別人数Ｘを推定する。
【００７１】
（１）経路別人数推定部１３０は、観測値データＹを整形して、観測値データＳを生成する。整形後の観測値データＳは、Ｄ行３列の行列であり、ｄ行目が［Ｍｄ，Ｕｄ，Ｙｄ´］である。ここで、Ｄは、観測値データＹに含まれる観測値Ｙｔ，ｊから欠損値を除いた観測値Ｙｔ，ｊの個数である。言い換えれば、Ｄは、観測値データＹに含まれる観測値Ｙｔ，ｊのうち、欠損値でない観測値Ｙｔ，ｊの要素数である。欠損値でない観測値Ｙｔ，ｊに対して１から順にインデックスを振り直して、各要素毎の値を［Ｍｄ，Ｕｄ，Ｙｄ´］に変換して得られたものが観測値データＳである。
【００７２】
Ｍｄは、ｄ番目（ｄ＝１，２，・・・，Ｄ）の観測値Ｙｄ´の観測地点のインデックスであり、１≦Ｍｄ≦Ｊである。Ｕｄは、当該観測値Ｙｄ´の観測時間帯（観測期間）を表す情報であり、所定の時間幅ΔＴ毎に区切った時間帯をｔｋ（ｋ＝１，２，・・・）として、ｄ番目の観測値Ｙｄ´を観測した時間帯に相当する時間区間（単位時間）ｔｉのリストである。ここで、以降では、ΔＴを観測時間幅と呼ぶこととする。
【００７３】
例えば、或る観測値Ｙｄ´がｔ２〜ｔ４で表される時間帯を観測することで得られた場合、値Ｕｄ＝｛ｔ２，ｔ３，ｔ４｝となる。同様に、別の或る観測値Ｙｄ´がｔ３〜ｔ４で表される時間帯を観測することで得られた場合、値Ｕｄ＝｛ｔ３，ｔ４｝となる。
【００７４】
なお、観測時間幅ΔＴは、十分小さく設定することが好ましい。観測時間幅ΔＴを十分小さく設定することで、観測時間帯の時間幅が異なる複数の観測値データＹを用いる場合や１つの観測値データＹで異なる時間幅の観測時間帯が存在する場合等にも、全ての観測時間を考慮した観測値データＳを生成することができる。具体的には、例えば、時間幅が「１０分」の観測時間帯と、時間幅が「１５分」の観測時間帯とが存在する場合、ΔＴを「５分」（すなわち、全ての観測時間帯の時間幅の公約数）として観測値データＳを生成する。つまり、観測値データＹの各観測期間全体を所定の観測時間幅に分割したものを単位時間ｔ１，ｔ２，・・・，ｔＴとし、各観測期間を１以上の単位時間の組み合わせで表現し直した（正規化した）ものがＵｄである。そして、観測値データＳは、観測値データＹから欠損値を取り除き、正規化した観測期間（Ｕｄ）毎及び観測地点毎の観測値が特定できる形に整形し直したデータである。これにより、トラヒック量の観測期間又は観測周期が異なる観測値データＹが与えられた場合やトラヒック量の観測期間又は観測周期にずれがある観測データＹが与えられた場合等でも、観測期間の違いや観測周期のずれを許容することができる。
【００７５】
（２）次に、経路別人数推定部１３０は、観測行列Ｈの各要素をＨｄ，ｔとして、以下の式２により観測行列Ｈを生成する。
【００７６】
【数２】
2019082757.tif 000004
ここで、ＡＭｄはルーチング行列ＡのＭｄ行目の要素を並べた１×Ｉの行列である。また、観測期間Ｕｄにｔが含まれない場合のＨｄ，ｔ＝０はスカラではなく、各要素が０の１×Ｉの行列を表す。結果として、観測行列Ｈは、Ｄ×（Ｉ×Ｔ）の行列となる。
【００７７】
（３）次に、経路別人数推定部１３０は、以下の式３により、目的関数Ｌを最小化するＸ´を求める。
【００７８】
【数３】
2019082757.tif 000005
ただし、人数は非負であるため、制約条件Ｘｔ，ｉ´≧０を満たすように目的関数Ｌを最小化する。言い換えると、Ｙ´＝ＨＸ´を満たす（Ｉ×Ｔ）次元のベクトルＸ´を求める。
【００７９】
上記の式３を最小化するＸ´を求める手法としては、例えば、信頼領域Ｒｅｆｌｅｃｔｉｖｅ法アルゴリズム等を用いれば良い。信頼領域Ｒｅｆｌｅｃｔｉｖｅ法アルゴリズムは、例えば、Coleman, T. F. and Y. Li."A Reflective Newton Method for Minimizing a Quadratic Function Subject to Bounds on Some of the Variables,"SIAM Journal on Optimization, Vol. 6, Number 4, pp.1040-1058, 1996.等に開示されている。
【００８０】
（４）次に、経路別人数推定部１３０は、上記の（３）で求めた（Ｉ×Ｔ）次元のベクトルＸ´を、先頭要素から順に１行にＩ個ずつ並べることでＴ行Ｉ列の行列Ｘに変換する。この行列Ｘが経路別人数Ｘである。Ｘの（ｔ，ｉ）要素が時刻ｔにおいて経路Ｒｊを通過する人数の推定結果となる。
【００８１】
ステップＳ１０４： 経路別人数推定部１３０は、上記のステップＳ１０４で得られた経路別人数Ｘを出力する。
【００８２】
以上により、本発明の実施の形態における経路別人数推定装置１０は、観測値データＹから経路別人数Ｘを推定及び出力することができる。しかも、本発明の実施の形態における経路別人数推定装置１０は、観測値データＹに含まれる観測値に欠損値があったり、観測値の観測期間の長さが異なっていたりする場合であっても、経路別人数Ｘを推定することができる。
【００８３】
本発明の実施の形態における経路別人数推定装置１０により得られた経路別人数Ｘを、例えば、人流シミュレータへの入力とすることで、人流の時間的な推移を再構成することができる。また、この経路別人数Ｘは、マーケティングにおける顧客動線の把握や、雑踏警備における誘導策の検討等にも役立つと考えられる。
【００８４】
本発明は、具体的に開示された上記の実施形態に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。
【符号の説明】
【００８５】
１０        経路別人数推定装置
１００      経路別人数推定プログラム
１１０      経路候補生成部
１２０      ルーチング行列生成部
１３０      経路別人数推定部
【図１】
2019082757.tif 000006
【図２】
2019082757.tif 000007
【図３】
2019082757.tif 000008
【図４】
2019082757.tif 000009
【図５】
2019082757.tif 000010