Minimal vehicle capacity

[pierrethiriet]

In the current vrp-cli, only maximal capacity can be fixed for each vehicle of the fleet In our case, it would be interesting to also set up a minimal load by truck to ensure their good use (e.g for the rented ones). With defaults options, the solvers minimize the number of tours, thus it usually picks up solutions with vehicles at their maximal capacity or close. But, in our configuration, to minimize the driver load (and because it is our organization until low), we use all the cars available. So we set objectives to maximize-tours. It is obviously not optimal from a cost point of view but none the less it is still our strategy for now. But we end up with some trucks not loaded enough. My guess is that a hard constraint on minimal vehicle capacity, would probably solve this issue. Or maybe I miss used some objectives options ? Thanks again for your apps !

[reinterpretcat]

Hi!

Yes, I also think minimal load feature will be useful, but it is not straightforward how to implement it as hard constraint. At the moment, maybe try to use balance-max-load objective as secondary to assign a bit more jobs to 'small' routes from 'bigger' ones. See https://reinterpretcat.github.io/vrp/concepts/pragmatic/problem/objectives.html#work-balance-objectives

[pierrethiriet]

Hi, The objectives mecanism in vrp_cli is indeed quite flexible ! The balance activities objectives seem to help while balance load (not all demands are equal) has a too strong impact on the performance. Note: the color corresponds not to the same vehicle in the example below.

• maximize-tours Total distance: 214km The vehicle in dark blue is only serving one client in the southern area before its end location while it has a large capacity.

• maximize-tours + balance-max-load Total distance: 280km Higher cost in driving distance. The effect of this secondary objective seems too strong with the default parameters. Also, too many vehicles going to the city in the southern area while not necessary

• maximize-tours + balance-activites Total distance: 249km Better, but according to this particular run (each run giving different results), some seem to have too many cars going to the main city, the light, blue, dark blue and red here. I understand that there are not criteria for spatial clustering of the trip, but some gave a better feeling than others while having the same performance.

Aside from the minimal load capacity, I guess I can minimize having too many vehicles in one area by assigning an allowedAreas to one vehicle. But I am not sure about that as this option is a hard constraint while I would still like to let the vehicle to potentially serve some clients along the roads to reach its target area (allowedAreas).

[reinterpretcat]

Have you tried to play with options parameters? It is the way to avoid balancing strictness.

Yes, you can use allowedAreas to restrict vehicles to specific areas, but this is not optimal.

I think the proper solution would be to add extra parameter to maximize-tours which will trigger desired behavior. I would need to think about implementation.

[pierrethiriet]

Thanks for your answer. In a new test with the same options give now different solutions that seem better than the previous one without balancing activities (?). But when balancing activities, the tolerance option seems to help. But I am not sure to understand the threshold one. Increasing the tolerance and keeping the threshold low give good results.

In all cases:

• Primary objective:
  • minimize-unassigned
  • maximize-tours
• Secondary objective:
  • minimize-cost

1. Default - 202km

2. Balance activities (secondary obj) tolerance: 0.05 - threshold: 0.01 (default options) - 244km

3. Balance activities (secondary obj) tolerance: 0.1 - threshold: 0.01 (default options) - 213km

[reinterpretcat]

threshold is described in the docs:

threshold: a target coefficient of variation value which specifies desired minimum balancing level. All values below threshold are considered equal which helps the search algorithm to optimize conflicting objectives.

Essentially, you can use it to limit balancing to some value.

The purpose of tolerance is to allow movement in search space which improves another objective (e.g. cost), but degrades balancing objective a bit.

In a new test with the same options give now different solutions that seem better than the previous one without balancing activities (?)

The search process is a bit non-determenistic, so it might lead to different results for different runs. I did recently some improvements with new search mode (broad/ROSOMAXA), so running longer should bring more stable results across multiple runs.

[pierrethiriet]

Thanks for your answer, and sorry I didn't read properly the documentation (very detailed and helpful by the way). So adjusting both options give mor room for moving the solution along a Pareto frontier (more or less).

A side question: does the order of the objective in the primary set or the secondary set matter? I guess no, but I am not sure as it is an array, so an order can exist.

I am quite interested in your last comment. I am not surprised that heuristic approaches can provide slightly different results. But in my case, the solver stops quite quickly (a few seconds) even if the termination criteria allows a longer run. I would mind a longer run for more stable results. Maybe I should also give a better look too cost variation and narrow its threshold.

My current approach is to run the same problem several times. Then we pick manually one of them based on results display on a map.

[reinterpretcat]

Thanks for feefback!

A side question: does the order of the objective in the primary set or the secondary set matter?

No, it should not matter.

But in my case, the solver stops quite quickly (a few seconds) even if the termination criteria allows a longer run.

Default termination criteria is 3000 generations or 300 seconds. I would recommend to set only time limit with --max-time option and experiment with its value. Essentially, I'm thinking about implementing something like automatic algorithm configuration depending on the problem variant, so time might be only one meaningful limit in the end. You can also try to reconfigure default parameters using --config option, but this requires some understanding of underlying algorithm. I plan to write some documentation to explain it a bit (I'm on vacation right now with my family, so I don't have too much time to dedicate for the project).

Max generations is a bit limiting as it implies the same 'weight' for all of them over the whole algorithm execution, but this might be incorrect if different sub-algorithms are used depending on the search phase (I plan to work on an extra step of heuristic for large scale problems). Cost change is not good enough in case of balancing objectives.