Ford–Fulkerson算法铁路运输系统中车辆流问题的研究
关键字：最大流 Ford–Fulkerson算法 标号法 车辆流 客流4841
The research of vehicle flow in the railway transport system
Abstract: The maximum flow problem of graph theory is a classical combinatorial optimization problem, and it has been used widely, in transportation, communications engineering, industrial, commercial, agricultural, and many other fields, to bring great convenience for our daily life. And its application also play a very important role in many fields, such as the mathematics, management science, and social sciences. In this paper, through the description and analysis of the classic algorithm of the maximum flow problem, called the Ford - Fulkerson algorithm, we give an algorithm based of the Ford - Fulkerson algorithm, called the labeling algorithm. And we clearly and completely describe how the labeling algorithm solve the maximum flow problem. And then, combined with the actual situation, the maximum flow problem and its algorithm are applied to solve the passenger flow problem and the vehicle flow problem in the transport system.Via some simplified assumptions and limiting conditions, we build a network model. And we use the c++ programming to implement the label algorithm, and use it to solve the passenger flow problem and vehicle flow problem.
Keywords: maximum flow, Ford–Fulkerson algorithm, labeling algorithm, vehicle flow, passenger flow
目录
一 绪论 1
1.1 课题的目的和意义 1
1.2 国内外研究现状与发展趋势 1
1.3 网络流基本概念及其数学模型 3
1.3.1 基本概念 3
1.3.2 数学模型 5
二 Ford–Fulkerson算法 6
2.1 Ford–Fulkerson算法的思想及原理 6
2.2 Ford–Fulkerson算法的具体步骤 7
2.3 Ford–Fulkerson算法的实现——标号法 8
2.4 寻求最大流的标号法举例 9
2.5 小结 11
三 最大流在交通运输系统中的应用 12
3.1 寻求最大流的标号法的C++实现 12
3.2 地铁运输系统中客流量问题 14
3.3 铁路运输系统中车辆流问题 17
3.3.1 车辆流问题模型建立 18
3.3.2 车辆流问题求解 19
四 全文总结 21
致谢 22
参考文献 23
附录 24
一 绪论
1.1 课题的目的和意义
图论是应用数学的一个重要分支，它涉及的内容非常广泛，并且在许多领域有十分广泛的应用。而最大流问题和它的对偶问题最小割问题则是图论中一个经典的组合优化问题，也是特殊的线性规划问题。它们的应用涉及交通运输、通信工程、VLSI、计算机科学与技术等许多工程领域和物理、化学、生物等许多科学领域。在应用数学、管理科学和社会科学等众多领域中最大流和最小割问题也起到了非常重要的作用。例如：在工程领域的电网络、网络可靠性测试等问题中的应用，在计算机科学和通信系统的一致并行计算机的调度问题、最大流路由问题、纹理分析问题和CAD中的最小割划分等问题中的应用，以及在交通运输中的各种路线调度问题的应用。