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

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 inefficient even for small instances. Therefore, we develop an Adaptive Large Neighbourhood Search (ALNS) heuristic for finding near optimal solutions. Numerical experiments are conducted to measure the effectiveness of the heuristic using small and medium-sized instances generated randomly. Results show that the proposed heuristic is able to find optimal or near optimal solutions in small instances.