Iterative time-decomposition matheuristic for the biomedical sample transportation problem

This paper proposes an iterative time-decomposition matheuristic for solving the biomedical sample transportation problem (BSTP), which is a routing problem with multiple and interdependent visits in the context of healthcare services. In this problem, each healthcare or specimen collection center collects biomedical samples from individuals. Because the lifespan of a specimen lasts only a few hours from collection to analysis, several collection centers must be visited more than once a day to collect the specimens and ensure that they are analyzed before perishing. Setting a maximum time to analyze the samples imposes a time interdependency between visits to the same center and the maximum duration of their corresponding routes. This is a complex routing problem, and commercial solvers have been inefficient at solving it. Hence, we propose an algorithm that uses a time-decomposition technique to reduce the interdependency and apply a Fix-&-Optimize technique to solve the problem efficiently. The matheuristic proves to be efficient in solving a set of real-life instances with high interdependency requirements from the Quebec laboratory network under the management of the Ministère de la Santé et des Services sociaux (Ministry of Health and Social Services)