Optimisation missing obvious solutions

[romainrey]

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

• Sometimes there is a doable solution that can have a higher sum of priorities
• Sometimes for the same number of points there is a shorter solution

---

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!

[jcoupey]

Sometimes there is a doable solution that can have a higher sum of priorities
Sometimes for the same number of points there is a shorter solution

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.

[romainrey]

Hi,

After discussing offline with Julien, here is a recap of the problem:

Use Case:
We want some vehicles to visit some shops to fix some machines. All of the fixes have different priorities:

• Some fixes have a deadline, but we can do them before, they are "maintenances". For those, the priority will be for example 1 if we are 3 months before the deadline, 2 if we are 2 months before, 3 if we are one month before.
• Some urgent fixes. This one has to be done right away and are already planed. For the optimization to take them into account we give them a super high priority and a specific skill that link them to the vehicle and the date where it is planed (see my issue on pre-planed job where we explained the solution).
• Overall the perfect solution is the one that: do all of the pre-planed jobs and maximize the sum of the priorities for the other jobs. And at equivalent sum of priority we prefer shorter solutions.
• All vehicles have a time window constrain and we expect to have a lot of unassigned jobs everytime because there is a lot of maintenance that we can anticipate but only a few we can do every day.

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)
The dots are the possible maintenances, going from yellow (low priority) to red (high priority)

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

[jcoupey]

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:

1. "loosen" existing routes by removing a number of jobs
2. reinsert unassigned jobs in loosened routes

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 (best_relocate_cost). Here the later predominates because there is another vehicle cruising on the west (not visible in the screenshot). In short, the third job on the west is considered more interesting to remove because it could more easily fit in the other 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.

[romainrey]

Thanks Julien for this analysis.
I'll track the new opened ticket,
By curiosity do you have any scope regarding when this would be address?
If I can help by any ways feel free to ask me for, I can probably provide more examples to test this issue once you have some solutions running

[jcoupey]

@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.

[jcoupey]

@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.

[jcoupey]

@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 master and will be part of the upcoming release. Always happy to have any feedback.

[romainrey]

Exciting @jcoupey !
I will try that this week end and let you know my feedback,
Thanks!

[romainrey]

Hi,
I have been running tests over the week end, results are encouraging! I haven't run through any problem yet but I'll keep testing it this week into more cases and keep you posted :)
Thanks!

PS: Meanwhile I posted an other suggestion #393 lmk what you think

[iedmrc]

Thanks @jcoupey for the new release and @romainrey , what about the results? How are your tests going?