特許ウォッチ

公開番号2024078255
公報種別公開特許公報(A)
公開日2024-06-10
出願番号2022190685
出願日2022-11-29
発明の名称経路探索支援装置、経路探索支援方法、及び経路探索支援システム
出願人株式会社日立製作所
代理人弁理士法人一色国際特許事務所
主分類G06Q 10/047 20230101AFI20240603BHJP(計算;計数)
要約【課題】多数の経由地が存在する場合であっても経由すべき経由地を経由する適切な経路を効率良く探索することを支援する経路探索支援装置、方法及びシステムを提供する。
【解決手段】経路探索支援装置100は、移動体が経由可能な経由地を示す単位ノードを作成する単位ノード作成部、単位ノードのうち、第1の条件を満たす単位ノードの組み合わせをリアルノードに設定するリアルノード設定部、リアルノード内の単位ノードを縮約するダミーノード設定部、設定した各ノードに基づき、車両が移動可能な経路を示す有向グラフを作成するリンク接続部、有向グラフに基づき、車両が出発地から経由地を経て到着地に至る経路を探索するグラフ探索部、算出した各種のデータを記憶する係数記憶部、各車両の移動経路の最適解を求める最適経路作成処理部及び算出した値に基づき、移動体の各経由地の経由有無を示す情報を出力する結果出力処理部を含む。
【選択図】図2
特許請求の範囲【請求項１】
複数の移動体のそれぞれが１又は複数の経由地を経て移動する経路の作成を支援する装置であって、
前記移動体が出発地から到着地まで移動する過程で経由可能な経由地を示す単位ノードを作成する単位ノード作成処理と、
前記単位ノードのうち、第１の条件を満たす１又は互いに隣接する２以上の単位ノードの組み合わせをリアルノードに設定するリアルノード設定処理と、
前記リアルノードを構成する単位ノードのうち、第２の条件を満たす１又は互いに隣接する２以上の単位ノードの組み合わせを検索し、検索した単位ノードをダミーノードに設定するダミーノード設定処理と、
前記リアルノードを構成する単位ノードのうち前記ダミーノード以外の単位ノードが示す経由地の経由回数を制約条件とし、移動体の移動経路に関する所定の評価関数を含む目的関数の値を最適化する場合の、前記単位ノードが示す経由地の利用有無を示す値を算出する最適経路作成処理と、
前記算出した値に基づき、前記移動体の各経由地の経由有無を示す情報を出力する結果出力処理とを実行する処理装置を備える、
経路探索支援装置。
続きを表示（約 1,500 文字）【請求項２】
前記処理装置は、前記リアルノード設定処理において、前記第１の条件を満たす単位ノードの組み合わせとして、当該組み合わせの単位ノード間の結合の強さを示す評価値が所定値以上である単位ノードを前記リアルノードに設定する、
請求項1に記載の経路探索支援装置。
【請求項３】
前記処理装置は、前記リアルノード設定処理において、前記第１の条件を満たす単位ノードの組み合わせとして、当該組み合わせの単位ノード間の移動時間の短さ又は距離の短さが所定値以上である単位ノードを前記リアルノードに設定する、
請求項２に記載の経路探索支援装置。
【請求項４】
前記処理装置は、前記ダミーノード設定処理において、前記第２の条件に関して、前記リアルノードを構成する単位ノードから、当該リアルノードを構成する単位ノード以外の単位ノードを経由するために経由が必要な、１又は互いに隣接する２以上の単位ノードを検索し、検索した単位ノードをダミーノードに設定する、
請求項１に記載の経路探索支援装置。
【請求項５】
前記処理装置は、前記ダミーノード設定処理において、前記第２の条件に関して、前記リアルノードにおける単位ノードから、他の単位ノードとの結合の強さを示す評価値が所定値以下である単位ノードを検索し、検索した単位ノードをダミーノードに設定する、
請求項１に記載の経路探索支援装置。
【請求項６】
前記処理装置は、
２以上の単位ノードの組み合わせによるリアルノードにおける前記単位ノード間の結合の上限の設定をユーザから受け付ける設定処理を実行し、
前記リアルノード設定処理において、前記上限を超えないような、互いに隣接する２以上の単位ノードの組み合わせをリアルノードに設定する、
請求項１に記載の経路探索支援装置。
【請求項７】
前記処理装置は、
前記ダミーノードの数の上限の設定をユーザから受け付ける設定処理を実行し、
前記ダミーノード設定処理において、前記上限を超えないようにダミーノードを設定す
る、
請求項１に記載の経路探索支援装置。
【請求項８】
前記処理装置は、
前記リアルノード設定処理において、前記各移動体に共通に適用される所定の制約条件を満たすリアルノードを作成し、
前記最適経路作成処理において、前記移動体に応じて異なる制約条件を前記目的関数に設定する、
請求項1に記載の経路探索支援装置。
【請求項９】
前記処理装置は、
前記最適経路作成処理において、前記リアルノードを構成する単位ノードのうち前記ダミーノード以外の単位ノードが示す経由地の経由回数に関する制約条件が満たされる際に最小となる制約条件用関数、及び、移動体の移動経路に関する評価関数を項として含む目的関数に関して、単位ノードが示す経由地の利用有無をスピンとし、前記制約条件用関数における変数間の感応度を前記スピンの間の相互作用の強度に設定したイジングモデルを演算し、
前記結果出力処理において、前記演算の結果に基づき、前記移動体の各経由地の経由有無を示す情報を出力装置に出力する、
請求項1に記載の経路探索支援装置。
【請求項１０】
前記処理装置は、前記単位ノードの候補であるノードの指定をユーザから受け付ける設定処理を実行する、請求項1に記載の経路探索支援装置。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明は、経路探索支援装置、経路探索支援方法、及び経路探索支援システムに関する。
続きを表示（約 2,500 文字）【背景技術】
【０００２】
グラフ理論を用いた最短経路問題においては、しばしば複雑な制約条件が設定される場合がある。このようなケースでは、候補となる経路のパターンを作成しておき、作成したパターンに対して集合被覆問題又は集合問題の解法アルゴリズムを適用することで、各経路の採用又は不採用のパターンを決定して最適化問題を解くことがある。
【０００３】
集合被覆問題を用いた経路計画作成の方法としては、例えば、特許文献１に、相乗りを含む運行計画の作成の対象となるユーザを要素とした集合に対して、劣加法性を満たす可能性の高さを示す指標を用いて上記集合の要素を順序付け、順位の高い順かつ所定数以内の要素の組み合わせが劣加法性を満たすか判定し、劣加法性を満たした要素の組み合わせを、相乗りの対象とする部分集合に追加することで、集合被覆問題として、要素の重複を許容して集合を部分集合に分割し、分割された部分集合を用いて運行計画を生成する運行計画プログラムが開示されている。
【先行技術文献】
【特許文献】
【０００４】
特開２０１７－１９１５０４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、経路のパターンは経路における経由地の数と共に指数関数的に増大するため、経由地の数が多い場合は、最適化問題の処理工程が計算機の処理能力又はアルゴリズムの性能を超えてしまい、解が得られなく可能性が高まる。
【０００６】
本発明は、このような問題に鑑みてなされたものであり、多数の経由地が存在する場合であっても経由すべき経由地を経由する適切な経路を効率良く探索することを支援することが可能な経路探索支援装置、経路探索支援方法、及び経路探索支援システムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記課題を解決するための本発明の一つは、複数の移動体のそれぞれが１又は複数の経由地を経て移動する経路の作成を支援する装置であって、前記移動体が出発地から到着地まで移動する過程で経由可能な経由地を示す単位ノードを作成する単位ノード作成処理と、前記単位ノードのうち、第１の条件を満たす１又は互いに隣接する２以上の単位ノードの組み合わせをリアルノードに設定するリアルノード設定処理と、前記リアルノードを構成する単位ノードのうち、第２の条件を満たす１又は互いに隣接する２以上の単位ノードの組み合わせを検索し、検索した単位ノードをダミーノードに設定するダミーノード設定処理と、前記リアルノードを構成する単位ノードのうち前記ダミーノード以外の単位ノードが示す経由地の経由回数を制約条件とし、移動体の移動経路に関する所定の評価関数を含む目的関数の値を最適化する場合の、前記単位ノードが示す経由地の利用有無を示す値を算出する最適経路作成処理と、前記算出した値に基づき、前記移動体の各経由地の経由有無を示す情報を出力する結果出力処理とを実行する処理装置を備える、経路探索支援装置である。
【０００８】
上記課題を解決するための本発明の他の一つは、複数の移動体のそれぞれが１又は複数の経由地を経て移動する経路の作成を支援する経路探索支援システムであって、前記移動体が出発地から到着地まで移動する過程で経由可能な経由地を示す単位ノードを作成する単位ノード作成処理と、前記単位ノードのうち、第１の条件を満たす１又は互いに隣接する２以上の単位ノードの組み合わせをリアルノードに設定するリアルノード設定処理と、前記リアルノードを構成する単位ノードのうち、第２の条件を満たす１又は互いに隣接する２以上の単位ノードの組み合わせを検索し、検索した単位ノードをダミーノードに設定するダミーノード設定処理と、前記リアルノードを構成する単位ノードのうち前記ダミーノード以外の単位ノードが示す経由地の経由回数を制約条件とし、移動体の移動経路に関する所定の評価関数を含む目的関数の値を最適化する場合の、前記単位ノードが示す経由地の利用有無を示す値を算出する最適経路作成処理と、前記算出した値に基づき、前記移動体の各経由地の経由有無を示す情報を出力する結果出力処理とを実行する処理装置を備える経路作成支援装置、及び、前記移動体が経由可能な経由地の入力をユーザから受け付ける入力処理と、前記結果出力処理で出力された情報を画面に表示する表示処理とを実行する処理装置を備える情報処理装置を含んで構成される経路探索支援システムである。
【発明の効果】
【０００９】
本発明によれば、多数の経由地が存在する場合であっても経由すべき経由地を経由する適切な経路を効率良く探索することを支援することができる。
上記した以外の構成及び効果等は、以下の実施形態の説明により明らかにされる。
【図面の簡単な説明】
【００１０】
本実施形態に係る経路探索支援システムの構成の一例を示す図である。
経路探索支援装置が備える機能の一例を示す図である。
経路探索支援装置が備えるハードウェアの一例を示す図である。
経路探索支援処理の概要を説明するフロー図である。
経路候補作成処理の詳細を説明するフロー図である。
設定画面の一例を示す図である。
リアルノードの探索の一例を説明する図である。
作成される有向グラフの構成の一例を示す図である。
ダミーノードの設定方法の一例を説明する図である。
グラフ解析部が記憶するデータベースの一例を示す図である。
スピン系の基底状態を得るためのタイミングチャートである。
イジングモデルにおける解法アルゴリズムをフローチャートである。
【発明を実施するための形態】
（【００１１】以降は省略されています）

関連特許