java 路径规划_基于C-W节约算法的车辆路径规划问题的Java实现

1 packagevrp;2

3 importjava.io.BufferedReader;4 importjava.io.File;5 importjava.io.FileNotFoundException;6 importjava.io.FileReader;7 importjava.io.IOException;8 importjava.util.ArrayList;9 importjava.util.Arrays;10 importjava.util.Collections;11 importjava.util.Comparator;12 importjava.util.LinkedList;13 importjava.util.List;14

15 /**

16 *@author陈海越17 *@version1.018 *@since新标准版5.019 *20 *

21 * 历史：22 *      建立: 2019/9/2 陈海越23 *

24 */

25 public classVRPTest {26

27 public static final String KONGGE = "\\s+|\r";28 public static final int FACTOR = 1;29 private intvehicleNumber;30 private inttotalPointNumber;31 private LinkedList vehicleCapacityList = new LinkedList<>();32 private LinkedList usedVehicleList = new LinkedList<>();33 private List postOfficeList = new ArrayList<>();34 private List routeList = new ArrayList<>();35 private float[][] distMatrix;36 private List savingList = new ArrayList<>();37

38

39 public static void main(String[] args) throwsException {40 VRPTest vrpTest = newVRPTest();41 vrpTest.readFromFile("C:\\Users\\Administrator\\Documents\\vrp_data\\test3.txt");42 vrpTest.vrp();43 }44

45 /**

46 * 从文件中读取数据47 */

48 public voidreadFromFile(String fileName) {49 File file = newFile(fileName);50 try{51 BufferedReader br = new BufferedReader(newFileReader(52 file));53 constructGeneral(br);54 constructVehicle(br);55 constructNodes(br);56 } catch(FileNotFoundException e) {57 e.printStackTrace();58 } catch(IOException e) {59 e.printStackTrace();60 }61 }62

63 private void constructGeneral(BufferedReader br) throwsIOException {64 String first =br.readLine().trim();65 String[] firstLineArr =first.split(KONGGE);66 vehicleNumber = Integer.parseInt(firstLineArr[0]);67 totalPointNumber = Integer.parseInt(firstLineArr[1]);68 }69

70 private void constructVehicle(BufferedReader br) throwsIOException {71 String vehicleCapacity =br.readLine().trim();72 for(String s : vehicleCapacity.split(KONGGE)) {73 vehicleCapacityList.add(Float.parseFloat(s));74 }75 }76

77 private void constructNodes(BufferedReader br) throwsIOException {78 for (int i = 0; i < totalPointNumber; i++) {79 String postStr =br.readLine().trim();80 String[] postArr =postStr.split(KONGGE);81 PostOffice postOffice =

82 new PostOffice(Integer.parseInt(postArr[0]), postArr[1],83 Float.parseFloat(postArr[2]),84 Float.parseFloat(postArr[3]),85 Float.parseFloat(postArr[4]),86 Float.parseFloat(postArr[5]),87 Integer.parseInt(postArr[6]),88 Integer.parseInt(postArr[7]),89 Integer.parseInt(postArr[8]),90 isDepot(i));91 postOfficeList.add(postOffice);92 }93 }94

95 private int isDepot(inti) {96 //第一条记录为仓库

97 return i == 0 ? 0 : 1;98 }99

100 public void vrp() throwsException {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 voidcalcDistMatrix() {118 int length =postOfficeList.size();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] =postOfficeList.get(i).distanceTo(postOfficeList.get(j));123 distMatrix[j][i] =distMatrix[i][j];124 }125 distMatrix[i][i] = 0;126 }127 }128

129 /**

130 * 计算节约距离列表131 */

132 private voidcalcSavingMatrix() {133 for (int i = 2; i < totalPointNumber; i++) {134 for (int j = 1; j < i; j++) {135 PostOffice pi =postOfficeList.get(i);136 PostOffice pj =postOfficeList.get(j);137 PostOffice depot = postOfficeList.get(0);138 float dist =pi.distanceTo(pj);139 float saving =

140 pi.distanceTo(depot) + pj.distanceTo(depot) -dist;141 savingList.add(newSavedDistance(postOfficeList.get(i), postOfficeList.get(j), saving));142 }143 }144 savingList.sort(Collections.reverseOrder());145 }146

147 private booleantwoOptOptimise() {148 for(Route route : routeList) {149 if(route.twoOptOptimise()) {150 return true;151 }152 }153 return false;154 }155

156 private booleancapacityOptimise() {157 for(Route route : routeList) {158 if(route.vehicleOptimise(vehicleCapacityList, usedVehicleList)) {159 return true;160 }161 }162 return false;163 }164

165

166

167 /**

168 * 构建基础路径169 */

170 private void calcRoute() throwsCloneNotSupportedException {171 //将所有点单独与集散中心组成一条路径，路径对象中包含集散中心

172 PostOffice depot = postOfficeList.get(0);173 for(int i = 1 ; i

176 PostOffice startNode =(PostOffice) depot.clone();177 startNode.setCurrentRoute(r);178 PostOffice endNode =(PostOffice) depot.clone();179 endNode.setCurrentRoute(r);180 postOfficeList.get(i).setCurrentRoute(r);181 //更新路径上的点

182 r.setNodesAndUpdateLoad(new LinkedList<>(Arrays.asList(startNode, postOfficeList.get(i), endNode)));183

184 //更新到达时间

185 r.updateArrivedTime();186 //更新路径长度

187 r.setLength(r.calcLength(r.getNodes()));188 //更新原路径上点的前后关系

189 r.updateNodeTracing();190 //更新载重

191 routeList.add(r);192 }193 }194

195 /**

196 * CW节约算法构建路程197 *@throwsException198 */

199 private void cwSaving() throwsException {200 //取出save值最大的路径，尝试加入当前路径

201 for(SavedDistance savedDistance : savingList) {202 mergeSavedDistance(savedDistance);203 }204 }205

206 /**

207 * 合并路径规则：208 * 两点中有一点在路径尾部，一点在路径头部，并且路径总容积满足车辆容积限制209 * 先单独判断是为了防止已经分配了车辆的路径没有充分负载210 *@paramsavedDistance211 */

212 private void mergeSavedDistance(SavedDistance savedDistance) throwsException {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 (r1.equals(r2)) return;219

220 if (r1.getCapacity() != 0) {221 //如果r1已分配车辆，计算容积限制

222 tryMergeToRoute(savedDistance, r1, r2, p1, p2);223 return;224 }225

226 if (r2.getCapacity() != 0) {227 //如果r2已分配车辆，计算容积限制

228 tryMergeToRoute(savedDistance, r2, r1, p2, p1);229 return;230 }231

232 //如果都没有分配过车辆, 给r1分配目前容积最大的车辆

233 if (r1.getCapacity() == 0) {234 if (vehicleCapacityList.isEmpty()) throw new Exception("汽车已经分配完了");235 //设置车辆总容积

236 Float capacity =vehicleCapacityList.pop();237 usedVehicleList.add(capacity);238 r1.setCapacity(capacity *FACTOR);239

240 tryMergeToRoute(savedDistance, r1, r2, p1, p2);241 return;242 }243

244 //超过r1容积限制，尝试r2。如果没有分配过车辆, 给r2分配目前容积最大的车辆

245 if (r2.getCapacity() == 0) {246 if (vehicleCapacityList.isEmpty()) throw new Exception("汽车已经分配完了");247 //设置车辆总容积

248 Float capacity =vehicleCapacityList.pop();249 usedVehicleList.add(capacity);250 r2.setCapacity(capacity *FACTOR);251

252 tryMergeToRoute(savedDistance, r2, r1, p2, p1);253 }254 }255

256 private voidtryMergeToRoute(SavedDistance savedDistance,257 Route existRoute,258 Route mergedRoute,259 PostOffice existNode,260 PostOffice mergedNode) throwsException {261 if(appendMergedRoute(existRoute, mergedRoute, existNode,262 mergedNode)) {263 if (capacityFeasible(existRoute, mergedRoute, false)) {264 //合并到现有路径之后

265 if(mergedRoute.hardTimeWindowFeasible(existNode)) {266 mergeRoute(existRoute, mergedRoute, savedDistance267 , existNode, false);268 }269 }270 } else if(insertMergedRoute(existRoute, mergedRoute,271 existNode, mergedNode)) {272 if (capacityFeasible(existRoute, mergedRoute, true)) {273 //合并到现有路径之前

274 if(existRoute.hardTimeWindowFeasible(mergedNode)) {275 mergeRoute(existRoute, mergedRoute, savedDistance276 , existNode, true);277 }278 }279 }280 }281

282 private booleaninsertMergedRoute(Route existRoute,283 Route mergedRoute,284 PostOffice existNode,285 PostOffice mergedNode) throwsException {286 if (mergedRoute.getNodes().size() < 3 || existRoute.getNodes().size() < 3)287 throw new Exception("合并路径节点少于3个");288 return existRoute.getNodes().indexOf(existNode) == 1 && mergedRoute.getNodes().indexOf(mergedNode) == mergedRoute.getNodes().size() - 2;289 }290

