Optimizing specimen collection for processing in clinical testing laboratories

We study the logistics of specimen collection for a clinical testing laboratory that serves sites dispersed in an urban area. The specimens that accumulate at the customer sites throughout the working day are transported to the laboratory for processing. The problem is to construct and schedule a series of tours to collect the accumulated specimens from the sites throughout the day. Two hierarchical objectives are considered: (i) maximizing the amount of specimens processed by the next morning, and (ii) minimizing the daily transportation cost. We show that the problem is NP-hard and formulate a linear Mixed Integer Programming (MIP) model to solve the bicriteria problem in two levels. We characterize properties of optimal solutions and develop a heuristic approach based on solving the MIP model with additional constraints that seeks for feasible solutions with specific characteristics. To evaluate the performance of this approach, we provide an upper bounding scheme on the daily processed amount, and develop two relaxed MIP models to generate lower bounds on the daily transportation cost. The effectiveness of the proposed solution approach is evaluated using realistic problem instances. Insights on key problem parameters and their effects on the solutions are extracted by further experiments.