一类点权网络的最小费用流问题

以城市路网为背景求最小费用流时不能忽略交叉口的费用和通行能力限制,但由于交叉口延误等费用和通行能力具有方向性,普通最小费用流算法无法直接应用于这类问题.文中以节点权重表示交叉口的延误和通行能力,将城市道路网表示为一个节点具有分方向权重的点权网络,提出了一个改进的最小费用路算法求解这类点权网络中的最小费用流问题.算法计算时间复杂性为O(nmf0).以一个数值算例说明了算法的应用.     

基于最大流的路网结构优化

用组合图论法构造道路网络的赋权有向图,分析路网结构的均衡性,确定造成路网不均衡的关键路段．利用网络可行流的平衡关系,以流等价和点守恒原则为约束条件,建立网络最大流模型．根据最大流最小割定理,用割集矩阵法求网络的最大流．网络流量最大时,那些流量饱和的路段即为关键路段．增加关键路段的通行能力,即可增加路网的通行能力．     

交通运输网络中两个结点间有流量约束的最小费用最大流算法

对交通运输网络最小费用最大流的分配是在满足容量限制条件和流量守恒条件下,基于总费用最低的原则进行的,但在实际应用中,通常对交通运输网络中两个结点之间的流量有具体的要求和约束限制条件.针对交通运输网络中两个结点之间有流量约束的最小费用最大流问题进行了分析,总结了两个结点之间的流量不能超过限制值、不能低于限制值以及在一定范围内的3种约束条件.基于连续最短路算法中构造伴随增流网络的思路,设计了这3种约束限制条件下的最小费用最大流分配算法.利用这个算法,可以解决交通运输网络中两个结点之间有流量约束的最小费用最大流分配问题.在交通运输领域,两个结点之间有流量约束的最小费用最大流问题普遍存在,这些算法也为解决实际的运输问题提供了应用基础.     

基于GA的动态时延受限多播路由算法

探讨了包交换计算机网络中，具有端到端时延限制的动态多播路由问题．提出了一种基于遗传算法(GA)的动态时延受限多播路由优化算法．当节点加入或退出时，算法先利用Dijkstra第k最短路径算法求出节点到源点的最短路径集，再用遗传算法搜索最小多播树，仿真试验表明该算法可以动态求得满足时延约束的最小多播树．     

有流量需求和分品种容量限制的运输网络最大流算法

基于Ford-Fulkerson算法求最大流的思路,对有流量需求的分品种容量限制的运输网络构造最大流算法,将有流量需求的转运节点分为转运节点和汇节点,同时构建单源单汇,寻找增流链进行流量调整。最后,通过示例对算法进行验证,计算出了满足流量需求和分品种容量限制的运输网络的最大流。     

基于价格机制的无线多跳网络拥塞控制算法

为有效缓解拥塞,并在QoS保证与业务公平性之间找到合适的平衡点,基于定价机制提出了一种链路层逐跳拥塞控制算法.该算法考虑了MAC的时间限制和二进制干扰模型限制,将传输失败率作为网络拥塞的控制准则之一引入拥塞价格函数中;流路径上的每个节点根据接收到的拥塞价格动态调整每个流的传输速率;优化目标是系统中总的流效用之和达到权重比例公平.此外,还考虑了节点内部流的调度策略,根据等待时间函数动态调整节点内各个流的优先级,以保证每个流的QoS需求和公平性.仿真结果表明:提出的拥塞控制策略能够有效缓解链路拥塞,系统总吞吐率比未采用拥塞控制机制提高约41%,公平性提高约29%,且极大地改善了平均时延、平均丢包率、平均吞吐率等其他性能指标.     

基于复杂网络理论的地铁线网脆弱性分析

针对突发事件造成的节点失效会严重影响地铁运营的效率这一问题,提出了一套基于复杂网络理论的地铁线网脆弱性分析方法。以武汉市现阶段地铁线网为例,采用Pajek构建了涵盖58个站点,57条连接边的当前城市地铁线网拓扑结构图,系统分析了随机攻击和蓄意攻击模式下城市地铁网络的静态与动态脆弱性水平。结果表明:累计节点蓄意攻击对地铁线网破坏性最大,随机攻击次之,单个节点蓄意攻击最小,度大节点为线网中的脆弱点。     

带有区间数弧容量上限的网络优化

