Constraint on the time gap between PickupShipment and corresponding DeliverShipment

Hi,

I am trying to implement a constraint to make sure that, for some (if not all) shipments, the time gap between the end time of their PickupShipment and the start time of the corresponding DeliverShipment (or maybe some other definition, such as start-start time gap, or start-end time gap, or end-arrival time gap, etc.) must not exceed some threshold.

This could be practically useful as, for some goods (say, frozen food, fresh fruit/seafood, etc.), the on-the-road time should not exceed some threshold (say, 4 hours).

As far as I see, it requires hard activity constraint and involves two parts:

  1. when newAct is the DeliverShipment of one such shipment, obtain the end time of corresponding PickupShipment via jobInsertionContext.getRelatedActivityContext(), calculate the start time of newAct via prevActDepTime and routingCosts.getTransportTime(), and compare the gap against the threshold.

  2. when the route already serves one (or multiple) such shipment(s), for each of them, calculate the new time gap assuming newAct is inserted, and compare against the threshold.

The second part will be time-consuming, as it will require looping through part of (if not all of) the tourActivity list of the route.

Next step I might want to generalize it to a constraint on the time gap between any two activities (say, a Service and a DeliverShipment), whether they are in the same route or not.

What do you think? Please let me know. Thanks.

Best regards,
He

Would you mind to create a branch called “dynamic-in-vehicle-time” or so and we can both work on a nice solution?

see https://github.com/graphhopper/jsprit/issues/261

I’m part way through this using a HardActivityConstraint.

When I get a DeliverShipment, I have access to the corresponding PickupShipment, but the corresponding PickupShipment activity is not present in the vehicle route.

How do I access the corresponding PickupShipment activity’s insertion point in the vehicle route - that is, where abouts it would appear in the vehicle route? All I can see are previosuly inserted jobs.

Do I need to use a StateManager?

Hi Dave,
You should grab the information directly. Look at this:

cm.addConstraint(new HardActivityConstraint() {
    @Override
    public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
        if(newAct instanceof DeliverShipment){
            TourActivity correspondingPickup = iFacts.getAssociatedActivities().get(0);
            System.out.println("underlying job id of corresponding pickup: " + ((TourActivity.JobActivity)correspondingPickup).getJob().getId());
            System.out.println("underlying job id of delivery: " + ((TourActivity.JobActivity)newAct).getJob().getId());
            System.out.println("related activity of newAct:" + correspondingPickup);
            System.out.println("insertion index of related activity of newAct: " + iFacts.getRelatedActivityContext().getInsertionIndex());
            System.out.println("arr time at related act of newAct: " + iFacts.getRelatedActivityContext().getArrivalTime());
            System.out.println("newAct: " + newAct);
            System.out.println("insertion index of newAct: " + iFacts.getActivityContext().getInsertionIndex());
        }
        return ConstraintsStatus.FULFILLED;
    }
}, ConstraintManager.Priority.CRITICAL);

As I just realized, you cannot use

System.out.println("arr time at newAct: " + iFacts.getActivityContext().getArrivalTime());

additionally even .getActivityContext().getArrivalTime() pretends to give you the arrival time. You need to calculate the arrival time at newAct in your constraint. I will change this.

Note that if underlying job of newAct is a Service, .getAssociatedActivities() only contains newAct. If the underlying jobs is a Shipment, it contains two activities, i.e. pickup and delivery activity.

Best Stefan

Hi Dave and Stefan,

Please kindly find attached my implementation of the shipment max duration constraint and a small test case.

There definitely could be a lot of improvements to be done to the second part of the constraint in many ways, but I did not have time for it recently.

For example, it needs to check only when the newAct is between the PickupShipment and the DeliverShipment of a constrained shipment, otherwise the potential insertion will not increase the duration of that shipment.

Another potential improvement could be to use a state updater to record the arrival/start/end time of the PickupShipment and the DeliverShipment of a constrained shipment, so that it would not need to be calculated in the constraint as it is now and thus could save a lot of time.

Yet, the loop over the tour activities from the newAct till the DeliverShipment cannot be avoided, as (I think) it is required to calculate the new arrival/start/end time of the DeliverShipment.

Please kindly let me know what you think. Thanks.

Best regards,
He

