HardConstrastraint with percent values

jsprit
#1

I am trying to do a hardConstraint based on profit of service and cost of route ((cost / profit) * 100) the objective is provide a maxPercentLoss parameter and avoid some deliveries.The problem is if first delivery is less then parameter it dont continue to next.

public class LossConstraint implements HardActivityConstraint {

private final double maxPercentLoss;
private final StateManager stateManager;
private final VehicleRoutingActivityCosts activityCost;
private final VehicleRoutingTransportCosts transportCost;
private final Capacity defaultValue;

public LossConstraint(double maxPercentLoss, StateManager stateManager, VehicleRoutingActivityCosts activityCost, VehicleRoutingTransportCosts transportCost) {
    this.maxPercentLoss = maxPercentLoss;
    this.stateManager = stateManager;
    this.activityCost = activityCost;
    this.transportCost = transportCost;
    this.defaultValue = Capacity.Builder.newInstance().build();
}

@Override
public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
    double profit = getProfits(iFacts);
    double cost = getCosts(iFacts, prevAct, newAct, nextAct);
    double percentRoute = profit <= 0 ? 0 : ((cost / profit) * 100);
    if (percentRoute > maxPercentLoss) {
        return HardActivityConstraint.ConstraintsStatus.NOT_FULFILLED;
    }
    return HardActivityConstraint.ConstraintsStatus.FULFILLED;
}

private double getProfits(JobInsertionContext insertionContext) {
    Capacity loadAtEnd = stateManager.getRouteState(insertionContext.getRoute(), InternalStates.LOAD_AT_END, Capacity.class);
    loadAtEnd = firstNonNull(loadAtEnd, defaultValue);
    double profit = loadAtEnd.get(JspritUtil.PROFIT_INDEX);
    profit += insertionContext.getJob().getSize().get(JspritUtil.PROFIT_INDEX);
    return profit;
}

private double getCosts(JobInsertionContext iFacts, TourActivity prevAct, TourActivity act, TourActivity nextAct) {
    Double costs = stateManager.getRouteState(iFacts.getRoute(), InternalStates.COSTS, Double.class);
    costs = firstNonNull(costs, 0.0);
    costs += getCostsBetween(iFacts, prevAct, act) + getCostsBetween(iFacts, act, nextAct) - getCostsBetween(iFacts, prevAct, nextAct);
    return costs;
}

private double getCostsBetween(JobInsertionContext iFacts, TourActivity prevAct, TourActivity act) {
    double costs = transportCost.getTransportCost(prevAct.getLocation(), act.getLocation(), prevAct.getEndTime(), iFacts.getNewDriver(), iFacts.getNewVehicle());
    costs += activityCost.getActivityCost(act, act.getArrTime(), iFacts.getNewDriver(), iFacts.getNewVehicle());
    return costs;
}

}

#2

Hello,

My mind is that a SoftActivityConstraint would be more effective in the way that a hard constraint will have a pain to build an entire solution. A soft constraint will allow some locally bad choices which could appears as global good one.

You’ll need to edit the Objective function too

#3

I tried to write this solution… but I would like to avoid some deliveries. It is possible with softconstraints?

#4

If the associated cost calculation defined in the Objective function is not too much penalizing it will avoid deliveries if it has an interest.

#5

LossConstraint

