From f3c59a17062fb0a89b5f89b7845341386952a6b1 Mon Sep 17 00:00:00 2001
From: rk <94314517@qq.com>
Date: 星期三, 24 九月 2025 16:01:06 +0800
Subject: [PATCH] Merge remote-tracking branch 'origin/master'
---
server/system_service/src/main/java/com/doumee/core/utils/TspSolver.java | 158 ++++++++++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 158 insertions(+), 0 deletions(-)
diff --git a/server/system_service/src/main/java/com/doumee/core/utils/TspSolver.java b/server/system_service/src/main/java/com/doumee/core/utils/TspSolver.java
new file mode 100644
index 0000000..06e17e2
--- /dev/null
+++ b/server/system_service/src/main/java/com/doumee/core/utils/TspSolver.java
@@ -0,0 +1,158 @@
+package com.doumee.core.utils;
+
+import com.google.ortools.Loader;
+import com.google.ortools.constraintsolver.*;
+import lombok.extern.slf4j.Slf4j;
+
+@Slf4j
+public class TspSolver {
+ public static void main(String[] args) throws Exception {
+ // 鍒濆鍖栨暟鎹ā鍨�
+ Loader.loadNativeLibraries();
+ DataModel data = new DataModel();
+ data.initDataList();//鏋勯�犳暟鎹�
+
+ long start =System.currentTimeMillis();
+ System.out.println("=============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();
+ System.out.println("=============end=========="+end);
+
+ System.out.println("=============鑰楁椂=========="+(end -start)+"锛坢s锛�"+(end -start)/1000 +"s"+(end -start)/60/1000 +"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 = "";
+ while (!routing.isEnd(index)) {
+ route += manager.indexToNode(index) + " -> ";
+ routeDemand += data.demands[manager.indexToNode(index)];
+ 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");
+ }
+
+ static class DataModel {
+ //璺濈鐭╅樀
+ public int lenght;
+ //鏈�澶ц溅杈嗛檺鍒�
+ public int vehicleNumber;
+ //璧风偣
+ public static final int depot = 0;
+
+ //姣忎竴涓偣鐨勫晢鍝佺殑鏁伴噺
+ public long[] demands;
+ //杞﹁締鏈�澶у杞�
+ public long[] vehicleCapacities ;
+ public long[][] distanceMatrix ;
+ public void initDataList(){
+ lenght = 500;
+ vehicleNumber = 8;
+ demands = new long[lenght];
+ vehicleCapacities =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;
+ total0+=tem;
+ System.out.print(tem+" ,");
+ }
+ System.out.println( "\ntotal Capacity:"+total0+"=====================");
+ long total = 0;
+ for (int i = 0; i <lenght ; i++) {
+ long tem = (int)(Math.random()*100+100);
+ demands[i] =tem;
+ 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];
+ }
+ }
+ }
+
+ System.out.println( "\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