摘要
旅行推销商问题(TSP)属于组合优化领域中一个典型的NP Hard问题。本文在最近城市搜索法的基础上,提出一种改进的启发式算法———两端延伸最近城市搜索法,这种方法能够很快得到最优解(近优解),且大大降低了计算复杂度。同时,对TSP问题进行了分类,并给出相应的启发式解法。
The traveling salesman problem(TSP) is one of the typical NP-Hard problems in combination optimization.In this paper,an improved heuristics algorithm,both ends extending and nearest city searching,for solving traveling salesman problem is put forward based on the method of nearest city searching.Using this method,the optimum solution can be quickly achieved,and the complexity of computation is simplified.At the same time,all kinds of TSP and their heuristics algorithms are given.
出处
《管理工程学报》
CSSCI
2005年第2期114-118,共5页
Journal of Industrial Engineering and Engineering Management
基金
陕西省自然科学基金资助项目(2000DG06)
关键词
旅行推销商问题
启发式算法
最近城市搜索
traveling salesman problem(TSP)
heuristics algorithm
nearest city searching
