Pre-planned jobs

[romainrey]

Hi,

I would need to use vroom to optimize several vehicles which have to do some jobs, but I already know that some given vehicules have to do some given jobs. These ones are 'already' planned and I need vroom to only complete the planning.

For example you have to visit different cities but you know that you have to go to city X, and this is non-negociable.

How to force this? I tried priority but this is not enough, even with priority 0 on all jobs and 10 on mandatory job.

Thanks

Ps:
I am in a situation where I have a lot of jobs and a restricted time window so I know that there will be a lot of unassigned jobs. I just don't want one of my mandatory job to be unassigned.

[jcoupey]

Looks like you need a combination of two things.

1. Making sure a job is performed by a given vehicle: for this you need to assign this job a specific skill that only the matching vehicle has.

2. Trying to force all "already planned" jobs to be included in the solution: set high priority to those jobs and low priority to all other non-mandatory jobs.

Note that the later cannot guarantee that all "mandatory" jobs will be included in the solution if you have lots of jobs and strict constraints (e.g. time windows).

[jcoupey]

@romainrey out of curiosity, can you expand a bit on the context and what you're trying to achieve?

[romainrey]

Thanks for the quick answer,

Indeed the strategy you detailed is exactly the one I followed. I set up unique matching by skill to ensure only the good car can do the job and I set priority 10 and 0 to push it to go to these jobs.

Unfortunatly this is not enough to make it work...

For context:
I have some technicians who need to repair some shops. Some jobs are urgent repairs and are mandatory, other are predictive maintenance and can be done in the current month.
I want to do the mandatory jobs and to find the most optimal predictive maintenance "on the way".

[jcoupey]

Unfortunatly this is not enough to make it work...

Can you please be a bit more verbose on what does "not work"? I think I get what you expect but I'm not sure what is actually different in the solutions you get? Maybe provide a simple example if you can?

[romainrey]

Sorry for the lack of details, here a more complete answer:

Let's look at the example below,
We have 1 vehicle, 3 jobs with high priority and around 20 with low priority, and a time window constrain (in fact only saying a 12h day maximum)

and the final solution gives me:
Job: 11, 8, 19, 3, 21

whereas jobs 1, 2, 3 were 'mandatory'

(All locations are in France)
{"vehicles":[{"id":1,"start":[0.5478,49.5754],"end":[0.5478,49.5754],"skills":[0,1],"time_window":[0,43200]}],"jobs":[{"id":1,"location":[-0.8686,48.8557],"service":3600,"skills":[0,1],"priority":10},{"id":2,"location":[-1.4545,49.0662],"service":10800,"skills":[0,1],"priority":10},{"id":3,"location":[-0.3107,49.1694],"service":7200,"skills":[0,1],"priority":10},{"id":5,"location":[-1.0733,49.0899],"service":3600,"skills":[0,0],"priority":0},{"id":6,"location":[-1.5796,49.6435],"service":7200,"skills":[0,0],"priority":0},{"id":7,"location":[-0.2087,48.9068],"service":3600,"skills":[0,0],"priority":0},{"id":8,"location":[-0.3933,49.1732],"service":3600,"skills":[0,0],"priority":0},{"id":9,"location":[-1.4545,49.0662],"service":3600,"skills":[0,0],"priority":0},{"id":10,"location":[-1.3515,48.6813],"service":4500,"skills":[0,0],"priority":0},{"id":11,"location":[-0.3698,49.1848],"service":5400,"skills":[0,0],"priority":0},{"id":12,"location":[-0.3591,49.1812],"service":7200,"skills":[0,0],"priority":0},{"id":13,"location":[-1.4545,49.0662],"service":21600,"skills":[0,0],"priority":0},{"id":14,"location":[-0.3698,49.1848],"service":5400,"skills":[0,0],"priority":0},{"id":15,"location":[-0.2138,48.8882],"service":8100,"skills":[0,0],"priority":0},{"id":16,"location":[-1.2481,49.3031],"service":7200,"skills":[0,0],"priority":0},{"id":17,"location":[-0.4778,49.2078],"service":18900,"skills":[0,0],"priority":0},{"id":18,"location":[-1.6164,49.6398],"service":15300,"skills":[0,0],"priority":0},{"id":19,"location":[-0.3107,49.1694],"service":5400,"skills":[0,0],"priority":0},{"id":20,"location":[-0.7644,49.2398],"service":7200,"skills":[0,0],"priority":0},{"id":21,"location":[-0.1708,49.1837],"service":9900,"skills":[0,0],"priority":0},{"id":22,"location":[-1.6325,49.4701],"service":4500,"skills":[0,0],"priority":0},{"id":23,"location":[-0.2973,49.278],"service":9900,"skills":[0,0],"priority":0},{"id":24,"location":[-0.3975,49.289],"service":10800,"skills":[0,0],"priority":0},{"id":25,"location":[-1.555,49.294],"service":31500,"skills":[0,0],"priority":0}]}

[jcoupey]

I'm getting the expected result when running your input against my local OSRM instance with France data.

