Capacitated Drone Routing Problem With Time Windows And Scheduled Lines: Mathematical Formulation And Metaheuristic Approach

Abstract

The rise of e-commerce has led to both opportunities and challenges for last-mile delivery services, requiring companies and logistic providers to invest in more efficient and energy-efficient last-mile delivery systems. In recent years, many large companies have adopted drones as the new delivery vehicle and many projects have proven the potential of the drone’s delivery system, especially in urban areas. However, the implementation of drone-based delivery systems has not been widely adopted, partially due to the lack of an effective and comprehensive operation framework. This study is dedicated to investigating the Vehicle Routing Problem in a new problem setting, which considers the integration of a public transportation system into the drone-based last-mile delivery system. The problem is called Capacitated Drone Routing Problem with Time Windows and Scheduled Lines (CDRP- TW-SL). A mathematical based on the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) is developed to solve this problem. Due to the complexity of the problem, which is NP-hard, a Large Neighborhood Search (LNS) metaheuristic is proposed to solve the CDRP-TW-SL. Complex constraints such as scheduled lines, departure time, drone energy and time window are comprehensively considered in the proposed algorithm. Especially, a greedy initialize heuristic is developed to create the feasible initial solution to the problem, as an input for the LNS algorithm. Results from computational experiments show that the mathematical model can be effectively used to solve small-size instances using exact methods. The greedy initial heuristic is proven to be effective in solving from small (5- 10 customers) to medium (20 – 50 customers) and large (100 customers) instances. Although the performance of the LNS algorithm has not been stable enough to get optimal solution, it performs well in reducing computational time to find an acceptable objective value compared to the exact method solution.