Otimização das Rotas de Coleta de Cofres em Parquímetros

Foi proposto pela EMEL ? Empresa Municipal de Mobilidade e Estacionamento de Lisboa, E.M. S.A. o desenvolvimento de um instrumento de apoio que permitisse construir rotas para a recolha dos cofres dos parquímetros de determinadas zonas de Lisboa. A empresa pretende otimizar o seu processo de coleta tendo por base uma lógica de coleta por valor previsto para cada um dos parquímetros da cidade, como alternativa a um modelo instalado, mais geográfico (por rua), que utiliza o valor da rota para determinar a frequência de coleta (número de repetições da rota por semana ou mês, e.g.). Pretendia-se determinar rotas que permitissem a coleta dos parquímetros de maior valor, preterindo os de menor valor, poupando assim tempo e otimizando os meios humanos e técnicos. O problema exposto enquadra-se na categoria de Vehicle Routing Problems (VRP), ou seja, pretende-se gerar um conjunto de rotas, com início e término num determinado vértice, capaz de servir um conjunto de clientes sendo satisfeito um conjunto de restrições.