291 private booleanappendMergedRoute(Route existRoute,292 Route mergedRoute,293 PostOffice existNode,294 PostOffice mergedNode) throwsException {295 if (mergedRoute.getNodes().size() < 3 || existRoute.getNodes().size() < 3)296 throw new Exception("合并路径节点少于3个");297 return existRoute.getNodes().indexOf(existNode) == existRoute.getNodes().size() - 2 && mergedRoute.getNodes().indexOf(mergedNode) == 1;298 }299

300 private booleancapacityFeasible(Route existRoute,301 Route mergedRoute,302 boolean isInsert) throwsException {303 if (existRoute.getCapacity() > (mergedRoute.getTotalReceive() +existRoute.getTotalReceive()) ) {304 if(isInsert) {305 Float curLoad = mergedRoute.getTotalSendOut() +existRoute.getTotalReceive();306 for(PostOffice node : existRoute.getNodes()) {307 if (curLoad - node.getReceive() + node.getSendOut() >existRoute.getCapacity()) {308 return false;309 }310 curLoad = curLoad - node.getReceive() +node.getSendOut();311 if (curLoad < 0)312 throw new Exception("isInsert=true, 当前载重出错，小于0");313 }314 } else{315 Float curLoad = existRoute.getTotalSendOut() +mergedRoute.getTotalReceive();316 for(PostOffice node : mergedRoute.getNodes()) {317 if (curLoad - node.getReceive() + node.getSendOut() >existRoute.getCapacity()) {318 return false;319 }320 curLoad = curLoad - node.getReceive() +node.getSendOut();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 *@paramexistRoute334 *@parammergedRoute335 *@paramsavedDistance336 *@paramp337 *@parambeforeP338 *@throwsException339 */

340 private voidmergeRoute(Route existRoute, Route mergedRoute,341 SavedDistance savedDistance, PostOffice p342 , Boolean beforeP) throwsException {343 //合并点在p1之前

344 LinkedList mergedNodes =mergedRoute.getNodes();345 mergedNodes.removeFirst();346 mergedNodes.removeLast();347

348 //从合并处插入被合并路径中所有营业点

349 existRoute.getNodes().addAll(existRoute.getNodes().indexOf(p) + (beforeP ? 0 : 1), mergedRoute.getNodes());350 //更新原有路径上所有营业点所在路径

351 mergedNodes.forEach(node ->{352 node.setCurrentRoute(existRoute);353 });354 //更新原路径上点的前后关系

355 existRoute.updateNodeTracing();356 //更新到达时间

357 existRoute.updateArrivedTime();358 //更新载重

359 existRoute.addReceive(mergedRoute.getTotalReceive());360 existRoute.addSendOut(mergedRoute.getTotalSendOut());361 //更新路径长度

362 existRoute.setLength(existRoute.calcLength(existRoute.getNodes()));363 //清除被合并路径

364 if (mergedRoute.getCapacity() !=0f) {365 vehicleCapacityList.push(mergedRoute.getCapacity() /FACTOR);366 vehicleCapacityList.sort(Comparator.reverseOrder());367 usedVehicleList.remove(mergedRoute.getCapacity() /FACTOR);368 }369 routeList.remove(mergedRoute);370 }371

372

373

374 private voidprintGeneral() {375 System.out.println("车辆总数: " +vehicleNumber);376 System.out.println("邮局总数: " +totalPointNumber);377 System.out.println("使用车辆: " +usedVehicleList);378 System.out.println("剩余车辆: " +vehicleCapacityList);379 //System.out.println("邮局位置: " + postOfficeList);380 //if (savingList.size() >= 5) {381 //System.out.println("\n节约距离 top 5: " + savingList.subList(0, 5).toString());382 //}

383 }384

385 private voidprintRoute() {386 System.out.println("\n路径: ");387 for (int i = 0; i < routeList.size(); i++) {388 Route r =routeList.get(i);389 System.out.println(i + " " +r.toString());390 }391 }392

393 private voidprintTimeSchedule() {394 System.out.println("\n到达时间 ");395 for (int i = 0; i < routeList.size(); i++) {396 Route r =routeList.get(i);397 System.out.println(i + " " +r.timeSchedule());398 }399 }400

401

402 public intgetTotalPointNumber() {403 returntotalPointNumber;404 }405

406

407 public LinkedListgetUsedVehicleList() {408 returnusedVehicleList;409 }410

411 public ListgetPostOfficeList() {412 returnpostOfficeList;413 }414

415 public ListgetRouteList() {416 returnrouteList;417 }418

419 }