Drones are a promising alternative to use instead of trucks in last-mile deliveries of small packages in urban environments due to their increased mobility and lower greenhouse emissions. To explore the usage of drones to deliver small packages in a 3D environment, an any-time solver for the problem was developed. The solver uses the metaheuristic adaptive large neighbourhood search to iteratively attempt to improve an existing solution that was found using prioritised planning on a scenario problem. To find delivery routes in environments of up to a size of 350 times 350 times 30 meters that is filled with randomly generated rectangular buildings, two search algorithms, Lazy-Theta* and A* with a simple drone collision avoidance algorithm were used. While considering a drone’s flight speed, current battery, carrying capacity, desired minimum distance to other drones, and delivery deadlines for each delivery, it was found that solutions in parts of fictional cities were possible to achieve and that the best performing heuristic utilised a delivery route’s delay and cost, leading to the highest improvement rate (defined as the percentage of iterations that improved the current solution) of 38.46% among all scenarios. The use of multiple heuristics performed better than using single heuristics even though the greatest improvement rate of a single heuristic is 38.10% and was achieved by the Delay heuristic in a larger scenario. It was noted that seeing improvements in a solution became more common when a scenario contained more deliveries and when the number of re-planned deliveries in each iteration was roughly equal to eight. Unlike the improvement rates, the overall improvement of a solution’s cost was small and often none regardless of scenario and chosen heuristics. In addition, the solver has performance issues which meant that up to 1800 iterations could be evaluated on small scenarios and environments with a budget of up to four minutes and in larger scenarios, a budget of up to 16 minutes could evaluate as few as 20 iterations. The results show that it is possible to use drones to deliver packages in a 3D environment but that more work is needed to obtain better solutions.