public class LossConstraint implements SoftActivityConstraint {

private final double maxPercentLoss;
private final StateManager stateManager;
private final VehicleRoutingActivityCosts activityCost;
private final VehicleRoutingTransportCosts transportCost;
private final Capacity defaultValue;

public LossConstraint(double maxPercentLoss, StateManager stateManager, VehicleRoutingActivityCosts activityCost, VehicleRoutingTransportCosts transportCost) {
    this.maxPercentLoss = maxPercentLoss;
    this.stateManager = stateManager;
    this.activityCost = activityCost;
    this.transportCost = transportCost;
    this.defaultValue = Capacity.Builder.newInstance().build();
}

@Override
public double getCosts(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {        
    double profit = getProfitsRoute(iFacts, prevAct, newAct, nextAct, prevActDepTime);
    double cost = getCosts(iFacts, prevAct, newAct, nextAct);        
    double percentRoute = profit <= 0 ? 0 : ((cost / profit) * 100);
    
    if (percentRoute > maxPercentLoss) {
        double actCost = getCostsBetween(iFacts, prevAct, newAct);
        return actCost * 10;
    }
    return 0.0;
}

private double getProfitsRoute(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
    Capacity futureMaxLoad;
    double profit = 0.0;
    if (prevAct instanceof Start) {
        futureMaxLoad = stateManager.getRouteState(iFacts.getRoute(), InternalStates.MAXLOAD, Capacity.class);
        futureMaxLoad = firstNonNull(futureMaxLoad, defaultValue);
    } else {
        futureMaxLoad = stateManager.getActivityState(prevAct, InternalStates.FUTURE_MAXLOAD, Capacity.class);
        futureMaxLoad = firstNonNull(futureMaxLoad, defaultValue);
    }
    profit += futureMaxLoad.get(JspritUtil.PROFIT_INDEX);
    profit += newAct.getSize().get(JspritUtil.PROFIT_INDEX);
    return profit;
}

private double getCosts(JobInsertionContext iFacts, TourActivity prevAct, TourActivity act, TourActivity nextAct) {
    Double costs = stateManager.getRouteState(iFacts.getRoute(), InternalStates.COSTS, Double.class);
    costs = firstNonNull(costs, 0.0);
    costs += getCostsBetween(iFacts, prevAct, act) + getCostsBetween(iFacts, act, nextAct) - getCostsBetween(iFacts, prevAct, nextAct);
    return costs;
}

private double getCostsBetween(JobInsertionContext iFacts, TourActivity prevAct, TourActivity act) {
    double costs = transportCost.getTransportCost(prevAct.getLocation(), act.getLocation(), prevAct.getEndTime(), iFacts.getNewDriver(), iFacts.getNewVehicle());
    costs += activityCost.getActivityCost(act, act.getArrTime(), iFacts.getNewDriver(), iFacts.getNewVehicle());
    return costs;
}

}

CustomCostCalculatorFactory

public class CustomCostCalculatorFactory {

private final RouteAndActivityStateGetter stateManager;

public CustomCostCalculatorFactory(RouteAndActivityStateGetter stateManager) {
    this.stateManager = stateManager;
}

public SolutionCostCalculator createCalculatorWithLoss(double maxPercentLoss) {
    return new SolutionCostCalculator() {

        @Override
        public double getCosts(VehicleRoutingProblemSolution solution) {
            double c = 0.0;
            int countPercentLoss = 0;
            for (VehicleRoute r : solution.getRoutes()) {
                c += stateManager.getRouteState(r, InternalStates.COSTS, Double.class);
                c += getFixedCosts(r.getVehicle());
                if (getLossPercent(r) > maxPercentLoss) {
                    countPercentLoss++;
                }
            }
            c += countPercentLoss * c * .1;
            c += solution.getUnassignedJobs().size() * c * .1;
            return c;
        }

        private double getFixedCosts(Vehicle vehicle) {
            if (vehicle == null) {
                return 0.0;
            }
            if (vehicle.getType() == null) {
                return 0.0;
            }
            return vehicle.getType().getVehicleCostParams().fix;
        }

        private double getLossPercent(VehicleRoute r) {
            Double cost = stateManager.getRouteState(r, InternalStates.COSTS, Double.class);
            Integer profit = stateManager.getRouteState(r, InternalStates.LOAD_AT_END, Capacity.class).get(JspritUtil.PROFIT_INDEX);
            double percentRoute = profit <= 0 ? 0 : ((cost / profit) * 100);
            return percentRoute;
        }

    };
}

}

VehicleRoutingAlgorithm

        constraintManager.addConstraint(new LossConstraint(
                maxPercentLoss,
                stateManager,
                vrp.getActivityCosts(),
                costMatrix));            
               
        SolutionCostCalculator costCalculator = new CustomCostCalculatorFactory(stateManager).createCalculatorWithLoss(maxPercentLoss);
        vraBuilder.setObjectiveFunction(costCalculator);

It’s seems to be working … But if parameter maxPercentLoss is very low i would like move the jobs to UNASSIGNED JOB LIST. How can I do it?