Hard Constraint doesn't seem to be applying

[kneekill]

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!

[jie31best]

Hi @kneekill,

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

HardActivityConstraint behavior

Is it possible that a route (list of activities) which fails HardActivityConstraint be part of the final response? I’m currently am experiencing this issue and would like to know if it’s my dab or the library’s. I’ve made sure every time a route with an specific list of activities goes through a certain constraint it fails, even singled out the shape of it. But it continues to appear. The other case are routes which never pass by the constraints end up being part of the result.

Non-fulfilled routes appear as solution

I have a hard constraint which verifies that the load at any moment of the route does not go below zero. The constraint worked well most times but some edge cases started to appear where the solution would contain invalid routes which do contain only one activity with a negative load. I started to check the iterations that lead to such result and there was never a FULFILLED iteration with such route. That specific combination would always appear as NOT_FULFILLED or NOT_FULFILLED_BREAK. My que…

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

[jie31best]

Regarding how to resolve this

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.

[jie31best]

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

[jie31best]

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) {

        }
    });

[Hung_Do_Xuan]

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.