閾値を動的に調整する閾値受理法とGraph-based Heuristicsを用いた自動ピッキングシステムの運用計画法

カテゴリ: 部門大会

論文No: PS5-10

グループ名: 【C】2022年電気学会電子・情報・システム部門大会

発行日: 2022/08/24

タイトル(英語): A Solution Method Combining Threshold Accepting and Graph-based Heuristics for Operational Planning and Scheduling Benchmark Ploblems in an AutomaticPicking System

著者名: 上嶋 克也（千葉大学）,牧野 瑠佳（千葉大学）,中間 公啓（千葉大学）,小圷 成一（千葉大学）

著者名(英語): Katsuya Uejima (Chiba Univercity),Ruka Makino (Chiba Univercity),Kimihiro Nakama (Chiba Univercity),Seiichi koakutsu (Chiba Univercity)

キーワード: 閾値受理法|シミュレーテッドアニーリング|グラフ理論グラフ理論|Threshold Accepting|Simulated Annealing|Graph Theory

要約(日本語): 自動ピッキングシステムの運用計画ベンチマーク問題に対して、Meta-heuristicsの一つであるSimulated Annealing(SA)やグラフ理論を応用したGraph-based Heuristics(GbH)が提案されている。しかし、前者は確率的最適化による大域的探索により良好な解が期待できる一方、計算時間が多大である。後者はグラフ理論に基づく決定論的計算処理により高速に解が得られる一方で、一部の決定変数の最適化に課題がある。また、SAとGbHを組み合わせた手法も提案されており、従来のSAやGbHを単体で用いた場合と比べ良好な解を生成できる一方、現実的な時間内での計算が困難である。そこで、本研究ではThreshold Accepting(TA)とGbHを組み合わせた手法を提案する。計算機実験の結果、現実的な時間内で良好な解を生成できた。