$ vroom -i input.json | jq '.routes[].steps[].job'
null
3
2
1
null

I see two potential causes.

1. You're running an outdated version of vroom prior to the introduction of priority constraints. What version are you using?
2. The travel time matrix used on your side is significantly different from mine. Are you using OSRM? In that case and in order to allow reproducing the problem, please provide a standalone version of your input file following those steps.

[romainrey]

Hi,

This is encouraging,

I didn't have the time to to the standalone version as suggest, I'll do it asap.
Meanwhile, running 'vroom -h' I got 'Version 1.5.0-dev'.
The option 1. (wrong version) kind of makes sense to me in the way that if we look at the optimization, it really looks like it gives no importance to the priority parameter and just try to optimize the distance/time. As you can see on this screenshot: link image

[romainrey]

By running the process on your link I got the following json file
The optimisation based from it does not change anything for me

[jcoupey]

I can confirm I'm getting the expected behaviour with your standalone input file and a recent version. You need to checkout tag v1.5.0 and rebuild vroom.

The priority key has been introduced in the last v1.5.0 release, see the changelog. On the other hand 1.5.0-dev means "the development version prior to the v1.5.0 release", so what happens is the priority keys in your input are simply ignored.

As a general rule of thumb, and unless you need to mess up with a feature that is under development, I'd recommend using release builds by checking out specific version tags.

[romainrey]

I installed the new version this morning and I confirm that it is indeed working way better.
I managed to get the json example solved correctly. Thanks for spotting this!

I tested it on some real case scenario that I have with a lot more jobs and vehicles. The solution works well in 90% of the case by giving to people the mandatory jobs they are qualified to do.
I also noticied that reducing the number of possible jobs leads to better results.
So I will probably run the optimization with all jobs and for the few vehicles where some mandatory
jobs has not been taken, I will re-run the optimization only with them and with less possible jobs (which acts as a pre-selection in some ways...).

I was also thinking about a potential way to add more weight to the mandatory job. By duplicating a job and adding service=0 to its copy and priority=10, the vehicle will get 20 priority points (10 for the real job and 10 for the duplicate) by going there without spending more time, so that should give it an incentive to go there. We can even add 3, 4, ... duplicate jobs for one real job to add more weight.
But that does not look to improve much the case where it misses the mandatory job. I think the problem is that it doesn't even consider going by these jobs in the solutions it tests fo these cases.

[jcoupey]

We can even add 3, 4, ... duplicate jobs for one real job to add more weight

I get it that it's tempting to try forcing the weight this way, and in term of pure modelling it makes sense. However I wouldn't recommend doing this for two reasons:

1. That would be adding an unnecessary complication to the way solutions are evaluated, and besides this is already what priorities do, because during the local search solutions are compared first based on priority sum. So if you already have 0 / 10 priorities and not all 10-priority jobs are assigned, then the problem is elsewhere.

2. It would basically ruin the improvement options during the local search phase. If you set one or several dummy jobs at the same exact position, most likely the heuristic used to build initial routes will insert them all in a row. So far, so good. But then if the local search process needs to exchange the "real" job with a job from another route at some point because it's cheaper ("exchange" operator), then this move won't be detected any more. Indeed we don't have an operator to exchange an arbitrary number of jobs from one route to another (testing exhaustively such options would have a prohibitive cost).

[jcoupey]

So if you already have 0 / 10 priorities and not all 10-priority jobs are assigned, then the problem is elsewhere.

@romainrey to make sure I get it right, can you confirm this is what's happening in the 10% of cases you mention, that is:

• you only have priority 0 or 10 respectively for optional and mandatory jobs
• some mandatory jobs show up as unassigned in the solution and it's not related to another constraint
• in particular, solving the same problem with only mandatory jobs result in a solution with no unassigned jobs

If so, then I agree we don't provide the expected solution and it would be valuable if you could share a standalone instance to reproduce.

[romainrey]

I get it that it's tempting to try forcing the weight this way, and in term of pure modelling it makes sense. However I wouldn't recommend doing this for two reasons

All right I get it, it makes more sense now, thanks for the explanation. It was indeed risky to try that without knowing the underlying optimizations you were doing.

@romainrey to make sure I get it right, can you confirm this is what's happening in the 10% of cases you mention, that is:

Sorry I forgot to mention a crucial information: I was simplifying the problem in this thread with only priorities 0 and 10 because the simple example wasn't working for me. But now that the simple example is working (thanks to version upgrade), I got back to my initial problem: working with several priorities values.
After analyzing the solutions I noticed that all solution suggested by the algorithm actually gives a higher sum of priorities. So we can't blame the algo as it does what we expect him to do.

However the business need is real: I need to repair some shops, so these are urgent and mandatory interventions (priority 10). But I also need to do some maintenance and the priority of the maintenance could be based on a contract delay we have to respect (e.g predictive maintenance priority 0, 6 months in advance priority 1, ..., 1 month late priority 5).

