集装箱港口作业驱动的排序模型与算法

The operations management in a container terminal is one of the most important issues that affect the terminal’s productivity and competitiveness. With the process of economic globalization, the large material flow and complicated operations scheme are bringing a tough challenge to academia. In recent years, OR methods have received considerable importance for the operations management in container terminals. From combinatorial optimization, especially the scheduling perspective, this project mainly studies some optimization problems that occur in berth allocation (BA) and quay crane scheduling (QCS), including BA with transshipment, BA integrating quay crane assignment, QCS with non-interference constraints, coordinated QCS with yard planning and so on. For each problem, we first formulate it into a scheduling model, and then study the computational complexity. Polynomial time approximation algorithms are designed for those (strong) NP-hard problems, while online algorithms are designed for online problems. The performance ratios of algorithms are analyzed. Finally, we provide heuristics or exact algorithms with numerical analysis. By studying problems that arise in container terminals, the project not only branches out scheduling theory, but also brings some new ideas and methods into it. It is greatly expected to achieve original results.

集装箱港口作业管理是影响港口生产力和竞争力的关键因素，经济全球化使得港口的物流量迅速增长，作业流程尤其复杂，从而对学术界提出了更加严峻的挑战。近年来，运筹学方法的应用逐渐成为港口作业管理研究的主要方向。本项目从组合优化特别是排序论这一视角研究由泊位分配和岸桥调度等重要港口作业驱动的优化问题，包括结合转运的泊位分配，集成岸桥分派的泊位分配，无干涉作业的岸桥调度以及协同堆场作业的岸桥调度等。核心内容是建立这些优化问题的排序模型，证明问题的计算复杂性；设计（强）NP-难问题的多项式时间近似算法和在线问题的在线算法，分析算法的性能比；设计启发式算法或精确算法，并进行数值分析。谋求在解决港口作业的具体问题的同时拓展排序理论的研究空间，为排序理论的发展提供新思路、新方法，争取若干原创性的新成果。

集装箱港口资源的有限性、作业的时效性使其与排序理论存在天然联系，本项目就是利用排序甚至组合优化方法研究泊位分配和岸桥调度等重要港口作业驱动的优化问题。通过引入柔性序约束、部分无交叉约束，建立了混合整数规划模型，提出了港口作业排序的若干新模型，设计了基于启发式规则的近似算法，并给出了算法的最坏情况分析和基于随机试验的数值分析。港口作业排序的本质是带有序约束图或冲突图排序的拓展，其中冲突图排序又与路径划分、三角形填充、路径点覆盖等问题密切相关。利用图的最大匹配、最大路-圈覆盖、最大独立集构造初始可行解，通过贪婪、组合、局部搜索等方法产生改进解，最终得到了上述排序和图优化问题的具有近似性能保证的多项式时间算法。因此，本项目不仅对集装箱港口作业管理的实际问题提出了直接有效的解决办法，而且据此发展了组合优化和排序理论，既有广度又有深度，成果丰富，达到了项目的预期目标。