Jsprit：无法添加多个相关作业
我正在使用JSPRIT来解决路由和旅行者问题。 它实际上适用于简单的约束（时间，容量等）。 但我试图实施“相关工作”的成员。 我成功完成了像第7个工作这样的简单案例，在列表中的第1个工作之前提供了服务。
我想分组和优化一些服务。 我想强迫第7次在第1次和第21次之前在第13次之前送达。 也许还有一些。
当我尝试这个时，结果顺序仅在第1个之前的第7个但第21个不在第13个之前，有时甚至不在同一个路径中。
这是一个比以下更复杂的案例： JSprit中的相关工作 。
有人会有例子吗？ 有人试过吗？
public final static int PERSON_DIMENSION_INDEX = 0; public final static boolean VEHICLE_RETURNS_AT_DEPOT = false; public final static Location TEST_VEHICLE_LOCATION = Location.newInstance(48.856614, 2.352222); public final static int TEST_VEHICLE_LOCATION_INDEX = 0; public final static int MAX_INCREMENT = 25; public final static boolean USE_DISTANCE_MATRIX = true; public final static boolean ADD_TIME_CONSTRAINTS = false; public final static boolean USE_ONE_BEFORE_ANOTHER_CONSTRAINT = true; private static final boolean PLOT_RESULT = false; public static void main(String[] args) { /* * Date today : 8 o'clock */ // .getDirections(contextTest, "27 rue jacques louvel tessier", "10 rue // de geispitzen"); Calendar c = new GregorianCalendar(); c.set(Calendar.HOUR_OF_DAY, 8); // anything 0 - 23 c.set(Calendar.MINUTE, 0); c.set(Calendar.SECOND, 0); Date d1 = c.getTime(); // the midnight, that's the first second of the // day. System.out.println("Date today 8h clock"); System.out.println(d1.toString()); System.out.println(d1.getTime() / 1000); final long TODAY_START_TIME = d1.getTime() / 1000; /* * Here, get the vehicles types. */ List vehicleTypes = getVehiclesTypesFromDatabase(); /* * Built de jsprit vehicle types. */ Map jSpritvVehicleTypes = new HashMap(); for (TypeVehicle vehicleType : vehicleTypes) { String vehicleTypeId = String.valueOf(vehicleType.getId()); int vehicleCapacity = vehicleType.getAvailableSeats(); VehicleTypeImpl jSpritvVehicleType = VehicleTypeImpl.Builder.newInstance(vehicleTypeId) .addCapacityDimension(PERSON_DIMENSION_INDEX, vehicleCapacity).build(); jSpritvVehicleTypes.put(vehicleTypeId, jSpritvVehicleType); } /* * Here, get the vehicles. */ List vehicles = getVehiclesFromDatabase(); /* * Here, build the vehicles. */ Map jSpritVehicles = new HashMap(); for (Vehicle Vehicle : vehicles) { String vehicleId = String.valueOf(Vehicle.getId()); List habilitations = Vehicle.getHabilitations(); String thisVehicleTypeId = String.valueOf(Vehicle.getType()); VehicleTypeImpl vehicleType = jSpritvVehicleTypes.get(thisVehicleTypeId); Skills skills = null; for (Habilitation habilitation : habilitations) { skills = new Skills.Builder().addSkill(habilitation.getLabel()).build(); } VehicleImpl vehicleImpl = VehicleImpl.Builder.newInstance(vehicleId).setType(vehicleType).addSkills(skills) .setStartLocation(TEST_VEHICLE_LOCATION).setEarliestStart(TODAY_START_TIME).build(); jSpritVehicles.put(vehicleId, vehicleImpl); } /* * Here, get the spots to serve (pickups and deliveries) */ List places = getSpots(); // This will change a lot. List services = new ArrayList(); int increment = 0; String[] origins = new String[MAX_INCREMENT]; String[] destinations = new String[MAX_INCREMENT]; origins[0] = TEST_VEHICLE_LOCATION.getCoordinate().getX() + "," + TEST_VEHICLE_LOCATION.getCoordinate().getY(); destinations[0] = TEST_VEHICLE_LOCATION.getCoordinate().getX() + "," + TEST_VEHICLE_LOCATION.getCoordinate().getY(); increment++; for (Place place : places) { if (increment < MAX_INCREMENT) { String id = String.valueOf(increment); int dimensionValue = place.getAccessibility(); double lat = place.getLat(); double lng = place.getLng(); Location location = Location.newInstance(lat, lng); Service.Builder builder = Service.Builder.newInstance(id) .addSizeDimension(PERSON_DIMENSION_INDEX, dimensionValue).setLocation(location); /* * TIME CONSTRAINTS */ if (ADD_TIME_CONSTRAINTS) { int random = randomNumber(0, 43200); // 12 hours of possible // work. 8am / 8pm System.out.println("Time windows : " + new Date((TODAY_START_TIME + random) * 1000).toString() + " / " + new Date((TODAY_START_TIME + random + 1800) * 1000).toString()); builder.addTimeWindow(TODAY_START_TIME + random, TODAY_START_TIME + random + 1800); } Service service = builder.build(); services.add(service); origins[increment] = lat + "," + lng; destinations[increment] = lat + "," + lng; increment++; } } /* * Here, get the constraints (ex : one before another) */ /* * Here, get the time limits */ VehicleRoutingTransportCostsMatrix costsMatrix; if (USE_DISTANCE_MATRIX) { /* * Distances matrix */ VehicleRoutingTransportCostsMatrix.Builder vrtcMatrix = VehicleRoutingTransportCostsMatrix.Builder .newInstance(true); GeoApiContext context = null; costsMatrix = generateCostMatrix(origins, destinations, vrtcMatrix, context); } /* * Init jsprit */ VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance(); vrpBuilder.addAllVehicles(jSpritVehicles.values()).addAllJobs(services); vrpBuilder.setFleetSize(FleetSize.INFINITE); if (USE_DISTANCE_MATRIX) { System.out.println("Using DISTANCE MATRIX..."); vrpBuilder = vrpBuilder.setRoutingCost(costsMatrix); } else { System.out.println("NOT Using DISTANCE MATRIX..."); } VehicleRoutingProblem problem = vrpBuilder.build(); /* * get the algorithm out-of-the-box. */ VehicleRoutingAlgorithm algorithm; if (USE_ONE_BEFORE_ANOTHER_CONSTRAINT) { /** * Adding constraints... */ String before = "11"; String after = "9"; final StateManager stateManager = new StateManager(problem); stateManager.addStateUpdater(new JobsInRouteMemorizer(stateManager)); ConstraintManager constraintManager = new ConstraintManager(problem, stateManager); constraintManager.addConstraint(new OneJobBeforeAnother(stateManager, before, after)); final RewardAndPenaltiesThroughSoftConstraints contrib = new RewardAndPenaltiesThroughSoftConstraints(problem, before, after); SolutionCostCalculator costCalculator = new SolutionCostCalculator() { @Override public double getCosts(VehicleRoutingProblemSolution solution) { double costs = 0.; List routes = (List) solution.getRoutes(); for(VehicleRoute route : routes){ costs+=route.getVehicle().getType().getVehicleCostParams().fix; costs+=stateManager.getRouteState(route, InternalStates.COSTS, Double.class); costs+=contrib.getCosts(route); } return costs; } }; VehicleRoutingAlgorithmBuilder vraBuilder = new VehicleRoutingAlgorithmBuilder(problem, "algorithmConfig.xml"); vraBuilder.addCoreConstraints(); vraBuilder.setStateAndConstraintManager(stateManager, constraintManager); vraBuilder.setObjectiveFunction(costCalculator); algorithm = vraBuilder.build(); } else { algorithm = Jsprit.createAlgorithm(problem); } /* * and search a solution which returns a collection of solutions (here * only one solution is constructed) */ Collection solutions = algorithm.searchSolutions(); /* * use the static helper-method in the utility class Solutions to get * the best solution (in terms of least costs) */ for (VehicleRoutingProblemSolution vehicleRoutingProblemSolution : solutions) { System.out.println("Solution #" + ((List) solutions).indexOf(vehicleRoutingProblemSolution)); System.out.println(vehicleRoutingProblemSolution.getCost()); } VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions); SolutionPrinter.print(problem, bestSolution, Print.VERBOSE); new GraphStreamViewer(problem, bestSolution).labelWith(Label.ID).setRenderDelay(100).display(); if(PLOT_RESULT){ new GraphStreamViewer(problem, bestSolution).labelWith(Label.ID).setRenderDelay(100).display(); } } 我终于找到了。 我只是忘了将生成的成本添加到成本计算器中。 见下文 ：
final List contribs = new ArrayList (); for (Integer id : forcedOrdersList.keySet()) { List order= forcedOrdersList.get(id); String before = order.get(0); String after = order.get(1); constraintManager.addConstraint(new OneJobBeforeAnother(stateManager, before, after)); contribs.add(new RewardAndPenaltiesThroughSoftConstraints(problem, before, after)); } SolutionCostCalculator costCalculator = new SolutionCostCalculator() { @Override public double getCosts(VehicleRoutingProblemSolution solution) { double costs = 0.; List routes = (List ) solution.getRoutes(); for(VehicleRoute route : routes){ costs+=route.getVehicle().getType().getVehicleCostParams().fix; costs+=stateManager.getRouteState(route, InternalStates.COSTS, Double.class); for (RewardAndPenaltiesThroughSoftConstraints contrib : contribs) { costs+=contrib.getCosts(route); } } return costs; } };