本文是一篇物流论文，本文的创新之处在于：现阶段，以我国实际背景和场景为基础的煤炭港口调度研究集中在软件仿真、规则启发式研究方面，或将动态的调度问题转化为静态求解，这些方法都忽略了问题本质的动态性。
第1章 绪论
1.1 研究背景及意义
1.1.1 研究背景
2020版的《Statistical Review of World Energy》[1]报告显示，由于全球经济低迷，全球能源市场的增速在2019年呈现出了放缓趋势，这种趋势在上一年增长强劲的美国、俄罗斯和印度等国家中表现得尤为明显。而中国却例外地在同年加速了对能源的消耗，并在全球能源市场的扩张中占据了主导地位。在能源结构方面，可再生能源和天然气正在逐步取代煤炭在能源结构中的占比，煤炭的消费量也迎来了过去六年里的第四次下降。然而，以中国、印度尼西亚和越南为首的新兴经济体的煤炭消费量仍在不断增长，与消费量一样，这些国家的煤炭产出量也有较大增幅。长期以来，煤炭在我国能源消费总量的占比一直居于首位，且体量十分庞大，中国作为世界上最大的煤炭生产与消费国，在2019年的煤炭产出和消费量均达到了全球总量的一半以上。结合目前的经济发展状况可以看出，煤炭作为我国现行的主要能源，对于我国国民经济稳定发展有着不可忽视的作用。
1.2 国内外相关研究现状
1.2.1 煤炭港口调度研究
目前，关于港口调度问题的研究集中在集装箱港口[6-9]，而散货港口，更确切地说对于煤炭港口的研究较少。如前文所述，煤炭港口的运作模式可分为拉动式和推动式两种，针对不同模式下的煤炭港口调度问题研究的侧重点也有所不同。
1.2.1.1 拉动式港口研究
拉动式港口的研究可分为精确算法[10,12]和启发式算法[13,14]两个方向。精确算法的研究使用包括列生成[10]、分支定价[10]和benders分解[12]等在内的经典线性规划算法来求解模型，但鉴于港口调度问题的动态性和复杂性，这类算法想要达到较好的效果往往依赖于模型简化。文献[10]针对巴西散货码头的主要作业环节，构建了一体化的混合整数规划（Mixed Integer Programming，MIP）模型，并设计了一种基于列生成和分支定价思想的精确算法，该算法能够保证求解小规模算例的最优性，但求解大规模算例时只能得出相应的界。考虑到拉动式煤炭港口中的煤堆矩形在堆场的时空布局类似于二维装箱问题，有学者将其转化为了带特殊约束的二维装箱问题（Two-Dimensional Packing Problem），并用约束规划（Constraint Programming，CP）范式对其进行建模。为了对比MIP和CP两种优化范式在煤炭堆场空间调度问题的表现性能，文献[11]在需求已知的条件下，分别使用MIP和CP对堆场空间、堆垛设备和取料设备等堆场资源进行建模求解，通过计算实验证明了CP的求解效果更好，并对CP求解器的多种约束传播机制和求解策略组合进行对比实验，得出了求解该类问题的最优策略设置。由于CP只能处理整型变量，在处理调度问题时会丢失部分的时态结构，因此，文献[12]结合两种规划范式的优势，将整体问题进行分解，分别用MIP和CP对港口调度主问题和堆场调度子问题进行建模，并提出一种基于benders分解的精确算法来提高模型求解效率。上述的文献[10]和[12]的决策时间步长均为1h，相较之下，启发式算法能以更细的时间粒度实现对港口作业的精准调度。以典型的拉动式煤炭供应链HVCC（Hunter Valley Coal Chain）为例，文献[13]提出一种基于贪婪思想的遗传算法，该算法从全局和系统角度考虑了更全面的港口调度问题，并实现了煤炭出港作业在时空维度的连续调度。结合精确算法和启发式算法的优点，文献[14]以港口堆场为核心节点分别建立了煤炭供应的MIP和CP模型，通过滚动时序方法获得问题的初始解，并设计了一种大规模邻域搜索算法对解进行改进，计算实验表明，CP的自定义搜索策略机制让其在求解中表现出更优异的性能。
第2章 相关领域知识
2.1 煤炭出港作业调度概述
2.1.1 煤炭出港作业调度问题定义
煤炭出港作业调度问题在不同的研究背景和场景下有着不同的含义。除了包含对港口设备资源的调度外，在拉动式运作模式下，煤炭出港作业调度的内容还包括港口堆存空间方面的决策；而在推动式运作模式下，煤炭出港作业调度的内容则涉及到船舱对配煤方案的选择。
本文是以我国煤炭港口的实际运作状况为基础，针对推动式运作模式下的煤炭出港作业调度问题进行的研究。问题的主要内容包括船舱对配煤方案选择以及港口作业设备的调度，并且涉及到的决策内容充分考虑到了调度问题的动态性本质。可以看出，本文所指的煤炭出港作业调度问题具有特定的研究范围和内涵，这里将其定义为“配煤与装船协同调度优化”问题，后文提到的煤炭出港作业调度问题均与这个定义等价。
2.1.2 港口的空间与设备布局
煤炭出港作业调度问题涉及到的调度对象众多、作业环节繁杂，为了帮助更好地理解问题发生的场景，本节将从堆场布局、码头前沿布局以及设备连接关系三个方面分别进行介绍。
2.1.2.1 堆场布局
堆场是煤炭港口中原煤暂存的区域，不论是在输出型煤炭港口，还是输入型煤炭港口，堆场都是至关重要的部分。除了具备仓储功能外，堆场还是煤炭供应网络的集散中心和完成运输模式转换的中间节点。因此，堆场在煤炭供应链中兼具了储存、调节供需和运输模式转换三大功能：
（1）储存：大部分来自矿区的原煤到达港口后，并不会直接装载到船舶上运走，而是先堆存在堆场中，当有船舶到港产生需求时才会被取走。在推动式的运作模式下，堆场储存的原煤能够应对突发的需求，使港口具备了一定的快速响应能力。
（2）调节供需：港口储存的是种类有限的原煤，而煤炭的用途多种多样，不同的使用场所对煤炭属性、品质的要求也各有差异。为了以有限的品种满足客户多样化的需求，煤炭港口在出港调度中增加了配煤环节，配煤是将不同的原煤品种进行组合，通过调整组合中的原煤比例生产出符合客户需求的合同煤种的过程。配煤赋予了港口生产、加工的属性，使港口能够通过灵活选择多种配煤方案来调节推动式运作模式下的煤炭供、需不匹配问题。
2.2 约束规划的基本理论
约束规划源自于人工智能和计算机科学领域，是一项集成了人工智能、运筹学以及图论等多种理论的优化技术。1965年，Golomb发表了关于回溯规划[45]的研究，以此为开端，约束规划作为一种新的优化范式出现并得到研究。
2.2.1 表示形式
约束规划的经典形式可以定义为约束满足问题（Constraint Satisfaction Problem，CSP）[46,47]，一个CSP问题可以表示一个三维数据P=⟨X,D,C⟩，其中X是变量集合，用n维元组X=⟨x1,x2,…,xn⟩表示，D=⟨D1,D2,…,Dn⟩是与变量相对应的域的集合，即xi∈Di，求解CSP时需要满足的t个约束用元组C=⟨C1,C2,…,Ct⟩表示。问题P的一个解可以表示为A=⟨a1,a2,…,an⟩，其中ai∈Di，并且A满足集合C中所有的约束条件。假设问题P所有的可行解构成了集合sol(P)，P的求解目标是从sol(P)中找到一个可行解，或者证明sol(P)为空，即问题P不可行。
经典的CSP可以通过特化或泛化形成不同的变型，其中一种重要的特化变型是将D中所有的域限定为有限集合，即有限域（Finite Domain，FD）问题[48]。CSP的另一种重要特化变型是布尔可满足性（Boolean Satisfiability，SAT）问题[49]，SAT问题中的约束都被表示为子句（Clause），域都被限定为布尔类型{T,F}。3-SAT问题，即约束（子句）含有的变量维数小于或等于3的SAT问题，已经被证明是一个NP难的决策问题。
经典的CSP问题可以推广到一种重要的泛化变型——约束优化问题（Constraint Optimization Problem，COP）[50]。COP保留了CSP的基本组成，同时增加了一个表示成本函数的变量，标准形式的COP要求最小化这个变量，COP变型使约束规划的求解范围扩展到了优化问题。
第3章 煤炭出港作业调度问题的数学描述 ........................... 1
3.1 问题分析 .............................. 1
3.1.1 问题描述 .................................... 1
3.1.2 调度特征分析 ........................................ 2
第4章 求解策略与算法设计 .............................. 1
4.1 模型求解策略研究 ..................................... 1
4.1.1 搜索树生成 ..................................... 1
4.1.2 求解策略分析 ...................................... 2
第5章 计算实验与案例分析 ....................................... 1
5.1 计算实验 ............................................... 1
5.1.1 数据来源与设计 ................................ 1
5.1.2 实验环境 ..................................... 3
第5章 计算实验与案例分析
5.1 计算实验
煤炭出港作业调度问题是从我国现阶段的煤炭供应实际中抽象而来，为了更好地对问题展开研究，本文根据现实世界数据随机生成了两组不同规模的标准测试数据集A和B，分别对上一章提出的策略和算法进行计算实验，每组数据集包含10个算例。需要说明的是，CP只能处理整数，因此计算实验中使用的数据均为整数类型。
5.1.1 数据来源与设计
算例中的数据主要由两个部分构成：场景数据和客户需求信息数据。场景数据包含了港口结构和进行调度时的港口初始状态信息，场景数据对应建立的调度模型，其复杂程度决定了模型求解的难度；客户需求信息数据是规划期内所有提名信息的总和，其包含的数据量直接影响了问题规模的大小。关于两部分数据的来源和设计思路将在下面进行详细说明。
5.1.1.1 场景数据
本文所使用的场景结构是基于国内某大型煤炭港口的实际情况转化而来，港口初始状态则是根据港口结构按一定规则随机生成。
（1）港口结构：结构中定义了2个储煤区域和4个码头前沿，其中大、小码头前沿各2个，大型的码头前沿中设有3台装船机和3个大吨位泊位，小型的码头前沿中设有1台装船机和1个小吨位泊位。一个储煤区域中分布有5个条形堆场，并分别与一大一小两个码头前沿相连。如表5-1所示，港口结构中共计有10个条形堆场、97个垛位、15台取料机、8台装船机以及8个泊位（6个大吨位泊位，2个小吨位泊位）。
第6章 总结与展望
6.1 全文总结
煤炭作为我国最重要的一次能源，在过去几十年间，支撑了我国经济的飞速发展。特殊的地理特征和发展历程造就了我国现有的“北煤南运”和“西煤东调”的运输格局，港口作为煤炭供应链的核心节点，协调着整个供应链网络的动态平衡。十四五规划后，我国提出了推动数字经济和实体经济深度融合的目标，自动化、智能化技术将进一步为港口赋能。煤炭作为极具代表性的大宗散货，煤炭港口的发展也将受到关注，以运筹优化和人工智能为基础的理论和技术也会逐渐渗透到港口的日常运作管理中。
煤炭港口是一个复杂的物流系统，其内部作业调度也极具动态性，近年来，不乏有学者对相关问题进行了研究，但都难以用动态的视角深入到调度层面的问题。基于此，本文以煤炭港口中最为重要的出港作业调度问题为研究内容，从问题分析、模型构建、求解算法设计和案例分析等方面对问题进行了详细探讨。论文的主要研究成果和创新点如下：
（1）对煤炭出港作业调度问题进行了详细剖析和梳理
详细梳理了推动式运作模式下的煤炭出港作业调度问题的全部流程和决策内容，通过对实际生产数据的分析，提炼出了生产作业场景中的关键要素与系统行为特征，首次提出并定义了“配煤与装船协同调度优化”问题。
（2）建立了煤炭出港作业调度问题的数学模型
以图形化的方式对问题的调度场景和决策过程进行了清晰描述，并以此为基础，利用目前在求解调度问题上具有领先性能的约束规划方法对问题建立了完整的逻辑关系模型，并探讨了模型在更大范围生产场景下的扩展应用。
（3）模型的求解策略研究与变邻域搜索算法设计
通过对约束规划方法求解原理的分析，从分组顺序、变量选择策略和值选择策略三个维度对模型的求解策略进行了实验设计，并设计了一种改进的变邻域搜索算法来增强CP模型处理大规模实例的性能。
参考文献（略）