基于动态网络流的煤炭供应链设备维护调度混合算法研究

摘要

对煤炭装卸设备定期维护和保养是保证设备正常运行、煤炭顺利输送的关键。为确保煤炭供应链系统的稳定性，供应链上的各组成设施如铁路、港口设备以及煤炭生产地设备等每年都要进行定期的预防性和矫正性维护。这些维护作业造成的系统中断对系统容量的影响不容忽视。在供应链管理的思想下，设备的维护检修任务必须作为一个整体考虑，协调起来制定检修计划，才能保证系统的总中断时间最短，从而达到在计划时间段内最大化系统通货能力的效果。 本文在现有研究的基础上，着重研究了一种描述煤炭供应链设备维护调度问题的带边中断动态网络最大流模型。即给定一个具有源点和汇点的的网络，考虑网络中一些因维护而需要定期中断的弧的调度安排问题，弧上的中断任务必须在规定的时间窗口内完成，当启动中断任务后，相对应的网络弧在中断时间内不连通，而目标就是要协调调度各段弧的中断时间，使网络总流量在规定的时间跨度内最大化。此问题是一个崭新的组合优化问题，且已经被证明是NP难问题。本文开发了以禁忌搜索（启发式）和整数线性规划（精确算法）相结合的混合算法，对该模型开展了科学理论研究，结果表明，本文设计的混合算法在求解规模较大基准算例时，性能表现优异。论文的主要研究工作和创新如下： （1）针对煤炭供应链系统中设施设备的检修安排现状，细致地分析了合理安排设备维护作业对系统总吞吐量的影响，阐明了设备维护调度的重要性，从理论上分析了煤炭供应链设备维护调度问题与动态网络流问题的相关性，运用带边中断动态网络最大流问题模型描述该实际问题。 （2）着重分析了带边中断动态网络最大流模型的理论特性，设计了以禁忌搜索算法为主体，结合整数线性规划提供的原始及对偶信息来加快搜索进程的混合算法，并详细阐述了混合算法的设计流程。 （3）开展了数据实验，应用标准测试数据，采用Python语言编程，调用Gurobi优化求解器对混合算法进行了有效验证，结果表明混合算法在各组优化实验中表现都比较好，特别是在大网络大规模的算例中，混合算法表现最好。

目录

声明

第1章 绪论

1.1 课题研究背景及意义

1.2 课题来源

1.3 国内外相关研究现状

1.4 研究内容及结构安排

1.5 本章小结

第2章 网络流理论及相关算法介绍

2.1 网络最大流问题

2.2 混合整数线性规划

2.3 禁忌搜索算法

2.4 本章小结

第3章 带边中断动态网络最大流模型分析

3.1 问题分析

3.2 问题数学描述与模型

3.3 算例分析

3.4 本章小结

第4章 混合算法设计

4.1 混合算法设计框架

4.2 前期准备条件

4.3 混合算法具体设计

4.4 本章小结

第5章 实验计算与分析

5.1 实验数据来源及说明

5.2 计算环境及对比实验

5.3 实验结果及分析

5.4 本章小结

第6章 总结与展望

6.1 全文总结

6.2 研究展望

致谢

参考文献

攻读硕士期间研究成果和参与项目