A dynamic programming labeling algorithm to optimize the transportation of organs for transplantation

Abstract

When an organ becomes available for transplantation, a recipient must be selected, and, since donor and recipient are sometimes geographically apart, the transportation of the organ must be planned and executed within the time window imposed by the maximum preservation time of the organ, which can impact recipient selection. Reducing the time elapsed between the surgical removal of the organ and its transplantation, known as the Cold Ischemia Time - CIT, significantly improves transplantation outcomes. Therefore, in order to minimize CIT, air transportation is generally the best option, and sometimes the only mode able to deliver the organ before perishing. Planning the transportation of an organ means choosing among thousands of possible sequences of flights, the one that delivers the organ as fast as possible to its destination. This problem can be modeled as a resource constrained shortest path. Given the urgency and importance of this task, which is solved manually in Brazil, this Thesis presents a labeling algorithm to find the optimal sequence of flights. Computational tests performed on 25 Brazilian real cases showed a reduction, on average, of 37,46% for the CITs and 44,17% for the transportation times.