摘 要

船舶在抵达码头前，港口的泊位调度是根据调度期间内计划船舶到港时间和相关信息为到港的船舶安排靠港泊位并为之分配服务的岸桥，从而使到港的船舶总的留港时间最小。

为了缩短集装箱码头的停留时间，提出了集装箱码头到港的停留时间最短的泊位和岸桥联合调度优化方法。船舶的留港时间包括船舶在港口等待泊位分配的时间和其在岸桥被服务的时间。加入岸桥分配后，由于船舶在靠泊后不一定马上能够分配有岸桥服务，因此船舶服务时间就分为等待岸桥时间和岸桥工作时间。于是将泊位调度与岸桥分配这两个有相互联系的问题联合在一起进行系统的分析，构建了泊位-岸桥联合调度模型。并基于遗传算法对所建模型进行算法开发。泊位调度、岸桥分配单独优化与联合优化效果的比较结果指出，对系统进行联合优化，有助于提高集装箱码头的运行效率。本文对集装箱码头泊位-岸桥联合调度问题的研究背景及研究现状的基础上进行剖析，并结合实际的案例，构建泊位-岸桥联合调度模型。

本文在对近几年来国内外对集装箱港口码头的泊位调度的研究现状基础上，对集装箱港口码头，混合整数规划模型和遗传算法的基本方法进行了阐述，并以此为基础建立泊位-岸桥联合调度的优化模型，分析了模型的影响要素、模型的假设等方面，并设计了算法设计，用实际案例对模型进行解释说明。

关键词：泊位，岸桥；联合调度；动态调度；遗传算法

Abstract

Before the ship arrives at the terminal, the berth scheduling of the port is based on the planned arrival time of the ship during the dispatch period and relevant information to arrange the port berth for the ship arriving at the port and to distribute the service to the ship. The port time is the smallest.

In order to shorten the residence time of container terminals, the shortest berth and shore bridge joint scheduling optimization method for container terminal arrival time is proposed. The port staying time of the ship includes the time the ship is waiting for the berth allocation at the port and the time at which it is served at the shore bridge. After joining the shore bridge allocation, since the ship may not be able to distribute the shore bridge service immediately after berthing, the ship service time is divided into waiting shore bridge time and shore bridge working time. Then the two interrelated problems of berth scheduling and shore bridge allocation are combined to analyze the system, and a berth-shore bridge joint scheduling model is constructed. The algorithm is developed based on the genetic algorithm. The comparison between berth scheduling and shore bridge allocation optimization and joint optimization results indicates that joint optimization of the system will help improve the operational efficiency of the container terminal.

This paper analyzes the research background and research status of container terminal berth-shore bridge joint scheduling problem, and combines the actual case to construct a berth-shore bridge joint scheduling model. Based on the research status of berth scheduling of container port terminals at home and abroad in recent years, this paper expounds the basic methods of container port terminal, mixed integer programming model and genetic algorithm, and builds berth-shore bridge based on this. The optimization model of joint scheduling analyzes the influencing factors of the model and the assumptions of the model, and designs the algorithm design to explain the model with actual cases.

Keywords:Berth, shore bridge; joint scheduling; dynamic scheduling; genetic algorithm

目 录

第1章 绪论 3

1.1研究背景及意义 3

1.2文献综述 3

1.2.1构建整数规划模型 3

1.2.2构建泊位-岸桥分配模型 4

1.2.3构建泊位-集卡-箱区三环节协调调度数学模型 5

1.3主要内容和技术方案 5

1.3.1研究目标 5

1.3.2研究内容 5

1.3.3技术方案及措施 6

1.4 本章小结 7

第2章 基本理论和方法 8

2.1混合整数规划模型 8

2.2遗传算法的基本思想 8

2.3遗传算法的基本运算过程 9

2.4遗传算法的特点 9

2.5适应度函数 9

2.6初始群体选取 10

