庞博[1]2009年在《动态网络中的流问题》文中研究说明网络流理论是图论与组合最优化相结合的产物,是运筹学理论中发展最快的分支之一.网络流理论主要研究网络中的最优化问题,其中两个基础的问题是求最短路和最小费用流.随着科学技术的发展进步和人类活动的日益复杂,在许多新型的网络中,经典的静态网络最优化的模型不再适用.本文就近年来的热点新型网络——动态网络中的流问题进行研究,主要研究了与求最短路和最小费用流相关的问题.通过将动态网络进行分类,提出了各自的问题模型,并给出了求解新模型的网络算法.本文的主要工作成果有以下几个方面:1.提出了动态网络的分类标准,将动态网络分成两类,时变动态网络和动态拓扑结构网络,指出了它们的区别和联系,并将动态拓扑结构网络中的流问题转化为对网络流问题进行灵敏度分析.2.提出了最小最大时间流的概念,证明了在离散化的时变-容量网络中,以时间作为费用的最小费用流是最小最大时间流.并以时变网络中的最短路算法为基础,提出了时变-容量网络的最小最大时间流算法.3.定义了最优添加顶点和最优添加弧,提出了求最短路上的最优添加顶点和最优添加弧的算法.给出了最优添加顶点和最优添加弧之间相互转化的方法.4.研究了最小费用流的灵敏度分析相关问题,利用在剩余网络中增广最小费用流的构造,提出了求最小费用流关键弧的MVA-MCF算法,算法相比自然算法在复杂性上有明显降低.提出了求最小费用流的最优添加弧的BAA-MCF算法,它与自然算法相比,在某些情况下复杂性更低.5.提出了求时变网络中关键弧的算法.算法通过Fibonacci堆存储数据,利用时变网络最短路算法的特殊性得出,它的复杂性相比自然算法有明显降低.6.介绍了等容网络和等距网络的工程背景,分析了一般网络算法在它们中的复杂性优化,给出了等容网络的灵敏度分析在多径路传输中的应用.
马宇斌[2]2013年在《天基信息网络流问题的算法研究》文中研究表明随着航天技术飞速发展,构建天基信息网络,夺取空间优势成为各国科技和军事发展的重要任务.天基信息网络是一种以各种类型的卫星为网络节点,通过星间链路连接起来的空间无线网络系统,具有覆盖范围广、传输容量大等特点.路由问题和流问题作为天基信息网络信息传输的两种重要方式,日益成为国内外学者研究的课题.本文针对天基信息网络的特点,对其流问题进行了研究.通过对流问题的分类,提出了针对性强、有着重要应用背景和现实意义的叁个流问题,并给出了相应的求解算法.本文的主要工作成果有以下几个方面:1、提出了天基信息网络流问题的分类标准,将其细分为静态流问题、动态信息流问题和动态拓扑流问题叁种,指出了它们之间的区别与联系,阐述了它们各自所对应的现实应用背景,并将动态拓扑流问题转化成对静态网络问题作敏感度分析.2、根据天基信息网络的Qo S协议模式,阐述了多目标优化问题的实用价值,抽象出带主次双费用的最小双费用流问题模型.并利用原始对偶的思想,为该问题设计出正确高效的求解算法,最后将算法推广到最小多费用流问题上去.3、针对天基信息网络中存在的信息传输时延问题,抽象出连续时间容量网络的模型,提出了最短动态时间流的概念.发现了经典网络和带节点限制网络之间的关系,并分别为这两种网络模型设计出最短动态时间流算法.4、介绍了天基信息网络最大信息流敏感度分析的背景和研究现状,对其中的两个重要子问题——关键卫星问题和最佳添加链路弧问题,分别设计出高效的求解算法.相比按定义求解的自然算法,本文的算法在理论复杂性和实际计算量上都有明显降低.
陈挚[3]2004年在《容量—时间网络的时间流问题》文中指出本文主要考虑在容量-时间网络中寻找军事装备物资供应的最短时间流问题,即发出的流量为已知时,用最短的通过时间,使一个流从发点出发到达终点,并且流在各弧上流动时不会超过它们的容量限制。对于这个问题的研究,有很多的因素需要考虑,首先是对于各种约束条件,如距离、时间、费用等,如何寻找网络的最优解,其次把传统的算法应用于实际交通网络时可能需要很长的计算时间,这就需要利用网络的知识,使得问题的求解尽量简化,从而达到节省时间的目的。我们从五个方面讨论最短时间流问题,对各种情况分别开发了一些专门的有效的算法去解决这些问题。 关于讨论容量-时间网络的最短时间流问题和容量-时间网络在给定时间内的最大流问题,我们提出了网络的时间概念,对这两种情况分别建立了组合优化模型,并给出了各个模型的算法。而对在有拥堵的状态下,容量-时间网络的最短时间流问题,给出了此问题的数学描述,进行了详细的理论分析,最后得出了问题的有效的算法。我们将层次分析法引入最优化理论,将定量分析和定性分析有机地结合起来,很好地解决了容量网络中多目标线路的最优选择问题。最后分析了动态网络的一些基本性质,对动态时间流问题提出了一个有效的算法,并通过一个数字例子来说明这个算法。
庞博, 谢政, 陈挚, 张军[4]2010年在《动态容量网络中的最小最大时间流问题》文中研究说明动态(时间依赖的)容量网络与传统静态网络相比更具现实意义,在交通网络、物流网络和通信网络中都有着广泛的应用。在时间依赖网络最短路算法的基础上,研究具有实际背景的动态容量网络的最小最大时间流问题,给出求动态容量网络的最小最大时间流的多项式算法和算法的应用实例,其时间复杂度为O(mMv)。
马宇斌, 谢政, 陈挚[5]2013年在《连续时间容量网络的最短动态时间流问题》文中研究表明针对一类带节点处理速率限制的连续时间容量网络,提出了该网络中的最短动态时间流问题,并给出其线性规划形式;通过分析该网络与经典网络之间的内在联系,利用最大接收流和退流的思想分别设计出准确求解两种网络最短动态时间流的高效算法;证明了算法的正确性并分析出算法有较小的复杂度;最后,通过一个算例演示了算法的执行。
刘杨杨[6]2014年在《信息网络中流问题的灵敏度分析》文中指出随着科技的发展,一种新型的信息传输方式——信息网络流传输成为主流,信息网络理论的研究成为热点问题。而信息网络的拓扑结构并不是固定不变的,所以研究拓扑结构的变化对网络流最优解的影响对于信息网络的稳定性有非常重要的意义。本文以信息网络为研究对象,着重研究了信息网络中流问题的灵敏度分析。本文的主要内容包括:1、针对静态网络最大流的弧容忍度问题,分析了最大流和最小截的性质,由此给出了求解每条弧的最大流弧容忍度上下界的算法,并且证明了在算法中采用不同的最大流和最小截得到的弧容忍度上下界是相同的。2、在动态网络最大流问题中,细化了原有的最大动态流算法,由此提出了最大动态流的关键弧算法,并将算法与原有算法和按定义求解的算法进行分析,最后通过构造辅助网络来求解关键顶点问题。3、在动态网络中,分析了最短时间流的性质,说明了最短时间流与最大动态流的关系,由此给出了一个求解最短时间流问题的算法,在此基础上提出了最短时间流的关键弧算法,并将算法与按定义求解的算法进行了数值比较。
周爱平[7]2015年在《高速网络流量测量关键问题研究》文中指出网络流量测量是了解网络运行状况和理解网络行为的基础。随着带宽的快速增加和互联网的普及,我们将面临网络流量测量的新挑战。由于海量网络流量数据与有限系统资源之间的矛盾存在,传统的流量测量算法已经很难满足高速网络应用需求。近年来,多核技术已成为当前处理器体系架构发展的必然趋势。另外,随着云计算技术的推广,云计算平台具有对海量网络流量数据进行并行分布式处理的强大能力。因此,基于多核技术与云计算平台的并行分布式设计成为提高网络流量测量算法性能的有效途径。尽管网络流量测量算法广泛应用于网络安全、网络计费及流量工程等领域,但在高速网络环境下还有许多网络流量测量问题需要研究与解决。本论文围绕流量突发性,提出相关模型和流量测量算法,解决高速网络环境下流量测量面临的关键问题,为网络运行和管理提供有力支撑。从流量突发性角度,提出峰值流量测度,分析网络行为和建立合理的容量规划模型,为新建校园网的接入带宽提供准确评估；针对网络流量分布的重尾特性和MapReduce算法中负载不均衡问题,提出一种MapReduce框架下基于自适应抽样的大流识别方法；针对基于流抽样的超点检测方法存在计算负荷重、检测精度低、实时性差问题,提出超点检测的并行数据流方法；为了满足长持续时间流检测的高速网络应用需求,设计了基于共享数据结构的长持续时间流的并行检测方法和基于独立数据结构的长持续时间流的并行检测方法,基于独立数据结构的长持续时间流检测方法更好地满足高速网络的应用需求。实验验证了上述模型和算法的有效性。论文的主要工作和创新点为：(1)从流量突发性角度,提出峰值流量测度,分析网络行为和建立一种合理的容量规划模型,为新建校园网的接入带宽提供准确评估。首先,通过假设检验和拟合优度检验表明峰值流量服从渐近高斯分布,通过自相关性分析表明峰值流量间彼此相互独立；其次,研究网络内在特征对峰值流量的影响,一方面,通过统计学方法建立方差分析模型,研究接入带宽与峰值流量之间的关系,分析表明接入带宽对峰值流量的影响较小,另一方面,通过统计学方法建立协方差分析模型,研究接入带宽、网络用户数与峰值流量之间的关系,分析表明接入带宽与网络用户数存在较强的相关性,网络用户数是影响峰值流量的主要因子；最后,在上述分析的基础上建立线性回归模型及容量规划模型。通过实验验证容量规划模型的有效性。(2)针对网络流量分布的重尾特性和MapReduce算法中负载不均衡问题,提出了一种MapReduce框架下基于自适应抽样的大流识别方法。由于MapReduce框架中通过Hash函数按照分组将任务分配到每个reducer,如果分组服从均匀分布,那么每个reducer被分配相同的任务数,reducer之间是负载均衡的；如果分组服从偏态分布,那么每个reducer被分配不相同的任务数,导致reducer之间负载不均衡。另外,通过自适应抽样技术得到准确的流长分布估计,同时可以极大地减少所需的计算和存储资源。方法的实施中,一个MapReduce作业通过自适应抽样过程获得原始流长分布估计,在此基础上制定数据划分策略；另一个MapReduce作业通过数据划分策略指导大流识别。理论分析表明通过自适应抽样获得的流长分布估计是无偏的,通过配置参数可以控制流长分布估计的相对误差。实验结果表明,与默认的基于Hash函数的数据划分方法和TopCluster相比,提高了大流识别方法的性能,实现了reducer之间的负载均衡。(3)针对基于流抽样的超点检测方法存在计算负荷重、检测精度低、实时性差问题,提出了一种超点检测的并行数据流方法。随着多核处理器的发展,并行设计成为算法性能提高的一种有效途径。首先,为每个线程建立本地Sketch数据结构,当报文到达时,通过多个Hash函数运算,将Sketch数据结构中对应位置为1,当测量时间周期结束后,对多个本地Sketch数据结构进行合并；其次,估计节点的链接度,确定超列；最后,利用定理5.1对Sketch数据结构中任意两个超列的组合进行逆计算构造节点的IP地址,估计节点的链接度,如果节点链接度大于阈值,则认为该节点是超点。重复上述步骤,直到处理完所有的超列组合。性能分析和实验结果表明,该方法具有良好的检测精度和较低的开销。(4)为了满足长持续时间流检测的高速网络应用需求,在多核硬件平台上,从共享数据结构和独立数据结构角度设计长持续时问流的并行检测方法。由于基于共享数据结构的长持续时间流检测方法中不同线程之间共享数据结构(Cuckoo Hash表),共享数据结构读操作远多于写操作,引入读写锁来实现线程之间的同步,导致线程之间的同步开销过大,不能够满足高速网络的长持续时间流检测应用需求。针对上述问题,基于独立数据结构的长持续时间流检测方法为不同线程建立本地数据结构,从而线程之间不需要同步,且产生较少的开销。性能分析表明,基于独立数据结构的长持续时间流检测方法具有低的时间和空间复杂度。实验结果表明,该方法具有良好的时间效率,与相关方法相比,具有较好的检测精度和流持续时间估计。
黄孝鹏[8]2007年在《堵塞流理论在路网容量和最短时间流中的应用研究》文中进行了进一步梳理堵塞流理论是网络流规划理论中的非确定性、随机多值性研究领域中的一个新分支,它是网络流理论研究中的一个具有开拓性和创新性的前沿领域。而以往对交通网络系统中路网容量和时间流问题的研究,都没有考虑到网络堵塞的情况。基于此,本文前一部分结合网络系统的堵塞流理论来研究路网容量,引入网络堵塞最小流这个重要的网络性能指标,应用信息熵的方法,结合各堵塞流值在交通网络随机流仿真中出现的仿真概率,对路网容量进行了重新定义,并结合路网防堵塞扩容改建的动态算法,利用新的定义,最后得到与实际一致的结果,并对计算方法进行了推广。在交通运输网络中,对网络系统中时间的要求也极为严格。故在本文后一部分研究了决策者如何制定最短时间流决策的问题,建立了静态数学规划模型,给出了模型的算法,讨论了算法的复杂性,并用算例验证。随后,又对网络时间流问题进行了进一步的深入研究,分析了动态堵塞情形下时间流的特性,考虑交通网络堵塞程度对通过时间的影响,引进堵塞系数,构造动态时间函数,建立了在动态堵塞情况下的最短时间流模型,给出了模型的算法,用算例验证,并与静态情形进行了比较分析。另外,在实际解决时间流问题时,由于各种主客观条件的制约,决策者都逐步注意到了不确定性。一种情况是考虑物流运输网络中道路服务水平的不确定性及其对运输时间的模糊影响。针对此,本文提出了带模糊约束的最短时间流问题,建立数学模型,给出了求解数学模型的有关算法,并用具体算例进行了比较分析。另一种情况是当容量为一个区间数变量时,此时根据风险决策的有关理论来研究区间数弧上的时间流优化问题,给出保守时间流、乐观时间流的定义和最小风险时间流的定义,建立数学规划模型,并设计了寻优算法。最后,本文还给出了算例和比较分析,验证了算法的有效性。本文从堵塞流的角度来研究路网容量和最短时间流问题。希望通过本次研究,能解决现实生活中的一些问题,并能对堵塞流的理论研究与实证分析提供一些有价值的尝试。
吴晓东[9]2008年在《大规模部队铁路输送研究》文中认为我军大规模部队机动的主要方式是铁路输送,要求在一定的路网条件下,依据一定的运输顺序,满足一定的军事和运输要求,短时间内完成分散配置的大批部队向相对集中的一个或多个方向的机动。大规模部队铁路输送运量大、时限紧、要求高,需要做到统筹规划、周密部署、精心组织,其中难点问题众多且关系复杂,急需对此进行深入研究。本文首次对大规模部队铁路输送问题进行了系统分析和理论总结,分析了大规模部队铁路输送的特点、需求与组织结构,阐述了决策优化的理论实质,研究解决了其中的难点和核心问题,提出相关模型与算法,并通过仿真进行验证。论文研究有助于相关决策的科学化与合理化,能够满足军事运输工作的要求,可为大规模部队铁路输送工作提供理论指导和方法借鉴。论文主要研究以下问题:(1)大规模部队铁路输送的基础理论研究。论文在分析输送特点、需求与运输条件的基础上,提出了包含决策层、执行层、控制层的分层组织结构,探讨了各层次的职能分工及相互关系。论文将大规模部队铁路输送的决策优化总结为两个基本问题:时间约束-最小容量输送问题(TMCTP)问题与容量约束-最短时间输送问题(CMTTP)问题,分析了两问题的优化处理流程和相互间的密切关系,为决策优化的进一步研究打下基础。(2)大规模部队铁路输送的输送序列问题。论文在分析输送序列的意义、依据与原则的基础上,提出输送序列问题本质是偏序结构的拓扑排序,设计了“决策序列树”方法求解部队的输送序列,并通过算例给予验证。(3)大规模部队铁路输送的输送径路问题。论文在分析输送径路选择的要求与原则基础上,提出知识库、案例库、模型推理机相结合的知识案例推理方法(KCBR)选择输送径路。针对多点至多点输送径路选择的不同类型问题,建立了时间-容量约束的最小费用流问题(TLMCFP)、分阶段-时间-容量约束的最小费用流问题(STLMCFP)、时间约束-最小容量费用流问题(TMCCFP)、分阶段-时间约束-最小容量费用流问题(STMCCFP)、最小时间-费用流问题(MTCFP)等模型作为推理基础,设计了“最小费用最早完成流增广”算法及相关改进算法求解上述模型。(4)大规模部队铁路输送的运行计划问题。论文通过建立数学模型描述了军列运行计划安排问题,在此基础上设计了“固定点号”方法制定并优化运行计划。并基于“固定点号”方法建立了“车站对点号模型”、“多车站对点号模型”、“单径路点号模型”、“多径路点号模型”、“运行时刻模型”等模型。论文提出了分支定界算法和“贪婪点号算法”两种算法求解上述模型并给出算例。(5)大规模部队铁路输送的仿真分析。论文提出了大规模部队铁路输送的Positivistic Petri网仿真模型,研究了列车仿真运行的模拟方法和对突发事件的处理方法,并结合算例对仿真结果进行了指标分析。(6)大规模部队铁路输送的保障研究。论文讨论了部队铁路输送与相关保障之间的关系,研究了在考虑车底循环套用情况下车站的车辆需求,并建立了单车站与多车站车辆需求模型。
黄宇达, 李学威, 赵红专, 王迤冉[10]2016年在《考虑路段拥堵的最短时间流优化问题》文中提出针对以往对交通网络系统中路网时间流问题没有考虑网络拥塞的情况,研究了决策者如何制定最短时间流的决策问题,建立了静态数学规划模型,给出了模型的算法,讨论了算法的复杂性。随后,又对网络时间流问题进行了进一步的深入研究,分析了动态堵塞情形下的时间流特性,考虑交通网络堵塞程度对通过时间的影响,引进堵塞系数,构造动态时间函数,建立了在动态堵塞情况下的最短时间流模型,并给出了模型的算法,同时用算例验证了方法的有效性。
参考文献：
[1]. 动态网络中的流问题[D]. 庞博. 国防科学技术大学. 2009
[2]. 天基信息网络流问题的算法研究[D]. 马宇斌. 国防科学技术大学. 2013
[3]. 容量—时间网络的时间流问题[D]. 陈挚. 国防科学技术大学. 2004
[4]. 动态容量网络中的最小最大时间流问题[J]. 庞博, 谢政, 陈挚, 张军. 计算机工程. 2010
[5]. 连续时间容量网络的最短动态时间流问题[J]. 马宇斌, 谢政, 陈挚. 计算机应用. 2013
[6]. 信息网络中流问题的灵敏度分析[D]. 刘杨杨. 国防科学技术大学. 2014
[7]. 高速网络流量测量关键问题研究[D]. 周爱平. 东南大学. 2015
[8]. 堵塞流理论在路网容量和最短时间流中的应用研究[D]. 黄孝鹏. 南京航空航天大学. 2007
[9]. 大规模部队铁路输送研究[D]. 吴晓东. 北京交通大学. 2008
[10]. 考虑路段拥堵的最短时间流优化问题[J]. 黄宇达, 李学威, 赵红专, 王迤冉. 计算机与数字工程. 2016