Adaptive ant colony optimization for solving dynamic vehicle and drone routing with time window constraints
摘要
This paper proposes a novel extension to the traditional Vehicle Routing Problem by introducing the Dynamic Vehicle Routing Problem with Drone considering Time Windows. This new problem incorporates dynamic request handling and the innovative use of drones to address delivery challenges within specific time constraints. To tackle Dynamic Vehicle Routing Problem with Drone considering Time Windows, we develop an adaptive Ant Colony Optimization algorithm. In which, initial routes are constructed to handle known requests, establishing a baseline solution. The algorithm adapts to real-time requests in the dynamic phase by transferring pheromone values between time steps to find the best solutions at each iteration. This mechanism effectively exploits past solutions and explores high-quality routes for new requests with strict time windows. Our proposed algorithm is validated through extensive experimental scenarios that simulate various spatial distributions and time-sensitive demands. Results show that our method produced high-quality solutions compared to existing heuristics and nature-inspired methods, particularly in complex environments with random requests and tight time constraints.