オーダーピッキングにおける商品の相関に基づく動的な商品配置方法

全文

(1)Vol.2016-ICS-183 No.18 2016/3/16. 情報処理学会研究報告 IPSJ SIG Technical Report. オーダーピッキングにおける商品の相関に基づく動的な商品配置方法伊藤佑介1,a). 加藤昇平1,b). 概要：近年，物流センターの大規模化が顕著となっている．物流センターでの作業のうち，オーダーピッキングにおける移動時間の割合が大半を占めているといわれている．オーダーピッキングの移動時間を短縮する方法として商品配置を変更する方法があるが，オーダーピッキング開始後に商品配置を変更することについてはこれまでに考慮されていなかった．そこで本研究では，オーダーピッキング開始後に動的に商品配置を変更する方法を提案し，その有効性を検証する．. 1. はじめに近年，インターネット通販の普及などにより物流セン. る研究は多く存在するが，オーダーピッキング開始後に商品配置を入れ替える方法はこれまでに考慮されていなかった．実際には，オーダーピッキング開始後に商品の注文頻. ターの大規模化が顕著となっている．物流センターは物流. 度や商品同士の相関が大きく変化することが考えられる．. の機能の大部分を担う働きをしている．物流センターの代. そこで本稿では，オーダーピッキング開始後における動的. 表的な例に Amazon がある．Amazon は多種多様な商品を. な商品配置変更手法を提案し，その有効性を検証する．. 自社の物流センターに持ち，現在ではインターネット通販の代表的な存在となっている．物流センターの大規模化に. 2. 従来研究. 従い，オーダーピッキングに従事する労働者の確保が難し. オーダーピッキングの移動時間は主に商品配置，集配経. くなってきているという現状がある．オーダーピッキング. 路，作業者への伝票割当に大きく依存する．従来研究で. とは，注文や出荷指示に応じて商品を物流センター内から. は，オーダーピッキングの移動時間の削減を目標に商品配. 取り出す作業である．このような現状の中で多くの企業が. 置，集配経路，作業者への伝票割当の 3 つを最適化する方. オーダーピッキングの自動化に関心を示しており，将来的. 法が主として行われてきた．商品配置の最適化では，注文. にはオーダーピッキングの大部分が自動化されることが予. 頻度の高い商品を作業者の初期位置近くに配置することに. 想される．また，物流センターの運営においてコストは重. より，オーダーピッキングの移動時間を削減している．移. 要な要因の一つである．物流センターの経営コストの内，. 動経路の最適化では，伝票内の商品を最短経路で取りに行. 顧客からの注文に従って商品を集めるオーダーピッキング. くことによって，作業者への伝票割当の最適化では，作業. にかかるコストが大部分を占めており [1]，オーダーピッ. 者へ適切な伝票を割り当てることによってオーダーピッキ. キングにかかる時間の半分が移動時間であると言われてい. ングの移動時間の削減が行われている．本稿では，この中. る [2]．オーダーピッキングの移動時間を削減することによ. でも商品配置の最適化に着目する．これまでに，商品配置. り，より多くの注文商品を処理することが可能なため，人. の最適化を行った研究は多く行われてきた，岩崎らは棚へ. 件費の削減や顧客の満足度の向上に繋がると考えられる．. の作業者の集中を避けるために人気商品を細かく分けて配. このような背景から，オーダーピッキングの効率化を目的. 置することによって，待機時間を減らすことが可能である. とした研究が多く行われている [3]．オーダーピッキングの. ことを示した [3]．また，南らは注文される商品の依存関. 効率化を目的とした研究の一つに商品配置の最適化が挙げ. 係を共起ネットワークで表し，生成された共起ネットワー. られる．オーダーピッキングにおける商品配置を最適化す. クを自己組織化マップにより棚の位置に写像する商品配置方法を提案した [4]．. 1. a) b). 名古屋工業大学 Nagoya Institute of Technology, Dept. of Computer Science and Engineering, Graduate School of Engineering, Gokiso-cho, Showa-ku, Nagoya-si 466–8555, Japan [email protected] [email protected]. c 2016 Information Processing Society of Japan ⃝. 2.1 従来研究における問題点従来研究ではオーダーピッキング開始後に商品の注文頻度・相関が変化する状況は考慮されておらず，オーダーピッ. 1.