提出了弧容量上限为区间数的网络优化问题;给出了保守最大流、乐观最大流、最小风险代价乐观最大流和最小风险代价流的定义和数学模型;针对目标函数的非线性特性,设计了特殊的算法步骤;引入可调圈概念,通过求最大流和给定流配流问题的多重解以获得最小风险代价最优解;最后,本文还给出了算例,验证了算法的有效性．     

容量及转运点限制的多品种交通网最小代价流

传统的运送问题是在运送品种单一、运送条件理想情况下的最小代价流分配,但在实际的交通网络应用中,往往会出现多品种流的运送问题。同时,由于设备的限制,在同一个阶段的不同品种流的容量限制也可能不尽相同,不同品种在转运点的接发能力也不尽相同。本文主要考虑解决各品种的容量约束以及转运点的最大接发能力问题,分情况讨论复合指标修改规则,通过增流链调整规则修改复合参数,并根据汇的调整量修改复合指标,构造不需要改变网络拓扑结构的最小代价流算法。此算法不需要构造增流网络,也避免了二次求解问题。最后通过示例给出了具体的算法步骤,为以后在此基础上的优化研究提供基础。     

城市轨道交通换乘节点与网络运行效率关系研究

换乘节点是城市轨道交通不同线路间转乘的必经场所,对城市轨道交通系统运行有重要影响.本文基于复杂网络理论,将平均路径长度、网络局部效率和网络全局效率作为网络运行效率的评价指标,研究了换乘节点比例、换乘节点衔接线路数及换乘节点分布与网络运行效率的变化关系.研究表明,网络平均路径长度随换乘节点比例、换乘节点衔接线路数增加呈幂函数降低;网络局部效率随换乘节点比例增加呈指数下降,网络全局效率随换乘节点比例增加呈对数增加且换乘效率越高,增长越明显;换乘节点衔接线路数的增加会降低网络局部效率,增加网络全局效率;换乘节点在各线路分布越均匀,网络全局效率越高.     

一类流量增减最大值可预见的不确定网络最大流的模型与算法

不确定网络最大流问题是现实中普遍存在的一种网络流问题,针对该问题中的流在传输过程中增减并存的特征给出了一种模型及算法.将其网络上增加弧上的增加量作为初始输入量之一,经过特定运算将其转化为只损耗网络,运用有损耗网络最大流问题的算法进行最终求解.最后,通过实例验证了其正确性.     

战时动态交通网络最大能力路径问题算法研究

战时或应急条件下,交通网络具有动态特征,研究确定动态交通网络的最大能力路径,不但可以拓展最大流问题基本理论,而且对于完成大规模军用物资的运输保障任务,也有着十分重要的现实意义。提出了动态交通网络最大能力路径的概念,并基于最大流理论,结合实例介绍了寻找最大能力路径的具体算法,有助于紧急情况下确定交通网络中的最大能力路径。     

一种接收端与中间节点混合驱动的友好拥塞控制机制

针对目前拥塞控制算法中UDP流引起拥塞而不能采取有效调整的问题,在网络QoS环境下对其进行了研究;采用由接收端驱动与中间节点混合驱动的拥塞控制机制,满足多媒体应用中UDP和TCP流之间的友好性要求.将此机制用NS2进行模拟,结果显示:在友好性、吞吐量及丢包率方面,RMDCC算法比TFRC算法有改善.     

瓶颈路段上拥挤收费水平与收费时段的优化问题

本文主要在瓶颈路段建立单一收费方案,并且优化瓶颈路段上的拥挤收费水平 和收费时段.首先,应用 Greenshields 模型描述了瓶颈路段上流量的演化过程,并计算每个 时刻出行者的出行时间和出行费用.通过出行费用与流量的关系调整每个时刻流量的分 配,得到稳定状态时排队的长度和运动部分的速度.然后,建立双层规划模型,其中上层模 型是最小化最大排队车辆数和最大化运动部分的最小速度,下层模型是应用 Greenshields 模型模拟出行者的出行行为.应用改进的遗传算法求解双层规划模型,得到最优的收费水 平和收费时段.最后,应用一个简单的算例来验证本文所建立的模型及其算法,并且通过 变换参数来分析所得到的现象和结论.     

基于点线能力约束的多层级节点协同布局优化模型及算法研究

