How OR helps kidney patients in the UK

NHS Blood and Transplant (NHSBT) estimates that over 37,500 people in the UK have end-stage renal failure; nearly 21,000 are on dialysis. As of 31 March 2017, there were 5,233 patients on the transplant list for a donor kidney. The number of kidney transplants carried out each year is much lower than this: 3,347 transplants took place between 1 April 2016 and 31 March 2017, of which 1,009 were from living donors.

There are legal frameworks to help boost the number of donors in circumstances where next of kin is not compatible with the patient. Under the paired kidney exchange (PKE), two or more kidney patients can swap their willing but incompatible donors in a cyclical fashion so that both receives a compatible kidney. Groups of three patients in a PKE are known as three-way exchanges.

There are significant logistical challenges to carrying out PKE transplants, partly because all operations must be performed simultaneously to avoid the risk of donors reneging on their commitments once their loved-one has received a kidney. Donor illness is another risk, and the larger the number of participants, the more complex the situation. Even three-way exchanges require significant coordination to secure six operating theatres and surgical teams on a single day.

An early algorithm could only manage datasets of up to 100 potential transplants, so a more capable algorithm was required to more intelligently identify and optimise the process of PKEs.

Researchers began by developing a novel approach involving graph matching algorithms which enabled optimal sets of PKEs – both pairs and three-way exchanges. They also expanded the capacity of the algorithm to deal with larger datasets of up to 3,000 potential transplants. Simulations using the algorithm indicated the likely benefit of allowing more three-way exchanges than had previously been allowed, in addition to pair exchanges. NHSBT took the decision to authorise this, and researchers were able to further improve the optimisation using a technique common in OR, integer programming. Kidneys from altruistic donors were also incorporated into the decision-making, enabling domino paired donation (DPD) chains.

The algorithms solved the complex problem with five optimality criteria in a hierarchical fashion, maximising transplants and mitigating the risks associated with three-way exchanges and long chains of donors and patients. Other factors included waiting time, sensitisation (degrees of compatibility) and the relative ages of patients and donors. The algorithm returned its optimal solution within seven seconds. Since its launch, further refinements have taken place to help the algorithm cope with future challenges that may emerge from larger pool sizes and more complex criteria.

By optimising these PKEs and DPD chains, the algorithms have led to 752 actual transplants taking place between 2008 and 2017. This is an increase of 218 (or 41%) over what the previous status quo techniques would have achieved. According to NHSBT, each kidney transplant saves the NHS £240,000 over ten years (based on a comparison with the cost of dialysis over that time and accounting for the cost of the operation). This means that enabling an increase of 218 transplants has saved the NHS around £52 million over a ten year period.

Full article available in Impact Magazine, Spring 2018: ‘How Operational Research Helps Kidney Patients in the UK’ pp16-19