Real-time coordinated vehicle-drone path planning for urban healthcare delivery services

Abstract

Drone-assisted delivery applications in healthcare services have been implemented/tested in various cities. To support drone-assisted healthcare delivery applications, this paper examines the real-time path-planning problem for a heterogeneous fleet of drones and trucks, given a set of depots respectively hosting a fleet of parallel-working trucks and drones. We consider both deterministic scheduled demand and dynamic new demand, and optimise the routing and scheduling for the truck-drone fleets in real-time. We introduce a rolling horizon framework, where the demand information and the status of the drones and the trucks are updated at each epoch as new demands emerge. The operator can re-optimise the routing and scheduling of all vehicles (including en-route vehicles) to meet demand as far as possible and save operating cost. To tackle this problem, we develop a mixed-integer linear programming model that allows multi-visit and multi-trip in a journey of a planning horizon for the drones and trucks. The model also considers the decision on service split (among vehicles) at demand sites to address the payload capacity limitation of a single drone or a single truck. A tailored Adaptive Large Neighborhood Search (ALNS) heuristic is then developed to efficiently solve large-scale instances in computationally tractable time. We also conduct a large-scale case study based on Hong Kong blood product delivery instances to showcase the applicability of the proposed approach, as well as the impact of the number of dynamic demands generated in a planning period and their spatial distribution features on the cost outcomes.