GraphHopper.com | Forum | GitHub | Maps | Blog

Minimising number of vehicles used


#1

Hi Folks

I’m working on ideas to use the minimum number of vehicles to satisfy a days load. I have two key thoughts on approaches and would like the benefit of you folk who undoubtedly have considered this issue.

Proposal 1.
Use a soft route constraint to “encourage” consolidation of delivery jobs onto vehicles that already have jobs. This would return a favourable score if the vehicle proposed already has delivery jobs on it or a less favourable score if the vehicle proposed does not yet have delivery any jobs assigned to it. My understanding is that, being a soft constraint, a less favourable score will not prevent the job being allocated if that is the only solution.

Proposal 2.
Run the solution several times in a “binary search” manner using various vehicle numbers until the minimum number of vehicles used with no unallocated delivery jobs. This means that if we have say 10 vehicles we run the solution with 5 vehicles and see if there are any unallocated jobs. If there are unallocated job we run it again with 7, or, if there were no unallocated job we run it again with 3. We repeat this until we get the lowest number of vehicles required. In theory the maximum number of iterations would be about 10 regardless of the number of trucks - but understanding that the variables are not linear.

Proposal 3.
Something you suggest that I smack my forehead and go “Duh. of course”.

Could Proposal 1 be as simple as:
public class MinimiseFleetUsage implements SoftRouteConstraint {
private final Integer LIKE = 0;
private final Integer DONT_LIKE = 1;

private Map<String,String> map = null;

public MinimiseFleetUsage(Map<String,String> map) {
Utils.LOGGER.log(Level.INFO, "Initialising Soft Route Constraint for to minimise fleet size");
    this.map = map;
}
@Override
public double getCosts(JobInsertionContext insertionContext) {
	return insertionContext.getRoute().getActivities().size() > 0 ? LIKE : DONT_LIKE;
}

}

kind regards
Grant


Draw backs of using Infinite Fleet Size
#2

related post: your proposal 1 seems doing the same thing as fixed cost, and your proposal 2 seems doing what Stefan was suggesting in the post.


#3

That was a great article He. Thanks for pointing it out.


#4

Is there optimal solution for this problem?