GraphHopper.com | Forum | GitHub | Maps | Blog

If specified initial solution is the best ever solution, activities will have 0 arrival and end times


#1

When an initial solution is added to the algorithm, its cost is calculated, but its routes are not visited, i.e., all activities will have 0 arrival and end times.

If it happens to be the best ever solution, meaning all solutions generated during the ruin and recreate process are worse than it, it will be returned directly as the final solution and thus the activities in the final solution will have 0 arrival and end times.

An example (which is inspired from this post) is provided below.

Best regards,
He

    VehicleType vehicleType = VehicleTypeImpl.Builder.newInstance("type")
        .addCapacityDimension(0, 3)
        .build();
    Vehicle v = VehicleImpl.Builder.newInstance("v1")
        .setType(vehicleType)
        .setStartLocation(Location.newInstance(0, 0))
        .build();
    Shipment s1 = Shipment.Builder.newInstance("north-" + 1)
        .setPickupLocation(Location.newInstance(0, 1))
        .setDeliveryLocation(Location.newInstance(0, 0))
        .addSizeDimension(0, 1)
        .setName("north")
        .build();
    Shipment s2 = Shipment.Builder.newInstance("north-" + 2)
        .setPickupLocation(Location.newInstance(0, 1))
        .setDeliveryLocation(Location.newInstance(0, 0))
        .addSizeDimension(0, 1)
        .setName("north")
        .build();
    Shipment s3 = Shipment.Builder.newInstance("east-" + 1)
        .setPickupLocation(Location.newInstance(1, 0))
        .setDeliveryLocation(Location.newInstance(0, 0))
        .addSizeDimension(0, 1)
        .setName("east")
        .build();
    Shipment s4 = Shipment.Builder.newInstance("east-" + 2)
        .setPickupLocation(Location.newInstance(1, 0))
        .setDeliveryLocation(Location.newInstance(0, 0))
        .addSizeDimension(0, 1)
        .setName("east")
        .build();
    final VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance()
        .addJob(s1).addJob(s2).addJob(s3).addJob(s4)
        .addVehicle(v)
        .setFleetSize(VehicleRoutingProblem.FleetSize.FINITE)
        .build();

    VehicleRoute route = VehicleRoute.Builder.newInstance(v)
        .setJobActivityFactory(vrp.getJobActivityFactory())
        .addPickup(s1).addPickup(s2)
        .addDelivery(s1).addDelivery(s2)
        .addPickup(s3).addPickup(s4)
        .addDelivery(s3).addDelivery(s4)
        .build();
    VehicleRoutingProblemSolution initSolution = new VehicleRoutingProblemSolution(
        Collections.singleton(route),
        Double.MAX_VALUE);

    Jsprit.Builder algoBuilder = Jsprit.Builder.newInstance(vrp);

    // to make sure the initial solution is the best ever solution
    algoBuilder.setProperty(Jsprit.Strategy.WORST_REGRET, "0.");
    algoBuilder.setProperty(Jsprit.Strategy.CLUSTER_REGRET, "0.");

    final double maxCosts = 100;
    algoBuilder.setObjectiveFunction(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());

                    // to make sure the initial solution is the best ever solution
                    if (act instanceof DeliverShipment && prevAct instanceof TourActivity.JobActivity) {
                        String actDir = ((DeliverShipment) act).getJob().getName();
                        String prevActDir = ((TourActivity.JobActivity) prevAct).getJob().getName();
                        if (!actDir.equals(prevActDir)) costs += 100;
                    }

                    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;
        }
    });

    VehicleRoutingAlgorithm algo = algoBuilder.buildAlgorithm();

    double cost = algo.getObjectiveFunction().getCosts(initSolution);
    System.out.println("initial solution cost = " + cost);
    initSolution.setCost(cost);
    algo.addInitialSolution(initSolution);

    VehicleRoutingProblemSolution solution = Solutions.bestOf(algo.searchSolutions());
    SolutionPrinter.print(vrp, solution, SolutionPrinter.Print.VERBOSE);

#2

what can be done is to update the route times before adding it as an initial solution:

    StateManager stateManager = new StateManager(vrp);
    ConstraintManager constraintManager = new ConstraintManager(vrp, stateManager);
    algoBuilder.setStateAndConstraintManager(stateManager, constraintManager);

    VehicleRoutingAlgorithm algo = algoBuilder.buildAlgorithm();
    
    for (VehicleRoute vehicleRoute : initSolution.getRoutes())
        stateManager.reCalculateStates(vehicleRoute);

    algo.addInitialSolution(initSolution);

i guess this could also be done inside the .addInitialSolution() method before it calculates the cost for the initial solution, not sure which is more preferable.