Minimum Load hard constraint

jsprit
1

Hi Folks

Im struggling with a constraint to check for minimum loads. I don’t think my requirement is unusual but my friend google has not found any similar issues or solutions. Let me explain.

Our trucks have different capacities and different minimum load values.
They also do, what I call, multiple “runs” per route and this is the trouble I have. That is to say a route might look like:

P1D1 P2BP3P4D2D3D4 B P5PD5

I have implemented both a hard constraint and a solution checker to try and ensure that undersized routes are allowed through.
Breaks are also scheduled

I need to make sure that the minimum load of each “run” is not too small.

P1(5)D1(5)P2(10)P3(10)P4(10)D2(10)D3(10)D4(10)5P(5)D5(5)
|------1-------|==============2================|-----3-------|
In above route, assuming a minimum load of 10, Runs 1 and 3 are undersized and should not be allowed. Run 2 is ok.
The approach I have taken for the hard constraint is that whenever I see a Delivery newAct where the prevAct was NOT a delivery and the nextAct is NOT a delivery, I search backward up the route to get the last Pickup and I check the load at that point + the size of the proposed job. It does not work.

I believe an Activity based Hard Constraint is not appropriate because individual activities cannot be evaluated to qualify the “run”. For example if a newAct is the first job being added to the route and is undersized it is not reasonable to reject it as NOT_FULFILLED as there may be other jobs added later. Equally there may NOT be other jobs added later but there is no way to predict that. Also when a new “run” is started there is no way to say that the “previous run” is no good.

Using a Route based Hard Constraint, as I understand it, is still about a proposal to add a job but qualifying the whole route on the basis of adding the job.

What I think is needed is the ability, when a route is completed, to remove any inappropriate jobs from that route and mark them as unassigned, and accept the remainder of the route if there are good “runs” remaining. Alternatively, worst case, to reject the whole route as being not ok.

Is this thinking correct or am I missing something?
Is there a way to implement my proposed solution ?

Your help would be very much appreciated.

kind regards
Grant

2

Hi Grant,

I agree with you that a hard constraint might not be appropriate because it might make it difficult to create a new “run”. And even if you implement a hard constraint, the ruin phase might break such constraint and result in an undersized “run”.

Thus I would propose the following:

  1. Implement a soft activity constraint to impose a penalty if the insertion resulted in an undersized “run”, and/or a reward if it make an undersized “run” not undersized;
  2. Add the same logic to the objective function to make sure it is in line with the soft constraint - e.g., a penalty for each undersized “run”;

You will need to tweak the value of the penalty/reward as a too small value might not serve your purpose and a too large value might distort the route optimality.

Moreover, the above “soft” approach might still generate undersized “runs”. Thus you might need a post-processing step after the insertion phase finishes, as you proposed:

  1. Implement an IterationEndsListener, in which you check each route in each solution, and unassign the jobs in each undersized “run”.

You cannot use an InsertionEndsListener here, because you only have access to the routes and not the unassigned job set in it.

Meanwhile you might want to implement an InsertionStartsListener with the same logic to make sure there are no undersized “runs” when you start the insertion phase, but I guess that is optional, because you already have the soft constraint and objective function to encourage job insertions to make undersized “runs” not undersized, as well as the post-processing step.

Hopefully the above approach will work.

Best regards,
He