在节日期间,旅游已经成为大家追求的时尚,在有限的假期内,合理的安排旅游行程已经成为人们炙手可热的话题。合理安排旅游行程其实这就是一个旅行商问题。旅行商问题是一个经典的组合优化问题,也是一个NP难题。但它在实际中的应用却非常广泛。历年来,人们一直努力的目标,就是寻找一种既有高质量的解,又能快速收敛的近似算法。旅行商问题的研究近几年来已经出现了很多新成果,到目前为止,在国际上主要有迪杰斯特拉(Dijkstra)算法,二叉树方法,Floyd算法,神经网络方法,遗传算法等方法。每种算法都具有自己的优缺点和局限性,其中遗传算法是最适合解决旅行商问题的算法。本文是针对华北地区旅游路线这个区域进行举例分析的。首先,对现有的多种算法进行系统的分析指出其优缺点。接着详细论述了遗传算法求解旅行商问题的几种不同的方案,总结了各种方案的使用范围及其优缺点,以此提出了自己的改进方案。最后本文用VC++程序实现改进方案,找出华北地区的主要旅游景点的最佳旅游路线。