Heuristic approaches for multi-criteria optimisation in kidney exchange programs

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