The penalty-free heterogeneous p-median problem: formulations and algorithms
Problema das p-medianas Heterogêneo, Segmentação de Consumidores, Otimização Combinatória.
Apresenta-se neste trabalho uma nova formulação para o Problema das p-medianas Heterogêneo (HPM), proposto para recuperar a estrutura de categorias presente em dados oriundos de uma tarefa de classificação (sorting task). Esta nova formulação é denominada Problema das p-medianas Heterogêneo Livre de Penalidade (PFHPM), uma versão convexa e mono-objetivo do HPM, na qual seu principal parâmetro é eliminado. Este parâmetro, um fator de penalidade, é responsável pela ponderação dos elementos de sua função objetivo. O ajuste deste parâmetro tem influência no modo como o modelo original recupera a estrutura de categorias, dependendo de conhecimento prévio acerca do problema para que este não gere classificações errôneas. Neste trabalho, ainda, duas formulações complementares são apresentadas para o PFHPM, a partir das quais pôde-se obter limitantes inferiores otimistas para o problema. No contexto desta pesquisa, estes limitantes são utilizados para validar um algoritmo de Busca em Vizinhança Variada (VNS) proposto para resolver o PFHPM. Este algoritmo mostrou-se eficiente, obtendo soluções de boa qualidade para o problema, tanto para instâncias geradas por Simulação de Monte Carlo quanto para dados reais, a um custo computacional baixo. As estatísticas mostradas neste trabalho sugerem que o novo algoritmo e a nova formulação do HPM apresentam maior precisão que o modelo original, tanto na recuperação da estrutura de categorias quanto na percepção heterogênea da informação. Finalmente, um exemplo de aplicação do PFHPM é mostrado, assim como alguns direcionamentos futuros, propondo-se a extensão da nova formulação apresentada a ambientes fuzzy.