文章目录

一、算法合辑1.1 SA模拟退火算法1.2 TS禁忌搜索算法1.3 ACO蚁群算法1.4 GA遗传算法1.5 ILS迭代局部搜索算法1.6 VNS变邻域搜索算法1.7 ALNS自适应大邻域搜索算法 二、算法运行示例三、测试用例说明四、TSP路径可视化

一、算法合辑

1.1 SA模拟退火算法

【运筹优化】SA模拟退火算法求解TSP问题(Java实现)

模拟退火算法求解tsp问题：48个城市...初始解为：[0, 4, 5, 9, 17, 10, 16, 36, 38, 13, 43, 11, 20, 30, 3, 7, 21, 25, 37, 39, 42, 18, 45, 8, 47, 29, 41, 12, 28, 34, 32, 19, 24, 2, 31, 33, 26, 6, 23, 44, 1, 14, 22, 27, 35, 46, 40, 15]最佳迭代次数:20436最短路程为（伪欧氏距离）：13258.608285728313最佳路径为：[21, 40, 15, 7, 37, 30, 43, 36, 18, 26, 16, 42, 29, 5, 27, 35, 6, 17, 45, 32, 19, 46, 47, 25, 3, 1, 28, 33, 2, 22, 10, 12, 13, 24, 4, 41, 9, 34, 44, 23, 31, 38, 20, 11, 14, 39, 8, 0, 21]求解用时：0.472 s-------------------------------------------------------------------------模拟退火算法求解tsp问题：48个城市...初始解为：[0, 40, 14, 34, 25, 8, 37, 22, 13, 2, 24, 1, 19, 38, 47, 11, 45, 36, 9, 17, 27, 10, 12, 26, 46, 15, 32, 18, 35, 6, 20, 4, 7, 43, 44, 31, 5, 41, 30, 21, 3, 28, 42, 23, 16, 39, 29, 33]最佳迭代次数:8331最短路程为（欧氏距离）：39498.407326103916最佳路径为：[4, 47, 25, 3, 34, 44, 9, 23, 41, 1, 28, 40, 15, 7, 37, 30, 45, 43, 17, 6, 36, 18, 26, 16, 42, 29, 5, 27, 35, 32, 19, 46, 20, 31, 38, 24, 12, 10, 39, 8, 0, 21, 2, 14, 11, 22, 13, 33, 4]求解用时：0.474 s-------------------------------------------------------------------------

1.2 TS禁忌搜索算法

【运筹优化】(改进)TS禁忌搜索算法求解TSP问题(Java实现)

数组型禁忌搜索求解tsp问题：48个城市...初始解：[8, 9, 16, 7, 46, 22, 6, 5, 41, 18, 30, 35, 0, 26, 23, 3, 37, 27, 17, 39, 1, 14, 10, 42, 20, 38, 28, 34, 33, 44, 29, 47, 24, 15, 13, 25, 19, 43, 21, 11, 40, 4, 45, 32, 12, 31, 2, 36]最佳迭代次数:62437最短路程为(伪欧氏距离)：10671.03579944003最佳路径为：[14, 32, 45, 35, 29, 42, 26, 16, 18, 36, 5, 27, 6, 17, 43, 30, 37, 8, 7, 0, 39, 2, 21, 15, 40, 33, 28, 1, 25, 3, 34, 44, 9, 23, 41, 4, 47, 38, 31, 20, 12, 24, 13, 22, 10, 46, 19, 11, 14]求解用时：2.157 s-------------------------------------------------------------------------数组型禁忌搜索求解tsp问题：48个城市...初始解：[39, 21, 6, 47, 42, 24, 33, 22, 0, 2, 46, 8, 16, 25, 27, 29, 45, 36, 44, 3, 26, 41, 9, 17, 20, 10, 1, 14, 12, 31, 5, 13, 37, 19, 35, 28, 18, 34, 40, 4, 7, 15, 23, 38, 30, 43, 32, 11]最佳迭代次数:97655最短路程为(欧氏距离)：33555.27645708514最佳路径为：[8, 7, 0, 39, 14, 11, 10, 12, 24, 13, 22, 2, 21, 15, 40, 33, 28, 1, 25, 3, 34, 44, 9, 23, 41, 4, 47, 38, 31, 20, 46, 19, 32, 45, 35, 29, 42, 16, 26, 18, 36, 5, 27, 6, 17, 43, 30, 37, 8]求解用时：2.412 s-------------------------------------------------------------------------

