9
$\begingroup$

Has anyone used the google OR tools in python to solve the workforce scheduling problem. Can you please let me know

  1. Advantages and Disadvantages
  2. Any issues faced during usage and implementation
$\endgroup$
  • $\begingroup$ Welcome to OR.SE, would you say you want to solve your problem using mathematical optimization model or using algorithmic procedure? $\endgroup$ – A.Omidi Aug 12 '19 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 Logistics Aug 13 '19 at 4:35
  • $\begingroup$ Isn't worksforce scheduling more akin to employee rostering than to vehicle routing? $\endgroup$ – Geoffrey De Smet Aug 14 '19 at 7:01
  • $\begingroup$ @Geoffrey - it depends if they're travelling or not. $\endgroup$ – Open Door Logistics Aug 14 '19 at 22:35
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\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$ – Laurent Perron Aug 13 '19 at 3:51
7
$\begingroup$

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

$\endgroup$
  • 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$ – Laurent Perron Aug 13 '19 at 16:02
  • $\begingroup$ that well definitely be helpful :) $\endgroup$ – JakobS Aug 17 '19 at 20:46
6
$\begingroup$

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.

$\endgroup$
  • $\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$ – Lalitha Sundar Iyer S Aug 21 '19 at 10:42
  • $\begingroup$ It seems like a trivial set covering problem. $\endgroup$ – Laurent Perron Aug 21 '19 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$ – Lalitha Sundar Iyer S Aug 21 '19 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$ – Laurent Perron Aug 23 '19 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.