2.7算法结合思想 10

2.8本章小结 10

第3章 泊位—岸桥联合调度模型的构建 12

3.1问题描述 12

3.2模型的影响因素 12

3.3模型假设 13

3.4模型建立 14

3.5本章小结 17

第4章 算法设计与实现 19

4.1案例说明 19

4.2遗传算法的实现 20

4.2.1染色体的结构与编码 20

4.2.2种群初始化 20

4.2.3适应度函数 21

4.2.4选择操作 21

4.2.5交叉操作 22

4.2.6变异操作 23

4.3结论 24

第五章 总结与展望 25

5.1总结 25

5.2展望 25

参考文献 26

致谢 27

第1章 绪论

1.1研究背景及意义

随着经济的发展，贸易的往来，港口这个环节以及产生的巨大的作用对于经济的发展。然而在集装箱码头运作过程中，港口首先面临的问题是制定泊位计划，即确定到达各船舶进入到各泊位进行装、卸集装箱作业的位置、次序和时间。制作出合适的泊位调度计划有助于往来的船舶的通过，在一定程度上减少港口企业的运营成本，还能够增加顾客的满意程度；同时也间接或直接地影响到集装箱港口其他后续环节的作业效率。随着港口作业需求量的不断增加，对码头的运营管理提出了更为新的要求。首先，集装箱港口需要和船公司提前进行沟通，并依据其提供的公司船舶的预计到港时间，以及其集装箱的装卸箱量，和港口目前自身的状况制定出泊位调度的一套方案。但是通常在我们制定完分配计划后，往往在集装箱码头进行作业时，出现不可预测的恶劣天气或者机械发生故障等一系列随机产生的干扰事件，因此出现此种现象时，通常会加大提前制定的泊位计划无法实行的可能。因此，这时需要制定出合适的泊位调度计划，以此来应对，当有较小的随机干扰事件发生时，能够依靠制定的泊位分配计划其本身的鲁棒性来减少这些干扰事件所带来的消极影响。因此，合理的制定出合适的泊位分配计划在目前的集装箱港口现状中已成为码头运作优化管理的不可或缺的一步。

1.2文献综述

针对相关港口泊位调度的研究，笔者对所查阅的相关中英文文献进行归纳和整理，并提取了一些代表性的研究文献，与此同时，作者还查看了算法上的书籍，如段海滨[1]《蚁群算法原理及其应用》。

泊位调度是指根据集装箱码头各个泊位的空闲情况和物理条件下的约束为到达港口的船舶提供停靠的泊位以及安排到港的船舶停泊的顺序。目前国内外关于集装箱港口的泊位调度这个问题已经进行了很深的研究，从最初的将泊位与岸桥这两个研究对象分别进行单独的调度到近些年来将泊位调度问题的研究从单纯的泊位问题调度的研究上转变为考虑了更多关于系统联合调度的因素。

1.2.1构建整数规划模型

2002年，Kap Hwan Kim^[2]就针对泊位调度问题，建立了混合整数规划 (MIP) 模型。将模拟退火算法应用于泊位调度问题，寻找接近最优的解。2006年，韩晓龙^[3]基于泊位资源关系到整个码头的作业效率。首先，其将泊位调度问题转变为一个在二维上进行装箱的问题，随后同时考虑码头泊位的数量与岸桥资源这两者之间的关系，构建出整数规划的模型，最后用案例检验该模型与算法的有效性。以此来提高集装箱港口的作业效率。2009年，韩笑乐^[4]将泊位分配和船舶开始作业的时间作为决策的变量，为提高集装箱港口的作业效率和船公司顾客的满意度 ，以船舶总在港时间与加权延迟时间之和最小为目标建立数学模型。并根据修改后的先到先服务等规则的启发式算法生成初始解，将模拟退火算法与禁忌深度搜索结合，设计出混合算法，对泊位调度的问题进行优化处理，以此来研究具有不同服务优先级别的船舶动态到达情形下的离散泊位调度问题。

