物流管理论文哪里有？本文着重分析了带边中断动态网络最大流模型的结构特点与计算复杂度之间的关系，介绍了 Benders 分解对此问题进行模型分解的过程，并将 CBD和 B&BC 两种不同的 Benders 算法的求解效率进行了对比，此外还进一步分析了初级子问题割对 B&BC 算法求解效率的影响。
第 1 章 绪论
1.3 国内外相关研究现状
1.3.1 网络流问题
网络流问题在生产、生活中应用极其广泛，经过几十年的研究，取得了丰硕的理论成果。网络流问题根据是否考虑时间因素，又可分为静态网络流问题和动态网络流问题。接下来就分别对其进行介绍。
1.3.1.1 静态网络流问题
传统的静态网络流问题不考虑时间因素，网络结构不发生改变，整个网络始终处于一种静止状态。这类模型的建模相对较为简单，模型所包含的整数变量也相对较少，因此求解也会相对较为容易。到现在为止，静态网络流的研究已经非常广泛，研究内容主要包括最短路问题（Shortest Path Problem）、最大流问题（Maximum Flow Problem）、最小费用流问题（Minimum Cost Flow Problem）。
最短路问题是静态网络流问题中最经典、最简单的问题之一，目前主要分为分为单源、全局、无回路三种，已经广泛应用于设备更新、管道铺设、交通规划、应急管理等场景。单源最短路，根据网络图中边的权值有无负值，可分别使用 Dijkstra 算法和 Bellman-Ford 算法进行求解；全局最短路一般采用 Floyd算法进行求解，但要求网络图中不含负回路；无回路最短路可使用拓扑排序法求解[2]。
最大流问题作为最短路问题的互补问题，极大丰富了静态网络流问题的相关研究，关于最大流问题的详细介绍请参考章节 2.3。
最小费用流问题是静态网络流问题最基本的模型，其主要研究如何选择合适的路径，使得流量从源点流到汇点所需要的费用最小化。1972 年，Edmonds和 Karp[3]针对此问题首次提出了多项式时间的算法，他们的算法把最小费用流问题缩减为了一系列的最短路问题。1985 年，Tardos[4]开发了第一个强多项式时间的算法，此算法在一定程度上促进了其他的强多项式时间算法的出现。关于最小费用流问题经典算法的详细研究可参考 Angelo[5]的文章。
第 3 章 带边中断动态网络最大流问题
3.1 问题分析
3.1.1 基础网络建模
煤炭在矿山被开采出来经过铁路的运输到达港口，在港口经过翻车机、堆料机、取料机、装船机等的轮番作业后到达船舶，其中无论铁路还是港口，都对应着多条煤炭运输线路，这些线路互相连接形成了一个庞大的煤炭供应链网络。可以发现，这个网络的运行涉及到非常多的设备，但这些设备普遍具有一定的预防性维护周期及故障后维修情况，且每次维护花费的时间及对作业效率的影响都不一定相同。其中不合理的设备维护给整个供应链网络的正常运行带来了巨大的损失，因此针对设备的维护作业建立一个合理的模型进行调度是十分重要的，详细情况可参考章节 1.3.3。
综上所述，煤炭供应链网络不仅环节多、结构复杂，最为关键的是，其设备维护工作跨越多个时间周期，这使得煤炭供应链网络结构呈现出一种动态变化的趋势，此时普通的数学模型难以精确描述整个问题。动态网络流问题则由于灵活、可扩展性强的特性，在解决此类问题时表现出非常大的优势。接下来我们详细介绍此问题如何建模为特殊的动态网络流问题。
建模时，铁路网和码头的装卸、运输设备网的组合被表示为一个数学网络G =(V, A) ，煤炭则被表示为流经网络中弧的流； A 为有向弧的集合，表示铁路运输和港口作业设备的煤炭流动方向，V 为节点的集合，表示铁路站点和码头煤炭装卸点，其中每个设备有固定的单位时间处理能力，它们对应网络中弧的容量，由于设备需要定期进行维护，因此维护期间网络中弧的容量会受到一定的影响。此外，对整个网络运营效率的评价有很多标准，如网络营运成本、总流量、碳排放等，但此处网络营运的首要目标仍然是围绕通过一段时间对维护工作的合理调度来提高网络总流量，达到整个煤炭供应链效率的提高。
第 5 章 改进的 Benders 分解算法
5.1 预流推进算法
由于 Benders 分解算法的求解效率主要受到主问题和子问题求解效率的影响，因此针对主问题和子问题特殊的结构进行有效改进是加快求解的一种有效方式。带边中断动态网络最大流问题的二级子问题是一个网络最大流问题，传统的Gurobi 建模默认使用单纯形法对二级子问题进行求解，其并未有效利用二级子问题的结构。
针对网络最大流问题，Dantzig 在 1951 年首次提出使用网络单纯形法对此进行求解，其时间复杂度为2O(N*M*U)（式中：N 为网络节点数量，M 为弧数量，U 为最大弧容量）。此后，学者们不断设计更加有效的求解算法改进问题的求解速度，如增广路径算法、Dinic 算法、预流推进算法。预流推进算法作为网络流算法求解中一种相对高效的求解算法，其理论时间复杂度为2O(N* M) 。
因此本文设计基于预流推进的 B&BC 即 Pre-B&BC，即使用预流推进算法来求解 Benders 分解过程中产生的二级子问题，期望能够提升求解速度。但是本文并不设计预流推进算法的具体求解过程，而是借助于先进的算法包 networkx 构建有向图，并调用其中的预流推进算法进行求解。接下来我们将对其进行详细介绍。
networkx 最早出现在 2002 年，是使用 Python 语言编写，用于构建、操作和研究复杂网络的软件包。networkx 可以通过标准格式和非标准格式对网络进行存储，此外，其还包括了很多针对静态网络流的求解算法，如网络单纯形法、最短增广路径算法、预流推进算法等。
5.2 有效不等
虽然改进子问题的求解算法在理论上能加快问题的求解速度，但是经过研究证实，主问题在整个求解过程占到的时间能够达到 90%甚至更多。因此从优化的角度，如何减少主问题的复杂程度，缩减主问题的求解区间，将是提升求解效率的一个更加有效的方法。
通过前面章节 2.4.2 我们已经了解到，可以通过加入不等式来缩减 CBD 的迭代次数和收敛速度，但由于加入不等式会增加主问题的复杂程度，因此如何合理控制加入的不等式数量以及确保加入的不等式有效对于求解至关重要，但目前对于 B&BC 如何加入不等式的研究较少。针对带边中断动态网络最大流问题，文献 35 采用主问题的线性松弛来产生多组有效不等式，然而这种方式既不能保证割的有效性，还使得主问题的求解规模变大，其对 B&BC 算法的改进效果并不明显。因此本文将加入两种特殊的不等式，分别探索他们对 B&BC 算法的改进效果。
第 6 章 总结与展望
6.2 研究展望
带边中断动态网络最大流问题作为一种特殊的动态网络流问题，具有调度与动态网络最大流相结合的结构，非常适合使用 Benders 分解进行求解。因此本文比较了两种 Benders 分解算法 CBD 与 B&BC 在此问题求解效率上的差异，分析了初级子问题割对于B&BC算法求解的影响，此外还从不同角度尝试对B&BC算法进行了改进。然而由于研究时间和学术水平有限，本文在某些方面的研究还不够深入，有待进一步进行完善和丰富：
（1）改变调度问题或网络最大流问题对于 Benders 分解求解效率的影响。 对于实际工业应用来说，本文的模型可能过于抽象化而无法直接进行应用，因此需要改变某些约束条件以适应实际问题，但这些改变对于求解的影响是未知的，尚需要实验进行进一步探索来了解。
（2）针对加入主问题的割采用更加有效的筛选策略。
虽然本文所加入的 Benders 割均为违反割，但是这并不能保证我们所加入的Benders 割是最有效的，而且加入过多的 Benders 割会导致主问题在探索分支节点时速度变慢。因此我们认为如果能够采取更加有效的方式筛选加入主问题的Benders 割，将很有可能加速主问题的收敛速度。
（3）使用机器学习方法指导主问题的分支与节点选择策略。
在本文的主问题求解中，采用的是 Gurobi 默认的分支与节点选择策略。然而 Benders 割是一个动态加入的过程，我们认为若能根据加入的 Benders 割对分支与节点选择策略进行实时调整，指导主问题采用更好的节点进行分支，这将在很大程度上缩减分支定界树的大小，保障在较短时间内找到更好的解，从而缩短问题的求解时间。
参考文献（略）
