GraphHopper.com | Forum | GitHub | Maps | Blog

Hard Constraint doesn't seem to be applying


#1

Hey guys,

I’m having trouble with my hard constraint not being applied to a solution.

Some background: I’m trying to solve a similar problem to VRP but not exactly so I’m using Jsprit with constraints to model my problem.

Trailers are zero weighted deliveries with a priority of 10 (ie the lowest priority). I have a constraint below that is attempting to prevent two trailers being taken in a row but as you can see in the solution below it, “vehicle2” takes on 3 trailers in a row, namely trailer4, trailer6 and dummy. This constraint is the only one being applied, I removed the others in an attempt to debug.

    static class NoTrailersInARow implements HardActivityConstraint {

    @Override
    public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct,
            TourActivity nextAct, double prevActDepTime) {

        if(isInstanceOfDelivery(prevAct) && isInstanceOfDelivery(newAct)) {
            return ConstraintsStatus.NOT_FULFILLED;
        }
        if(isInstanceOfDelivery(newAct) && isInstanceOfDelivery(nextAct)) {
            return ConstraintsStatus.NOT_FULFILLED;
        }
        
        return ConstraintsStatus.FULFILLED;
    }
    
    private boolean isInstanceOfDelivery(TourActivity act) {
        return act.getName().equals("delivery");
    }
    
}

   +---------+----------------------+-----------------------+-----------------+-----------------+-----------------+-----------------+
| route   | vehicle              | activity              | job             | arrTime         | endTime         | costs           |
+---------+----------------------+-----------------------+-----------------+-----------------+-----------------+-----------------+
| 1       | vehicle              | start                 | -               | undef           | 0               | 0               |
| 1       | vehicle              | delivery              | TRAILER1        | 10              | 10              | 10              |
| 1       | vehicle              | pickupShipment        | JOB1            | 12              | 12              | 12              |
| 1       | vehicle              | deliverShipment       | JOB1            | 13              | 13              | 13              |
| 1       | vehicle              | delivery              | TRAILER2        | 29              | 29              | 29              |
| 1       | vehicle              | pickupShipment        | JOB3            | 38              | 38              | 38              |
| 1       | vehicle              | deliverShipment       | JOB3            | 42              | 42              | 42              |
| 1       | vehicle              | end                   | -               | 47              | undef           | 47              |
+---------+----------------------+-----------------------+-----------------+-----------------+-----------------+-----------------+
| 2       | vehicle2             | start                 | -               | undef           | 0               | 0               |
| 2       | vehicle2             | delivery              | TRAILER4        | 8               | 8               | 8               |
| 2       | vehicle2             | delivery              | TRAILER6        | 18              | 18              | 18              |
| 2       | vehicle2             | delivery              | DUMMY           | 20              | 20              | 20              |
| 2       | vehicle2             | delivery              | TRAILER8        | 24              | 24              | 24              |
| 2       | vehicle2             | pickupShipment        | JOB6            | 29              | 29              | 29              |
| 2       | vehicle2             | deliverShipment       | JOB6            | 34              | 34              | 34              |
| 2       | vehicle2             | delivery              | TRAILER5        | 50              | 50              | 50              |
| 2       | vehicle2             | pickupShipment        | JOB5            | 51              | 51              | 51              |
| 2       | vehicle2             | deliverShipment       | JOB5            | 57              | 57              | 57              |
| 2       | vehicle2             | delivery              | TRAILER7        | 77              | 77              | 77              |
| 2       | vehicle2             | pickupShipment        | JOB4            | 84              | 84              | 84              |
| 2       | vehicle2             | deliverShipment       | JOB4            | 89              | 89              | 89              |
| 2       | vehicle2             | end                   | -               | 100             | undef           | 100             |
+---------+----------------------+-----------------------+-----------------+-----------------+-----------------+-----------------+
| 3       | vehicle3             | start                 | -               | undef           | 0               | 0               |
| 3       | vehicle3             | delivery              | TRAILER3        | 21              | 21              | 21              |
| 3       | vehicle3             | pickupShipment        | JOB2            | 29              | 29              | 29              |
| 3       | vehicle3             | deliverShipment       | JOB2            | 31              | 31              | 31              |
| 3       | vehicle3             | end                   | -               | 53              | undef           | 53              |
+--------------------------------------------------------------------------------------------------------------------------------+  

Any help on this will be much appreciated!


#2

Hi @kneekill,

Regarding why this happens, a possible reason is the ruin process. See the following related discussions:

Regarding how to resolve this, an elegant way is to implement a custom ruin strategy to make sure that, when the ruin phase ends, you will not have two “delivery” activities in a row.

A workaround would be to implement a soft activity insertion constraint to encourage the insertion of a non-“delivery” activity between two “delivery” activities.

Best regards,
He


#3

hmm, on a second thought, actually, an InsertionStartsListener or a RuinListener might be good enough. I will do a bit of tests and get back to you.


#4

Hi @kneekill,

