The collection and transport of biomedical samples represents a major challenge in hospital logistics. Hospitals, clinics or collection centers, generate every day thousands of samples that must be transported to laboratories to be analyzed. Since samples deteriorate rapidly in the uncontrolled environmental conditions of transport, the authorities have set to three hours the maximum time that any sample can pass between the time it leaves its collection point and its arrival at the laboratory. This constraint, along with the time windows and multiple visits required by the collection centers, greatly complicate this vehicle routing problem. Anaya Arenas et al. 2015 proposed two mathematical models and fast heuristics to solve the biomedical samples’ transportation problem, but it remained far too complex to be solved to optimality for real-life sized instances. In this paper we propose a high-performance multi-start algorithm which regularly reached the optimum on medium-sized problems and improved the best known solutions for several larger-sized problems.

Keywords