Guided Genetic Algorithm for Solving Capacitated Vehicle Routing Problem With Unmanned-Aerial-Vehicles

Abstract

This study proposes a capacitated vehicle routing problem (CVRP) approach to optimise Vehicle Routing Problem (VRP) and pesticides spraying. The VRP consists of finding the route which covers every point of a certain area of interest. This paper considers a search and pesticides spraying mission, using group of Unmanned Aerial Vehicles (UAVs). In this scenario, the objective is to minimise the total battery consumption level and tank consumption level to not exceed their maximum battery and tank capacities. A hybrid metaheuristic optimisation algorithm is formulated by integrating Genetic Algorithm (GA) with a guided local search algorithm called guided genetic algorithm (GGA). The performance of the proposed GGA algorithm is compared to four single-solution based metaheuristic algorithms (Guided Local Search [GLS], Tabu Search [TS], Simulated Annealing [SA], and Iterated Local Search [ILS]) and two population-based metaheuristics algorithms (GA and Particle Swarm Optimisation [PSO] algorithm). The results revealed that the proposed GGA outperformed the other algorithms in most instances. GGA showed competitive results, closely following the TS’s performance across different scenarios. The evaluation of GGA is conducted by analysing its mean, standard deviation, best solution, and worst solution of ten iterations. In addition, Wilcoxon signed-rank test is conducted across a total of 36 instances. The optimisation results and discussion provide confirmation that the proposed GGA method beat the compared algorithms.

Keywords

• Capacitated vehicle routing problem
• genetic algorithm
• guided local search
• path planning
• UAV