Exact solution method for vehicle-and-drone cooperative delivery routing of blood products

Blood products, such as platelets, play a major role in saving and maintaining lives, and preventing and treating diseases, which need timely delivery. To achieve cost-efficient and fast deliveries, integrating unmanned aerial vehicles (or drones) into blood product distribution network design provides a competitive advantage, which however increases the operational challenges. We address the vehicle -and -drone cooperative delivery routing problem where a fleet of blood transport vehicles, each of which carries a given number of homogeneous drones, are deployed to collaboratively deliver blood products from a blood centre to a set of hospitals. To take advantage of the drone fleet, some or all of the drones associated with a vehicle can be simultaneously dispatched to make deliveries to nearby hospitals when the vehicle is parked at an intermediate movable depot (a hospital cluster centre), where the drones can set off from and land on the vehicle. The goal is to find the collaborative routes of the vehicle -drone combinations to minimize the sum of the assignment cost, the transport cost, and the total disutility of blood product delivery. We devise an exact algorithm for solving the problem in the framework of the integer L-shaped method, which decomposes the problem into a Benders master problem and a Benders subproblem. The Benders master problem determines which hospitals are served as cluster centres, and which hospitals are assigned to each cluster centre that will be served by drones. The resulting Benders subproblem reduces to a capacitated vehicle routing problem with time window that is solved by a branch -and -price algorithm to identify Benders optimality and feasibility cuts, and the found cuts are incorporated into the Benders master problem to guide the solution process. We perform extensive computational experiments to verify the computation efficiency of the algorithm, ascertain the benefit of vehicle -and -drone cooperative delivery over vehicle -only delivery, and analyse the sensitivity of key parameters. We also show how our model would perform should it be used for blood product delivery in the Blood Centre of Chongqing, China.