总方案计算
private SolutionCostCalculator getObjectiveFunction(final VehicleRoutingProblem vrp, final double maxCosts) { if (objectiveFunction != null) return objectiveFunction; SolutionCostCalculator solutionCostCalculator = new SolutionCostCalculator() { @Override public double getCosts(VehicleRoutingProblemSolution solution) { double costs = 0.; for (VehicleRoute route : solution.getRoutes()) { costs += route.getVehicle().getType().getVehicleCostParams().fix; boolean hasBreak = false; TourActivity prevAct = route.getStart(); for (TourActivity act : route.getActivities()) { if (act instanceof BreakActivity) hasBreak = true; costs += vrp.getTransportCosts().getTransportCost(prevAct.getLocation(), act.getLocation(), prevAct.getEndTime(), route.getDriver(), route.getVehicle()); costs += vrp.getActivityCosts().getActivityCost(act, act.getArrTime(), route.getDriver(), route.getVehicle()); prevAct = act; } costs += vrp.getTransportCosts().getTransportCost(prevAct.getLocation(), route.getEnd().getLocation(), prevAct.getEndTime(), route.getDriver(), route.getVehicle()); if (route.getVehicle().getBreak() != null) { if (!hasBreak) { //break defined and required but not assigned penalty if (route.getEnd().getArrTime() > route.getVehicle().getBreak().getTimeWindow().getEnd()) { costs += 4 * (maxCosts * 2 + route.getVehicle().getBreak().getServiceDuration() * route.getVehicle().getType().getVehicleCostParams().perServiceTimeUnit); } } } } for(Job j : solution.getUnassignedJobs()){ costs += maxCosts * 2 * (11 - j.getPriority()); } return costs; } }; return solutionCostCalculator; }
单个插入点,插入位置评估计算 -> (localActivityInsertionCostsCaculator.java):
public InsertionData getInsertionData(final VehicleRoute currentRoute, final Job jobToInsert, final Vehicle newVehicle, double newVehicleDepartureTime, final Driver newDriver, final double bestKnownCosts) { JobInsertionContext insertionContext = new JobInsertionContext(currentRoute, jobToInsert, newVehicle, newDriver, newVehicleDepartureTime); Service service = (Service) jobToInsert; int insertionIndex = InsertionData.NO_INDEX; TourActivity deliveryAct2Insert = activityFactory.createActivities(service).get(0); insertionContext.getAssociatedActivities().add(deliveryAct2Insert); /* check hard constraints at route level */ InsertionData noInsertion = checkRouteContraints(insertionContext, constraintManager); if (noInsertion != null) return noInsertion; Collection<HardConstraint> failedActivityConstraints = new ArrayList<>(); /* check soft constraints at route level */ double additionalICostsAtRouteLevel = softRouteConstraint.getCosts(insertionContext); double bestCost = bestKnownCosts; additionalICostsAtRouteLevel += additionalAccessEgressCalculator.getCosts(insertionContext); TimeWindow bestTimeWindow = null; /* generate new start and end for new vehicle */ Start start = new Start(newVehicle.getStartLocation(), newVehicle.getEarliestDeparture(), Double.MAX_VALUE); start.setEndTime(newVehicleDepartureTime); End end = new End(newVehicle.getEndLocation(), 0.0, newVehicle.getLatestArrival()); TourActivity prevAct = start; double prevActStartTime = newVehicleDepartureTime; int actIndex = 0; Iterator<TourActivity> activityIterator = currentRoute.getActivities().iterator(); boolean tourEnd = false; while(!tourEnd){ TourActivity nextAct; if(activityIterator.hasNext()) nextAct = activityIterator.next(); else{ nextAct = end; tourEnd = true; } boolean not_fulfilled_break = true; for(TimeWindow timeWindow : service.getTimeWindows()) { deliveryAct2Insert.setTheoreticalEarliestOperationStartTime(timeWindow.getStart()); deliveryAct2Insert.setTheoreticalLatestOperationStartTime(timeWindow.getEnd()); ActivityContext activityContext = new ActivityContext(); activityContext.setInsertionIndex(actIndex); insertionContext.setActivityContext(activityContext); ConstraintsStatus status = fulfilled(insertionContext, prevAct, deliveryAct2Insert, nextAct, prevActStartTime, failedActivityConstraints, constraintManager); if (status.equals(ConstraintsStatus.FULFILLED)) { double additionalICostsAtActLevel = softActivityConstraint.getCosts(insertionContext, prevAct, deliveryAct2Insert, nextAct, prevActStartTime); double additionalTransportationCosts = activityInsertionCostsCalculator.getCosts(insertionContext, prevAct, nextAct, deliveryAct2Insert, prevActStartTime); if (additionalICostsAtRouteLevel + additionalICostsAtActLevel + additionalTransportationCosts < bestCost) { bestCost = additionalICostsAtRouteLevel + additionalICostsAtActLevel + additionalTransportationCosts; insertionIndex = actIndex; bestTimeWindow = timeWindow; } not_fulfilled_break = false; } else if (status.equals(ConstraintsStatus.NOT_FULFILLED)) { not_fulfilled_break = false; } } if(not_fulfilled_break) break; double nextActArrTime = prevActStartTime + transportCosts.getTransportTime(prevAct.getLocation(), nextAct.getLocation(), prevActStartTime, newDriver, newVehicle); prevActStartTime = Math.max(nextActArrTime, nextAct.getTheoreticalEarliestOperationStartTime()) + activityCosts.getActivityDuration(nextAct,nextActArrTime,newDriver,newVehicle); prevAct = nextAct; actIndex++; } if(insertionIndex == InsertionData.NO_INDEX) { InsertionData emptyInsertionData = new InsertionData.NoInsertionFound(); for (HardConstraint c : failedActivityConstraints) { emptyInsertionData.addFailedConstrainName(c.getClass().getSimpleName()); } return emptyInsertionData; } InsertionData insertionData = new InsertionData(bestCost, InsertionData.NO_INDEX, insertionIndex, newVehicle, newDriver); deliveryAct2Insert.setTheoreticalEarliestOperationStartTime(bestTimeWindow.getStart()); deliveryAct2Insert.setTheoreticalLatestOperationStartTime(bestTimeWindow.getEnd()); insertionData.getEvents().add(new InsertActivity(currentRoute, newVehicle, deliveryAct2Insert, insertionIndex)); insertionData.getEvents().add(new SwitchVehicle(currentRoute,newVehicle,newVehicleDepartureTime)); insertionData.setVehicleDepartureTime(newVehicleDepartureTime); return insertionData; }
一个节点选择好一个最优插入点后,需要评估对整体方案的影响
计算插入一个节点后的代价,用来比较各个unsignedJobs的打分: static double score(Job unassignedJob, InsertionData best, InsertionData secondBest, ScoringFunction scoringFunction){ if (best == null) { throw new IllegalStateException("cannot insert job " + unassignedJob.getId()); } double score; if (secondBest == null) { //either there is only one vehicle or there are more vehicles, but they cannot load unassignedJob //if only one vehicle, I want the job to be inserted with min iCosts //if there are more vehicles, I want this job to be prioritized since there are no alternatives score = (11 - unassignedJob.getPriority()) * (Integer.MAX_VALUE - best.getInsertionCost()) + scoringFunction.score(best, unassignedJob); } else { score = (11 - unassignedJob.getPriority()) * (secondBest.getInsertionCost() - best.getInsertionCost()) + scoringFunction.score(best, unassignedJob); } return score; }
相关推荐
《JSPRIT算法在车辆路径问题中的应用与详解》 JSPRIT,全称为Java Shortest Path Routing and Iterative Trips,是一个强大的开源工具,专为解决车辆路径问题(Vehicle Routing Problem, VRP)而设计。它基于Java...
jsprit jsprit是一个基于Java的开源工具包,用于解决丰富的和 。 它轻巧,灵活且易于使用,并且基于当前正在解决的单个通用电容式VRP 多仓库VRP 带Time Windows的VRP 带回传的VRP 带提货和送货的VRP 具有异构机队的...
9. **性能优化**:由于VRP问题的复杂性,服务器端可能需要优化算法执行效率,如使用多线程、内存管理优化、计算资源分配等策略。 10. **测试**:为了保证代码质量,开发者应编写单元测试和集成测试,可能使用JUnit...
3. **解决方案评估**:通过计算总距离、总成本或违反约束的程度来评估解决方案的质量。 4. **可视化**:JSprit还提供了一些基本的可视化工具,帮助用户理解解决方案的路线布局。 **JSprit的使用方法** 1. **安装与...
J-Horizon 是基于 java 的车辆路由问题软件,它使用 jsprit 库来解决:Capacitated VRP、Multiple Depot VRP、带时间窗口的 VRP、带回程的 VRP、带取货和交付的 VRP、带同构或异构车队的 VRP、带开放或封闭...
pgrServer Dijkstra最短路径搜索 行驶距离等时线 旅行营业员问题 全向路径 车辆路径问题(VRP)介绍pgrServer是一种路由服务,即使在密集网络(例如OpenStreetMap(OSM)数据集)下,也可以使用pgRouting拓扑将数据...