How to deal with Shipments with more possible PickupLocations

jsprit
1

Hi all,
i face the problem where a shipment doesn’t have a defined pickup location,
instead i want the algorithm to choose the best one.
I think this feature should be in the Jsprit library, and i hope to contribute on this.

The solution i followed was to create multiple siblings of the shipment, one of each pickup location, and then by putting a HardRouteConstraint which only allows one of the siblings in the solution.
Results, as the quoted answers below suggest, are not optimal.

Following the below @stefan’s advice and forking jsprit to implement this feature how would you start?

So far i found those answers on the argument:
First one by Philip Welch - Open Door Logistics

Could you model this as 3 different pickup-delivery requests for each real request (one for each of the 3 depots) with an additional global constraint that only one of these should ever be loaded?
This would work in-terms of the model being correct, although the optimiser may not optimise it that effectively, as on each iteration it would effectively randomly choose, rather than optimally choose, the request which ‘wins’ and gets loaded. I suspect you’d need a modified recreate heuristic which systemically tested each option, for it to optimise effectively.

Second by @stefan

The other way might be to fork jsprit and extends it such that it can deal with shipments having multiple pickup and delivery locations. I assume it is not the most difficult extension since instead of having one pickup loop you have several (but it is probably little more difficult than just adding another loop).
Another way is what was once suggested from Phil that you can define four shipments A->C, A->D,B->C,B->D and define A->C and A->D as related, i.e. that you need to make sure (by defining an appropriate constraint) that only one shipment, either A->C or A->D, can be in the solution. The other will end up in the unassigned job list. But as Phil also wrote, it is more a random walk rather than a guided search. But still, you might get reasonable solutions, especially if you use the regret insertion (since regret insertion scores the jobs first according to opportunity costs, second_best - best).

and third by @jie31best (replying in my old topic)

For example, for job S, assume depot A, C and D are possible pickup locations, then you create three shipments S_a, S_c and S_d, and add a constraint that only one of the three can be served. I think it would be a hard route constraint such that, if the newAct job is one of the three, and if any of the other two are already served (you need a state updater to record this), the insertion is not allowed.
This seems to depend heavily on the order of insertion (in best insertion, half time it depends on job priority, and half time it is random; in regret insertion, it depends on regret score). It may or may not lead to sub-optimal result - I am not sure, and you might want to do some tests regarding this.

1 Like
2

My gut feeling is that it would be generally similar to how multiple time windows is implemented.

In the insertion cost calculators, for each associated activity of the job, you first loop over all possible locations, then loop over all possible time windows (associated with each location, i presume).

There will need to be other changes too. For example, you will need a setLocation method for TourActivity, and of course the way you define location(s) for the job and time windows for each location in the builder for Shipment (and Service).

It might require other changes as well, I am not sure, but above is what I have in mind for now.

3

Thanks @jie31best

So far i have implemented the possibility to

addPickupLocation

for shipments and by following @stefan’s advice i was willing to loop over the possible pickupLocations and “find the best one” this way:

