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 lombok.extern.slf4j.Slf4j;
|
import com.google.protobuf.Internal.IntListAdapter.IntConverter;
|
|
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();
|
System.out.println("=============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();
|
System.out.println("=============end=========="+end);
|
|
System.out.println("=============耗时=========="+(end -start)+"（ms）"+(end -start)/1000 +"s"+(end -start)/60/1000 +"m");
|
*/}
|
public static void startSearch(DataModel data) {
|
// 初始化数据模型
|
Loader.loadNativeLibraries();
|
long start =System.currentTimeMillis();
|
System.out.println("=============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, 300000000,
|
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");
|
// routing.addDimensionWithVehicleTransits()
|
Solver solver = routing.solver();
|
|
//设置搜索方法
|
RoutingSearchParameters searchParameters =
|
main.defaultRoutingSearchParameters()
|
.toBuilder()
|
.setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
|
.build();
|
|
// 执行算法
|
Assignment solution = routing.solveWithParameters(searchParameters);
|
if(solution ==null){
|
throw new BusinessException(ResponseStatus.BAD_REQUEST.getCode(),"未找到最优路线！");
|
}
|
// 打印路线
|
resultSolution(data, routing, manager, solution);
|
long end =System.currentTimeMillis();
|
System.out.println("=============end=========="+end);
|
System.out.println("=============耗时=========="+(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[] vehicleCapacities ;
|
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[] vehicleCapacities1, long[][] distanceMatrix1){
|
this.demands = demands1;
|
this.vehicleNumber = vehicleNumber1;
|
this.vehicleCapacities=vehicleCapacities1;
|
this.distanceMatrix=distanceMatrix1;
|
}
|
public void initDataList(){
|
lenght = 100;
|
vehicleNumber = 7;
|
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},
|
};*/
|
|
}
|
|
}
|
