求解集装箱堆场堆垛问题的约束满足算法

集装箱堆垛问题普遍存在于港口码头堆场作业管理中,是在集装箱数目已知的前提下,要求满足交货期限制、重量限制以及垛位高度限制等约束条件,目标是实现占用垛位数最少。通过问题分析,将其归结为一类带顺序约束的装箱问题,并建立了约束满足优化模型,设计了嵌入经典装箱启发式原则的约束满足求解算法。为了验证模型和算法的可行性和有效性,根据某集装箱码头堆场的实际生产情况构造测试算例,实验结果表明,该算法对于实现垛位数最小化、求解复杂约束下的大规模堆场问题较现有的装箱启发式有一定程度的改善。

Constraint Satisfaction Technology for Container Stacking Problem in Container Yards

To deal with stack selection problem for containers in the yards with the known its numbers,in which the constraints such as date of delivery,weight and height of stack location were considered and the target was to occupy as few stacks as possible.Based on the characteristics of problem,it was reduced to a bin packing problem with ordered constraint.This is a new combinatorial optimization problem which has many applications in practice.A constraint satisfaction model was given,and a hybrid solving algorithm was designed based on constraint satisfaction technology embedding with Best-Fit approximation algorithm.At last,by the data simulative examples of container terminal,simulation results illustrate the effectiveness of the proposed algorithm for large-scale storage yard problem with complex constraints over the existing bin packing heuristics.