Hi ,
Thank you for your time and thank you to stefan (and Team) for such great library. Your work makes our life very easy !
I have one suggestion on how can we minimise total number of vehicles and unassigned jobs simultaneously.
I think, first objective of any VRP algorithm should be minimising unassigned jobs and then finding best routes. In the default cost calculator of jsprit, we directly add fixed cost of vehicles and penalise each unassigned jobs by 1% of route cost (code snippet attached below). I find doing this is just not sufficient because behaviour of algorithm depends largely on the actual values of distances and fixed vehicle costs.
Problem : Minimise total number of vehicles and unassigned jobs simultaneously.
Description :
Consider a simple case , where I have only distance costs.
Suppose fixed costs for all the vehicles are very high, say approximately 100 times of typical distance value. In such cases, the default cost equation may tend to keep lot of jobs unassigned even if there is additional unused vehicle with sufficient capacity and time. In this case, cost equation is largely dominated by fix vehicle costs rather then distances.
If distance costs are approximately 100 times of fix costs then fix costs will have very minimal effect. For many practical purpose, this situation will be same as setting fix costs to 0.
Proposed Solution
- Normalise all distances such that their final values will be in between 0 to 1
- Keep fix cost for each vehicle >> 1
- Penalty for all unassigned jobs >> max(fixed cost of all vehicles)
I think this proposed solution will work in both cases and will be able to minimise total number of vehicles and unassigned jobs simultaneously and will also not depend ratio between distance costs to fix costs.
I would like to get suggestions on this proposed approach, any point from library which I did not understand correctly, views on what additional care should be taken while implementing this approach.
Let me know, if any additional clarification is needed.
Default Cost Calculator
public double getCosts(VehicleRoutingProblemSolution solution) {
double c = 0.0;
for (VehicleRoute r : solution.getRoutes()) {
c += stateManager.getRouteState(r, InternalStates.COSTS, Double.class);
c += getFixedCosts(r.getVehicle());
}
c += solution.getUnassignedJobs().size() * c * .1;
return c;
}