赖志柱，戈冬梅，张云艳（1.贵州工程应用技术学院a.理学院；b.生态工程学院，贵州毕节551700）



求解TSP问题的改进最邻近法

赖志柱1a，戈冬梅1b，张云艳1a
（1.贵州工程应用技术学院a.理学院；b.生态工程学院，贵州毕节551700）

摘要：考察TSP问题的线路构造，建立TSP问题的数学模型，分析了最邻近法的基本思想及不足，通过改进最邻近法构造线路的方向及将所有城市均作为一次线路构造的起点，提出了双向最邻近法、完全最邻近法和完全双向最邻近法三种改进方法，算例表明改进后的方法比最邻近法能获得更多的不同线路及更优的线路。

关键词：TSP问题；最邻近法；线路

1引言

旅行商问题（Traveling Salesman Problem,TSP），也称为旅行推销员问题或货郎担问题，是运筹学、图论以及组合优化中的著名难题，由于其应用的广泛性，引起了人们的极大的兴趣。TSP问题的解决方法可以直接或较容易地应用于解决类似的问题，如交通车辆的巡回线路问题、民航机组人员的轮班安排问题、教师任课班级负荷分配问题、装配线进度问题等。该问题的求解算法主要分为两类：与问题特征相关的启发式搜索算法[1][2]（如动态规划法、分支定界法等）以及独立于问题的智能优化算法[3][4]（如遗传算法、模拟退火算法等）。通常，将TSP问题的启发式方法分为线路构造法、线路改进法和综合法三类[5]，最邻近法是线路构造法中最简单的一种，但该方法对于城市规模较大的TSP问题求解效果较差，本文拟就最邻近法做些改进，以期改进后的方法在线路构造中能给出更优的结果以及对规模较大的TSP问题也有较好的效果。……