摘要
梯队装载问题是铁路军事运输中的典型NP问题。在分析铁路军事运输梯队装载问题的基础上,提出以长度为基本数据,以军列换长最小和使用车辆总数最少为目标的装载优化模型,证明了该问题是NP完全问题。针对普通计算机求解梯队装载问题计算能力不足的实际,引入并行计算技术,用并行全枚举法进行求解数学模型。最后通过实例分析,验证了算法的可行性和有效性。
Echelon loading problem is a typical NP problem in military railage. Based on analyzing the echelon loading problem in military railage, this paper proposes a loading optimization model based on length, with the total length of train and total vehicular amount as optimization target. The problem is proved to be a NP - complete problem. Considering to the computing disability of common PC, parallel computing is introduced, and a parallel algorithm of full permutation is used to solve this model. In the end, an experiment is performed so as to show the feasibility and effectiveness of the algorithm.
出处
《军事交通学院学报》
2009年第2期9-12,共4页
Journal of Military Transportation University
关键词
并行计算
梯队装载
NP完全问题
parallel computing
echelon loading
NP - complete problem
