Shipment loading

jsprit
1

Hello,

I have multiple shipments with various PickUp and Delivery time windows.
All the shipments are loaded at the depot, but whatever the quantity, the time to perform this action is only dependant ont the vehicle (10 or 15 minutes, I can load 1 or 15 shipments in that time).

Is there a proper way to implement it ? Nowadays, i’m using a SoftActivityConstraint, which set the arrival time of the new Activity. (Is this additionnal time propagate afterwards ?) or to the next Activity, depend on the case.

Thanks,

Gwénaël.

2

Hi @braktar,

Are you asking for something like vehicle-dependent service duration for jobs? That is, for a particular job (service, pickup, or delivery), vehicle A serves it using 15 minutes, while vehicle B serves it using 10 minutes.

If so, then this feature is not available yet, but will be soon - see @stefan’s response in this post.

There is also an open pull request #151 on this.

Best regards,
He

1 Like
3

Thanks for the answer.

my question is a bit different, but need this feature too :slightly_smiling: .

As I’m picking up a shipment, I want to delete the operation time of all the next pick up performed at this place until the vehicle leaves it.

5

As we set a new Arrival Time, Does it propagate ?
Does it shift all the nexts activities given this new parameter ? How ? Or, do we need to update the Arrival Time of the nexts activities ?

6

Here is the state of my implementation :

public class ReloadConstraint implements SoftActivityConstraint {

    ArrayList<double[]> local_vehicle_windows;

    public ReloadConstraint(ArrayList<double[]> local_vehicle_windows) {
        super();
        this.local_vehicle_windows = local_vehicle_windows;
    }

    @Override
    public double getCosts(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double depTimeAtPrevAct) {
    	double cost = 0;
    	
    	// Add a new activity as first reloading activity
    	// new activity == depot and previous != depot
    	// d 'p'
    	double newActArrTime = depTimeAtPrevAct + costMatrix.getTransportTime(prevAct.getLocation(), newAct.getLocation(), 0.0, iFacts.getNewDriver(), iFacts.getNewVehicle());

        if (newAct.getLocation() == iFacts.getNewVehicle().getStartLocation() && prevAct.getLocation() != iFacts.getNewVehicle().getStartLocation() && prevAct.getIndex() >= 0){
            newActArrTime += local_vehicle_windows.get(Integer.parseInt(iFacts.getNewVehicle().getId()))[2];
        }
        newActArrTime = Math.max(newActArrTime, newAct.getTheoreticalEarliestOperationStartTime());
        newAct.setArrTime(newActArrTime);

        double newActEndTime = newActArrTime + newAct.getOperationTime();

        VehicleRoute route = iFacts.getRoute();
        List<TourActivity> tourActivities = route.getActivities();
        if (!(nextAct instanceof End)) {
            boolean actAfterNew = false;
            for (TourActivity tourActivity : tourActivities) {
                if (!actAfterNew && !tourActivity.equals(nextAct)){
                    continue;
                }
                actAfterNew = true;

                prevAct = newAct;
                newAct = tourActivity;
                
                depTimeAtPrevAct = newActEndTime;

                newActArrTime = depTimeAtPrevAct + costMatrix.getTransportTime(prevAct.getLocation(), newAct.getLocation(), 0.0, iFacts.getNewDriver(), iFacts.getNewVehicle());

    	    	if (newAct.getLocation() == iFacts.getNewVehicle().getStartLocation() && prevAct.getLocation() != iFacts.getNewVehicle().getStartLocation() && prevAct.getIndex() >= 0){
    		        newActArrTime += local_vehicle_windows.get(Integer.parseInt(iFacts.getNewVehicle().getId()))[2];
    		    }
    	    	
    	        newActArrTime = Math.max(newActArrTime, newAct.getTheoreticalEarliestOperationStartTime());
                newAct.setArrTime(newActArrTime);
                
    	    	newActEndTime = newActArrTime + newAct.getOperationTime();
            }
        }
        return cost;
    }
}

