緩和解情報を用いた発見的解法探索初期解の検討

摘要

大規模な物流センターや生産工場では自動倉庫を導入して作業の効率化を図っている．自動倉庫は，多数の収納器を3 次元の格子状に並べた収納庫と，指定された収納器へ物品の搬送·入庫（および，任意の収容器からの出庫·搬送）を行う自動搬送機（スタッカークレーン；SC）とで構成される．1 台のSC は2 次元状の容器集合（立体棚1 面）を受持ち，指示された容器位置への移動と物品交換を自動的に行う．以下では，1 台のSC に焦点を当てる．ある時点で1 台のSC が処理すべき物品（対応する入出庫作業）は多数あるが，SC が一度に保持できる物品数（容量）は高々数個なので，複数回に分けてこれらを処理する．すなわち，SC は倉庫の入出庫口で入庫品を載せて出発し，それらを収納しつつ，出庫品を取出し再び入出庫口に戻る動作（巡回）を繰り返す．同一の巡回で処理する物品をうまく選び，能率良く巡回して少ない所要時間で全ての処理を終えることが望ましい．胡ら[1] はこのようなSC の運行計画を決定する問題を提起し，「入出庫スケジューリング問題」と名付け，この問題に対する発見的解法を提案した．田中ら[2] はこの問題に対し，容量制約付き配送経路問題の枠組みを適用した解法を提案している．この解法は，徐々に強化される緩和解の情報を利用し，高速に高精度の解を求める．しかし，問題例のサイズ（入出庫品の数）が大きくなると実行時間と精度は低下する．また，沼田ら[3] は，入出庫品交換近傍の可変深度近傍探索を用いた発見的解法（以後解法N と呼ぶ）を提案している．この解法は，文献[2] と比べ得られる解の精度はやや劣るが，入出庫品数の増加に対して頑健な性能を示す．一般に探索型解法の出力結果は初期解（初期組分け）に依存する．そのため，解法N は多スタート戦略を援用しているが，こうすると計算時間が増大する．良い初期解（良い初期組分け）を安定的に得るためには，文献[2] のように，緩和解の情報を利用するのが有効ではないかと考えられる．本発表では，緩和解情報を基に生成した初期組分けが解法N の結果にどのように影響するかを数値実験により調べて報告する．