A hybrid learning model for the vehicle routing problem with drones in the era of industry 4.0
AdvisorKrishnan, Krishna K.
MetadataShow full item record
Arishi, A. 2022. A hybrid learning model for the vehicle routing problem with drones in the era of industry 4.0 -- In Proceedings: 18th Annual Symposium on Graduate Research and Scholarly Projects. Wichita, KS: Wichita State University
Under the vision of industry 4.0, the application of drones or unmanned aerial vehicles (UAV) in last-mile transportation has been capturing the attention of many logistics giants. Leaders in logistics and transportation such as Amazon, UPS, and Uber are investigating the use of drones to solve the last-mile problem. However, finding an optimal routing strategy for a truck with multiple drones is an NP-hard problem. Traditional methods suffer from a long computation time and scalability issues. In this study, we consider a different scheme of the last-mile delivery problem in which a modern truck equipped with a fleet of drones is used to deliver light parcels to a set of customer locations. In this formulation, the truck starts from the depot and visits a set of launching sites where the truck parks and drones can be deployed to make all last-mile deliveries. All drones have a limited flying range and load capacity that cannot exceed in every trip. After serving the customer, drones must return to the truck for a battery swap. Once all drones are collected, the truck moves to the next parking location and repeats the process until all customers are served. To tackle this problem, a hybrid machine learning approach for location clustering and routing decisions for last-mile delivery is proposed. The proposed hybrid model comprises two stages. We propose a constrained k-means algorithm to cluster customer locations based on the user-specified constraints in the first stage. The centroid of each constrained cluster will serve as a parking spot for the truck. In the second stage, a deep reinforcement model is trained to cover all parking spots. Using the proposed hybrid approach, the objective is to reduce the total operational cost of the truck-drones delivery problem by finding a good partition that optimizes the trade-off between the number of parking stops and the distance covered by each drone while adhering to the userspecified constraints. Extensive experiments are carried out to evaluate the effectiveness of the proposed approach. Solutions obtained are compared with other classical methods. Results show that our approach can produce quality solutions in real-time. Moreover, a sensitivity analysis of key parameters is conducted to highlight critical trade-offs in using the multiple drones and their dependence on operating costs and problem sizes.
Presented to the 18th Annual Symposium on Graduate Research and Scholarly Projects (GRASP) held at the Rhatigan Student Center, Wichita State University, April 29, 2022
Research completed in the Department of Industrial, Systems and Manufacturing Engineering, College of Engineering