Deakin University

File(s) under permanent embargo

Heuristic approaches for multi-criteria optimisation in kidney exchange programs

conference contribution
posted on 2015-12-04, 00:00 authored by Luke Nickholds, Vicky MakVicky Mak
The Kidney Exchange Problem (KEP) is an optimisation problem that was first discussed in Rapaport (1986) but has only more recently been the subject of much work by combinatorial optimisation re-searchers. This has been in parallel with its increased prevalence in the medical community. In the basic formulation of a KEP, each instance of the problem features a directed graph D = (V,A) . Each node i ∈ V represents an incompatible pair wherein the patient needs to trade kidneys with the patient of another incompatible pair. The goal is to find an optimal set of cycles such that as many patients as possible receive a transplant. The problem is further complicated by the imposition of a cycle-size constraint, usually considered to be 3 or 4. Kidney exchange programs around the world implement different algorithms to solve the allocation problem by matching up kidneys from potential donors to patients. In some systems all transplants are considered equally desirable, whereas in others, ranking criteria such as the age of the patient or distance they will need to travel are applied, hence the multi-criteria nature of the KEP. To address the multi-criteria aspect of the KEP, in this paper we propose a two-stage approach for the kidney exchange optimisation problem. In the first stage the goal is to find the optimal number of exchanges, and in the second stage the goal is to maximise the weighted sum of the kidney matches, subject to the added constraint that the number of exchanges must remain optimal. The idea can potentially be extended to multiple-objectives, by repeating the process in multiple runs. In our preliminary numerical experiments, we first find the maximum number of kidney matches by using an existing open source exact algorithm of Anderson et al. (2015). The solution will then be used as an initial solution for the stage two optimisation problem, wherein two heuristic methods, steepest ascent and random ascent, are implemented in obtaining good quality solutions to the objective of maximizing total weight of exchanges. The neighbourhood is obtained by two-swaps. It is our intention in the future to implement a varying neighbourhood scheme within the same two heuristic framework, or within other meta-heuristic framework.



Modelling and Simulation. International Congress (21st : 2015 : Gold Coast, Queensland)


1780 - 1786


Modelling and Simulation Society of Australia and New Zealand


Gold Coast, Queensland

Place of publication

[Canberra, A.C.T.]

Start date


End date






Publication classification

E Conference publication; E1 Full written paper - refereed

Copyright notice

2015, Modelling and Simulation Society of Australia and New Zealand


T Weber, M McPhee, R Anderssen

Title of proceedings

MODSIM 2015 : Proceedings of the 21st International Congress on Modelling and Simulation