随着我国经济的持续快速发展,港口集装箱吞吐量快速增加,港口码头集装箱拥堵和港口压船现象不断出现。如何提高港口集装箱码头的装卸速度和吞吐效率,从而减少船舶在港停泊时间成为我国集装箱码头的当务之急。在集装箱堆场,影响装船效率的主要因素之一是堆场翻箱问题,除了对装船时取箱过程中的翻箱问题进行优化,提高装船效率的另一种方法就是对集装箱进行预翻箱整理,使得集装箱的堆放顺序符合取箱顺序,以尽量减少取箱装船过程中的翻箱次数。本文以集装箱堆场单贝位出口箱装船时和装船前的翻箱过程为研究对象,对其进行优化,从而减少翻箱次数,达到提高集装箱码头装船效率的目的。本文首先介绍了集装箱堆场和(预)翻箱问题,分析了翻箱操作产生的原因和其造成的影响,分析了降低翻箱次数的重要性和解决方法；然后提出了集装箱堆场单贝位出口箱装船时翻箱问题的假设,构建了翻箱问题的整数模型,结合贝位规模和箱子数量不断变化的翻箱案例,利用分支定界精确算法对其进行了优化,并对优化结果进行了分析。鉴于集装箱堆场装船时翻箱问题属于组合优化问题,具有NP特性,在问题规模较大时利用分支定界算法难以或者无法在可以忍受的时间内得到最优解,因而本文针对装船时翻箱过程中落箱位置的箱位选取设计了启发式规则,利用visual c++编写了翻箱问题的程序,结合贝位规模及集装箱数量不断变化的翻箱问题随机案例,对其进行了优化,并对优化结果进行了分析,同时和分支定界算法的优化结果进行了比较,验证了其正确性。由于启发式算法本身的特性,其对问题进行优化得到的解只能是问题的近优解或可行解,本文基于问题空间搜索算法的思想对提出的启发式算法作了进一步改进。本文提出了集装箱堆场单贝位出口箱装船前预翻箱问题的假设,构建了装船前预翻箱问题的整数数学模型,利用分支定界精确算法对预翻箱随机案例进行了求解优化,并对优化结果进行了分析。优化实验结果及其分析表明：1)分支定界算法能够结合数学模型获得问题的精确解或最优解,但随着贝位规模及箱子数量的增大,时间成本呈指数增加；2)启发式算法及基于问题空间搜索的改进启发式算法,能在较短时间内得到问题的近优解或可行解；3)随着案例规模的增大,改进后的启发式算法能够较改进前的启发式算法得到质量更高的解。