连续时间容量网络的最短动态时间流问题

发布时间：2019-05-08 07:47

【摘要】：针对一类带节点处理速率限制的连续时间容量网络,提出了该网络中的最短动态时间流问题,并给出其线性规划形式;通过分析该网络与经典网络之间的内在联系,利用最大接收流和退流的思想分别设计出准确求解两种网络最短动态时间流的高效算法;证明了算法的正确性并分析出算法有较小的复杂度;最后,通过一个算例演示了算法的执行。
[Abstract]:For a class of continuous-time capacity networks with node processing rate constraints, the shortest dynamic time flow problem in the network is proposed, and its linear programming form is given. By analyzing the inherent relationship between the network and the classical network, an efficient algorithm for accurately solving the shortest dynamic time flow of the two networks is designed by using the idea of the maximum receiving flow and the backflow. The correctness of the algorithm is proved and the complexity of the algorithm is analyzed. Finally, an example is given to demonstrate the implementation of the algorithm.
【作者单位】： 国防科学技术大学理学院;
【分类号】：TP393.0

【参考文献】

相关期刊论文 前5条

1 庞博;谢政;陈挚;张军;;动态容量网络中的最小最大时间流问题[J];计算机工程;2010年07期

2 高飞,王光兴,阎家斌;计算无线通信网络2-终点可靠性的快速算法[J];计算机应用;2004年01期

3 高明霞;贺国光;;一类点权网络的最小费用流问题[J];武汉理工大学学报(交通科学与工程版);2012年03期

4 孙奥;朱桂斌;江铁;史名一;;一种时间依赖路网最小时间路径规划算法研究[J];计算机应用研究;2012年11期

5 李荣胜;赵文峰;徐惠民;;网格作业完工时间与作业分割粒度的关系[J];计算机应用;2011年02期

【共引文献】

相关期刊论文 前10条

1 孙小军;王志强;;带负权最短路问题前趋法的改进[J];安徽大学学报(自然科学版);2009年02期

2 王德忠,方健;切槽加工走刀路径优化问题的处理[J];包装工程;2002年04期

3 杨罗辉;;一类基于模糊图论的费用与时间最优化问题的模型[J];长春大学学报;2007年12期

4 郝自军;何尚录;;最短路问题的Floyd算法的若干讨论[J];重庆工学院学报(自然科学版);2008年05期

5 王兴伟,王岳昭,郑连伟,刘积仁;一种基于服务质量的点对点通信路由选择算法[J];东北大学学报;2000年02期

6 胡雷刚;付新华;肖明清;许明;;基于随机遗传算法的并行测试任务调度研究[J];电测与仪表;2008年10期

7 林农;;旅行商问题图论近似算法有效性分析[J];东莞理工学院学报;2012年01期

8 邓丰;陈楠;曾祥君;李泽文;程远林;袁超;;基于图论的电网故障行波定位装置最优配置算法[J];电力系统自动化;2010年11期

9 左郑敏,吴耀武,熊信艮,张正陵;联合电力网中最短路径的小偏差量δ算法[J];电力系统及其自动化学报;2000年06期

10 陈自力;潘燕燕;王军祥;;最小费用算法在城市交通网络中的应用[J];电脑知识与技术;2006年20期

相关会议论文 前4条

1 冷洪泽;谢政;徐桢;;基于带固定费用运输问题的自适应并行搜索算法研究[A];2008通信理论与技术新进展——第十三届全国青年通信学术会议论文集（上）[C];2008年

2 陈豪;何童;李传胪;;多层电磁屏蔽拓扑图的分析方法及应用[A];2005通信理论与技术新进展——第十届全国青年通信学术会议论文集[C];2005年

3 胡向东;王平;聂能;陈天基;;邮政运输指挥调度网路优化系统的设计与实现[A];1999年中国智能自动化学术会议论文集（下册）[C];1999年

4 王平;胡向东;;敏捷制造模式下的物流配送决策支持系统[A];2001年中国智能自动化会议论文集（下册）[C];2001年

相关博士学位论文 前10条

1 王伟;铁路网抗毁性分析与研究[D];北京交通大学;2011年

2 陈德良;物流网络可靠性的关键问题与应用研究[D];中南大学;2010年

3 王兵;逻辑进程范型的形式语义、算法评估及其在空间随机仿真中的应用[D];国防科学技术大学;2011年

4 李光;分类挖掘中的隐私保护问题研究[D];哈尔滨工业大学;2011年

5 张强;基于连通性的无线传感器网络节点定位技术研究[D];天津大学;2011年

6 王旭东;基于图论的智能电网最优孤岛划分模型和算法[D];天津大学;2011年

7 杨威;协作认知无线电网络优化模型与算法研究[D];国防科学技术大学;2011年

8 葛悦;模糊环境下若干网络优化问题的模型及其算法研究[D];哈尔滨工业大学;2012年

9 牛东晓;非确定性工程项目计划管理的新方法研究[D];华北电力大学;2002年

10 余燕平;多播路由算法的研究[D];浙江大学;2002年

相关硕士学位论文 前10条

1 董鹏飞;路由算法及过滤器部署算法的研究与分析[D];郑州大学;2010年

2 贾春风;IP网络合法监听规则的研究和实现[D];北京交通大学;2011年

3 周林涛;综合决策及其网络应用[D];昆明理工大学;2008年

4 毛凯;基于网络编码的无线广播重传算法研究[D];西安电子科技大学;2011年

5 薛韬;基于Web的通用虚拟实验平台设计与实现[D];西安电子科技大学;2009年

6 韩然然;西部地区公路网连通可靠性分析方法研究[D];北京交通大学;2011年

7 肖传宇;高速公路沿线应急资源优化配置系统研究[D];武汉理工大学;2011年

8 于江龙;无线传感器网络容错性及拓扑控制问题研究[D];杭州电子科技大学;2011年

9 吕静;会议选址和警车巡逻问题的算法研究[D];暨南大学;2011年

10 罗晓;智能化教学辅助训练系统[D];华东师范大学;2011年

【二级参考文献】

相关期刊论文 前9条

1 孔繁甲,乔百友,王光兴;无线广播网络的可靠性的一个算法[J];东北大学学报;1998年05期

2 何俊;戴浩;宋自林;刘刚;;时间依赖的交通网络模型及最短路径算法[J];解放军理工大学学报(自然科学版);2005年06期

3 孙艳蕊,张祥德,刘运妙;无线通讯网络可靠度的计算[J];计算机工程与应用;2001年06期

4 章昭辉;;一种基于离散变权网络的动态最短路径快速算法[J];计算机科学;2010年04期

5 余伟辉;陈闳中;;时间依赖有向无环网最小时间路径算法[J];计算机工程与科学;2008年11期

6 谭国真,高文;时间依赖的网络中最小时间路径算法[J];计算机学报;2002年02期

7 张涛;柳重堪;张军;;卫星时变拓扑网络最短路径算法研究[J];计算机学报;2006年03期

8 李星毅;翟晓峰;施化吉;;最小时间路径算法的改进及在路径优化中的应用[J];计算机应用研究;2008年06期

9 董振宁,孔淑兰;连续时间网络上的最小费用流问题[J];山东大学学报(理学版);2003年02期

相关硕士学位论文 前1条

1 张廷;城市道路行程时间预测研究[D];湖南大学;2010年

，

本文编号：2471730