GraphHopper.com | Forum | GitHub | Maps | Blog

Hard constraint for capacities


#1

Hello everyone,

My problem has vehicles with different pax capacities (3, 4, 6, 8). I’m wondering how it is possible to discard solutions which don’t maximize vehicle’s occupation. For example, if a service requires 3 car seats, a vehicle with 8 seats cannot fulfil this task (we must use a vehicle with 3 car seats). I guess a hard route constraint would work. My implementation starts getting the vehicle capacity through insertionContext.getNewVehicle().getType().getCapacityDimensions.get(1) and then compare it with the number of Job’s pax. I’m obtaining a solution which sometimes ignores the hard constraint, although I can’t find any case in which the constraint evaluates true for such cases (pairs vehicle-job). Is it possible that a service is inserted without being evaluated by the constraint?

Thank you all in advance


#2

Violation is happening at Ruin stage and not at insertion.

So your vehicle with capacity 8 might have 8 pax, but during ruin 5 of them might have been removed


#3

This isn’t documented anywhere, but as Bhoumik_Shah says the “ruin” phase can create solutions that violate your constraints.

I’ve found the best way of making sure your hard constraints are obeyed, are to also add checks for violations in a custom SolutionCostCalculator and penalize the solution enormously if it violates the hard constraints.

In our case, we did something like this:

public class MySolutionCostCalculator implements SolutionCostCalculator {
    @Override
    public double getCosts(VehicleRoutingProblemSolution solution) {
        double costs = 0.;
        // Here you look at the solution, which contains the routes: solution.getRoutes() 
        // and if you find something that violates your constraint, add Double.MAX_VALUE;
        // to the costs variable.
        // costs += Double.MAX_VALUE;
        // You might end up checking multiple hard constraint violations
        return costs;
    }
}

Then you set the “objective function” to this cost calculator for jsprit using Jsprit.Builder:

    Jsprit.Builder builder = Jsprit.Builder.newInstance(vrp);
    SolutionCostCalculator solutionCostCalculator = new MySolutionCostCalculator()
    builder.setObjectiveFunction(solutionCostCalculator);

    // Then the rest of the code to make jsprit run (e.g.)
    VehicleRoutingAlgorithm algorithm = builder.buildAlgorithm();
    algorithm.setMaxIterations(1000);
    Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();

#4

But doesn’t this severely revamp the CostCalculator, to the point it wouldn’t optimise the solution at all, except for the constraints? If I’m wrong please correct me, if not then is there a way to call the default getCosts() function before adding Double.MAX_VALUE to cost when the route violates constraints


#5

Yes, subsequently I’ve found out that giving huge penalities can lead to bad overall solutions!

Instead we’re using the same approach, but with a penalty that’s more in line with the “maxCosts” value, which we calculate like this:

JobNeighborhoods jobNeighborhoods = new JobNeighborhoodsFactory().createNeighborhoods(vrp, new AvgServiceAndShipmentDistance(vrp.getTransportCosts()), (int) (vrp.getJobs().values().size() * 0.5));
jobNeighborhoods.initialise();
final double maxCosts;
maxCosts = jobNeighborhoods.getMaxDistance();

What maxCosts represents is explained here.

So, now when we find a violation of our hard constraints when checking in our custom SolutionCostCalculator, we do something like this:

costs += maxCosts * <the number of violations in the hard constraint>