In the course of some testing, I have stumbled on something I haven’t really tested before; large disparity between available vehicles and the number of jobs. In this case, oversupply of vehicles. It seems to me that something is highly sub-optimal in these (fabricated) cases that might point at a way to trim some fat so I was interested if this is already addressed in a way I’m unaware of, or people’s opinion on this.
In my problem specification, I have 195 jobs. I know they can be served by 8 vehicles, all of the same type and working the same hours. It’s a real-road, asymmetric matrix. I don’t think the exact jobs themselves have any bearing on what happens. Algorithm setup is simple:
VehicleRoutingAlgorithm vra = Jsprit.Builder.newInstance(vrp) .setProperty(Jsprit.Strategy.CLUSTER_REGRET, "0.") .setProperty(Jsprit.Strategy.RADIAL_REGRET, "0.") .setProperty(Jsprit.Strategy.RANDOM_REGRET, "0.") .setProperty(Jsprit.Strategy.WORST_REGRET, "0.") .setProperty(Jsprit.Strategy.CLUSTER_BEST, "1.") .setProperty(Jsprit.Strategy.RADIAL_BEST, "0." ) .setProperty(Jsprit.Strategy.RANDOM_BEST, "1.") .setProperty(Parameter.THREADS,"3") .setProperty(Jsprit.Parameter.FIXED_COST_PARAM,"0.5") .buildAlgorithm();
100 iterations on an old laptop, average of 3 runs at each point. JSprit 1.7. I tested solution time against the number of specified vehicles, in addition to whether or not the fleet was made
FINITE. In the case of
INFINITE, I had still defined a fixed number of vehicles anyway of the same type (which, I think, reinforces the point even more).
All give exactly the same routing output. This looks wonky; problem complexity has linear (? if I find time to test, it might even hint at polynomial) dependency on the number of available vehicles in an almost 1:1 ratio. No vehicle swaps here are valid between assigned and unassigned vehicles; all additional time on each iteration is completely wasted because all vehicles are, technically, identical. The fact that
INFINITE fleet scales in the same way indicates to me that no effort is made to collapse
vehicleType instances into a single vehicle for consideration.
The argument against this is obviously that vehicles of the same type could be operated on different shift patterns, different skills etc., so collapsing consideration to just one representative vehicle for each type for swaps is not possible.
However, I wonder if there’s scope to collapse vehicle+driver combinations into something like decks of cards so that only one candidate of each combo is available at a time? On small problems this might not be significant, but on big problems this could be huge, especially for more generic problems where the number of combinations is significantly fewer than the number of physical vehicles.