I tested on the following example:

    VehicleTypeImpl type = VehicleTypeImpl.Builder.newInstance("type")
            .addCapacityDimension(0, 3)
            .build();
    VehicleImpl v1 = VehicleImpl.Builder.newInstance("v1")
            .setType(type)
            .setReturnToDepot(false)
            .setStartLocation(Location.newInstance(0, 0))
            .build();
    Delivery s1 = Delivery.Builder.newInstance("s1")
            .setLocation(Location.newInstance(0, 0))
            .build();
    Delivery s2 = Delivery.Builder.newInstance("s2")
            .setLocation(Location.newInstance(0, 0))
            .build();
    Service s3 = Service.Builder.newInstance("s3")
            .setLocation(Location.newInstance(0, 1))
            .build();
    VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance()
            .addJob(s1)
            .addJob(s2)
            .addJob(s3)
            .addVehicle(v1)
            .setFleetSize(VehicleRoutingProblem.FleetSize.FINITE)
            .build();

    Jsprit.Builder algorithmBuilder = Jsprit.Builder.newInstance(vrp);
    StateManager stateManager = new StateManager(vrp);
    ConstraintManager constraintManager = new ConstraintManager(vrp, stateManager);
    constraintManager.addConstraint(new HardActivityConstraint() {
        @Override
        public ConstraintsStatus fulfilled(
                JobInsertionContext iFacts,
                TourActivity prevAct,
                TourActivity newAct,
                TourActivity nextAct,
                double prevActDepTime) {

            if(isInstanceOfDelivery(prevAct) && isInstanceOfDelivery(newAct)) {
                return ConstraintsStatus.NOT_FULFILLED;
            }
            if(isInstanceOfDelivery(newAct) && isInstanceOfDelivery(nextAct)) {
                return ConstraintsStatus.NOT_FULFILLED;
            }

            return ConstraintsStatus.FULFILLED;
        }
    }, ConstraintManager.Priority.HIGH);
    algorithmBuilder.setStateAndConstraintManager(stateManager, constraintManager);

    VehicleRoutingAlgorithm algorithm = algorithmBuilder.buildAlgorithm();
    VehicleRoutingProblemSolution s = Solutions.bestOf(algorithm.searchSolutions());
    SolutionPrinter.print(vrp, s, SolutionPrinter.Print.VERBOSE);

so now, as you have observed, even with the constraint that two delivery activities cannot be in a row, I get a solution with cost 1 and sequence s1, s2, s3 - two delivery activities in a row.

Then I add the following InsertionStartsListener:

    algorithm.addListener(new InsertionStartsListener() {
        @Override
        public void informInsertionStarts(Collection<VehicleRoute> routes, Collection<Job> unassignedJobs) {
            Map<TourActivity, VehicleRoute> toDeleteActRouteMap = new HashMap<>();
            for(VehicleRoute route : routes){
                for (int i = 0; i < route.getActivities().size() - 1; i++) {
                    TourActivity act1 = route.getActivities().get(i);
                    TourActivity act2 = route.getActivities().get(i + 1);
                    if(isInstanceOfDelivery(act1) && isInstanceOfDelivery(act2)) {
                        toDeleteActRouteMap.put(act1, route);
                    }
                }
            }
            for (Map.Entry<TourActivity, VehicleRoute> entry : toDeleteActRouteMap.entrySet()) {
                TourActivity act = entry.getKey();
                VehicleRoute route = entry.getValue();
                if (act instanceof TourActivity.JobActivity) {
                    Job job = ((TourActivity.JobActivity) act).getJob();
                    boolean removed = route.getTourActivities().removeJob(job);
                    if(removed) {
                        unassignedJobs.add(job);
                    }
                }
            }
        }
    });

now I get a solution with cost 2 and sequence s2, s3, s1 - it follows the constraint.

Hopefully this helps.

Best regards,
He


When the ruin process breaks the constraints
#5

a corresponding RuinListener:

    algorithm.addListener(new RuinListener() {
        @Override
        public void ruinStarts(Collection<VehicleRoute> routes) {

        }

        @Override
        public void ruinEnds(Collection<VehicleRoute> routes, Collection<Job> unassignedJobs) {
            Map<TourActivity, VehicleRoute> toDeleteActRouteMap = new HashMap<>();
            for(VehicleRoute route : routes){
                for (int i = 0; i < route.getActivities().size() - 1; i++) {
                    TourActivity act1 = route.getActivities().get(i);
                    TourActivity act2 = route.getActivities().get(i + 1);
                    if(isInstanceOfDelivery(act1) && isInstanceOfDelivery(act2)) {
                        toDeleteActRouteMap.put(act1, route);
                    }
                }
            }
            for (Map.Entry<TourActivity, VehicleRoute> entry : toDeleteActRouteMap.entrySet()) {
                TourActivity act = entry.getKey();
                VehicleRoute route = entry.getValue();
                if (act instanceof TourActivity.JobActivity) {
                    Job job = ((TourActivity.JobActivity) act).getJob();
                    boolean removed = route.getTourActivities().removeJob(job);
                    if(removed) {
                        unassignedJobs.add(job);
                    }
                }
            }
        }

        @Override
        public void removed(Job job, VehicleRoute vehicleRoute) {

        }
    });

Restrict back to back same location job
#6

Hi, thanks for this solution, just wanted to ask if there is a possible equivalent for HardRouteConstraint, which would remove the whole route if violated.
Or if I can achieve this i through adding all activities into toDeleteActRouteMap.