ピックアップ対象に注目した倉庫の巡回路最適化 13D8102006J 増川 臨
中央大学理工学部情報工学科 田口研究室 2017年3月
あらまし：本研究では、実際に国内国外に 発送する補修部品の倉庫におけるピックア ップ作業を対象とする。一週間分の実デー タを用いて、必要な部品の注文に対し、回収 ルートの最適化を検討する。
最短巡回路（効率よく指定された点を巡 回する経路を求める）を解くための手法で
ある 2-opt 近傍を用いて、倉庫での回収ル
ートの最短経路を求める。次に、（メタ戦略 or配送計画問題）における回収量や回収手 順の最適化を検討していく。
キーワード：2-opt法、巡回路問題、配送計 画問題、ファーストフィット法
１ はじめに
今の時代，配送はなくてはならない存在 になっている．いろいろな配送計画と関連 する配送経路があり，様々な基準で効率の 良い配送計画を解く問題がある一方で，倉 庫から物を取り出す巡回路問題が少ないよ うに思えた．
移動する行程を早くするだけでなく，運 ぶものを選択する工程を考察することで時 間と運搬量の両方の効率化が可能になるの ではないかと思い，本研究に臨もうと考え た．
２ 配送計画問題
２．1 ファーストフィット法
ファーストフィット法(first fit method) は，ビンバッキング問題に対する代表的な 近似解法である．ビンバッキング問題(bin-
packing problem)とは，重さが異なるn個
の荷物を，Wの重さを入れることのできる T 個の箱に，すべて入れられるかどうかを 決定する問題である．本稿の言葉で表すと，
荷物は顧客が求める積荷であり，荷物の重 さは顧客の需要量，Wの重さを入れること のできるT個の箱は，Wの容量を持つT台 の運搬車である．
ファーストフィット法の考え方は次の通 りである．
初めに顧客をランダムな順に並べる．そ して並べた列の先頭の顧客から順番に，用 意していた運搬車に割り当てる．ある顧客 を割り当てる際，もし運搬車の容量を超え てしまうのならば，次の運搬車へ配属させ る．これ以降，顧客を最初の運搬車に積むこ
とが出来るのならば初めの運搬車へ，出来 ないのなら次の運搬車へ割り当てることが 出来たら完了である．
この手法を用いて全ての顧客を運搬車に 割り当て，各運搬車での配送順序は割り当 てられた順番とする．こうすると，配送計画 問題としての評価値（移動距離）を無視し た，運搬車の容量のみを考慮した初期解を 生成することになる．
2．2 2-opt近傍
2-opt 近傍は以下のように定義すること
ができる．
1. １つ以上の巡回路による解が構築され ている．
2. 解における2本の枝 (i ,i+1) ,(j , j+1) を (i , j+1) ，(j , i+1) につなぎ替える．2本 の枝を交換する組み合わせは，1つの巡 回路のみを対象とする場合と 2 つの巡 回路を対象とする場合がある．これら全 ての組み合わせを合わせたものが2-opt 近傍である．
本稿では，１つの巡回路を対象とした場 合と，2つの巡回路を対象とした場合の，2 種類に分けて考える．
3 使用データ
3．1 ピックアップデータ
① ロケーションNo
倉庫の中には全部で13224個の棚が配置 されている．その棚の位置を知るために必 要なのがロケーション No である．ロケー ション Noは7桁の数で表されていて，上 ３桁は縦の位置情報を決めていて，下４桁 の内の上２桁が横の位置情報を決めていて，
残りの下２桁が棚の中のどこに置いてある かを決めている．この方法でロケーション Noを解析すれば注文位置を把握できる．
② 出荷先コード
このコードは注文先にそれぞれ１８桁の 番号を振ったものである．よってこのコー ドを見れば注文先がわかるということが今 回の問題では重要な役割をしている．
今回の問題ではいくら空きがあっても同じ コンテナには同じ注文先の品物しか入れら れない様になっている．この制約を満たし ながら最適化するために空きがあった場合 同じコードを探すことでコンテナの中身を 満たすことが出来るので非常に重要なので ある．
③ オーダー種別，国内海外区分
それぞれ２つのコードが割り当てられて いて区別できるようにしてある．
④ 出庫ラベル出力済時間
部品が回収された時間を表すものであ る．
⑤ 出荷指示バラ総数
注文されたそれぞれの部品数を表すも の．
⑥ グループコード
部品の種類や注文先に応じてグループ 分けして番号を与えたもの．
⑦ オーダー数
③と⑥の組み合わせによって運べる上 限を決めたものである．
例）1-S-Wの組み合わせならば７個まで．
など
4 データ解析とネットワーク構築
4．1 特有なピックアップ方法に対するア プローチ
今回の問題は回収するときに８個のコン テナに荷物を入れていきコンテナがすべて 埋まるか，回収場所がなくなったときに初 期点に戻ってくるようにすることとなって いる．それ以外のときに初期点に戻ってく ることはない．
コンテナにまだ空きがある場合，次のこ とを考慮していく．
・同じコンテナに入れるには以下の制約 を満たす必要がある．
・コンテナに荷物を入れる空きがあるこ と ・出荷先コードが一緒であること
5 回収ルートの最適化 5．1 回収のための制約条件
1． 宛て先と部品の組み合わせは決まっ ている．
2．国内海外区分，オーダー種別，グルー プコードの３つによって1回に回収できる 部品の上限は決まっている．
3． 1宛て先1コンテナを割り当てる．
4．カートに乗せるコンテナの数は8n個 とする．(nは 1，2，3，4のいずれかであ る) 5． あて先が同じでなければコンテナに 空きがあっても入れてはいけない．
5．2 回収方法の最適化
最適化を行わなかったときの結果が図１ ０，上記の制約をすべて満たし，反復させた 結果が図１１のようになる．
この結果から今回の問題において制約を満 たした最適解は，反復回数1回かつコンテ
ナの数が16コであるといえる．
図１０
図１１ 6 まとめ
本研究では，実際に国内国外に発送する補 修部品の倉庫のデータを用いて，すべての 注文商品を回収するための回収ルートの最 適化を行った．具体的には現在の倉庫の制 約と実際のデータの分析をして，より効率 の良い回収ルートを導けるようにした．今 回の問題で回収ルートの最短経路探索には 反復局所探索法である 2-opt 法を利用し，
最短距離を導きだした．次に倉庫のネット ワークを形成し，実際の倉庫と同じように 部品間の距離を測定しルートを探索できる ようにすることで現実に近い数値が出せる ようになった．そして実データを分析し，個 数が少ないものが多いという特徴を捉え，
コンテナの空きに無駄があることに気づき，
元の制約の中にあった送り先が一緒である ものを同一のコンテナに入れるようにする ことでコンテナの空き部分を少しでも減ら すことが可能になり，今回の問題の最適化 で大きな意味を成した．
今回の問題においての制約を満たしてい
き，2-opt法などを適用した結果として，コ
ンテナの数を16コ，反復回数は1回で最適 解が得られた．この解は部品の大きさや 1 人あたりの作業量などを考慮した結果も含 めたものなので今回の問題の最適解とした．
謝辞
本研究を進めるにあたり，多くのご指導と ご助言をいただいた中央大学理工学部情報 工学科の田口東教授，山形浩一助教授に心 から感謝いたします．
参考文献
[1] 棚橋優，今堀慎治，“配送計画問題に対 するデータベース付きメタ戦略”，数理解析 研究所講究録，2014．
