特許ウォッチ

公開番号2024171441
公報種別公開特許公報(A)
公開日2024-12-12
出願番号2023088446
出願日2023-05-30
発明の名称割当問題処理システム及び割当問題処理方法
出願人株式会社日立製作所
代理人青稜弁理士法人
主分類G06Q 10/0631 20230101AFI20241205BHJP(計算;計数)
要約【課題】部分問題に分解した際に制約充足困難で計算が終了しなくなる問題を解消することで、大規模の割当問題を処理可能にする割当問題処理システム及び割当問題処理方法を提供する。
【解決手段】割当問題処理システムは、割当問題の問題区間の部分区間である部分問題区間に対応する部分問題を生成し、部分問題に対して割当候補となる複数の候補を生成し、複数の候補から最適な組み合わせを選択することにより部分問題に対する解である部分解を計算することにより、割当問題の解を計算する。割当問題処理システムは、部分解が割当問題の制約条件を充足しない場合、問題区間において部分問題区間をずらすことにより、部分問題を作り直して再計算を行うことと、部分問題の部分解を計算するときの前記制約条件を必要に応じて修正することと、の少なくとも一方を実行する。
【選択図】図1
特許請求の範囲【請求項１】
割当問題を処理する計算機を含む割当問題処理システムであって、
前記計算機は、
前記割当問題の問題区間の部分区間である部分問題区間に対応する部分問題を生成し、前記部分問題に対して割当候補となる複数の候補を生成し、前記複数の候補から最適な組み合わせを選択することにより前記部分問題に対する解である部分解を計算することにより、前記割当問題の解を計算する、
ように構成され、
前記計算機は、
前記部分解が前記割当問題の制約条件を充足しない場合、
前記問題区間において前記部分問題区間をずらすことにより、前記部分問題を作り直して再計算を行うことと、
前記部分問題の前記部分解を計算するときの前記制約条件を必要に応じて修正することと、
の少なくとも一方を実行する、
ように構成された、
割当問題処理システム。
続きを表示（約 3,000 文字）【請求項２】
請求項１に記載の割当問題処理システムにおいて、
前記計算機は、
前記部分解が前記割当問題の前記制約条件を充足しない場合、
前記問題区間において前記部分問題区間をずらすことにより、前記部分問題を作り直して再計算を行うことと、
前記部分問題の前記部分解を計算するときの前記制約条件を必要に応じて修正することと、
の両方を実行する、
ように構成された、
割当問題処理システム。
【請求項３】
請求項１に記載の割当問題処理システムにおいて、
前記計算機は、
前記部分解が前記割当問題の前記制約条件を充足しない場合、
前記問題区間において前記部分問題区間をずらすことにより、前記部分問題を作り直して再計算を行うことと、
前記部分問題の前記部分解を計算するときの前記制約条件を必要に応じて修正することと、
の何れか一方を実行する、
ように構成された、
割当問題処理システム。
【請求項４】
請求項２に記載の割当問題処理システムにおいて、
前記計算機は、
前記割当問題の問題区間における起点に基づいて前記部分問題を生成し、前記部分問題を解くたびに、前記起点をずらし、ずらした前記起点に基づいて次に解く前記部分問題を生成することを、前記割当問題の解に対応する全ての前記部分解に対して、前記制約条件を充足する解を得ることができるまで行うことにより、前記割当問題の解を計算する、
ように構成され、
前記計算機は、
前記部分解が前記制約条件を充足する場合、前記起点を前記問題区間の終点側にずらして次に解く前記部分問題を生成し、
前記部分解が前記制約条件を充足しない場合、前記起点を前記問題区間の始点側にずらして部分問題を作り直すことにより次に解く前記部分問題を生成する、
ように構成された、
割当問題処理システム。
【請求項５】
請求項２に記載の割当問題処理システムにおいて、
前記計算機は、
前記割当問題の問題区間における起点に基づいて前記部分問題を生成し、前記部分問題を解くたびに、前記起点をずらし、ずらした前記起点に基づいて次に解く前記部分問題を生成することを、前記割当問題の解に対応する全ての前記部分解に対して、前記制約条件を充足する解を得ることができるまで行うことにより、前記割当問題の解を計算するように構成され、
前記計算機は、
前記部分解が前記制約条件を充足する場合、前記起点を前記問題区間の終点側にずらして次に解く所定サイズの部分問題区間に対応する前記部分問題を生成し、
前記部分解が前記制約条件を充足しない場合、前記部分解が制約条件を充足しない前記部分問題を、前記起点を前記問題区間の始点側にずらして前記所定サイズの部分問題区間に対応する部分問題に作り直すことにより、次に解く前記部分問題を生成する、
ように構成された、
割当問題処理システム。
【請求項６】
請求項２に記載の割当問題処理システムにおいて、
前記計算機は、
前記割当問題の問題区間における起点に基づいて前記部分問題を生成し、前記部分問題を解くたびに、前記起点をずらし、ずらした前記起点に基づいて次に解く前記部分問題を生成することを、前記割当問題の解に対応する全ての前記部分解に対して、前記制約条件を充足する解を得ることができるまで行うことにより、前記割当問題の解を計算するように構成され、
前記計算機は、
前記部分解が前記制約条件を充足する場合、前記起点を前記問題区間の終点側にずらして次に解く所定サイズの部分問題区間に対応する前記部分問題を生成し、
前記部分解が前記制約条件を充足しない場合、前記部分解が制約条件を充足しない前記部分問題を、前記起点を前記問題区間の始点側にずらして前記所定サイズと異なるサイズの部分問題区間に対応する部分問題に作り直すことにより、次に解く前記部分問題を生成する、
ように構成された、
割当問題処理システム。
【請求項７】
請求項２に記載の割当問題処理システムにおいて、
前記計算機は、
前記割当問題の問題区間における起点に基づいて部分問題区間に対応する前記部分問題を生成し、前記部分問題を解くたびに、前記起点をずらし、ずらした前記起点に基づいて次に解く前記部分問題を生成することを、前記割当問題の解に対応する全ての前記部分解に対して、前記制約条件を充足する解を得ることができるまで行うことにより、前記割当問題の解を計算するように構成され、
前記計算機は、
前記部分解が前記制約条件を充足する場合、前記起点を前記問題区間の終点側にずらして次に解く所定サイズの部分問題区間に対応する前記部分問題を生成し、
前記部分解が前記制約条件を充足しない場合、前記部分解が制約条件を充足しない前記部分問題を、前記起点を前記問題区間の始点側にずらして前記所定サイズと異なるサイズの部分問題区間に対応する部分問題又は前記所定サイズの部分問題区間に対応する部分問題に作り直すことにより次に解く前記部分問題を生成し、
生成した前記部分問題の前記部分解が前記制約条件を充足しない場合、前記部分解が制約条件を充足しない前記部分問題を、前記起点をずらさないで、生成した前記部分問題のサイズとは異なるサイズの部分問題区間に対応する部分問題に作り直すことにより、次に解く前記部分問題を生成する、
ように構成された、
割当問題処理システム。
【請求項８】
請求項４に記載の割当問題処理システムにおいて、
前記計算機は、
各起点での前記部分問題の生成を行った回数を計算し、
前記回数が、所定の閾値回数以上になった場合、前記割当問題を解くことが困難と判定する、
ように構成された、
割当問題処理システム。
【請求項９】
請求項４に記載の割当問題処理システムにおいて、
難解な制約条件を示す情報が格納された記憶装置を備え、
前記計算機は、
前記難関な制約条件に基づいて、次に解く前記部分問題の前記制約条件が難解であるか否かを判定し、
次に解く前記部分問題の前記制約条件が難解であると判定した場合、前記難解な制約条件を示す情報に基づいて、前記次に解く部分問題に対応する前記制約条件が緩和するように、前記制約条件を修正する、
ように構成された、
割当問題処理システム。
【請求項１０】
請求項９に記載の割当問題処理システムにおいて、
前記計算機は、
前記部分問題を生成する場合に、前記割当問題の前記制約条件に基づいて、前記部分問題に対応する前記難解な制約条件を示す情報を作成し、前記記憶装置に格納する、
ように構成された、
割当問題処理システム。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明は、割当問題処理システム及び割当問題処理方法に関する。
続きを表示（約 1,900 文字）【背景技術】
【０００２】
社会システムの生産性向上のためアニーリング法が組合せ最適化問題の高速解法として注目を浴びている。交通系や配送・巡回経路決定などの実問題では多数の複雑な制約条件を加味する必要があり、特に勤務シフト作成や人員配置といったような割当問題は、所謂ＮＰ困難な問題に分類され、従来のコンピュータに基づくアルゴリズムでは、実用に耐えうる速度での計画の立案が困難であることが知られている。このため、割当計画立案の自動化へのシーズないしニーズが高まっていると考えられる。
【０００３】
本発明に関連する従来技術として、例えば、下記特許文献１及び特許文献２に記載の技術が挙げられる。特許文献１の技術は、集合分割問題における部分集合の候補の情報である候補情報を取得する取得手段と、前記取得手段により取得された前記候補情報に基づいて、前記集合分割問題に対応するイジングモデルにおけるハミルトニアンの式を生成する生成手段と、を有する。
【０００４】
特許文献２の技術は、集合分割問題の最適解を求める最適化システムを、集合分割問題を双対問題に変換し、双対問題の解を求め、双対問題の解を含み２値変数により表される列生成子問題を作成し、列生成子問題を求解する。特許文献２の技術は、列生成子問題の解に収束条件を満たさない解が含まれる場合、当該列生成子問題の解を部分集合の候補として部分集合族に追加し、列生成子問題の解に収束条件を満たさない解が含まれなくなるまで列生成子問題の生成および求解を繰り返す。
【先行技術文献】
【特許文献】
【０００５】
特開２０１７－１５１８１０号公報
特開２０２１－４３６９３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本願発明者等は、鋭意研究を行い、上述した割当計画立案は、「最適化問題」として計算機で解くことができるとの知見ないしコンセプトのもと、以下のように行うことを検討している。
【０００７】
すなわち、実社会の大規模な最適化問題を高速で解くには、例えばイジングモデルなどの「相互作用モデル」で問題を記述し、ＣＭＯＳアニーリングのような「最適化問題専用計算技術」を用いて計算を実行する方法が考えられる。相互作用モデルを用いて計画立案を行うにあたり、複雑な制約条件を効率的に扱う方法として、割当問題を所定の固定サイズで複数の部分問題に分割し、列生成法等を用いて部分問題の候補生成を行った後に、集合分割問題や集合被覆問題を解く手段を用いることを検討した。この手段では、部分問題を順次解いていき、ある部分問題で制約充足しない解がでた場合、その前に解いた部分問題に戻るループを、部分制約を満たすまで計算することを行う。
【０００８】
しかし、この手段により大規模な割当問題を処理すると、ある部分問題で制約充足しない解がでた場合にその前に解いた部分問題に戻るループを行ったとしても、必ずしも部分制約を満たすことができるとは限らないので、部分問題の解が制約充足困難で計算が終了しなくなってしまうことが生じ得る。
【０００９】
本発明は上記課題を解決するためにされた。即ち、本発明の目的の一つは、部分問題に分解した際に制約充足困難で計算が終了しなくなる問題を解消することで、大規模の割当問題を処理可能にする割当問題処理システム及び割当問題処理方法を提供することにある。
【課題を解決するための手段】
【００１０】
上記課題を解決するために、本発明の割当問題処理システムは、割当問題を処理する計算機を含む割当問題処理システムであって、前記計算機は、前記割当問題の問題区間の部分区間である部分問題区間に対応する部分問題を生成し、前記部分問題に対して割当候補となる複数の候補を生成し、前記複数の候補から最適な組み合わせを選択することにより前記部分問題に対する解である部分解を計算することにより、前記割当問題の解を計算するように構成され、前記計算機は、前記部分解が前記割当問題の制約条件を充足しない場合、前記問題区間において前記部分問題区間をずらすことにより、前記部分問題を作り直して再計算を行うことと、前記部分問題の前記部分解を計算するときの前記制約条件を必要に応じて修正することと、の少なくとも一方を実行するように構成される。
（【００１１】以降は省略されています）

関連特許