Has anyone used the google OR tools in python to solve the workforce scheduling problem. Can you please let me know
- Advantages and Disadvantages
- Any issues faced during usage and implementation
$\begingroup$
$\endgroup$
4
asked Aug 12, 2019 at 8:14
-
$\begingroup$ Welcome to OR.SE, would you say you want to solve your problem using mathematical optimization model or using algorithmic procedure? $\endgroup$– A.OmidiAug 12, 2019 at 17:27
-
$\begingroup$ Is this for a real-life problem or an academic problem? Workforce scheduling problems in real-life are often dynamic / real-time (e.g. if you get same-day jobs, want to reassign jobs if technicians get delayed, etc). Google OR tools isn't really setup to solve real-time/dynamic vehicle routing problems, it's primarily engineered for static cases. $\endgroup$– Open Door LogisticsAug 13, 2019 at 4:35
-
$\begingroup$ Isn't worksforce scheduling more akin to employee rostering than to vehicle routing? $\endgroup$– Geoffrey De SmetAug 14, 2019 at 7:01
-
$\begingroup$ @Geoffrey - it depends if they're travelling or not. $\endgroup$– Open Door LogisticsAug 14, 2019 at 22:35
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
In addition to the answer from @Mehdi... I've recently started to work with OR-tools and find it very nice for prototyping. The Python interface allowed me to produce a first version of my model within one day. The times to obtain a first solution seem good - it performed very favorable in the MiniZinc Challenge 2018.
The main struggles/disadvantages that I've run into so far are the very limited support for floating point numbers. Compared to MiniZinc for example (which I also used) there is no possibility to have cumulative constraints with floats. Also, some constraints seem to be lacking from the catalog/ that MiniZinc offers. For example the AddMaxEquality function allows only variables and no expressions to be used, so you'll have to add additional variables.
I also found that the documentation could use some improvements - for example the solver parameters were hidden in the source code and there was no dedicated place where they were listed (or I looked in the wrong directions).
-
1$\begingroup$ I do not know how to document properly a protobuf file using doxygen. I think I will just add a link to the protobuf file on github. At least it is readable. $\endgroup$ Aug 13, 2019 at 16:02
-
$\begingroup$
$\endgroup$
1
I used OR-tools for TSP and VRP. These are my observations:
1- It provides a good quality solution in reasonable time. However, it is not the optimal solution and in some cases you can find much better solutions easily.
2- The implantation in Python is straightforward.
3- It is not flexible. You can not add many extensions to the problem, just basic assumptions and constraints.
4- You will have some option such as giving the initial solution, the algorithm settings.
If you want a good solution fast and you are sure you will not expand the problem later, then go for it.
-
2$\begingroup$ I wonder why you think it is not flexible. The concept of dimensions is pretty flexible in my opinions. It models tsp, vrp, pdp with time windows, capacities. And you can add all the constraints of the underlying constraint solver. $\endgroup$ Aug 13, 2019 at 3:51
$\begingroup$
$\endgroup$
4
Workforce scheduling describes many different problems.
The best technology for those is IMO CP-SAT (see the introduction, the reference manual in the CP-SAT sections and a set of recipes).
A popular concert is shift scheduling. This example has gained a lot of traction in the past. It shows how to implement useful constraints on the problem that contains fixed daily shifts.
answered Aug 13, 2019 at 3:59
-
$\begingroup$ Thanks. I am working on an problem where 120 resources overall , 4 overlapping shifts. Incoming volumes for every hour the day and TAT of 24 hrs for every case that comes in at every hour of the day. I want to solve to find the minimum number of employees required for each shift. I want to understand how to use teh CPS SAT solver for this $\endgroup$ Aug 21, 2019 at 10:42
-
$\begingroup$ It seems like a trivial set covering problem. $\endgroup$ Aug 21, 2019 at 11:54
-
$\begingroup$ Thanks. But can greedy algorithm be used when shifts are overlapping? The intervals should not have conflict right?. Or are you suggesting that I define the intervals based on time of arrival of the case? $\endgroup$ Aug 21, 2019 at 13:06
-
$\begingroup$ For each hour, count the manpower needed. For each hour, count the contribution of each intersected shift, weighted by the number of time this shift is selected. Make sure the contribution exceed the demand. It will take care of the overlapping part. $\endgroup$ Aug 23, 2019 at 18:47