An Iterative Exact Algorithm over a Time-Expanded Network for the Transportation of Biomedical Samples

In this article we propose an iterative algorithm to address the optimization problem of distributing a set of multiple highly perishable commodities in a healthcare network. In the biomedical sample transportation problem, numerous commodities with short lifespans presume multiple transportation requests at the same facility in a day and restrict the maximum time to reach their destination. These two characteristics create an interdependency between the routing and the pickup decisions in time that is highly complex. To address these timing issues, we model this problem as a service network design problem over a time-expanded network. Our solution method aggregates the network at two levels. First, the commodities are aggregated and artificially consolidated, reducing the symmetry arising when multiple transportation requests are solicited within a short period of time. Second, the space-time nodes in the network are constructed dynamically, thus reducing the size of the mathematical model to be solved at each iteration. Moreover, the method creates auxiliary networks to calculate good-quality primal bounds to the problem. Our algorithm proves to be efficient to solve a set of real-life instances 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) with a detailed network of up to 2,377 periods and 277 transportation requests. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This work was supported by the Natural Sciences and Engineering Research Council of Canada [Grants 2018-04609, 2020-06311]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0061 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0061 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .