特許
J-GLOBAL ID：202103011038248327
鋼材の山分け計画作成装置、鋼材の山分け計画作成方法、およびプログラム
発明者：
出願人/特許権者：
代理人 (1件)：
國分 孝悦
公報種別：特許公報
出願番号（国際出願番号）：特願2018-073916
公開番号（公開出願番号）：特開2019-185303
特許番号：特許第6954218号
出願日： 2018年04月06日
公開日（公表日）： 2019年10月24日
請求項（抜粋）：
【請求項1】 鉄鋼プロセスにおける工程間の置場として鋼材を配置するヤードに搬入される複数の鋼材を、所定の山積み制約を満たすように山積みして、次工程に払い出す最終的な山姿となった複数の払出山に山分けするための山分け計画を作成する問題を集合分割問題とし、当該集合分割問題を、列生成法を用いて解くことにより山分け計画を作成する鋼材の山分け計画作成装置であって、
前記鋼材を、前記山積み制約を満たす様に積んだ山である複数の実現可能山のそれぞれについて、当該実現可能山を解として採用する場合に「1」となり、当該実現可能山を解として採用しない場合に「0」となる0-1変数を決定変数として、当該実現可能山に対する前記鋼材の山立てについての評価値である列コストと、初期解として与えられた実現可能山の集合とを用いて、前記決定変数および前記列コストを含む目的関数の値が最小または最大になる前記決定変数を求めることにより、前記複数の鋼材を重複することなく且つ漏れなく含む前記実現可能山の最適な組み合わせを求める問題を原問題とし、
前記原問題の線形緩和問題を主問題とした場合の双対問題の最適解である双対解を導出する双対解導出手段と、
前記原問題の最適解を構成する実現可能山の候補である候補山を生成する列生成子問題の最適解を導出する列生成手段と、
前記列生成手段により導出された前記候補山が、収束要件を満足するか否かの判定である列判定を行う列判定手段と、
前記列判定手段により、前記列生成手段により導出された前記候補山が、前記収束要件を満足しないと判定されると、前記列生成手段により生成された前記候補山を前記実現可能山の集合に追加する列追加手段と、
前記列判定手段により、前記列生成手段により導出された前記候補山が、前記収束要件を満足すると判定されると、その時点で前記双対解導出手段により導出されている前記双対解である双対最適解と、当該双対最適解が得られたときの当該双対問題の目的関数の値である双対最適値とを取得する双対最適解・最適値取得手段と、
前記実現可能山を新たに抽出するための条件である閾値および仮想最適値であって、前記実現可能山ごとの評価値に対して設定される閾値の初期値と、抽出された当該実現可能山の前記原問題の最適解としての適否を判定する指標となる値である仮想最適値の初期値とを、前記双対最適値に基づいて設定する閾値・仮想最適値設定手段と、
前記閾値と前記実現可能山ごとの評価値とを用いて表現される列列挙条件を満たす前記実現可能山を抽出する最適列抽出手段と、
前記最適列抽出手段により抽出された前記実現可能山の集合に対する前記原問題の部分問題を解くことにより、前記複数の鋼材を重複することなく且つ漏れなく含む前記実現可能山の最適な組み合わせと、そのときの当該部分問題の目的関数の値である部分問題の最適値とを導出する部分問題最適値導出手段と、
前記部分問題最適値導出手段により前記部分問題の実行可能な解が導出されたか否かを判定する実行可能解有無判定手段と、
前記実行可能解有無判定手段により、前記部分問題の実行可能な解が導出されたと判定されると、前記部分問題最適値導出手段により導出された前記部分問題の最適値と、前記仮想最適値の現在値とに基づいて、前記部分問題の最適値が前記原問題の最適値となるか否かの判定である最適値判定を行う最適値判定手段と、
前記実行可能解有無判定手段により、前記部分問題の実行可能な解が導出されなかったと判定された場合と、前記最適値判定手段により、前記部分問題の最適値が前記原問題の最適値にならないと判定された場合に、前記閾値の現在値と前記仮想最適値の現在値とを更新する閾値・仮想最適値更新手段と、
前記最適値判定手段により、前記部分問題の最適値が前記原問題の最適値になると判定されると、当該部分問題の最適値に対応する前記実現可能山の組み合わせを示す情報を、前記原問題の最適解を示す情報として出力する出力手段と、を有し、
前記列判定手段は、前記双対解導出手段による前記双対解の導出と、前記列生成手段による前記列生成子問題の最適解の導出と、前記列判定と、前記列追加手段による前記候補山の追加と、を繰り返す収束計算を、前記収束要件を満足すると判定するまで実行し、
前記列生成子問題は、前記双対解と、前記山積み制約とを用いて、前記実現可能山の集合に追加する前記候補山を求める問題であり、
前記実現可能山ごとの評価値は、前記原問題の最適解と前記双対最適解との差を前記実現可能山ごとに評価した値であり、
前記最適列抽出手段による前記実現可能山の抽出と、前記部分問題最適値導出手段による前記部分問題の最適値の導出と、前記実行可能解有無判定手段による前記判定と、前記最適値判定とを繰り返す計算は、前記最適値判定手段により、前記部分問題の最適値が前記原問題の最適値となると判定されるまで実行され、
前記部分問題は、前記列コストと、前記最適列抽出手段により抽出された前記実現可能山の集合とを用いて、前記決定変数および前記列コストを含む前記目的関数の値が最小または最大になるときの前記決定変数を求める問題であることを特徴とする鋼材の山分け計画作成装置。
IPC (2件)：
G05B 19/418 ( 200 6.01)
, G06F 17/10 ( 200 6.01)
G05B 19/418 Z
, G06F 17/10 Z