树型禁忌搜索求解tsp问题：48个城市...初始解：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47]最佳迭代次数:1327最短路程为（伪欧氏距离）：11784.944565636517最佳路径为：[47, 4, 28, 33, 2, 0, 7, 8, 37, 30, 43, 17, 6, 27, 18, 36, 5, 42, 16, 26, 29, 35, 45, 32, 14, 11, 19, 46, 12, 20, 38, 31, 23, 9, 44, 34, 3, 25, 41, 1, 40, 15, 21, 39, 10, 22, 13, 24, 47]求解用时：3.443 s-------------------------------------------------------------------------树型禁忌搜索求解tsp问题：48个城市...初始解：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47]最佳迭代次数:1550最短路程为（欧氏距离）：38188.50171871759最佳路径为：[23, 44, 34, 3, 25, 1, 28, 33, 40, 15, 37, 30, 43, 17, 6, 35, 32, 11, 10, 12, 38, 31, 20, 46, 19, 29, 42, 16, 26, 18, 36, 5, 27, 45, 14, 39, 8, 7, 0, 21, 2, 22, 13, 24, 47, 4, 41, 9, 23]求解用时：3.377 s-------------------------------------------------------------------------

1.3 ACO蚁群算法

【运筹优化】ACO蚁群算法求解TSP问题(Java实现)

蚁群算法求解tsp问题：48个城市...最佳迭代次数:156最短路程为（伪欧氏距离）：11107.778186984036最佳路径为：[46, 12, 24, 13, 22, 10, 11, 14, 45, 32, 19, 16, 42, 26, 18, 36, 5, 29, 35, 27, 6, 17, 43, 30, 37, 7, 0, 8, 39, 2, 21, 15, 40, 33, 47, 4, 28, 1, 25, 3, 34, 44, 9, 41, 23, 31, 38, 20, 46]求解用时：2.885 s-------------------------------------------------------------------------蚁群算法求解tsp问题：48个城市...最佳迭代次数:44最短路程为（欧氏距离）：35156.69540961502最佳路径为：[39, 8, 37, 30, 43, 17, 6, 27, 35, 29, 5, 36, 18, 26, 42, 16, 19, 32, 45, 14, 11, 10, 22, 13, 24, 12, 46, 20, 31, 38, 47, 4, 41, 9, 23, 44, 34, 3, 25, 1, 28, 40, 33, 2, 21, 15, 0, 7, 39]求解用时：2.781 s-------------------------------------------------------------------------

1.4 GA遗传算法

【运筹优化】GA遗传算法求解TSP问题(Java实现)

遗传算法求解tsp问题：48个城市...初始解为：39492.9415375181最佳迭代次数:18085最短路程为（伪欧氏距离）：11716.839185306864最佳路径为：[37, 0, 7, 8, 39, 14, 32, 11, 10, 22, 40, 15, 21, 2, 33, 13, 12, 24, 4, 47, 28, 1, 3, 25, 41, 9, 34, 44, 23, 31, 38, 20, 46, 19, 45, 35, 6, 5, 36, 18, 16, 42, 26, 29, 27, 17, 43, 30, 37]求解用时：3.007 s-------------------------------------------------------------------------遗传算法求解tsp问题：48个城市...初始解为：126129.1728169最佳迭代次数:94162最短路程为(欧氏距离)：37319.47142582528最佳路径为：[21, 15, 40, 33, 2, 13, 24, 4, 28, 1, 25, 3, 34, 44, 9, 23, 41, 47, 38, 31, 20, 46, 22, 12, 10, 11, 19, 32, 45, 29, 26, 18, 36, 16, 42, 5, 35, 17, 27, 6, 43, 30, 37, 14, 39, 8, 7, 0, 21]求解用时：3.044 s-------------------------------------------------------------------------

1.5 ILS迭代局部搜索算法

【运筹优化】ILS局部迭代搜索算法求解TSP问题(Java实现)

局部迭代搜索算法求解tsp问题：48个城市...初始解为：[0, 29, 13, 35, 12, 23, 11, 19, 6, 43, 45, 10, 16, 9, 39, 47, 25, 3, 22, 31, 28, 27, 21, 7, 46, 37, 15, 41, 44, 26, 14, 33, 40, 30, 8, 1, 20, 18, 34, 38, 4, 5, 2, 24, 42, 32, 36, 17]最佳迭代次数:0最短路程为（伪欧氏距离）：10601.127449906018最佳路径为：[15, 21, 2, 22, 13, 24, 12, 10, 11, 14, 39, 8, 0, 7, 37, 30, 43, 17, 6, 27, 5, 36, 18, 26, 16, 42, 29, 35, 45, 32, 19, 46, 20, 31, 38, 47, 4, 41, 23, 9, 44, 34, 3, 25, 1, 28, 33, 40, 15]求解用时：0.278 s-------------------------------------------------------------------------局部迭代搜索算法求解tsp问题：48个城市...初始解为：[0, 23, 46, 39, 4, 36, 24, 6, 5, 44, 20, 17, 15, 19, 18, 2, 32, 28, 7, 8, 11, 12, 3, 10, 31, 37, 42, 41, 43, 13, 21, 40, 30, 14, 29, 1, 16, 27, 38, 33, 25, 35, 47, 9, 45, 26, 34, 22]最佳迭代次数:0最短路程为（欧式距离）：33555.276457085136最佳路径为：[47, 38, 31, 20, 46, 19, 32, 45, 35, 29, 42, 16, 26, 18, 36, 5, 27, 6, 17, 43, 30, 37, 8, 7, 0, 39, 14, 11, 10, 12, 24, 13, 22, 2, 21, 15, 40, 33, 28, 1, 25, 3, 34, 44, 9, 23, 41, 4, 47]求解用时：0.288 s-------------------------------------------------------------------------

