| dc.description.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. | en_US |
