Dynamic Workforce Scheduling (1) — An Introduction
This article is part of a series in which I speak about my little journey in using an Artificial Intelligence Problem Solver for Dynamic Workforce Scheduling.
The Problem Definition
We need to assign tasks to inspectors to visit facilities. The number of facilities could reach tens of thousands of sites for some areas, while the inspectors are in hundreds or thousands.
There are many ways to solve the problem but not all solutions are optimal.
To have more clear understanding of the problem, imagine having a collection of sites (in my case facilities) that we need the workers/vehicles (in my case inspectors) to visit. As in this image, there is a 16 sites to be visited.
When assigning each site to a worker/vehicle, assuming we have 4 workers, the tasks could be assigned as follow where each color is related to a worker. Note that the optimal solution depends on the problem factors. So, the next picture is just a sample that shows a reasonable solution. Where, we can see, the sites are somehow clustered and assigned according to their locations. In other words, the same worker will not visit, for example, sites that are faraway form each others like 1, 15, 16 and 2.
Actually the proposed problem, is best to be solved with an AI Solver in order to find a near-optimal solution. However, per in mind that getting the optimal solution is impossible for complex scenarios. Also, do not be confused with other AI Technics that aim to estimation, expect or classify.
Dynamic Workforce Scheduling as an Optimization Problem
Dynamic Workforce Scheduling is an optimization problem: the goal of optimization is to find the best or a near-optimal solution to a problem out of a large set of possible solutions.
Like all optimization problems, our problem has the following elements.
- The constraints — restrictions on the set of possible solutions, based on the specific requirements of the problem. In our case, for example, the facility has to be visited during the open hours. Moreover, an inspector will require time to arrive and time to spend at every facility.
- The objective — what you want to optimize. In our case, the objective could be maximizing the number of detected violation, weighted be some factors like activity sensitivity (importance).
- A feasible solution is one that satisfies all the given constraints for the problem, without necessarily being optimal.
- An optimal solution is one for which the value of the objective function is the best.
In our case, the optimal solution could be visiting the most sensitive facilities regularly. Or, it is the solution that would result in the highest number of penalties with the ultimate goal of minimizing violations in order to increase the life quality of people. Or, it could be a mix of this and that…
Vehicle Routing Problem with Time Windows
Actually, the Dynamic Workforce Scheduling is a variation of the problem that is known as “Vehicle Routing Problem with Time Windows”. And the Vehicle Routing Problem (VRP) is a generalization of the Travel Salesman Problem (TSP). Where TSP has only one Salesman, while in VRP there are many Vehicles.
So, to well understand the Dynamic Workforce Scheduling, you can google for “Travel Salesman Problem” and “Vehicle Routing Problem with Time Windows”. And, I recommend reading the Routing section at the official documentation website of Google OR-Tools (even if you are not planning to use their Solver). And be sure to reach the sub-section: Vehicle Routing Problem with Time Windows. I found there is no need to describe VRP here as it is already explained in details there.
The System Overview
Below is the inputs and the output of the Solver. I intentionally named it “Solver” not an “AI Solver” to make it clear that this problem is not mandatory to be solved with AI Solver.
Actually, before my work on this there was a team who worked on the same project and they modeled the problem and solved it using a greedy algorithm without and AI Solver. However, as you may know, when using a Greedy Algorithm the problem of looking for a Local Minimum could lead to not reaching a Global Minimum. And here is where the AI Solver shine.