1.2.2构建泊位-岸桥分配模型

2007年，张煜^[5]考虑到在继续泊位调度研究时，对岸桥的分配过程中，通过影响船舶的作业时间，进而从整体上影响到船舶在港的总时间，其在构建泊位分配模型的时候将岸桥的分配环节一并的考虑到所建模型之中，并以此建立了泊位调度的连续化动态模型。2008年，周鹏飞^[6]则是因为集装箱港口码头的岸桥对船舶的操作时间具有随机性，以及船舶到达港口的时间也具备随机性，因此他建立了面向随机环境的集装箱码头泊位-岸桥分配模型，并验证了其构建的模型能够模拟码头泊位-岸桥分配问题的随机决策环境并能反映决策者对待风险的态度和偏好，其算法在允许的运算时间内能获得稳定的满意解。同年，韩骏^[7]则是建立减少集装箱码头船舶在港的停留时间，并以此为目标的泊位与岸桥协调调度优化方法。将泊位与岸桥这两个环节进行系统化分析，并用免疫遗传算法对所建模型进行相应的算法开发。

2011年，靳志宏^[8]在已知集装箱码头的泊位的规模跟数量的前提下，结合排队论的理论建模，开发模拟迭代算法，来研究集装箱码头泊位资源动态配置优化。在对泊位进行调度时，船舶等待时间与岸桥服务时间有相互影响。同年，靳志宏^[9]将集装箱码头泊位与岸桥进行联合动态调度，建立动态环境下的泊位与岸桥联合调度优化 MIP（混合整数规划）模型。此外他还考虑到，如果泊位与岸桥之间频繁的进行转换，这样会极大的影响集装箱码头的作业效率，因此他将泊位跟岸桥分别划分为两个不同的集合，也就是说每个泊位都有其固定可用的岸桥与之相对的进行服务，以此来减少岸桥频繁的移动所造成的影响。2012年，Lu Zhen^[10]研究提出了一个双目标优化模型,以最大限度地降低成本, 最大限度地提高进度的鲁棒性。还开发了一种启发式方法来求解大规模问题案例中的双目标模型。2014年，陈超^[11]在已有研究的基础上，结合现有的实际情况，提出了出口箱随机入港下的泊位调度问题。然后，针对集装箱码头目前采用的多种装卸作业方式 ，将集卡的运输路径与泊位的调度的问题相结合在一起 ，建立了泊位调度优化模型 ，并开发了遗传算法的启发式算法进行求解。

2015年，zhen.lu^[12]从随机的角度出发, 提出了一种随机规划公式, 该公式可以处理船舶运行时间偏差的任意概率分布, 并得到一个鲁棒的公式适用于概率分布信息有限的情况。

1.2.3构建泊位-集卡-箱区三环节协调调度数学模型

邱建梅^[13]则是为提高集装箱码头的作业效率与减少集装箱码头的运作成本为研究目标，然后她根据在当前的竞争环境中产生的出口箱随机入港策略与中转箱临时随机堆放策略，分析出进行合理的集装箱分散的堆放会对集装箱码头的作业系统产生关键性的影响，随后将码头的多种作业方式进行考虑，及其多种方式并行的情况，从而提出了集装箱分散堆放下的码头泊位、集卡及箱区三个环节进行协调调度的方案。并且通过构建泊位、集卡、箱区三环节协调调度数学的模型和设计基于三层染色体编码的遗传求解算法，确立出其主要的求解技术的路线。王志意^[14]则认为以往的研究大多只以到港船舶在码头的总时间最小为研究目标，并没有考虑在进行作业操作时集装箱港口码头的资源使用的费用情况，因此他将集装箱船舶的在港口的总的时间成本，生产成本以及集装箱船舶延期所带来的惩罚成本的总体费用最小作为其研究目标。与此同时他也把集卡和岸桥的等待成本和船舶的延期成本纳入其研究的范围内，使得目标函数更为贴近实际的港口运作情形。随后他根据连续泊位-岸桥-集卡-箱区调度问题的特征，设计了有针对性的遗传算法，并在进行染色体编码、交叉和变异操作等各个阶段均采用分层的方式进行。为确保解的可行性，对每一个解都进行了检验，并对不可行解进行了基因修复操作。并用MATLAB软件进行遗传算法的程序编写并以此求解。吴发民^[15]将动态连续泊位分配问题由单码头扩展到多码头，建立满足多个码头对同一个港口进行泊位分配的数学模型，此外，这个数学模型重点考虑的是不同的码头的泊位水深不同的情况。

