This requires an introductary knowledge of Evolutionary Computing. I recommend a resource online Evolutionary Computation 1 or similar
This is an example of an algorithm used for home healthcare timeslot allocation. The project is broken down as:
| File/Folder | Description |
|---|---|
| Papers/ | A sample of papers which can give you background reading on the subject, and alternative approaches (MILP/VRP) as well as the Evolutionary Approaches taken here |
| Distances.csv & Times.csv | A section of generated data, of an example of data pulled from the Maps API/estimated, to give the travel times required for calculating routes |
| DemoCSV | An example output of the Evolutionary Algorithm, which could be fed back in via API to a system, to enable the timeslots to be parsed |
| Home Healthcare Routing Example.ipynb | A Jupyter Notebook showing a walkthrough example of an Evolutionary approach to solving the carer routing problem |
We have a set of carers that need to visit patients throughout the day. Patients can pre-book timeslots between a given time, and require carers to show up within 15 minutes either side of that timeslot specification.
For a problem like this, the first consideration is how to define the solution-space. We need to ensure that our complicated problem specification can map to a single chromosome, with all of the information captured within.
Ultimately, the approach taken for this problem was to assign all carers a number. Each element of the chromosome represents the ordered start times of the timeslots, with the values in the chromosomes matching the number of the carer that needs to visit the patient. So, the following:
- Carers: [Jim Jones, Sarah Smith, Sally Songbird]
- Timeslots: [9:00 - 9:30, 10:00 - 11:00, 13:00 - 13:15]
- Chromosome: [[0],[1],[0]] Translates to: Jim Jones would go to the 9:00-9:30 approintment, Sarah Smith would go to the 10:00 - 11:00 appointment and Jim Jones would then go to the 13:00 - 13:15 appointment.
How to we calculate the fitnesses for these examples? In other words, how can we evaluate these solutions and know if they're good or not? In the example, I propose the use of 3 fitness functions - waiting time (how long is the carer waiting between different timeslots - we want to maximise the time spent caring for patients), overrunning penalties (if the carer goes directly from one home visit to another and the visits are scheduled too close together - causing the slot to start and finish late, we want to penalise it too), and penalties for finishing shifts late (although this could in theory be a hard restriction on the values that could be chosen for given slots too).
Collectively, this fitness function allows the algorithm to maximise the time that carers spend caring for patients, while also ensuring that we're penalising solutions where patients are spent waiting for long periods of time.
The current solution for calculating the travel times between different locations has been relying on the Google Maps API and holding the distances in a Matrix. This is a good solution for small-medium sets of carers, but the cost could rack up for large sets of patients/carers. An alternative is discussed below:
| Problem | Solution |
|---|---|
| Some carers can only walk between locations, some can cycle and some can drive | The only thing that needs changed is the travel time calculations between locations - everything else can remain the same. Cycling, walking and driving can be three distinct travel time matrices |
| Some patients don't want to see certain carers | A hard restriction can be added to ensure that the carer can't service a given patient |
| Some carers don't want to see certain patients | Ditto above |
| Some patients require certain qualifications to be seen to | Ditto above |
| Some patients require several carers arrive to service the same slot (e.g. for lifting patient etc) | Change the Chromosome from ints to sets of ints, then change the assumption to be that slots start when both carers are present and to penalise the waiting time of one carer |
There are several pieces of extension work that can be done for this algorithm:
- Multithreading is a piece of work that could be done to greatly speed up the generation
- Some restrictions could be put in place to limit the slots (i.e. one carer can't be picked twice for 2 9am slots, carers can't be picked for slots after their shifts finish etc.)
- The requirement on maps could be dropped, if an algorithm for calculating approximate travel times between locations can be estimated using the coordinates
- To serve carers & patients in multiple locations, a k-means clustering algorithm could be layered on top of the solution, to separate the calculation of routes over several cities (e.g. London and Birmingham are 2 clusters) - with a heuristic to have 'travelling' carers that can figure out if carers need to serve one area or another
- There are issues with the convergence of the current EA solutions for this example.