Drone Arc Routing Problems and Metaheuristic Solution Approach

Abstract

The drone arc routing problem (DARP) is one of the arc routing problems (ARPs) that has been studied by researchers recently. Unlike traditional ARPs, drones can travel directly between any two points in the graph. Due to the flexibility of drones, it is possible to use edges not defined in the graphs when deadheading the edges. This advantage of drones makes this problem more challenging than any other ARP. With this study, the energy capacities of drones are considered in a DARP. Thus, a novel DARP called the drone arc routing problem with deadheading demand (DARP-DD) is addressed in this study. Drone capacities are used both when servicing the edges and when deadheading the edges in the DARP-DD. A special case of the DARP-DD, called the multiple service drone arc routing problem with deadheading demand (MS-DARP-DD), is also discussed, where some critical required edges may need to be served more than once. To solve these challenging problems, a simulated annealing algorithm is used, and the components of the algorithm are designed. Additionally, novel neighbor search operators are developed in this study. The computational results show that the proposed algorithm and its components are effective and useful in solving the DARP-DD and MS-DARP-DD.

Keywords

• capacitated arc routing problem
• drone arc routing problem
• deadheading demand
• multiple service
• simulated annealing algorithm