The multi-trip vehicle routing problem with increasing profits for the blood transportation: An iterated local search metaheuristic

Abstract

This paper studies a multi-trip routing problem of a shuttle fleet to transport blood units from collection sites to a blood center. In this problem, the blood units intended to produce platelets and cryoprecipitate must be processed within eight hours from their donation and arrive at the blood center at a time less than its closing time to guarantee enough processing time. Since it is assumed that blood units are donated at a collection site following a constant ratio over its operating hours, this problem is modeled as a multi-trip vehicle routing problem with increasing profits for which a mixed-integer linear programming formulation is proposed. A hybrid iterated local search metaheuristic and an extended version are developed as solution methods. The extended version includes a mixed-integer linear programming component into the local search of the hybrid metaheuristic to optimize the decision on the departure times of the trips. The solution methods are tested on a new set of instances based on the blood collection system of Bogota, Colombia.

Este artículo estudia un problema de rutas de viajes múltiples de una flota de lanzaderas para transportar unidades de sangre desde los sitios de recolección hasta un centro de sangre. En este problema, las unidades de sangre destinadas a producir plaquetas y crioprecipitado deben procesarse dentro de las ocho horas siguientes a su donación y llegar al centro de sangre en un horario inferior a su hora de cierre para garantizar un tiempo de procesamiento suficiente. Dado que se supone que las unidades de sangre se donan en un sitio de recolección siguiendo una proporción constante durante sus horas de operación, este problema se modela como un problema de ruta de vehículos de viajes múltiples con ganancias crecientes para el cual se propone una formulación de programación lineal entera mixta. Como métodos de solución se desarrollan una metaheurística de búsqueda local iterada híbrida y una versión extendida. La versión extendida incluye un componente de programación lineal entera mixta en la búsqueda local de la metaheurística híbrida para optimizar la decisión sobre los horarios de salida de los viajes. Los métodos de solución se prueban en un nuevo conjunto de instancias basadas en el sistema de recolección de sangre de Bogotá, Colombia.