(57)【要約】【構成】ロケーションの整理計画を、＃１  空きにするロケーションの探索、＃２  空けるロケーションの物品をどのロケーションに搬送するかの探索、＃３  どの台車にどの搬送作業を割り付けるかのスケジューリングの３つの問題に分割し、各問題毎に最適解を求める。【効果】平置き倉庫のロケーションの整理計画を計算可能な問題に変換し、実用的な時間内で準最適解を求めることができる。【選択図】    図４
2004359452.tif 000002
【特許請求の範囲】
【請求項１】
平置き倉庫内の物品を台車により再配置することにより、倉庫内を整理して空きロケーションを作る方法において、
ロケーションの現状、投入する台車の台数、整理の作業時間を入力情報として、空きにするロケーションを探索するステップ、空けるロケーションの物品をどのロケーションに搬送するかを探索するステップ、及びどの台車にどの搬送作業を割り付けるかを計画するスケジューリングステップの３ステップを行うことを特徴とする、平置き倉庫のロケーション整理方法。
【請求項２】
ロケーション整理の実行中に、ロケーション整理での残余の搬送作業に対して、前記スケジューリングステップを再度行い、台車への搬送作業の割り付けを再計画することを特徴とする、請求項１の平置き倉庫のロケーション整理方法。
【請求項３】
多数の物品を複数のロケーションに平置きして、台車により入出庫する平置き倉庫において、
ロケーションの現状、投入する台車の台数、整理の作業時間を入力情報として、空きにするロケーションを探索し、空けるロケーションの物品をどのロケーションに搬送するかを探索し、かつどの台車にどの搬送作業を割り付けるかを計画するための制御部を設けたことを特徴とする、平置き倉庫。
【発明の詳細な説明】
【０００１】
【発明の利用分野】
この発明は平置き倉庫に関し、特にパレットを再配置して空きロケーションを作り出すロケーションの整理に関する。
【０００２】
【従来技術】
【０００３】
【特許文献１】特開平６−２３９４２０号公報
特許文献１は、平置き倉庫のロケーションの整理について開示している。そして変品種変量生産が重要になるに連れ、平置き倉庫でもロケーションを整理して、次の出庫をスムーズに行えるように準備する必要性が増している。
【０００４】
平置き倉庫のロケーションの整理計画は、（ｉ）パレットの再配置計画と、（ｉｉ）複数のフォークリフトによるパレットの搬送計画、の２つに分けられる。（ｉ）の再配置計画では、現状のパレット配置に対し、次の入出庫に備えてパレット配置を最適化する。（ｉｉ）の搬送計画では、（ｉ）の再配置計画で決定された配置を実現させるため、作業とその順序を複数のフォークリフトに割り当てる。ところで図１に平置き倉庫２の例を示すと、４はフォークリフトの通路で、６は個別のロケーションで、８はロケーション内の空きスペースである。平置き倉庫２では、同じ品種の物品を同じロケーション６に配置することが好ましく、異なる品種の物品を同じロケーションに配置することは好ましくない。また各品種に対して製造日などの違いがあることを考慮すると、同じ品種で製造日が同一もしくは近接したものを同じロケーションにまとめることになる。
【０００５】
これらの制約のため、パレットの配置には極めて多数のパターンが考えられ、パレットの配置パターンは品種の数に応じて指数的に増加し、莫大なものとなる。また（ｉｉ）の搬送計画は、巡回セールスマン問題の一種であり、基本的にＮＰ困難な問題である。このような大規模な最適化問題に対し、実用的な時間（目安として１０分以内）で準最適な解を求めることは極めて難しい。
【０００６】
平置き倉庫では、複数のフォークリフトが作業スペースを共有するため、フォークリフト間の干渉がある。このため、仮に平置き倉庫に対するパレットの再配置計画や搬送計画の準最適解が求まったとしても、これらの最適解にフォークリフト同士の干渉を考慮することは実質上不可能である。また有人のフォークリフトの場合、作業能率は運転手により異なり、これを搬送計画に盛り込むことも困難である。
【０００７】
図２に現状で用いられている平置き倉庫の整理計画のアルゴリズムを示すと、パレット数の少ないロケーションから空きにするロケーションの候補として、リストを作成する。次にリストの上位（パレット数の少ないロケーション）からフォークリフトに搬送作業を割り当て、搬送先は品種が一致し製造日が近接あるいは一致する範囲で、パレット数の多いロケーションから、あるいは品種や製造日が所定の条件を充たせば、近接したロケーションからとする。そして１つのロケーションには１台のフォークリフトを割り当てる。この手法では、どのロケーションを空きにするかを、パレット数が少ないとの経験的な基準で定め、搬送計画を最適化すること、言い換えると巡回セールスマン問題に取り組むことは放棄している。
【０００８】
【発明の課題】
この発明の課題は、効率的に平置き倉庫のロケーションを整理できるようにすることにある（請求項１〜３）。
請求項２の発明での追加の課題は、ロケーションの整理をさらに効率的にすることにある。
【０００９】
【発明の構成】
この発明の平置き倉庫のロケーションの整理方法は、平置き倉庫内の物品を台車により再配置することにより、倉庫内を整理して空きロケーションを作る方法において、ロケーションの現状、投入する台車の台数、整理の作業時間を入力情報として、空きにするロケーションを探索するステップ、空けるロケーションの物品をどのロケーションに搬送するかを探索するステップ、及びどの台車にどの搬送作業を割り付けるかを計画するスケジューリングステップの３ステップを行うことを特徴とする（請求項１）。
【００１０】
好ましくは、ロケーション整理の実行中に、ロケーション整理での残余の搬送作業に対して、前記スケジューリングステップを再度行い、台車への搬送作業の割り付けを再計画する（請求項２）。
【００１１】
またこの発明の平置き倉庫は、ロケーションの現状、投入する台車の台数、整理の作業時間を入力情報として、空きにするロケーションを探索し、空けるロケーションの物品をどのロケーションに搬送するかを探索し、かつどの台車にどの搬送作業を割り付けるかを計画するための制御部を設けたことを特徴とする（請求項３）。
【００１２】
特に好ましくは、空きにするロケーションの探索では、空きにするロケーションの候補毎に、空けるロケーションの物品をどのロケーションに搬送するかの、搬送先の探索を複数回繰り返して、空きにするロケーションの候補の効率を評価する。また空けるロケーションの物品をどのロケーションに搬送するかの搬送先の探索では、搬送先の候補毎にどの台車にどの搬送作業を割り付けるかの計画を立案して、搬送先の候補の効率を評価する。
【００１３】
ここで好ましくは、空きにするロケーションの候補の探索では複数の候補を評価し、搬送先の探索では空きにするロケーションの候補毎に搬送先の候補を複数評価する。この評価では、好ましくは局所的な最適解に落ち込まないように、シミュレーテッドアニーリングや遺伝的アルゴリズムなどを用い、それ以前の候補よりも低効率の候補でも、所定の条件、例えば所定の確率で、新たな候補を採用するようにする。好ましくはシミュレーテッドアニーリングを用い、それ以前の候補よりも効率の高い候補は採用し、それ以前の候補よりも効率の低い候補は所定の確率で採用し、この確率を実行済みの探索回数が大きく、かつ効率の低下の程度が大きいほど、小さくなるようにして、探索の終期には準最適解に達するようにする。
【００１４】
台車への搬送作業の割り付け計画（搬送計画）は、複数のセールスマンに対する巡回セールスマン問題となり、ＮＰ困難な問題である。この問題は、搬送元のロケーションを一方の集合とし、搬送先のロケーションを他方の集合とする２部グラフの問題と見なして、２部グラフ間での長い経路を求める問題（ラージアークアルゴリズム）として解いても良い。しかし実施例では、これよりも計算量が少ない計算法（後述のグリーディ法）を用いた。
【００１５】
【発明の作用と効果】
この発明では、ロケーションの整理計画を、
＃１  空きにするロケーションの探索、
＃２  空けるロケーションの物品をどのロケーションに搬送するかの探索、
＃３  どの台車にどの搬送作業を割り付けるかのスケジューリング、
の３つの問題に分割し、各問題毎に準最適解を求める。このため平置き倉庫のロケーションの整理計画を計算可能な問題に変換し、準最適解を求めることができる（請求項１〜３）。
【００１６】
従来の整理計画では、パレット数の少ないロケーションから空きにし、空きにするロケーション毎に台車を割り付ける（図２）などの、ロケーションの現状のみを入力情報とするアルゴリズムが用いられている。図２のアルゴリズムに、パレット数の多いロケーションから搬送先とするなどのアルゴリズムを追加することもあるが、これもロケーションの現状のみを考慮し、投入するフォークリフト等の台車の台数や作業時間を考慮していない点では同様である。これらのアルゴリズムでは、短時間で空きにできるパレット数の少ないロケーションから作業を開始して、作業時間が無くなると、中途でも作業を中止することになる。
【００１７】
また搬送先は、能力一杯にパレットを保管できるように、パレット数の多いロケーションから優先するなどのことが行われるが、台車の走行経路長を短縮するなどの配慮は行われていない。これ対して、作業時間や作業台数を考慮し、問題を、＃１  空きにするロケーションの探索、＃２  空けるロケーションの物品をどのロケーションに搬送するかの探索、＃３  どの台車にどの搬送作業を割り付けるかのスケジューリング、に３分割すると、＃３のスケジューリングにより同じ量の搬送作業に対して台車の走行経路長の合計を最短にし、＃２で最適な搬送先を選択し、＃１で、与えられた作業時間と作業台数とに対して、どのロケーションを空きにするかを最適化できる（請求項１〜３）。
【００１８】
さらに整理作業の実行中に、＃３のスケジューリングを再度行うと、スケジューリングを再度行わない場合に比べ、例えば５％程度多くの空きロケーションを作ることができた。スケジューリングの最適化はＮＰ困難な問題で、かつ台車相互の干渉などの予想困難な問題が介在するが、整理作業の実行中に再スケジューリングを行えば、上記のような困難を回避できる（請求項２）。
【００１９】
この発明の効率（ここでは同じ作業時間と作業台数で空きにできるロケーションの数）は、品目数、搬送するパレット数などにも依存するが、例えば図２の従来例に対し、１０〜２０％程度多くの空きロケーションを作ることができた。またロケーション整理の計画作成に必要な計算時間は、ＣＰＵタイムで１時間未満のオーダー（例えば１０分程度）であり、作業時間に余裕ができそうな時や、昼休み、朝の作業開始前の準備時間、夕刻の終業後の余裕時間などに、整理計画を立てることが可能な範囲である。従ってこの発明では、予めスケジュールした時だけでなく、臨機応変に平置き倉庫のロケーションを整理できる。
【００２０】
【実施例】
実施例では、計画段階で使用するモデル＝計画モデルと、シミュレーション環境を定義する実行モデル、の２つのモデルを用意する。また実施例では、図３〜図９に整理計画の作成法を示し、図１０〜図１２にその評価結果を示し、図１３に整理計画を立案実行するための制御部を示す。２つのモデルの仕様を以下に示す。
【００２１】
＜前提条件＞
作業時間はロケーション間の移動コストの和で表現される。移動コストは、事前に荷物の配置をランダムに変えた１０００回の（実行モデルでの）シミュレーションで得た、各ロケーション間の最短経路長の平均をフォークリフトの平均移動速度で割ったものを用いた。これはパレットの移載に必要な時間を無視するモデルである。
＜モデル化される要素＞
（１）  各ロケーションの情報：  パレット数・品目・製造日，最大容量
（２）  ロケーション間の移動コスト
なお品目は単なる品種の意味で用いる場合と、品種と製造日の組み合わせの意味で用いることとがあるが、そのいずれであるかは前後の表現で明らかにする。
【００２２】
【実行モデル】
＜前提条件＞
（１）  フォークリフトは一定速度で移動するものとする。
（２）  パレットをすくったり、下ろしたりする動作にかかる時間は、０として無視する。
（３）  フォークリフトは交通ルールを遵守し・衝突を回避し、最短経路でロケーション間を移動する。
【００２３】
＜モデル化される要素＞
（１）  各ロケーションの情報：  位置・形状，パレット数・品目・製造日，最大容量
（２）  フォークリフト同士やフォークリフトとパレットとの干渉
（３）  衝突回避等のための交通ルール（通行区分，待機）
計画モデルに対し実行モデルでは、２次元平面上をフォークリフトが移動し、幾何的な距離とフォークリフト同士やフォークリフトとパレットの干渉がある。衝突を回避しフォークリフト同士のデッドロックを防ぐため、適宜の交通ルールを定め、速度制限、優先走行順序と待機順序などを定め、また目的のロケーションで他のフォークリフトが作業しているときは、その手前の位置で待機するなどの制約を課す。
【００２４】
入力情報、出力情報、使用する変数の定義を以下に示す。
2004359452.tif 000003
ｋはフォークリフトを示す添字で、（１）は作業時間が最大のフォークリフトでも指定された時間内に作業を完了することを意味する。
ｘ∈Ｓ
Ｓ：        搬送スケジュールの集合
ｘ：        搬送スケジュール
Ｅ（ｘ）：      空のロケーションの数
Ｔｋ（ｘ）：    フォークリフトｋの作業時間
Ｔｒｅｑｕｅｓｔ：  要求作業時間
【００２５】
＜入力情報＞
（１）  各ロケーションの情報：  位置，形状，在庫パレット数・品目・製造日，最大容量
（２）  要求作業時間
（３）  フォークリフトの台数
＜出力情報＞
各フォークリフトの搬送スケジュール：  「ロケーションｉからｊへの１パレットの搬送」を単位タスクとして、各フォークリフト毎にタスクを実行する順序を示したもの。フォークリフト毎の搬送スケジュールの全フォークリフトに対する総和を考えると、搬送スケジュールｘとなる。
【００２６】
＜変数の定義等＞
Ｌ：  ロケーションの集合
ｉ：  原則としてロケーションを表す添字
Ｑｉ：  ロケーションｉのパレット数
Ｋｉ：  ロケーションｉに置かれている品目
Ｃｉ：  ロケーションｉの容量
ｗｉｊ：  ロケーションｉ−ｊ間の移動コスト
Ｒｉｊ：  ロケーションｉ−ｊ間の搬送回数
Ｆ：    フォークリフトの集合
Ｎｋ：  フォークリフトｋの現在いるロケーション
Ｓｋ：  フォークリフトｋのスケジュール
【００２７】
整理計画を３つの段階に分解する。
＃１  空にするロケーションの決定
＃２  パレットの搬送先の決定
＃３  スケジュールリング
図３〜図５に示すとおり、＃２は＃３を、＃１は＃２と＃３を内包しているが、各々の階層では独立したアルゴリズムで解を求めることができる。＃１，２ではシミュレーテッドアニーリング（以下ＳＡ）を、＃３では巡回路生成に関する近似アルゴリズム（グリーディ法やラージアークアルゴリズム）を用いる。これらを共通の枠組みとした上で、作業開始前のオフラインでの計画と、実際の整理作業と平行したオンラインの再計画とを行う。オフラインでは＃１−＃３を、オンラインでは＃３を実行する。
【００２８】
ロケーション整理での最適化問題は（１）式で与えられ、（１）式をそのまま評価関数として使うこともできるが、制約条件により探索過程で解が推移する空間が制限され、探索効率が悪化することが考えられる。そこで実施例では、次式を評価関数として用いる。
2004359452.tif 000004
ここで、αは定数、（３）式での最大値はｋに関して求め、（４）式のＰｋｉｊ（ｘ）は、スケジュールｘにおいてフォークリフトｋがロケーションｉ−ｊ間を移動する回数で、（４）式のｉ，ｊはロケーションの集合Ｌの範囲で検討する。ペナルティ関数Ψ（ｘ）は得られた作業時間が要求を満たす際は１より小さい正の値、充たさない場合は負の値となる。
【００２９】
初期解は以下のようにして生成する。このアルゴリズム１によって、ロケーションｉからｊへの搬送回数Ｒｉｊが得られる。
アルゴリズム１    （初期解の生成法）
ステップ１    全ての品目ｍに対し、再配置により空きにすることができるロケーションの数ΔＥｍを求める。
ステップ２  ロケーションｉが同じ品目がおかれているロケーションの中で、パレット数が少ない順にΔＥｍ番目までであれば、Ｍｉをｔｒｕｅとし、そうでなければｆａｌｓｅとする。ステップ２は全ロケーションに対して行う。
ステップ３  Ｍｉがｔｒｕｅのロケーションを、パレット数の少ない順にリストして、順列Πとする。
ステップ４      Ｒｉｊ←０（∀ｉ∈Ｌ，∀ｊ∈Ｌ）  ｔ←１とする。
ステップ５      順列Πのｔ番目の要素をａに代入
ステップ６      （Ｋａ＝Ｋｊ∩Ｃｊ−Ｑｊ−Σｉ∈ＬＲｉｊ）＞０を満たすｊ（∈Ｌ）をランダムに選び、Ｒａｊ←Ｒａｊ＋１とする。これをＱａ回繰り返す。
ステップ７      後述のアルゴリズム３を実行。得られた解が要求作業時間を満たせばｔ←ｔ＋１としステップ５へ、満たさない場合はＲａｊ←０（∀ｊ∈Ｌ）として終了。
【００３０】
＃１，＃２での探索アルゴリズムとして、図８に示すシミュレーテッドアニーリングを用いる。シミュレーテッドアニーリングは選んだ近傍解が現在より改善されれば採択し、改悪されても改悪量をｄとしてｅｘｐ（−ｄ／ｔｉ）の確率で採択する。ｔｉは温度関数で、ｔｉが探索回数ｉに対し正値で単調減少するため、探索の初期段階では大域的な探索をし、探索が進むにつれ解が改善される方向に探索範囲を絞り、準最適解に収束することができる。
【００３１】
先ず初めの段階として。空けるロケーションを探索する。これは図３の＃１（図４、図５のＬａｙｅｒ１）に対応する。この階層でのフローチャートを図５に示す。ここでは、図７に示す３つの近傍探索法を用いる。
【００３２】
Ａｄｄ：        任意のパレット受け入れロケーションから、ランダムにａ（∈Ｌ）を選び、空にするロケーションのリストに追加し、Ｋａ＝Ｋｊ∩Ｃｊ−Ｑｊ−Σｉ∈ＬＲｉｊ＞０を満たすｊ（∈Ｌ）をランダムに選び、Ｒａｊ←Ｒａｊ＋１とする。
Ｄｅｌｅｔｅ：    空にするロケーションのリストから、ランダムにｂ（∈Ｌ）を選び、リストから削除。Ｒｂｊ←０（∀ｊ∈Ｌ）とする。
Ｅｘｃｈａｎｇｅ：  Ｄｅｌｅｔｅを実行後、Ａｄｄを実行する。
【００３３】
ここで注意すべき点は、入れ替え（Ｅｘｃｈａｎｇｅ）という操作である。この操作は追加と削除の組み合わせであるが、連続に行った後で解の評価を行うところに意味がある。入れ替えでは（２）式におけるＥ（ｘ）の値を固定したまま解を推移させることが可能で、作業時間の短縮のみに焦点を絞ることができる。また図５に示すように、得られたスケジュールが要求作業時間を満たすときは追加し、越える場合は削除または入れ替えを適当な確率、例えば等確率で選ぶ。このように取り得る近傍探索法を限定することにより、空きにするロケーションの探索効率の改善を図る。
【００３４】
空けるロケーションを決定した後、次にどこにパレットを搬送させるかを決定する（図３の＃２、図４，図５のＬａｙｅｒ２に対応）。この階層でのアルゴリズムのフローチャートを図６に示す。ここでは、次に示す近傍探索法を用いる。
Ｓｈｉｆｔ：  （Ｋｉ＝Ｋｊ＝Ｋｋ∩Ｒｉｊ＞０）  ∩  （Ｃｋ−Ｑｋ−Σｌ∈ＬＲｌｋ＞０）を満たす、ｉ，ｊ，ｋ（∈Ｌ，ｉ≠ｊ，ｊ≠ｋ，ｋ≠ｉ）をランダムに選び、Ｒｉｊ←Ｒｉｊ−１，Ｒｉｋ←Ｒｉｋ＋１とする。
【００３５】
図６のアルゴリズムでは、搬送先のロケーションをシフト動作により変化させて搬送先の組み合わせの新たな候補を発生させ、この候補毎に＃３のスケジューリング問題の近似解を求めて、搬送先の組み合わせの候補を評価し、シミュレーテッドアニーリングにより所定の回数搬送先の候補の探索を繰り返して、搬送先の組み合わせの準最適解を求める。
【００３６】
決定されたパレットの配置を実現させるべく、実際にフォークリフトに搬送作業をその作業順と共に割り当てる（図３の＃３、図４のＬａｙｅｒ３，図５の搬送スケジューリングに対応）。ここでのスケジューリング問題は一般に巡回セールスマン問題（以下ＴＳＰ）と呼ばれるものの一種で、ＴＳＰの解法には、ラージアークアルゴリズムなどがある。しかし、これらのアルゴリズムの計算時間は、いずれも搬送するパレット数の３乗のオーダーで増加するため、本問題のように大規模で、しかも全体のアルゴリズム（＃１〜＃３）の最下層で繰り返し計算を行う（図３〜図５、図６参照）には不向きである。従って実施例では、以下のようなアルゴリズム（グリーディ法）を用いる。
【００３７】
アルゴリズム２  （グリーディ法：  ＴＳＰの近似解法）
変数の定義    フォークリフトｋの作業見積もり時間をＴｋ，ロケーションｉにおける優先フォークリフトを示すインデックスをＩｉとする。
ステップ１    ∀ｋ∈Ｆに関して、Ｔｋ←０，Ｎｋにフォークリフトｋの最寄りロケーションをセットする。また∀ｉ∈Ｌに関して、Ｉｉ←φとする。
ステップ２    ａｒｇｍｉｎｋＴｋとなるｋを選ぶ。これは引数ｋに対してＴｋが最小となるｋを選ぶことで、ａｒｇｍｉｎｘＹｘは引数Ｙｘが最小となるｘを選ぶことである。そのｋに対し、
（∃ｊ∈Ｌ，Ｒｉｊ＞０）  ∩  （Ｉｉ＝ｋ  ∪  Ｉｉ＝φ）  の条件下でａ←ａｒｇｍｉｎｉｗＮｋｉとする。そのようなロケーションがない場合はステップ４へ移行する。
ステップ３    Ｒａｊ＞０の条件下でｂ←ａｒｇｍｉｎｊｗａｊとする。ロケーションＮｋからａまでの「移動」と、ロケーションａからｂまでの「搬送」をスケジュールＳｋに加える。Ｔｋ←Ｔｋ＋ｗＮｋａ＋ｗａｂ，Ｎｋ←ｂ，Ｉａ←ｋ，Ｒａｂ←Ｒａｂ−１とする。
Ｒｉｊ＝０（∀ｉ∈Ｌ，∀ｊ∈Ｌ）ならば終了、そうでなければステップ２へ。
ステップ４    ∃ｊ∈Ｌ，Ｒｉｊ＞０の条件下でａ←ａｒｇｍｉｎｉｗＮｋｉとし、ステップ３へ戻る。
【００３８】
このアルゴリズムでは、ロケーションｉにおける優先フォークリフトを示すインデックスＩｉを設け、１つの搬送元ロケーションに複数のフォークリフトが集中することを防いでいる。
【００３９】
以上が、オフラインでの整理計画法であるが、実施例では実作業の開始後にも、作業の進行状況を情報として取り入れ、逐次再計画を行う。用いる情報は、
（ｉ）    その時点でのパレット配置、
（ｉｉ）  フォークリフトの位置、
（ｉｉｉ）  残りの搬送スケジュール、
の３つである。再計画対象はスケジューリングの部分のみとし、これは再計画に要する時間を極力短縮するためである。なお再計画に数分必要であると、その間作業を止めるか、数分前のパレットやフォークリフトの配置を元にスケジューリングをやり直すことになる。再計画のアルゴリズム（アルゴリズム３）はアルゴリズム２とほぼ同様であるが、ステップ１のみ以下のように異なる。図９に、３台のフォークリフトに対する６パレットの搬送タスクに関し、スケジューリングを再度行う例を示す。
【００４０】
アルゴリズム３  （オンラインでの再計画法）
ステップ１    ∀ｋ∈Ｆに関して、フォークリフトｋがロケーションｉからｊまで搬送中ならばＴｋ←ｗｉｊ，Ｎｋ←ｊとする。搬送中でなければＴｋ←０，Ｎｋには最寄りのロケーションをセットする。未実行の搬送スケジュール（移動のみのものを含まない）をロケーションｉ−ｊ間毎に数え上げＲｉｊに代入。また、Ｓｋ←φ，（∀ｋ∈Ｆ），Ｉｉ←φ，（∀ｉ∈Ｌ）とする。
ステップ２−４    アルゴリズム２に同じ。
【００４１】
実施例の有効性を検証すべくシミュレーション実験を行った。図１にシミュレーションで使用する倉庫のレイアウトを示す。ロケーション数は１１６，品目数は５０，フォークリフト台数は８とした。パレットは２段積みでロケーション奥から詰めて置いていく。１つのロケーションには奥行き２０，横２列，垂直２段で最大８０パレット置くことができる。各ロケーションの在庫パレット数、及びその品目はランダムで５０パターン生成する。また、フォークリフトの速度は一定で３．０ｍ／ｓとする。
【００４２】
シミュレーテッドアニーリングにおける温度関数ｔｉは以下の式を用いる。
ｔｉ＝ζｉ−１ｔ１                            （５）
＃１の空きにするロケーションの探索ではζ＝０．９０，ｔ１＝１．０とし，＃２の搬送先の探索ではζ＝０．９５，ｔ１＝１００とした。終了条件は＃１では２４０回，＃２では１０００回の探索を終えた時点とした。また式（３）においてα＝０．５４ｍｉｎ−１とした。オンラインでの再計画は作業時間にして１．０ｍｉｎごとに行った。計画にはＰｅｎｔｉｕｍ４（Ｐｅｎｔｉｕｍはインテル社の登録商標）  １．５ＧＨｚのＣＰＵを搭載した計算機を用いた。オフラインでの計画には約１８０ＣＰＵｓｅｃ，オンラインでの再計画には０．０１ＣＰＵｓｅｃ以下の計算時間を要した。
【００４３】
まずオンラインでの逐次再計画の有効性について検証する。表１に逐次再計画を行ったものと、行わなかったものの３つの異なる要求作業時間に対する、各５０試行平均のデータを示す。ここで、空きロケーション数とは要求作業時間内に空けられたロケーションの数，超過時間とは要求作業時間に対し、計画した作業を全て遂行するのに要した時間の超過分、作業終了時間差とはフォークリフト間のの作業終了時刻の最大差を指している。
【００４４】
【表１】
2004359452.tif 000005
【００４５】
表１より、逐次再計画を行ったものは全時間平均で４．７％多くのロケーションを空けている。特筆すべきところは、作業終了時間差が、逐次再計画を行うと逐次再計画を行わない場合の、４０〜２０％に抑えられている点である。このことより、逐次再計画によって作業が進行状況に合わせて割り当てられ、各フォークリフト間の作業時間格差を減少させていることが分かる。このことで、結果的に作業時間を短縮させ、要求作業時間内により多くのロケーションを空けることができた。
【００４６】
【実施例の効率評価】
図１０〜図１２に、図２の従来例との比較で実施例の効率を示す。図２の従来例では、パレット数の少ないものから空きにするロケーションとし、空きにする各ロケーションについて１台ずつフォークリフトを配置し、作業時間内に手空きになったフォークリフトがあると、次にパレット数の少ないロケーションを空きにする作業を開始する。
【００４７】
図１０は、１０分、２０分、３０分の要求作業時間内に空きにできたロケーションの数の比較で、各要求作業時間に対して、パレット配置のテストパターンを２０種用意して行った。実施例ではどの作業時間でも効率が高く、平均で１４％多くのロケーションを空きにしている。
【００４８】
図１１は、パレット数や品目数に対する空きにできたロケーション数の依存性を示し、要求作業時間は２０分とした。パレット数が同じで品目数が少なくなると、どのロケーションからどのロケーションにパレットを搬送するかの作業のバリエーションが増し、実施例と従来例との効率の差が増している。一方パレット数や品目数が増すと、遠距離搬送が通常になり、スケジューリングの差が出ないなどにより、効率の差は小さくなる。
【００４９】
図１２は、要求作業時間を２０分にした際の、フォークリフトの台数と、空きにできたロケーションの数とを示す。どの台数でも、実施例は従来例よりも高い作業効率を示す。
【００５０】
図１３に、実施例の平置き倉庫の制御部１０の構成を示す。１２は操作パネルで、整理計画の立案や実行などの指示を受け、在庫ファイル１３は各ロケーションの在庫パレット数と品目とを記憶しており、フォークリフト管理部１４は複数のフォークリフト１６に搬送指令を割り付け、搬送結果を管理する。通信部１５からフォークリフト１６へ搬送指令を送信する。またフォークリフト１６は搬送作業を完了すると、その場で完了した旨を通信により報告するので、フォークリフト１６の現在位置と作業の進捗状況とが判明する。フォークリフト１６は有人でも無人でも良い。
【００５１】
整理計画の立案時には、その旨をマニュアルなどで操作パネル１２から入力し、フォークリフト管理部１４で記憶している稼働中のフォークリフトの台数、あるいは操作パネル１２からマニュアルで入力した台数を作業台数とする。また作業時間は操作パネル１２からマニュアルで入力する。
【００５２】
空きロケーション探索部１８は、図４〜図５の手法で、＃１の空きにするロケーションを探索する。パレット搬送先探索部２０は、図４〜図７の手法で、＃２のパレットの搬送先のロケーションを探索する。ここで＃１や＃２の探索は、複数回行って最適化し、途中での候補の評価にはシミュレーテッドアニーリング部２８を用い、採用確率は図８に示すものなどを用い評価部３０で実行する。
【００５３】
スケジューリング処理部２２は、グリーディ処理部２３あるいはラージアークアルゴリズム処理部２４などを用いて、＃３のフォークリフトへの搬送スケジュールを作成する。スケジューリングの手法は、制御部１０の計算能力に応じて追加や変更をして行けばよい。オンライン再計画部２６は、フォークリフト１６が整理作業を開始した後に、適宜の間隔で＃３のフォークリフトの搬送スケジュールを再作成する。
【図面の簡単な説明】
【図１】ロケーションの整理対象の平置き倉庫の斜視図
【図２】従来例での作業計画の作成アルゴリズムを示すフローチャート
【図３】実施例での、ロケーション整理に関する問題の分割を示す図
【図４】実施例での、ロケーション整理計画の全体的作成アルゴリズムを示す図
【図５】実施例での空きロケーションの探索アルゴリズムを示す図
【図６】実施例での、搬送先の探索アルゴリズムを示すフローチャート
【図７】実施例での、空きにするロケーションの探索手法を示す図
【図８】実施例での、シミュレーテッドアニーリングでの新たな計画の採用確率を、探索回数並びに改悪量の関数として示す図
【図９】実施例での、ロケーション整理の実行中の、オンライン逐次再計画を模式的に説明する図
【図１０】要求作業時間に対する空きローケーション数を、従来例と実施例とで示す図
【図１１】パレット数と品目数に対する空きローケーション数を、従来例と実施例とで示す図
【図１２】フォークリフト数に対する空きローケーション数を、従来例と実施例とで示す図
【図１３】実施例の平置き倉庫でのロケーション整理制御部のブロック図
【符号の説明】
２      平置き倉庫
４      通路
６      ロケーション
８      空きスペース
１０    制御部
１２    操作パネル
１３    在庫ファイル
１４    フォークリフト管理部
１５    通信部
１６    フォークリフト
１８    空きロケーション探索部
２０    パレット搬送先探索部
２２    スケジューリング処理部
２３    グリーディ処理部
２４    ラージアークアルゴリズム処理部
２６    オンライン再計画部
２８    シミュレーテッドアニーリング部
３０    評価部
【図１】
2004359452.tif 000006
【図２】
2004359452.tif 000007
【図３】
2004359452.tif 000008
【図４】
2004359452.tif 000009
【図５】
2004359452.tif 000010
【図６】
2004359452.tif 000011
【図７】
2004359452.tif 000012
【図８】
2004359452.tif 000013
【図９】
2004359452.tif 000014
【図１０】
2004359452.tif 000015
【図１１】
2004359452.tif 000016
【図１２】
2004359452.tif 000017
【図１３】
2004359452.tif 000018