堵塞流理论在随机流动网络优化设计、改造及运行中的应用

论文摘要

网络中由于流动单元的随机流动,造成网络的堵塞,或使网络流通的可靠性降低,这种不确定性、多值性的网络流量特点是堵塞流理论重点研究的对象.基于堵塞流理论从流量随机流动的角度和网络结构自身的原因分析了网络中发生流量堵塞的缘由,并将该理论应用到对随机流动网络的优化设计、改造及运行过程的研究中.该理论是网络流理论在不确定性、随机性多值流领域的新分支.针对堵塞流的理论研究和应用研究,论文包括如下几个方面的研究工作:1.基于本文研究的网络中流动单元随机流动特点,提出了随机流动网络的概念,给出了该网络模型的定义和相关假设,建立了随机流动网络中个体流动的饱和流模型.2.在堵塞流理论的基础上,进一步探讨了求解网络最小饱和流的算法,明确了无环饱和流和有环饱和流的区别.首先利用网络割矩阵对已有的求解最小饱和流的分支定界算法进行了改进;其次基于堵塞截面寻找有条件最长增广路,提出了求解无环最小饱和流的有条件最长增广路近似算法,并对该算法的复杂性作了分析.最后分析了改变各弧容量对网络堵塞程度的影响,针对网络中一些弧容量的悖论现象,研究了这类弧容量变化对网络最小饱和流值的影响.3.对随机流动网络防堵塞优化设计及改造进行了研究:首先建立了弧容量有限制的网络防堵塞优化设计的一般模型,优化原设计的弧容量以消除或尽量减少网络结构上的堵塞点,用最经济的方法改善网络的堵塞程度,提高网络弧利用率.该模型具有一般性,算例分析了优化设计方法的合理性和可行性;其次建立了已有交通网络优化改造的一般模型,并与最小成本改造法相比较,结果表明该模型的合理性和普遍适用性.4.建立了评估随机流动网络流通性能的评价指标.分析了网络运行过程中用户选择正向增广路径的不同方式对随机饱和流分布的影响,提出了三种选择路径方案,利用Monte-Carlo仿真分别模拟出网络中随机饱和流的分布,比较这三种不同路径选择方式下随机饱和流值的变化以及相对应的概率分布;其次基于网络的期望流通值对网络提出了优化改造方案;最后研究了城市交通网络防堵塞改造问题,目前单行道改造是很多国家普遍推行的方法,本文基于评价指标建立了多重目标评估模型以找出最佳单行道改造方案.5.研究了随机流动网络运行过程中出现的两类问题,其一是将通行时间考虑到饱和流问题中,动态网络优化不仅需要考虑饱和流值,还要考虑饱和流在网络中的通行时间.网络中发生紧急事故时,若各用户总是选择通行时间最短的路径增流,考虑单位流量通过弧花费的时间与弧上已有流量和容量均有一定的函数关系,则每次增流的路径不尽相同.提出了最短时间饱和流问题及相应的算法研究,该饱和流反映了基于用户需求最大化的目标;其二是对带模糊约束的随机流动网络饱和流问题进行了研究.讨论了网络中弧容量约束模糊的情况下,如何以最大的满意度满足模糊条件得到最佳最大流和最佳最小饱和流,给出了相应的算法研究,使饱和流问题变成一个模糊环境下的决策问题.6.对随机流动网络的可靠性进行了研究:利用网络饱和流模型仿真出网络中各弧不同流量的概率分布,随机流动网络的可靠性用网络饱和流不小于给定需求的概率值来衡量.基于网络饱和时堵塞截面中弧流量分布决定了网络饱和流值的性质,将网络饱和流不小于给定需求的可靠性转化为求解堵塞截面中反向弧流量和不大于某个确定值的概率.算例说明了可靠性算法的实用性和有效性.最后是对随机流动网络可靠性研究的一个实际应用的例子,突发公共安全事件对人类造成的威胁,由于地域和经济因素,很多区域无法建立完善的医疗救护站.本文考虑构建医疗救护网络系统,该系统内至少有一个医疗救护站,可以向系统内的其他区域辐射医疗救护功能.从受灾区域到医疗救护站的实际流通能力大小是该网络援救能力可靠性的保证.医疗救护网络可靠性的研究有助于我们正确评估发生紧急事故下医疗救护网络的援救能力.

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题来源及其研究意义
• 1.1.1 本文研究的意义
• 1.1.2 堵塞流理论研究的实际应用前景
• 1.2 国内外研究现状
• 1.3 论文结构
• 1.4 创新点
• 1.5 小结
• 第二章 堵塞流理论的简要综述及随机流动网络的定义
• 2.1 堵塞流理论中的基本概念与定理
• 2.2 堵塞流理论中饱和流的组合优化模型
• 2.3 随机流动网络模型
• 2.3.1 随机流动网络的定义
• 2.3.2 随机流动网络模型的应用领域
• 2.4 随机流动网络中个体流动单元随机流动的饱和流模型
• 2.4.1 随机流动网络中饱和流的概念
• 2.4.2 网络个体流动单元随机流动的饱和流模型
• 2.5 小结
• 第三章 堵塞流理论中无环饱和流的研究
• 3.1 求解最小饱和流的分支定界法的改进算法
• 3.1.1 确定网络图的准堵塞截面
• 3.1.2 利用网络图的准堵塞截面确定最小饱和流的优化模型
• 3.1.3 算法研究
• 3.1.4 实例分析
• 3.2 有向网络中无环最小饱和流问题及其算法研究
• 3.2.1 无环最小饱和流和有环最小饱和流的分析比较
• 3.2.2 网络理论最小流通能力的确定
• 3.2.3 有条件最长增广路算法研究
• 3.2.4 求解网络无环最小饱和流的算例
• 3.2.5 计算结果与双向增流及仿真计算结果的比较
• 3.3 堵塞网络中弧容量悖论现象对最小饱和流的影响
• 3.3.1 网络中弧容量的悖论现象
• 3.3.2 网络验证
• 3.4 小结
• 第四章 随机流动网络防堵塞优化设计和改造研究
• 4.1 随机流动网络防堵塞优化设计的一般模型
• 4.1.1 前言
• 4.1.2 随机流动网络防堵塞优化设计的一般模型
• 4.1.3 举例
• 4.2 交通网络防堵塞的优化改造
• 4.2.1 前言
• 4.2.2 现有交通网络改造实施的已知条件
• 4.2.3 交通网络防堵塞改造的一般模型
• 4.2.4 实例分析与比较
• 4.3 小结
• 第五章 基于评价指标对随机流动网络优化改造及运行的仿真研究
• 5.1 随机流动网络流通性能的评价指标
• 5.2 基于评价指标对随机流动网络的优化改造
• 5.2.1 基于期望流通值对网络优化改造的方法研究
• 5.2.2 初始网络流量分布的随机流动仿真试验结果
• 5.2.3 实例改造方案的仿真方法研究
• 5.2.4 紧急疏散网络运行过程中防堵塞的应急改造
• 5.3 基于不同路径选择方案对网络运行中饱和流的仿真研究
• 5.3.1 引言
• 5.3.2 相关定义及方案评估指标
• 5.3.3 交通网络中不同路径选择方案及MC 仿真研究
• 5.3.4 相关实证研究
• 5.3.5 仿真结果分析比较
• 5.4 城市街道网单行道改造方案的评估
• 5.4.1 有关单行道改造的文献综述
• 5.4.2 街道网的改造方案及评估模型
• 5.4.3 结合实例分析街道网的单行道改造
• 5.5 小结
• 第六章 随机流动网络运行过程中若干问题的研究
• 6.1 随机流动网络中最短时间饱和流问题的研究
• 6.1.1 相关背景知识
• 6.1.2 对随机流动网络中通行时间的假设
• 6.1.3 最短时间饱和流问题
• 6.1.4 最短时间饱和流问题的算法研究
• 6.2 带模糊约束的随机流动网络中的饱和流问题
• 6.2.1 模糊网络流分析的研究背景
• 6.2.2 带模糊容量限制的最大流问题和最小饱和流问题
• 6.3 小结
• 第七章 随机流动网络可靠性研究
• 7.1 有关网络可靠性研究的文献综述
• 7.2 基于同一堵塞截面评估随机流动网络的可靠性
• 7.2.1 堵塞状态下随机流动网络通行能力分析
• 7.2.2 随机流动网络可靠性分析
• 7.2.3 基于饱和流模型计算各弧不同流量的概率分布
• 7.2.4 随机流动网络可靠性算法研究
• 7.2.5 实例分析
• 7.2.6 误差分析
• 7.3 基于多个堵塞截面评估随机流动网络的可靠性
• 7.3.1 网络有效堵塞截面的确定
• 7.3.2 堵塞截面弧流量分布的仿真研究
• 7.3.3 有多个堵塞截面的随机流动网络的可靠性研究
• 7.3.4 实例分析
• 7.4 有关随机流动网络可靠性的实际应用
• 7.4.1 医疗救护网络的研究背景
• 7.4.2 医疗救护网络实例的可靠性研究
• 7.5 小结
• 第八章 结论与展望
• 8.1 论文的主要工作
• 8.2 展望
• 参考文献
• 致谢
• 在学期间的研究成果及发表的学术论文
• 附录 25 个网络数据