优化

MrShi

2026-01-13 3a154bdb0a5aaa2c0ac3eac95a6ba747068bd454

 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);
        //创建求解器manager对象，初始化求解器数据
        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)+"（ms）"+(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);
        //创建求解器manager对象，初始化求解器数据
        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)+"（ms）"+(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},
        };*/

    }

}