You are not logged in.

Heuristic approaches for multi-criteria optimisation in kidney exchange programs

Nickholds, L. and Mak-Hau, V. 2015, Heuristic approaches for multi-criteria optimisation in kidney exchange programs, in MODSIM 2015 : Proceedings of the 21st International Congress on Modelling and Simulation, Modelling and Simulation Society of Australia and New Zealand, [Canberra, A.C.T.], pp. 1780-1786.

Attached Files
Name Description MIMEType Size Downloads

Title Heuristic approaches for multi-criteria optimisation in kidney exchange programs
Author(s) Nickholds, L.
Mak-Hau, V.ORCID iD for Mak-Hau, V. orcid.org/0000-0002-9306-5780
Conference name Modelling and Simulation. International Congress (21st : 2015 : Gold Coast, Queensland)
Conference location Gold Coast, Queensland
Conference dates 29 Npv. - 4 Dec. 2015
Title of proceedings MODSIM 2015 : Proceedings of the 21st International Congress on Modelling and Simulation
Editor(s) Weber, T.
McPhee, M.J.
Anderssen, R.S.
Publication date 2015
Start page 1780
End page 1786
Total pages 7
Publisher Modelling and Simulation Society of Australia and New Zealand
Place of publication [Canberra, A.C.T.]
Keyword(s) kidney exchange
multicriteria optimisation
population generation
Summary 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.
ISBN 9780987214355
Language eng
Field of Research 010206 Operations Research
080202 Applied Discrete Mathematics
080199 Artificial Intelligence and Image Processing not elsewhere classified
Socio Economic Objective 920499 Public Health (excl. Specific Population Health) not elsewhere classified
HERDC Research category E1 Full written paper - refereed
ERA Research output type E Conference publication
Copyright notice ©2015, Modelling and Simulation Society of Australia and New Zealand
Persistent URL http://hdl.handle.net/10536/DRO/DU:30080603

Document type: Conference Paper
Collections: School of Information Technology
Open Access Checking
Connect to link resolver
 
Unless expressly stated otherwise, the copyright for items in DRO is owned by the author, with all rights reserved.

Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in TR Web of Science
Scopus Citation Count Cited 0 times in Scopus
Google Scholar Search Google Scholar
Access Statistics: 123 Abstract Views, 0 File Downloads  -  Detailed Statistics
Created: Thu, 23 Jun 2016, 15:17:50 EST

Every reasonable effort has been made to ensure that permission has been obtained for items included in DRO. If you believe that your rights have been infringed by this repository, please contact drosupport@deakin.edu.au.