あき空間の制約論理による表現とpackingへの応用

概要

論文の詳細を見る
packing問題は、宅配業務や倉庫の荷物管理など積み上げ問題を扱う分野の中で配置問題の一つとして位置づけられ、効率が良く、また経済的な配置を実現する方法が求められており、さらに、様々な要求に対して対応できるようなシミュレータの開発が望まれている。物体を配置するとき、あき空間が全く無いように配置できる問題は、単純なバックトラック法で解くことも可能であるが、あき空間が存在するような不完全なpacking問題では、配置位置にずれが生じるため位置の自由度が大きくなり、問題を解くことが非常に困難となる。そこで、探索空間の縮小を基本概念とする制約論理に基づいてpacking問題を解くことを考えた。本稿では、packing問題に制約論理に基づいた無矛盾性と制約伝播の考察を行うとともに、新しい手法について提案する。また、2次元空間へできるだけ高さが低くなるように正方形をPackingする問題へ、いくつかのヒューリスティックを適用しシミュレータの開発を行った。その結果、制約論理による問題縮小の有意性とヒューリスティックによる有効性を確認できた。
一般社団法人情報処理学会の論文
1995-09-20