求解入库堆垛问题的改进约束满足算法  

Improved algorithm for warehousing entry problem based on constraint satisfaction

作　　者：王敏[1] 李铁克[1] 

机构地区：[1]北京科技大学经济管理学院,北京100083

出　　处：《计算机工程与应用》2010年第1期7-10,共4页Computer Engineering and Applications

基　　金：国家自然科学基金No.70771008;No.70371057~~

摘　　要：入库堆垛问题普遍存在于堆场作业管理中,是在货物数目和出库顺序已知的前提下,要求较长(重)的货物置于较短(轻)的货物下方,目标是实现占用垛位数最少。通过问题分析,将其归结为一类带顺序约束的A形装箱问题,并建立了约束满足模型,设计了嵌入经典装箱启发式的约束满足求解算法。实验表明,该算法对于求解复杂约束下的大规模堆场问题较现有的装箱启发式有一定程度的改善。To deal with stack selection problem with the known item numbers and retrieval order during the loading process,in which the longest（and/or heaviest） incoming items are placed at the bottom in needed and the target is to occupy as few stacks as possible.This problem is reduced to an extension of bin packing problem named A-shaped bin packing problem with ordered constraint.This is a new combinatorial optimization problem which has many applications in practice, such as in warehousing stack entering in the yard management.A constraint satisfaction model is given,and a hybrid solving algorithm is designed based on constraint satisfaction technology embedding with Best-Fit approximation algorithm.Simulative examples illustrate the effectiveness of the proposed algorithm for large-scale storage yard problem with complex constraints over the existing bin packing heuristics.

关 键 词：堆垛问题 堆场管理 装箱问题 约束满足 装箱启发式 

分 类 号：TP29[自动化与计算机技术—检测技术与自动化装置]