KPDGUI: An interactive application for optimization and management of a virtual kidney paired donation program

Abstract

Background and objectives: The aim in kidney paired donation (KPD) is typically to maximize the number of transplants achieved through the exchange of donors in a pool comprising incompatible donor-candidate pairs and non-directed (or altruistic) donors. With many possible options in a KPD pool at any given time, the most appropriate set of exchanges cannot be determined by simple inspection. In practice, computer algorithms are used to determine the optimal set of exchanges to pursue. Here, we present our software application, KPDGUI (Kidney Paired Donation Graphical User Interface), for management and optimization of KPD programs.

Methods: While proprietary software platforms for managing KPD programs exist to provide solutions to the standard KPD problem, our application implements newly investigated optimization criteria that account for uncertainty regarding the viability of selected transplants and arrange for fallback options in cases where potential exchanges cannot proceed, with intuitive resources for visualizing alternative optimization solutions.

Results: We illustrate the advantage of accounting for uncertainty and arranging for fallback options in KPD using our application through a case study involving real data from a paired donation program, comparing solutions produced under different optimization criteria and algorithmic priorities.

Conclusions: KPDGUI is a flexible and powerful tool for offering decision support to clinicians and researchers on possible KPD transplant options to pursue under different user-specified optimization schemes.

Keywords: Fallback options; Kidney paired donation; Optimization; Simulation models; User interfaces.

Figure 1:

An exchange cycle within a KPD program, where each node represents a donor-candidate pair. The cycle here has the donor of pair 91 donating to the candidate of pair 53, and the donor of pair 53 donating to the candidate of pair 94, whose donor closes the cycle by donating to the candidate of pair 91.

Figure 2:

A chain within a KPD program, where larger red nodes represent donor-candidate pairs and the smaller purple node represents an NDD. The chain begins with a transplant from NDD 109 to the candidate of pair 44, followed by a transplant from the donor of pair 44 to the candidate of pair 97, and so on through pairs 99 and 103. The donor from pair 103 that remains can then either donate to a candidate on the deceased donor waiting list or remain in the program as an NDD to initiate a future KPD chain.

Figure 3:

An LRS within a KPD program. This LRS is a 4-node subgraph of the original KPD network, consisting of pairs 22, 47, 83, and 88, admitting two sub-cycles of size 3 (between pairs 88, 22, and 83, and between pairs 88, 47, and 83), and three sub-cycles of size 2 (between pairs 22 and 83, 47 and 83, and 83 and 88). After selection, the viability of the matches and the availability of the donors and candidates in the LRS are determined. If either of the size-3 sub-cycles remain viable, we proceed to transplantation with that sub-cycle. If both remain viable, we proceed with the sub-cycle that admits the higher utility. If neither of the size 3 sub-cycles is viable, then we proceed with the best size-2 sub-cycle that remains. It is also possible that none of the sub-cycles will remain viable (say, if pair 83 were unavailable).

Figure 4:

Prompts for donor (left) and candidate (right) characteristics

Figure 5:

KPDGUI solutions produced for a virtual KPD program under three optimization schemes: (a) Cycles and Chains, (b) Cycles and Chains with Fallbacks, (c) Locally Relevant Subgraphs.