Combined location and routing problems in drug distribution

Mathematical programming models and algorithms have been successfully used for decades to optimize operations in distribution logistics: typical examples concern freight carriers, mail services and on-demand pick-up and delivery services. A more recent field of investigation concerns the application of similar techniques to the optimization of logistics operations in health care systems and emergency management. These sectors are characterized by a larger dependency on “human factors”, such as the behavior of the customers (which is often unpredictable), fairness in service provision (which is not an issue in industrial logistics) and lack of reliable historical data (because of the uniqueness of the events considered, especially in case of emergency management). We tackle a variation of the Vehicle Routing Problem (VRP) arising in the context of the distribution of vaccines and anti-viral drugs in case of a pandemic outbreak. The problem requires to reach the maximum number of citizens within a specified time limit. The starting point for our study is a paper by Shen et al., who presented a stochastic VRP model which is then reformulated and solved as a deterministic VRP with a tabu search algorithm. We explore the option of reaching citizens in two ways: by establishing depots, and delivering the drugs at homes using an heterogeneous fleet of vehicles, or by establishing distribution centers where the citizens go by their own means to receive treatments or drugs. In this way a particular combined location-routing problem arises. We present an exact algorithm for such a problem, which is based on column and cut generation and branch-and-bound, and where the pricing subproblem is solved through advanced dynamic programming techniques.