多层级物流节点布局对物流系统的降本增效具有重要作用. 提出物流网络简化处理策略，结合实际物理网络结构，以最短路径、共同弧段及通道运能三要素为重点构建了多层级物流节点的网络拓扑；在此基础上，结合不同层级物流节点的最大服务半径、服务能力及成本等属性，系统性考虑节点及通道运能，构建基于点线能力约束的多层级节点协同布局优化模型；结合模型决策变量特点，利用改进的和声搜索算法进行求解. 采用实际案例进行测试和应用，进行相应情景分析. 结果表明，模型及算法具有良好的适应性，为实际多层级物流节点选址提供一定决策依据.     

Network lifetime global optimization for multi-source and single-sink topology in wireless sensor networks

The multi-source and single-sink (MSSS) topology in wireless sensor networks (WSNs) is defined as a network topology, where all of nodes can gather, receive and transmit data to the sink. In energy-constrained WSNs with such a topology, the joint optimal design in the physical, medium access control (MAC) and network layers is considered for network lifetime maximization (NLM). The problem of integrating multi-layer information to compute NLM, which involves routing flow, link schedule and transmission power, is formulated as a non-linear optimization problem. Specially under time division multiple access (TDMA) scheme, this problem can be transformed into a convex optimization problem. To solve it analytically we make use of the property that local optimization is global optimization in convex problem. This allows us to exploit the Karush-Kuhn-Tucker (KKT) optimality conditions to solve it and obtain analytical solution expression, i.e., the globally optimal network lifetime (NL). NL is derived as a function of number of nodes, their initial energy and data rate arrived at them.Based on the analysis of analytical approach, it takes the influence of data rates, link access and routing method over NLM into account. Moreover, the globally optimal transmission schemes are achieved by solution set during analytical approach and applied to algorithms in TDMA-based WSNs aiming at NLM on OMNeT<++> to compare with other suboptimal schemes.     

运能不匹配的城市轨道交通换乘方案研究

城市轨道交通换乘站有别于普通车站,其影响因素众多,应重点考虑换乘客流对车站设计方案的影响。在运能不匹配的情况下,对同台换乘、节点换乘、通道换乘等多种换乘方式的客流承载力进行验算,得到不同换乘方式承担大换乘客流的风险能力。当运能不匹配的轨道交通线路间换乘时,首先应选择合理的换乘节点,尽量采用多点换乘,避免大换乘客流集中产生风险,其次应适当增加换乘车站规模。当换乘站位于大断面区段存在较大客流风险时,应慎重选择同台换乘方式,可考虑通道换乘;当换乘站位于客流小断面区段存在较小的客流风险时,可优先选择换乘便捷的同台换乘或者节点换乘。总之,运能不匹配的换乘站应依据不同的客流特征选择合理的换乘方式,在满足换乘能力的前提下,优先选择换乘便捷、服务水平高的换乘方式。     

轨道交通车站大客流事件的形成、传播及对策

为定量分析轨道交通车站大客流事件形成及传播机理并提出应对策略,从大客流事件界定入手,将其发生与否归结为车站容量、输送能力及乘客到达流量之间的数量关系。区分大型活动大客流、事故/故障大客流、高峰小时大客流3类大客流事件,定量分析其形成原理,同时给出其影响的传播机理,在此基础上有针对性地提出应对策略。研究结果表明,当车站乘客到达流量与车站输送能力叠加后的流量超过车站容量并继续增加时,大客流事件将发生,并通过"涟漪反应"将其影响在轨道交通网络中传播。为此,可从事件预防、应急处置和事后评估三个层次,以及控制到达流量、提高服务能力、加强客流组织和关注薄弱环节四个方面来制定大客流事件应对策略。     

超级拥挤公交网络均衡配流

使用公交路段的表示方法描述公交网络,公交路段上的出行费用受拥挤影响,公交车辆上的乘客流量受车辆运营能力限制.在拥挤影响和能力限制的双重约束下,建立公交乘客均衡配流模型,设计求解算法并给出算例.模型和算法尤其适用于高峰时期乘客流量大于线路运营能力的超级拥挤公交网络均衡配流.     

多品种流中特定品种在结点上的流量有要求的最大流算法设计

本文首先分析多品种流交通网络的特性,在借鉴Ford-Fulkerson算法的基础上构造了求多品种问题最大流的基于多品种流的Ford-Fulkerson算法。然后分析了多品种流交通网络对特定品种在结点上的流量有要求的几种情况,并设计了这几种情况下交通网络求最大流的算法。在实际交通网络中多品种流问题普遍存在,对特定结点的品种的流量有要求的多品种问题更是不胜枚举,本文的算法为解决实际问题提供了应用基础。