1.6 VNS变邻域搜索算法

【运筹优化】VNS变邻域搜索算法求解TSP问题(Java实现)

变领域搜索算法求解tsp问题：48个城市...初始解为：[0, 33, 40, 8, 7, 29, 6, 46, 36, 38, 12, 43, 24, 21, 1, 25, 5, 10, 34, 42, 11, 45, 15, 23, 19, 18, 28, 16, 27, 39, 20, 31, 13, 30, 14, 37, 2, 4, 47, 3, 17, 26, 41, 32, 9, 44, 22, 35]最佳迭代次数:14最佳邻域：1最短路程为（伪欧氏距离）：10601.12744990602最佳路径为：[12, 10, 11, 14, 39, 8, 0, 7, 37, 30, 43, 17, 6, 27, 5, 36, 18, 26, 16, 42, 29, 35, 45, 32, 19, 46, 20, 31, 38, 47, 4, 41, 23, 9, 44, 34, 3, 25, 1, 28, 33, 40, 15, 21, 2, 22, 13, 24, 12]求解用时：1.028 s-------------------------------------------------------------------------变领域搜索算法求解tsp问题：48个城市...初始解为：[0, 8, 15, 43, 1, 31, 6, 32, 17, 41, 23, 12, 42, 25, 18, 11, 47, 39, 16, 44, 26, 19, 21, 29, 37, 28, 10, 7, 13, 33, 38, 4, 20, 9, 5, 46, 22, 40, 14, 2, 27, 45, 36, 3, 24, 35, 30, 34]最佳迭代次数:17最佳邻域：1最短路程为（欧氏距离）：34672.496967443556最佳路径为：[39, 0, 7, 8, 37, 30, 43, 17, 6, 27, 5, 36, 18, 26, 16, 42, 29, 35, 45, 32, 19, 46, 12, 20, 38, 31, 23, 9, 44, 34, 3, 25, 1, 41, 47, 4, 28, 40, 15, 21, 2, 33, 13, 24, 22, 10, 11, 14, 39]求解用时：0.983 s-------------------------------------------------------------------------

1.7 ALNS自适应大邻域搜索算法

【运筹优化】ALNS自适应大领域搜索算法求解TSP问题(Java实现)

自适应大领域搜索算法求解tsp问题：48个城市...初始解为：[0, 17, 20, 33, 34, 18, 3, 45, 1, 28, 27, 47, 37, 29, 19, 43, 35, 24, 8, 6, 5, 9, 4, 23, 22, 7, 11, 16, 26, 12, 2, 39, 10, 41, 36, 46, 14, 38, 44, 42, 30, 32, 40, 21, 15, 13, 31, 25]最佳迭代次数:79334最短路程为（伪欧氏距离）：11445.721083723423最佳路径为：[3, 34, 44, 23, 9, 41, 47, 38, 31, 12, 13, 24, 20, 46, 19, 11, 10, 22, 39, 14, 32, 45, 35, 29, 16, 42, 26, 18, 36, 5, 27, 6, 17, 43, 30, 37, 7, 8, 0, 2, 21, 15, 40, 33, 4, 28, 1, 25, 3]求解用时：0.352 s-------------------------------------------------------------------------自适应大领域搜索算法求解tsp问题：48个城市...初始解为：[0, 23, 7, 4, 13, 14, 45, 29, 1, 35, 22, 46, 34, 47, 40, 39, 2, 6, 41, 3, 19, 18, 8, 31, 20, 17, 21, 32, 16, 24, 10, 9, 44, 15, 26, 27, 28, 36, 11, 12, 30, 37, 42, 43, 38, 25, 5, 33]最佳迭代次数:76250最短路程为（欧氏距离）：35852.28551388712最佳路径为：[4, 47, 24, 13, 12, 22, 10, 11, 14, 39, 21, 15, 40, 28, 1, 41, 25, 3, 34, 44, 9, 23, 31, 38, 20, 46, 19, 32, 45, 35, 29, 42, 16, 26, 18, 36, 5, 27, 6, 17, 43, 30, 37, 8, 7, 0, 2, 33, 4]求解用时：0.336 s-------------------------------------------------------------------------

