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.
You assumed a static travel distance, which might be fine for now, but I suppose a constraint here should be able to handle general cases. I guess it will require to add more states: activity vehicle-dependent arrival times, yet it might be a bit tricky due to the pickup shipment issue;
Do you think we need to handle the case when actAfterPickup is End?
When actBeforePickup is Start, I don’t think we should set it to iFacts.getRoute().getStart(), because the new vehicle start location and departure time could be different from those of the route start;
When it comes to the generalized/extended job definition (a job is a list of activities), I suppose we cannot handle the pickup shipment issue in this way if(newAct instanceof DeliverShipment){} any more?
thats correct. if the vehicle does not need to return to depot then additional distance of pickup act is not calculated correctly
also correct
What do you mean here?
I do not think that this is an issue here. It is not maxTimeOrDistance of job i InVehicle but related to overall distance. Why do you think it is an issue?
Does that mean we still need to differentiate between Pickup and ShipmentPickup? Or what is your suggestion here?
Thanks a lot for your input. Really nice :).
Best,
Stefan
Please find below clarifications of my questions 4-6, but let me try to define what I have been calling the pickup shipment issue first:
When a job is a list of N activities, and when you are evaluating the insertion of the i-th activity. What you have in the states are what the world is like before the insertion of the whole job, and thus you will need to calculate the impact of the insertion of all the preceding i-1 activities in the job. Put it in the context of Shipment, when you are evaluating the insertion of the DeliverShipment, you need to calculate the impact of the insertion of the corresponding PickupShipment. Thus I call it the pickup shipment issue.
What I was saying is that, in some other constraints or cost calculators, when newAct is a DeliverShipment, we might also need to consider the impact of the insertion of the corresponding PickupShipment. Not sure if the two classes I put there as examples require that, though.
Meanwhile, I wonder if those two classes will need to consider the different vehicle issue? For example, in both classes, there is calculation of tp_costs_prevAct_nextAct when the route is not empty, in which you used prevAct.getLocation(), nextAct.getLocation() and iFacts.getRoute().getVehicle(). Not sure if that could be problematic, because, for example, prevAct could be Start and its location would be the start location of the new vehicle rather than that of the route?
I think what we were suggesting is that, for each state you have in the state manager (which could include the states in VehicleDependentTraveledDistance for this max distance constraint, and those in UpdateMaxTimeInVehicle for the max time in vechile constraint), you make a corresponding new one, and then, in the ShipmentInsertionCalculator, before the deliverShipmentLoop, update it taking into account the “insertion” of the pickupShipment, and then use it in the evaluation of the deliverShipment insertion. The update part will need to loop through all the activities in the route, but will keep the same complexity as current.
In this way, the impact of the insertion of the PickupShipment is already considered in the state, and thus will not require calculating it in the constraint (e.g., additionalDistanceOfPickup).
I think this is not only about Pickup or PickupShipment, but about the general case. When you are evaluating the insertion of the i-th activity, you will need to calculate the impact of the insertion of all the preceding i-1 activities in the job. It seems to me that it will be overwhelming.
What I have in mind is to go with the way as suggested in 5). For each state, you make an array, the length of which is the maximum number of activities in a job. Then in the JobInsertionCaculator (which I suppose would be a generalization of ServiceInsertionCalculator and ShipmentInsertionCalculator), you have a N-layer loop to evaluate the insertion of the whole job, where N is the number of activities in the job. In the i-th layer you evaluate the insertion of the i-th activity in the job, and, before that layer, you update the i-th element in the array for each state and use it in the i-th layer loop. Note that the 1st element in the array for each state is what we already have and updated in the state updaters and thus is not updated in the JobInsertionCaculator.
Hi He,
Thanks for your answers. Let me read this carefully over the weekend and then I ll come back with some question regarding your proposal of memorizing states.
Thanks again for your input.
Have nice weekend,
Stefan
If prevAct is Start shouldn’t we use double distancePrevAct2NewAct = distanceCalculator.getDistance(iFacts.getNewVehicle().getStartLocation(), newAct.getLocation(), iFacts.getNewDepTime(), iFacts.getNewVehicle());
Similarly if nextAct is end.
What if in case of shipment delivery prevAct is not actual previous activity?
To give an example, Let’s say initial route is Start-A-B-C-End
In this route we first insert pickUpShipment§ with insertion index 1,
hence actual route will be Start-A-P-B-C-End
Now if while inserting dropShipment(D) we have prevAct = A and nextAct=B.
In this case prevAct is A but actual previous activity is P.
Hence we need to consider effect of insertion of related activities on route as well.
Hi @Bhoumik_Shah, Thanks for your ideas/doubts. The easiest way here would be to find concrete examples where the constraint fails. Even better if you could do it in a unit test. If not, your example would also be fine for us.
Best,
Stefan
I have a question about the implementation of the VehicleDependentTraveledDistance class.
Why is it classifying two vehicles with the same vehicleTypeIdentifier as equals?
Since it doesn’t take into account the vehicle’s id, wouldn’t two vehicles that are similar sans the id would be evaluated as equal, taking one into account and tossing the other? What is the benefit of this approach?
To achieve this in minimal changes, You can use “userData” variable from “Vehicle” to store the max distance and make the constraint to use the max distance value from userData instead of the Map.
Or you can always write your own implementation of Vehicle and Constraint.
