Optimization involves finding a set of problem parameter values that corresponds to minimization of some cost value. There is a class optimization algorithms calledHeuristic Optimization for real world complex non linear optimization problems. Many of them are inspired by natural processes. Simulated Annealing is one such algorithm. We will use this algorithm to find optimum patient appointments in a doctor’s office. The implementation is part of my Python package called arotau. It contains various heuristic optimization algorithm implementation. I will be adding more in future. Here is the GitHub repo.

Simulated Annealing

Simulated Annealing (SA) algorithm is inspired by the physical annealing process. In physical annealing some material is heated up and then gradually cooled down and during that time the material is shaped into the desired form. There is temperature parameter in SA. As the algorithm iterates temperature is gradually brought down. At high temperature more exploration is allowed enable escape from local minima. Exploration is encourage by probabilistically accepting worse solution. At low temperature, worse solutions are less likely to be accepted promoting exploration.

Like any heuristic optimization, SA does not guarantee optimum solution. It’s sub optimal, but computational resource usage is much less than brute force approach, which is often not even feasible because of combinatorial explosion.

Patient Appointment

Generally patient appointments for a doctor is mad on a first come first serve basis. If any body needs appointment on the same day, urgent care is likely to be the only option. For this solution, we will consider a different approach. Appointments are confirmed only on the day of the appointment. Regular patients will typically call ahead days earlier for an appointment on a given day. People needing urgent care will call on the same day or the day before. Generally number of patients will be larger than the number of available slots.

At the beginning of the day, there is a pool of patients, mostly normal and some needing urgent care. The job of SA is to pick the n patients to fill the all the n slots for the day. The cost is based on the patients who were left out. Those patients left out are added to the pool for the next day.

There are 2 factor in the cost computation. The first cost factor is the accumulated delay, with higher cost for longer delays. The other is the time gap between appointment request and desired appointment data, with higher cost associated with higher gap. This cost factor, coerces the solution to be more like traditional first come first serve model. The constraint for the solution is that patients with delay exceeding certain number of days will have to included for that day.

Optimization Solution.

The SA implementation is part of the aorta packkage. All configurations parameters are specified in a properties file. Here is some sample output

patient details
ID 04935045  type 1  delay 2 request 5
ID 44141028  type 1  delay 2 request 4
ID 03505356  type 2  delay 0 request 0
ID 27166804  type 1  delay 2 request 5
ID 60947619  type 1  delay 2 request 10
ID 00610704  type 1  delay 0 request 4
ID 08119702  type 1  delay 3 request 7
ID 01454498  type 2  delay 1 request 0
ID 57685023  type 1  delay 4 request 10
ID 00159361  type 1  delay 5 request 7
ID 73589245  type 1  delay 4 request 0
ID 45135105  type 1  delay 5 request 5
ID 77676595  type 2  delay 1 request 0
ID 15329508  type 1  delay 3 request 9
ID 48014861  type 1  delay 0 request 5
ID 99593775  type 1  delay 4 request 3
optimizer started, check log file for output details...

best solution found
cost: 0.437 	soln: ['45135105', '96889484', '19369773', '23278263', '61952872', 
'36576619', '08119702', '99593775', '60947619', '44050589', '75425283', '86731891', 
'50830889', '79067422', '49144257', '12626049', '57685023', '15329508', '44141028', 
'23490591', '01454498', '43467147', '18111612', '71443926', '80215690', '66703337', 
'00159361', '44561152', '97819157', '37272111', '07618155', '48014861']

In first part of the output we have patient details. Type 1 is normal patient and type 2 is urgent. Delay is the delay from the desired appointment date. The last field is gap as the number of days between request date and appointment date.

The second part of the solution contains the solution which consists of the 32 patients selected for appointment for the day.There is also the cost associated with this solution. Please refer to the tutorial for steps to execute the use case. Here is the driver Python code. The driver code contains a call back Python class. The callback class needs to implement 2 methods with evaluate() returning the cost value and validate() returning a boolean indicating whether the solution is valid.

There is aPython package called matumizi that aortau depends on. The package matumizi provides many exploratory data analysis functions along with various functions for statistics and general utility.

Wrapping Up

SA is a simple heuristic optimization solution for solving complex optimization problems. In this post we have seen how it can be applied to optimize doctor’s office patient appointments. It can be used to solve various optimization problems including hyper parameter tuning for machine learning models.