The hybrid vehicle-drone routing problem for pick-up and delivery services

This paper presents a mathematical formulation and efficient solution methodology for the hybrid vehicle-drone routing problem (HVDRP) for pick-up and delivery services. The problem is formulated as a mixed-integer program, which minimizes the vehicle and drone routing cost to serve all customers. The formulation captures the vehicle-drone routing interactions during the drone dispatching and collection processes and accounts for drone operation constraints related to flight range and load carrying capacity limitations. A novel solution methodology is developed which extends the classic Clarke and Wright algorithm to solve the HVDRP. The performance of the developed heuristic is benchmarked against two other heuristics, namely, the vehicle-driven routing heuristic and the drone-driven routing heuristic. A set of experiments are conducted to evaluate the performance of the developed heuristics and to illustrate the capability of the developed model in answering a wide variety of questions related to the planning of the vehicle-drone delivery system.