本文是一篇物流管理论文，本文所研究的是动态开放垛位模式下的煤炭堆场空间调度问题，只适用采取动态开放垛位模式对堆场场地空间进行划分的煤炭港口，具有一定局限性。现实中，还有很多港口采取了静态的固定垛位模式来对堆场场地空间进行划分，针对这类港口的堆场空间调度问题，还有待进一步的研究。
第 1 章 绪论
1.1 研究背景及意义
1.1.1 研究背景
煤炭是重要的化石能源，也是工业革命以来人类社会的主要能源之一。2018年全球一次能源消费中，煤炭占比 27.2%[1]。由于我国富煤贫油少气的能源分布特点，我国的能源结构极度依赖煤炭，是世界上最大的煤炭生产国和煤炭消费国。图 1-1[2]是 2009 年以来我国能源生产与能源消费的组成结构，可以看出，尽管由于能源供给侧调整 2014-2016 年煤炭生产量和煤炭消费量有所下降，但自 2017年开始，煤炭生产量和煤炭消费量开始恢复增长；长期以来，煤炭在我国的能源结构中都占据着主导地位。因此，煤炭的生产和运输对我国社会民生和经济发展的稳定有着不可忽视的作用。
图 1-1 我国能源生产与消费结构组成
我国的煤炭资源主要分布在山西、陕西、内蒙古西部地区，而我国南方地区、东部沿海地区又是煤炭的主要需求地，供给点与需求点分离的市场结构直接造成我国“北煤南运”和“西煤东调”的运输格局。在煤炭运输方式的选择上，水路运输运力充足、成本低的特点契合了煤炭的大宗散货属性，有效弥补了铁路运输运力不足的缺点，与铁路运输组成的铁水联运方式是当下我国煤炭的主要运输方式，具体表现为：三大煤炭产地的煤炭通过大秦线、包神、神朔、朔黄铁等运往秦皇岛港、黄骅港、天津港、京唐港等煤炭下水港口，再通过水运运往东南沿海港口。
...........................
1.2 国内外相关研究现状
1.2.1 煤炭堆场调度研究
煤炭堆场调度是对煤炭堆场资源的分配，即根据堆场核心资源——场地空间大小、堆料机、取料机、皮带机的容量，将其分配给堆场即将进行的作业任务，尽可能使得堆场的这些资源能最大化地服务于堆场的生产活动，从而提高堆场的吞吐量和作业效率。根据煤炭堆场资源的组成，煤炭堆场的调度主要包括煤炭堆场设备的调度和煤炭堆场空间的调度以及二者的联合调度。
1.2.1.1煤炭堆场设备调度研究
在堆场设备调度的研究中，部分学者聚焦于煤炭堆场中的单一设备，利用仿真技术或启发式算法来研究其调度。Hu 和 Yao[3]以堆、取料机的调度为研究对象，在尽可能缩短完工时间的目标下，利用结合了贪婪指派策略的遗传算法来优化堆、取料机的调度，并应用于实际案例得到了较好的结果。Enrico 等[4]针对取料机的调度，以最大化取料机的取料完工时间为目标函数，建立取料机移动的时空图，研究了是否带有顺序约束、是否带有位置约束两两组合下单台、双台取料机调度的八种情况。Vianen 等[5]对堆取料机的作业建立仿真模型，通过仿真软件进行优化对堆取料机重新调度，减少了火车在干散货码头的等待时间，提高了干散货码头的性能。随后，Vianen 等[6]又针对皮带机设备，考虑网络连通性、存储策略和随机分布等影响参数，利用仿真模型来设计散货码头的皮带机网络，实验结果表明增加堆垛之间的冗余性相对最大化连接点的数量而言，对提高皮带机设备网络的效率更有效。还有学者则将堆场设备与煤炭码头的其他设备结合进行研究。颜佳佳[7]针对黄骅港煤炭码头，从实际数据出发，以堆料机、皮带机、翻车机等元素构建仿真模型，利用 Witness 仿真软件进行分析，发现堆料机设备存在严重的作业不均衡现象。刘巧斌[8]针对中转型煤炭码头，集成卸船、堆场、装船等作业系统，研究堆取料机、泊位等资源的联合调度，设计了基于启发式规则的遗传算法有效求解了其建立的数学模型，并应用于实例案例，为煤炭码头装卸作业系统的集成调度与优化提供了新思路。胡大勇[9]以考虑装船机、卸船机、堆取料机设备，通过分析码头并行设备顺序作业时间和作业流程排斥的约束，建立了散货码头并行设备调度问题的优化模型，并设计了单一队列式编码的遗传算法，以有效的速度对问题进行了求解。
............................
第 2 章 相关理论基础
2.1 煤炭堆场空间调度问题
2.1.1 煤炭堆场概述
煤炭港口是煤炭流通过程中水路换装的枢纽，是煤炭供应链的核心节点，其基本功能是煤炭的中转和装卸。而煤炭在港口进行中转时，由于上游火车与下游船舶到达港口的时间和运输煤炭的数量均有所差异，无法直接完成换装作业，故需规划一定的场地来暂时堆存煤炭，以满足煤炭在港口的中转。煤炭所堆存的场地区域和设施设备所组成的作业单元就是煤炭港口的堆场。
煤炭港口是煤炭流通过程中水路换装的枢纽，是煤炭供应链的核心节点，其基本功能是煤炭的中转和装卸。
随着港口的蓬勃发展，煤炭堆场已经从单一的存储场地演变为具有集散、缓冲、调节等功能的现代化、综合性的堆场，成为整个煤炭港口的核心部分。具体体现为：
（1）集散功能
考虑到火车、船舶、港口的不平衡，除了极少量煤炭采取直接换装作业以外，大部分煤炭在进入港口之后，都是先堆存在煤炭堆场场地，然后再通过其他作业间接完成换装作业的。
（2）缓冲功能
在目前我国煤炭的运输工具中，船舶的装载量要远小于火车的装载量，为了节省船舶在港口等待的时间，提高装卸作业的效率，确保装卸作业的统一协调，堆场通过堆存煤炭，可以实现对煤炭的缓冲存储。
（3）调节功能
煤炭的需求具有随季节和周期波动的特性，铁路、水路运输也都受困于设备检修或恶劣天气存在运输中断的情况，而煤炭生产是持续不断的，所以堆场的堆存能力可以调节煤炭输出港口和煤炭接卸港之间的煤炭需求波动，从而稳定上游的煤炭生产。
..............................
2.2 二维条形装箱问题
2.2.1 二维装箱问题概述
装箱问题是一类经典的组合优化问题，与其相关的研究被统称为切割及装箱问题（Cutting and Packing Problem，C&P），在运输业、制造业、计算机行业等众多行业都有着广泛的应用，其本质是利用有限的资源服务尽可能多的需求，对节约成本、提高效率有着重要的意义。装箱问题可简单描述为：给定若干物品和容器，寻求一种将物品装入容器的方案，使得某项指标达到最优。
根据研究对象的维度，装箱问题可以分为一维装箱、二维装箱、三维装箱、多维装箱问题，但目前的研究普遍集中于三维以内。顾名思义，一维装箱仅考虑物品一个维度的属性，如长度、重量、体积等；二维装箱考虑了物品两个维度的属性，如现实生活中所熟悉的具有长度和宽度的平面物品——布匹裁剪、玻璃切割、集成电路芯片布局等；三维装箱则考虑了物品三个维度的属性，如集装箱、快递货物的长宽高属性。
本文研究的煤炭堆场空间调度问题考虑了煤堆占据堆场空间的长度和时间两个属性，属于二维装箱问题，故接下来进一步研究二维装箱问题。根据待装物品的形状，二维装箱问题可以分为规则物品装箱和不规则物品装箱。根据待装物品的信息是否全部已知，二维装箱问题又可分为在线二维装箱问题和离线二维装箱问题，其中离线二维装箱问题是指待装物品包括但不限于尺寸在内的信息在装入容器前全部已知，而在线二维装箱问题仅仅知道下一个要装入容器的物品的信息。现实中，通常所研究的二维装箱问题的待装物品多为矩形物品且装入容器前物品的信息已知，本文所研究的二维装箱问题亦是如此。
.............................
第 3 章 煤炭堆场空间调度问题的数学模型 ............................. 27
3.1 问题描述 .................................. 27
3.2 条件假设 .................................... 28
第 4 章 煤炭堆场空间调度问题的算法设计 .................... 36
4.1 约束规划模型设计 ........................................ 36
4.1.1 约束模型说明 ................................... 36
4.1.2 参数和决策变量 ............................... 36
第 5 章 计算实验 ..................................... 45
5.1 实验设计 .................................... 45
5.2 计算环境 .................................... 46
第 5 章 计算实验
5.1 实验设计
为了分析影响 GRASP 算法性能的因素、比较 CP 和 GRASP 算法在求解煤炭堆场空间调度问题上的性能，本文根据实际的煤炭堆场数据，设定煤炭堆场中一个条形场地的长度为 1400m，即在该问题转化为二维条形装箱问题所建立的模型中令条形的长度 L=1400；同时，本文结合煤炭码头实际客户的需求，将其划分为几种不同的情况，随机生成了测试数据包，测试数据的结构如表 5-1 所示。
在表 5-1 中，测试数据包由 ABC 三组不同的测试数据构成，每组数据根据特定的数学分布随机生成，各自对应着现实场景下一类船舶的需求情况。在每组测试数据中，包含 5 个不同的数据实例，每个实例又由多艘船舶的需求组成，其中每一艘船舶的需
