On-demand heterogeneous drone delivery problem

In the on-demand problem domain, actual demand frequently deviates from the expected demand. This paper intricately delves into the exploration of on-demand heterogeneous multi-drone routing problem (ODHDRP), in which a transport drone carries multiple terminal drones to subregions in the first echelon, and the terminal drones deliver parcels during a flight trip to customers with demands in subregions to maintain economies of scale in the second echelon. We formulate the customer demands using a normal distribution, and exploit a reliability model of customer demands with chance constraints. To solve the ODHDRP efficiently, we propose a hybrid iterative optimisation heuristic (HIOH) approach. Firstly, a clustering algorithm considering the drone's payload is designed to divide the customer-region into several subregions. Subsequently, the dynamic programming algorithm is introduced to generate the initial route to each subregion. Secondly, an iterative optimisation algorithm with heuristic operators and reliability-based strategies is designed to handle the chance constraints and optimise the routes. The experiments substantiate the superior performance of the proposed method in contrast to baseline algorithms. Moreover, the sensitivity of key factors in the proposed model is analysed and several managerial insights are derived.