Automatic Generation Of Guard Roles

Context

There are 4933 pharmacies in Belgium, and each pharmacy (in groups) are obliged to create a network of night-guard pharmacies covering complete Belgium. Compare it with a hospital that has 2000 nurses and want's to distribute the burden of the 'night' shift or 'weekend' shifts over the 2000 nurses on an 'equal foot' basis, but here we add a geographical aspect. So its a maximal covering location problem combined with an typical 'personel' planning problem

The challenge...

The distribution of the pharmacies follows certain rules: 11million inhabitants having access to 5000 pharmacies, you can estimate that each pharmacy serves 2200 inhabitants. This is approximately true.
You see a glimpse of the guard kalender : blackpoints, feast days, day/night guard (sun/moon)

1. Each pharmacy is equal and has to do equal number of guards. That is in this description rounded 12 days guard. We give each pharmacy a guard-capital. Meaning when at the end of the year one pharmacy has done 10 days guard, the next year the pharmacy has to do two days guard more. On average each pharmacy is doing 12 days per year. So starting with an equal guard capital. We try to minimize the difference from the mean (mse).

2. The guard is divided in a day part from 9:00u-22:00 and from 22:00pm to 9:00am as night guard.
   Each Pharmacy can choose to do guard during 1 day, having 12 days and 6 nights distributed over the year. With at least 2 sunday guards per year and one sunday night.
   Or each pharmacy can choose to do his guard in blocks of 4 weekdays (Mo-Tu-We-Th /// Fr-Sa-So) Doing at least two midweek blocks and two weekendblocks ending up with 2 day's too much guard capital. From those blocks he get alternating fe the Mo and We a nightshift. Or by example the Fr/So or Sa as nightshift . The nightshifts are also equally distributed.
   The choice for midweek/weekend or day guard is a freedom indicated in the database. We filled in a random example. Usually the freedom collides with regions.
   So a dayblock and a nightblock each get one guard point.

3. Each customer has to find a pharmacy within 20 minutes from his home. On average this rule is easily obeyed, since its possible to find 3-5 pharmacies within 20 minutes in 'city' zones. Its only in very rural zones this rule can be violated. We use a GISS database to correctly calculate the distance and travelling time between each pharmacy. You can use google-api or haversine, internally we have exact data. But within this proof of concept this doesn't matter. Actually highway's are draining more people to a pharmacy, and the algorithm shows the pharmacy as a faster alternative than geographic haversine closer pharmacies. So a very fine tuned model takes this driving speed into account in function of that 20 minutes rule. But here the haversine distance between the closest clusters should give a good approximation. It actually counts only for the case where the 20 minutes rule is 'violated'

4. If we divide Belgium in 165 clusters there are 30 pharmacies per cluster. Each cluster has 1 pharmacy available for 66000 inhabitants within 20 minutes. This during DAYTIME. (Daytime is defined until 22:00u) At night the scheme HALVES. 82 clusters, with 60 pharmacies per cluster. Each night cluster has then 132.000 inhabitants. The same rule each cluster has 1 pharmacy available.
   We search to MAXIMIZE the DISTANCE between each guard-pharmacy , so that there is an maximal SPREAD for the guard. This guarantees that customers find very fast a pharmacy. If you think about it,on the Belgium card you can superimpose a 'grid' that is shifting each day and each night selecting a pharmacy in the intersections of the grid. The only interfering element here is that 50% of the pharmacies chooses to have guard in weekend/midweek scheme, and 50% wants day/night guards, hence you have to swap the guard between neighbouring pharmacy's, so the distance rule remains respected.

5. Each Pharmacy can block 3 weeks of vacation, that is typical during school vacations periods that pharmacy's tend to block periods. We call it black-points; You can generate random 3 weeks school/holiday vacation weeks that are blocked for each pharmacy. The database is filled in with a manual created sample.. Actually the pharmacist can block 3weeks, or 6 weekend and mid/week blocks. Here i simplified to three week (number of week , week of year)

6. Doing guard on a holiday like Christmas, New Year, Eastern, Sinksen, National Feast Day, is rewarded with an extra guard capital point. Those pharmacies can do as such 1 day less guard. This as a last twitch

What do we need at the end

1° a database of all pharmacy's and their guard capital points. We tend to minimize the difference with the mean capital points. And usually the current algorithm selects the first the pharmacies in a cluster with the lowest capital points as prime candidate.

2° a list of guards for all the 165clusters for all 365days, or 60225 guards per year. And a measurement that estimates the distance between all pharmacies. for that day.. The Mean square error of the distance between the pharmacies has to be minimized