The only solution I see to deal with this for me is to rerun the optimization on the missing ones and reduce the priorities (for example by saying only <inferior 3 months in advance priority 1 else if superior then 0), this will help to reduce the sum of priorities of non mandatory-jobs solutions. But this will make me loose some information on the real priority of the maintenance to do and also a cost of recomputing optimization

The other solution would be to put the priority parameter on a range from 0 to 100 as you were suggesting in your original post. That would solve all these problems and it should not change anything for those using it with the range 0 to 10. But I don't know if this on your plan... But at least now your know that some business case actually justify it :)

[jcoupey]

I'm not sure changing the priority scale would fundamentally make things different, other than by providing a little more granularity. If you want to give it a try, you only have to adjust this check. A priority is a 32-bit unsigned integer so you just want to be careful that priority sums do not overflow.

predictive maintenance priority 0, 6 months in advance priority 1, ..., 1 month late priority 5

I don't quite understand what is wrong with the way you translate your business logic into priorities. If the provided solution actually gives the highest priority sum, then how is it different from what you're trying to achieve?

[romainrey]

you only have to adjust this check.

Thanks will try this! I will keep you updated

what is wrong with the way you translate your business logic into priorities

Let's recap:

• I have some maintenance that I can choose when I want to do them, and they have priorities depending on their contract date limit. So let's say that they can have priority 1 to 5.
• I also have some mandatory urgent fixes to do, for which I don't have the choice to do them. I need to do them. I want to give them the highest priority.

But in reality a combination of maintenance cannot replace a mandatory jobs. Even 5 maintenance of priority 5 can't replace one mandatory urgent fix. Because the fix is mandatory and cannot be left unassigned. What I can only do is to add some maintenance after or before the fix if I still have time in my day.

So the problem with priority 10 is that a combination of maintenance can easily replace one mandatory job (for example only 3 maintenance with priority 5 (so a total of 15) so can do it).

But in reality one day can only contain 5 operations maximum (either fix or maintenance). So if I put the mandatory fixes to a priority of 100 and I keep the priority between 1 and 5 for maintenance (I keep priority for them because this help me to rank them between maintenance) then there is no combination possible of maintenance that could be preferred to a mandatory fix. So that solves my situation.

[jcoupey]

Yes, the 0-10 priority scale woks well in most cases with just a few priority classes but it may indeed be too restrictive if you want to have 5 levels of optional jobs.

Happy to have feedback on your tests and findings!

[romainrey]

After testing on several examples, changing the priority to 100 for mandatory and keeping low values (usually <10) for the other worked well for me. I don't have any problem anymore on this! Thanks a lot for the help all along
Maybe in future version the max priority could be a parameter?

An other question: today the major part of my time is taking by the loading phase and not the solving phase (13s for loading and 0.3 for solving). I am using vroom express and json in the query. Is there any ways to make this loading quicker?

[jcoupey]

@romainrey adding yet another parameter is not ideal and anyway I think it's clearer for everyone to have a fixed range for priority values. Based on the way it's been implemented, the scale itself does not really matter as long as it allows to use enough priority "classes". So in the light of your feedback I'm in favour of your previous suggestion to raise the max value to 100. Besides, as you mentioned, that change would not affect at all anyone using the current [0,10] scale.

[jcoupey]

Is there any ways to make this loading quicker

Are you referring to the summary.computing_times value in the response? The loading part there is parsing the input file (that's usually very fast thanks to rapidjson), then mostly computing the matrix, plus a couple pre-computations.

A loading time of 13s seems indeed very high, especially because the solving time suggest you have a small problem. Can you provide more context on your setup:

• typical problem size (number of jobs and vehicles)
• OSRM setup (local or remote server? using osrm-routed?)

[romainrey]

Great news for the official increase of priority!

About my problem complexity I have:
600 jobs
15 vehicles
30-80 jobs possible per vehicles (indeed each vehicle will not browse all possible jobs thanks to skills)
And I am using a local osrm setup (using osrm backend on docker)
If you want to try on yours, I can send you a private json by mail :)

[jcoupey]

@romainrey first check the time it takes for your local OSRM instance to complete a table request with ~600 locations to confirm this is the bottleneck. Then make sure you use the CH pipeline (rather than MLD) for faster requests. Any other troubleshooting with OSRM and/or Docker is out of the VROOM scope.

Another option you have to speed-up things is to install libosrm on your system. Then when compiling vroom it will link to libosrm and you can use -r libosrm to use OSRM directly from C++. This saves serializing the OSRM table and route responses, sending them through http, then parsing them. Note that you'll have to load the OSRM data in memory for this.

[romainrey]

Sorry for getting back late on this,

I checked and this was indeed the bottleneck.
I am now using the CH pipeline, I improved from 13s to about 3-4s, so that's a very satisfying improvement!

I didn't try the other improvement as I am not sure I want to overload the RAM with it
But we are reaching times which are acceptable to wait for a web app as it is a computation that is manually launched and not too often.

So I think it is now all good for me, thanks a lot Julien for your help. I hope I could help you on this nice project one day if there is something more into Python or R which are my main skills. Anyways I will let you know if I have some comments, or ideas for improvement.

Thanks!