A vehicle routing problem for biological sample transportation in healthcare: mathematical formulations and a metaheuristic approach
Preprint
Abstract
In this paper, a real-world transportation problem is addressed, concerning the collection and the transportation of biological sample tubes from sampling points to a main hospital. Blood and other biological samples are collected in different centers during morning hours. Then, the samples are transported to the main hospital, for their analysis, by a fleet of vehicles located in geographically distributed depots. Each sample has a limited lifetime and must arrive to the main hospital within that time. If a sample cannot arrive to the hospital within the lifetime, either is discarded or must be processed in dedicated facilities called Spoke Centers.Two Mixed Integer Linear Programming formulations and an Adaptive Large Neighborhood Search (ALNS) metaheuristic algorithm have been developed for the problem. Computational experiments on different sets of instances based on real-life data provided by the Local Healthcare Authority of Bologna, Italy, are presented. A comparison on small instances with the optimal solutions obtained by the formulations shows the effectiveness of the proposed ALNS algorithm. On real-life instances, different batching policies of the samples are evaluated. The results show that the ALNS algorithm is able to find solutions in which all the samples are delivered on time, while in the real case about the 40% [5] of the samples is delivered late.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- A multi-depot dial-a-ride problem with heterogeneous vehicles and compatibility constraints in healthcareOmega, 2017
- Selective vehicle routing for a mobile blood donation systemEuropean Journal of Operational Research, 2015
- A memetic algorithm for the patient transportation problemOmega, 2015
- Hybridization of tabu search with feasible and infeasible local searches for periodic home health care logisticsOmega, 2014
- New mixed integer-programming model for the pickup-and-delivery problem with transshipmentEuropean Journal of Operational Research, 2014
- The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution methodEuropean Journal of Operational Research, 2010
- Exact and heuristic algorithms for the vehicle routing problem with multiple interdependent time windowsComputers & Operations Research, 2008
- A general heuristic for vehicle routing problemsComputers & Operations Research, 2007
- The Pickup And Delivery Problem With Time Windows And TransshipmentINFOR: Information Systems and Operational Research, 2006
- A parallel route building algorithm for the vehicle routing and scheduling problem with time windowsEuropean Journal of Operational Research, 1993