An iterated local search for the biomedical sample transportation problem with multiple and interdependent pickups

Abstract

This article addresses a new version of the biomedical sample transportation problem, as a vehicle routing problem with precedence constraints arising in the context of healthcare logistics, and proposes an iterated local search algorithm to solve it. This new version is more realistic and complex since it considers the collection centres’ opening hours and the moment at which they are visited as decision variables, granting additional flexibility to elaborate more efficient routes. Indeed, this problem is harder to model and to solve than its previous version because the constraint on the short samples’ lifetime leads to interdependency between successive pickups at each collection center. A metaheuristic is thus proposed to solve real-life instances. Numerical experiments confirm (1) the value of simultaneously planning routes, opening hours, and visit hours (which is new in the literature) and (2) the efficiency of the proposed algorithm to solve this problem.

Keywords:

• VRP with interdependency
• VRP with synchronisation constraints
• VRP with interdependent time windows
• healthcare logistics
• biomedical sample transportation
• OR in healthcare services
• iterated local search

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), Discovery Grants Program [grants OPG 0293307 and OPG 0172633], the scholarship from the International research internship—Strategic Clusters Program, attributed to Ana María Anaya-Arenas, by the Fonds de recherche du Québec—Nature et technologies (FRQNT), and the financial support of the Ministère de la Santé et des Services sociaux (MSSS). This financial support is gratefully acknowledged.