Integer Linear Programming for Optimizing Drone-Based Delivery Routes

Abstract

The growing demand for rapid and effcient delivery solutions, especially in healthcare and remote logistics, presents unique challenges for drone routing, including limited battery life, restricted flight zones, and the need for effcient path optimization. This paper addresses these challenges by proposing an Integer Linear Programming (ILP) model to optimize multipoint drone delivery routes. The objective of the model is to minimize total travel distance or time during drone delivery operations while ensuring that each designated delivery location is visited exactly once, with a return to the starting point. The ILP model incorporates practical constraints such as battery limitations, maximum allowable flight distance, and avoidance of no-fly zones, making it suitable for real-world drone delivery applications. Evaluation across four distinct scenarios, including urban and mixed environments, demonstrates that the ILPbased approach enhances route effciency, achieving an average reduction of approximately 25% in total travel distance compared to heuristic methods, specifically the Nearest Neighbor (NN) heuristic. Moreover, it outperforms metaheuristic methods like Genetic Algorithm (GA) and Ant Colony Optimization (ACO) in both distance effciency and adherence to constraints. The ILP model demonstrates computational feasibility, solving problems with up to 50 delivery points in approximately 3 minutes on average. These findings highlight the potential of the ILP framework as a robust tool for optimizing drone delivery networks, offering significant improvements in operational effciency and scalability.