海运在运输体系中占据了极为重要的位置,是进出口贸易的重要运载通道。随着货物体量的持续攀升,码头间的竞争也日趋激烈。集装箱码头的作业效率是衡量其竞争力的重要指标,其中集装箱装船效率更是制约码头吞吐量的一个重要因素。由于集装箱到达码头时具有随机性,所以其在堆场的堆放情况不会完全符合装载计划的要求,这时就会出现翻箱。在同一条件下,一组翻箱操作更少的作业顺序往往具有更短的作业时间,可大大提升装船作业效率。因此,我们的目标便是在给定集装箱装船取箱顺序下,给出一个以翻箱操作最少为目标的作业顺序。本文提出了一种新的更紧的上界(Upper Bound)计算方式,使用前探(look-ahead)方法,在前D层完全分支获得所有可行节点,取节点中上界最小的值作为最终的上界。为了克服随着问题规模加大而造成的求解效率低的问题,本文从小规模问题的精确解中提取特征,通过数据挖掘的方式构造了剪枝器以提升大规模问题下的上界计算效率。针对所研究的问题,本文提出了改进的分支定界(branch-and-bound)算法以求取精确解,为了在短时间内获得大规模问题质量较好的解,本文提出了改进的束搜索(beam search)算法得到启发式解。两个算法均使用了所提出的新的上界。在精确算法中,我们变原本下界(Lower Bound)优先分支策略为上界优先分支策略;同时改进原本无目的的搜索方式。在启发式算法中,我们以上界为节点是否保留的评判指标。为了进一步提升算法效果,本文提出了若干无希望节点删除标准,同时针对上界相同时的节点保留,提出了不同于当前研究常用的随机选点的方法。本文通过详实的数值实验验证了新的上界计算方法可获得更好的上界;同时验证了带剪枝器的上界计算方法相较于不带剪枝器的上界计算方法更具运算效率。通过对比证实了有目标的搜索方法在求解精确解时探索的节点数和运行时间相比无目标的搜索方法更少,上界优先分支方法相比下界优先分支方法在探索节点数上更少。实验发现带关联分支剪枝器的上界在启发式算法中综合算法效果和运行时间而言表现最好,同时证明了所提出的无希望节点删除和相同上界时节点选择方法可提升算法效果。本文同时进行了分支深度D和集束宽度W的灵敏度分析,给出了实验结果。