1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
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);
| //创建求解器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");
| }
|
| 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},
| };*/
|
| }
|
| }
|
|
