摘 要

本论文是带资源约束的基本最短路问题的割平面算法研究，最短路径问题是图论中的经典问题，在重要程度上来说的话，其算法研究对最短路问题的优化有很大的实用价值，许多实际的优化问题都可以变成最短路径问题解答。随着社会的飞速发展和人们日常生活的需求的发展，传统的最短路径问题解决方法已不能再满足人们的需求。资源受限的最短路径的问题可以采取多种形式，包括本论文中讨论的问题数学模型。

ESPPRC和容量资源限制之间的最短路径问题。介绍了具有资源限制的最短路径问题的精确算法，该算法的效率不足以满足需求，因此我们尝试提出一种改进的算法以加快精确计算最短路的速度。本文讨论了资源受限的短路径问题的三种解决方案分析了各种算法的优缺点，提出了思路和改进方向。在原有算法的基础上，提出了一种改进的ESPPRC算法，该算法结合了割平面算法。在这种方法中，将整数问题线性松弛为非整数线性问题，并对其进行求解，来求解 ESPPRC问题。线性规划理论说明，在温和的假定下（如果线性规划存在最优解，并且可行域不包含一条线），总存在一个极值点或顶点是最优的。 检验所获的最优解是否为整数解。如否，则必然存在一线性不等式将最优点和真可行集的凸包分离。找到这样的不等式是分离问题，而这样的不等式就是切割。 切割可以被加入到被松弛的线性规划中，使得当前的非整数解对松弛不再可行。该过程不断重复，直到找到最优整数解。

并使用Solomon数据集在本文中验证了改进算法，并测试了改进算法的性能。对改进算法的详细评估表明，它们比原始算法更有效。最后，简要概述了ESPPRC问题在现实生活中的应用以及拟议的改进。设想将算法应用于具有多种约束的其他类型的最短路径问题。

关键词：最短路径问题、割平面算法、路径拼接

Abstract

This paper is the study of cutting plane algorithm for the basic shortest path problem with resource constraints. The shortest path problem is a classical problem in graph theory. To an important extent, its algorithm research has great practical value for the optimization of the shortest path problem. Many practical optimization problems can be turned into the shortest path problem solution. With the rapid development of society and the needs of people's daily life, the traditional shortest path problem-solving method can no longer meet people's needs. The shortest path problem with limited resources can take many forms, including the mathematical model discussed in this paper.

Shortest path problem between espprc and capacity resource limit. This paper introduces an accurate algorithm for the shortest path problem with resource constraints. The efficiency of this algorithm is not enough to meet the needs. Therefore, we try to propose an improved algorithm to speed up the accurate calculation of the shortest path. This paper discusses three solutions to the short path problem with limited resources, analyzes the advantages and disadvantages of various algorithms, and puts forward ideas and improvement directions. Based on the original algorithm, an improved espprc algorithm is proposed, which combines the cutting plane algorithm. In this method, the integer problem is linearly relaxed to a non integer linear problem and solved to solve the espprc problem. Linear programming theory shows that under mild assumption (if there is an optimal solution in linear programming and the feasible region does not contain a line), there is always an optimal point or vertex. Check whether the optimal solution is an integer solution. If not, there must be a linear inequality to separate the convex hull of the best and the true feasible set. Finding such inequality is a separation problem, and such inequality is cutting. Cutting can be added to the relaxed linear programming, so that the current non integer solution is no longer feasible for relaxation. The process is repeated until the optimal integer solution is found.

The improved algorithm is validated in this paper by using Solomon data set, and the performance of the improved algorithm is tested. The detailed evaluation of the improved algorithm shows that they are more effective than the original algorithm. At last, the application of espprc in real life and the proposed improvement are briefly summarized. It is envisaged to apply the algorithm to other types of shortest path problems with multiple constraints.

Keywords: shortest path problem, cutting plane algorithm, path splicing

目 录

摘 要 1

Abstract 1

第1章 绪论 1

1.1研究背景及研究意义 1

1.2国内外现状 2

1.3 主要研究内容 2

1.4章节安排 3

第2章 研究问题介绍 5

2.1最短路问题分析 5

2.2常用算法分析 5

2.3多约束的最短路问题 5

2.3.1问题介绍 5

2.3.2问题分析 6

2.4研究目标 7

2.5拟采用技术方案及措施 8

2.6本章小结 9

第3章 ESPPRC问题的算法模型和分析 10

3.1 ESPPRC问题描述 10

3.2改进的算法设计 10

3.3算法可行性 12

3.4 算法实现 13

3.5本章小结 14

第4章 实验数据 15

4.1实验结果 15

4.2结果对比 16

4.3 ESPPRC 问题的其他应用 16

4.4本章小结 17

结论 18

参考文献 19

致谢 21

第1章 绪论

最短路径问题是图论中的经典优化问题，也是在现代交通网络应用中有着重要位置。带资源优化的最短路径问题是最短路径问题中加入了资源的约束，且在路径花费的资源不应超过给定资源的上限。ESPPRC问题具有广泛的研究意义和应用意义，目前随着大众的认知以及网络通讯的飞速发展，许许多多生活中的问题，在现在都可以抽象为ESPPRC问题来进行解决，或将求解最短路问题的方法和思想作为解决现实问题的一部分来进行研究。，ESPPRC问题已逐渐成为人们研究的热点问题。

1.1研究背景及研究意义