Approach to achieve minimum number of vehicles

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

  1. Normalise all distances such that their final values will be in between 0 to 1
  2. Keep fix cost for each vehicle >> 1
  3. 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;


Everything you’ve suggested is already accounted for in the algorithm. In fact, people can sometimes be frustrated that the solution does not use all of the vehicles You can see from the links from Stefan in this post, as only one example, of how it’s based on academic research.

Unassigned jobs are given huge penalties. Nothing is left unassigned if it can be reasonably accommodated by any vehicle.

Normalisation of any parameter doesn’t make sense to me. It would not affect convergence, and it would require some abstract thinking to put man-hour cost and fuel cost on the same plane to converge. I’d rather it be in units I can define and understand.

Is there something specific happening with your solution that caused you to raise this?