Logistics of clinical testing

Abstract

Sağlık hizmetlerinde, tanılayıcı ve tedavi edici önemli kararlar genellikle klinik testlerinsonuçlarına dayanır. Klinik laboratuvarlar, hastalardan toplanan numunelerineşgüdümlü olarak toplanma, taşınma, ve işlenmesi ile testlerin zamanında ve hatasızgerçekleştirilmesini hedefler. Bu tezde, klinik laboratuvarlarda gözlenen numunetoplama problemi ele alınmıştır. Bu problemde, coğrafi olarak dağınık lokasyonlardazaman içerisinde biriken numunelerin sınırlı işleme kapasitesine sahip ekipmanlaişlenmek üzere merkezi bir tesise taşınması gerekmektedir. Ortaya çıkan rotalama veçizelgeleme problemi, işleme için toplama problemi (Collection for Processing Problem? CfPP) olarak adlandırılmıştır. Problemin başlıca özellikleri analiz edilmiş,doğrusal karma tamsayılı programlama (KTP) modeli geliştirilmiş, ve sezgisel çözümyöntemleri tasarlanmıştır.Çok araçlı problem tüm birimlerinin işlenmesinin bitiş süresinin enküçüklenmesi(makespan) amaç fonksiyonu ile çalışılmış ve polinom zamanlı, sabit faktörlü biryaklaşıklama algoritması geliştirilmiştir. Tek araçlı problem iki sıradüzenli amaçfonksiyonu ile çalışılmıştır. Bu problemde, birincil amaç, verilen zaman sınırına kadarişlenen miktarı enbüyüklemek iken; ikincil amaç, taşıma maliyetlerini enküçüklemektir.Problemin çözümü için iki sezgisel yöntem geliştirilmiştir. İllk yöntem, bazı belirginözelliklere sahip uygun çözümleri aramaya yönelik bir KTP modelinin çözülmesinedayanmaktadır. İkincisi ise, tabu arama yöntemi ile doğrusal programlamayı birleştirenönceliklendirilmiş iki kriterli bir sezgi ötesi yöntemdir. Önerilen sezgisel yöntemlerinperformansını ölçmek amacıyla, zaman sınırına kadar işlenen miktar için bir üst sınır bulmayöntemi ve taşıma maliyetleri için alt sınır bulan iki gevşetilmiş KTP modeligeliştirilmiştir. Aynı zamanda, önerilen sezgisel yöntemlerin etkinliği gerçekçi problemörnekleri üzerinde gösterilmiştir. Ayrıca, sayısal deneyler ile kilit problem parametreleriüzerinde öngörüler ve bunların çözümler üzerindeki etkileri çıkartılmıştır.

In the delivery of healthcare services, important diagnostic and therapeutic decisions areoften based on the results of clinical tests. Clinical testing laboratories aim to achieve timelyand error free processing of the tests by means of coordinated collection, transportation,and processing of the specimens obtained from the patients. This thesis addresses thespecimen collection problem that clinical testing laboratories face daily. In this problem,specimens that accumulate throughout the working day at customer sites should betransported to a facility for subsequent processing on equipment with limited capacity.We formalize the resulting routing and scheduling problem as collection for processingproblem (CfPP). We analyze several fundamental properties of the problem, develop alinear mixed integer programming (MIP) model, and propose a number of heuristicapproaches to identify effective collection strategies.For the multi-vehicle problem with the makespan objective, we develop a polynomial-time,constant-factor approximation algorithm. We study the single vehicle problem with twohierarchical objectives. The first-level objective is to maximize the processed amount bya deadline, whereas the second-level objective is to minimize transportation costs. Wepropose two heuristic approaches to address the single vehicle problem. The firstapproach solves the MIP model with additional constraints to obtain feasible solutionswith specific characteristics. The second approach is a prioritized bicriteria matheuristicthat combines tabu search with linear programming. To evaluate the performance of theseapproaches, we provide an upper bounding scheme on the processed amount by a deadline,and two relaxed MIP models to generate lower bounds on the transportation cost.The effectiveness of the proposed solution approaches is evaluated using realistic probleminstances. Insights on key problem parameters and their effects on the solutions areextracted by further experiments.