JspritTestShipmentMaxDuration.java (6.0 KB)
ShipmentMaxDurationConstraint.java (6.7 KB)

1 Like

Will check this asap. Thanks a lot, He.

Thanks Stefan.

For clarification - the insertion index is the location in the routes where
the PickupShipment should be placed if this constraint passes, and the
DeliverShipment is always placed between prevAct and nextAct in the
routes. Is this a correct assumption?

For example:
Let ifacts.routes.getActivities = P1, P2, D1, D2. (pickup1, pickup2,
deliver1, deliver2)
PS = pickup shipment, DS = deliver shipment
PrevAct = D1, NextAct = D2.

PS (pickup shipment) is index 1.
DS is always index 0 when I use getInsertionIndex, but this should be
inserted between PrevAct and NextAct anyway.

Would the route I need to test constraint against look like this:
P1, PS, P2, D1, DS, D2?

Correct.

Correct.[quote=“Dave_Hepworth, post:7, topic:836”]
Would the route I need to test constraint against look like this:P1, PS, P2, D1, DS, D2?
[/quote]

Exactly!

Hi,
Look at this.
It is a first version of this maxTimeInVehicle feature. Would be great
if you could try it out and let me know if you get unexpected results.
Note
that maxTimeInVehicle can only be used for Delivery and Shipment.
Pickup and Service is unsupported yet (since making it work for them is
harder than expected )
Best,
Stefan

Hi Stefan,

Regarding your new branch addressing this max in vehicle time constraint, I think Phil raised a valid point. The root cause is that the states are not updated when pickupShipment insertion position is determined.

Assume you have the following route and act start/end times: Start, P1, D1, End (0,10,20,30), where 10 is end time of P1 and 20 is start time of D1. Now you try to insert shipment (P2, D2).

Assume other constraints force the insertion to be Start, P2, P1, D2, D1, End (0, 10, 20, 30, 40, 50), where 10 is end time of P2, 20 is end time of P1, 30 is start time of D2 and 40 is start time of D1. Assuming both shipments have max in vehicle time 20, thus the insertion should be valid.

However, when you try to insert the new shipment, you insert P2 first. P2 is determined to be inserted between Start and P1, and now P1 end time delays to 20, thus the latestStart of D1 needs to update to 40. But it is not. It is still 30. Now you try to insert D2, which will delay D2 start time to 40, which is later than 30, thus the insertion will be disallowed.

At the end of this reply is the code of the example. Meanwhile you need the following line, which together with the priority makes sure that s1 is inserted first.

algorithmBuilder.setProperty(Jsprit.Strategy.RANDOM_BEST, "0.0");

Please let me know what you think. Thanks.

Best regards,
He

   VehicleTypeImpl vehicleType = VehicleTypeImpl.Builder.newInstance("type").build();
    VehicleImpl vehicle = VehicleImpl.Builder.newInstance("veh").setType(vehicleType)
            .setStartLocation(Location.newInstance(0, 0))
            .setReturnToDepot(false)
            .build();
    Shipment shipment1 = Shipment.Builder.newInstance("s1")
            .setPickupLocation(Location.newInstance(0, 0))
            .setDeliveryLocation(Location.newInstance(10, 0))
            .setPickupServiceTime(10)
            .setDeliveryServiceTime(10)
            .addPickupTimeWindow(0, 10)
            .setPriority(1)
            .setMaxTimeInVehicle(20d)
            .build();
    Shipment shipment2 = Shipment.Builder.newInstance("s2")
            .setPickupLocation(Location.newInstance(0, 0))
            .setDeliveryLocation(Location.newInstance(10, 0))
            .setPickupServiceTime(10)
            .setDeliveryServiceTime(10)
            .addPickupTimeWindow(0, 0)
            .addDeliveryTimeWindow(30, 30)
            .setMaxTimeInVehicle(20d)
            .build();
    VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance()
            .addVehicle(vehicle)
            .addJob(shipment1)
            .addJob(shipment2)
            .setFleetSize(VehicleRoutingProblem.FleetSize.FINITE)
            .build();
1 Like

But this is what I calculated in advance. I know that D1 can only be shifted to time x so that the insertion of P2 does not violate (P1,D1) constraint. But maybe I just do not understand your points ;). Therefore, I would suggest that you check it out and try to find cases where the current approach fails. If you find a case then I have it in black and white and can try to improve this.

