Adaptive large neighbourhood search heuristic on vehicle routing problem with drones and time windows

Abstract

Last-mile deliveries are the most costly and time-consuming part of the supply chain. Advancements in drone technology resulted in cheaper and faster drones capable of parcel delivery. However, their range is quite limited for drone-only delivery. Using synchronized drones and trucks could lower costs and delivery times by combining their superior features. This thesis addresses Vehicle Routing Problem with Drones and Time Windows (VRPDTW). The problem is formulated with waiting time restrictions on drones and cost minimization objective. Due to NP-hard nature of the problem, exact solution methods are ine cient even for small instances. Therefore, we develop an Adaptive Large Neighbourhood Search (ALNS) heuristic for nding near optimal solutions. Numerical experiments are conducted to measure the e ectiveness of the heuristic using small and medium-sized instances generated randomly. Results show that the proposed heuristic is able to nd optimal or near optimal solutions in small instances.