Best way to enforce backhaul pick immediately after delivery

Hi,

The problem

I am working on a problem, where the vehicles picks up one or more items from given locations and then they deliver them to the destination of each pick (in any order). The twist is, that when they deliver something to a destination, they have to pick up immediately the backhaul cargo as well and they should be transported back to the original pickup location. (The two cargos have the same dimension, so capacity is never a problem.)

For example:

Tasks to do:

1 box of banana from Ap to Ad
1 box of apple from Bp to Bd
1 box of banana from Ap to Ad
1 box of lemon from Cp to Cd

From this, I create Shipment jobs (two from each):

Shipment 1.1 cargo: banana, pick location Ap, delivery location Ad
Shipment 1.2 cargo: banana, pick location Ad, delivery location Ap
Shipment 2.1 cargo: apple, pick location Bp, delivery location Bd
Shipment 2.2 cargo: apple, pick location Bd, delivery location Bp
etc…

What I would expect something like this:

Route 1:

  • R1.1: Pick banana from Ap (Shipment 1.1)
  • R1.2: Pick banana from Ap (Shipment 3.1)
  • R1.3: Pick apple from Bp (Shipment 2.1)
  • R1.4: Deliver apple to Bd (Shipment 2.1)
  • R1.5: Pick apple(backhaul) from Bd (Shipment 2.2)
  • R1.6: Deliver banana to Ad (Shipment 1.1)
  • R1.7: Pick banana(backhaul) from Ad (Shipment 1.2)
  • R1.8: Deliver banana to Ad (Shipment 3.1)
  • R1.9: Pick banana(backhaul) from Ad (Shipment 3.2)
  • R1.10: Deliver banana(backhaul) to Ap (Shipment 1.2)
  • R1.11: Deliver banana(backhaul) to Ap (Shipment 3.2)
  • R1.12: Deliver apple(backhaul) to Bp (Shipment 2.2)

Route 2:

  • R2.1: Pick lemon from Cp (Shipment 4.1)
  • R2.2: Deliver lemon to Cd (Shipment 4.1)
  • R2.3: Pick lemon(backhaul) from Cd (Shipment 4.2)
  • R2.4: Deliver lemon(backhaul) to Cp (Shipment 4.2)

What I must force is that R1.4 and R1.5 is after each other in the right order. (Also (R1.6,R1.7), (R1.8, R1.9), and (R2.2, R2.3) should follow each other tightly.)

My first solution idea

My solution idea was to create a HardActivityConstraint:

public class PickupEmptyAfterDeliveryConstraint implements HardActivityConstraint {

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

    if (newAct instanceof PickupActivity) {
        PickupActivity pa = (PickupActivity) newAct;
        String newId = pa.getJob().getId();
        ConstraintsStatus status;

        if (!newId.startsWith(AudiJspritCalculator.BACKHAUL_SHIPMENT_PREFIX)) {
            // This is not a backhaul pick -> ok
            status = ConstraintsStatus.FULFILLED;
        } else {
            String name = newId.substring(AudiJspritCalculator.BACKHAUL_SHIPMENT_PREFIX.length());

            if (prevAct instanceof DeliveryActivity) {
                // Previous activity is a delivery
                DeliveryActivity da = (DeliveryActivity) prevAct;
                if (da.getJob().getId().equals(AudiJspritCalculator.FILLIN_SHIPMENT_PREFIX + name)) {
                    // Previous activity is a delivery of the fill of the backhaul, so it's ok
                    status = ConstraintsStatus.FULFILLED;
                } else {
                    // Previous activity is not the delivery of the fill of the backhaul, fail
                    status = ConstraintsStatus.NOT_FULFILLED;
                }
            } else {
                // Previous activity is not a delivery, so fail (a backhaul pick cannot start a route)
                status = ConstraintsStatus.NOT_FULFILLED;
            }
        }

        return status;
    }

    return ConstraintsStatus.FULFILLED;
}

}

This means that the constraint rejects insertation when

  • The newAct is a pick of a backhaul shipment
  • AND the previuos activity is
    • not a delivery of a fill shipment
    • OR a not the delivery of the pickup of the newAct

This works fine in theory, but life is much harder. What I’ve found out after some testing and thinking, that this constraint so much reduces the number of acceptable results from all the possible solutions, that a genetic algorithm will never run into any valid solution. In other words: with this constraints the backhaul pickups is restricted to be inserted into only a single valid positions in all routes and the algorithm will never try this.

So my conclusion that maybe I have to do this completely differently, but I am stucked how I could do it.
Any suggestions?

