A fix-and-optimize variable neighborhood search for the biomedical sample transportation problem

Biomedical tests play a crucial role in helping physicians to make accurate diagnoses. To perform these tests, thousands of samples are daily transported from several healthcare facilities, where they are collected from patients, to laboratories, where they are analyzed. We consider the challenging Biomedical Sample Transportation Problem (BSTP), which is a complex variant of the vehicle routing problem with time windows, where both the number of visits and the opening and closing hours of the collection centers are decision variables, while the objective is to minimize the total duration of routes. We propose a linear programming formulation for the BSTP, and we develop a matheuristics to solve the problem in real-size problem instances, which consists of a decomposition coupled with a Variable Neighborhood Search (VNS) algorithm. The decomposition is based on a spatio-temporal clustering method, which takes into account both the travel times between the centers and their collection periods; then, a Fix-and-Optimize VNS is applied to improve the decomposed solution. The performance of the proposed method is assessed over a large number of realistic instances, which are based on the laboratory network in the Province of Québec, Canada. Results show good quality solutions and the capability of the matheuristics to solve real-size problem instances within an adequate time.