-
Notifications
You must be signed in to change notification settings - Fork 328
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Optimisation missing obvious solutions #319
Comments
First we provide no guarantee of optimality, so both of the above can definitely happen. What bothers me is if it does and we miss an obvious change that would improve the solution. We have a range of local search operators that are applied in such a way that the provided solution should be free of some obvious valid changes: e.g. adding an unassigned job, moving a job from one route to another or within a route, exchanging two jobs from two different routes, etc. So in order to fully see what you mean I'll have to look at examples to reproduce both situations with indications on what improvement we're missing. |
Hi, After discussing offline with Julien, here is a recap of the problem: Use Case:
Here on the map you can see in green the starting and ending position. And in red the maintenance suggested. (in this example there is no pre-planed jobs on the map) This solution does not look optimal, and a more obvious one would be this one: Thanks Julien for investigating these and can't wait to hear your feedback on this |
First I can confirm that the suggested solution is indeed a valid one, and better both on priority and travel time, so we need to understand why we're not able to reach it. Here we'd need to remove a job from a route and replace it with an unassigned job. Each local search round we perform applies to the set of jobs that are already included in routes (except if the time gain allows to add an extra unassigned job at some point). So this is not where it can happen. We already have another specific way to handle the situation where it's desirable to remove some jobs after a local search step:
The rationale behind this is to allow deeper changes that what the "simple" local search operators can achieve and start off with a new improved solution. Now the problem in the above situation is that the job we'd like to remove is not considered a good candidate for removal. The reason for this is that the removal rule does not only account for gain when removing the job but ponder it with the cost of assigning the job to another route ( Now removing jobs solely based on travel time gain would fix the problem in this situation, but an overall change for this behaviour is not a good option as we'd break the desirable effect where pondering the cost allows to move sets of jobs from one route to another attractive route. What we need instead is a new local search operator that allows removing a job to make room in a route for an unassigned job that would improve priority and/or travel time cost. I'll open a dedicated ticket for this. @romainrey thanks for reporting, I guess this probably never came up before because of the specific setting you have with many unassigned jobs. |
Thanks Julien for this analysis. |
@romainrey no timing or deadline for #324 so far. Tickets that is prioritized for the next release are usually gathered in the next milestone. This is a direct result of what I find most useful for my own use-cases and clients. There are several ways you can contribute: if you want to try something code-wise, I can give you a few pointers on how to get started. Otherwise providing more examples that highlight the problem is very valuable too in order to make sure the proposed fix does solve the problem in all encountered situations. |
@romainrey note that this is occurring because your instances have both a distributed fleet with vehicles that potentially compete on a subset of jobs and many unassigned jobs. A temporary workaround would be to split your problem into several sub-problems, one per vehicle zone. Because you have so many unassigned jobs, your vehicle zones only overlap theoretically so this would work in your situation. |
@romainrey with #383 merged, solutions should now be much better in term of overall priority/cost choices in situations with many unassigned jobs like the one you faced. The changes are available in |
Exciting @jcoupey ! |
Hi, PS: Meanwhile I posted an other suggestion #393 lmk what you think |
Thanks @jcoupey for the new release and @romainrey , what about the results? How are your tests going? |
Hi,
I am using vroom and my solutions are often sub optimal and I can spot right away a better solution if I look at a map.
I am using vroom with 1000-1500 jobs and 30 vehicles. But my time windows are such that usually only 5 jobs can be assigned to a vehicles. I also have priorities among this jobs, priorities going from 1 to 5.
The solutions usually becomes better once I limit the number of vehicles of solutions. But this is not doable for my real world solution.
I am reaching some limits of the optimisation or I am doing something wrong?
By suboptimal I mean
I am using vroom 1.5.0.
with this config file:
cliArgs:
geometry: false # retrieve geometry (-g)
threads: 3 # number of threads to use (-t)
explore: 5 # exploration level to use (0..5) (-x)
limit: '5mb' # max request size
logdir: '/..' # the path for the logs relative to ./src
maxlocations: 5000 # max number of jobs/shipments locations
maxvehicles: 500 # max number of vehicles
override: true # allow cli options override (-g, -t and -x)
path: '' # VROOM path (if not in $PATH)
port: 3000 # expressjs port
router: 'osrm' # routing backend (osrm, libosrm or ors)
timeout: 300000 # milli-seconds
I have tested it by putting an input with an other matrix, not computed from my local osrm but I still have problems.
I can provide a reproducible example, but I can't post it here because I don't want to expose my data... (just send me a mail at rom.rey06 at gmail.com and I can send it to you)
Thanks for your help!
The text was updated successfully, but these errors were encountered: