jsprit
jsprit copied to clipboard
graphhopper
Softbounds for TimeWindows
Hello,
I've implemented a Softbounds feature quite deeply. Does it make sense, or is a softConstraint enough ?
Hi @braktar, Thanks a lot for your pull request 👍 . Would you mind to explain a bit what you did? What is your reasoning for this?
I asked since this is a pull request with significant changes. Therefore, I would prefer to discuss the underlying idea of your approach first to really understand what you did.
I based it on the purpose of He Huang https://groups.google.com/forum/#!searchin/jsprit-mailing-list/He$20Huang/jsprit-mailing-list/CVjcp3KpLIM/L4yOZR8JCwAJ
But I was wanting to go a bit deeper, with a follow of the cost calculation all along the resolution.
So the main idea is that a soft TimeWindow is an extension of the current one, but with two new bounds which are within the range defined by the two olds. This interpretation of soft TimeWindows is flexible is the way it doesn't break the mechanisms already in place, and allow to have soft bounds on lower bound, upper bound or both. I make it optional, so in case the problem have no soft TimeWindow, the impact on the solve time is unisignificant.
Then, I redefined the naming for this : HardStart - SoftStart - SoftEnd - HardEnd [ -- [ --- ] - ]
The associated costs are depending on the vehicleType
Ok. Understood. How do you consider soft bounds in the insertion process? Lets assume, you want to insert k between i and j then the insertion costs are basically delta_c = c(i,k) + c(k,j) - c(i,j). Thus, one can calculate it just by looking at i,j,k. If you deal with soft bounds, then delta_c = c(i,k) + c(k,j) - c(i,j) + epsilon where epsilon covers additional costs that emerge from postponing the start time of subsequent activities, i.e. activities after j. Do you consider this epsilon in your approach?
I am also wondering whether we really require this explicit representation of soft bounds. Cant we just consider soft costs by implementing activity costs? For example, you can define soft bounds for each activity and implement this
public double getActivityCost(TourActivity tourAct, double arrivalTime, Driver driver, Vehicle vehicle){
if arrivalTime is within softbounds of tourAct then no additional costs
else penalyze
}
You point some weakness of my current implementation. I should have another look to this.
In the insertion context, the soft bound cost calculation should be : c(i,k) (the softCost with the new inserted point, which include the cost calculation until this end of the route) VS c(i,j) (the softCost without the new point, which include the cost calculation until this end of the route)
An estimated cost epsilon could be usefull in order to recalculate each time the propagation of constraint.
To calculate a soft bound cost, you need every activity visited next to the focused activity.
Yes, you are correct. And this can be time consuming. So we might think about a good estimation function f(epsilon) that indicates the expected additional costs so that we do not need to loop through the entire route for each and every insertion.
If we had such a function, then I assume that we could model soft bounds just by reimplementing VehicleRoutingActivityCosts where we put the soft bounds to, and by implementing SoftActivityCosts where we put f(epsilon) to. Maybe I oversee smth. here?
The logic used by the soft bounds is time consuming. I cannot recommand to use it. We don't use jsprit in production on our side and didn't bring any improvement to this feature since.
The PR is still open mostly to give hints to anyone which would like to follow the track and bring a proper softbounds implementation.
Hello @braktar, thanks a lot for your work. But I have a question about the method getcost() in the class LocalActivityInsertionCostsCalculator, 【 if (isEnd(nextAct) && !toDepot(iFacts.getNewVehicle())) return tp_costs_prevAct_newAct】I think 【return tp_costs_prevAct_newAct+soft_cost_newAct 】 is more better,do you think so?
