大规模定量传输的时间扩展网络K最短路径算法

doi:10.3778/j.issn.1002-8331.2008.25.006

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (25): 20-23.DOI: 10.3778/j.issn.1002-8331.2008.25.006

大规模定量传输的时间扩展网络K最短路径算法

黄泽汉^1,2,谭跃进¹,邓宏钟¹

1.国防科技大学信息系统与管理学院，长沙 410073
2.海军工程大学管理工程系，武汉 430033

收稿日期:2008-01-10 修回日期:2008-06-10 出版日期:2008-09-01 发布日期:2008-09-01
通讯作者: 黄泽汉

Time-expanded network K shortest paths algorithm for over-loading transportations

HUANG Ze-han^1,2,TAN Yue-jin¹,DENG Hong-zhong¹

1.College of Information System and Management，National University of Defense Technology，Changsha 410073，China
2.Department of Management Engineering，Naval University of Engineering，Wuhan 430033，China

Received:2008-01-10 Revised:2008-06-10 Online:2008-09-01 Published:2008-09-01
Contact: HUANG Ze-han

摘要/Abstract

摘要： 大规模的军用物资调度，需要传输的物资远远超出保障网络实际传输能力的情况下，现有的Dijkstra算法、Floyd算法以及传统的网络K-最短路径算法，难以求解这类网络调度优化问题。在蚁群算法的基础上，设计了一种基于时间扩展的网络K-最短路径算法，满足网络传输一致性假设的前提下，求解大规模定量传输问题。最后给出面向任务的物流保障网络调度的应用实例，获得满意的网络调度优化方案。

关键词: 物流保障网络, 网络调度, 最短路径

Abstract: The mass multi-commodity network scheduling problems can not be solved by the Dijkstra，the Floyd and the other the conventional static algorithms under over-loading transportation.Based on the Hypotheses of the temporal consistency of transportation，this paper presents a time-expanded network K shortest paths algorithm（TEN-KSP）.In the last，a application case on the logistics support network scheduling problems is studied by this algorithm，and satisfied optimal solutions are gained.

Key words: logistics support network, networks scheduling, shortest paths

黄泽汉^1,2,谭跃进¹,邓宏钟¹. 大规模定量传输的时间扩展网络K最短路径算法[J]. 计算机工程与应用, 2008, 44(25): 20-23.

HUANG Ze-han^1,2,TAN Yue-jin¹,DENG Hong-zhong¹. Time-expanded network K shortest paths algorithm for over-loading transportations[J]. Computer Engineering and Applications, 2008, 44(25): 20-23.

[1]	李俊. 结合最短路径改进的社会力人群疏散仿真模型[J]. 计算机工程与应用, 2021, 57(8): 264-270.
[2]	叶颖诗，魏福义，蔡贤资. 基于并行计算的快速Dijkstra算法研究[J]. 计算机工程与应用, 2020, 56(6): 58-65.
[3]	李艳，王阳阳，张红岩，武优西. 不可达顶点剪枝算法及其在最短路径中的应用[J]. 计算机工程与应用, 2020, 56(15): 51-57.
[4]	张昕，严沛，郭阳，王慧慧. 基于k-shell的复杂网络最短路径近似算法[J]. 计算机工程与应用, 2019, 55(14): 54-60.
[5]	张林霞，何利文，黄俊. 基于SDN网络的安全设备路由研究[J]. 计算机工程与应用, 2018, 54(4): 103-109.
[6]	高遵海，高颖，程果. 图的赋权路径矩阵与所有点对最短路径问题[J]. 计算机工程与应用, 2017, 53(9): 47-50.
[7]	应文杰，徐开，徐少平. 羽毛球机器人机械臂运动轨迹多目标规划[J]. 计算机工程与应用, 2017, 53(3): 258-265.
[8]	姚博1，冯宏伟1，高原2，马佳丽1，冯筠1. 过必经节点集的动态剪枝搜索算法[J]. 计算机工程与应用, 2017, 53(15): 57-62.
[9]	袁亚博，刘羿，吴斌. 改进蚁群算法求解最短路径问题[J]. 计算机工程与应用, 2016, 52(6): 8-12.
[10]	韩建妙，刘业政. 基于遗传算法的超市最短导购路径推荐[J]. 计算机工程与应用, 2016, 52(4): 238-242.
[11]	孟颖翔1，高东怀2，许浩2，许卫中2. 基于最短路径的多子网链路层拓扑发现算法[J]. 计算机工程与应用, 2016, 52(2): 131-134.
[12]	侯晓琴1，胡志华1，高超峰1，罗勋杰2. 自动化仓库巷道网络AGV货区遍历优化——设计基于优先权遗传算法实现[J]. 计算机工程与应用, 2016, 52(12): 31-36.
[13]	吴幸良，涂风华. 采用图模型的个性化标签推荐方法[J]. 计算机工程与应用, 2015, 51(9): 142-146.
[14]	黄书力，胡大裟，蒋玉明. 经过指定的中间节点集的最短路径算法[J]. 计算机工程与应用, 2015, 51(11): 41-46.
[15]	耿显亚，许峰. 基于图论模型的一类集成电路布线算法[J]. 计算机工程与应用, 2015, 51(1): 21-25.

大规模定量传输的时间扩展网络K最短路径算法

Time-expanded network K shortest paths algorithm for over-loading transportations

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics