Impose order in Jsprit with HardActivityConstraint

Question

In a scenario of re-solving a previously solved problem (with some new data, of course), it's typically impossible to re-assign a vehicle's very-first assignment once it was given. The driver is already on its way, and any new solution has to take into account that:

the job must remain his (can't be assigned to another vehicle)
the activity that's been assigned to him as the very-first, must remain so in future solutions

For the sake of simplicity, I'm using a single vehicle scenario, and only trying to impose the second bullet (i.e. ensure that a certain activity will be the first in the solution).

This is how I defined the constraint:

new HardActivityConstraint()
{
    @Override
    public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct,
                                       double prevActDepTime)
    {
        String locationId = newAct.getLocation().getId();

        //  we want to make sure that any solution will have "C1" as its first activity
        boolean activityShouldBeFirst = locationId.equals("C1");

        boolean attemptingToInsertFirst = (prevAct instanceof Start);

        if (activityShouldBeFirst && !attemptingToInsertFirst)
            return ConstraintsStatus.NOT_FULFILLED_BREAK;

        if (!activityShouldBeFirst && attemptingToInsertFirst)
            return ConstraintsStatus.NOT_FULFILLED;

        return ConstraintsStatus.FULFILLED;
    }
}

This is how I build the algorithm:

VehicleRoutingAlgorithmBuilder vraBuilder;
vraBuilder = new VehicleRoutingAlgorithmBuilder(vrpProblem, "schrimpf.xml"); 
vraBuilder.addCoreConstraints();
vraBuilder.addDefaultCostCalculators();

StateManager stateManager = new StateManager(vrpProblem);
ConstraintManager constraintManager = new ConstraintManager(vrpProblem, stateManager);
constraintManager.addConstraint(new HardActivityConstraint() { ... }, Priority.HIGH);
vraBuilder.setStateAndConstraintManager(stateManager, constraintManager);

VehicleRoutingAlgorithm algorithm = vraBuilder.build();

The results are not good. I'm only getting solutions with a single job assigned (the one with the required activity). In debug it's clear that the job insertion iterations consider many viable options that appear to solve the problem entirely, but at the bottom line, the best solution returned by the algorithm doesn't include the other jobs.

UPDATE: even more surprising, is that when I use the constraint in scenarios with over 5 vehicles, it works fine (worst results are with 1 vehicle).

I'll gladly attach more information if needed.

Thanks Zach

Stefan Schröder · Answer 1 · 2015-03-10T08:59:08.517

0

First, you can use initial routes to ensure that certain jobs need to be assigned to specific vehicles right from the beginning (see example).

Second, to ensure that no activity will be inserted between start and your initial job(location) (e.g. "C1" in your example), you need to prohibit it the way you defined your HardActConstraint, just modify it so that a newAct can never be between prevAct=Start and nextAct=act(C1).

Third, with regards to your update, just have in mind that the essence of the algorithm is to ruin part of the solution (remove a number of jobs) and recreate the solution again (insert the unassigned jobs). Currently, the schrimpf algorithm ruins a number of jobs relative to the total number of jobs, i.e. noJobs = 0.5 * totalNoJobs for the random ruin and 0.3 * totalNoJobs for the radial ruin. If your problem is very small, the share of jobs to be removed might not sufficiant. This is going to change with next release, where you can use an algorithm out of the box which defines an absolute minimum of jobs that need to be removed. For the time being, modify the shares in your algorithmConfig.xml.

edited Mar 10 '15 at 08:59

answered Mar 10 '15 at 08:31

Stefan Schröder

1,037
7
13

1

thanks for the quick and elaborate reply, Stefan. However, and correct me if I'm wrong, it appears that the way addInitialVehicleRoute() works is limited for Shipments - if I add the Pickup part of a Shipment to the initialVehicleRoute, I'm also required to include the Delivery part, which defies the purpose of letting the algo figure out the best way to include the Delivery part in a future route – Zach-M Mar 10 '15 at 12:59
1

Also, as for your second point, suggesting to modify the constraint so that newAct never comes between Start and C1 - what I did was in fact more general, not letting a non-C1 newAct come after Start (regardless of nextAct). Logically, both these flavors should achieve the same result, except the more general form should get us there faster. Why would you suggest to weaken the constraint? – Zach-M Mar 10 '15 at 13:11
You are correct, the way you implemented the constraint is smarter than what I proposed. – Stefan Schröder Mar 11 '15 at 07:44

Impose order in Jsprit with HardActivityConstraint

1 Answers1