Maximum trip distance constraint

btw, in the following case,

should we set it to 0 or should we use the distance from vehicle start location to its end location (if not open route)?

I think it should be 0.

Consider a case when start location is S and end location is E.

routeDistance == null only in the case when we add first pickUp or first delivery.

First Pickup (P1) :
additionalDistance = SP1 + P1E
hence newRouteDistance = SP1 + P1E

First Delivery (D1) :
it will go inside this loop:
if(context.getRoute().getTourActivities().getActivities().size() == 0)

By the way any idea about why is it not checking this constraint for a case when P2 is delivered by V1 and still we get such route in answer?

Oh,
I just realized it should not be 0.
you are right. It should be distance from vehicle start location to its end location (if not open route).

But as in above case start and end locations are same, it won’t matter.

Hi @Bhoumik_Shah,

I am able to reproduce your case. I will look into it.

Interesting thing is, if you deactivate either one of the two vehicles, you will get expected solution:

  1. if you deactivate v3, both jobs are unassigned;
  2. if you deactivate v1, you will get the solution that you obtained after 2 iterations in your case.

Best regards,
He

Hi @jie31best,

Even I noticed both the above cases.
Also if you add one more vehicle V2 with start and end location as loc_2, it will take 9 iteration, instead of 3 to give an infeasible solution.

Hi @Bhoumik_Shah,

I think the problem lies in the following scenario:

When context.getNewVehicle() - called the new vehicle hereafter - is not the same as context.getRoute().getVehicle() - called the old vehicle hereafter,

  1. when prevAct is Start, assuming nextAct is not End, you calculate the additionalDistance as d1 + d2 - d3, where d1 is the distance from prevAct to newAct, d2 is the distance from newAct to nextAct, and d3 is the distance from prevAct to nextAct. In this case, in d1 you should use the start location of the new vehicle, and in d3 you should use the start location of the old vehicle;

  2. when nextAct is End,

2.1) if both the new vehicle and the old one need to return to depot, then again, in d2, you should use the end location of the new vehicle, and in d3 you should use the end location of the old vehicle;

2.2) if both do not need to return to depot, luckily d1 is enough and we should be all set for this case;

2.3) if the new vehicle needs to return to depot and the old vehicle does not, the additional distance would be d1 + d2, and in d2 you use the end location of the new vehicle;

2.4) if the new vehicle does not need to return to depot and the old one does, the additional distance would be d1 - d3, and in d3 you use the end location of the old vehicle.

Make sense?

@stefan do you think this is related to the bug I reported last time?

Best regards,
He

Hi @jie31best,

That makes sense.
I see your point and I can verify is using debug.
Will let you know if this works once I implement it.

Thanks for your help.

Hi @jie31best,

As per my understanding,

If in a given iteration we get ConstraintsStatus.FULFILLED; the oldVehicle is replaced by newVehicle and Context.associatedActivities are inserted in the route.

In this case shouldn’t we also consider the case when neither prevAct is Start nor nextAct is End?
oldRoute: oldStart - P1 - P2 - D2 - D1 - oldEnd

nNow if I add P3 at index 2
newRoute : newStart - P1 - P2 - P3 - D2 - D1 - newEnd

If that’s true, wouldn’t it be just easier to calculate route length from scratch each time.
i.e: from newStart to associated activities in sequence to newEnd.

Hi @Bhoumik_Shah,

In general we would like to avoid looping through the activities in the constraint, because otherwise it would be time-consuming and not scalable.

However, if the new vehicle and the old vehicle are not the same, and if the distance is dependent on vehicle, I guess we will not have a choice. @stefan what do you think?

Luckily this is not the case in your case. So I guess we would just need to add to the additionalDistance the following part:

newStart-P1 + D1-newEnd - oldStart-P1 - D1-oldEnd 

What do you think?

Best regards,
He

Or how about this:

In the state updater, we do not calculate and memorize the route distance as from the start to the end, but from the first activity location to the last activity location. It seems that it would make the constraint part simpler.

What do you think?

Hi @jie31best,

Yes, In this particular case we won’t have to loop through.
But as we have already made distance as vehicle dependent,

getDistance(Location from, Location to, double departureTime, Vehicle vehicle)

Users using vehicle dependent distances will face lots of difficulties.

I think same difficulties will come in TimeWindow constraint if we use vehicle dependent travel time. How do we tackle that now?

I think that will help in this case.

But it will fail in case of vehicle dependent distances.

Is it possible to make sure that on a route vehicle does not change once we add some nodes on it.

How much that will affect the computation time?

setAllowVehicleSwitch()?

For Jsprit algorithm, it is set via Parameter.VEHICLE_SWITCH.

In the case of vehicle-dependent distance, I would think that it might be a good idea to calculate a route distance for each of the vehicles and create a state for each of them in the state updater. This would be better than to loop through activities in the constraint and calculate the route distance on the fly.

What do you think?

Yes,
It gave expected answer after making Parameter.VEHICLE_SWITCH false.

I need to check effect of this parameter on quality of solution and computation time.

Yes It would be better than looping through. But we have to do the same for other constraints also.
e.g: TimeWindow constriant, Maximum Trip duration constraint etc.

On the other hand if making Parameter.VEHICLE_SWITCH false, does not affect quality of soluton and computation time significantly life will become much easier.

Hi, Thanks for your interesting discussion @Bhoumik_Shah and @jie31best. If you make a pull request with the constraint and updater, I can have a look, we can test it together and merge it in the master if you want.
Best, Stefan

Hi @stefan,

I have a question here: why transport distance is not driver-dependent while transport time and cost could be?

Best regards,
He

Hmm, this is because I thought it is not that important even it might be inconsistent. BTW: Do you think it makes sense to add .getDistance(...) to VehicleRoutingTransportCosts? Since latter is one of the more important interfaces we should be carefull changing it. However, for me it looks as though that distance is almost as important as time is.

Hi @jie31best,

I’m trying to implement vehicle dependent states as mentioned by you.

The state manager remembers states of routes that are created after insertion.

Now consider a route in above case:
Vehicle: V3
Activities: Start@ loc3 - pickupShipment2@ Loc_3 - deliver@ Loc2 - End @ loc3
State = 1000

Now newAct = pickupShipment1 @ loc1
New Vehicle = V1

In this case :
Double routeDistance = stateManager.getRouteState(context.getRoute(), context.getNewVehicle(), distanceStateId, Double.class);

returns null as this gives null.

Should we add state of the route with new vehicle in the state manager at this step?

In your state updater, do you 1) calculate the route distance for the route and its corresponding vehicle and then call putRouteState for that route and that vehicle only; or 2) calculate the route distance for the route and ALL vehicles and call putRouteState for that route and each of the vehicles?

I suspect the former since you get null when calling getRouteState, meaning you did not calculate and putRouteState for V1 for that route (whose vehicle is V3) in the state updater.