Comments (7)
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.
from vrp.
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
from vrp.
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).
from vrp.
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.
from vrp.
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
-
Balance activities (secondary obj) tolerance: 0.05 - threshold: 0.01 (default options) - 244km
-
Balance activities (secondary obj) tolerance: 0.1 - threshold: 0.01 (default options) - 213km
from vrp.
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.
from vrp.
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.
from vrp.
Related Issues (20)
- Associate Cost to Waiting Time HOT 17
- capacity constraints HOT 1
- Option to provide custom costs matrix HOT 4
- No solutions when using orders or skills HOT 3
- fleet.vehicles.limits.maxDuration is driving duration or total? HOT 2
- RepeatableRandom displaying non-repeatable results HOT 1
- VRP does not respond, ignores SIGINT and max-time HOT 5
- Infeasible solution
- Why cannot set time and duration costs to zeros? HOT 3
- Thread 'main' panicked - intermittent error HOT 1
- Error - called `Option::unwrap()` on a `None` value HOT 6
- Pip wheels for python 3.11 HOT 1
- Custom conditions for jobs/fleet definition HOT 6
- Index out of Bounds in Fast Service Objective HOT 3
- Unexpected behavior of required breaks with time aware matrices
- The model provide different results HOT 1
- Examples for time dependent routing
- Parameter for visiting same location multiple times across shifts
- Pydantic Model Issue HOT 1
- Add support CPUs NPU HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from vrp.