Formulações de Programação Linear Inteira para o Problema de Alocação Mínima de Estações de Recarga

Este trabalho estuda uma variante do Problema de Alocação Mínima de Estações de Recarga (MIN-STATION) e uma generalização dessa variante. No problema considerado, busca-se determinar um conjunto mínimo de vértices intermediários para instalação de estações de recarga que permita conduzir robôs não rotulados, com autonomia limitada, de um conjunto de origens a um conjunto de destinos. O problema é recente, NP-difícil em grafos gerais e ainda não tratado por meio de Programação Linear Inteira (PLI). Propõe-se uma formulação base em PLI, baseada em fluxo em um dígrafo de alcance. Em seguida, apresenta-se uma formulação para uma generalização que incorpora custos de instalação, autonomias heterogêneas e critérios de elegibilidade entre origens e destinos. Nos experimentos, a formulação generalizada é parametrizada para representar a versão base, permitindo comparar o desempenho das duas formulações em redes de transporte.