Introduction
For large operations, the allocation of work can be a sizeable daily task. For this article, I am going to focus on using PuLP to create a model to allocate work. It’s possible to automate this process using VBA in Excel, however, this would be a ‘greedy’ approach finding the optimal route for each individual driver but not for the entire allocation so it would not be as effective.
Excel does have a solver that can solve linear and non-linear problems, but this is limited to 200 decision variables and for large operations, this solution would be feasible.
What is PuLP?
PuLP is an open-source library in Python that can be used to solve these kinds of optimisation problems.
In order to solve the problem using PuLP you need to set up a linear objective function where the model will then try to maximise or minimise this overall value. Typically in transport operations you will have routes and drivers starting at intervals throughout the day so I would like the model to try and minimise the overall deviation in start time. However, I also want to take into account the preference of the driver – making it more favourable to match their preferences in route type.
To solve this problem we need to create a decision variable for every single combination of route and driver.
This sets up the decision variables to be binary only taking a value of 0 or 1. Essentially if the model returns a value of 1 for a combination it implies that it’s in the final solution.
To avoid the model planning drivers with a difference in start time greater than 60 minutes i have decided to use a heuristic and maximise the following function.
I have assigned a negative value (-100) to any combination that has a difference in start time greater than 60 minutes. As i am maximising the objective function this is essentially a penalty which means that the model would rather leave the driver unassigned if there are no feasible routes.
To try and take into account driver preferences the score returned from the difference in start times is multiplied by 2 if the route type and driver preference match, and by 0.5 if they do not. This makes a route, driver combination with a matching preference more favourable by around 30 minutes, however, if the model can not match the preference it would still assign the driver to a route because the value would still be greater than 0.
Now we need to set up a few constraints.
- A route can not appear in the solution more than once.
- A driver can not appear in the solution more than once.
You can create constraints in a similar way to setting up the objective function and assign an inequality to the model object.
Now to solve the problem. I have set up a basic example with 10 drivers and 10 routes.
PuLP managed to allocate work for 9 drivers in this example – with 5 of the drivers being allocated work that matches their preference.
PuLP could not allocate work for driver D9 – as the only route remaining R2 has a difference in start time greater than 60 minutes.
Using Linear Programming can automate the process of allocating work whilst finding the most efficient way to plan your workforce and take into account worker preferences.
