A Multi-Objective Metaheuristic with learning capabilities for a Green UAV Grid Routing Problem
Autores
|
7031 |
44,256,3082,3081,3080,3079
|
|
|
7032 |
44,256,3082,3081,3080,3079
|
|
|
7033 |
44,256,3082,3081,3080,3079
|
|
|
7034 |
44,256,3082,3081,3080,3079
|
|
|
7035 |
44,256,3082,3081,3080,3079
|
|
|
7036 |
44,256,3082,3081,3080,3079
|
Informações:
Publicações do PESC
This paper deals with Unmanned Aerial Vehicle (UAV) routing in dynamic grid scenarios with limited battery autonomy and multiple charging stations. Inspired by a multi-criteria view of real systems, we consider different objective functions introduced in the literature, while respecting the navigation over forbidden areas and a real-time flight autonomy. A multi-objective variant of Variable Neighborhood Search is considered for finding sets of non-dominated solutions. Twelve neighborhood structures were developed in order to explore the solution space, including learning techniques. The latter stores known routes in order to speed up the search. A case of study was developed where UAVs have to serve clients spread throughout a grid, representing a map. Each UAV starts in a given grid point with a given battery charge, where the grid is composed by four different kinds of points: a regular one and three special (prohibited, recharge and client). Any update can happen on the routes on real-time, so the metaheuristic should handle real-time information and update the plan and GUI (Graphics User Interface) accordingly. Any sequence of valid adjacent points forms a route, but since this yields a huge number of combinations, a preprocessing technique is proposed to pre-compute distances in a given dynamic scenario. Computational results demonstrate the performance of different variants of the proposed algorithms.
Este artigo trata do roteamento de veículos aéreos não tripulados (VANTs) em cenários de grade dinâmica com autonomia limitada de bateria e múltiplas estações de carregamento. Inspirados em uma visão multicritério de sistemas reais, consideramos diferentes funções objetivo introduzidas na literatura, respeitando a navegação em áreas proibidas e também uma autonomia de voo em tempo real. Uma variante multi-objetiva do VNS (Variable Neighborhood Search) é considerada para encontrar conjuntos de soluções não dominadas. Doze estruturas de vizinhança foram desenvolvidas para explorar o espaço de solução, incluindo técnicas de aprendizado. Este último armazena as rotas conhecidas para agilizar a busca. Foi desenvolvido um caso de estudo em que VANTs têm que atender clientes espalhados por uma grade, representando um mapa. Cada VANT começa em um determinado ponto da grade com uma determinada carga de bateria, onde a grade é composta por quatro tipos diferentes de pontos: um regular e três especiais (representando áreas proibidas, pontos de recarga e clientes). Qualquer atualização pode acontecer nas rotas em tempo real, então a metaheurística deve lidar com informações em tempo real e atualizar o plano e a GUI (Interface Gráfica do Usuário) de acordo. Qualquer sequência de pontos adjacentes válidos forma uma rota, mas como isso produz um grande número de combinações, uma técnica de pré-processamento é proposta para pré-calcular as distâncias em um determinado cenário dinâmico. Resultados computacionais demonstram o desempenho de diferentes variantes dos algoritmos propostos.