(57)【特許請求の範囲】
【請求項１】
処理データを格納する格納手段と、最適値を格納する最適値格納手段とを備え、遺伝的アルゴリズムを用いて積み付け対象物を所定の積付高さ目標を有する積付エリアに積み付けるための３次元積み付けスケジューリングを行う積付スケジューリング装置であって、
前記積み付け対象物の縦方向長さ、横方向長さ及び高さで規定される荷姿および該荷姿の重心位置に関する荷姿情報、評価関数のパラメータ、繰り返す世代交代の所定の回数、積付エリアに関するエリア情報を含むデータを入力して前記格納手段に格納する入力手段と、
前記荷姿情報に基づいて、前記積付エリア内の固定的な部分エリアに配置する荷姿および前記部分エリアを決定して前記格納手段に格納する前処理手段と、
前記格納手段に格納された、前記積み付け対象物の縦方向長さ、横方向長さ及び高さで規定される荷姿を同種の遺伝子として表現し、積み付ける全ての荷姿に対応する遺伝子を１次元に配列して複数の荷姿により構成される個体を染色体として表現し、遺伝子の配列順序の異なる複数の染色体を作成して前記格納手段に格納する初期個体群作成手段と、
前記格納手段に格納された、それぞれの前記染色体である遺伝子配列の１次元配列順に基づいて、それぞれの遺伝子に対応する前記荷姿の高さを順次加算し、前記荷姿の高さの加算値が前記所定の積付高さ目標値に達する毎に前記遺伝子配列を分割し、該分割された遺伝子配列毎にその中に含まれる荷姿をその底面積または重量の降順に並べ替えた配列である柱を形成し順次前記格納手段に格納する柱形成手段と、
前記格納手段に格納された柱を前記積付エリアの行毎に所定のルールに基づいて、すなわち該所定のルールは、前記積付エリアの同一行に配置される柱の縦方向の長さの差が所定値以下であって、かつ横方向の柱の長さの和と前記積付エリアの行方向の長さとの差が所定値以下であるように順次配置する柱を選択するか、あるいは空き面積率が小さくなるように順次配置する柱を選択して、前記積付エリアに配置する位置を決定する柱配置手段と、
前記柱配置手段により所定の積付高さ目標を有する積付エリアに３次元的に積み付けられた荷姿がどの程度前記積付エリアに適して配置されているかを前記入力手段で入力された評価関数のパラメータにより決定される評価関数を用いて評価し、そのうち最も評価の高い染色体の評価値と前記最適値格納手段に格納されている染色体の評価値を比較し、評価値の高い方の染色体を前記最適値格納手段に格納する評価手段と、
前記最適値格納手段に格納された染色体を基に少なくとも２つの前記染色体間で遺伝子配列を交叉すること、または、一つの前記染色体内で少なくとも二つの遺伝子の配列位置を入れ替えて該染色体における遺伝子配列を変えること、または、前記評価手段による評価に基づいて前記染色体を削除すること、により次世代の染色体群を作成し前記格納手段に格納する次世代個体群作成手段と、
を備え、
前記柱形成手段による柱の生成、前記柱配置手段による柱配置、前記評価手段による評価と最適値の前記最適値格納手段への格納を、前記次世代個体群作成手段による世代交代が所定回数繰り返されるまで繰り返し、
さらに、前記格納手段に格納された前記荷姿情報を用いて、前記最適値格納手段に格納された所定回数だけ世代交代が繰り返された柱配置で且つ評価された柱を、縦向きに配置された柱同士と横向きに配置された柱同士が隣接するように並び替える後処理手段と、
該後処理手段により並び替えが行なわれた前記積付エリア内に積み付けられた柱を３次元表示する出力手段と、
を備えることを特徴とする積付スケジューリング装置。
【請求項２】
前記出力手段は、前記入力手段により入力されたデータ、およびまたは、前記評価手段により評価された評価結果を出力することを特徴とする請求項１に記載の積付スケジューリング装置。
【請求項３】
前記柱形成手段は、前記積付エリアを複数の仮想積付空間に分け、各仮想積付空間毎に柱を形成し、前記柱配置手段は、前記仮想積付空間の全てにおいて形成された全柱を配置することを特徴とする請求項１に記載の積付スケジューリング装置。
【請求項４】
遺伝的アルゴリズムを用いて積み付け対象物を所定の積付高さ目標を有する積付エリアに積み付けるための３次元積付スケジューリングを、処理データを格納する格納手段と、最適値を格納する最適値格納手段を備える情報処理装置において実行するための方法であって、
入力手段が、前記積み付け対象物の縦方向長さ、横方向長さ及び高さで規定される荷姿及び該荷姿の重心位置に関する荷姿情報、評価関数のパラメータ、繰り返す世代交代の所定の回数、積付エリアに関するエリア情報を含むデータを入力し、入力した結果を前記格納手段に格納する入力ステップと、
前処理手段が、前記格納手段に格納された、前記荷姿情報および前記積付エリアに関するエリア情報を用いて、前記積付エリア内の固定的な部分エリアに配置する荷姿および前記部分エリアを決定して前記格納手段に格納する前処理ステップと、
初期個体群作成手段が、前記格納手段に格納された、前記積み付け対象物の縦方向長さ、横方向長さ及び高さで規定される荷姿を同種の遺伝子として表現し、積み付ける全ての荷姿に対応する遺伝子を１次元に配列して複数の荷姿により構成される個体を染色体として表現し、遺伝子の配列順序の異なる複数の染色体を作成して前記格納手段に格納する初期個体群作成ステップと、
柱形成手段が、前記格納手段に格納された、それぞれの前記染色体である遺伝子配列の１次元配列順に基づいて、それぞれの遺伝子に対応する前記荷姿の高さを順次加算し、前記荷姿の高さの加算値が前記所定の積付高さ目標値に達する毎に前記遺伝子配列を分割し、該分割された遺伝子配列毎にその中に含まれる荷姿をその底面積または重量の降順に並べ替えた配列である柱を形成し順次前記格納手段に格納する柱形成ステップと、
柱配置手段が、前記格納手段に格納された柱を前記積付エリアの行毎に所定のルールに基づいて、すなわち該所定のルールは、前記積付エリアの同一行に配置される柱の縦方向の長さの差が所定値以下であって、かつ横方向の柱の長さの和と前記積付エリアの行方向の長さとの差が所定値以下であるように順次配置する柱を選択するか、あるいは空き面積率が小さくなるように順次配置する柱を選択して、前記積付エリアに配置する位置を決定する柱配置ステップと、
評価手段が、前記柱配置ステップにより所定の積付高さ目標を有する積付エリアに３次元的に積み付けられた荷姿がどの程度前記積付エリアに適して配置されているかを前記入力ステップで入力された評価関数のパラメータにより決定される評価関数を用いて評価し、そのうち最も評価の高い染色体の評価値と前記最適値格納手段に格納されている染色体の評価値を比較し、評価値の高い方の染色体を前記最適値格納手段に格納する評価ステップと、
次世代個体群作成手段が、前記最適値格納手段に格納された染色体を基に少なくとも２つの前記染色体間で遺伝子配列を交叉すること、または、一つの前記染色体内で少なくとも二つの遺伝子の配列位置を入れ替えて該染色体における遺伝子配列を変えること、または、前記評価ステップによる評価に基づいて前記染色体を削除すること、により次世代の染色体群を作成し前記格納手段に格納する次世代個体群作成ステップと、
前記柱形成ステップによる柱の生成、前記柱配置ステップによる柱配置、前記評価ステップによる評価と最適値の前記最適値格納手段への格納を、前記次世代個体群作成ステップによる世代交代が所定回数繰り返されるまで繰り返すステップと、
後処理手段が、前記格納手段に格納された前記荷姿情報を用いて、前記最適値格納手段に格納された所定回数だけ世代交代が繰り返された柱配置で且つ評価された柱を、縦向きに配置された柱同士と横向きに配置された柱同士が隣接するように並び替える後処理ステップと、
出力手段が、前記後処理ステップにより並び替えが行なわれた前記積付エリア内に積み付けられた柱を３次元表示する出力ステップと、
を含む方法。
【請求項５】
前記出力手段により実行される出力ステップは、前記入力手段により実行される入力ステップにより入力されたデータ、およびまたは、前記評価手段により実行される評価ステップにより評価された評価結果を出力することを特徴とする請求項４に記載の方法。
【請求項６】
前記柱形成手段により実行される柱形成ステップは、前記積付エリアを複数の仮想積付空間に分け、各仮想積付空間毎に柱を形成し、前記柱配置手段により実行される柱配置ステップは、前記仮想積付空間の全てにおいて形成された全柱を配置することを特徴とする請求項４に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、サイズの異なる複数の荷姿を限られた容積に３次元的に積み付ける際に、積付制約条件を守りつつ積載量や、移動空間（トラックの荷台）などにおける荷崩れしにくさなどを最大にする積付パターンをスケジューリングする積付スケジューリング装置および方法に関し、特に、最適化問題の解候補を生命の染色体である遺伝子配列に見立てて表現し、染色体の問題適応度によって自然淘汰や、遺伝子配列操作を繰り返すことによって、最適解を探索する遺伝的アルゴリズムを用いた積付スケジューリング装置および方法に関する。
【０００２】
【従来の技術】
近年、売上の減少など経営環境が厳しくなる中、物流分野にメスを入れ、コスト削減を進める動きが活発である。事業活動全体における物の流れをコンピュータにより総合的に管理し、在庫削減・配送効率向上などを進めるといった物流分野への情報化投資や、物流拠点の再構築といった物流投資が行われている。大半の企業は、調達・生産・販売・回収物流のいずれかに関わっており、大きなニーズが存在すると考えられる。ある統計によれば、物流分野への機械化・情報化の投資額は年間４０００億円ほど、そのうち情報化への投資比率は、１０％前後と言われている。
【０００３】
従来、倉庫や製品を移動用のパレットへ積み付けるスケジューリングとして、以下のような従来技術が存在していた。
第１の従来技術は、熟練したオペレータが経験的な勘あるいはノウハウに基づき、積付パターンを決定していた。
【０００４】
第１の従来技術の場合、オペレータの熟練度が不十分であると、積付に不慣れなため積載効率が悪くなることがあった。また、熟練者であっても積み付ける製品の種類と数量が膨大になってくると、必ずしも最適な積付パターンを決定することはできないことがあった。さらに、製品別の積付数量がコンピュータにより電子データで管理されている場合は、オペレータの作業が入ることにより、一貫した電子データ管理が分断されてしまうことがあった。つまり、データ入力といった人手の作業が入ることにより、データの不整合が生じることがあった。
【０００５】
第２の従来技術は、積み付けるルールを詳細に決定し、ロジックに基づきスケジュールを行っていた。
第２の従来技術の場合、積付数量や荷姿により、積付ルールを規定する必要があった。しかしながら、積付ルールを基にロジックにより積付パターンを決定するため、ルール通り積み付けられるが、積付パターンが固定されるために積載効率や、荷崩れしにくさが最大である事は保証されていない。また、常に積載効率や、荷崩れしにくさが最大になるように積み付けルールを詳細に決めるのは事実上不可能であった。さらに、固定ロジックであるため積付パターンの変更や荷姿の増加が非常に難しかった。
【０００６】
第３の従来技術は、人工知能（ＡＩ）による手法を用いてスケジュールを行っていた。
第３の従来技術であるＡＩ手法を用いた積付スケジュールは、予め複数の積付ルールを用意し、積付ルールを組み合わせることにより、希望の積付パターンを実現するという点では、第２の従来技術のよる手法よりも積付パターンの自由度が増している。しかし、積付ルールを選択し、組み合わせる作業が複雑であり、オペレータでは作業が難しいという欠点があった。また、積付方向が一定方向しか積付できなかったり、新規の荷姿を登録する作業が難しいという欠点もあった。
【０００７】
積付パターンを個々の荷姿の組合せと考え、組合せ問題の( 準) 最適解を求める事により、最適な積付パターンを求めることが考えられる。このように全ての組み合わせを検証することにより最適解は得られるが、時間的な制約から良い手法とは言えない。
【０００８】
そこで、遺伝的アルゴリズム（ＧＡ：Genetic Algorithm ）を用いて、準最適解を求めることにより、積付パターンを決定することが考えられる。
特開平９−１９０４８３号公報には、遺伝的アルゴリズムを用いた「製品積載計画装置」が開示されている。しかし、このスケジューリング機能は、目標重量からの偏差や重心位置を最適にするよう、２次元的に積付パターンを決定するものであり、３次元的（製品を積み重ねる）に積付を行うものには対応していない。
【０００９】
【発明が解決しようとする課題】
第１の課題としては、オペレータの熟練度が不十分であると、積付に不慣れなため積載効率が悪くなったり、積載効率と荷崩れしにくさを両立させることが難しかったりすることがあった。また、熟練者であっても積み付ける製品の種類と数量が膨大になってくると、必ずしも最適な積付パターンを決定することはできないことがあった。さらに、製品別の積付数量がコンピュータにより電子データで管理されている場合は、オペレータの作業が入ることにより、一貫した電子データ管理が分断されてしまうことがあった。つまり、データ入力といった人手の作業が入ることにより、データの不整合が生じることがあった。
【００１０】
第２の課題としては、積付数量や荷姿により、積付ルールを規定する必要があり、また、常に積載効率が最大になるように積み付けたり、積載効率と荷崩れしにくさを両立させるルールを詳細に決めるのは事実上不可能であった。さらに、固定ロジックであるため積付パターンの変更や荷姿の増加が非常に難しかった。
【００１１】
第３の課題としては、積付ルールを選択し、組み合わせる作業が複雑であり、オペレータでは作業が難しいという欠点があった。また、積付方向が一定方向しか積付できなかったり、新規の荷姿を登録する作業が難しいという欠点もあった。
【００１２】
さらに、遺伝的アルゴリズムを用いて、準最適解を求めることにより、積付パターンを決定する特開平９−１９０４８３号公報の「製品積載計画装置」は、目標重量からの偏差や重心位置を最適にするよう、２次元的に積付パターンを決定するものであり、３次元的（製品を積み重ねる）に積付を行うものには対応していなかった。
【００１３】
本発明の目的は、サイズの異なる複数の荷姿（製品）を限られたスペースのパレット等へ３次元的に積み付ける際、積付ルールの重要度の変更や、積付ルールの追加を容易に行うことにより、固定空間（倉庫等）や移動空間（トラックの荷台等）に対して、自由度の高い積付パターンのスケジューリングを可能とする積付スケジューリング装置および方法を提供することである。
【００１４】
【課題を解決するための手段】
本発明は、上記課題を解決するため、下記のような構成を採用した。すなわち、本発明の一態様によれば、本発明の積付スケジューリング装置は、処理データを格納する格納手段と、最適値を格納する最適値格納手段とを備え、遺伝的アルゴリズムを用いた積み付けスケジューリングを行う積付スケジューリング装置であって、同種の荷姿を同種の遺伝子として表現し、積み付ける全ての荷姿に対応する遺伝子をそれぞれ配列して、複数の荷姿により構成される個体を染色体として表現し、遺伝子の配列順序の異なる複数の染色体を作成し、前記格納手段に格納する初期個体群作成手段と、少なくとも２つの前記染色体間で遺伝子配列を交叉すること、または、一つの前記染色体内で少なくとも二つの遺伝子の配列位置を入れ替えて該染色体における遺伝子配列を変えること、または、評価に基づいて前記染色体を削除すること、により次世代の染色体群を作成し前記格納手段に格納する次世代個体群作成手段と、前記格納手段に格納された、それぞれの前記染色体である遺伝子配列の遺伝子順に基づいて、それぞれの遺伝子に対応する前記荷姿を順次積み付けし、前記荷姿の高さの加算値が所定値に達する毎に分割し、該荷姿の底面積または重量の降順に荷姿を積重ねて柱を形成し前記格納手段に格納する柱形成手段と、前記格納手段に格納された柱を順次所定のルールに基づいて積付エリアに配置する柱配置手段と、前記柱配置手段により積み付けられた荷姿がどの程度前記積付エリアに適して配置されているかを評価関数を用いて評価し、最適値の染色体を前記最適値格納手段に格納する評価手段と、を備える。
【００１５】
これにより、サイズの異なる複数の荷姿を限られた積付エリアへ積み付ける際、積み付けを制約する条件を守りつつ積付量や、移動空間（トラックの荷台等）などにおける荷崩れしにくさなどを最大または最適にスケジューリングすることができる。
【００１７】
また、好適には、本発明の積付スケジューリング装置は、さらに、積み付ける荷姿に関する荷姿情報、前記評価関数のパラメータ、繰り返す世代交代の数、積付エリアに関するエリア情報を含むデータを入力する入力手段と、重心位置情報を含む前記荷姿情報に基づいて、前記積付エリア内の固定的な部分エリアに配置する第１の荷姿および前記部分エリアを決定する前処理手段と、高さ情報を含む前記荷姿情報に基づいて、前記柱を構成する各荷姿を荷崩れしないように並び替える後処理手段と、前記入力手段により入力されたデータ、前記評価手段により評価された評価結果を出力する出力手段とを備えることが望ましい。
【００１８】
また、好適には、本発明の積付スケジューリング装置は、上記出力手段が、上記積付エリア内に積み付けられた荷姿を３次元表示することが望ましい。また、好適には、本発明の積付スケジューリング装置は、上記柱形成手段が、上記積付エリアを複数の仮想積付空間に分け、各仮想積付空間毎に柱を形成し、上記柱配置手段が、上記仮想積付空間の全てにおいて形成された全柱を配置することが望ましい。
【００１９】
すなわち、本発明の一態様によれば、本発明の積付スケジューリング方法は、遺伝的アルゴリズムを用いた積付スケジューリングを、処理データを格納する格納手段と、最適値を格納する最適値格納手段を備える情報処理装置において実行するための方法であって、
同種の荷姿を同種の遺伝子として表現し、積み付ける全ての荷姿に対応する遺伝子をそれぞれ配列して、複数の荷姿により構成される個体を染色体として表現し、遺伝子の配列順序の異なる複数の染色体を作成し、前記格納手段に格納する初期個体群作成ステップと、
少なくとも２つの前記染色体間で遺伝子配列を交叉すること、または、一つの前記染色体内で少なくとも二つの遺伝子の配列位置を入れ替えて該染色体における遺伝子配列を変えること、または、評価に基づいて前記染色体を削除すること、により次世代の染色体群を作成し前記格納手段に格納する次世代個体群作成ステップと、
前記格納手段に格納された、それぞれの前記染色体である遺伝子配列の遺伝子順に基づいて、それぞれの遺伝子に対応する前記荷姿を順次積み付けし、前記荷姿の高さの加算値が所定値に達する毎に分割し、該荷姿の底面積または重量の降順に荷姿を積重ねて柱を形成し前記格納手段に格納する柱形成ステップと、
前記柱を所定のルールに基づいて積付エリアに配置する柱配置ステップと、
前記柱配置ステップにより積み付けられた荷姿がどの程度前記積付エリアに適して配置されているかを評価関数を用いて評価し、最適値の染色体を前記最適値格納手段に格納する評価ステップと、
を含む。
【００２０】
これにより、サイズの異なる複数の荷姿を限られた積付エリアへ積み付ける際、積み付けを制約する条件を守りつつ積付量や、移動空間（トラックの荷台等）などにおける荷崩れしにくさなどを最大または最適にスケジューリングすることができる。
【００２２】
また、好適には、本発明の積付スケジューリング方法は、さらに、積み付ける荷姿に関する荷姿情報、前記評価関数のパラメータ、繰り返す世代交代の数、積付エリアに関するエリア情報を含むデータを入力する入力ステップと、前記入力ステップにより入力されたデータ、前記評価ステップにより評価された評価結果を出力する出力ステップとを備えることが望ましい。
【００２３】
また、好適には、本発明の積付スケジューリング方法は、上記出力ステップが、上記積付エリア内に積み付けられた荷姿を３次元表示することが望ましい。また、好適には、本発明の積付スケジューリング方法は、上記柱形成ステップが、上記積付エリアを複数の仮想積付空間に分け、各仮想積付空間毎に柱を形成し、上記柱配置ステップが、上記仮想積付空間の全てにおいて形成された全柱を配置することが望ましい。
【００２４】
【発明の実施の形態】
以下、本発明の実施の形態を、図面を参照しながら詳細に説明する。
また、以下の説明においては特に指定のない限り、固定空間（倉庫等）と移動空間（トラックの荷台等）の両方を同時に説明している。
【００２５】
図１は、本発明の実施の形態における積付スケジューリング装置の機能構成図である。
本実施の形態における積付スケジューリング装置は、積み付ける荷姿を遺伝子として表現し、複数の荷姿により構成される個体を遺伝子が配列している染色体として表現し、前記染色体が自然淘汰により世代交代を繰り返すことで最適な遺伝子を探索する遺伝的アルゴリズムを用いる。
【００２６】
遺伝的アルゴリズムとは、生物の遺伝機構を模倣したアルゴリズムであり、特に、生物の遺伝機構のうち進化・適応にかかわる部分に着目したものである。
生物の進化・適応は、既存の個体（親）から新たな個体（子）が生まれる際に個体の持つ染色体間の交叉や、染色体を構成する遺伝子の突然変異などが発生し、その結果、環境に適応した染色体を持つ個体が生き延びて次世代の親となり、環境に適応しない個体は淘汰されるという考えの特徴を問題の解探索に応用したものである。すなわち、解を染色体（遺伝子の一次元ストリングス）と見立てて表現して解候補となる染色体集団を形成し、自己複製、交叉、突然変異等の操作を繰り返し施して多様な染色体（解候補）を形成すると共に、淘汰、選択等の操作により解候補のいくつかを残して他は捨てて最適解の探索を行うものである。
【００２７】
ここで、環境に相当するものが目的関数または評価関数であり、目的関数を最適にするものほど大きな値を採るように評価関数が染色体に対して定義される。そして、この評価関数を用いて、解集団の中で高い適応度の染色体をより高い確率で選択・自己複製するものである。
【００２８】
また、交叉は、これらの染色体集団から２つの染色体を選択して、その遺伝子を互いに入れ替える操作であり、例えば、任意の同じ長さの遺伝子配列を染色体から切取り、お互いの遺伝子配列を入れ替えて染色体に連結し、新たな染色体を作成する一点交叉など、様々な遺伝子の交叉方法がある。
【００２９】
さらに、突然変異は、任意の染色体の任意の遺伝子座にある遺伝子を別の遺伝子にランダムに変異させるものである。
そして、遺伝的アルゴリズムは、これらの操作の繰り返しにより多様な染色体を発生させ、目的関数値からより最適な解を得ようとするものである。
【００３０】
図１において、積付スケジューリング装置１は、入力部１０と、前処理部１５と、初期個体群作成部２０と、積付部３０と、評価部４０と、最適値格納部５０と、後処理部５５と、次世代個体群作成部６０と、出力部７０とを備える。
【００３１】
入力部１０は、積み付ける荷姿に関する荷姿情報、評価関数のパラメータ、繰り返す世代交代の数、積付エリアに関するエリア情報を含むデータを入力する。前処理部１５は、重心位置情報を含む上記荷姿情報に基づいて、上記積付エリア内の固定的な部分エリアに配置する第１の荷姿および上記部分エリアを決定する。初期個体群作成部２０は、同種の荷姿を同種の遺伝子として表現し、積み付ける全ての荷姿を配列した個体として、配列順序の異なる複数の個体を作成する。
【００３２】
図２は、荷姿と遺伝子との関係および個体と染色体との関係を説明するための図であり、同種の荷姿（（ｂ）の１、２、３）を同種の遺伝子（（ａ）の１、２、３、…、Ｘ）として表現している。
【００３３】
図１の説明に戻り、積付部３０は、個体を分割して１つ以上の柱を形成し、柱を積付エリアに配置する。評価部４０は、積付部３０により積み付けられた荷姿がどの程度積付エリアに適して配置されているか（固定空間（倉庫等）であれば容積率、移動空間（トラックの荷台等）であれば積載効率と荷崩れしにくさなど）を評価関数を用いて評価する。
【００３４】
図３は、積み付けを行なう際の積付ルールの一例であり、図４および図５は、評価関数の各パラメータ設定画面の一例であり、上記評価は、これらの積付ルールやパラメータを用いた評価関数を用いる。
【００３５】
図１の説明に戻り、最適値格納部５０は、評価部４０による評価結果が最も高い個体と既に格納されている個体のうち評価結果の高い方を格納する。後処理部５５は、高さ情報を含む上記荷姿情報に基づいて、上記柱を構成する各荷姿を荷崩れしないように並び替える。次世代個体群作成部６０は、個体を構成する荷姿の配列を変え、次世代の個体を作成する。出力部７０は、入力部１０により入力されたデータ、評価部４０により評価された評価結果を出力する。
【００３６】
また、積付部３０は、柱形成部３１と、柱配置部３２とを備える。
柱形成部３１は、荷姿の高さの加算値が所定値に達する毎に分割し、底面積または重量の降順に荷姿を積重ねて柱を形成する。なお、荷姿としては同一であっても中身（商品）が異なる場合もあるが、その場合は、伝票の番号順に並べたり、同一商品をまとめて出荷量の多い順に並べることも可能である。
柱配置部３２は、柱を所定のルールに基づいて配置する。
【００３７】
また、次世代個体群作成部６０は、選択部６１と、交叉部６２と、突然変異部６３とを備える。
選択部６１は、評価部４０による評価結果の低い個体を削除し、評価結果の高い個体を選択する。交叉部６２は、少なくとも２つの個体間で荷姿の配列を交叉する。交叉の対象とされる個体は、例えば、評価部４０による評価結果の高い個体ほど、その確率を高くする。突然変異部６３は、１つの個体内で少なくとも２つの荷姿の配列位置を入れ替える。
【００３８】
また、出力部７０は、積付エリア内に積み付けられた荷姿を３次元表示することも可能である。
また、柱形成部３１は、積付エリアを複数の仮想積付空間に分け、各仮想積付空間毎に柱を形成し、柱配置部３２は、仮想積付空間の全てにおいて形成された全柱を配置することも可能である。
【００３９】
図６は、図１を用いて説明した初期個体群作成部２０が作成した複数の個体を説明するための図である。
図６において、荷姿の種類として荷姿区分１、２、３、…、Ｘがあり、荷姿区分１の荷姿が４個、荷姿区分２の荷姿が３個、荷姿区分３の荷姿が２個を含んでいる積付対象荷姿から、個体１、個体２、個体３、個体４等のｎ個の個体群が作成されている。個体１、個体２、個体３は、乱数を用いて荷姿の配列しており、個体４は、荷姿区分３、荷姿区分２、荷姿区分１の順に荷姿を配列している。
【００４０】
図７は、図１を用いて説明した柱形成部３１が行なう柱の形成を説明するための図である。
図７において、個体１は、左端の荷姿（荷姿区分３）から順に高さを加算していき、所定の積付目標高さを超えたところ（左端の荷姿区分３から３つ）で区切る。そして、区切られた荷姿区分３、荷姿区分２、荷姿区分３の３つの荷姿を大きい順（底面積または重量）に重ねて柱▲１▼を形成する。続いて、４つ目の荷姿から同様にして柱▲２▼を形成する。
【００４１】
図８は、図１を用いて説明した柱配置部３２が行なう柱の配置を説明するための図（その１）である。
図８において、図７で説明したようにして形成された柱▲１▼、柱▲２▼、柱▲３▼、柱▲５▼、柱▲７▼が、所定のルールに基づいて積付エリア内に配置される。柱の配置は、積み付けることのできる量が最大になるように、柱の位置や向き等が決定されるが、詳細については図１０乃至図１２を用いて後述する。
【００４２】
図９は、図１を用いて説明した評価部４０が用いる評価関数の一例である。図９において、評価値Ｑは、値Ｑ１と値Ｑ２と値Ｑ３と値Ｑ４との和から求められ、値Ｑ１は、複数種類の荷姿から構成される柱の数に重み付け値α１を乗じた値であり、値Ｑ２は、柱を構成することができない荷姿の組合わせ総数に重み付け値α２を乗じた値であり、値Ｑ３は、高さ制限のある荷姿（商品）の上に積まれる荷姿の総数に重み付け値α３を乗じた値であり、値Ｑ４は、端数がある場合の空き体積率に重み付け値α４を乗じた値である。なお、値Ｑ１〜Ｑ４の上記の説明から明らかなとおり、これらは評価の上でペナルティとなるものであるから、上記重み付け値ｑ１〜ｑ４は、負の値を取るものとする。
【００４３】
図１０は、図１を用いて説明した柱配置部３２が行なう柱の配置を説明するための図（その２）である。
図１０において、まず、柱▲１▼が積付エリアの１行１列目の位置に縦向きで配置され、次に、柱▲２▼が積付エリアの１行２列目の位置に縦向きで配置される。この時、柱▲１▼と柱▲２▼との１行内の幅の差Ａが、例えば、図５に示したパラメータ設定画面例で入力した１０ｍｍ以内であるかを判断し、１０ｍｍ以内であれば、柱▲３▼が積付エリアの１行３列目の位置に縦向きで配置される。この時、柱▲３▼が積付エリアからはみ出てしまうオーバーハング部分Ｂが、移動空間（トラックの荷台上のパレット等）での荷崩れを意識し、所定値以下であるかを判断する。
【００４４】
図１１は、図１を用いて説明した柱配置部３２が行なう柱の配置を説明するための図（その３）である。
図１１において、柱の配置を行なう際に、柱が縦向きでも横向きでも配置することが可能である場合は、配置した後の行単位における空き面積率の小さい方を選択する（この例では、縦方向の場合）。
【００４５】
図１２は、図１を用いて説明した柱配置部３２が行なう柱の配置を説明するための図（その４）である。
図１２において、積付エリアの１行目には、図１０および図１１で説明したような過程を経て、柱▲１▼、柱▲２▼、柱▲３▼が配置されている。続いて、柱▲４▼が積付エリアの２行１列目の位置に横向きで配置され、次に、柱▲５▼が積付エリアの２行２列目の位置（柱▲４▼の隣）に横向きで配置される。この時、柱▲５▼が積付エリアからはみ出てしまうオーバーハング部分が、移動空間（トラックの荷台上のパレット等）での荷崩れを意識し、所定値以下であるかを判断するが、この場合は、所定値以上と判断され、柱▲５▼を配置することはできない。そこで、次の柱である柱▲６▼を積付エリアの２行２列目の位置（柱▲４▼の隣）に横向きで配置し、柱▲５▼は、積付エリアの次の行である３行目に配置する。
【００４６】
図１３は、図１を用いて説明した選択部６１が行なう選択および交叉部６２が行なう交叉を説明するための図である。なお、図７乃至図１２を用いて説明してきたような柱の形成、柱の配置、個体の評価を、図６に示した個体群に適用した場合に、図６の各個体の評価結果として、個体１が−６０点、個体２が−２０点、個体３が−４０点、個体４が−１０点であるとして、図１３の説明を行なう。
【００４７】
図１３において、一番上の個体は、図６の個体２が選択され、同様に選択された図６の個体４（二番目の個体）と、それぞれの一部の配列が交叉されている。また、三番目の個体は、図６の個体３が選択され、同様に選択された図６の個体４（二番目の個体、二回目）と、それぞれの一部の配列が交叉されている。すなわち、最も低い評価結果であった図６の個体１は、選択されずに削除され、最も高い評価結果であった個体４は、２度選択され交叉の対象となったことになる。なお、交叉の対象となる配列をどの部分にするのかについては、例えば、ランダムに決定する。
【００４８】
図１４は、図１を用いて説明した突然変異部６３が行なう交叉を説明するための図である。
図１４において、一番上の個体は、図１３の一番上の交叉後の個体について、左から３番目の荷姿（荷姿区分３）と左から５番目の荷姿（荷姿区分２）とを入れ替えている。また、一番下の個体は、図１３の一番下の交叉後の個体について、左から４番目の荷姿（荷姿区分２）と左から９番目の荷姿（荷姿区分Ｘ）とを入れ替えている。なお、突然変異の対象となる荷姿をどれにするのかについては、例えば、ランダムに決定する。
【００４９】
図１５は、本発明の実施の形態における積付スケジューリング処理を示すフローチャートである。
図１５において、処理が開始されると、まずステップＳ０で、積み付ける荷姿に関する荷姿情報、評価関数のパラメータ、繰り返す世代交代の数、積付エリアに関するエリア情報を含むデータを入力する。ステップＳ１で、重心位置情報を含む上記荷姿情報に基づいて、上記積付エリア内の固定的な部分エリアに配置する第１の荷姿および上記部分エリアを決定する。ステップＳ２で、同種の荷姿を同種の遺伝子として表現し、積み付ける全ての荷姿を配列した個体として、配列順序の異なる複数の個体を作成する。ステップＳ３で、荷姿の高さの加算値が所定値に達する毎に個体を分割し、底面積または重量の降順に荷姿を積重ねて１つ以上の柱を形成する。ステップＳ４で、柱を所定のルールに基づいて積付エリアに配置する。ステップＳ５で、配置された荷姿がどの程度積付エリアに適して  （固定空間（倉庫等）であれば容積率、移動空間（トラックの荷台等）であれば積載効率と荷崩れのしにくさなどで）配置されているかを評価関数を用いて評価する。ステップＳ６で、評価結果が最も高い個体と既に格納されている個体のうち評価結果の高い方をメモリ等に格納する。このメモリに最終的に格納されている個体が最適な個体となる。
【００５０】
続いて、ステップＳ７で、ステップＳ０で入力した繰返し世代交代数に達したか否かを判断する。そして、ステップＳ０で入力した繰返し世代交代数に達したならば（ステップＳ７：ＹＥＳ）、ステップＳ１１で、高さ情報を含む前記荷姿情報に基づいて、前記柱を構成する各荷姿を荷崩れしないように並び替える。ステップＳ１２で、入力されたデータや評価された評価結果を表示したり、積付エリア内に積み付けられた荷姿を３次元表示し、終了する。また、ステップＳ０で入力した繰返し世代交代数に達していなければ（ステップＳ７：ＮＯ）、次のステップＳ８に移る。次のステップＳ８乃至ステップＳ１０では、個体を構成する荷姿の配列を変え、次世代の個体を作成する。具体的には、ステップＳ８で、評価結果の低い個体を削除し、評価結果の高い個体を選択する。ステップＳ９で、少なくとも２つの個体間で荷姿の配列を交叉する。交叉の対象とされる個体は、例えば、評価結果の高い個体ほど、その確率を高くする。ステップＳ１０で、１つの個体内で少なくとも２つの荷姿の配列位置を入れ替える。
【００５１】
その後、ステップＳ７で繰返し世代交代数に達したと判断されるまで、所定実行回数になるまで、ステップＳ３以降を繰り返す。
以上、本発明の実施の形態を、図面を参照しながら詳細に説明してきたが、積み付ける荷姿は、どの荷姿も固定的（決まった位置に決まった順序で積み付ける）でないことが前提であった。
【００５２】
図１６は、本発明の実施の形態の変形例を説明するための図である。
図１６において、斜線付きの直方体は、移動空間（トラックの荷台等）で、荷卸し順や移動中の荷物全体の重心位置、その荷物そのもののバランスなどのために、積付手順が固定的な荷姿を示しており、斜線なしの直方体は、積付手順が固定的でない荷姿を示している。このように、積付エリアに積付手順が固定的な荷姿と積付手順が固定的でない荷姿とを積み付けるには、まず、積付手順が固定的な荷姿を決まった位置に決まった順序で積み付け、その後に、残りの積付手順が固定的でない荷姿を、図１乃至図１５を用いて説明してきたようにして積み付ける。
【００５３】
図１７乃至図２２は、本発明の実施の形態の変形例を具体的に説明するための図（その１から６）である。
まず、図１７において、積付手順が固定的な荷姿の柱（柱１乃至６）が決まった位置に決まった順序で配置されている。そして、図１８において、積付手順が固定的な荷姿の柱が積み付けられた後に、残りの積付手順が固定的でない荷姿の柱を、図１乃至図１５を用いて説明してきたようにして配置する。
【００５４】
図１９においては、荷物を取出す場合の外側からの荷物の視認性を考慮して、幅の小さい柱が積付エリアの外側にくるように同一行内で並べ替えられており、図２０においては、移動空間（トラックの荷台等）での荷崩れのしにくさを考慮して、縦向き（長手）に配置された柱と横向き（短手）に配置された柱とが纏められている。また、図２１においては、さらに、移動空間（トラックの荷台等）での荷崩れのしにくさを考慮して、同じ向き（縦向きあるいは横向き）に纏めて配置されたグループ内において、行方向の長さが長い順に入れ替えられており、図２２においては、移動空間（トラックの荷台等）での荷崩れしにくさや、荷物取出し時の外側からの荷物の視認性を考慮して、同一柱において上段の荷姿と下段の荷姿との幅差が所定値を超えるような柱を、積付エリアの端（端の列）に移動している。
【００５５】
次に、本発明の積付スケジューリング装置を用いて、荷姿を積み付けた実施結果を説明する。
図２３は、積み付ける予定の荷姿の数量およびサイズを示した図表である。
【００５６】
図２３において、荷姿は、荷姿１乃至荷姿１４の１４種類があり、例えば、荷姿１は、数量が３０個で、サイズが縦３８１ｍｍ×横１９４ｍｍ×高さ３２２ｍｍの直方体である。
【００５７】
このような計３５１個の荷姿を、縦１１３０ｍｍ×横１６２０ｍｍのパレット３個に積み付けるとする。主な積付の条件としては、積付上限高さが１３００ｍｍ、同一行内での行幅差の許容値が１０ｍｍ、同一柱内における荷姿サイズ差の許容値が１０ｍｍ、同一号車内における柱の高低差許容値が２００ｍｍであるとし、遺伝的アルゴリズムにおける制約条件としては、同一荷姿を棒積みにする：０．０、大小判別可能荷姿を棒積みにする：５０．０、積載効率を上げる（端数荷姿を減らす）：９９９．０、高低差を守る：５．０であるとする。
【００５８】
図２４乃至図２６は、パレット（パレット１乃至３）に積み付けられた柱を示す図である。
図２４において、積付エリアであるパレット１には、柱１乃至柱２２の２２本の柱が配置されており、図２５において、パレット２には、柱２３乃至柱３９の１７本の柱が配置されており、図２６において、パレット３には、柱４０乃至柱５４の１５本の柱が配置されている。
【００５９】
図２７乃至図２９は、パレット（パレット１乃至３）に積み付けられた柱を構成する荷姿を示す図表である。
図２７において、柱１乃至柱２２の２２本の各柱の高さ、柱を構成する荷姿の数、およびその構成荷姿が示されている。例えば、柱１は、高さが１３００ｍｍで、４個の荷姿１２により構成されている。図２８において、柱２３乃至柱３９の１７本の各柱の高さ、柱を構成する荷姿の数、およびその構成荷姿が示されている。例えば、柱２４は、高さが１２０９ｍｍで、３個の荷姿１３と５個の荷姿１４の８個の荷姿により構成されている。図２９において、柱４０乃至柱５４の１５本の各柱の高さ、柱を構成する荷姿の数、およびその構成荷姿が示されている。例えば、柱５４は、高さが８７５ｍｍで、５個の荷姿１１により構成されている。
【００６０】
図３０は、本発明の他の実施の形態における積付スケジューリング処理を示すフローチャートである。
図３０において、フロー（ａ）は、上述してきた積付の処理の概略を示している。すなわち、積付のスケジューリングが、所定の積付エリア内において、柱を形成（生成）する工程とその柱を配置する（並び替える）工程とから行われることを示している。一方、フロー（ｂ）は、固定空間（倉庫等）で積み付けを複数回に分けて行なう場合や移動空間（トラックの荷台等）において積み付けを複数箇所で行なう場合を想定している。すなわち、図１を用いて説明した柱形成部３１が、積付エリアを複数の仮想積付空間に分け（仮想積付空間設定）、各仮想積付空間毎に柱を形成（生成）し、図１を用いて説明した柱配置部３２が、仮想積付空間の全て（全積付場所）において形成された全柱を配置する（並べ替える）。
【００６１】
図３１は、本発明の実施の形態における積付スケジューリング装置を備えたシステムの構成の一例である。
図３１において、ＧＡ積付スケジューリングシステムは、上述してきたような積付スケジューリング装置を備え、サーバと、パレタイザ制御盤を備えたパレタイザ制御装置と接続されている。サーバは、ＧＡ積付スケジューリングシステムに対して、積付予定データや各種マスタデータを送信し、サーバからこれらを受信したＧＡ積付スケジューリングシステムは、上述してきたような積付のスケジューリングを行ない、その積付スケジューリング結果のデータをサーバに送信する。また、サーバは、ＧＡ積付スケジューリングシステムから送信されてきた積付スケジューリング結果のデータを受信し、これに基づいて、パレタイザ制御装置に対して、実際の荷姿の積付指示を行なう。パレタイザ制御装置は、積付が完了したら、その旨をサーバに送信して積付が終了する。
【００６２】
上述のように、本発明の実施の形態を、図面を参照しながら説明してきたが、本発明が適用される積付スケジューリング装置は、その機能が実行されるのであれば、上述の実施の形態に限定されることなく、単体の装置であっても、複数の装置からなるシステムあるいは統合装置であっても、ＬＡＮ、ＷＡＮ等のネットワークを介して処理が行なわれるシステムであってもよいことは言うまでもない。
【００６３】
また、バスに接続されたＣＰＵ、ＲＯＭやＲＡＭのメモリ、入力装置、出力装置、外部記録装置、媒体駆動装置、可搬記録媒体、ネットワーク接続装置で構成されるシステムでも実現できる。すなわち、前述してきた実施の形態のシステムを実現するソフトウェアのプログラムコードを記録したＲＯＭやＲＡＭのメモリ、外部記録装置、可搬記録媒体を、積付スケジューリングシステムあるいは積付スケジューリング装置に供給し、その積付スケジューリングシステムあるいは積付スケジューリング装置のコンピュータがプログラムコードを読み出し実行することによっても、達成されることは言うまでもない。
【００６４】
この場合、記録媒体から読み出されたプログラムコード自体が本発明の新規な機能を実現することになり、そのプログラムコードを記録した可搬記録媒体等は本発明を構成することになる。
【００６５】
プログラムコードを供給するための可搬記録媒体としては、例えば、フロッピーディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、磁気テープ、不揮発性のメモリーカード、ＲＯＭカード、電子メールやパソコン通信等のネットワーク接続装置（言い換えれば、通信回線）を介して記録した種々の記録媒体などを用いることができる。
【００６６】
また、コンピュータがメモリ上に読み出したプログラムコードを実行することによって、前述した実施の形態の機能が実現される他、そのプログラムコードの指示に基づき、コンピュータ上で稼動しているＯＳなどが実際の処理の一部または全部を行ない、その処理によっても前述した実施の形態の機能が実現される。
【００６７】
さらに、可搬型記録媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリーに書き込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行ない、その処理によっても前述した実施の形態の機能が実現され得る。
【００６８】
すなわち、本発明は、以上に述べた実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内で種々の構成または形状を取ることが出来る。
【００６９】
【発明の効果】
以上説明してきたように、本発明によれば、サイズの異なる複数の荷姿を限られた積付エリアへ積み付ける際、積み付けを制約する条件を守りつつ積付量を最大または最適にスケジューリングすることができる。
【図面の簡単な説明】
【図１】本発明の実施の形態における積付スケジューリング装置の機能構成図である。
【図２】荷姿と遺伝子との関係および個体と染色体との関係を説明するための図である。
【図３】積み付けを行なう際の積付ルールの一例である。
【図４】評価関数の各パラメータ（ＧＡパラメータ、評価関数パラメータ）設定画面の一例である。
【図５】評価関数の各パラメータ（積付パラメータ）設定画面の一例である。
【図６】図１を用いて説明した初期個体群作成部２０が作成した複数の個体を説明するための図である。
【図７】図１を用いて説明した柱形成部３１が行なう柱の形成を説明するための図である。
【図８】図１を用いて説明した柱配置部３２が行なう柱の配置を説明するための図（その１）である。
【図９】図１を用いて説明した評価部４０が用いる評価関数の一例である。
【図１０】図１を用いて説明した柱配置部３２が行なう柱の配置を説明するための図（その２）である。
【図１１】図１を用いて説明した柱配置部３２が行なう柱の配置を説明するための図（その３）である。
【図１２】図１を用いて説明した柱配置部３２が行なう柱の配置を説明するための図（その４）である。
【図１３】図１を用いて説明した選択部６１が行なう選択および交叉部６２が行なう交叉を説明するための図である。
【図１４】図１を用いて説明した突然変異部６３が行なう交叉を説明するための図である。
【図１５】本発明の実施の形態における積付スケジューリング処理を示すフローチャートである。
【図１６】本発明の実施の形態の変形例を説明するための図である。
【図１７】本発明の実施の形態の変形例を具体的に説明するための図（その１）である。
【図１８】本発明の実施の形態の変形例を具体的に説明するための図（その２）である。
【図１９】本発明の実施の形態の変形例を具体的に説明するための図（その３）である。
【図２０】本発明の実施の形態の変形例を具体的に説明するための図（その４）である。
【図２１】本発明の実施の形態の変形例を具体的に説明するための図（その５）である。
【図２２】本発明の実施の形態の変形例を具体的に説明するための図（その６）である。
【図２３】積み付ける予定の荷姿の数量およびサイズを示した図表である。
【図２４】パレット（パレット１）に積み付けられた柱を示す図である。
【図２５】パレット（パレット２）に積み付けられた柱を示す図である。
【図２６】パレット（パレット３）に積み付けられた柱を示す図である。
【図２７】パレット（パレット１）に積み付けられた柱を構成する荷姿を示す図表である。
【図２８】パレット（パレット２）に積み付けられた柱を構成する荷姿を示す図表である。
【図２９】パレット（パレット３）に積み付けられた柱を構成する荷姿を示す図表である。
【図３０】本発明の他の実施の形態における積付スケジューリング処理を示すフローチャートである。
【図３１】本発明の実施の形態における積付スケジューリング装置を備えたシステムの構成の一例である。
【符号の説明】
１  積付スケジューリング装置
１０  入力部
１５  前処理部
２０  初期個体群作成部
３０  積付部
３１  柱形成部
３２  柱配置部
４０  評価部
５０  最適値格納部
５５  後処理部
６０  次世代個体群作成部
６１  選択部
６２  交叉部
６３  突然変異部
７０  出力部
【図１】
0004313491.tif 000002
【図２】
0004313491.tif 000003
【図３】
0004313491.tif 000004
【図４】
0004313491.tif 000005
【図５】
0004313491.tif 000006
【図６】
0004313491.tif 000007
【図７】
0004313491.tif 000008
【図８】
0004313491.tif 000009
【図９】
0004313491.tif 000010
【図１０】
0004313491.tif 000011
【図１１】
0004313491.tif 000012
【図１２】
0004313491.tif 000013
【図１３】
0004313491.tif 000014
【図１４】
0004313491.tif 000015
【図１５】
0004313491.tif 000016
【図１６】
0004313491.tif 000017
【図１７】
0004313491.tif 000018
【図１８】
0004313491.tif 000019
【図１９】
0004313491.tif 000020
【図２０】
0004313491.tif 000021
【図２１】
0004313491.tif 000022
【図２２】
0004313491.tif 000023
【図２３】
0004313491.tif 000024
【図２４】
0004313491.tif 000025
【図２５】
0004313491.tif 000026
【図２６】
0004313491.tif 000027
【図２７】
0004313491.tif 000028
【図２８】
0004313491.tif 000029
【図２９】
0004313491.tif 000030
【図３０】
0004313491.tif 000031
【図３１】
0004313491.tif 000032