(2) Vol.2016-ICS-183 No.18 2016/3/16. 情報処理学会研究報告 IPSJ SIG Technical Report. キング時に商品配置の入れ替えは行われていなかった．実. conf idence(X,Y) ≥ minconf. (5). 際にはオーダーピッキング開始後に商品の注文頻度や商品同士の相関が大きく変化し，オーダーピッキング開始後に. 相関ルールを導出した後，確信度が降順になるように並べ. も商品を入れ替えることでオーダーピッキングの効率が上. 替えを行い，またリフト値 < 1 である相関ルールは除外. がる可能性があると考えられる．. する．並べ替えた相関ルールを順に抽出し，その相関ルー. 3. 提案手法. ルを構成する商品を初期位置から最も近い位置かつ商品が互いに可能な限り近く位置になるように商品配置を変更す. 本稿では，オーダーピッキング開始後の商品の注文頻度・. る．なお，4.1 節における実験設定において，各商品配置. 相関が変化する状況を考慮し，オーダーピッキングにおけ. 変更作業において一度移動を行った商品は商品配置を変更. る動的な商品配置変更手法を提案する．本稿における商品. しない．. 配置の変更手法を示す．. 3.1 相関ルールを用いた商品配置変更手法商品の並び替えは既存手法である Complementaly-based method[5] に倣って行う．Complementaly-based method は最初に出現頻度を基に商品配置の入れ替えを行った後，共起頻度を基に商品配置を入れ替える手法である．本稿では，共起頻度ではなく相関ルールを用いて商品配置の入れ替えを行う．相関ルール (Association Rule) とは，ある事象 (X) の下である事象 (Y) が発生する関係であり X → Y と表される．本稿において，矢印の左側を前提部，右側を結論部とする．相関ルールを導出する際の指標として，支持度，確信度，リフト値の 3 つを用いる．支持度は全伝票のうち，前提部と結論部に含まれる全ての商品が含まれる伝票の割合であり，式 (1) で表される． support(X) =. X が含まれる伝票数全伝票数. (1). 確信度は前提部の商品が含まれる伝票のうち，結論部の商品が含まれる伝票の割合であり，式 (2) で表される．確信度が高いほど，前提部と結論部の商品は関連が強いと言える．. conf idence(X, Y ) =. X と Y が共に含まれる伝票数 (2) X が含まれる伝票数. リフト値はある商品 X の購買が他の商品 Y の購買とどの程度相関しているかを表す指標であり，式 (3) を用いて表される．また一般的にリフト値は 1 以上であるとき信頼度が高いと言われる．. X と Y が共に含まれる伝票数 X が含まれる伝票数 lif t(X, Y ) = Y が含まれる伝票数全伝票数. (3). また，相関ルールの探索には Apriori アルゴリズム [6] を用いる．相関ルールは商品の組み合わせであり，商品数が増加すると急激に増加するため全ての組み合わせの相関ルールを探索するのは困難である．そこで Apriori アルゴリズムを用いて効率的に相関ルールの探索を行う．Apriori アルゴリズムを用いる際，minsup，minconf を入力値として与え，式 (4)，(5) を満たす全ての相関ルールを導出する．. support(X ∪ Y) ≥ minsup c 2016 Information Processing Society of Japan ⃝. (4). 3.2 動的な商品配置変更手法オーダーピッキング時に動的に商品の並び替えを行うにあたって，相関ルールの探索を行う間隔 f をパラメータとして予め設定をする．エージェントが f 個の伝票を処理する度に処理された f 個の伝票なるデータ集合に対し Apriori アルゴリズムを適用し，頻出商品集合 F を抽出する．F から商品一つのみで構成される頻出商品集合 F1 を抽出し，前回の探索で抽出した商品一つのみで構成される頻出商品集合 F1 ´と比較する．両者に違いが見られた場合には相関ルールを導出し，3.1 節で示した方法を用いて商品配置の変更を行う．両者に違いが見られなかった場合には，相関ルールの導出を行わず商品配置の変更も行わない．. 4. シミュレーション実験提案手法の有効性を検証するため，実験を行った．実験において，確認する点は次の二つである．. • 商品の入れ替えにかかるコストαを変化させ，提案手法が有効であるαの範囲を検証する． • 相関ルールの探索を行う間隔 f を変化させ，最も効果的な f の値を検証する． 4.1 実験設定次のような問題を作成し実験を行う．物流センターは 11 × 11 マスで構成され，エージェント，棚はそれぞれ 1 マスの大きさを持つ．棚には商品が入っており，エージェントは棚に隣接する場合にのみ棚から商品を取り出すことができる．全エージェントは初期位置からスタートする．エージェントは初期位置で伝票を受け取り，伝票に従い商品を順にピッキングする．伝票内の商品を全てピッキングした後，初期位置へ戻り次の伝票を受け取る．また，伝票内の商品をピッキングした後，エージェントは自身の現在地から商品が入っている棚の中で最も距離が近い棚を順に訪問する．このとき，現在地から棚までの距離はユークリッド距離によって求める．エージェントは上下左右の 4 方向に動くことができ，エージェント同士の衝突は考慮せず同じマスに複数体のエージェントが存在することができる．また，目的の棚で既に他のエージェントが作業を行っている場合は，そのエージェントが作業を終えるまで待機状態に入る．待機状態に入ったエージェントは自分の順番が来. 2.

