Unexpected number of unassigned jobs about vrp HOT 8 CLOSED

Sorry for the noise... When trying to create a minimal reproducible example for you, we realized there was a bug in our software which generated the problem definition files. In a nutshell, we have to apply a correction factor for the in- and outwards routes of the depot (to model tour starts and tour ends which come with some extra administrations tasks for the drivers). It turned out this correction was not always correct, so vrp-cli was correct in not assigning some of the shops in those scenarios because it was basically impossible under the given (erroneous) constraints.

from vrp.

It is hard to say what is wrong here without seeing actual data. However, few notes here:

• minimize-cost objective uses cost value calculated using total duration and distances. You can try to reduce duration cost of the vehicle or increase distance cost (or simply add minimize-distance objective as second in hierarchy, before the cost one)
• I think SHIFT_TIME_CONSTRAINT in this use case is triggered as vehicles have already a lot of jobs to serve in their tours and cannot simply serve more without violating shift time limit
• problem complexity vs running time: was the solver given enough of time to solve the problem?
• setting the same value on every job is meaningless, minimize-unassigned should be enough here. The purpose of value property is to mark which jobs should be preferred for assignment when not all jobs can be assigned

from vrp.

minimize-distance seems a good idea, I will try it soon and report back the results.

from vrp.

It does not help, unfortunately...

from vrp.

Too many unknown to suggest something more concrete:

• what is the size of the problem?
• what kind of VRP variant is used?
• how long was run the solver?
• what is the target hardware?
• ...

from vrp.

• Single depot, ~200 deliveries, ~8-10 vehicles
• Capacitated VRP with time windows, multi-trips allowed
• ~45 minutes
• CPU-optimized DigitalOcean droplet with 32 CPUs and 64 GiB of RAM-> though I usually only use the default vrp-cli settings because I run a couple of problems in parallel

Note that vrp-cli produces excellent results on a larger problem (a depot which serves 450-480 shops) with lots of double-trips. For most other depots, the results are also very good but there are some unassigned jobs here and there. For one of the depots, 2-10% of the jobs remains unassigned. The same code produces the input files for vrp-cli.

If you are interested and would like to have my use case as a testbed I can contact you via LinkedIn and send you the problem.json, config.json, and distances.json file in private.

from vrp.

• multi-trip (reload) is an experimental feature and might have some quality issues
• when I was testing on hardware with multiple CPUs (e.g. 24-96), I noticed that default search progress, measured in generations per second, is much slower than on 12-16 CPUs. This is related to default algorithm configuration and thread-pool settings for data parallelism. At the moment, defaults works best for 12-16 CPUs. A parallelism setting exists to change amount of thread pools and threads which might improve performance on such hardware, but it requires a bit understanding of internals. A simpler approach could be just to limit amount of used threads by setting RAYON_NUM_THREADS environmental variable to lower values (e.g. 16).
  Improving default logic here is something in my TODO list.

Yes, data can be shared with me. If it has some sensible information, please obfuscate it a bit (e.g. rename job/vehicle ids). You can use indexing instead of real geolocations. Please also provide some info about expected results (e.g. best known solution)

from vrp.

Thank you, I will try to create a minimal example.

from vrp.