OptaPlanner: Make planning entities chained and nullable

Question

Dear OptaPlanner community

For a specific use case of the OptaPlanner framework, I would like to use the chained data structure, as it is used in the Vehicle Routing example. The problem in our case is that there are a lot of customers, and not all of them can be served in a specific planning cycle. For that reason, I thought using nullable planning variables could be useful, so not all tasks need to be assigned, while still having valid chains of Suppliers. My questions is, how could I solve this problem? Have an extra chain with unassigned tasks? Is there another way to circumvent this issue? Regards Raphael

score 5 · Answer 1 · answered Oct 17 '18 at 15:10

I had a similar issue, where I needed to allow skipping of certain customers and minimize the number of vehicles used. I adapted the standard Optaplanner (7.12.0) VRP example by using a "Ghost" vehicle, like so:

@XStreamAlias("VrpGhostVehicle")
public class GhostVehicle extends Vehicle {
    @Override
    public Depot getDepot() {
        return null;
    }

    @Override
    public Long getId() {
        return Long.valueOf(0);
    }

    @Override
    public boolean isGhost() {
        return true;
    }

    @Override
    public int getCapacity() {
        return Integer.MAX_VALUE;
    }
}

To model customers that cannot be skipped, I added a "unskippable" boolean field to Customer.java. Then, in your vehicleRoutingScoreRules.drl, I adjusted and added constraints like:

rule "vehicleCapacity"
    when
        $vehicle : Vehicle(ghost == false, $capacity : capacity)
        accumulate(
            Customer(
                vehicle == $vehicle,
                $demand : demand);
            $demandTotal : sum($demand);
            $demandTotal > $capacity
        )
    then
        scoreHolder.addHardConstraintMatch(kcontext, $capacity - $demandTotal);
end

// ############################################################################
// Soft distance constraints
// ############################################################################

rule "distanceToPreviousStandstill"
    when
        $vehicle : Vehicle(ghost == false)
        $customer : Customer(previousStandstill != null, vehicle == $vehicle, $distanceFromPreviousStandstill : distanceFromPreviousStandstill)
    then
        scoreHolder.addSoftConstraintMatch(kcontext, - $distanceFromPreviousStandstill);
end

rule "distanceFromLastCustomerToDepot"
    when
        $vehicle : Vehicle(ghost == false)
        $customer : Customer(previousStandstill != null, vehicle == $vehicle)
        not Customer(previousStandstill == $customer)
    then
        Vehicle vehicle = $customer.getVehicle();
        scoreHolder.addSoftConstraintMatch(kcontext, - $customer.getDistanceTo(vehicle));
end


// ############################################################################
// Time window constraints 
// ############################################################################

rule "arrivalAfterDueTime"
    when
        $vehicle : Vehicle(ghost == false)
        TimeWindowedCustomer(dueTime < arrivalTime, vehicle == $vehicle, $dueTime : dueTime, $arrivalTime : arrivalTime)
    then
        scoreHolder.addSoftConstraintMatch(kcontext, -1000 * Math.abs($dueTime - $arrivalTime.longValue()));
end

rule "arrivalBeforeReadyTime"
    when
        $vehicle : Vehicle(ghost == false)
        TimeWindowedCustomer(readyTime > arrivalTime, vehicle == $vehicle, $readyTime : readyTime, $arrivalTime : arrivalTime)
    then
        scoreHolder.addSoftConstraintMatch(kcontext, -1000 * Math.abs($readyTime - $arrivalTime.longValue()));
end


// ############################################################################
// Constraints pertaining to station skipping and vehicle usage
// ############################################################################

rule "skippedCustomer"
    when
        $vehicle : Vehicle(ghost == true)
        $customer : Customer(vehicle == $vehicle, $unskippable : unskippable, $demand : demand)
    then
        if ($unskippable) {
            scoreHolder.addHardConstraintMatch(kcontext, -10000 * $demand);
        } else {
            scoreHolder.addSoftConstraintMatch(kcontext, -10000 * $demand);
        }
end

rule "usedTooManyVehicles"
    when
        $vehicle : Vehicle(nextCustomer != null, ghost == false)
    then
        scoreHolder.addSoftConstraintMatch(kcontext, -500000);
end

The bottom three rules are constraints I added to the example and I added further checks for ghost==false to the rules that should only apply to real vehicles. Notice that for unskippable customers we set a hard constraint whereas for skippable ones we set a soft constraint. The relative weights for skipping a customer or using a vehicle are of course application specific.

score 2 · Accepted Answer · answered Jul 10 '18 at 07:52

2

Chained planning variables don't support nullable=true yet (in version 7.8 at least).

In any case, I 'd apply continuous planning and start planning the next days too - the decisions on the next days might affect the decisions on the first day (for example presume you have 100 packets that needs to be delivered before day 2, but on day 2 half your drivers are on vacation and you don't have enough time to deliver them all on day 2 alone, so you need to deliver some on day 1 already.)

So, I 'd create VehicleDay which has a fixed Vehicle and Day - and I 'd use that everywhere were the example uses Vehicle now.

answered Jul 10 '18 at 07:52

Geoffrey De Smet

26,223
11
73
120

Thanks very much for your help. However, I am looking more at a problem, where some tasks Vehicles simply won't be assigned, for example because they are not profitable enough. This is fundamentally different from the normal vehicle routing problem, because here we would need nullable planning variables. I followed your hint and created a chain for each Vehicle and each day. – Raphael Beckmann Jul 11 '18 at 06:29
But no matter, how long we plan in advance, some tasks will simply never be assigned. Creating a "Garbage anchor" only delivers suboptimal results. Do you spontaneously have a tip for me, off the top of your head? Or should I give up on chained variables and use a less elegant solution instead, that is like the solution to VRP but without chains? Thanks so much again. Regards Raphael – Raphael Beckmann Jul 11 '18 at 06:29
Each task has a createdTime. It might even have a dueTime (and a readyTime for that matter). Add constraints which punish tasks that are too old and/or are handled after their dueTime. – Geoffrey De Smet Jul 11 '18 at 06:33
Thanks for your answer, I appreciate it – Raphael Beckmann Jul 13 '18 at 06:01

OptaPlanner: Make planning entities chained and nullable

2 Answers2

Linked