PS: Maybe a ShipmentWithBackhaul job would be nice one day. :slight_smile:

Hi @Balage1551,

I think in the constraint you need to handle the following five cases:

  1. the newAct is a backhaul pickup and the corresponding fill shipment is already inserted - need to check whether the prevAct is the delivery of the corresponding fill shipment;

  2. the newAct is the delivery of a fill shipment and the corresponding backhaul shipment is already inserted - need to check whether the nextAct is the pickup of the corresponding backhaul shipment;

  3. the newAct is a backhaul pickup and the corresponding fill shipment is not inserted yet - need to check (a);

  4. the newAct is the delivery of a fill shipment and the corresponding backhaul shipment is not inserted yet - need to check (a); and

  5. the newAct is neither the pickup of a backhaul shipment nor the delivery of a fill shipment - need to check (a).

(a) whether the prevAct and the nextAct is a pair of i) delivery of a fill shipment and ii) pickup of the corresponding backhaul shipment.

What you have works for case 1 but you need to address other cases as well.

You will need to add to the state manager a state that memorizes whether a shipment is inserted or not for each fill/backhaul shipment.

Hopefully this works for you.

Best regards,
He

Thanks for the answer. They are great help!
This morning I’ve found out the missing option 2), but the other options I missed (especially the one when one inserts between a valid pair).

However, meanwhile, I ran into other problems and these stands even after implementing your other cases.

Ruin/insertation: a ruin could remove one item of a pair (= a fill delivery/backhaul pickup pair), but in case it doesn’t remove the other item of the pair, the insertation phase could only insert the item back to its original position. It leads a much slower convergation and would with high probability stuck the pair to the vehicle it was first inserted.

Therefor, I have to do one of the following:

Option A:
Create my own ruin/insert stategy where the pair is removed/inserted together. My only problem, I don’t know how to do it correctly.

Option B
Use three services instead of two shipments:

  • Service 1 = Fill pickup
  • Service 2 = Pair (fill delivery+backhaul pickup)
  • Service 3 = Backhaul delivery

and then keeping the three on the same route by hard constraint (order-correctly). However, the insert/ruin together problem of Option A still stands here, so I will need specialized ruin/insert strategy for this too.

Option C
Create a new Job type for BackhaulShipment and keeping together the three internally. It looks the tidiest solution, but after some deeper code digging I’ve found out that the handling of Shipment is not in the Shipment implementation alone, but wired into several classes (using instanceof and dedicated methods), so introducing a new Job implementation needs some contribution in several other classes. At the moment I don’t feel my current understanding of the code strong enough to do this.

I would be thankful for any advice, link to any example.

Best regards,
Balage

Hi Balage,

If I were you, I’d go with option A. You can take a look at how @stefan implements the strategies and the Jsprit algorithm.

But before that, I think you can try increasing the min/max share of the ruin strategies in the Jsprit algorithm (I assume you are using the Jsprit algorithm), and the default values are set here. Note this will lead to longer run time.

Best regards,
He

it seems to me that Option C would be useful if one would like to achieve that the related jobs are either all assigned or all unassigned - which has been asked about for a couple of times on this site (e.g., here and here).

I aggree with He.
First, I think it is really worth the effort to get rid of the tight coupling and the “instanceof” approach. Actually, when I wrote this, I thought that “everything” can be modelled with Shipments and Services ;). But I aggree with @Balage1551 improving this makes many things simpler and more elegant, and much more robust for future extensions.
Second, when it comes to the backhaul example, I think you are much better off modelling it as two seperate shipments, especially since capacity consumption of the backhaul shipment usually differs from the “main” shipment.
But I think also that jsprit should be developed so that one can model its own business specific case and if @Balage1551 thinks a new job type solves it, it should be possible.

EDIT: We might think of a job as a sequence of related activities. For example, a service is basically a single Pickup- or DeliveryActivity. A shipment is a sequence of a Pickup- AND DeliveryActivity, but one can also think of another job that is a sequence of four activities Do-A, Do-B, Do-C an finally Do-D.

EDIT2: The problem that I see here is that we need a mechanism that lets the user of a new activity define which impact this activity has on vehicle capacity, time windows and the various core constraints. This is a huge challenge. Additionally, one needs to generalize job insertion, for example, if you have a job with 4 activities, you first need to calculate insertion costs of the first act, then given insertion of first act, the insertion costs of the second act. Given first and second, the insertion costs of third etc… This is challenging too. When using Service and Shipments only, you can leverage existing insertion approach and just controll insertion via constraints.

is it possible to generalize ShipmentInsertionCalculator so that it can fit a job with any number of (sequenced) activities?