Ok. I think I now see your point … let me investigate further.

I just improved on this issue further. It might not be optimal yet in terms of computation time, but it should approach optimum in terms of functionality: https://github.com/graphhopper/jsprit/tree/max-time-feature
It is basically an (first) implementation of what you suggested. Thanks @jie31best again.

2 Likes

Hi @stefan,

nice job! :thumbsup:

regarding estimating in-vehicle time of pickups, it seems to me you are just missing the new route end time? if so, I think you just need a state updater for vehicle-dependent route/activity end time and another one for vehicle-dependent future waiting time of each activity, and from there you will be able to calculate the new route end time. if this makes sense, perhaps you can take a look at how I did it in PR #332. :wink:

Best regards,
He

Hello,
I want to use this solution for slightly different purpose to meet “Delivery Before” constraint. In this case, delivery of the shipment should be completed before specific date/time.

I was referring to MaxTimeInVehicle implementation available in 1.7.3-SNAPSHOT. I am getting Null pointer exception in MaxTimeInVehicleConstraint. Looks like constraint is not able to get activity state.

I have 2 shipments, 2 vehicles. Vehicles and pickup locations are same.

at com.graphhopper.jsprit.core.problem.constraint.MaxTimeInVehicleConstraint.fulfilled(MaxTimeInVehicleConstraint.java:110)
at com.graphhopper.jsprit.core.algorithm.recreate.AbstractInsertionCalculator.fulfilled(AbstractInsertionCalculator.java:52)
at com.graphhopper.jsprit.core.algorithm.recreate.ShipmentInsertionCalculator.getInsertionData(ShipmentInsertionCalculator.java:155)

Regards,
Amit

Source code to reproduce the problem,
public class DeliveryBeforeTest {

public static void main(String[] args) {

	Location.Builder locBuilder = Location.Builder.newInstance();
	Coordinate coordinate = Coordinate.newInstance(5, 5);
	locBuilder.setId("VL1").setCoordinate(coordinate);
	Location VL1 = locBuilder.build();

	Location.Builder locBuilder1 = Location.Builder.newInstance();
	Coordinate coordinate1 = Coordinate.newInstance(5, 5);
	locBuilder1.setId("PL1").setCoordinate(coordinate1);
	Location PL1 = locBuilder1.build();

	Location.Builder locBuilder2 = Location.Builder.newInstance();
	Coordinate coordinate2 = Coordinate.newInstance(2, 2);
	locBuilder2.setId("DL1").setCoordinate(coordinate2);
	Location DL1 = locBuilder2.build();

	Location.Builder locBuilder3 = Location.Builder.newInstance();
	Coordinate coordinate3 = Coordinate.newInstance(2, 8);
	locBuilder3.setId("DL2").setCoordinate(coordinate3);
	Location DL2 = locBuilder3.build();

	// All time window units are in milli-seconds
	// Max time in vehice - 30 minutes
	Shipment shipment1 = Shipment.Builder.newInstance("s1").addSizeDimension(0, 1).setPickupLocation(PL1)
			.setDeliveryLocation(DL1).setPickupTimeWindow(new TimeWindow(1506565800000D, 1506574800000D))
			.setPickupServiceTime(2400000).setDeliveryServiceTime(3000000).setMaxTimeInVehicle(1800000L).build();

	// Max time in vehice - No bound
	Shipment shipment2 = Shipment.Builder.newInstance("s2").addSizeDimension(0, 2).setPickupLocation(PL1)
			.setDeliveryLocation(DL2).setPickupTimeWindow(new TimeWindow(1506565800000D, 1506574800000D))
			.setPickupServiceTime(2400000).setDeliveryServiceTime(3000000).setMaxTimeInVehicle(Double.MAX_VALUE)
			.build();

	VehicleTypeImpl.Builder vehicleTypeBuilder1 = VehicleTypeImpl.Builder.newInstance("vehicleType1")
			.addCapacityDimension(0, 3);
	VehicleType vehicleType1 = vehicleTypeBuilder1.build();

	VehicleTypeImpl.Builder vehicleTypeBuilder2 = VehicleTypeImpl.Builder.newInstance("vehicleType2")
			.addCapacityDimension(0, 5);
	VehicleType vehicleType2 = vehicleTypeBuilder2.build();

	VehicleImpl.Builder vehicleBuilder = VehicleImpl.Builder.newInstance("vehicle1");
	vehicleBuilder.setStartLocation(VL1);
	vehicleBuilder.setType(vehicleType1);
	vehicleBuilder.setEarliestStart(0);
	vehicleBuilder.setReturnToDepot(false);
	VehicleImpl vehicle1 = vehicleBuilder.build();

	VehicleImpl.Builder vehicleBuilder2 = VehicleImpl.Builder.newInstance("vehicle2");
	vehicleBuilder2.setStartLocation(VL1);
	vehicleBuilder2.setType(vehicleType2);
	vehicleBuilder2.setEarliestStart(0);
	vehicleBuilder2.setReturnToDepot(false);
	VehicleImpl vehicle2 = vehicleBuilder2.build();

	VehicleRoutingTransportCostsMatrix.Builder costMatrixBuilder = com.graphhopper.jsprit.core.util.VehicleRoutingTransportCostsMatrix.Builder
			.newInstance(true);

	// Distance in meters and travel time in milli-seconds
	costMatrixBuilder.addTransportDistance("PL1", "DL1", 32000);
	costMatrixBuilder.addTransportTime("PL1", "DL1", 5820000);

	costMatrixBuilder.addTransportDistance("PL1", "DL2", 32000);
	costMatrixBuilder.addTransportTime("PL1", "DL2", 5820000);

	costMatrixBuilder.addTransportDistance("DL1", "DL2", 5000);
	costMatrixBuilder.addTransportTime("DL1", "DL2", 300000);

	costMatrixBuilder.addTransportDistance("VL1", "DL1", 32000);
	costMatrixBuilder.addTransportTime("VL1", "DL1", 5820000);

	costMatrixBuilder.addTransportDistance("VL1", "DL2", 32000);
	costMatrixBuilder.addTransportTime("VL1", "DL2", 5820000);

	costMatrixBuilder.addTransportDistance("VL1", "PL1", 0);
	costMatrixBuilder.addTransportTime("VL1", "PL1", 0);

	VehicleRoutingTransportCosts costMatrix = costMatrixBuilder.build();

	VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
	vrpBuilder.addVehicle(vehicle1).addVehicle(vehicle2);

	vrpBuilder.addJob(shipment1).addJob(shipment2);
	VehicleRoutingProblem problem = vrpBuilder.setRoutingCost(costMatrix).build();

	StateManager stateManager = new StateManager(problem);
	ConstraintManager constraintManager = new ConstraintManager(problem, stateManager);

	StateId latestStartId = stateManager.createStateId("latest-start-id");
	stateManager.addStateUpdater(new UpdateMaxTimeInVehicle(stateManager, latestStartId,
			problem.getTransportCosts(), problem.getActivityCosts()));

	constraintManager.addConstraint(new MaxTimeInVehicleConstraint(problem.getTransportCosts(),
			problem.getActivityCosts(), latestStartId, stateManager, problem), ConstraintManager.Priority.CRITICAL);

	VehicleRoutingAlgorithm algorithm = Jsprit.Builder.newInstance(problem)
			.setStateAndConstraintManager(stateManager, constraintManager).buildAlgorithm();

	algorithm.setMaxIterations(500);

	Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();

	VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions);

	SolutionPrinter.print(problem, bestSolution, SolutionPrinter.Print.VERBOSE);
}

}

sorry I might have misunderstood something, but why doesn’t the time window fulfill your requirement?

Hi @jie31best,
I think, Shipment.Builder’s setDeliveryTimeWindow can be used to set delivery time window during which delivery operation can start.
we cannot use this method to ensure that delivery activity gets completed within specified time window.

I tried using setDeliveryTimeWindow to achieve my requirement but it does not work as expected.

Regards,
Amt

but the service time is fixed.

for example, if you want a service to end between 8:00 and 9:00, and the service time is 30 minutes, then you can just define the time window as (7:30, 8:30).

Makes sense. This should should work. I did a wrong calculation. Thanks a lot for the help.

Regards,
Amit