Due to the limitation in the number of deceased and compatible live kidney donors compared to end stage renal disease (ESRD) patients, kidney paired donation (KPD) exchange programs were proposed in various countries around the world. Due to logistic and resource constraints, the maximum size of each kidney exchange cycle cannot exceed a preset limit k. The decision version of the k-cycle exchange problem is of the NP-Complete time-complexity class. Various algorithms were proposed in literature to solve the vanilla k-cycle exchange problem with no regards to assigning nephrectomy and implantation operations to transplant centers given capacity constraints, and the geographical distribution of patients, donors and transplant centers around the country and therefore the access they have to each other. Moreover, it was proposed in literature that it is medically viable to transport a kidney for long distances after nephrectomy and before implantation in the patient at another center. In this thesis, a number of compact mathematical programs and associated algorithms are proposed and benchmarked for solving the capacitated k-cycle kidney exchange problem given the geographical locations of donors, patients and transplant centers, with and without transportability of kidneys after nephrectomy. Computational experiments show that 2 formulations, namely capacitated reduced extended edge assignment (CRXEA) and capacitated reduced extended edge assignment with transportability (CRXEAT), were the most computationally efficient, for the problem variants without and with kidney transportability respectively. Moreover, the standard KPD instance generator was extended and used alongside the dominant formulations to identify the extent of benefits attainable by allowing kidneys to be transported after nephrectomy in different simulation scenarios. Computational experiments validated the merit of allowing transportability of kidneys under specific, arguably realistic scenarios.
말기 신장 질환 (ESRD) 환자와 비교하여 고인 및 호환 생존 신장 기증자의 수의 제한으로 인해 전 세계 여러 국가에서 신장 기증 (KPD) 교환 프로그램이 제안되었다. 물류 및 자원 제약 때문에 각 신장 교환주기의 최대 크기는 미리 설정된 한도를 초과 할 수 없다. k- 사이클 교환 문제의 결정 버전은 NP-Complete 시간 복잡성 클래스에 속한다. 용량 제한과 환자, 기증자 및 이식 센터의 지리적 분포를 고려할 때 이식 센터에 신장 절제술과 이식 수술을 할당하는 것과 관련없이 바닐라 k- 사이클 교환 문제를 해결하기위한 다양한 알고리즘이 문헌에서 제안되었다. 또한 신장 절제술 후 및 다른 센터의 환자에게 이식하기 전에 장거리 용으로 신장을 운반하는 것이 의학적으로 실행 가능하다는 것이 문헌에서 제안되었다. 이 논문에서는 신장 절제술 후 신장의 이동성이있는 경우와 없는 경우의 기증자, 환자 및 이식 센터의 지리적 위치를 고려한 수용성 k- 사이클 신장 교환 문제를 해결하기 위해 여러 가지 간단한 수학 프로그램 및 관련 알고리즘을 제안하고 벤치마킹한다. 시뮬레이션에 따르면 신장 수송 능력이 없는 문제에 대해 수용 능력이 감소된 확장 경계 할당 (CRXEA)과 수송 능력을 갖춘 축소 된 확장 에지 할당 (CRXEAT)이라는 두 가지 공식이 가장 계산적으로 효율적이었다. 또한 표준 KPD 인스턴스 생성기를 확장하여 다른 시뮬레이션 시나리오에서 신장 절제 후 신장을 전달함으로써 얻을 수있는 이점의 범위를 확인하기 위해 지배적 인 공식과 함께 사용했다. 마지막으로 시뮬레이션은 특정, 틀림없이 사실적인 시나리오에서 신장의 이동성을 허용한다는 장점을 입증했다.