1.3主要内容和技术方案

1.3.1研究目标

本文旨在不确定环境下，设计并改进遗传算法，并根据该模型，结合实际数据，对模型求解验证，来优化码头泊位分配运作管理。

1.3.2研究内容

第一章为绪论，包括本文研究的背景及意义、文件综述、以及本文的目标、主要内容和技术方案。其中文件综述包括近几年来国内外对集装箱港口码头的泊位调度的研究现状，以及其各自采用的研究方法。

第二章为本文采用的基本理论与方法，包括集装箱港口码头一些基础设备的含义，混合整数规划模型概念以及遗传算法的基本思想及其算法特点。

第三章为泊位-岸桥联合调度模型的构建，包括对本文的问题的描述、以及对模型的影响因素的分析、模型的假设、以及对模型的建立这几个方面进行展开，对所建模型进行诠释。

第四章为本文的算法设计与实现，包括遗传算法的各个环节，并用实际案例对模型进行解释说明。

第五章为本文的总结与展望，即对本文进行总结，并对今后的研究，应对泊位-岸桥-集卡等其他系统的联合协调提出展望。

最后是致谢，致谢家人、老师，朋友帮助我成长，鼓励我顺利完成学业，针对很感谢他们在我完成本篇文章时给予我的帮助。

1.3.3技术方案及措施

首先先进行大量的国内外文献的阅读，大概的了解相关的研究现状，并在学习的过程中明确出本问题的研究内容与其研究的意义。随后在查阅相关文献了解并掌握码头运作流程及其运作的模式，最后根据所研究的问题，分析出泊位分配的影响因素。最后就是构建出随机环境下泊位分配的数学模型。并设计求解算法，再用案例进行验证。本文的技术路线如图1.1所示。

图1.1 研究技术路线

1.4 本章小结

本章分析了泊位联合调度问题的研究背景及意义，掌握了其国内外研究现状，了解了泊位-岸桥联合调度问题的研究是有实际意义的，总结出本文的主要研究内容及其研究的思路，并依据研究内容规划出本文的组织结构。并在前人的基础上，总结其经验，构建算法模型，对所查阅的相关文献进行整理与归纳，提取其中具有代表性的文献进行参考，并从不同的研究角度对这些文献进行总结，比较他们之间的差异性，以及其各自设计的算法的对所研究问题的优点，和他们各自的研究方向，比如以总的在港时间最小为目标进行优化，再如是以总的在港时间成本（包括船舶在港口的总的延时成本，港口的运营成本）最小为目标的。然后对这些文献各自的研究方法进行分析比较，如有些文献采用的是模拟退火的算法，而有些则是采用的遗传算法、蚁群算法。通过对不同的文献的阅读，能够更好的把握所研究的问题的方向。除此之外还给出了本文的技术路线，先对所要研究的问题进行文献查阅，然后了解并掌握集装箱码头的运作情况，翻阅资料之后，确定本文以船舶在港口的总时间最小为目标函数，然后对所研究的问题进行算法学习，并建立数学模型，通过对MATLAB软件的学习，编写遗传算法的程序，最后在采用案例对所建的模型进行检验，以此来完成本篇文章。