I consider now only the case where I pickup after a delivery activity. That allow me to don’t shift at the first departure and to propagate easily.
By propagate, I consider to recompute the shift at each insertion, which make the computation heavier, but I have not find another way.

It works quite well, Except for one Activity after reloading which don’t take into account the shift.
I think i’m missing a case, but can’t find out which one it is.

Edit : I’m switching to use a HardActivityConstraint, seems to give well constrained results.

7

Hi Gwénaël,

I get what you would like to achieve here: every time a vehicle comes back to the depot from somewhere else (btw, why do you also need prevAct.getIndex() >= 0?) and before it starts service, it waits for a time period, the length of which is vehicle-dependent and stored in the ArrayList.

However, I am not sure about the way you implement it because I personally have never used .setArrTime() like you do. Your ReloadConstraint does not reward or penalize any insertion (because the returned cost is always 0) but just sets the arrival times for newAct and shifts that of all downstream activities every time you try to insert newAct at a particular position.

Let me use a small example to explain:

Assume there are existing activities A and B in a route and activity C is to be inserted, then there are three possible insertion positions: 1) b/w Start and A; 2) b/w A and B; and 3) b/w B and End. When you try to insert C b/w Start and A, you set arrival times for C, A, and B; then, when you try to insert C b/w A and B, you set arrival time for C and B again; finally, when you try to insert C b/w B and End, you set arrival time for C again.

Therefore, after trying to insert C into the route over all three possible positions, you set the arrival time of C as when you try to insert it at the last possible position (i.e., b/w B and End), and you set the arrival times for all existing activities as when you try to insert C before it.

This looks incorrect to me. I think what you should do is to define what insertion you would like to reward or penalize (allow or forbid in the case of HardActivityConstraint) and avoid using .setArrTime() in your custom constraint.

Best regards,
He

8

Oh ! Thanks a lot for those explanations, it makes me understand a lot much better the mechanisms of Jsprit.

Then, my approach I wrong because i’m updating the Arrival and End Time even if the activity can’t fulfilled the Constraint.
But I didn’t get that, the Insertion try multiple case before choosing one.
That mean, I need to recompute the whole route each try to consider all the waits already define.

Moreover, I have switched to a HardConstraint which is much fitted in my case.

9

I’ve moved the shift into the ActivityTimeTracker class, which update correctly the tour time once we call UpdateActivityTimes. The Shift itself, is now property of the vehicles, but it will be much general as a Location property.

I just can’t find or understand, how it’s updated through the insertion of UnassignedJobs.
The search insert some Jobs on the same Route and ignore the real state of the ActivityTimes.
Can someone enlighten me on this point ?

EDIT :

After a deep read of the source code, I’ve understand there is multiple level in the control of the search :

ActivityTimeTracker - Ensure a correct time calculation once we recreate a solution.
SolutionAnalyser - Ensure we have a correct time calculation once we compare Solutions
ShipmentInsertionCalculator/ServiceInsertionCalculator/ServiceOnRouteLevelCalculator - Ensure to have correct times for each try of insertion.
VehicleDependentTimeWindowConstraints - Ensure the correctness of the insertion.

Did I miss something ?

Thanks,

Gwénaël

10

A little report on my current reflection :

I solve my time shifting through the getTransportTime function.
Because of the context dependency, i need information from the previous activity which is given by the “from” Location.
It imply that I only consider the where the “to” Location is a reloading spot.

Currently, I only consider the Depot Location as needing a time shift in the case where the route is at the first loading operation in direct sequence.

To penalize multiple reloading, it seems that I need to apply an additional cost, similar to fix cost, in order to orient the resolution to explore effectively good solutions.

The next steps, will be to :

  • Apply this not only to the depot Location
  • consider a time shift dependent from the location & the vehicle. Currently, it is only vehicle dependent.

Edit : The penalize reloading cost doesn’t seems to work by editing the getTransportCost function.
Instead, the SoftActivityConstraint with the ObjectiveFunction works like a charm

1 Like