并行计算解决部队铁路梯队装载NP问题应用研究  

Application Research of Parallel Computing in Resolving the Military Railway Echelon Loading NP Problem

作　　者：韦广银[1] 杨镭[1] 刘中[2] 周飞飞[2] 于鹏[2] 

机构地区：[1]军事交通学院研究生管理大队,天津300161 [2]军事交通学院军事交通系,天津300161

出　　处：《军事交通学院学报》2009年第2期9-12,共4页Journal of Military Transportation University

摘　　要：梯队装载问题是铁路军事运输中的典型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.

关 键 词：并行计算 梯队装载 NP完全问题 

分 类 号：U294.893[交通运输工程—交通运输规划与管理]