for (Location location : shipment.getPickupLocations()) {
    //loops
    int     i       = 0;
    boolean tourEnd = false;
    //pickupShipmentLoop
    while (!tourEnd) {...
    ...

in

ShipmentInsertionCalculator.getInsertionData

Probably i have to implement a

setChoosenLocation

on shipment.

If it is correct how can i choose which one is better?
Where do i have to make this decision?

4

I was thinking that this loop would be immediately outside the one for the time windows:

for (Location pickupLocation : shipment.getPickupLocations()) {
    for(TimeWindow pickupTimeWindow : shipment.getPickupTimeWindows()) {
        ...

but I guess no big difference?

I’m not sure if you need to implement such method on Shipment. But I think you need a setLocation method on PickupShipment, or TourActivity in general, because you will need to set location for pickupShipment in the loop, otherwise you will not be able to calculate costs or go over constraints correctly.

pickupShipment.setLocation(pickupLocation);

I think this would be just like how best time window is chosen. Outside the loops you define a bestPickupLocation and set it as null.

Location bestPickupLocation = null;

Then you set it as pickupLocation in the following if clause:

if (totalActivityInsertionCosts < bestCost) {
    bestCost = totalActivityInsertionCosts;
    pickupInsertionIndex = i;
    deliveryInsertionIndex = j;
    bestPickupTimeWindow = pickupTimeWindow;
    bestDeliveryTimeWindow = deliveryTimeWindow;

    bestPickupLocation = pickupLocation;
}

Finally at the end you make sure pickupShipment got this best location:

pickupShipment.setLocation(bestPickupLocation);
5

Thanks a lot @jie31best for you support.
I’m getting very close to a general solution.
I had to make changes to

Shipment

class and

PickupShipment

class and then implemented the

PickupLocations

interface and the

PickupLocationsImpl

class just like for TimeWindows.

The major changes were done to

ShipmentInsertionCalculator.getInsertionData

and it seems to work fine.
The only thing so far not working as intended is that the solutions aren’t considering the

vehicleBuilder.setLatestArrival

and i’m getting solutions that go beyond the latestArrival.

Any ideas why?

I’m pasting the code below.

> /**
>      * Calculates the marginal cost of inserting job i locally. This is based on the
>      * assumption that cost changes can entirely covered by only looking at the predecessor i-1 and its successor i+1.
>      */
>     @Override
>     public InsertionData getInsertionData(final VehicleRoute currentRoute, final Job jobToInsert, final Vehicle newVehicle, double newVehicleDepartureTime, final Driver newDriver, final double bestKnownCosts) {
>         JobInsertionContext insertionContext = new JobInsertionContext(currentRoute, jobToInsert, newVehicle, newDriver, newVehicleDepartureTime);
>         Shipment            shipment         = (Shipment) jobToInsert;
>         TourActivity        pickupShipment   = activityFactory.createActivities(shipment).get(0);
>         TourActivity        deliverShipment  = activityFactory.createActivities(shipment).get(1);
>         insertionContext.getAssociatedActivities().add(pickupShipment);
>         insertionContext.getAssociatedActivities().add(deliverShipment);
> 
>         /*
>         check hard route constraints
>          */
>         InsertionData noInsertion = checkRouteContraints(insertionContext, constraintManager);
>         if (noInsertion != null) {
>             return noInsertion;
>         }
>         /*
>         check soft route constraints
>          */
>         double additionalICostsAtRouteLevel = softRouteConstraint.getCosts(insertionContext);
> 
>         double bestCost = bestKnownCosts;
>         additionalICostsAtRouteLevel += additionalAccessEgressCalculator.getCosts(insertionContext);
> 
>         int pickupInsertionIndex   = InsertionData.NO_INDEX;
>         int deliveryInsertionIndex = InsertionData.NO_INDEX;
> 
>         TimeWindow bestPickupTimeWindow   = null;
>         TimeWindow bestDeliveryTimeWindow = null;
>         Location bestPickupLocation = null;
> 
>         Start start = new Start(newVehicle.getStartLocation(), newVehicle.getEarliestDeparture(), newVehicle.getLatestArrival());
>         start.setEndTime(newVehicleDepartureTime);
> 
>         End end = new End(newVehicle.getEndLocation(), 0.0, newVehicle.getLatestArrival());
> 
>         ActivityContext pickupContext = new ActivityContext();
> 
>         TourActivity prevAct        = start;
>         double       prevActEndTime = newVehicleDepartureTime;
> 
>         List<TourActivity> activities = currentRoute.getTourActivities().getActivities();
> 
>         List<String> failedActivityConstraints = new ArrayList<>();
>         //loops
>         int     i       = 0;
>         boolean tourEnd = false;
>         //pickupShipmentLoop
>         while (!tourEnd) {
>             TourActivity nextAct;
>             if (i < activities.size()) {
>                 nextAct = activities.get(i);
>             }
>             else {
>                 nextAct = end;
>                 tourEnd = true;
>             }
> 
>             boolean pickupInsertionNotFulfilledBreak = true;
>             for (Location pickupLocation : shipment.getPickupLocations()) {
>                 for (TimeWindow pickupTimeWindow : shipment.getPickupTimeWindows()) {
>                     pickupShipment.setTheoreticalEarliestOperationStartTime(pickupTimeWindow.getStart());
>                     pickupShipment.setTheoreticalLatestOperationStartTime(pickupTimeWindow.getEnd());
>                     ((PickupShipment) pickupShipment).setLocation(pickupLocation);
>                     ActivityContext activityContext = new ActivityContext();
>                     activityContext.setInsertionIndex(i);
>                     insertionContext.setActivityContext(activityContext);
>                     ConstraintsStatus pickupShipmentConstraintStatus = fulfilled(insertionContext, prevAct, pickupShipment, nextAct, prevActEndTime, failedActivityConstraints, constraintManager);
>                     if (pickupShipmentConstraintStatus.equals(ConstraintsStatus.NOT_FULFILLED)) {
>                         pickupInsertionNotFulfilledBreak = false;
>                         continue;
>                     }
>                     else if (pickupShipmentConstraintStatus.equals(ConstraintsStatus.NOT_FULFILLED_BREAK)) {
>                         continue;
>                     }
>                     else if (pickupShipmentConstraintStatus.equals(ConstraintsStatus.FULFILLED)) {
>                         pickupInsertionNotFulfilledBreak = false;
>                     }
>                     double additionalPickupICosts = softActivityConstraint.getCosts(insertionContext, prevAct, pickupShipment, nextAct, prevActEndTime);
>                     double pickupAIC              = calculate(insertionContext, prevAct, pickupShipment, nextAct, prevActEndTime);
> 
>                     TourActivity prevAct_deliveryLoop  = pickupShipment;
>                     double       shipmentPickupArrTime = prevActEndTime + transportCosts.getTransportTime(prevAct.getLocation(), pickupShipment.getLocation(), prevActEndTime, newDriver, newVehicle);
>                     double       shipmentPickupEndTime = Math.max(shipmentPickupArrTime, pickupShipment.getTheoreticalEarliestOperationStartTime()) + activityCosts.getActivityDuration(pickupShipment, shipmentPickupArrTime, newDriver, newVehicle);
> 
>                     pickupContext.setArrivalTime(shipmentPickupArrTime);
>                     pickupContext.setEndTime(shipmentPickupEndTime);
>                     pickupContext.setInsertionIndex(i);
>                     insertionContext.setRelatedActivityContext(pickupContext);
> 
>                     double prevActEndTime_deliveryLoop = shipmentPickupEndTime;
> 
> 			/*
>             --------------------------------
> 			 */
>                     //deliverShipmentLoop
>                     int     j                    = i;
>                     boolean tourEnd_deliveryLoop = false;
>                     while (!tourEnd_deliveryLoop) {
>                         TourActivity nextAct_deliveryLoop;
>                         if (j < activities.size()) {
>                             nextAct_deliveryLoop = activities.get(j);
>                         }
>                         else {
>                             nextAct_deliveryLoop = end;
>                             tourEnd_deliveryLoop = true;
>                         }
> 
>                         boolean deliveryInsertionNotFulfilledBreak = true;
>                         for (TimeWindow deliveryTimeWindow : shipment.getDeliveryTimeWindows()) {
>                             deliverShipment.setTheoreticalEarliestOperationStartTime(deliveryTimeWindow.getStart());
>                             deliverShipment.setTheoreticalLatestOperationStartTime(deliveryTimeWindow.getEnd());
>                             ActivityContext activityContext_ = new ActivityContext();
>                             activityContext_.setInsertionIndex(j);
>                             insertionContext.setActivityContext(activityContext_);
>                             ConstraintsStatus deliverShipmentConstraintStatus = fulfilled(insertionContext, prevAct_deliveryLoop, deliverShipment, nextAct_deliveryLoop, prevActEndTime_deliveryLoop, failedActivityConstraints, constraintManager);
>                             if (deliverShipmentConstraintStatus.equals(ConstraintsStatus.FULFILLED)) {
>                                 double additionalDeliveryICosts = softActivityConstraint.getCosts(insertionContext, prevAct_deliveryLoop, deliverShipment, nextAct_deliveryLoop, prevActEndTime_deliveryLoop);
>                                 double deliveryAIC              = calculate(insertionContext, prevAct_deliveryLoop, deliverShipment, nextAct_deliveryLoop, prevActEndTime_deliveryLoop);
>                                 double totalActivityInsertionCosts = pickupAIC + deliveryAIC
>                                         + additionalICostsAtRouteLevel + additionalPickupICosts + additionalDeliveryICosts;
>                                 if (totalActivityInsertionCosts < bestCost) {
>                                     bestCost = totalActivityInsertionCosts;
>                                     pickupInsertionIndex = i;
>                                     deliveryInsertionIndex = j;
>                                     bestPickupTimeWindow = pickupTimeWindow;
>                                     bestDeliveryTimeWindow = deliveryTimeWindow;
>                                     bestPickupLocation = pickupLocation;
>                                 }
>                                 deliveryInsertionNotFulfilledBreak = false;
>                             }
>                             else if (deliverShipmentConstraintStatus.equals(ConstraintsStatus.NOT_FULFILLED)) {
>                                 deliveryInsertionNotFulfilledBreak = false;
>                             }
>                         }
>                         if (deliveryInsertionNotFulfilledBreak) {
>                             break;
>                         }
>                         //update prevAct and endTime
>                         double nextActArrTime = prevActEndTime_deliveryLoop + transportCosts.getTransportTime(prevAct_deliveryLoop.getLocation(), nextAct_deliveryLoop.getLocation(), prevActEndTime_deliveryLoop, newDriver, newVehicle);
>                         prevActEndTime_deliveryLoop = Math.max(nextActArrTime, nextAct_deliveryLoop.getTheoreticalEarliestOperationStartTime()) + activityCosts.getActivityDuration(nextAct_deliveryLoop, nextActArrTime, newDriver, newVehicle);
>                         prevAct_deliveryLoop = nextAct_deliveryLoop;
>                         j++;
>                     }
>                 }
>             }
>             if (pickupInsertionNotFulfilledBreak) {
>                 break;
>             }
>             //update prevAct and endTime
>             double nextActArrTime = prevActEndTime + transportCosts.getTransportTime(prevAct.getLocation(), nextAct.getLocation(), prevActEndTime, newDriver, newVehicle);
>             prevActEndTime = Math.max(nextActArrTime, nextAct.getTheoreticalEarliestOperationStartTime()) + activityCosts.getActivityDuration(nextAct, nextActArrTime, newDriver, newVehicle);
>             prevAct = nextAct;
>             i++;
>         }
>         if (pickupInsertionIndex == InsertionData.NO_INDEX) {
>             InsertionData emptyInsertionData = new InsertionData.NoInsertionFound();
>             emptyInsertionData.getFailedConstraintNames().addAll(failedActivityConstraints);
>             return emptyInsertionData;
>         }
>         InsertionData insertionData = new InsertionData(bestCost, pickupInsertionIndex, deliveryInsertionIndex, newVehicle, newDriver);
>         pickupShipment.setTheoreticalEarliestOperationStartTime(bestPickupTimeWindow.getStart());
>         pickupShipment.setTheoreticalLatestOperationStartTime(bestPickupTimeWindow.getEnd());
>         ((PickupShipment) pickupShipment).setLocation(bestPickupLocation);
>         deliverShipment.setTheoreticalEarliestOperationStartTime(bestDeliveryTimeWindow.getStart());
>         deliverShipment.setTheoreticalLatestOperationStartTime(bestDeliveryTimeWindow.getEnd());
>         insertionData.setVehicleDepartureTime(newVehicleDepartureTime);
>         insertionData.getEvents().add(new InsertActivity(currentRoute, newVehicle, deliverShipment, deliveryInsertionIndex));
>         insertionData.getEvents().add(new InsertActivity(currentRoute, newVehicle, pickupShipment, pickupInsertionIndex));
>         insertionData.getEvents().add(new SwitchVehicle(currentRoute, newVehicle, newVehicleDepartureTime));
>         return insertionData;
>     }
6

hmm, I’m not sure… The implementation looks fine to me. Can you double check that, after the shipment is inserted, the location of its pickup activity is indeed the one selected in the cost calculator?

Also could you provide an example in which the solution goes beyond the vehicle latest arrival?

Best regards,
He

7

@traveler It’s been a while, but were faced with the same “multiple pickup location” problem. Were you ever able to come up a with a solution to this?