Ground Vehicle and UAV Collaborative Routing and Scheduling for Humanitarian logistics using Random Walk Based Ant Colony Optimization

A well-planned humanitarian logistics involving rescuing people and providing on-time lifesaving facilities to disaster-affected areas can significantly mitigate the aftermath of disasters. However, damaged bridges and blocked roads can hinder last-mile deliveries in disaster-affected areas by ground vehicles only. So, in this paper, we propose a ground vehicle (GV) and unmanned air vehicle (UAV) collaborative delivery system in such areas. Here, a fleet of homogenous ground vehicles each equipped with a certain number of UAVs is deployed for last-mile deliveries. UAVs make the flight from GVs, deliver to end locations and return to the GV for battery replacement and/or start another flight. The objective of the model is to minimize the total delivery time within UAV flight endurance and payload constraints. Firstly K-means clustering algorithm has been used to cluster the disaster-affected region into different sectors. Then GV_Touring and UAV_Routing have been scheduled using nearest neighbor heuristic to serve ground approachable locations and UAV served locations respectively. Finally, the random walk based ant colony optimization-based (ACS_RW) has been developed to further optimize the overall travel time. Experimentation results show the potential benefits of the proposed algorithm over other available truck-drone collaborative transportation models.