Redundant vehicles have significant impact on solution calculation time

jsprit
1

Hi,

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 INFINITE or 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.

Any thoughts?

2

Thanks for analysing. Can we setup an artificial problem so that I can reproduce exactly what you mean here?
Actually, there is smth like a deck of cards. Have a look at the fleet manager (FINITE fleet), it memorizes vehicles that are actually “equal” within the same container working like a stack or a deck of cards. If a specific vehicle type is requested, it just picks a vehicle from the stack (rather than treating all the vehicles in that stack as unique vehicles).

3

Aha ok, then I need to spend some more time focusing on fleetManager implementation. I’m happy to make a concrete example for this but in case I’m going off course here; is this something I am supposed to interact with directly or should fleetManager be implemented without interference from me? I cannot find it used in any examples only in core which makes me think it should be default behaviour? In other words, is it supposed to automatically parse all vehicles added to the problem and generate the stacks?

If it is meant to be default behaviour then I appear to be sidestepping it somehow so I can give an example of that. If it’s not implemented by default for a FINITE fleet, I need to do some more research first in case I’m wasting everyone’s time :slight_smile:

1 Like
4

Can you reproduce this when creating 200 services (size 1) randomly distributed between -100 <= x <= +100 and -100 <= y <= +100. Start creating x1,y1 … x200,y200 successively with

Random rng = new Random(4711);

and n vehicles at 0,0 with a capacity of 25?
This is what I can easily setup here so we play with the exact same vrp.

PS: I d just use Euclidean space.

5

FleetManager is set automatically depending on whether the fleet is finite or infinite. For finite this one is used.

6

Thanks for the clarification. In that case, my data suggests that I am sidestepping this feature in some way. I’ll share a self-contained example based on your requested parameters, so we can see if I’m misusing the library or there’s something else going on.

Please note I’m travelling soon so I might take a few days to get back to you on this.

7

VehicleNumbers.java (3.6 KB)

Ok. The attached code does not exhibit undesired behaviour between 10 and 1000 vehicles. It works exactly as we would both anticipate - runtime is the same. I threw in the parts of the general approach I’m using in my real code. From this I take a few things:

  1. My suggestion is already accommodated by fleetManager, initial post is moot in the broader sense.

  2. It’s less likely (not ruling it out!) that I’m defining my actual problem in an unorthodox way that should be expected to bypass fleetManager

  3. There could be a feature in my setup that can cause fleetManager to fail to function properly in cases that I wouldn’t expect.

Might as well hang fire on testing on your end while I start layering in more features on my side. I’ll report back once I’ve tracked it down. Thanks for your responses.