二、算法运行示例

public class Run {// 分割线public static String line = "-------------------------------------------------------------------------";public static void main(String[] args) throws Exception {List<double[]> locationList = getLocationList();// 模拟退火算法saTest(new ArrayList<>(locationList));// 数组型禁忌搜索tsArrayTest(new ArrayList<>(locationList));// 树型禁忌搜索tsTreeTest(new ArrayList<>(locationList));// 蚁群算法acoTest(new ArrayList<>(locationList));// 遗传算法gaTest(new ArrayList<>(locationList));// 局部迭代搜索算法ilsTest(new ArrayList<>(locationList));// 变领域搜索算法vnsTest(new ArrayList<>(locationList));// 自适应大领域搜索算法alnsTest(new ArrayList<>(locationList));}// 树型禁忌搜索测试public static void tsTreeTest(List<double[]> locationList) throws Exception {long startTime = System.currentTimeMillis();System.out.println("树型禁忌搜索求解tsp问题："+locationList.size()+"个城市...");new TreeTS_TSP(locationList).solve();System.out.println("求解用时："+(System.currentTimeMillis()-startTime)/1000d+" s");System.out.println(line);}// 数组型禁忌搜索测试public static void tsArrayTest(List<double[]> locationList) throws Exception {long startTime = System.currentTimeMillis();System.out.println("数组型禁忌搜索求解tsp问题："+locationList.size()+"个城市...");new ArrayTS_TSP(locationList).solve();System.out.println("求解用时："+(System.currentTimeMillis()-startTime)/1000d+" s");System.out.println(line);}// 蚁群算法测试public static void acoTest(List<double[]> locationList) throws Exception {long startTime = System.currentTimeMillis();System.out.println("蚁群算法求解tsp问题："+locationList.size()+"个城市...");new AntColonyOptimization_TSP(locationList).solve();System.out.println("求解用时："+(System.currentTimeMillis()-startTime)/1000d+" s");System.out.println(line);}// 遗传算法测试public static void gaTest(List<double[]> locationList) throws Exception{long startTime = System.currentTimeMillis();System.out.println("遗传算法求解tsp问题："+locationList.size()+"个城市...");new GeneticAlgorithm_TSP(locationList).solve();System.out.println("求解用时："+(System.currentTimeMillis()-startTime)/1000d+" s");System.out.println(line);}// 自适应大领域搜索算法测试public static void alnsTest(List<double[]> locationList) throws Exception{long startTime = System.currentTimeMillis();System.out.println("自适应大领域搜索算法求解tsp问题："+locationList.size()+"个城市...");new ALNS_TSP(locationList).solve();System.out.println("求解用时："+(System.currentTimeMillis()-startTime)/1000d+" s");System.out.println(line);}// 模拟退火算法public static void saTest(List<double[]> locationList) throws Exception{long startTime = System.currentTimeMillis();System.out.println("模拟退火算法求解tsp问题："+locationList.size()+"个城市...");new SA_TSP(locationList).solve();System.out.println("求解用时："+(System.currentTimeMillis()-startTime)/1000d+" s");System.out.println(line);}// 局部迭代搜索算法public static void ilsTest(List<double[]> locationList) throws Exception{long startTime = System.currentTimeMillis();System.out.println("局部迭代搜索算法求解tsp问题："+locationList.size()+"个城市...");new ILS_TSP(locationList).solve();System.out.println("求解用时："+(System.currentTimeMillis()-startTime)/1000d+" s");System.out.println(line);}// 变领域搜索算法public static void vnsTest(List<double[]> locationList) throws Exception{long startTime = System.currentTimeMillis();System.out.println("变领域搜索算法求解tsp问题："+locationList.size()+"个城市...");new VNS_TSP(locationList).solve();System.out.println("求解用时："+(System.currentTimeMillis()-startTime)/1000d+" s");System.out.println(line);}private static List<double[]> getLocationList() throws IOException {FileInputStream fis = new FileInputStream("src/main/java/Algorithm/TSP/data/att48.txt");List<double[]> locationList = new ArrayList<>();int len = 0;StringBuilder sb = new StringBuilder();while ((len=fis.read())!=-1){sb.append((char)len);}fis.close();String[] split = sb.toString().split("\n");for (String s : split) {String[] s1 = s.split(" ");double[] doubles = new double[]{Double.parseDouble(s1[1]),Double.parseDouble(s1[2])};locationList.add(doubles.clone());}return locationList;}}

三、测试用例说明

以上使用的是tsplib上的数据att48，这是一个对称TSP问题，城市规模为48，其最优值为10628（取整的伪欧氏距离）。tsplib地址：http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/

四、TSP路径可视化

【运筹优化】JavaFx实现自适应屏幕的TSP路径可视化