Dynamic Workforce Scheduling (2) — Using an AI Solver
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
Dynamic Workforce Scheduling as an AI Problem
In research literature, our problem is called: Vehicle Routing Problem with Time Window.
When the scenario is not very complex, the problem could be solved without Artificial intelligence. But, when, like in my case, there are hundreds of vehicles/workers and tens of thousands of sites where each one has different time window(s) and different other properties, no human or non-AI algorithm can solve it.
Breaking the Ice with AI
Before start, break the ice and bear in mind that:
- AI is very wide and almost anything that cannot be solved in the conventional programming (simple if, else and for-loop) is possibly an AI case.
- AI is not just Machine Learning and Deep Learning. Actually Deep Learning is just one of the AI tools that can be used.
- Artificial intelligence is “artificial”. And it is generally nothing more than a complex mathematical model (the model depends on a set of mathematical equations).
For example, Neural networks are actually numerical networks with trial-and-error to adjust the equations’ coefficients. And a Genetic algorithm is basically a directed mix of computational solutions…
The Chosen AI Solver
Actually, I chose Google OR-Tools. This is for the following reasons:
- Open Source
- Relatively Active support for issues raised on GitHub (for free)
- Active Community
- Written in C++ for the best performance.
- Has wrappers for C#, Java and Python
Google uses it to optimize obtaining the street-level images required for Google Street View. It is used every day to find the shortest route for each vehicle that traverses every street in an assigned region (reference: https://developers.google.com/optimization/routing).
Other AI Solvers to be Investigated
Commercial
- IBM CPLEX Optimizer: https://www.ibm.com/analytics/cplex-optimizer (https://github.com/IBMDecisionOptimization)
- Gurobi Solver: http://www.gurobi.com/
Open Source
- OptaPlanner — Constraint satisfaction solver (https://www.optaplanner.org/)
- Strategic and Competitive Intelligence Professionals (SCIP): www.scip.org
- GLPK — GNU Linear Programming Kit: https://www.gnu.org/software/glpk/
- Concorde which is dedicated to solving very large TSPs to optimality but does not provide the ability to solve a more generalized TSP like VRP and VRP with time windows (http://www.math.uwaterloo.ca/tsp/concorde.html)
Some of the above tools found to have less documentation. Some others does not support many programming languages like C# for example. And/Or some of them have less active free support. However, they could be also investigated and used instead of Google OR-Tools.
More Understanding of the Problem
Actually, it helped me a lot when I read the documentation from the official website: https://developers.google.com/optimization/routing. And I strongly recommend navigating there and read everything in the routing. And I recommend reading even if you are not planning to use Google OR-Tools. Because once you have a well understanding of the problem, it will be relatively easy to use any good AI Solver.
Modeling is the Key
The most important point is to `model` your problem in the right way. Then, any good solver may work the best for you.
Below is a screenshot from the Google OR-Tools official website:
Actually, part of the modeling is the input of the solver. And, while some inputs are fixed like the working hours, some others depend on estimations like the expected Tasks Sizes and the Visits Rewards. Those estimated values are, most likely, the best to be calculated using another AI system that uses Machine Learning and Artificial Neural Network. However, if there is no data available yet, an Expert System or some predefined equations could be used just until a historical data is available.
