Machine learning approach for truck-drones based last-mile delivery in the era of industry 4.0

Abstract

Under the vision of industry 4.0, the integration of drones in last-mile delivery can transform traditional delivery practices and provide competitive advantages. However, the combinatorial nature of the routing problem and the technical limitations of the drones present a real challenge for adopting a stand-alone drone delivery as an alternative to truck delivery. This study introduces the Parking Location and Traveling Salesman Problem with Homogeneous Drones (PLTSPHD). This problem considers a scenario in which a single truck carries identical drones along with parcels from the depot to preassigned launching/parking sites, from where the drones complete the last-mile deliveries. In contrast to previous studies that tackle truck-drone delivery using conventional optimization approaches, this paper proposes a two-phase machine learning (ML) approach for the PLTSPHD, which minimizes the total operational cost of the last-mile problem. The proposed ML approach for PLTSPHD consists of clustering and routing phases. In the first phase, a constrained k-means clustering algorithm is proposed to cluster delivery locations based on the maximum flight range and number of available drones per truck. A deep reinforcement learning (DRL) model is then developed in the second stage to find an optimal route among all constrained clusters. Experimental results show that solving the presented truck-drone problem using the ML framework can significantly reduce the operational cost compared to standard truck delivery. The constrained clustering reduces the complexity of the routing problem while adhering to the constraints. In addition, the trained DRL model outperforms the state-of-art Google’s OR-tools solver and other types of well-known heuristics in terms of both solution quality and computation time. Moreover, a sensitivity analysis of different key parameters is conducted to highlight some key trade-offs in using multiple drones and their dependence on operating costs and problem sizes.