From 3a154bdb0a5aaa2c0ac3eac95a6ba747068bd454 Mon Sep 17 00:00:00 2001
From: MrShi <1878285526@qq.com>
Date: 星期二, 13 一月 2026 10:00:37 +0800
Subject: [PATCH] 优化
---
server/visits/dmvisit_service/src/main/java/com/doumee/core/tsp/TspSolver.java | 300 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 300 insertions(+), 0 deletions(-)
diff --git a/server/visits/dmvisit_service/src/main/java/com/doumee/core/tsp/TspSolver.java b/server/visits/dmvisit_service/src/main/java/com/doumee/core/tsp/TspSolver.java
new file mode 100644
index 0000000..9e3c01d
--- /dev/null
+++ b/server/visits/dmvisit_service/src/main/java/com/doumee/core/tsp/TspSolver.java
@@ -0,0 +1,300 @@
+package com.doumee.core.tsp;
+
+import com.doumee.core.constants.ResponseStatus;
+import com.doumee.core.exception.BusinessException;
+import com.google.ortools.Loader;
+import com.google.ortools.constraintsolver.*;
+import com.google.protobuf.Duration;
+import com.google.protobuf.DurationOrBuilder;
+import lombok.extern.slf4j.Slf4j;
+import com.google.ortools.constraintsolver.mainJNI;
+
+import java.util.ArrayList;
+import java.util.List;
+
+@Slf4j
+public class TspSolver {
+ public static void main(String[] args) throws Exception {
+ DataModel data = new DataModel();
+ data.initDataList();//鏋勯�犳暟鎹�
+
+ startSearch(data);
+ /*// 鍒濆鍖栨暟鎹ā鍨�
+ Loader.loadNativeLibraries();
+ DataModel data = new DataModel();
+ data.initDataList();//鏋勯�犳暟鎹�
+
+ long start =System.currentTimeMillis();
+ log.error("=============start=========="+start);
+ //鍒涘缓姹傝В鍣╩anager瀵硅薄锛屽垵濮嬪寲姹傝В鍣ㄦ暟鎹�
+ RoutingIndexManager manager = new RoutingIndexManager(data.distanceMatrix.length, data.vehicleNumber, data.depot);
+
+ // 鍒濆鍖栨眰瑙ｅ櫒
+ RoutingModel routing = new RoutingModel(manager);
+
+// // 娉ㄥ唽鍥炶皟鍑芥暟
+ final int transitCallbackIndex =
+ routing.registerTransitCallback((long fromIndex, long toIndex) -> {
+ int fromNode = manager.indexToNode(fromIndex);
+ int toNode = manager.indexToNode(toIndex);
+ return data.distanceMatrix[fromNode][toNode];
+ });
+
+ // 瀹氫箟鍥炶皟鍑芥暟鑷虫瘡鏉¤矾绾�
+ routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
+ // 澧炲姞璺濈缁村害绾︽潫
+ routing.addDimension(transitCallbackIndex, 0, 30000,
+ true,
+ "Distance");
+ RoutingDimension distanceDimension = routing.getMutableDimension("Distance");
+ distanceDimension.setGlobalSpanCostCoefficient(100);
+// // 娣诲姞瀹归噺闄愬埗
+ final int demandCallbackIndex = routing.registerUnaryTransitCallback((long fromIndex) -> {
+ int fromNode = manager.indexToNode(fromIndex);
+ return data.demands[fromNode];
+ });
+ routing.addDimensionWithVehicleCapacity(demandCallbackIndex, 0, data.vehicleCapacities, true, "Capacity");
+
+ Solver solver = routing.solver();
+
+
+ //璁剧疆鎼滅储鏂规硶
+ RoutingSearchParameters searchParameters =
+ main.defaultRoutingSearchParameters()
+ .toBuilder()
+ .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
+ .build();
+
+ // 鎵ц绠楁硶
+ Assignment solution = routing.solveWithParameters(searchParameters);
+
+ // 鎵撳嵃璺嚎
+ printSolution(data, routing, manager, solution);
+ long end =System.currentTimeMillis();
+ log.error("=============end=========="+end);
+
+ log.error("=============鑰楁椂=========="+(end -start)+"锛坢s锛�"+(end -start)/1000 +"s"+(end -start)/60/1000 +"m");
+ */}
+ public static void startSearch(DataModel data) {
+ // 鍒濆鍖栨暟鎹ā鍨�
+ Loader.loadNativeLibraries();
+ long start =System.currentTimeMillis();
+ log.error("寮�濮嬭鍒�=============start=========="+start);
+ //鍒涘缓姹傝В鍣╩anager瀵硅薄锛屽垵濮嬪寲姹傝В鍣ㄦ暟鎹�
+ RoutingIndexManager manager = new RoutingIndexManager(data.distanceMatrix.length, data.vehicleNumber, data.depot);
+
+ // 鍒濆鍖栨眰瑙ｅ櫒
+ RoutingModel routing = new RoutingModel(manager);
+
+ // 娉ㄥ唽鍥炶皟鍑芥暟
+ final int transitCallbackIndex =
+ routing.registerTransitCallback((long fromIndex, long toIndex) -> {
+ int fromNode = manager.indexToNode(fromIndex);
+ int toNode = manager.indexToNode(toIndex);
+ return data.distanceMatrix[fromNode][toNode];
+ });
+
+ // 瀹氫箟鍥炶皟鍑芥暟鑷虫瘡鏉¤矾绾�
+ routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
+ /* routing.addDimension(transitCallbackIndex, 0, 30000000,
+ true,
+ "Distance");
+ RoutingDimension distanceDimension = routing.getMutableDimension("Distance");
+ distanceDimension.setGlobalSpanCostCoefficient(100); */
+ // 娉ㄥ唽鍥炶皟鍑芥暟
+ final int transitCallbackIndex1 =
+ routing.registerTransitCallback((long fromIndex, long toIndex) -> {
+ int fromNode = manager.indexToNode(fromIndex);
+ return data.customerDemands[fromNode];
+ });
+ for (int d = 0; d < data.vehicleMaxNodes.length; d++) {
+ // 澧炲姞璺濈缁村害绾︽潫
+ routing.addDimension(transitCallbackIndex1, 0, data.vehicleMaxNodes[d],
+ true,
+ "customer_"+d);
+ RoutingDimension distanceDimension1 = routing.getMutableDimension("customer_"+d);
+ distanceDimension1.setGlobalSpanCostCoefficient(100);
+ }
+ // 娣诲姞瀹归噺闄愬埗
+ final int demandCallbackIndex = routing.registerUnaryTransitCallback((long fromIndex) -> {
+ int fromNode = manager.indexToNode(fromIndex);
+ return data.demands[fromNode];
+ });
+ routing.addDimensionWithVehicleCapacity(demandCallbackIndex, 0, data.vehicleCapacities, true, "Capacity");
+
+ Solver solver = routing.solver();
+ //璁剧疆鎼滅储鏂规硶(
+ RoutingSearchParameters searchParameters =
+ main.defaultRoutingSearchParameters()
+ .toBuilder()
+ .setTimeLimit(Duration.newBuilder().setSeconds(60*60*6).build())//鏈�涔�1灏忔椂
+ .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
+ .build();
+
+ // 鎵ц绠楁硶
+ Assignment solution = routing.solveWithParameters(searchParameters);
+ if(solution ==null){
+ log.error("瑙勫垝缁撴潫=============鏈壘鍒版渶浼樿矾绾匡紒" );
+ throw new BusinessException(ResponseStatus.BAD_REQUEST.getCode(),"鏈壘鍒版渶浼樿矾绾匡紒");
+ }
+ // 鎵撳嵃璺嚎
+ resultSolution(data, routing, manager, solution);
+ long end =System.currentTimeMillis();
+ log.error("瑙勫垝缁撴潫=============鑰楁椂=========="+(end -start)+"锛坢s锛�"+(end -start)/1000 +"s"+(end -start)/60/1000 +"m");
+ }
+ static void resultSolution( DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
+ long maxRouteDistance = 0;
+ List<TspSolverSolutions> mapList = new ArrayList<>();
+ for (int i = 0; i < data.vehicleNumber; ++i) {
+ TspSolverSolutions t = new TspSolverSolutions();
+ t.setLineIndex(i);
+ long index = routing.start(i);
+ log.info("Route for Vehicle " + i + ":");
+ long routeDistance = 0;
+ int routeDemand = 0;
+ String route = "";
+ List<Integer> routeList = new ArrayList<>();
+ while (!routing.isEnd(index)) {
+ int tNode = manager.indexToNode(index);
+ routeList.add( tNode);
+ route += tNode+ " -> ";
+ routeDemand += data.demands[tNode];
+ long previousIndex = index;
+ index = solution.value(routing.nextVar(index));
+ routeDistance += routing.getArcCostForVehicle(previousIndex, index, i);
+ }
+ int tNode = manager.indexToNode(index);
+ routeList.add( tNode);
+ log.info(route + tNode);
+ t.setRouteIndex(routeList);
+ t.setDistance(routeDistance);
+ log.info("Distance of the route: " + routeDistance + "m"+" Capacity of the route:"+routeDemand+"/"+data.vehicleCapacities[i]);
+ maxRouteDistance = Math.max(routeDistance, maxRouteDistance);
+ mapList.add(t);
+ }
+ data.setSolutions(mapList);
+ log.info("Maximum of the route distances: " + maxRouteDistance + "m");
+ }
+ static void printSolution( DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
+ long maxRouteDistance = 0;
+ for (int i = 0; i < data.vehicleNumber; ++i) {
+ long index = routing.start(i);
+ log.info("Route for Vehicle " + i + ":");
+ long routeDistance = 0;
+ int routeDemand = 0;
+ String route = "";
+ List<Integer> routeList = new ArrayList<>();
+ while (!routing.isEnd(index)) {
+ int tNode = manager.indexToNode(index);
+ routeList.add( tNode);
+ route += tNode+ " -> ";
+ routeDemand += data.demands[tNode];
+ long previousIndex = index;
+ index = solution.value(routing.nextVar(index));
+ routeDistance += routing.getArcCostForVehicle(previousIndex, index, i);
+ }
+ log.info(route + manager.indexToNode(index));
+ log.info("Distance of the route: " + routeDistance + "m"+" Capacity of the route:"+routeDemand+"/"+data.vehicleCapacities[i]);
+ maxRouteDistance = Math.max(routeDistance, maxRouteDistance);
+ }
+ log.info("Maximum of the route distances: " + maxRouteDistance + "m");
+ }
+
+ public static void startOptimize(){
+
+
+ }
+
+ public static class DataModel {
+ //璺濈鐭╅樀
+ public int lenght;
+ //鏈�澶ц溅杈嗛檺鍒�
+ public int vehicleNumber;
+ public List<TspSolverSolutions> solutions;
+ //璧风偣
+ public static final int depot = 0;
+
+ //姣忎竴涓偣鐨勫晢鍝佺殑鏁伴噺
+ public long[] demands;
+ public long[] customerDemands;
+ //杞﹁締鏈�澶у杞�
+ public long[] vehicleCapacities ;
+ public long[] vehicleMaxNodes ;
+ public long[][] distanceMatrix ;
+
+ public List<TspSolverSolutions> getSolutions() {
+ return solutions;
+ }
+
+ public void setSolutions(List<TspSolverSolutions> solutions) {
+ this.solutions = solutions;
+ }
+
+ public void initDataInfo(int vehicleNumber1, long[] demands1,long[] demands2, long[] vehicleCapacities1, long[][] distanceMatrix1,long[] vehicleMaxNodes){
+ this.demands = demands1;
+ this.customerDemands = demands2;
+ this.vehicleNumber = vehicleNumber1;
+ this.vehicleCapacities=vehicleCapacities1;
+ this.distanceMatrix=distanceMatrix1;
+ this.vehicleMaxNodes =vehicleMaxNodes;
+ }
+ public void initDataList(){
+ lenght = 10;
+ vehicleNumber = 5;
+ demands = new long[lenght];
+ customerDemands = new long[lenght];
+ vehicleCapacities =new long[vehicleNumber];
+ vehicleMaxNodes =new long[vehicleNumber];
+ distanceMatrix = new long[lenght][lenght];
+ int total0 =0;
+ for (int i = 0; i <vehicleNumber ; i++) {
+ long tem = (long) (Math.random() * 1000 + 20000);
+ vehicleCapacities[i] = tem;
+ vehicleMaxNodes[i] =50;
+ total0+=tem;
+ System.out.print(tem+" ,");
+ }
+ log.error( "\ntotal Capacity:"+total0+"=====================");
+ long total = 0;
+ for (int i = 0; i <lenght ; i++) {
+ long tem = (int)(Math.random()*100+100);
+ demands[i] =tem;
+ customerDemands[i] =1;
+ total+=tem;
+ System.out.print(tem+" ,");
+ for (int j = 0; j <lenght ; j++) {
+ if(i == j){
+ distanceMatrix[i][j] =0;
+ }
+ if(i<j){
+ distanceMatrix[i][j] =(int)(Math.random()*1000+1);
+ distanceMatrix[j][i] = distanceMatrix[i][j];
+ }
+ }
+ }
+
+ log.error( "\ntotal Demands:"+total+"=====================");
+ }
+ /* public final long[][] distanceMatrix = {
+ {0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662},
+ {548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210},
+ {776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754},
+ {696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358},
+ {582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244},
+ {274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708},
+ {502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480},
+ {194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856},
+ {308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514},
+ {194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468},
+ {536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354},
+ {502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844},
+ {388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730},
+ {354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536},
+ {468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194},
+ {776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798},
+ {662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0},
+ };*/
+
+ }
+
+}
\ No newline at end of file
--
Gitblit v1.9.3