(3) Vol.2016-ICS-183 No.18 2016/3/16. 情報処理学会研究報告 IPSJ SIG Technical Report 表1 移動時間 tw. 各動作の作業時間 1[s/マス]. 1 ピッキング時間 tp 1 組の商品の入れ替え時間 ts. 3[s] (入れ替える商品が入っている棚間の距離) × 2 + α . 表 2 パラメータ設定エージェント数 x. 3. 伝票数 n . 1000. 棚数. 24. 商品の種類. 24. 1 エージェントが所有する伝票の最大数. 1. minsup. 0.25. minconf. 0.4. 図 1 シミュレーションの実行画面. 表 3 実験 1 における作業時間. 図2. ロングテール. るまで，動かずに待機する．複数の作業者が待機状態にあるときは，First-In-First-Out で棚への到着順にピッキングを行う．全ての伝票を処理し．全エージェントが初期位置へ戻った時点で，シミュレーションを終了する．図 1 はシミュレーションの実行画面であり，緑色はエージェント，赤色は初期位置を表す．提案手法を用いて商品配置の変更を行う際，全エージェントは一旦ピッキング作業を中止し商品配置の変更作業に専念するものとする．商品配置の変. 並べ替えなし. 58535. α=0. 55608. α=25. 57007. α=50. 58055. α=75. 59797. 4.3 シミュレーション条件シミュレーションにおけるパラメータを表 2 に示す．エージェント数 x は 3，伝票数 n は 1000 とする．棚数，商品の種類は共に 24 であり，一つの棚に一種類の商品が入っているものとし，商品の初期配置は実験開始時にランダムに決定される．エージェントは初期位置で伝票を一つ受け取り，Apriori アルゴリズムを用いる際の入力値 minsup， minconf はそれぞれ 0.25，0.4 とする．相関ルールの探索を行う間隔 f ，1 商品の入れ替え時間 ts におけるαは各実験ごとに個別に設定する．また作業時間は 10 試行分の平均とする．. 更が完了した後は，商品配置の変更を行う前の位置へ戻り引き続きピッキング作業に移る．伝票は一様乱数を用いて人工的に作成したものを用いる．伝票はロングテールの法則 [7] に従うものとする．ロングテールの法則は，Chris Anderson によって提唱された商品の売り上げに関する概念で，商品はヘッドと呼ばれる販売数が大きな少品種の商品と，テールと呼ばれる販売数が小さい多品種の少品種からなることである．ロングテールは図 2[8] で表され，縦軸は販売数横軸は商品を表し，緑色の部分がヘッド，黄色の部分はテールである．. 4.2 評価指標評価指標には全エージェントの作業時間の合計を用いる．エージェントの各動作の作業時間を表 1 に示す．エージェントの作業時間は tw ，tp ，ts の合計で表される．ts におけるαは商品の入れ替えにかかるコストであり，実験ごとにパラメータとして設定する．. c 2016 Information Processing Society of Japan ⃝. 4.4 実験 1 4.4.1 実験目的実験 1 では商品の入れ替えにかかるコストαを変化させ，提案手法が有効であるαの範囲を検証する．商品の入れ替えを行わなかった場合，α=0，α=25，α=50，α=75 の場合の 5 種類の作業時間を比較する． 4.4.2 パラメータ設定実験 1 におけるパラメータにおいて，探索を行う間隔 f = 100 と設定する．また伝票内において，500 伝票 (p = 500) を境に商品の出現頻度・相関を変更する． 4.4.3 実験 1 結果実験 1 の結果を表 3 に示す．結果よりα=0，α=25，α =50 の場合においては、並べ替えを行わなかった場合に比べて作業時間が短縮されていることが確認できる．このことから，今回の実験設定においてはα ≤ 50 の範囲においては提案手法は有効であるといえる．. 3.

