GraphHopper.com | Forum | GitHub | Maps | Blog

Maximum trip distance constraint


#21

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


When vehicle switch is allowed, constraints and cost calculators might need to take it into account
Returning non-optimal solution when vehicle start/end locations are not the same
#22

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.


#23

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.


#24

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


#25

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?


#26

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?


#27

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?


#28

setAllowVehicleSwitch()?

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


#29

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?


#30

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.


#31

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


#32

Hi @stefan,

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

Best regards,
He


#33

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.


#34

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?


#35

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.


#36

Do we need to do step 2 after every insertion?

I’m doing as follow:

  1. after insertion calculate the route distance for the route and its corresponding vehicle and then call putRouteState for that route and that vehicle only.
  2. During next insertion if this gives null then calculate route distance of that route and new vehicle and call putRouteState for that route and that vehicle only.

try { if (vehicleDependentRouteStateMap.containsKey(route)) { state = type.cast(vehicleDependentRouteStateMap.get(route)[vehicle.getVehicleTypeIdentifier().getIndex()][stateId.getIndex()]); if (state == null){ vehicleDependentrouteActivityVisitor.visit(route,vehicle); state = type.cast(vehicleDependentRouteStateMap.get(route)[vehicle.getVehicleTypeIdentifier().getIndex()][stateId.getIndex()]); } } } catch (ClassCastException e) { throw getClassCastException(e, stateId, type.toString(), vehicleDependentRouteStateMap.get(route)[vehicle.getVehicleTypeIdentifier().getIndex()][stateId.getIndex()].getClass().toString()); } } return state;

Does it make sense?


#37

What exactly do you mean by “During next insertion”? If you mean in the constraint, then it should not be this way, because we would like to avoid looping through activities in the constraint.

What I have in mind is that, in your step 1 (which is in the state updater), you do the calculation not only for the corresponding vehicle, but for all the vehicles in vrp.getVehicles().

Note that, this time, you do not start from route.getStart().getLocation() and route.getStart().getEndTime() any more. Instead, you start from vehicle.getStartLocation() and vehicle.getEarliestDeparture().

Also when looping through the activities in the route, you cannot use activity.getEndTime() any more. Instead, you need to calculate it with vrp.getTransportCosts(). Note that there is a small issue here: when getting transport time, it requires driver. It is not clear what driver should be used here. I am using NoDriver, but it could be problematic if the travel time/cost is driver-dependent (which it is not in your case, though).


#38

driver is never used currently, thus, do not care about drivers.
I aggree with He. You need to calculate distance for all vehicles resulting in different route distances, e.g. that differ in start location. For services it is easy then, just check whether

distance(route,newVehicle) + additionalDistance(newAct,newVehicle) <= maxDistance(newVehicle).

It is more difficult for shipments. Here you need to figure out whether newAct is pickup or delivery.
If pickup then it is similar to the above, just check whether

distance(route,newVehicle) + additionalDistance(newPickupAct,newVehicle) <= maxDistance(newVehicle).

If delivery, you need to check whether

distance(route,newVehicle) + additionalDistance(correspondingPickupAct,newVehicle) + additionalDistance(newDeliveryAct,newVehicle) <= maxDistance(newVehicle)

When it comes to distance(route,newVehicle) this is what you need to update once a route has changed for every available vehicle, e.g. after each insertion.

EDIT: As He mentioned, all information you can retrieve directly from prevAct or nextAct refer to the current/old route, i.e. context.getRoute() along with vehicle and start times. Thus, if you allow that an idle vehicle (newVehicle != context.getRoute().getVehicle()) can overtake the entire route, you cannot use all information from the old route anymore.


#39

I agree with you @jie31best, @stefan;

I’m suggesting that rather than calculating distances for all the vehicles for a given route after insertion and saving in the state manager, we can do it on the go while checking constraint.

Let’s say our saved states are stored in map as follows:
vehicleDependentState[route] [vehicleId] [StateId] = distance

Now after first insertion we have route:

Vehicle : V3
Route: Start@loc3 - pickup_P2@ loc3 - deliver_P2 @loc2 - End@loc3

Hence we store distance state for only vehicle V3.

Now for constraint we calculate distance as:
Double routeDistance = stateManager.getRouteState(context.getRoute(), context.getNewVehicle(), distanceStateId, Double.class);

If for new vehicle distance state is not present, we calculate it and save it in vehicleDependentState.

This way we won’t have to calculate route distance for all the vehicles. It will be calculated only when a vehicle is switched and stored to avoid looping.


#40

Hi @stefan, @jie31best,

I have made a pull request with my implementation. It worked for my test cases.