特許ウォッチ

公開番号2024171069
公報種別公開特許公報(A)
公開日2024-12-11
出願番号2023087943
出願日2023-05-29
発明の名称情報処理システム
出願人株式会社日立製作所
代理人ポレール弁理士法人
主分類G06Q 10/04 20230101AFI20241204BHJP(計算;計数)
要約【課題】問題規模の削減及び計算時間削減を可能とする情報処理装置を提供することを目的とする。
【解決手段】割当先データと割当データ、制約条件、共有条件を得る手段と、割当先の要素の集合である割当先データに対して、制約条件に従って、割当対象の集合である割当データの中から割当を行うとともに、共有条件に従って割当の一部をグルーピングし、割当関係を示すグラフを作成するグラフ生成部と、割当関係を示すグラフの探索により割当候補を複数生成するグラフ探索部と、最適化モデルを生成し、割当候補に対する最適化処理を実施して最適化割当を得る最適化計算部と、最適化割当に含まれるグルーピングを解除して最終割当とする展開部を備える。
【選択図】図1
特許請求の範囲【請求項１】
割当先データと割当データ、制約条件、共有条件を得る手段と、
割当先の要素の集合である前記割当先データに対して、前記制約条件に従って、割当対象の集合である前記割当データの中から割当を行うとともに、前記共有条件に従って割当の一部をグルーピングし、割当関係を示すグラフを作成するグラフ生成部と、
割当関係を示す前記グラフの探索により割当候補を複数生成するグラフ探索部と、
最適化モデルを生成し、前記割当候補に対する最適化処理を実施して最適化割当を得る最適化計算部と、
前記最適化割当に含まれる前記グルーピングを解除して最終割当とする展開部を備えることを特徴とする情報処理システム。
続きを表示（約 370 文字）【請求項２】
請求項１に記載の情報処理システムであって、
前記グラフ探索部は、グルーピングされない割り当てに対してＫＰＩ計算を実施することを特徴とする情報処理システム。
【請求項３】
請求項１に記載の情報処理システムであって、
前記展開部は、グルーピングされた割り当てに対してＫＰＩ計算を実施することを特徴とする情報処理システム。
【請求項４】
請求項１に記載の情報処理システムであって、
前記最適化計算部は、前記グラフ探索部で生成した複数の割当の一部の割当を対象とする最適化計算を実施することを特徴とする情報処理システム。
【請求項５】
請求項２に記載の情報処理システムであって、
前記ＫＰＩ計算に基づくコストを付与することを特徴とする情報処理システム。

発明の詳細な説明【技術分野】
【０００１】
本発明は、情報処理システムに係り、特に組合せ最適化問題の問題規模削減のための情報処理システムに関する。
続きを表示（約 1,500 文字）【背景技術】
【０００２】
社会システムの生産性向上のためアニーリング法が組合せ最適化問題の高速解法として注目を浴びている。交通系や配送・巡回経路決定などの実問題では多数の複雑な制約条件を加味する必要があり、特に勤務シフト作成や人員配置といったような割当問題は、所謂ＮＰ困難な問題に分類され、従来のコンピュータに基づくアルゴリズムでは、実用に耐えうる速度での計画の立案が困難であることが知られている。このため、割当計画立案の自動化へのシーズないしニーズが高まっていると考えられる。
【０００３】
上記に関連する従来技術として、例えば下記特許文献１に記載の技術が挙げられる。
入力された情報に基づき、事前に計画された割当に対して、その一部分を再計画の対象とし候補グラフを作成し、割当問題の候補生成を行う前処理部及び、前機能部において生成された候補から候補選択を行う最適化部により、計画立案範囲を再計画部分に限定することで解候補を抑制しつつ割当を行う割当問題処理システム。
【先行技術文献】
【特許文献】
【０００４】
特開２０２２－１４５５０６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
特許文献１は、一般的な集合分割問題／集合被覆問題を相互作用モデルによって記述し、最適化問題を、事前に計画された元の計画に対して、元の計画を保持する部分と再計画を行う部分とにわけ、計画の一部分を再計画対象として限定することで、問題規模の削減を行い、指定するＫＰＩによってなるべく元の計画を保持するように割当を行う。
【０００６】
この技術では、一から計画を作成する際には、解の候補数が膨大となり最適化部において現実的な時間での解の探索が困難になる可能性が高いことが懸念される。
【０００７】
本発明者らは、鋭意研究を行い、このような再計画の立案は「最適化問題」として計算機で解くことができるとの知見ないしコンセプトのもと、以下のように思案するに至った。
【０００８】
すなわち、実社会の大規模な最適化問題を高速で解くには、例えばイジングモデルなどの「相互作用モデル」で問題を記述し、ＣＭＯＳアニーリングのような「最適化問題専用計算技術」を用いて計算を実行する方法が考えられる。相互作用モデルを用いて再計画立案を行うにあたり、複雑な制約条件を効率的に扱う方法として、列生成法等を用いて部分問題の候補生成を行った後に、集合分割問題や集合被覆問題を解く手段を用いることが有力である。
【０００９】
以上のことから本発明は、問題規模の削減及び計算時間削減を可能とする情報処理装置を提供することを目的とする。
【課題を解決するための手段】
【００１０】
以上のことから本発明においては、「割当先データと割当データ、制約条件、共有条件を得る手段と、割当先の要素の集合である割当先データに対して、制約条件に従って、割当対象の集合である割当データの中から割当を行うとともに、共有条件に従って割当の一部をグルーピングし、割当関係を示すグラフを作成するグラフ生成部と、割当関係を示すグラフの探索により割当候補を複数生成するグラフ探索部と、最適化モデルを生成し、割当候補に対する最適化処理を実施して最適化割当を得る最適化計算部と、最適化割当に含まれるグルーピングを解除して最終割当とする展開部を備えることを特徴とする情報処理システム。」としたものである。
【発明の効果】
（【００１１】以降は省略されています）

関連特許