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,
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;
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.
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.
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:
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.
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.
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
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.
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.
after insertion calculate the route distance for the route and its corresponding vehicle and then call putRouteState for that route and that vehicle only.
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;
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).
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
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
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.
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
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.