| Sumario: | Important advances in healthcare management by means of Operations Research techniques have been achieved over the past few years. One area in particular
is in helping patients in need of a kidney reduce their usually long waiting times.
One way to do this is through a kidney exchange program. If a patient needing a
kidney brings along a person (a relative or friend) willing to donate one of her/his
kidneys and if they both are clinically compatible then the donation can be done
immediately by mutual agreement. However, if this patient-donor pair (PDP) is not
compatible, an exchange with another PDP could take place. This could happen for
instance when the donor of one pair is compatible with the patient of another pair
and vice-versa. If such a pair is found, then they can agree to have a simultaneous
donation, have their kidney exchange surgeries relatively faster, avoiding the waiting
list. In some other cases, altruist donors, those without requiring a kidney in return,
may trigger a sequence of donations involving a series of incompatible PDPs. Now,
given a pool of PDPs with their compatibility information among pairs, finding the
largest amount of matches implies finding the largest amount of people that could
have their needed kidney surgeries in a timely fashion, rather than going to the
waiting list. Formally, the kidney exchange problem (KEP) is defined as finding the
largest amount of matches (either in form of cycles or chains) among a pool of PDPs.
In this thesis, we address the KEP by presenting and comparing a variety of existing
models and algorithms that cover almost all the kidney exchange variants known so
far. In particular, for one of the fundamental Kidney Exchange Problem formulations
encountered in the literature, a reduction method for substantially decreasing
the size of the problem is proposed. Moreover, we will set a natural partition on
the directed graph based on graph theory concepts in order to model reduced-size
instances, while keeping optimality. The proposed approach turns out to be very
effective to solve the KEP in terms of quality of solution and computational effort,
in many cases outperforming other KEP formulations.
|
|---|
