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

doi:10.3778/j.issn.1002-8331.2008.25.006

Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (25): 20-23.DOI: 10.3778/j.issn.1002-8331.2008.25.006

• 博士论坛 • Previous Articles Next Articles

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

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

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

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

通讯作者: 黄泽汉

Abstract

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

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

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

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

[1]	MA Xuan, LIU Dong, HU Jiaxin. Particle Swarm Optimization for Solving Problem of k-Shortest Paths via Designated Points [J]. Computer Engineering and Applications, 2019, 55(20): 89-94.
[2]	FAN Yuanyuan1，YANG Bin2. Triangular mesh segmentation based on fundamental group [J]. Computer Engineering and Applications, 2011, 47(32): 180-182.
[3]	WANG Shuo,YOU Feng,SHAN Lan,ZHAO Heng-yong. Research of Chinese word segmentation system applies in professional search engine [J]. Computer Engineering and Applications, 2008, 44(19): 142-145.

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

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 3

Recommended Articles

Metrics