Heuristicas e Metaheuristicas - p-Medianas

Heur´ısticas e Metaheur´ısticas para o Problema das

p-Medianas Capacitado

Hercules da Costa Sandim1

1Faculdade de Computac¸ao˜ – Universidade Federal de Mato Grosso do Sul do Sul (UFMS) Cidade Universitaria´ - 79.070-900 – Campo Grande – MS – Brasil

[e-mail]

Abstract. This article is a technical survey report on the classical p-Medians problem (PMP). This is a classic problem in Operations Research and Appli-cation in Logistics and may be characterized by a graph containing n vertices (or customers), of which we choose p, medians or facilities, with the objective of minimizing the total distance between each median and their immediate cus-tomers. The aim of this paper is to present: a review of the literature, heuristics and metaheuristics able to return viable solutions close to the optimal solution with acceptable runtime.

Key words: p-Medians, Greedy Algorithms, Heuristics, Local Search, Metaheu-ristics, Genetic Algorithms

Resumo. Este artigo e´ um relatorio´ tecnico´ de pesquisa sobre o Problema das p-Medianas nao˜ capacitado (PPM). Este e´ um problema classico´ na Pesquisa Operacional e com aplicac¸ao˜ em Log´ıstica, podendo ser caracterizado por um grafo contendo n vertices´ (ou clientes), dos quais devemos escolher p, deno-minados medianas ou instalac¸oes,˜ com o objetivo de minimizar a distanciaˆ total entre cada mediana e seus clientes mais proximos´. O objetivo deste ar-tigo e´ apresentar: o estado da arte deste problema e heur´ısticas construti-vas, heur´ısticas de busca local e metaheur´ısticas capazes de retornar soluc¸oes˜ viaveis,´ proximas´ a` soluc¸ao˜ otima,´ com tempo de execuc¸ao˜ admiss´ıvel.

Palavras-chave: p-Medianas, Algoritmos Gulosos, Heur´ısticas, Busca Local, Metaheur´ısticas, Algoritmos Geneticos´

1. Introduc¸ao˜

O problema de p-Medianas e´ um problema classico´ de localizac¸ao˜. O objetivo e´ de-terminar os locais de p facilidades (denominadas medianas) em uma rede de n nos,´ de modo a minimizar a soma das distanciasˆ entre cada no´ de demanda e a mediana mais proxima´. O problema de p-Medianas tem grande importanciaˆ pratica´ como, por exem-plo, na localizac¸ao˜ de escolas [Pizzolato et al. 2004] e de antenas de telecomunicac¸ao˜ [Lorena and Pereira 2002].

O Problema das p-Medianas pode ser classificado em capacitado (PPM) ou nao˜ capacitado (PPMN). O foco deste artigo esta´ no Problema das p-Medianas nao˜ capacitado. Neste problema o objetivo e´ escolher, dentre n vertices´ de um grafo, um conjunto de p vertices´ denominados medianas, de modo a minimizar a soma das distanciasˆ de cada vertice´ restante ate´ a mediana mais proxima´. O problema e´ dito nao˜ capacitado porque cada mediana possui capacidade ilimitada para o atendimento aos pontos de demanda. Na

---

versao˜ capacitada deste problema (nao˜ tratada neste artigo), para cada vertice´ mediana do grafo e´ associada uma capacidade maxima´. Assim, a soma das demandas de todos os vertices´ cobertos por uma mediana nao˜ deve ultrapassar a capacidade de atendimento da mesma [Lorena et al. 2001].

O PPM e´ considerado NP-Dif´ıcil [Kariv and Hakimi 1979] e ha´ diversos metodos´ que podem ser utilizados para sua resoluc¸ao˜. Dentre eles ha´ metodos´ exatos, heur´ısticos e metaheur´ısticos. Os metodos´ exatos encontram a soluc¸ao˜ otima´ do problema. Porem,´ o tempo computacional exigido pode nao˜ ser viavel,´ dependendo do tamanho da instanciaˆ. As heur´ısticas, apesar de nao˜ garantirem a obtenc¸ao˜ da soluc¸ao˜ otima,´ sao˜ capazes de resolver problemas de grande porte, retornando soluc¸oes˜ satisfatorias´ em tempo compu-tacional viavel´. Ja´ as metaheur´ısticas sao˜ heur´ısticas que apresentam mecanismos que as permitem escapar de otimos´ locais [Amorim et al. 2011].

Varias´ heur´ısticas e metaheur´ısticas temˆ sido propostas para estes problemas. Osman e Christofides [Osman and Christofides 1994], propuseram uma soluc¸ao˜ h´ıbrida com Simulated Annealing e Tabu Search. Maniezzo et al. [Maniezzo et al. 1998] apresentaram um algoritmo bionomicoˆ (tecnica´ que substitui a aleatoriedade dos ope-radores dos Algoritmos Geneticos´ por procedimentos normalizados). Lorena e Senne [Lorena and Senne 2004] exploraram heur´ısticas de busca local baseadas em procedi-mentos de localizac¸ao/alocac˜¸ao˜. Diaz e Fernandez´ [D´ıaz and Fernandez 2006] explo-ram uma soluc¸ao˜ h´ıbrida com Scatter Search e Path-Relinking. Osman e Ahmadi [Osman and Ahmadi 2007] investigaram uma linha para a construc¸ao˜ de metaheur´ısticas baseadas no uso de buscas locais ou GRASP (Greedy Randomized Adaptive Search Pro-cedure) e Fleszar e Hindi [Fleszar and Hindi 2008] apresentaram uma estrategia´ eficiente utilizando VNS (Variable Neighborhood Search).

Este artigo e´ um relatorio´ tecnico´ que apresenta algumas heur´ısticas e me-taheur´ısticas para a soluc¸ao˜ aproximada do PPM. Na Sec¸ao˜ 2 sao˜ apresentadas as ca-racter´ısticas do PPM, com a definic¸ao˜ e a formulac¸ao˜ matematica´ do problema. Na Sec¸ao˜ 3 sao˜ apresentadas duas heur´ısticas construtivas presentes na literatura para o PPM e al-gumas alterac¸oes˜ propostas por este artigo. Na Sec¸ao˜ 4 sao˜ apresentadas duas estrategias´ de busca local presentes na literatura para o PPM. Na Sec¸ao˜ 5 sao˜ apresentadas duas me-taheur´ısticas para o PPM e na Sec¸ao˜ 6, o artigo descreve os resultados obtidos atraves´ de experimentos realizados com os algoritmos apresentados nas sec¸oes˜ anteriores.

2. O Problema das p-Medianas

Em geral, um problema de otimizac¸ao˜ combinatoria´ pode ser expresso como:

[pic 1]

onde f (x) e´ a func¸ao˜ objetivo a ser minimizada e X e´ o conjunto de todas as soluc¸oes˜ poss´ıveis do problema. Uma soluc¸ao˜ x* e´ chamada soluc¸ao˜ otima´ quando:

[pic 2]

Dado um grafo completo e nao˜ orientado G = (V,E), em que V e´ o conjunto dos n vertices´ do grafo e E e´ o conjunto das arestas que representam as distanciasˆ entre os

---

vertices,´ deve-se encontrar um conjunto Vp V com cardinalidade p, em que Vp repre-senta o conjunto das medianas do problema, de modo que a soma ponderada das distanciasˆ de cada vertice´ restante em V - Vp ate´ o vertice´ mais proximo´ em Vp seja a m´ınima poss´ıvel.