(4) Vol.2016-ICS-183 No.18 2016/3/16. 情報処理学会研究報告 IPSJ SIG Technical Report 表 4 実験 2 の結果. [2]. p = 100. p = 250. p = 500. f = 50. 57000. 57045. 55748. f = 100. 57019. 57163. 55182. f = 200. 55849. 56297. 55254. f = 300. 57691. 57257. 57577. 4.5 実験 2 実験 2 では，相関ルールの探索を行う間隔 f を変化させ，最も効果的な f の値を検証する．商品の出現頻度・相関が変化するタイミングである p が 100，250，500 の場合の 3 種類の伝票を用意し，それぞれの伝票に対し相関ルールの探索を行う間隔が 50，100，200，300 とした場合の作業時間を比較する．. [3]. [4]. [5] [6]. [7] [8]. Tompkins, J. A., White, J. A., Bozer, Y. A. and Tanchoco, J. M. A.: Facilities Planning, Vol. 6 (1996). 岩崎幸安，鈴木育男，山本雅人，古川正志：物流センターにおける商品配置を考慮したピッキング作業の最適化，精密工学会学術講演会講演論文集，Vol. 2012, No. 0, pp. 461–462 (2012). 南賢一，古川正志，山本雅人ほか：注文商品の共起ネットワークを利用した商品配置方法の提案，情報処理学会研究報告. ICS,[知能と複雑系]， Vol. 2013, No. 10, pp. 1–6 (2013). W¨ascher, G.: Order picking: a survey of planning problems and methods, Springer (2004). Agrawal, R., Srikant, R. et al.: Fast algorithms for mining association rules, Proc. 20th int. conf. very large data bases, VLDB, Vol. 1215, pp. 487–499 (1994). Anderson, C.: ロングテール，早川書房 (2006). : Long tail-wikipedia. https://en.wikipedia.org/ wiki/Long_tail.. 4.5.1 パラメータ設定実験 2 におけるパラメータとして，1 商品の入れ替え時間 ts におけるα=25 とする． 4.5.2 実験 2 結果実験 2 の結果を表 4 に示す．実験結果より，f = 200 の場合に安定して高い効果が得られていることが確認できる．f の値が小さい場合に高い効果が得られなかった原因は，探索する間隔が短すぎるために正しい相関ルールの導出を行うことができなかったためと考えられる．また，f の値が大きい場合に高い効果が得られなかった原因は，探索する間隔が長すぎるために商品配置の変更をするタイミングが遅れてしまったためと考えられる．. 5. おわりに本稿では，オーダーピッキングの効率化を目標として，オーダーピッキング時における動的な商品配置方法を提案した．実験の結果から，適切なパラメータを設定することによって提案手法は有効であることが確認できた．また既存の商品配置手法と組み合わせることによっても，効果が得られると考えられる．. 5.1 今後の課題今後の課題として，今回対象とした物流センターは小規模なものであったため，より大規模な物流センターを対象とした実験を行い，実験結果が物流センターの形状や規模が変化した場合にも同様の結果となるかの検証を行いたい．シミュレーションにおいて，商品入れ替えを行う際は全作業者がピッキング作業を中止するなど現実的でない設定も見られたため，より現実的な実験設定の上での実験を行っていきたい．. 参考文献 [1]. Coyle, J. J., Bardi, E. J., Langley, C. J. et al.: The management of business logistics, Vol. 6, West Publishing Company St Paul, MN (1996).. c 2016 Information Processing Society of Japan ⃝. 4.

(5)