【运筹优化】不同版本 Cplex 求解 TSP 的速度对比 + Java 代码实现

一、前言

本文测试了Cplex的不同版本：12.6.3、12.8.0、12.9.0、12.10、20.10、22.10 在 TSP 问题上的求解性能

测试环境：Win11 + CPU i9-12900H + 内存32G + Java8

二、完整代码

2.1 算法部分

求解 TSP 的模型采用 MTZ 消除子回路，建立混合整数规划模型如下（Java 代码）：

public class IP_TSP {// 城市坐标<[x,y]>List<double[]> locationList;// 距离矩阵double[][] distance;// 城市数量int cityNum;// 开始地点索引int startIndex;public IP_TSP(List<double[]> locationList) {this.locationList = locationList;}public void solve() {initVar();solver();}private void solver() {try {IloCplex cplex = new IloCplex();//决策变量IloIntVar[][] intVars = new IloIntVar[cityNum][cityNum];for (int i = 0; i < cityNum; i++) {for (int j = 0; j < cityNum; j++) {if (i != j) {intVars[i][j] = cplex.intVar(0, 1);}}}//目标函数IloLinearNumExpr target = cplex.linearNumExpr();for (int i = 0; i < cityNum; i++) {for (int j = 0; j < cityNum; j++) {if (i != j) {target.addTerm(distance[i][j], intVars[i][j]);}}}//求目标函数的最小值cplex.addMinimize(target);//约束//约束1：每行每列之和等于1for (int i = 0; i < cityNum; i++) {IloLinearNumExpr expr_row = cplex.linearNumExpr();IloLinearNumExpr expr_col = cplex.linearNumExpr();for (int j = 0; j < cityNum; j++) {if (i != j) {expr_row.addTerm(1, intVars[i][j]);expr_col.addTerm(1, intVars[j][i]);}}cplex.addEq(expr_row, 1);cplex.addEq(expr_col, 1);}//约束2：消除子回路IloNumVar[] u = cplex.numVarArray(cityNum, 0, Double.MAX_VALUE);for (int i = 1; i < cityNum; i++) {for (int j = 1; j < cityNum; j++) {if (j != i) {IloLinearNumExpr expr = cplex.linearNumExpr();expr.addTerm(1.0, u[i]);expr.addTerm(-1.0, u[j]);expr.addTerm(cityNum - 1, intVars[i][j]);cplex.addLe(expr, cityNum - 2);}}}//取消cplex输出cplex.setOut(null);//求解if (cplex.solve()) {List<Integer> bestPath = new ArrayList<>();bestPath.add(startIndex);int index = startIndex;while (true) {for (int i = 0; i < intVars[index].length; i++) {if (index != i && cplex.getValue(intVars[index][i]) > 1e-06) {index = i;bestPath.add(i);break;}}if (index == startIndex) {break;}}System.out.println("最短路径为：" + bestPath);System.out.println("最短路径长度为：" + cplex.getObjValue());} else {System.err.println("此题无解");}} catch (Exception e) {e.printStackTrace();}}// 初始化变量public void initVar() {// 开始地点索引startIndex = 0;// 城市数量为点的数量cityNum = locationList.size();// 距离矩阵distance = new double[cityNum][cityNum];// 初始化距离矩阵for (int i = 0; i < distance.length; i++) {for (int j = i; j < distance[i].length; j++) {if (i == j) {// 对角线为无穷大distance[i][j] = Double.MAX_VALUE;} else {// 计算i到j的距离distance[i][j] = getDistance(locationList.get(i), locationList.get(j));distance[j][i] = distance[i][j];}}}}// 计算两点之间的距离（使用伪欧氏距离，可以减少计算量）public double getDistance(double[] place1, double[] place2) {// 伪欧氏距离在根号内除以了一个10
//        return Math.sqrt((Math.pow(place1[0] - place2[0], 2) + Math.pow(place1[1] - place2[1], 2)) / 10.0);return Math.sqrt((Math.pow(place1[0] - place2[0], 2) + Math.pow(place1[1] - place2[1], 2)));}}

2.2 调用部分

下面代码通过随机的方式，创造了城市数量 30~40 的 11 个 TSP 随机案例

public class Test {public static String line = "-------------------------------------------------------------------------";public static void main(String[] args) {Random random = new Random(666L);for (int cityNum = 30; cityNum <= 40; cityNum++) {solveByMip(cityNum, random);}}public static void solveByMip(int cityNum, Random random) {long startTime = System.currentTimeMillis();List<double[]> locationList = createLocationList(cityNum, random);new IP_TSP(locationList).solve();System.out.println("cityNum: " + cityNum + " , solveTime: " + ((System.currentTimeMillis() - startTime) / 1000d) + " s");System.out.println(line);}public static List<double[]> createLocationList(int cityNum, Random random) {List<double[]> locationList = new ArrayList<>();for (int i = 0; i < cityNum; i++) {locationList.add(new double[]{random.nextDouble() * 10000, random.nextDouble() * 10000});}return locationList;}}

三、运行结果示例

下面的输出是用 Cplex12.6.3 运行出来的，其他版本的运行输出就不展示了，在下一章直接对不同版本的求解速度进行统计

最短路径为：[0, 5, 14, 8, 17, 1, 3, 13, 11, 27, 29, 22, 12, 25, 20, 26, 4, 10, 7, 24, 21, 15, 9, 23, 19, 2, 16, 6, 18, 28, 0]
最短路径长度为：45583.110232714316
cityNum: 30 , solveTime: 0.573 s
-------------------------------------------------------------------------
最短路径为：[0, 12, 17, 27, 23, 21, 11, 14, 30, 19, 3, 29, 18, 13, 15, 26, 28, 1, 5, 16, 8, 20, 4, 10, 22, 9, 7, 2, 24, 6, 25, 0]
最短路径长度为：42724.7438801804
cityNum: 31 , solveTime: 0.18 s
-------------------------------------------------------------------------
最短路径为：[0, 26, 14, 5, 11, 9, 21, 13, 2, 22, 1, 7, 16, 15, 25, 27, 4, 17, 10, 28, 3, 23, 12, 30, 24, 31, 8, 6, 29, 20, 18, 19, 0]
最短路径长度为：46736.35653970036
cityNum: 32 , solveTime: 1.022 s
-------------------------------------------------------------------------
最短路径为：[0, 10, 16, 9, 23, 1, 3, 14, 6, 25, 26, 7, 5, 28, 8, 27, 12, 32, 11, 24, 21, 30, 17, 2, 22, 13, 29, 31, 19, 20, 15, 4, 18, 0]
最短路径长度为：45233.949316241386
cityNum: 33 , solveTime: 4.06 s
-------------------------------------------------------------------------
最短路径为：[0, 28, 5, 14, 13, 18, 26, 11, 16, 8, 33, 25, 20, 19, 27, 7, 24, 17, 21, 22, 12, 2, 15, 10, 31, 9, 29, 6, 23, 3, 4, 1, 30, 32, 0]
最短路径长度为：46999.268123455695
cityNum: 34 , solveTime: 0.787 s
-------------------------------------------------------------------------
最短路径为：[0, 16, 14, 20, 27, 21, 10, 3, 23, 33, 29, 25, 6, 18, 17, 28, 7, 31, 19, 26, 32, 8, 5, 9, 4, 34, 2, 12, 13, 22, 30, 1, 11, 24, 15, 0]
最短路径长度为：51482.36852924586
cityNum: 35 , solveTime: 0.374 s
-------------------------------------------------------------------------
最短路径为：[0, 23, 26, 35, 33, 29, 30, 15, 20, 12, 3, 17, 18, 24, 8, 27, 19, 21, 32, 31, 22, 34, 7, 1, 16, 13, 4, 28, 10, 2, 11, 5, 6, 9, 25, 14, 0]
最短路径长度为：49420.551512260885
cityNum: 36 , solveTime: 0.896 s
-------------------------------------------------------------------------
最短路径为：[0, 12, 1, 7, 10, 33, 32, 20, 21, 8, 29, 2, 6, 18, 36, 9, 28, 35, 31, 15, 27, 30, 22, 25, 34, 5, 23, 26, 14, 13, 19, 24, 3, 4, 16, 17, 11, 0]
最短路径长度为：52096.36583441236
cityNum: 37 , solveTime: 4.602 s
-------------------------------------------------------------------------
最短路径为：[0, 10, 13, 12, 19, 1, 21, 18, 28, 22, 9, 15, 25, 31, 23, 30, 5, 29, 16, 3, 7, 33, 36, 11, 8, 27, 4, 6, 20, 24, 14, 34, 17, 2, 35, 37, 26, 32, 0]
最短路径长度为：48481.89773743604
cityNum: 38 , solveTime: 5.914 s
-------------------------------------------------------------------------
最短路径为：[0, 15, 35, 20, 14, 32, 12, 29, 37, 5, 11, 16, 13, 6, 3, 25, 23, 9, 19, 22, 27, 38, 1, 34, 24, 4, 8, 31, 30, 10, 7, 26, 33, 18, 17, 28, 36, 21, 2, 0]
最短路径长度为：46654.509283092666
cityNum: 39 , solveTime: 0.773 s
-------------------------------------------------------------------------
最短路径为：[0, 24, 35, 4, 14, 16, 28, 39, 17, 30, 22, 37, 21, 8, 34, 13, 12, 19, 5, 20, 31, 9, 18, 25, 29, 27, 10, 33, 7, 3, 23, 6, 1, 2, 36, 38, 32, 15, 26, 11, 0]
最短路径长度为：50592.89805137726
cityNum: 40 , solveTime: 0.773 s
-------------------------------------------------------------------------

四、求解时间统计

表格里的数值是求解时间，单位是秒。

通过记录分析，我们可以发现整体表现最好的版本是 Cplex12.6.3，其不仅平均求解时间最短，且发挥也是最稳定的