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

doi:10.3778/j.issn.1002-8331.2010.01.003

计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (1): 7-10.DOI: 10.3778/j.issn.1002-8331.2010.01.003

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

王敏，李铁克

北京科技大学经济管理学院，北京 100083

收稿日期:2009-10-13 修回日期:2009-11-14 出版日期:2010-01-01 发布日期:2010-01-01
通讯作者: 王敏

Improved algorithm for warehousing entry problem based on constraint satisfaction

WANG Min，LI Tie-ke

School of Economics and Management，University of Science and Technology Beijing，Beijing 100083，China

Received:2009-10-13 Revised:2009-11-14 Online:2010-01-01 Published:2010-01-01
Contact: WANG Min

摘要/Abstract

摘要： 入库堆垛问题普遍存在于堆场作业管理中，是在货物数目和出库顺序已知的前提下，要求较长（重）的货物置于较短（轻）的货物下方，目标是实现占用垛位数最少。通过问题分析，将其归结为一类带顺序约束的A形装箱问题，并建立了约束满足模型，设计了嵌入经典装箱启发式的约束满足求解算法。实验表明，该算法对于求解复杂约束下的大规模堆场问题较现有的装箱启发式有一定程度的改善。

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

Abstract: 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.

Key words: stack selection problem, yard management, bin packing problem, constraint satisfaction, bin packing heuristics

中图分类号:

TP29

王敏，李铁克. 求解入库堆垛问题的改进约束满足算法[J]. 计算机工程与应用, 2010, 46(1): 7-10.

WANG Min，LI Tie-ke. Improved algorithm for warehousing entry problem based on constraint satisfaction[J]. Computer Engineering and Applications, 2010, 46(1): 7-10.

[1]	肖成龙，聂紫阳，王珊珊. 基于ParetoHeu和实例化失败统计的关联启发式方法[J]. 计算机工程与应用, 2020, 56(5): 57-64.
[2]	尚正阳1，顾寄南2，唐仕喜2，孙晓红2. 高效求解三维装箱问题的剩余空间最优化算法[J]. 计算机工程与应用, 2019, 55(5): 44-50.
[3]	张钧，贺可太. 求解三维装箱问题的混合遗传模拟退火算法[J]. 计算机工程与应用, 2019, 55(14): 32-39.
[4]	黄海1，李松斌2，3. 求解online packing problem的F-B绝对近似算法[J]. 计算机工程与应用, 2017, 53(11): 73-78.
[5]	崔文正. RCC8的一致分割及其算法[J]. 计算机工程与应用, 2015, 51(1): 143-150.
[6]	沈静，梅丹. 可满足实例的归结复杂度[J]. 计算机工程与应用, 2014, 50(22): 69-72.
[7]	朱臻1，高永明2，王斌2. 灵活准则地面测控资源约束满足模型研究[J]. 计算机工程与应用, 2014, 50(10): 260-265.
[8]	袁际军1，黄敏镁2. 基于UML与CCSP的产品配置方法[J]. 计算机工程与应用, 2013, 49(14): 1-9.
[9]	刘林浩1，杨鼎强1，王晨2. 一种带脆度的尺寸可变装箱问题[J]. 计算机工程与应用, 2013, 49(12): 263-266.
[10]	余蕾，陈国宏. 卸货顺序约束的单容器矩形装箱问题[J]. 计算机工程与应用, 2012, 48(28): 240-244.
[11]	张旭君，吕志民. 基于约束规划的一类排序问题通用求解方法[J]. 计算机工程与应用, 2012, 48(26): 219-224.
[12]	张春生1，2，李铁克1，2，王柏琳1，2，张文学1，2，3，孙彬1，2. 炼钢机器故障下炼钢-连铸调度DCSP建模与算法[J]. 计算机工程与应用, 2012, 48(22): 226-234.
[13]	赵艳艳1，2，李铁克1，2，王柏琳1，2. 求解加热炉调度的改进修复式约束满足算法[J]. 计算机工程与应用, 2012, 48(18): 23-26.
[14]	周秉利1，2，张群1. 钢铁企业生产能力平衡模型及启发式算法[J]. 计算机工程与应用, 2012, 48(15): 29-33.
[15]	曹大勇1，杨梅2，刘润涛3. 二维离线非旋转装箱问题的一个混合算法[J]. 计算机工程与应用, 2011, 47(7): 16-19.

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

Improved algorithm for warehousing entry problem based on constraint satisfaction

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics