Hi,
I’m trying to solve a problem where I have to optimize deliveries of 30 days but duration of a single trip can not be more than 2 days. i.e. A truck must return to initial location after maximum of 2 days after star of its trip.
I’m aware that I have to add constraint using state updater and hard activity constraint, but any hint about how to start will be appreciated.
Hi @Bhoumik_Shah,
I might not fully understand your problem, but does VehicleImpl/Builder/setLatestArrival work for you?
Best regards,
He
Hi @jie31best,
Thanks for your reply.
This method defines earliest start time and latest arrival time.
But I want to a constraint such that,
startTimeofFirstActivity - EndTimeofLastActivity <= MaximumDuration
i.e: I want to constraint duration between two activities.
Hi @Bhoumik_Shah,
In this case, what you need is a hard activity constraint, in which you need to calculate the following:
the delay in the end time of nextAct - you can check here to see how it is calculated;
the total amount of waiting time at all subsequent activities after nextAct - here is how it is obtained thanks to the internal state FUTURE_WAITING;
if (1) is greater than (2), meaning the insertion of newAct at the current position will lead to an increase in the trip duration of the current route, then you need to further calculate the following:
Then the new trip duration would be (3) + (1) - (2), and you check it against MaximumDuration.
Make sure to consider all possible situations, such as
nextAct instanceof End
etc.
Best regards,
He
Hi @jie31best,
I did exactly what you said and implemented using code below
public class maxTripDurationConstraint {
static class DurationConstraint implements HardActivityConstraint {
private final StateManager stateManager;
private final double maxDuration;
private final VehicleRoutingTransportCostsMatrix costMatrix;
DurationConstraint(double maxDuration, StateManager stateManager, VehicleRoutingTransportCostsMatrix transportCosts) {
this.maxDuration = maxDuration;
this.costMatrix = transportCosts;
this.stateManager = stateManager;
}
public ConstraintsStatus fulfilled(JobInsertionContext context, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double v) {
Double newAct_arrTime = prevAct.getEndTime() + costMatrix.getTransportTime(prevAct.getLocation(), newAct.getLocation(), prevAct.getEndTime(), context.getRoute().getDriver(), context.getRoute().getVehicle());
Double newAct_endTime = Math.max(newAct_arrTime, newAct.getTheoreticalEarliestOperationStartTime()) + newAct.getOperationTime();
Double nextAct_arrTime = newAct_endTime + costMatrix.getTransportTime(newAct.getLocation(), nextAct.getLocation(), prevAct.getEndTime(), context.getRoute().getDriver(), context.getRoute().getVehicle());
Double endTime_nextAct_new = Math.max(nextAct_arrTime, nextAct.getTheoreticalEarliestOperationStartTime()) + nextAct.getOperationTime();
Double endTime_nextAct_old = nextAct.getEndTime();
Double endTimeDelay_nextAct = Math.max(0, endTime_nextAct_new - endTime_nextAct_old);
Double oldDuration = context.getRoute().getEnd().getArrTime() - context.getRoute().getStart().getEndTime();
if (nextAct instanceof End) {
Double newDuration = oldDuration + endTimeDelay_nextAct;
if (newDuration > this.maxDuration) return ConstraintsStatus.NOT_FULFILLED;
else return ConstraintsStatus.FULFILLED;
} else {
Double futureWaiting = stateManager.getActivityState(nextAct, context.getRoute().getVehicle(), InternalStates.FUTURE_WAITING, Double.class);
if (futureWaiting == null) futureWaiting = 0.;
if (endTimeDelay_nextAct > futureWaiting) {
Double newDuration = oldDuration + endTimeDelay_nextAct - futureWaiting;
if (newDuration > this.maxDuration) return ConstraintsStatus.NOT_FULFILLED;
else return ConstraintsStatus.FULFILLED;
} else return ConstraintsStatus.FULFILLED;
}
}
}
}
and
{
StateManager stateManager = new StateManager(problem);
stateManager.updateSkillStates();
ConstraintManager constraintManager = new ConstraintManager(problem, stateManager);
constraintManager.addSkillsConstraint();
constraintManager.addConstraint(new maxTripDurationConstraint.DurationConstraint(maxDuration, stateManager, costMatrix), ConstraintManager.Priority.CRITICAL);
VehicleRoutingAlgorithm vra = Jsprit.Builder.newInstance(problem).addCoreStateAndConstraintStuff(true).setStateAndConstraintManager(stateManager,constraintManager).buildAlgorithm();
}
Still I’m getting trips with duration higher than maxDuration. Can you help me with it?
Hi @Bhoumik_Shah,
Please kindly find below the code I implement the maxRouteDurationConstraint:
private static class maxRouteDurationConstraint implements HardActivityConstraint {
private final StateManager stateManager;
private final double maxRouteDuration;
private final VehicleRoutingTransportCosts routingCosts;
public maxRouteDurationConstraint(double maxRouteDuration, StateManager stateManager, VehicleRoutingTransportCosts routingCosts) {
this.maxRouteDuration = maxRouteDuration;
this.routingCosts = routingCosts;
this.stateManager = stateManager;
}
@Override
public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double depTimeAtPrevAct) {
Double oldDuration = iFacts.getRoute().getEnd().getArrTime() - iFacts.getRoute().getStart().getEndTime();
if (oldDuration > this.maxRouteDuration)
return ConstraintsStatus.NOT_FULFILLED_BREAK;
double tp_time_prevAct_newAct = this.routingCosts.getTransportTime(prevAct.getLocation(), newAct.getLocation(), depTimeAtPrevAct, iFacts.getNewDriver(), iFacts.getNewVehicle());
double newAct_arrTime = depTimeAtPrevAct + tp_time_prevAct_newAct;
double newAct_endTime = CalculationUtils.getActivityEndTime(newAct_arrTime, newAct);
double routeDurationIncrease;
if (nextAct instanceof End && !iFacts.getNewVehicle().isReturnToDepot()) {
routeDurationIncrease = newAct_endTime - depTimeAtPrevAct;
}
else {
double tp_time_newAct_nextAct = this.routingCosts.getTransportTime(newAct.getLocation(), nextAct.getLocation(), newAct_endTime, iFacts.getNewDriver(), iFacts.getNewVehicle());
double nextAct_arrTime = newAct_endTime + tp_time_newAct_nextAct;
double endTime_nextAct_new = CalculationUtils.getActivityEndTime(nextAct_arrTime, nextAct);
double arrTime_nextAct = depTimeAtPrevAct + this.routingCosts.getTransportTime(prevAct.getLocation(), nextAct.getLocation(), prevAct.getEndTime(), iFacts.getRoute().getDriver(), iFacts.getRoute().getVehicle());
double endTime_nextAct_old = CalculationUtils.getActivityEndTime(arrTime_nextAct, nextAct);
double endTimeDelay_nextAct = Math.max(0.0D, endTime_nextAct_new - endTime_nextAct_old);
Double futureWaiting = this.stateManager.getActivityState(nextAct, iFacts.getRoute().getVehicle(), InternalStates.FUTURE_WAITING, Double.class);
if(futureWaiting == null) {
futureWaiting = Double.valueOf(0.0D);
}
routeDurationIncrease = Math.max(0, endTimeDelay_nextAct - futureWaiting);
}
Double newDuration = oldDuration + routeDurationIncrease;
if (newDuration > this.maxRouteDuration)
return ConstraintsStatus.NOT_FULFILLED;
else
return ConstraintsStatus.FULFILLED;
}
}
I tested it on a small test case and it worked fine.
Note that the way trip duration is defined in the code is different from what you said in an earlier comment, i.e., [quote=“Bhoumik_Shah, post:5, topic:758”]
Double oldDuration = context.getRoute().getEnd().getArrTime() - context.getRoute().getStart().getEndTime();
[/quote] is not the same as [quote=“Bhoumik_Shah, post:3, topic:758”]
startTimeofFirstActivity - EndTimeofLastActivity
[/quote] (well, this should be reversed, but you get the idea)
For the definition of trip duration as in the code, I think VehicleImpl/Builder/setLatestArrival should work - just define the vehicle latest arrival time = earliest start time + MaximumDuration.
Best regards,
He
Hi @jie31best,
Thanks for your implementation, it is working. I’m trying to figure out what was wrong with mine.
I know we can implement the above code by defining latest arrival time = earliest start time + MaximumDuration,
I was just testing my code on simpler implementation of trip duration.
The actual implementation would be ( Arrival time at final depot - Arrival Time at first delivery point + Travel time between depot and first delivery point ).
As jspirit considers starting time for each vehicle as Earliest start time of vehicle, but when we optimize routes for longer duration (i.e. 1 month) some vehicle waits for many days in depot before actually starting the trip. Which unnecessarily increases the waiting time cost. I will be modifying cost function so as to implement this different definition of trip duration.
Is there a way to modify it in core so as to get {Route().getStart().getEndTime();} equal to (Arrival Time at first delivery point - Travel time between depot and first delivery point ) without disturbing any other functionality of core?
Hi @Bhoumik_Shah,
I did some more tests and found a bug in the calculation of oldDuration - it’d be changed to the following:
Double oldDuration;
if (iFacts.getRoute().isEmpty())
oldDuration = 0.0;
else
oldDuration = iFacts.getRoute().getEnd().getArrTime() - iFacts.getRoute().getStart().getEndTime();
Best regards,
He
Hi @Bhoumik_Shah,
Please kindly find attached my implementation of what you want(ed).
It includes a state updater which calculates the so-called “real” start time for each route, a hard activity constraint in which it calculates 1) the shift in the route end time and 2) the shift in the “real” route start time (this only happens when prevAct is Start) so as to obtain the change in the route duration, and a small test case.
Note that this is nowhere near the variable (or dynamic, or flexible, whatever you call it) route departure time. And because of that, it could leads to non-optimal result, as shown in the test: the result will be s2-s4-s1-s3, and cost is 3, while the optimal result (suppose we have variable route departure time) will be s4-s2-s1-s3 and cost is 1.
Moreover, sometimes it could lead to unassigned jobs. For example, if you change the time window start time of s2 to 18, then you will get s4 unassigned. And this should not happen if we have variable route departure time.
Please kindly let me know what you think. Thanks.
Best regards,
He
JspritTestMaxRouteDuration.java (5.1 KB)
MaxRouteDurationConstraint.java (4.7 KB)
RouteRealStartTimeMemorizer.java (2.3 KB)
Hi anyone who is concerned,
Unfortunately there is a bug that the implemented constraint does not work well for shipments.
A small test cast is like the following:
Shipment s1 = Shipment.Builder.newInstance("s1")
.setPickupLocation(Location.newInstance(0, 0))
.setPickupTimeWindow(TimeWindow.newInstance(18, 18))
.setDeliveryLocation(Location.newInstance(0, 0))
.setDeliveryTimeWindow(TimeWindow.newInstance(18, 100))
.build();
Shipment s2 = Shipment.Builder.newInstance("s2")
.setPickupLocation(Location.newInstance(0, 0))
.setPickupTimeWindow(TimeWindow.newInstance(15, 15))
.setDeliveryLocation(Location.newInstance(0, 0))
.setDeliveryTimeWindow(TimeWindow.newInstance(21, 100))
.build();
When maxRouteDuration is set as 3, obviously s2 should be unassigned. However, the implemented constraint will allow it to be served.
The reason is that when the DeliverShipment of a shipment (say, that of s2) is to be inserted, the route start and end times are not updated because the shipment is not inserted yet, so they remain as before the PickupShipment is inserted.
Therefore, what needs to be added to the implementation is that, when (newAct instanceof DeliverShipment), the change in the route duration as a result of the insertion of the PickupShipment needs to be calculated too. It seems iFacts.getRelatedActivityContext() can help with it so that I don’t need to loop over (all) the activities.
Please kindly let me know what you think. Thanks.
Best regards,
He
Hi there,
Unfortunately it seems I cannot avoid looping over some (if not all) activities when newAct instanceof DeliverShipment.
The issue is not about calculating the change in the route duration as a result of the insertion of the corresponding PickupShipment. Instead, it is about the insertion of the DeliverShipment (i.e., newAct) itself. When I try to obtain the future waiting of nextAct using the internal state:
Double futureWaiting = this.stateManager.getActivityState(
nextAct, iFacts.getRoute().getVehicle(),
InternalStates.FUTURE_WAITING, Double.class);
it is the value before PickupShipment is inserted. But what I need is the value after PickupShipment is inserted, because the endTimeDelay_nextAct, which is calculated based on depTimeAtPrevAct, is the value after PickupShipment is inserted. It means that, in the calculation, there is a gap which is the change in the end time of nextAct (or the future waiting of it) caused by the insertion of PickupShipment.
However, it seems there is no easy way to get the new (after insertion of PickupShipment) future waiting of nextAct or the old (before insertion of PickupShipment) end time of nextAct. I tried to use nextAct.getEndTime() or calculate from nextAct.getArrTime(), but it seems it does not work. Maybe I’d try to calculate from prevAct.getEndTime()? But then it will get even more complicated, because I might need to distinguish whether prevAct is the corresponding PickupShipment.
If there is indeed no easy way to get that, it seems I will have to loop over the activities in the route.
@stefan what do you think? Please kindly let me know your comments. Meanwhile I wonder if LocalActivityInsertionCostsCalculator should also cater for this?
Best regards,
He
Hi He,
I went through your constraint classes. Thank you very much for your input.
We need to avoid looping through the entire route there. For bigger problems, it is way too slow. I have some ideas to avoid this, but unfortunately not much time to implement. If a route changed, we need to loop 1x forward and 1x backward to gather enough information. The forward loop is to determine the slack time for each activity (ignoring for now the slack time for all other activities). The second backward loop is to determine the min slack time at each activitiy, i.e. the max time nexAct can be shifted forward taking into account the slack time of all other activities. I think it should work and I will implement it once I find some time.
Best,
Stefan
Hi Stefan,
Thanks for your comments. I understand and agree that we need to avoid looping through activities.
For this particular constraint (max route duration constraint), I think we can achieve that. I realize that actually nextAct.getEndTime() can be used to obtain the “old” end time of nextAct, and we will need to cater for the case (nextAct instanceOf End). It can also be calculated from prevAct.getEndTime(), and this time we need to cater for the case prevAct is the corresponding PickupShipment.
For the other constraint (shipment max duration constraint), I am not sure. Do you think your proposed approach can work for that?
Best regards,
He
Hi He, I think that the approach can be used to model this max duration feature. Maybe I am wrong but I am quite confident ;). Once I am back from holidays I will elaborate it further …
Best, Stefan
Oh cool. Could you please elaborate a bit more?
There is an internal state TIME_SLACK but it seems it is not used anywhere?
With the two slack time states, will jsprit be closer to being able to model variable departure time?
Have a good time and enjoy your holidays (if it is not over yet). 
Best regards,
He
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,
Cool, thanks a lot! I will take a look and let you know.
Just to clarify: the new branch is for the max in vehicle time constraint, not the constraint discussed in this post (max route duration). Sorry for any confusion.
Best regards,
He
Hi He,
Correct, it is max in vehicle time constraint.
Best,
Stefan
Hi Stefan,
Since we’ve understood that it is problematic to call states in constraints when newAct is a DeliverShipment due to the fact that the states are not updated when pickupShipment insertion position is determined, I think it is time to get back to this post. Although later I was able to get around it for this particular constraint, I still have the same question as at the end of the post:
[quote=“jie31best, post:11, topic:758”] I wonder if LocalActivityInsertionCostsCalculator should also cater for this?
[/quote]
Please let me know what you think. Thanks.
Best regards,
He