Truck‐Drone Pickup and Delivery Service Optimization With Availability Profiles

ABSTRACT The absence of customers at the time of a pickup or delivery service not only results in additional costs associated with the failed service attempt but also decreases customer satisfaction. Thus, it is crucial to account for the possible convenient times of customers when designing the pickup and delivery service scheme. With the advantages of the drone in delivery speed and transport costs, we investigate the truck‐drone pickup and delivery problem with availability profiles, in which each node has an availability profile that consists of a set of service time windows, each of which has an availability probability such that the pickup or delivery service can be carried out at the node within the time window. The pickup and delivery services are collaboratively performed by a set of trucks and drones, in which each truck carries a drone. The truck can simultaneously perform the pickup and delivery services and act as an intermediate mobile warehouse, which must wait at the parking location for the return of the drone associated with it once it has dispatched the drone for performing services. The drone can independently provide the pickup and delivery services after taking off from the truck that carries it, and finally return to the truck after finishing the services. The goal is to find the optimal collaborative service scheme of the trucks and drones with the objective of minimizing the sum of the operational cost and expected service failure cost. To solve the problem, we devise an exact branch‐and‐price‐and‐cut (BPC) algorithm that incorporates a novel column‐and‐cut generation (CCG) scheme and a specialized bi‐directional labeling algorithm based on some structural properties for the intractable pricing problem, and introduce some improvement strategies to improve the performance of the solution algorithm. The numerical studies on random instances illustrate that the developed BPC algorithm performs significantly better than the CPLEX solver and two existing BPC algorithms, in which the service time window dominance rule in the developed structural properties and the improvement strategies significantly enhance the performance of the developed BPC algorithm, and the in‐out CCG scheme can efficiently overcome the degenerate behaviors of the classical column generation and cutting‐plane methods. The numerical studies on a case study of Cainiao intra‐city online‐to‐offline order delivery highlight the benefits of the truck‐drone collaborative pattern, which achieves about 10.32% cost savings and a 3.43% service failure rate decrease on average compared to the truck‐only pattern, and quantify the potential benefits of accounting for availability profiles, which can effectively make a trade‐off between the operational cost and service failure ratio.