基于C-W节约算法的车辆路径规划问题的Java实现
1 package vrp;
2
3 import ;
4 import ;
5 import ;
6 import ;
7 import ;
8 import ;
9 import ;
10 import ;
11 import ;
12 import ;
13 import ;
14
15 /**
16 * @author <a herf="chenhy@">陈海越</a>
17 * @version 1.0
18 * @since 新标准版5.0
19 *
20 * <pre>
21 * 历史：
22 * 建立: 2019/9/2 陈海越
23 * </pre>
24 */
25 public class VRPTest {
26
27 public static final String KONGGE = "\\s+|\r";
28 public static final int FACTOR = 1;
29 private int vehicleNumber;
30 private int totalPointNumber;
31 private LinkedList<Float> vehicleCapacityList = new LinkedList<>();
32 private LinkedList<Float> usedVehicleList = new LinkedList<>();
33 private List<PostOffice> postOfficeList = new ArrayList<>();
34 private List<Route> routeList = new ArrayList<>();
35 private float[][] distMatrix;
36 private List<SavedDistance> savingList = new ArrayList<>();
37
38
39 public static void main(String[] args) throws Exception {
40 VRPTest vrpTest = new VRPTest();
41 ("C:\\Users\\Administrator\\Documents\\vrp_data\\");
42 ();
43 }
44
45 /**
46 * 从文件中读取数据
47 */
48 public void readFromFile(String fileName) {
49 File file = new File(fileName);
50 try {
51 BufferedReader br = new BufferedReader(new FileReader(
52 file));
53 constructGeneral(br);
54 constructVehicle(br);
55 constructNodes(br);
56 } catch (FileNotFoundException e) {
57 ();
58 } catch (IOException e) {
59 ();
60 }
61 }
62
63 private void constructGeneral(BufferedReader br) throws IOException {
64 String first = ().trim();
65 String[] firstLineArr = (KONGGE);
66 vehicleNumber = (firstLineArr[0]);
67 totalPointNumber = (firstLineArr[1]);
68 }
69
70 private void constructVehicle(BufferedReader br) throws IOException {
71 String vehicleCapacity = ().trim();
72 for (String s : (KONGGE)) {
73 ((s));
74 }
75 }
76
77 private void constructNodes(BufferedReader br) throws IOException {
78 for (int i = 0; i < totalPointNumber; i++) {
79 String postStr = ().trim();
80 String[] postArr = (KONGGE);
81 PostOffice postOffice =
82 new PostOffice((postArr[0]), postArr[1],
83 (postArr[2]),
84 (postArr[3]),
85 (postArr[4]),
86 (postArr[5]),
87 (postArr[6]),
88 (postArr[7]),
89 (postArr[8]),
90 isDepot(i));
91 (postOffice);
92 }
93 }
94
95 private int isDepot(int i) {
96 //第一条记录为仓库
97 return i == 0 ? 0 : 1;
98 }
99
100 public void vrp() throws Exception {
101 calcDistMatrix();
102 calcSavingMatrix();
103 calcRoute();
104 cwSaving();
105 //optimise
106 twoOptOptimise();
107 capacityOptimise();
108
109 printGeneral();
110 printRoute();
111 // printTimeSchedule();
112 }
113
114 /**
115 * 计算距离矩阵
116 */
117 private void calcDistMatrix() {
118 int length = ();
119 distMatrix = new float[length][length];
120 for (int i = 0; i < totalPointNumber; i++) {
121 for (int j = 0; j < i; j++) {
122 distMatrix[i][j] = (i).distanceTo((j));
123 distMatrix[j][i] = distMatrix[i][j];
124 }
125 distMatrix[i][i] = 0;
126 }
127 }
128
129 /**
130 * 计算节约距离列表
131 */
132 private void calcSavingMatrix() {
133 for (int i = 2; i < totalPointNumber; i++) {
134 for (int j = 1; j < i; j++) {
135 PostOffice pi = (i);
136 PostOffice pj = (j);
137 PostOffice depot = (0);
138 float dist = (pj);
139 float saving =
140 (depot) + (depot) - dist;
141 (new SavedDistance((i), (j), saving));
142 }
143 }
144 (());
145 }
146
147 private boolean twoOptOptimise() {
148 for (Route route : routeList) {
149 if (()) {
150 return true;
151 }
152 }
153 return false;
154 }
155
156 private boolean capacityOptimise() {
157 for (Route route : routeList) {
158 if ((vehicleCapacityList, usedVehicleList)) {
159 return true;
160 }
161 }
162 return false;
163 }
164
165
166
167 /**
168 * 构建基础路径
169 */
170 private void calcRoute() throws CloneNotSupportedException {
171 //将所有点单独与集散中心组成一条路径，路径对象中包含集散中心
172 PostOffice depot = (0);
173 for(int i = 1 ; i<(); i++) {
174 Route r = new Route();
175 //更新点 所在路径
176 PostOffice startNode = (PostOffice) ();
177 (r);
178 PostOffice endNode = (PostOffice) ();
179 (r);
180 (i).setCurrentRoute(r);
181 //更新路径 上的点
182 (new LinkedList<>((startNode, (i), endNode)));
183
184 //更新到达时间
185 ();
186 //更新路径长度
187 ((()));
188 //更新原路径上点的前后关系
189 ();
190 //更新载重
191 (r);
192 }
193 }
194
195 /**
196 * CW节约算法构建路程
197 * @throws Exception
198 */
199 private void cwSaving() throws Exception {
200 //取出save值最大的路径，尝试加入当前路径
201 for (SavedDistance savedDistance : savingList) {
202 mergeSavedDistance(savedDistance);
203 }
204 }
205
206 /**
207 * 合并路径规则：
208 * 两点中有一点在路径尾部，一点在路径头部，并且路径总容积满足车辆容积限制
209 * 先单独判断 是为了防止 已经分配了车辆的路径没有充分负载
210 * @param savedDistance
211 */
212 private void mergeSavedDistance(SavedDistance savedDistance) throws Exception {
213 Route r1 = savedDistance.getP1().getCurrentRoute();
214 Route r2 = savedDistance.getP2().getCurrentRoute();
215 PostOffice p1 = savedDistance.getP1();
216 PostOffice p2 = savedDistance.getP2();
217
218 if ((r2)) return;
219
220 if (() != 0 ) {
221 //如果r1已分配车辆， 计算 容积限制
222 tryMergeToRoute(savedDistance, r1, r2, p1, p2);
223 return;
224 }
225
226 if (() != 0) {
227 //如果r2已分配车辆，计算 容积限制
228 tryMergeToRoute(savedDistance, r2, r1, p2, p1);
229 return;
230 }
231
232 //如果都没有分配过车辆, 给r1分配 目前容积最大的车辆
233 if (() == 0) {
234 if (()) throw new Exception("汽车已经分配完了");
235 //设置车辆总容积
236 Float capacity = ();
237 (capacity);
238 (capacity * FACTOR);
239
240 tryMergeToRoute(savedDistance, r1, r2, p1, p2);
241 return;
242 }
243
244 //超过r1容积限制，尝试r2。如果没有分配过车辆, 给r2分配 目前容积最大的车辆
245 if (() == 0) {
246 if (()) throw new Exception("汽车已经分配完了");
247 //设置车辆总容积
248 Float capacity = ();
249 (capacity);
250 (capacity * FACTOR);
251
252 tryMergeToRoute(savedDistance, r2, r1, p2, p1);
253 }
254 }
255
256 private void tryMergeToRoute(SavedDistance savedDistance,
257 Route existRoute,
258 Route mergedRoute,
259 PostOffice existNode,
260 PostOffice mergedNode) throws Exception {
261 if (appendMergedRoute(existRoute, mergedRoute, existNode,
262 mergedNode)) {
263 if (capacityFeasible(existRoute, mergedRoute, false)) {
264 //合并到现有路径之后
265 if ((existNode)) {
266 mergeRoute(existRoute, mergedRoute, savedDistance
267 , existNode, false);
268 }
269 }
270 } else if (insertMergedRoute(existRoute, mergedRoute,
271 existNode, mergedNode)) {
272 if (capacityFeasible(existRoute, mergedRoute, true)) {
273 //合并到现有路径之前
274 if ((mergedNode)) {
275 mergeRoute(existRoute, mergedRoute, savedDistance
276 , existNode, true);
277 }
278 }
279 }
280 }
281
282 private boolean insertMergedRoute(Route existRoute,
283 Route mergedRoute,
284 PostOffice existNode,
285 PostOffice mergedNode) throws Exception {
286 if (().size() < 3 || ().size() < 3)
287 throw new Exception("合并路径 节点少于3个");
288 return ().indexOf(existNode) == 1 && ().indexOf(mergedNode) == ().size() - 2;
289 }
290
291 private boolean appendMergedRoute(Route existRoute,
292 Route mergedRoute,
293 PostOffice existNode,
294 PostOffice mergedNode) throws Exception {
295 if (().size() < 3 || ().size() < 3)
296 throw new Exception("合并路径 节点少于3个");
297 return ().indexOf(existNode) == ().size() - 2 && ().indexOf(mergedNode) == 1;
298 }
299
300 private boolean capacityFeasible(Route existRoute,
301 Route mergedRoute,
302 boolean isInsert) throws Exception {
303 if (() > (() + ()) ) {
304 if (isInsert) {
305 Float curLoad = () + ();
306 for (PostOffice node : ()) {
307 if (curLoad - () + () > ()) {
308 return false;
309 }
310 curLoad = curLoad - () + ();
311 if (curLoad < 0)
312 throw new Exception("isInsert=true, 当前载重出错，小于0");
313 }
314 } else {
315 Float curLoad = () + ();
316 for (PostOffice node : ()) {
317 if (curLoad - () + () > ()) {
318 return false;
319 }
320 curLoad = curLoad - () + ();
321 if (curLoad < 0)
322 throw new Exception("isInsert=false, 当前载重出错，小于0");
323 }
324 }
325 return true;
326 }
327
328 return false;
329 }
330
331 /**
332 * 合并路径 算法
333 * @param existRoute
334 * @param mergedRoute
335 * @param savedDistance
336 * @param p
337 * @param beforeP
338 * @throws Exception
339 */
340 private void mergeRoute(Route existRoute, Route mergedRoute,
341 SavedDistance savedDistance, PostOffice p
342 , Boolean beforeP) throws Exception {
343 //合并点在p1之前
344 LinkedList<PostOffice> mergedNodes = ();
345 ();
346 ();
347
348 //从合并处 插入 被合并路径中所有营业点
349 ().addAll(().indexOf(p) + (beforeP ? 0 : 1), ());
350 //更新 原有路径上所有营业点 所在路径
351 (node -> {
352 (existRoute);
353 });
354 //更新原路径上点的前后关系
355 ();
356 //更新到达时间
357 ();
358 //更新载重
359 (());
360 (());
361 //更新路径长度
362 ((()));
363 //清除 被合并路径
364 if (() != 0f) {
365 (() / FACTOR);
366 (());
367 (() / FACTOR);
368 }
369 (mergedRoute);
370 }
371
372
373
374 private void printGeneral() {
375 ("车辆总数: " + vehicleNumber);
376 ("邮局总数: " + totalPointNumber);
377 ("使用车辆: " + usedVehicleList);
378 ("剩余车辆: " + vehicleCapacityList);
379 // ("邮局位置: " + postOfficeList);
380 // if (() >= 5) {
381 // ("\n节约距离 top 5: " + (0, 5).toString());
382 // }
383 }
384
385 private void printRoute() {
386 ("\n路径: ");
387 for (int i = 0; i < (); i++) {
388 Route r = (i);
389 (i + " " + ());
390 }
391 }
392
393 private void printTimeSchedule() {
394 ("\n到达时间 ");
395 for (int i = 0; i < (); i++) {
396 Route r = (i);
397 (i + " " + ());
398 }
399 }
400
401
402 public int getTotalPointNumber() {
403 return totalPointNumber;
404 }
405
406
407 public LinkedList<Float> getUsedVehicleList() {
408 return usedVehicleList;
409 }
410
411 public List<PostOffice> getPostOfficeList() {
412 return postOfficeList;
413 }
414
415 public List<Route> getRouteList() {
416 return routeList;
417 }
418
419 }