LuisHenriquePauletiMendes …repositorio.unicamp.br/.../Mendes_LuisHenriquePauleti_M.pdf · 2020. 2. 17. · Ficha catalográfica Universidade Estadual de Campinas Biblioteca do Instituto

Universidade Estadual de CampinasInstituto de Computação

INSTITUTO DECOMPUTAÇÃO

Luis Henrique Pauleti Mendes

Um problema de distritamento aplicado à antecipaçãodo faturamento em redes de serviço

CAMPINAS2019


Um problema de distritamento aplicado à antecipação dofaturamento em redes de serviço

Dissertação apresentada ao Instituto deComputação da Universidade Estadual deCampinas como parte dos requisitos para aobtenção do título de Mestre em Ciência daComputação.

Orientador: Prof. Dr. Fábio Luiz UsbertiCoorientador: Prof. Dr. Celso Cavellucci

Este exemplar corresponde à versão final daDissertação defendida por Luis HenriquePauleti Mendes e orientada pelo Prof. Dr.Fábio Luiz Usberti.

CAMPINAS2019

Ficha catalográficaUniversidade Estadual de Campinas

Biblioteca do Instituto de Matemática, Estatística e Computação CientíficaAna Regina Machado - CRB 8/5467

Mendes, Luis Henrique Pauleti, 1992- M522p MenUm problema de distritamento aplicado à antecipação do faturamento em

redes de serviço / Luis Henrique Pauleti Mendes. – Campinas, SP : [s.n.], 2019.

MenOrientador: Fábio Luiz Usberti. MenCoorientador: Celso Cavellucci. MenDissertação (mestrado) – Universidade Estadual de Campinas, Instituto de

Computação.

Men1. Otimização combinatória. 2. Programação linear inteira. 3. Meta-

heurística. I. Usberti, Fábio Luiz, 1982-. II. Cavellucci, Celso, 1951-. III.Universidade Estadual de Campinas. Instituto de Computação. IV. Título.

Informações para Biblioteca Digital

Título em outro idioma: A districting problem applied to billing anticipation in utilitiesnetworksPalavras-chave em inglês:Combinatorial optimizationInteger linear programmingMetaheuristicÁrea de concentração: Ciência da ComputaçãoTitulação: Mestre em Ciência da ComputaçãoBanca examinadora:Fábio Luiz Usberti [Orientador]Pedro Henrique Del Bianco HokamaCid Carvalho de SouzaData de defesa: 09-09-2019Programa de Pós-Graduação: Ciência da Computação

Identificação e informações acadêmicas do(a) aluno(a)- ORCID do autor: https://orcid.org/0000-0001-9748-1186- Currículo Lattes do autor: http://lattes.cnpq.br/4530600301213679

Powered by TCPDF (www.tcpdf.org)

Universidade Estadual de CampinasInstituto de Computação

INSTITUTO DECOMPUTAÇÃO


Um problema de distritamento aplicado à antecipação dofaturamento em redes de serviço

Banca Examinadora:

• Prof. Dr. Fábio Luiz UsbertiInstituto de Computação - UNICAMP

• Prof. Dr. Pedro Henrique Del Bianco HokamaInstituto de Matemática e Computação - UNIFEI

• Dr. Dr. Cid Carvalho de SouzaInstituto de Computação - UNICAMP

A ata da defesa, assinada pelos membros da Comissão Examinadora, consta noSIGA/Sistema de Fluxo de Dissertação/Tese e na Secretaria do Programa da Unidade.

Campinas, 09 de setembro de 2019

Agradecimentos

Gostaria de expressar minha gratidão a todos que, direta ou indiretamente, contribuírampara a concretização deste projeto. Meus sinceros agradecimentos:

• à minha família, em especial aos meu pais, Iluir e José, por apoiarem a minhadecisão de seguir a carreira acadêmica;

• aos meus professores, em especial aos meus orientadores, Prof. Fábio e Prof. Celso,por todo o conhecimento que me foi passado e por acreditarem no meu potencial;

• ao Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq), porfomentar este projeto.

Resumo

Neste projeto de pesquisa é investigado o Problema de Distritamento Econômico e Ca-pacitado (CEDP), que tem como objetivo encontrar em um grafo não-orientado e conexosubconjuntos de arestas que definam distritos conexos, balanceados, que respeitem umacapacidade máxima e maximizam o lucro. A motivação deste trabalho consiste na aplica-ção prática do CEDP para empresas que administram redes de distribuição de serviços;em particular, no processo de definição dos distritos para a leitura do consumo de seusclientes.

São apresentadas duas formulações matemáticas para o CEDP e são propostas meto-dologias para resolvê-lo. As metodologias exatas são baseadas nos paradigmas Branch-and-Bound (B&B) e Branch-and-Cut (B&C). Dada a complexidade do problema, tambémsão propostas metodologias heurísticas baseadas no GRASP e na relaxação Lagrangiana.

Com o intuito de avaliar as metodologias propostas, foram realizados experimentoscomputacionais em um benchmark de instâncias do CEDP. Analisando os resultados,pode-se notar que a metodologia GRASP obteve um bom desempenho, enquanto que aheurística Lagrangiana, que não convergiu, obteve um desempenho ruim.

Abstract

In this research project the Capacitated and Economic Districting Problem (CEDP) isinvestigated, which aims to find in a undirected connected graph subsets of edges definingconnected and balanced districts that respect a maximum capacity and maximize theprofit. The motivation of this work consists in the practical application of CEDP forutilities; particularly, in their process of defining the districts for meter reading.

We present two mathematical formulations for the CEDP and propose methodologiesto solve it. The exact methodologies are based on the Branch-and-Bound (B&B) andBranch-and-Cut (B&C) paradigms. Given the problem’s complexity, we also proposeheuristics methodologies based on GRASP and on Lagrangian relaxation.

In order to evaluate the proposed methodologies, computational experiments wereperformed on a benchmark. Analyzing the results, it can be noted that the GRASPmethodology performed well, while the Lagrangian heuristic, which did not converge,performed poorly.

Lista de Figuras

2.1 Exemplo de um distritamento. . . . . . . . . . . . . . . . . . . . . . . . . . 15

4.1 Redução polinomial de um problema A em um problema B. . . . . . . . . 194.2 Conjectura P 6= NP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214.3 Exemplo de uma instância específica do CEDP obtida transformando-se a

instância S = {2, 3, 5} do PP. . . . . . . . . . . . . . . . . . . . . . . . . . 22

5.1 Exemplo de um distritamento em G′. . . . . . . . . . . . . . . . . . . . . . 29

7.1 Performance Profiles dos Limitantes. . . . . . . . . . . . . . . . . . . . . . 627.2 Performance Profiles dos Limitantes para cada topologia. . . . . . . . . . . 637.3 Performance Profiles dos Limitantes para cada valor de m. . . . . . . . . . 647.4 Performance Profiles dos Limitantes para cada valor de B. . . . . . . . . . 657.5 Performance Profiles dos Limitantes para cada capacidade. . . . . . . . . . 667.6 Performance Profiles dos Limitantes para cada valor de |V |. . . . . . . . . 677.7 Performance Profiles dos Limitantes para cada densidade. . . . . . . . . . . 687.8 Soluções encontradas para a instância grid-m5V25E40B05D05. . . . . . . . 697.9 Solução encontrada para a instância grid-m10V100E140B05D05. . . . . . . 70

Lista de Tabelas

7.1 Soluções Factíveis e Ótimas encontradas por cada Metodologia. . . . . . . 597.2 Soluções Factíveis e Ótimas encontradas para cada topologia. . . . . . . . . 607.3 Soluções Factíveis e Ótimas encontradas para cada valor de m. . . . . . . . 607.4 Soluções Factíveis e Ótimas encontradas para cada valor de B. . . . . . . . 617.5 Soluções Factíveis e Ótimas encontradas para cada valor de D. . . . . . . . 617.6 Soluções Factíveis e Ótimas encontradas para cada valor de |V |. . . . . . . 627.7 Soluções Factíveis e Ótimas encontradas para cada valor de |E|. . . . . . . 62

A.1 Benchmark de Instâncias. . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

B.1 Limitantes Duais. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79B.2 Limitantes Primais. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83B.3 GAPs de Otimalidade. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

Lista de Abreviações e Siglas

• AP - Problema da Atribuição, do inglês Assignment Problem;

• B&B - Branch-and-Bound ;

• B&C - Branch-and-Cut ;

• CDP - Problema de Distritamento Capacitado, do inglês Capacitated DistrictingProblem;

• CEDP - Problema de Distritamento Econômico e Capacitado, do inglês Capacitatedand Economic Districting Problem;

• CPP - Problema do Carteiro Chinês, do inglês Chinese Postman Problem;

• DP - Problema de Distritamento, do inglês Districting Problem;

• GRASP - Procedimento de Busca Adaptativo Aleatório Guloso, do inglês GreedyRandomized Adaptive Search Procedure;

• ILP - Programa Linear Inteiro, do inglês Integer Linear Program;

• KP - Problema da Mochila, do inglês Knapsack Problem;

• LP - Programa Linear, do inglês Linear Program;

• MCRP - Problema de Redistritamento Capacitado Multicritério, do inglês Multi-criteria Capacitated Redistricting Problem;

• MKP - Problema das Múltiplas Mochilas, do inglês Multiple Knapsack Problem;

• PP - Problema da Partição, do inglês Partition Problem.

Sumário

1 Introdução 12

2 O Problema de Distritamento Econômico e Capacitado 14

3 Objetivos 173.1 Objetivos Gerais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.2 Objetivos Específicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4 Análise de Complexidade 18

5 Formulações em Programação Linear Inteira 245.1 Formulação por cortes de arestas . . . . . . . . . . . . . . . . . . . . . . . 245.2 Formulação por fluxo em redes no grafo linha . . . . . . . . . . . . . . . . 26

6 Metodologias de Resolução 306.1 Metodologias Heurísticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

6.1.1 Heurística Construtiva . . . . . . . . . . . . . . . . . . . . . . . . . 306.1.2 Método de Factibilização . . . . . . . . . . . . . . . . . . . . . . . . 326.1.3 Heurística de Busca Local . . . . . . . . . . . . . . . . . . . . . . . 41

6.2 Metodologias Exatas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446.2.1 Branch-and-Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . 446.2.2 Branch-and-Cut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

6.3 Meta-heurísticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476.3.1 Heurística Lagrangiana . . . . . . . . . . . . . . . . . . . . . . . . . 486.3.2 GRASP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

7 Experimentos Computacionais 577.1 Geração de Instâncias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 577.2 Análise dos Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

8 Considerações Finais 71

Referências Bibliográficas 72

A Benchmark de Instâncias 74

B Resultados Obtidos 79

12

Capítulo 1

Introdução

Em otimização combinatória, particularmente no que se refere a problemas de roteamentoe de particionamento, existem dois problemas representativos na literatura: o Problemado Carteiro Chinês, do inglês Chinese Postman Problem (CPP) e o Problema de Distri-tamento, do inglês Districting Problem (DP).

O CPP consiste em encontrar o menor circuito que percorre cada aresta de um grafoao menos uma vez. Este problema está relacionado a um dos problemas mais antigos emteoria dos grafos: encontrar um ciclo euleriano em um grafo conexo, isto é, encontrar umamaneira de percorrer toda aresta exatamente uma vez, retornando ao ponto de origem(EDMONDS; JOHNSON, 1973).

O CPP modela o problema do mundo real enfrentado por um carteiro que deve entre-gar correspondências em cada rua de uma certa região e retornar ao seu ponto de origem.O CPP também pode ser aplicado em outros contextos, como o dos leituristas das com-panhias provedoras de água e energia, que devem medir o consumo de todos os clientesde suas redes de distribuição.

O DP consiste em particionar um território, ou seja, agrupar pequenas áreas geográfi-cas, chamadas unidades básicas, em aglomerados geográficos maiores, chamados distritos,de forma que estes estejam de acordo com critérios de planejamento pré-estabelecidos.Exemplos típicos de unidades básicas são clientes, ruas ou códigos postais. Dois critériosde planejamento importantes são balanceamento e conexidade. Balanceamento refere-seao objetivo de estabelecer distritos que tenham tamanhos iguais. Um distrito é conexo sefor possível transitar entre suas unidades básicas sem ter de sair dele (KALCSICS, 2015).

O DP é um modelo simples para vários problemas do mundo real. Kalcsics (2015) ilus-tra várias aplicações interessantes do DP, incluindo distritamento político e planejamentode território de vendas. Distritamento político consiste no problema de dividir uma áreagovernamental em distritos eleitorais a partir dos quais candidatos políticos são eleitos.Já o planejamento de território de vendas é uma tarefa comum a todas as companhiasque operam com uma equipe de vendas e consiste em subdividir o mercado em regiões

13

que são atendidas por um ou mais representantes de vendas.Uma variante do DP é o Problema de Distritamento Capacitado, do inglês Capacitated

Districting Problem (CDP), onde cada distrito possui uma capacidade máxima que podeestar relacionada, por exemplo, ao número máximo de unidades agrupadas por distrito,ou ainda a um limite de atendimento de demanda por distrito. Uma das aplicaçõespráticas do CDP consiste em definir as regiões a serem percorridas pelos leituristas dascompanhias de redes de serviço. Assis, Franca e Usberti (2014) estudaram um problemasimilar: o Problema de Redistritamento Capacitado Multicritério, do inglês MulticriteriaCapacitated Redistricting Problem (MCRP). No MCRP um conjunto de distritos originaisjá existe e o critério de balanceamento é incorporado na função objetivo, enquanto que navariante do CDP estudada neste projeto o desbalanceamento é incorporado nas restriçõese a função objetivo tem um viés econômico.

Neste projeto será estudado o Problema de Distritamento Econômico e Capacitado,do inglês Capacitated and Economic Districting Problem (CEDP), um problema novo naliteratura que consiste em uma variante do CDP onde os distritos, além de possuíremuma capacidade máxima, são formados a partir de um critério econômico, visando, porexemplo, a redução de custos ou o aumento do faturamento. Assim como o CDP, umaaplicação prática consiste em definir regiões a serem percorridas pelos leituristas dascompanhias de redes de serviço, porém também leva-se em consideração a antecipação defaturamento quando se aloca consumidores com maiores consumos em distritos que sãofaturados previamente.

Este documento está organizado da seguinte maneira. No Capítulo 2 o CEDP é formal-mente descrito. No Capítulo 3 os objetivos deste projeto são apresentados. No Capítulo 4é feita uma análise da complexidade do CEDP utilizando a teoria de NP-completude. NoCapítulo 5 são apresentados dois modelos matemáticos para o CEDP. O Capítulo 6 des-creve as metodologias propostas neste projeto para a solução do problema. O Capítulo 7apresenta os experimentos computacionais executados e a análise dos resultados obtidos.Finalmente, o Capítulo 8 traz os comentários finais sobre este projeto.

14

Capítulo 2

O Problema de DistritamentoEconômico e Capacitado

Uma definição formal do CEDP é apresentada a seguir. Seja m ∈ Z∗+ o número dedistritos desejados; D ∈ Z∗+ a capacidade de cada distrito; B ∈ [0, 1] o desbalanceamentomáximo permitido para cada distrito; G = (V,E) um grafo conexo não-orientado, ondeV representa o conjunto de vértices e E representa o conjunto de arestas, sendo que cadaaresta consiste em um conjunto de exatamente dois vértices. Associada a cada arestae ∈ E há uma demanda de ∈ Z+. Associado a cada aresta e ∈ E e a cada j ∈ {1, . . . ,m}há um lucro ce,j ∈ Z+ obtido ao se alocar a aresta e no j-ésimo distrito. O objetivo doCEDP consiste em dividir E em uma coleção E = {E1, . . . , Em} de m distritos conexos,maximizando o lucro total e respeitando a capacidade e o desbalanceamento máximo.

O lucro de um distrito Ej ∈ E é dado por cEj=∑e∈Ej

ce,j. Enquanto que o lucro total

de um distritamento E é dado por cE =∑Ej∈E

cEj=∑Ej∈E

∑e∈Ej

ce,j.

A demanda dEjde um distrito Ej ∈ E pode ser calculada como o tamanho de um ciclo

de carteiro chinês mínimo no subgrafo induzido G[Ej]. Porém, resolver um CPP paracada subgrafo induzido G[Ej] pode ser computacionalmente custoso. Uma outra formade sobre-estimar a demanda dEj

é somar duas vezes a demanda de cada aresta em Ej:dEj

= 2∑e∈Ej

de. Note que dEj= 2

∑e∈Ej

de é uma 2-aproximação do CPP em G[Ej], que

pode ser obtida através de um circuito euleriano que percorre cada aresta duas vezes.Um distrito Ej ∈ E é conexo se o subgrafo induzido G[Ej] for conexo. Distritos perfei-

tamente balanceados geralmente não são possíveis devido à natureza discreta do problema.Porém, existem diversas abordagens na literatura para quantificar o desbalanceamento eincorporar esse critério no processo de distritamento (KALCSICS, 2015).

A medida local de desbalanceamento de um distrito Ej ∈ E adotada neste trabalho ébaseada no desvio relativo da demanda dEj

do distrito em relação à demanda média dos

15

distritos, dada por d̄E =1

m

∑Ej∈E

dEj:

balEj=

∣∣∣∣dEj− d̄Ed̄E

∣∣∣∣ .Um distrito Ej ∈ E está perfeitamente balanceado se balEj

= 0.A medida global de desbalanceamento de um distritamento E é calculada como o

desbalanceamento máximo de um distrito:

balmaxE = max

Ej∈E{balEj

}.

Note que se balmaxE = 1, pode existir algum Ej ∈ E tal que Ej = ∅. Neste caso, o

distritamento E não consiste em uma partição do conjunto de arestas E.A Figura 2.1 mostra um exemplo de distritamento em um grafo onde todas as arestas

possuem a mesma demanda. Neste exemplo, as arestas foram divididas em três subcon-juntos: as vermelhas pontilhadas, as verdes contínuas e as azuis tracejadas. Note que osdistritos definidos pelos subconjuntos de arestas são conexos, pois o subgrafo induzido porcada subconjunto de arestas é conexo. Note também que, como todas as arestas possuemdemandas iguais, os distritos são perfeitamente balanceados, pois cada subconjunto dearestas possui exatamente quatro arestas.

Figura 2.1: Exemplo de um distritamento.

Uma aplicação do CEDP consiste em um problema enfrentado por companhias prove-doras de redes de serviço como água e energia: definir em que dia útil do mês será realizadaa leitura de cada um de seus clientes. Esta decisão deve considerar vários critérios logís-ticos, como a carga horária dos leituristas, o consumo médio, a localização geográfica e,

16

no caso de um redistritamento, o dia útil do mês em que atualmente é realizada a leiturado consumo de cada um de seus clientes. A solução desse problema tem potencial deaumentar o faturamento dessas companhias. Por exemplo, clientes que apresentam umalto consumo médio devem ter maior prioridade para serem faturados antes daqueles commenor consumo médio, pois assim uma maior quantia de dinheiro pode ser aplicada emum fundo de investimento de alta liquidez por mais tempo, aumentando o valor rendido.Por outro lado, a fim de respeitar a carga horária dos leituristas, as companhias devemdar preferência por realizar no mesmo dia a leitura do consumo de clientes que estãolocalizados próximos uns aos outros, pois desta forma os leituristas despenderão menostempo se locomovendo entre os clientes.

É possível modelar este problema como um CEDP onde o número de distritos mcorresponde ao número de dias úteis do mês disponíveis para a companhia realizar aleitura do consumo de seus clientes; D corresponde à força de trabalho (em homens-hora)disponível por distrito; B corresponde à tolerância de desbalanceamento permitida pelacompanhia; e o grafo G = (V,E) corresponde à topologia da rede, sendo que cada vérticev ∈ V corresponde a um cruzamento de ruas e cada aresta e ∈ E corresponde a umsegmento de rua conectando dois cruzamentos. A demanda de, associada ao segmentode rua e, corresponde ao tempo necessário para os leituristas percorrerem e, realizando aleitura do consumo dos clientes nele localizados. Já o custo ce,j associado ao segmento derua e e ao j-ésimo distrito corresponde ao ganho de capital da companhia ao realizar aleitura do consumo de todos os clientes localizados no segmento de rua e no dia útil j.

Os valores de e ce,j são parâmetros de entrada. Seja se o comprimento do segmento derua e e v a velocidade média dos leituristas, tem-se que de =

sev. Seja Ce o conjunto de

clientes localizados no segmento de rua e, pi o faturamento médio do cliente i, r a taxa dejuros diária do fundo de investimento e ji o dia útil do mês em que atualmente é realizadaa leitura do consumo do cliente i, tem-se que ce,j =

∑i∈Ce

pi(1 + r)(ji−j).

Neste projeto será estudado exclusivamente o problema de definir os distritos que serãoatendidos pelos leituristas. O problema de definir os caminhos dos leituristas dentro decada distrito já foi investigado por Maziero, Usberti e Cavellucci (2015) e Mendes e Usberti(2017).

17

Capítulo 3

Objetivos

Neste capítulo são apresentados os objetivos gerais e os objetivos específicos deste projetode pesquisa de mestrado:

3.1 Objetivos Gerais

• Investigar formalmente o CEDP, analisando sua complexidade e propondo formula-ções matemáticas e metodologias de solução exata e heurística.

• Conduzir experimentos computacionais das metodologias propostas visando umaanálise comparativa das mesmas.

3.2 Objetivos Específicos

• Propôr e implementar metodologias de solução exatas, fundamentadas em Progra-mação Linear Inteira, Branch-and-Bound e Branch-and-Cut.

• Propôr e implementar meta-heurísticas visando a solução de instâncias de portereal.

• Elaborar um conjunto representativo de instâncias artificiais para avaliar computa-cionalmente as metodologias propostas.

• Avaliar o desempenho das metodologias propostas com base em métodos analíticosde avaliação comparativa de desempenho.

18

Capítulo 4

Análise de Complexidade

Neste capítulo é apresentada uma análise de complexidade do CEDP utilizando a teoriade NP-completude, a qual já foi amplamente estudada na literatura (CORMEN et al.,2009; MANBER, 1989; GAREY; JOHNSON, 1979; SZWARCFITER, 1986).

A teoria de NP-completude restringe-se a problemas de decisão, isto é, a problemascuja resposta é “sim” ou “não”. Os problemas de otimização podem ser facilmente con-vertidos em problemas de decisão impondo-se um limite no valor a ser otimizado. Porexemplo, ao invés de procurar por um distritamento de lucro máximo no CEDP, pode-seperguntar se existe um distritamento de lucro maior ou igual a K. Se for possível resolvero problema de decisão, pode-se estender a solução para o problema de otimização corres-pondente, por exemplo, por busca binária. No restante deste capítulo, será consideradaapenas a versão de decisão do CEDP.

Uma importante técnica utilizada pela teoria da NP-completude é a redução polino-mial entre problemas. Reduzir um problema A em um problema B consiste em resolvero problema A utilizando uma “caixa preta” que resolve o problema B. Formalmente,uma redução de um problema A em um problema B consiste em um procedimento quetransforma qualquer instância α de A em uma instância β de B e um procedimento quetransforma uma solução para β em uma solução para α. Se a transformação de α em β

e a transformação de uma solução para β em uma solução para α puderem ser realizadasem tempo polinomial no tamanho de α, então diz-se que existe uma redução polinomialde A em B. Reduções polinomiais podem alcançar dois objetivos distintos, dependendoda direção na qual são feitas. Uma redução polinomial de A em B implica na existênciade um algoritmo polinomial para A caso se conheça um algoritmo polinomial para B. Poroutro lado, se A é conhecido por ser difícil, por exemplo, se sabe-se que não existe nenhumalgoritmo polinomial para A, então o mesmo resultado se aplica a B, isto é, também nãoexiste nenhum algoritmo polinomial para B. A Figura 4.1 ilustra uma redução polinomialde A em B.

A teoria da NP-completude classifica os problemas de decisão de acordo com suas

19

Figura 4.1: Redução polinomial de um problema A em um problema B.

complexidades nas classes P, NP, NP-difícil e NP-completo. A classe P compreende todosos problemas de decisão que podem ser resolvidos por algoritmos polinomiais. A classeNP compreende todos os problemas de decisão que podem ser “verificados” em tempopolinomial, isto é, se for dado um “certificado” de uma solução, então pode-se verificarque o certificado é correto em tempo polinomial no tamanho da instância do problema.Note que qualquer problema em P também está em NP, uma vez que se um problema estáem P então pode-se resolvê-lo em tempo polinomial sem sequer possuir um certificado.

No Teorema 4.1 mostra-se que o CEDP pertence à classe NP, exibindo-se um certificadoda resposta “sim” e elaborando-se um algoritmo para verificar se o certificado está correto.

Teorema 4.1. CEDP ∈ NP.

Demonstração. Seja (m,D,B,G = (V,E), d, c,K) uma instância do CEDP, conformedescrita no Capítulo 2, onde K é um limite inferior no lucro a ser maximizado, e E =

{E1, . . . , Em} um certificado para a resposta “sim” desta instância, que consiste em m

distritos, isto é, m subconjuntos de arestas.Para verificar se o certificado está correto, é necessário verificar se:

• o distritamento E consiste em um divisão de E. Para tanto, é necessário verificar

se Ei ∩ Ej = ∅ para todo i, j ∈ {1, . . . ,m} com i 6= j e sem⋃j=1

Ej = E:

– Para verificar se Ei ∩ Ej = ∅ para todo i, j ∈ {1, . . . ,m} com i 6= j, bastaverificar se para cada e ∈ Ei, e /∈ Ej;

– Para verificar sem⋃j=1

Ej = E é necessário verificar sem⋃j=1

Ej ⊆ E e se E ⊆m⋃j=1

Ej.

∗ Para verificar sem⋃j=1

Ej ⊆ E, basta, para cada Ej ∈ E e para cada e ∈ Ej,

verificar se e ∈ E;

∗ Para verificar se E ⊆m⋃j=1

Ej, basta, para cada e ∈ E, verificar se existe

algum Ej ∈ E tal que e ∈ Ej;

• cada distrito Ej ∈ E é conexo, ou seja, se cada subgrafo induzido G[Ej] é conexo, oque pode ser feito em tempo linear por meio de uma Busca em Largura, do inglêsBreadth-First Search (BFS), ou de uma Busca em Profundidade, do inglês Depth-First Search (DFS) (CORMEN et al., 2009; MANBER, 1989);

20

• cada distrito Ej ∈ E respeita a capacidade máxima D. Para tanto, basta verificarse a soma de duas vezes a demanda de cada aresta de cada distrito é menor ou iguala capacidade máxima, isto é, dEj

≤ D para todo Ej ∈ E ;

• cada distrito Ej ∈ E respeita o desbalanceamento máximo B. Para tanto, primeira-

mente computa-se a demanda média dos distritos d̄E =2

m

∑e∈E

de e, então, verifica-se

se (1−B)d̄E ≤ dEj≤ (1 +B)d̄E para todo Ej ∈ E ;

• o lucro do distritamento E é de pelo menos K. Para tanto, basta verificar se cE =∑Ej∈E

∑e∈Ej

ce,j ≥ K.

Como todas estas verificações podem ser realizadas em tempo polinomial no tamanhoda instância, conclui-se que o CEDP pertence à classe NP.

A classe NP-difícil compreende todos os problemas de decisão que são pelo menos tãodifíceis quanto os problemas mais difíceis em NP. Um problema A está em NP-difícil see somente se todo problema B em NP pode ser reduzido polinomialmente em A. Comoconsequência, um algoritmo polinomial para qualquer problema em NP-difícil implicana existência de algoritmos polinomiais para todos os problemas em NP. A classe NP-completo compreende todos os problemas de decisão que podem ser verificados em tempopolinomial e que são pelo menos tão difíceis quanto os problemas mais difíceis em NP,isto é, NP-completo = NP ∩ NP-difícil. Ainda não foi descoberto nenhum algoritmopolinomial para qualquer problema em NP-difícil e conjectura-se não existir tal algoritmo,ou seja, conjectura-se que P 6= NP (Figura 4.2).

No Teorema 4.3 mostra-se que o CEDP pertence à classe NP-difícil. Para tanto, reduz-se um problema de decisão em NP-difícil para o CEDP. O problema de decisão escolhidopara a demonstração é o Problema da Partição, do inglês Partition Problem (PP). Umainstância do PP consiste em um conjunto S ⊆ Z+ e a questão a ser respondida é se existe

um subconjunto S ′ ⊆ S tal que∑s∈S′

s =∑s∈S\S′

s =1

2

∑s∈S

s. O resultado de que o PP

pertence à classe NP-completo e, consequentemente, à classe NP-difícil, é utilizado comoo Lema 4.2.

Lema 4.2. PP ∈ NP-completo (GAREY; JOHNSON, 1979)

Teorema 4.3. CEDP ∈ NP-difícil.

Demonstração. Seja S = {s1, . . . , sn} uma instância genérica do PP, isto é, S é um con-junto qualquer de n números inteiros não-negativos. Transforma-se S em uma instânciaespecífica (m,D,B,G = (V,E), d, c,K) do CEDP da seguinte maneira:

• m = 2;

21

Figura 4.2: Conjectura P 6= NP.

• D =∑s∈S

s;

• B = 0;

• V = {v0, v1, . . . , vn}, ou seja, G possui n+ 1 vértices distintos;

• E = {{v0, v1}, . . . , {v0, vn}}, ou seja, G possui n arestas distintas ligando o vérticev0 a cada um dos demais vértices;

• a cada aresta ei = {v0, vi} ∈ E são associados a demanda dei = si e os lucroscei,1 = cei,2 = 0;

• K = 0.

Note que a instância específica do CEDP pode ser construída em tempo polinomial a partirda instância genérica do PP. A Figura 4.3 ilustra uma instância específica do CEDP obtidaa partir da instância S = {2, 3, 5} do PP.

Se a resposta para a instância genérica do PP for “sim”, então existe um subcon-

junto S ′ ⊆ S tal que∑s∈S′

s =∑s∈S\S′

s =1

2

∑s∈S

s. Sejam S ′ = {s1, . . . , sn′} e S \ S ′ =

{sn′+1, . . . , sn}. Pela construção da instância específica do CEDP, existe uma coleçãoE = {E1, E2} de distritos, isto é, existe uma coleção E = {E1, E2} de subconjuntos de E,onde E1 = {{v0, v1}, . . . , {v0, vn′}} e E2 = {{v0, vn′+1}, . . . , {v0, vn}}, tal que:

• E é uma divisão de E, pois E1 ∩ E2 = ∅ e E1 ∪ E2 = E;

22

Figura 4.3: Exemplo de uma instância específica do CEDP obtida transformando-se ainstância S = {2, 3, 5} do PP.

• os distritos E1 e E2 são conexos, pois todas as arestas dos subgrafos induzidos G[E1]

e G[E2] possuem o vértice v0 em comum;

• os distritos E1 e E2 respeitam a capacidade máximaD =∑s∈S

s, pois as demandas dos

distritos E1 e E2 são, respectivamente, dE1 = 2∑e∈E1

de = 2(d{v0,v1}+ . . .+d{v0,vn′}) =

2(s1 + . . .+ sn′) = 2∑s∈S′

s =∑s∈S

s e dE2 = 2∑e∈E2

de = 2(d{v0,vn′+1} + . . .+ d{v0,vn}) =

2(sn′+1 + . . .+ sn) = 2∑s∈S\S′

s =∑s∈S

s;

• os distritos E1 e E2 respeitam o desbalanceamento máximo B = 0, pois a demanda

média dos distritos é d̄E =2

m

∑e∈E

de =2

2(d{v0,v1}+. . .+d{v0,vn}) = s0+. . .+sn =

∑s∈S

s

e dE1 = dE2 = d̄E =∑s∈S

s;

• o lucro do distritamento E é de pelo menos K = 0, pois os lucros dos distritos E1 eE2 são, respectivamente, cE1 =

∑e∈E1

ce,1 =∑e∈E1

0 = 0 e cE2 =∑e∈E2

ce,2 =∑e∈E2

0 = 0 e

cE = cE1 + cE2 = 0 = K.

Logo, o conjunto de arestas E pode ser dividido em uma coleção E = {E1, E2} de dois

23

distritos conexos que respeitam a capacidade máxima D =∑s∈S

s, o desbalanceamento

máximo B = 0 e tem lucro pelo menos K = 0. Portanto, a resposta para a instânciaespecífica do CEDP também é “sim”.

Se a resposta para a instância específica do CEDP for “sim”, então as arestas em E

podem ser divididas em uma coleção E = {E1, E2} de dois distritos conexos que respeitama capacidade máxima D =

∑s∈S

s e o desbalanceamento máximo B = 0 e de lucro pelo

menos K = 0. Sejam E1 = {{v0, v1}, . . . , {v0, vn′}} e E2 = {{v0, vn′+1}, . . . , {v0, vn}} e

seja d̄E =2

m

∑e∈E

de =∑e∈E

de a demanda média dos distritos. Pela construção da instância

específica do CEDP, tem-se que d{v0,vi} = si para cada aresta {v0, vi} ∈ E, logo d̄E =∑s∈S

s.

Como os distritos respeitam o desbalanceamento máximo B = 0, tem-se dE1 = 2∑e∈E1

de =

d̄E =∑s∈S

s e dE2 = 2∑e∈E2

de = d̄E =∑s∈S

s. Então, pela construção da instância específica

do CEDP, o conjunto S pode ser particionado nos subconjuntos S ′ = {s1, . . . , sn′} e

S \ S ′ = {sn′ , . . . , sn} de tal forma que∑s∈S′

s =∑s∈S\S′

s =1

2

∑s∈S

s. Portanto, a resposta

para a instância genérica do PP também é “sim”.Logo, a resposta para instância genérica do PP é “sim” se e somente se a resposta para

a instância específica do CEDP for “sim”. Portanto, o PP é polinomialmente redutível aoCEDP. Como, pelo Lema 4.2, o PP pertence à classe NP-completo e, consequentemente,à classe NP-difícil, conclui-se que o CEDP também pertence à classe NP-difícil.

Por fim, o resultado de que o CEDP pertence à classe NP-completo segue dos resul-tados dos Teoremas 4.1 e 4.3.

Corolário 4.4. CEDP ∈ NP-completo

Demonstração. Pelo Teorema 4.1, CEDP ∈ NP, e, pelo Teorema 4.3, CEDP ∈ NP-difícil.Como NP-completo = NP ∩ NP-difícil, conclui-se que CEDP ∈ NP-completo.

24

Capítulo 5

Formulações em Programação LinearInteira

Um Programa Linear, do inglês Linear Program (LP), consiste no problema de minimizarou maximizar uma função objetivo linear na presença de restrições lineares (desigualdadese/ou igualdades) (BAZARAA; JARVIS, 1977).

Considere o seguinte LP genérico:

max{cx : Ax ≤ b, x ∈ Rn+}

onde A é uma matriz de dimensões m × n com os coeficientes das restrições, c é umvetor linha de dimensão n com os coeficientes da função objetivo, b é um vetor coluna dedimensão m com os coeficientes do lado direito das desigualdades (ou igualdades) e x éum vetor coluna de dimensão n com as variáveis de decisão do problema. Um ProgramaLinear Inteiro, do inglês Integer Linear Program (ILP), consiste em um LP onde algumas(ou todas) variáveis de decisão devem assumir valores inteiros (WOLSEY, 1998).

Muitas vezes são utilizadas formulações em ILP para modelar problemas de otimizaçãocombinatória, uma vez que as variáveis discretas podem ser representadas por númerosinteiros. Em Wolsey (1998) são apresentadas formulações de vários problemas de oti-mização combinatória, incluindo problemas clássicos da literatura, como o Problema daMochila, do inglês Knapsack Problem (KP), e o Problema do Caixeiro Viajante, do inglêsTraveling Salesman Problem (TSP).

Duas formulações em ILP para o CEDP são apresentadas a seguir.

5.1 Formulação por cortes de arestas

Variáveis de decisão:

25

xe,j =

1, se a aresta e ∈ E for alocada a Ej,

0, caso contrário.

Função objetivo:

max

{m∑j=1

∑e∈E

ce,jxe,j

}(5.1)

Restrições:

m∑j=1

xe,j = 1,∀e ∈ E (5.2)

2∑e∈E

dexe,j ≤ min

{D,

2(1 +B)

m

∑e∈E

de

}, ∀j ∈ {1, . . . ,m} (5.3)

2∑e∈E

dexe,j ≥2(1−B)

m

∑e∈E

de,∀j ∈ {1, . . . ,m} (5.4)

xe,j + xf,j −∑

g∈δG(V ′)

xg,j ≤ 1,∀e, f ∈ E, V ′ ⊂ V \ f, V ′ ⊃ e, j ∈ {1, . . . ,m} (5.5)

xe,j ∈ {0, 1},∀e ∈ E, j ∈ {1, . . . ,m} (5.6)

A função objetivo (5.1) busca por uma solução de lucro máximo, onde o lucro deuma solução é dado pelo somatório dos lucros associados a colocar cada aresta em cadadistrito. As restrições (5.2) garantem que cada aresta e ∈ E será alocada a exatamente umdistrito. As restrições (5.3) garantem que a capacidade de cada distrito será respeitada.As restrições (5.3) e as restrições (5.4) garantem que o desbalanceamento máximo serárespeitado. As restrições (5.5) garantem que se duas arestas e, f ∈ E são alocadas aum mesmo distrito Ej (xe,j = xf,j = 1), então ao menos uma aresta de cada corte dearestas δG(V ′)1 que separa e de f também será alocada a esse distrito (

∑g∈δG(V ′)

xg,j ≥ 1),

ou seja, essas restrições garantem que os distritos serão conexos. Por fim, as restrições(5.6) garantem a integralidade das variáveis.

Nesta formulação a demanda de um distrito Ej ∈ E é dada por dEj= 2

∑e∈E

dexe,j.

Como cada distrito Ej ∈ E deve respeitar a capacidade máxima, chega-se ao primeirotermo da função de mínimo das restrições (5.3). A demanda média dos distritos é

1Dado um grafo G = (V,E) e um subconjunto de vértices V ′ ⊂ V , δG(V ′) denota o subconjunto dearestas com um extremo em V ′ e o outro em V \ V ′, ou seja, δG(V ′) = {{u, v} ∈ E : u ∈ V ′, v ∈ V \ V ′}.

26

dada por d̄E =1

m

∑Ej∈E

dEj=

1

m

m∑j=1

2∑e∈E

dexe,j =2

m

∑e∈E

de

m∑j=1

xe,j, porém, como cada

aresta é alocada a exatamente um distrito (restrições (5.2)), tem-se que d̄E =2

m

∑e∈E

de.

Logo, o desbalanceamento de cada distrito Ej ∈ E é dado por balEj=

∣∣∣∣dEj− d̄Ed̄E

∣∣∣∣ =∣∣∣∣∣∣∣∣∣2∑e∈E

dexe,j

2

m

∑e∈E

de

− 1

∣∣∣∣∣∣∣∣∣. Como balmaxE ≤ B ⇒ max

Ej∈E{balEj

} ≤ B, tem-se que, para todo dis-

trito Ej ∈ E , balEj≤ B ⇒

∣∣∣∣∣∣∣∣∣2∑e∈E

dexe,j

2

m

∑e∈E

de

− 1

∣∣∣∣∣∣∣∣∣ ≤ B ⇒ −B ≤2∑e∈E

dexe,j

2

m

∑e∈E

de

− 1 ≤ B ⇒

2(1−B)

m

∑e∈E

de ≤ 2∑e∈E

dexe,j ≤2(1 +B)

m

∑e∈E

de. Com isso, deduz-se o segundo termo da

função de mínimo das restrições (5.3), assim como a corretude das restrições (5.4).

5.2 Formulação por fluxo em redes no grafo linha

O grafo linha L(G) de G = (V,E) é definido como aquele que tem as arestas de G comoseus vértices, com dois vértices sendo adjacentes se e somente se as arestas correspondentessão adjacentes em G (DIESTEL, 2010; BEINEKE, 1970). Formalmente, L(G) = (U,A)

onde U = E e A = {{e, f} : e, f ∈ U, |e ∩ f | = 1}. Note que |U | = |E| e |A| =1

2

∑v∈V

(|δG(v)|2)− |E| (HARARY, 1969).

No grafo linha L(G), o objetivo do CEDP consiste em dividir U em uma coleçãoU = {U1, . . . , Um} de m distritos conexos, maximizando o lucro total e respeitando acapacidade e o desbalanceamento máximo.

O lucro de um distrito Uj ∈ U é dado por cUj=∑e∈Uj

ce,j. Enquanto que o lucro total

de um distritamento U é dado por cU =∑Uj∈U

cUj=∑Uj∈U

∑e∈Uj

ce,j.

A demanda de um distrito Uj ∈ U é dada por dUj= 2

∑e∈Uj

de. Enquanto que a demanda

média de um distritamento U é dada por d̄U =1

m

∑Uj∈U

dUj=

2

m

∑e∈U

de.

Um distrito Uj ∈ U é conexo se o subgrafo induzido L(G)[Uj] for conexo. Uma forma degarantir a conexidade dos distritos consiste em utilizar fluxo em redes. Para tanto, bastaconectar um vértice fonte artificial e′ a todos os vértices, fazendo com que |U | unidadesde fluxo saiam de e′ por exatamente m arestas e cada vértice e ∈ U consuma exatamente

27

uma unidade de fluxo. Seja G′ o supergrafo de L(G) obtido ao adicionar o vértice fonteartificial e′. Formalmente, G′ = (U ′, A′) onde U ′ = U ∪ {e′} e A′ = A ∪ {{e′, e} : e ∈ U}.Note que |U ′| = |E|+ 1 e |A′| = 1

2

∑v∈V

(|δG({v})|2).

A Figura 5.1 mostra o mesmo distritamento da Figura 2.1 no grafo G′. Nesta figura,os vértices em U foram particionados em três subconjuntos: os vermelhos pontilhados, osverdes contínuos e os azuis tracejados. As arestas por onde o fluxo passa em cada distritotambém são destacadas. Note que estas arestas induzem uma árvore em G′ e uma árvorepara cada distrito em L(G).

Variáveis de decisão:

xe,j =

1, se o vértice e ∈ U for alocado a Uj,

0, caso contrário.

y{e′,e},j =

1, se a aresta {e′, e} ∈ A′ \ A for alocada a Uj,

0, caso contrário.

ze,f,j ∈ R+ : fluxo percorrendo a aresta {e, f} ∈ A′ no sentido e→ f em Uj

Função objetivo:

max

{m∑j=1

∑e∈U

ce,jxe,j

}(5.7)

Restrições:

m∑j=1

xe,j = 1,∀e ∈ U (5.8)

2∑e∈U

dexe,j ≤ min

{D,

2(1 +B)

m

∑e∈U

de

}, ∀j ∈ {1, . . . ,m} (5.9)

2∑e∈U

dexe,j ≥2(1−B)

m

∑e∈U

de,∀j ∈ {1, . . . ,m} (5.10)

∑e∈U

y{e′,e},j = 1,∀j ∈ {1, . . .m} (5.11)

m∑j=1

∑e∈U

ze′,e,j = |U | (5.12)

ze′,e,j − |U |y{e′,e},j ≤ 0,∀{e′, e} ∈ A′ \ A, j ∈ {1, . . .m} (5.13)

28

ze,f,j − |U |xe,j ≤ 0, ∀e ∈ U, {e, f} ∈ δL(G)({e}), j = {1, . . . ,m} (5.14)

zf,e,j − |U |xe,j ≤ 0,∀e ∈ U, {e, f} ∈ δL(G)({e}), j = {1, . . . ,m} (5.15)

∑{e,f}∈δG′ ({e})

zf,e,j −∑

{e,f}∈δG′ ({e})

ze,f,j − xe,j = 0, ∀e ∈ U, j ∈ {1, . . . ,m} (5.16)

xe,j ∈ {0, 1},∀e ∈ U, j ∈ {1, . . . ,m} (5.17)

y{e′,e},j ∈ {0, 1},∀{e′, e} ∈ A′ \ A, j ∈ {1, . . . ,m} (5.18)

ze,f,j ∈ [0, |U |],∀{e, f} ∈ A′, j ∈ {1, . . . ,m} (5.19)

A função objetivo (5.7) e as restrições (5.8), (5.9) e (5.10) são análogas à função obje-tivo (5.1) e às restrições (5.2), (5.3) e (5.4) da formulação da Seção 5.1, respectivamente.

As restrições (5.11) garantem que haverá uma aresta {e′, e} ∈ A′ \ A adjacente aovértice artificial e′ alocada a cada distrito Uj. A restrição (5.12) garante que sairão |U |unidades de fluxo do vértice artificial e′. As restrições (5.13) garantem que se a aresta{e′, e} ∈ A′ \ A não for alocada a um distrito Uj (y{e′,e},j = 0), então não haverá fluxosaindo de e′ para e pelo distrito Uj (ze′,e,j = 0). Juntas, as restrições (5.11), (5.12) e(5.13) garantem que |U | unidades de fluxo sairão de e′ por m arestas. As restrições (5.14)garantem que se um vértice e ∈ U não for alocado a um distrito Uj (xe,j = 0), entãonenhum fluxo sairá do vértice e pelo distrito Uj (ze,f,j = 0,∀{e, f} ∈ δL(G)({e})). Asrestrições (5.15) garantem que se um vértice e ∈ U não for alocado a um distrito Uj

(xe,j = 0), então nenhum fluxo entrará no vértice e pelo distrito Uj (zf,e,j = 0, ∀{e, f} ∈δL(G)({e})). Juntas, as restrições (5.14) e (5.15) garantem que só haverá fluxo percorrendouma aresta {e, f} ∈ A por um distrito Uj (ze,f,j > 0) se ambos os vértices extremose, f ∈ U estiverem alocados ao distrito Uj (xe,j = xf,j = 1). As restrições (5.16) garantema conservação do fluxo, isto é, se um vértice e ∈ U for alocado a um distrito Uj (xe,j = 1),então a quantidade de fluxo que entra em e pelo distrito Uj é uma unidade maior do quea quantidade de fluxo que sai de e pelo distrito Uj (

∑f∈δG′ ({e})

zf,e,j −∑

f∈δG′ ({e})

ze,f,j = 1);

por outro lado, se um vértice e ∈ U não for alocado a um distrito Uj (xe,j = 0), entãoa quantidade de fluxo que entra em e pelo distrito Uj é igual a quantidade de fluxo quesai de e pelo distrito Uj (

∑f∈δG′ ({e})

zf,e,j −∑

f∈δG′ ({e})

ze,f,j = 0). Juntas, as restrições (5.11),

(5.12), (5.13), (5.14), (5.15) e (5.16) garantem que os distritos serão conexos.

29

Por fim, as restrições (5.17) garantem a integralidade das soluções, enquanto que asrestrições (5.18) e (5.19) definem o domínio das variáveis y e z, respectivamente.

Figura 5.1: Exemplo de um distritamento em G′.

30

Capítulo 6

Metodologias de Resolução

Neste capítulo são apresentadas metodologias heurísticas, exatas e meta-heurísticas parao CEDP. Sobre heurísticas, são apresentadas uma heurística construtiva gulosa-aleatória,um método de factibilização de soluções não factíveis e uma heurística de busca local.Sobre métodos exatos, são propostos dois algoritmos fundamentados nos paradigmasBranch-and-Bound e Branch-and-Cut. Sobre meta-heurísticas, foram desenvolvidas umaHeurística Lagrangiana e um GRASP (“Greedy Randomized Search Procedure”) para asolução do CEDP.

6.1 Metodologias Heurísticas

Uma heurística consiste em uma técnica projetada para obter soluções não triviais paraproblemas de otimização, sem garantias de otimalidade, quando métodos exatos são muitolentos.

6.1.1 Heurística Construtiva

Uma heurística construtiva gulosa-aleatória é um método heurístico que começa com umasolução vazia e, iterativamente, escolhe um elemento para incorporar a solução atual demodo aleatório e guloso, até que se obtenha uma solução completa. A cada iteração, aescolha do próximo elemento a ser adicionado na solução atual é determinada ordenando-se todos os elementos em uma lista de candidatos com respeito a uma função gulosa, quemede o benefício de selecionar cada elemento. O candidato que efetivamente entra nasolução é escolhido aleatoriamente a partir da lista dos melhores candidatos, chamada delista restrita de candidatos.

No Algoritmo 1 apresenta-se o pseudo-código da heurística construtiva gulosa-aleatóriaproposta para o CEDP. No laço das linhas 2 ∼ 4 constrói-se uma solução vazia (E1 ←∅; . . . ;Em ← ∅;). Em cada iteração do laço das linhas 5 ∼ 58 escolhe-se um elemento paraincorporar a solução atual até que uma solução completa seja obtida, isto é, escolhe-se

31

uma aresta não alocada e e um distrito Ej para alocá-la até que todas as arestas sejamalocadas. O valor do benefício de cada elemento é dado pelo ganho na função objetivo aose alocar a aresta e no distrito Ej, dado por ce,j.

No laço das linhas 7 ∼ 16 popula-se a lista de candidatos com distritos Ej não vazios(Ej 6= ∅) com demanda abaixo do mínimo permitido (dEj

< (1 − B)d̄E) e arestas e não

alocadas (e /∈m⋃k=1

Ek) adjacentes ao distrito Ej (e ∈ δG(Vj)) que não violam a demanda

máxima permitida (dEj+ 2de ≤ min

{D, (1 +B)d̄E

}), isto é, popula-se a lista com candi-

datos que irão expandir os distritos não vazios com demanda abaixo do mínimo permitido.Este laço é priorizado em relação aos demais com o intuito de evitar que distritos fiquemcom demanda abaixo do mínimo permitido. Por exemplo, se existir um distrito Ej comdemanda abaixo do mínimo permitido, mas priorizar-se criar novos distritos ou expandirdistritos que já possuem demanda acima do mínimo permitido, pode acontecer de todasas arestas adjacentes a Ej serem alocadas a outros distritos, de forma que se torna inviá-vel expandir Ej, fazendo com que ele fique conexo e com a demanda abaixo do mínimopermitido.

Se todos os distritos não vazios têm demanda acima do mínimo permitido ou se não forpossível expandir nenhum distrito não vazio com demanda abaixo do mínimo permitidopreservando-se a conexidade e respeitando-se a demanda máxima permitida, no laço daslinhas 18 ∼ 31 popula-se a lista de candidatos com distritos Ej vazios (Ej = ∅) e arestas

e não alocadas (e /∈m⋃k=1

Ek), e com distritos não vazios (Ej 6= ∅) e arestas e não alocadas

(e /∈m⋃k=1

Ek) adjacentes ao distrito Ej (e ∈ δG(Vj)) que respeitam a demanda máxima

permitida (dEj+ 2de ≤ min

{D, (1 +B)d̄E

}), isto é, popula-se a lista com candidatos

que irão criar novos distritos ou expandir distritos que já possuem demanda acima domínimo permitido. Note que se for criado um novo distrito Ej, o laço das linhas 7 ∼ 16

garante que as próximas iterações do laço das linhas 5 ∼ 58 irão expandir Ej com arestasadjacentes enquanto for possível ou até que Ej possua a demanda mínima permitida.

Se não houver distritos vazios e não for possível expandir os distritos não vaziospreservando-se a conexidade e respeitando-se a demanda máxima permitida, no laço das li-nhas 34 ∼ 40 popula-se a lista de candidatos com distritos Ej e arestas e não alocadas (e /∈m⋃k=1

Ek) que respeitam a demanda máxima permitida (dEj+ 2de ≤ min

{D, (1 +B)d̄E

}).

Se não houver distritos vazios e não for possível expandir os distritos não vaziosrespeitando-se a demanda máxima permitida, no laço das linhas 43 ∼ 47 popula-se a

lista de candidatos com distritos Ej e arestas e não alocadas (e /∈m⋃k=1

Ek).

Após popular a lista de candidatos, nas linhas 49 ∼ 54 popula-se a lista restrita decandidatos com os melhores candidatos, utilizando o threshold α. SejamminC emaxC osvalores mínimos e máximos dos candidatos, respectivamente, um candidato (e, j) entrarána lista restrita de candidatos somente se ce,j ≥ maxC − α(maxC −minC). Na linha 55

32

escolhe-se aleatoriamente um candidato (e, j) da lista restrita de candidatos e, finalmente,o candidato escolhido é incorporado na solução atual na linha 56.

O parâmetro α controla o quão gulosa ou o quão aleatória será a heurística: se α = 0,apenas candidatos com valor igual ao máximo serão considerados e, portanto, a escolhasempre será gulosa; por outro lado, se α = 1, todos os candidatos serão considerados e,portanto, a escolha sempre será totalmente aleatória.

A complexidade de cada iteração do laço das linhas 5 ∼ 58 é dominada pelo laço daslinhas 7 ∼ 16. O laço das linhas 7 ∼ 16 itera por cada um dos m distritos e, a cadaiteração, o laço das linhas 10 ∼ 14 itera, no pior caso, por cada uma das |E| arestas,sendo que cada iteração é executada em tempo constante. Logo, cada iteração do laçodas linhas 5 ∼ 58 tem complexidade de O(m|E|). A cada iteração do laço das linhas5 ∼ 58 uma aresta é alocada a um distrito até que todas as arestas estejam alocadas.Logo, são realizadas |E| iterações deste laço. Portanto, a complexidade do Algoritmo 1 éde O(m|E|2).

6.1.2 Método de Factibilização

Dada uma instância (m,D,B,G = (V,E), d, c) do CEDP, uma coleção E = {E1, . . . , Em}de m subconjuntos de E é uma solução factível somente se:

1. E for uma divisão de E. Para tanto, é necessário que:

(a) Ei ∩ Ej 6= ∅ para todo i, j ∈ {1, . . . ,m} com i 6= j, isto é, cada aresta sejaalocada a no máximo um distrito;

(b)m⋃j=1

Ej = E, isto é, cada aresta seja alocada a no mínimo um distrito;

2. cada distrito Ej ∈ E seja conexo, isto é, que G[Ej] seja conexo para todo Ej ∈ E ;

3. cada distrito Ej ∈ E respeite a capacidade máxima de distritamento D, isto é, quedEj≤ D para todo Ej ∈ E ;

4. cada distrito Ej ∈ E respeite o desbalanceamento máximo B. Para tanto, é neces-sário que:

(a) dEj≥ (1−B)d̄E para todo Ej ∈ E ;

(b) dEj≤ (1 +B)d̄E para todo Ej ∈ E .

A heurística construtiva da Seção 6.1.1 e a heurística lagrangiana da Seção 6.3.1,podem obter soluções não factíveis, isto é, podem obter coleções E = {E1, . . . , Em} de msubconjuntos de E que violam um ou mais dos critérios de factibilidade elencados acima.Logo, um método que factibiliza tais soluções faz-se necessário.

33

Algoritmo 1 Heurística Construtiva (O(m|E|2))1: Heurística-Construtiva(m, D, B, G = (V,E), d, c)2: para todo j ∈ {1, . . . ,m} faça3: Ej ← ∅;4: fim para

5: enquanto E \m⋃j=1

Ej 6= ∅ faça

6: CL← ∅;7: para todo j ∈ {1, . . . ,m} faça8: se Ej 6= ∅ ∧ dEj

< (1−B)d̄E então9: Seja Vj ⊆ V tal que G[Ej] = (Vj, Ej);

10: para todo e ∈ δG(Vj) \m⋃k=1

Ek faça

11: se dEj+ 2de ≤ min

{D, (1 +B)d̄E

}então

12: CL← CL ∪ {(e, j)};13: fim se14: fim para15: fim se16: fim para17: se CL = ∅ então18: para todo j ∈ {1, . . . ,m} faça19: se Ej = ∅ então20: para todo e ∈ E \

m⋃k=1

Ek faça

21: CL← CL ∪ {(e, j)};22: fim para23: senão24: Seja Vj ⊆ V tal que G[Ej] = (Vj, Ej);

25: para todo e ∈ δG(Vj) \m⋃k=1

Ek faça


{D, (1 +B)d̄E

}então

27: CL← CL ∪ {(e, j)};28: fim se29: fim para30: fim se31: fim para32: fim se

34

33: se CL = ∅ então34: para todo j ∈ {1, . . . ,m} faça35: para todo e ∈ E \

m⋃k=1

Ek faça


{D, (1 +B)d̄E

}então

37: CL← CL ∪ {(e, j)};38: fim se39: fim para40: fim para41: fim se42: se CL = ∅ então43: para todo j ∈ {1, . . . ,m} faça44: para todo e ∈ E \

m⋃k=1

Ek faça

45: CL← CL ∪ {(e, j)};46: fim para47: fim para48: fim se49: Sejam minC e maxC os valores mínimo e máximo dos candidatos em CL,

respectivamente;50: RCL← ∅;51: para todo (e, j) ∈ CL faça52: se ce,j ≥ maxC − α(maxC −minC) então RCL← RCL ∪ {(e, j)}53: fim se54: fim para55: Escolha um candidato (e, j) ∈ RCL aleatoriamente;56: Ej ← Ej ∪ {e};57: retorna E = {E1, . . . , Em};58: fim enquanto59: fim

35

No Algoritmo 2 apresenta-se o pseudo-código do método de factibilização propostopara o CEDP. Na linha 2 factibiliza-se as arestas alocadas a mais de um distrito (critério1.a). Na linha 3 factibiliza-se os distritos desconexos (critério 2). Na linha 4 factibiliza-se os distritos com demanda acima do máximo permitido (critérios 3 e 4.a). Se apósfactibilizar distritos com demanda acima do máximo permitido ainda existir algum dis-trito desconexo, na linha 5 novamente factibiliza-se os distritos desconexos. Na linha 6

factibiliza-se os distritos com demanda abaixo do mínimo permitido (critério 4.b). Porfim, na linha 7 factibiliza-se as arestas que não estão alocadas a nenhum distrito (critério1.b). Note, porém, que como encontrar uma solução factível para o CEDP é um problemaNP-completo, o método de factibilização proposto pode falhar.

Algoritmo 2 Método de Factibilização (O(m|E|3))1: Factibiliza-Solução(m, D, B, G = (V,E), d, c, E = {E1, . . . , Em})2: E ← Factibiliza-Arestas-Alocadas-a-Múltiplos-Distritos(m, D, B, G,d, c, E);

3: E ← Factibiliza-Distritos-Desconexos(m, D, B, G, d, c, E);4: E ← Factibiliza-Distritos-Com-Demanda-Acima-Do-Máximo(m, D, B,G, d, c, E);

5: E ← Factibiliza-Distritos-Desconexos(m, D, B, G, d, c, E);6: E ← Factibiliza-Distritos-Com-Demanda-Abaixo-Do-Mínimo(m, D, B,G, d, c, E);

7: E ← Factibiliza-Arestas-Não-Alocadas(m, D, B, G, d, c, E);8: retorna E ;9: fim

O método que factibiliza as arestas alocadas a mais de um distrito é apresentado noAlgoritmo 3. Para cada e ∈ E, nas linhas 3 ∼ 8 computa-se a quais distritos a arestae está alocada. Se e estiver alocada a mais de um distrito (|distritos| > 1), nas linhas10 ∼ 19 escolhe-se o melhor distrito Ej para se alocar a aresta e e, então, nas linhas20 ∼ 24 desaloca-se a aresta e dos distritos Ek com k 6= j (Ek ← Ek \ {e}).

Uma aresta pode estar alocada em atém distritos. Então, como a operação de inserçãoem conjunto tem complexidade logarítmica no tamanho do conjunto, cada execução dalinha 6 tem complexidade de O(log(m)). Logo, como são executadas m iterações, o laçodas linhas 4 ∼ 8 tem complexidade de O(m log(m)). Analogamente, como um distritopode ter até |E| arestas, cada execução da linha 22 tem complexidade de O(log(|E|)).Logo, o laço das linhas 20 ∼ 24 tem complexidade de O(m log(|E|)). Portanto, como sãorealizadas |E| iterações do laço das linhas 2 ∼ 26, a complexidade do Algoritmo 3 é deO(m|E| log(m|E|))

O método que factibiliza os distritos desconexos é apresentado no Algoritmo 4. Paracada distrito Ej ∈ E , se G[Ej] não for conexo, no laço das linhas 7 ∼ 13 escolhe-se amelhor componente conexa E∗ de Ej, isto é, a componente conexa de maior valor e, emcaso de empate, a de menor cardinalidade. Então, na linha 14 remove-se de Ej as arestas

36

Algoritmo 3 Factibiliza Arestas Alocadas a Múltiplos Distritos (O(m|E| log(m|E|)))1: Factibiliza-Arestas-Alocadas-a-Múltiplos-Distritos(m, D, B, G = (V,E),d, c, E = {E1, . . . , Em})

2: para todo e ∈ E faça3: distritos← ∅;4: para todo j ∈ {1, . . . ,m} faça5: se e ∈ Ej então6: distritos← distritos ∪ {j};7: fim se8: fim para9: se |distritos| > 1 então

10: j ← 0;11: maxC ← −∞;12: minD ←∞;13: para todo k ∈ distritos faça14: se maxC < ce,k ∨ (maxC = ce,k ∧minD > dEk

) então15: j ← k;16: maxC ← ce,k;17: minD ← dEk

;18: fim se19: fim para20: para todo k ∈ distritos faça21: se k 6= j então22: Ek ← Ek \ {e};23: fim se24: fim para25: fim se26: fim para27: retorna E ;28: fim

37

das demais componentes conexas (Ej ← E∗).Uma componente conexa de um distrito Ej pode ter até |Ej|−1 arestas. Então, como

um distrito Ej pode ter |E| arestas, o cálculo da linha 10 tem complexidade de O(|E|).Como um distrito Ej pode ter até |Ej| componentes conexas, temos que o laço das linhas7 ∼ 13 é iterado até |E| vezes. Logo, a complexidade do laço das linhas 7 ∼ 13 é deO(|E|2) Portanto, como o laço das linhas 4 ∼ 16 é iterado m vezes, a complexidade doAlgoritmo 4 é de O(m|E|2).

Algoritmo 4 Factibiliza Distritos Desconexos (O(m|E|2))1: Factibiliza-Distritos-Desconexos(m, D, B, G = (V,E), d, c, E = {E1, . . .,Em})

2: para todo j ∈ {1, . . . ,m} faça3: se G[Ej] for desconexo então4: E∗ ← ∅;5: maxC ← −∞;6: maxE ← −∞;7: para todo componente conexa G′ = (V ′, E ′) de G[Ej] faça8: se maxC <

∑e∈E′

ce,j ∨ (maxC =∑e∈E′

ce,j ∧maxE < |E ′|) então

9: E∗ ← E ′;10: maxC ←

∑e∈E′

ce,j;

11: maxE ← |E ′|;12: fim se13: fim para14: Ej ← E∗;15: fim se16: fim para17: retorna E ;18: fim

O método que factibiliza os distritos com demanda acima do máximo permitido éapresentado no Algoritmo 5. Para cada distrito Ej ∈ E , enquanto a demanda de Ej estiveracima do máximo permitido (dEj

> min{D, (1 +B)d̄E

}), no laço das linhas 8 ∼ 22

procura-se a melhor aresta e ∈ Ej para se remover do distrito Ej, preservando-se suaconexidade e respeitando-se a demanda mínima permitida (dEj

− 2de ≥ (1 − B)d̄E). Nolaço das linhas 11 ∼ 20 procura-se um novo distrito Ek 6= Ej, também preservando-se aconexidade do distrito Ek e respeitando-se a demanda máxima permitida (dEk

+ 2de ≤min

{D, (1 +B)d̄E

}). Caso não se encontre nenhuma aresta, no laço das linhas 24 ∼ 30

procura-se a melhor aresta e ∈ Ej para se remover do distrito Ej, porém sem preservar aconexidade nem respeitar a demanda mínima permitida. Por fim, na linha 32 desaloca-sea aresta escolhida e de Ej (Ej ← Ej \{e}) e, caso tenha sido encontrado um novo distritoEk 6= Ej para se alocar e, na linha 34 aloca-se e ao distrito Ek (Ek ← Ek ∪ {e}).

Cada iteração do laço das linhas 11 ∼ 20 é executado em tempo constante e são

38

executadas da ordem de |E| iterações, logo sua complexidade é de O(|E|). Como umdistrito Ej pode ter até |E| arestas, a complexidade do laço das linhas 8 ∼ 22 é de O(|E|2).A cada iteração do laço das linhas 3 ∼ 36 uma aresta é removida de um distrito Ej atéque sua demanda respeite o máximo permitido. No pior caso, Ej passará a ter apenasuma aresta, isto é, serão executadas |Ej| − 1 iterações do laço. Como a complexidade decada iteração é dominada pelo laço das linhas 8 ∼ 22, a complexidade do laço das linhas3 ∼ 36 é de O(|E|3). Portanto, como o laço das linhas 2 ∼ 37 é executado m vezes, acomplexidade do Algoritmo 5 é de O(m|E|3).

O método que factibiliza os distritos com demanda abaixo do mínimo permitido éapresentado no Algoritmo 6. Para cada distrito Ej ∈ E , enquanto a demanda de Ejestiver abaixo do mínimo permitido (dEj

< (1−B)d̄E), no laço das linhas 9 ∼ 15 procura-

se a melhor aresta e não alocada (e /∈m⋃l=1

El) para se alocar ao distrito Ej, preservando-se

a conexidade do distrito Ej e respeitando-se a demanda mínima permitida (dEj+ 2df ≤

min{D, (1 +B)d̄E

}). Caso não se encontre nenhuma aresta, no laço das linhas 17 ∼ 25

procura-se a aresta e já alocada a algum distrito Ek 6= Ej (e ∈ Ek) para ser realocada aodistrito Ej, também preservando-se a conexidade dos distritos Ej e Ek e respeitando-se asdemandas máxima (dEj

+ 2de ≤ min{D, (1 +B)d̄E

}) e mínima (dEk

− 2de ≥ (1−B)d̄E)permitidas. Por fim, se for encontrada uma aresta e, na linha 28 aloca-se e ao distrito Ej(Ej ← Ej ∪ {e}) e, caso a aresta e já estiver alocada a um outro distrito Ek, na linha 30

desaloca-se e do distrito Ek (Ek ← Ek \ {e}).Cada iteração do laço das linhas 9 ∼ 15 é executado em tempo constante e são

executadas da ordem de |E| iterações, logo sua complexidade é de O(|E|). A cada iteraçãodo laço das linhas 3 ∼ 35 uma aresta é adicionada a um distrito Ej até que sua demandarespeite o mínimo permitido. No pior caso, Ej era vazio e passará a ter apenas |E| arestas,isto é, serão executadas |E| iterações do laço. Como a complexidade de cada iteração édominada pelo laço das linhas 9 ∼ 15, a complexidade do laço das linhas 3 ∼ 35 é deO(|E|2). Portanto, como o laço das linhas 2 ∼ 36 é iterado m vezes, a complexidade doAlgoritmo 6 é de O(m|E|2).

O método que factibiliza as arestas não alocadas é apresentado no Algoritmo 7. En-

quanto houver arestas que não estão alocadas a nenhum distrito (m⋃j=1

Ej 6= E), no laço das

linhas 8 ∼ 19 procura-se a melhor aresta e que não está alocada a nenhum distrito (e /∈m⋃j=1

Ej) e o melhor distrito Ej para se alocar a aresta e, conservando-se a conexidade do dis-

trito Ej e respeitando-se a demanda máxima permitida (dEj+2de ≤ min

{D, (1 +B)d̄E

}).

Caso não se encontre nenhuma aresta, no laço das linhas 21 ∼ 31 procura-se a melhoraresta e que não está alocada e o melhor distrito Ej para se alocar a aresta e, porém sempreservar a conexidade nem respeitar a demanda máxima permitida. Por fim, na linha33 aloca-se a aresta e ao distrito Ej (Ej ← Ej ∪ {e}).

39

Algoritmo 5 Factibiliza Distritos Com Demanda Acima Do Máximo (O(m|E|3))1: Factibiliza-Distritos-Com-Demanda-Acima-Do-Máximo(m, D, B, G =

(V,E), d, c, E = {E1, . . . , Em})2: para todo j ∈ {1, . . . ,m} faça3: enquanto dEj

> min{D, (1 +B)d̄E

}faça

4: e← ∅;5: k ← j;6: minC ←∞;7: maxD ← −∞;8: para todo f ∈ Ej faça9: se G[Ej \ {f}] for conexo então

10: maxC ← −∞;

11: para todo g ∈ (δG(f) ∩ (m⋃l=1

El)) \ Ej faça

12: Seja l ∈ {1, . . . ,m} tal que g ∈ El;13: se dEj

−2df ≥ (1−B)d̄E∧dEl+2df ≤ min

{D, (1 +B)d̄E

}∧(e =

∅ ∨ minC > cf,j ∨ (minC = cf,j ∧ (maxD < df ∨ (maxD = df ∧ maxC < cf,l))))então

14: e← f ;15: k ← l;16: minC ← cf,j;17: maxD ← df ;18: maxC ← cf,l;19: fim se20: fim para21: fim se22: fim para23: se e = ∅ então24: para todo f ∈ Ej faça25: se e = ∅ ∨minC > cf,j ∨ (minC = cf,j ∧maxD < df ) então26: e← f ;27: minC ← cf,j;28: maxD ← df ;29: fim se30: fim para31: fim se32: Ej ← Ej \ {e};33: se k 6= j então34: Ek ← Ek ∪ {e};35: fim se36: fim enquanto37: fim para38: retorna E ;39: fim

40

Algoritmo 6 Factibiliza Distritos Com Demanda Abaixo Do Mínimo (O(m|E|2))1: Factibiliza-Distritos-Com-Demanda-Abaixo-Do-Mínimo(m, D, B, G =

(V,E), d, c, E = {E1, . . . , Em})2: para todo j ∈ {1, . . . ,m} faça3: enquanto dEj

< (1−B)d̄E faça4: e← ∅;5: k ← j;6: maxC ← −∞;7: maxD ← −∞;8: Seja Vj ⊆ V tal que G[Ej] = (Vj, Ej);

9: para todo f ∈ δG(Vj) \ (m⋃l=1

El) faça

10: se dEj+ 2df ≤ min

{D, (1 +B)d̄E

}∧ (e = ∅ ∨maxC < cf,j ∨ (maxC =

cf,j ∧maxD < df )) então11: e← f ;12: maxC ← cf,j;13: maxD ← df ;14: fim se15: fim para16: se e = ∅ então17: para todo f ∈ δG(Vj) ∩ (

m⋃l=1

El) faça

18: Seja l ∈ {1, . . . ,m} tal que f ∈ El;19: se dEj

+ 2df ≤ min{D, (1 +B)d̄E

}∧dEl

−2df ≥ (1−B)d̄E ∧G[El \{f}] for conexo ∧ (e = ∅ ∨maxC < cf,j − cf,l ∨ (maxC = cf,j − cf,l ∧maxD < df ))então

20: e← f ;21: k ← l;22: maxC ← cf,j − cf,l;23: maxD ← df ;24: fim se25: fim para26: fim se27: se e 6= ∅ então28: Ej ← Ej ∪ {e};29: se k 6= j então30: Ek ← Ek \ {e};31: fim se32: senão33: break;34: fim se35: fim enquanto36: fim para37: retorna E ;38: fim

41

Cada iteração do laço das linhas 9 ∼ 18 é executado em tempo constante e sãoexecutadas da ordem de |E| iterações, logo sua complexidade é de O(|E|). O laço daslinhas 8 ∼ 19 é iterado da ordem de |E| vezes e cada iteração tem complexidade deO(|E|), logo sua complexidade é de O(|E|2). Cada iteração do laço das linhas 22 ∼ 30

é executado em tempo constante e são executadas m iterações, logo sua complexidade éde O(m). O laço das linhas 21 ∼ 31 é iterado da ordem de |E| vezes e cada iteração temcomplexidade de O(m), logo sua complexidade é de O(m|E|). Então, a complexidade decada iteração do laço das linhas 2 ∼ 34 é de O(|E|(m+ |E|)). A cada iteração, uma arestaé alocada até que todas as arestas estejam alocadas. Logo, são executadas da ordem de|E| iterações. Portanto, a complexidade do Algoritmo 7 é de O(|E|2(m+ |E|)).

6.1.3 Heurística de Busca Local

Uma heurística de busca local é um método utilizado para resolver problemas de oti-mização que se inicia a partir de uma solução factível inicial e, então, iterativamentemelhora a solução atual enquanto for possível, isto é, move-se para uma solução factívelde melhor valor na vizinhança da solução atual até que um ótimo local seja alcançado.Tipicamente, cada solução factível tem mais de uma solução vizinha e a escolha de paraqual delas a busca irá mover-se é tomada utilizando apenas informações sobre as soluçõesna vizinhança da solução atual, por isso o nome busca local.

No Algoritmo 8 apresenta-se o pseudo-código de uma heurística de busca local parao CEDP. Primeiramente, na linha 2 procura-se a permutação dos distritos da soluçãoinicial que resulta no distritamento de maior valor utilizando-se o método húngaro para oProblema da Atribuição, do inglês Assignment Problem (AP) (KUHN, 1955). O laço daslinhas 5 ∼ 22 é executado enquanto a solução atual puder ser melhorada ou até que |E|melhorias tenham sido feitas. Para cada distrito Ej ∈ E , no laço da linhas 8 ∼ 20 procura-se uma aresta e ∈ Ej e um novo distritos Ek 6= Ej para se realocar e que obtenha um lucromelhor (ce,j < ce,k), preservando-se a conexidade dos distritos Ej e Ek e respeitando-se asdemandas mínima (dEj

− 2de ≥ (1−B)d̄E) e máxima (dEk+ 2de ≤ min

{D, (1 +B)d̄E

})

permitidas. Por fim, como as arestas em cada distrito possivelmente foram alteradas, nalinha 23 novamente procura-se pela melhor permutação dos distritos.

As linhas 2 e 23, que invocam o método húngaro para o AP, tem complexidade deO(m3). Como um distrito pode ter até |E| arestas, cada execução das linhas 13 e 14 temcomplexidade de O(log(|E|)). No pior caso, o laço das linhas 10 ∼ 18 é iterado |E| vezes,logo sua complexidade é de O(|E| log(|E|)). O laço das linhas 8 ∼ 20 é iterado da ordemde |E| vezes, logo sua complexidade é de O(|E|2 log(|E|)). O laço das linhas 7 ∼ 21

é iterado m vezes, logo sua complexidade é de O(m|E|2 log(|E|)). Por fim, o laço daslinhas 5 ∼ 22 é iterado, no máximo, |E| vezes e sua complexidade é de O(m|E|3 log(|E|)).Portanto, a complexidade do Algoritmo 8 é de O(m3 +m|E|3 log(|E|)).

42

Algoritmo 7 Factibiliza Arestas Não Alocadas (O(|E|3 +m|E|2))1: Factibiliza-Arestas-Não-Alocadas(m, D, B, G = (V,E), d, c, E ={E1, . . . , Em})

2: enquantom⋃j=1

Ej 6= E faça

3: e← ∅;4: j ← 0;5: maxC ← −∞;6: minW ←∞;7: minD ←∞;

8: para todo f ∈ E \ (m⋃k=1

Ek) faça

9: para todo g ∈ δG(f) ∩ (m⋃k=1

Ek) faça

10: Seja k ∈ {1, . . . ,m} tal que g ∈ Ek;11: se dEk

+ 2df ≤ min{D, (1 +B)d̄E

}∧ (e = ∅∨maxC < cf,k ∨ (maxC =

cf,k ∧ (minW > df ∨ (minW = df && minD > dEk)))) então

12: e← f ;13: j ← k;14: maxC ← cf,k;15: minW ← df ;16: minD ← dEk

;17: fim se18: fim para19: fim para20: se e = ∅ então21: para todo f ∈ E \ (

m⋃k=1

Ek) faça

22: para todo k ∈ {1, . . .m} faça23: se e = ∅ ∨maxC < cf,k ∨ (maxC = cf,k ∧ (minW > df ∨ (minW =

df ∧minD > dEk))) então

24: e← f ;25: j ← k;26: maxC ← cf,k;27: minW ← df ;28: minD ← dEk

;29: fim se30: fim para31: fim para32: fim se33: Ej ← Ej ∪ {e};34: fim enquanto35: retorna E ;36: fim

43

Algoritmo 8 Heurística de Busca Local (O(m3 +m|E|3 log (|E|)))1: Heurística-de-Busca-Local(m, D, B, G = (V,E), d, c, E = {E1, . . . , Em})2: E ← Alocacao-De-Custo-Máximo(E);3: melhorou← true;4: contador ← 0;5: enquanto melhorou ∧ contador < |E| faça6: melhorou← false;7: para todo j ∈ {1, . . . ,m} faça8: para todo e ∈ Ej faça9: se G[Ej \ {e}] for conexo ∧dEj

− 2de ≥ (1−B)d̄E então10: para todo f ∈ δG(e) \ Ej faça11: Seja k ∈ {1, . . . ,m} tal que f ∈ Ek;12: se dEk

+ 2de ≤ min{D, (1 +B)d̄E

}∧ ce,j < ce,k então

13: Ej ← Ej \ {e};14: Ek ← Ek ∪ {e};15: melhorou← true;16: contador ← contador + 1;17: fim se18: fim para19: fim se20: fim para21: fim para22: fim enquanto23: E ← Alocacao-De-Custo-Máximo(E);24: retorna E ;25: fim

44

6.2 Metodologias Exatas

Nesta seção são apresentados os algoritmos Branch-and-Bound (B&B) e Branch-and-Cut (B&C), que são paradigmas para resolver problemas de otimização combinatóriadiscretos, muito utilizados para resolver problemas formulados como ILP (WOLSEY,1998; NEMHAUSER; WOLSEY, 1988; BERTSIMAS; TSITSIKLIS, 1997).

6.2.1 Branch-and-Bound

O método B&B para ILP utiliza uma abordagem de divisão e conquista para exploraro conjunto de soluções inteiras factíveis. Como explorar todo o conjunto é impraticávelpara a maioria dos problemas, são utilizados limitantes primais e duais no valor ótimopara evitar explorar certas partes do conjunto.

Para a metodologia B&B, utilizou-se a formulação ILP por fluxo em redes no grafolinha, apresentada na Seção 5.2. Seja S = {x ∈ B|U |×m : x satisfaz a (5.8), (5.9),(5.10), (5.11), (5.12), (5.13), (5.14), (5.15) e (5.16) para algum y ∈ B|A′\A|×m e algumz ∈ R2|A′|×m} o conjunto de soluções inteiras factíveis para o CEDP:

w = max

{∑e∈E

m∑j=1

ce,jxe,j : x ∈ S

}.

Divide-se recursivamente o conjunto S em uma coleção finita de subconjuntos S =

{S1, . . . , Sk} e resolve-se separadamente cada um dos subproblemas:

wi = max

{∑e∈E

m∑j=1

ce,jxe,j : x ∈ Si

}, i ∈ {1, . . . k}.

Os subproblemas são resolvidos recursivamente e suas soluções ótimas são comparadas,retornando-se a melhor. Esta é a parte de ramificação do método, que induz uma árvore desubproblemas. Esta ramificação pode ser vista como uma enumeração total dos elementosde S. Porém, como a enumeração total não é viável para a maioria dos problemas, precisa-se evitar dividir o conjunto inicial S em muitos subconjuntos. Se for possível estabelecerque não são mais necessárias subdivisões no subconjunto Si ∈ S, então diz-se que a árvorede subproblemas pode ser podada no nó correspondente a Si.

Sejam wi e wi, respectivamente, limitantes primal e dual de wi, no valor de umasolução ótima de cada subproblema Si ∈ S. Então w =

kmaxi=1{wi} e w =

kmaxi=1{wi}

são, respectivamente, limitantes primal e dual de w, o valor de uma solução ótima parao problema original S. Os limitantes primais podem ser obtidos por meio de soluçõesfactíveis para os subproblemas, enquanto que os limitantes duais podem ser obtidos pormeio de relaxações ou dualidade.

45

Pode-se podar a árvore de subproblemas e, assim, enumerar um grande número desoluções implicitamente, se qualquer uma das seguintes condições é satisfeita:

• Poda por inviabilidade: Si = ∅.

• Poda por dominância de valor: wi ≤ w.

• Poda por otimalidade: uma solução ótima para Si é conhecida.

No Algoritmo 9 apresenta-se o pseudo-código de um algoritmo B&B para o CEDP.Na implementação do método B&B, foi utilizado o resolvedor Gurobi 8.11. Também

utilizou-se a heurística construtiva da Seção 6.1.1 e o método de factibilização da Seção6.1.2 para obter uma solução inicial como ponto de partida do Gurobi. Além disso,utilizou-se a heurística de busca local da Seção 6.1.3 para melhorar as solução factíveisobtidas pelo Gurobi, caso não fosse possível obter a solução ótima dentro do limite detempo.

6.2.2 Branch-and-Cut

O método B&C é uma variante do método B&B no qual planos de corte são gerados aolongo da árvore de subproblemas. A ideia desse método é explorar cada nó em busca demelhores limitantes duais. Existe, na prática, um trade-off, pois, se muitos cortes foremadicionados em cada nó, a reotimização pode ficar muito lenta.

Para a metodologia B&C, utilizou-se a formulação ILP do CEDP por corte de arestas,apresentada na Seção 5.1. As restrições (5.5) são em número exponencial no tamanho daentrada, de modo que não é possível carregar todas elas na memória para uma instânciade interesse prático. Logo, inicialmente carrega-se o modelo da Seção 5.1 sem as restrições(5.5) e, ao encontrar uma solução relaxada x∗ para o problema, adiciona-se ao modelo umaou mais restrições válidas violadas por x∗ como lazy-constraints, caso exista. O problemade encontrar uma ou mais desigualdades válidas violadas por uma solução relaxada échamado de problema de separação.

No Algoritmo 10 apresenta-se o pseudo-código de um algoritmo para o problema deseparação do CEDP. Primeiramente, na linha 2 constrói-se o conjunto R de desigualdadesválidas violadas pela solução atual (R← ∅). Para cada distrito Ej ∈ E , no laço das linhas5 ∼ 9 computa-se as arestas e que estão no distrito Ej na solução atual. Se o distrito Ejnão for conexo, no laço das linhas 11 ∼ 15 percorre-se cada par de componentes conexasE ′ e E ′′ de Ej e cada par de arestas (e, f) ∈ E ′×E ′′, adicionando-se a desigualdade válidaviolada xe,j + xf,j −

∑g∈δG(V ′)

xg,j ≤ 1 a R . Por fim, na linha 18 retorna-se o conjunto R

com todas as desigualdades válidas violadas que foram encontradas.Como δG(V ′) pode ter da ordem de |E| arestas, cada execução da linha 13 tem comple-

xidade de O(|E|). Cada componente conexa de um distrito tem da ordem de |E| arestas,

46

Algoritmo 9 Branch-and-Bound1: Branch-and-Bound(S)2: S ← {S};3: x? ← ∅;4: w ← −∞;5: w ← −∞;6: enquanto S 6= ∅ faça7: Selecione um problema ativo Si de S8: se Si = ∅ então9: S ← S \ {Si};

10: senão11: Compute um limitante dual wi e uma solução dual x′ para Si;12: se wi ≤ w então13: S ← S \ {Si};14: senão15: se uma solução ótima x?i para Si de valor wi é conhecida então16: se w ≤ wi então17: x? ← x?i ;18: w ← wi;19: fim se20: S ← S \ {Si};21: senão22: Divida o problema Si em uma coleção de subproblemas Si;23: S ← S \ {Si};24: S ← S ∪ Si;25: fim se26: fim se27: fim se28: fim enquanto29: retorna x?;30: fim

47

logo o laço das linhas 12 ∼ 14 tem complexidade de O(|E|3). No pior caso, todas asaresta um distrito Ej podem ser desconexas das demais, de modo que Ej pode ter daordem de |E| componentes conexas. Logo, são executadas da ordem de |E|2 iterações dolaço das linhas 11 ∼ 15 de modo que sua complexidade é de O(|E|5). Por fim, como sãoexecutadas m iterações do laço das linhas 3 ∼ 17, a complexidade do Algoritmo 10 é deO(m|E|5).

Algoritmo 10 Algoritmo para o Problema de Separação do CEDP (O(m|E|5))1: Algoritmo-para-o-Problema-de-Separação-do-CEDP(m, D, B, G =

(V,E), d, c, x∗)2: R← ∅;3: para todo j ∈ {1, . . . ,m} faça4: Ej ← ∅;5: para todo e ∈ E faça6: se x∗e,j = 1 então7: Ej ← Ej ∪ {e};8: fim se9: fim para

10: se G[Ej] não for conexo então11: para todo par (G′ = (V ′, E ′), (G′′ = (V ′′, E ′′)) de componentes conexas

distintas de G[Ej] faça12: para todo (e, f) ∈ E ′ × E ′′ faça13: R← R ∪ {xe,j + xf,j −

∑g∈δG(V ′)

xg,j ≤ 1};

14: fim para15: fim para16: fim se17: fim para18: retorna R;19: fim

Assim como no método B&B, na implementação do método B&C, foi utilizado oresolvedor Gurobi 8.11. Também utilizou-se a heurística construtiva da Seção 6.1.1 e ométodo de factibilização da Seção 6.1.2 para obter uma solução inicial como ponto departida. Também utilizou-se a heurística de busca local da Seção 6.1.3 para melhorar assolução factiveis obtidas pelo Gurobi, caso não fosse possível obter a solução ótima dentrodo limite de tempo.

6.3 Meta-heurísticas

Para instâncias grandes, onde a aplicação de uma metodologia exata é computacional-mente inviável, uma heurística torna-se uma alternativa para a obtenção de soluçõesfactíveis de boa qualidade, porém sem garantia de otimalidade, em tempo computacionalpolinomial no tamanho da entrada.

48

6.3.1 Heurística Lagrangiana

Uma técnica bem conhecida na literatura para encontrar limitantes duais para problemasde otimização combinatória formulados como ILP é a relaxação Lagrangiana (NEMHAU-SER; WOLSEY, 1988; WOLSEY, 1998; BEASLEY, 1993).

Considere o ILP genérico:

w = max{cx : x ∈ S}, onde S = {x ∈ Zn+ : Ax ≤ b}

que pode ser reescrito como:

w = max{cx}

A1x ≤ b1(restrições complicadoras)

A2x ≤ b2(restrições tratáveis)

x ∈ Zn+

(IP)

onde A =

(A1

A2

)e b =

(b1

b2

). Suponha que A2x ≤ b2 são m −m1 “restrições tratáveis”,

no sentido que um programa com apenas estas restrições é fácil. Deste modo, removendo-se as m1 “restrições complicadoras” A1x ≤ b1, a relaxação resultante é mais fácil de seresolver do que o problema original. Porém, o limitante dual obtido por esta relaxaçãopode ser fraco, pois algumas restrições importantes são completamente ignoradas.

Uma maneira de atacar esta dificuldade é introduzindo um vetor de multiplicadores deLagrange λ ∈ Rm1

+ , o qual é anexado a este conjunto de restrições e levado para a funçãoobjetivo, resultando no seguinte problema:

w(λ) = max{cx+ λ(b1 − A1x)}

A2x ≤ b2

x ∈ Zn+

(RL(λ))

O problema RL(λ) é chamado de relaxação Lagrangiana com parâmetro λ ou ProblemaPrimal Lagrangiano. A relaxação Lagrangiana não contém as restrições complicadoras,que passam a ser consideradas na função objetivo com “penalidade” λ(b1 − A1x). Vistoque λ ≥ 0, violações de A1x ≤ b1 fazem a penalidade ser negativa, assim, intuitivamente,A1x ≤ b1 será satisfeita se λ for adequadamente grande.

Para encontrar o melhor limitante dual dentre a infinidade de valores possíveis paraλ, torna-se necessário resolver o Problema Dual Lagrangiano:

wDL = min{w(λ) : λ ∈ Rm1+ }. (DL)

49

Uma técnica disponível para resolver o problema DL é o método do subgradiante, queé um procedimento iterativo onde, a partir de um conjunto inicial de multiplicadores deLagrange, novos multiplicadores são gerados de forma sistemática.

Em uma heurística Lagrangiana, toma-se uma solução para o problema RL(λ) e tenta-se convertê-la em uma solução factível para o problema IP por meio um método defactibilização. Esta solução factível fornece um limitante primal no valor de uma soluçãoótima para o problema IP.

A característica chave da heurística Lagrangiana é que, assim como o valor da soluçãopara o RL(λ) fornece informações úteis (um limitante dual no valor de uma solução ótimapara o problema IP), a estrutura da solução para o problema RL(λ) (isto é, o valor dasvariáveis) também pode fornecer informações úteis sobre a estrutura da solução ótimapara o problema IP. Assim, cada vez que resolve-se o problema RL(λ) dentro do métododo subgradiente, a heurística Lagrangiana tem uma oportunidade para transformar asolução para o problema RL(λ) em uma solução para o problema IP.

Para a heurística Lagrangiana, utilizou-se a formulação ILP do CEDP por fluxo emredes no grafo linha, apresentada na Seção 5.2. As seguintes restrição foram relaxadas:(5.11), (5.12), (5.13), (5.14), (5.15) e (5.16).

Para relaxar as restrições (5.11), anexou-se os multiplicadores de Lagrange λIj ∈R,∀j ∈ {1, . . . ,m}, obtendo-se a penalidade:

m∑j=1

λIj (1−∑e∈U

y{e′,e},j) =m∑j=1

λIj −m∑j=1

∑e∈E

y{e′,e},j

Para relaxar a restrição (5.12), anexou-se o multiplicador de Lagrange λII ∈ R, obtendo-sea penalidade:

λII(1− 1

|U |

m∑j=1

∑e∈U

ze′,e,j) = λII −m∑j=1

∑e∈U

λII

|U |z{e′,e},j

Para relaxar as restrições (5.13), anexou-se os multiplicadores de Lagrange λIIIe,j ∈ R+,∀e ∈U, j ∈ {1, . . . ,m}, obtendo-se a penalidade:

m∑j=1

∑e∈U

λIIIe,j (−ze′,e,j + |U |y{e′,e},j) = −m∑j=1

∑e∈U

λIIIe,j ze′,e,j +m∑j=1

∑e∈U

|U |λIIIe,j y{e′,e},j

Para relaxar as restrições (5.14), anexou-se os multiplicadores de Lagrange λIV{e,f},j ∈R+,∀{e, f} ∈ A, j ∈ {1, . . . ,m}, obtendo-se a penalidade:

m∑j=1

∑e∈U

∑{e,f}∈δL(G)({e})

λIVe,f,j(−ze,f,j + |U |xe,j) =

50

= −m∑j=1

∑e∈U

∑{e,f}∈δL(G)({e})

λIVe,f,jze,f,j +m∑j=1

∑e∈U

(|U |∑

{e,f}∈δL(G)({e})

λIVe,f,j)xe,j

Para relaxar as restrições (5.15), anexou-se os multiplicadores de Lagrange λV{e,f},j ∈R+, ∀{e, f} ∈ A, j ∈ {1, . . . ,m}, obtendo-se a penalidade:

m∑j=1

∑e∈U

∑{e,f}∈δL(G)({e})

λ5e,f,j(−zf,e,j + |U |xe,j) =

= −m∑j=1

∑e∈U

∑{e,f}∈δL(G)({e})

λVe,f,jzf,e,j +m∑j=1

∑e∈U

(|U |∑

{e,f}∈δL(G)({e})

λVe,f,j)xe,j

Por fim, para relaxar as restrições (5.15), anexou-se os multiplicadores de LagrangeλV Ie,j ,∀e ∈ U, j ∈ {1, . . . ,m}, obtendo-se a penalidade:

m∑j=1

∑e∈U

λV Ie,j (−ze′,e,j −∑

{e,f}∈δL(G)({e})

zf,e,j + ze,e′,j +∑

{e,f}∈δL(G)({e})

ze,f,j + xe,j) =

= −m∑j=1

λV Ie,j ze′,e,j −m∑j=1

∑e∈U

∑{e,f}∈δL(G)({e})

λV Ie,j zf,e,j +m∑j=1

λV Ie,j ze,e′,j+

+m∑j=1

∑e∈U

∑{e,f}∈δL(G)({e})

λV Ie,j ze,f,j +m∑j=1

∑e∈U

λV Ie,jxe,j

Somando estas penalidades à função objetivo 5.7, obtemos o seguinte Problema PrimalLagrangiano:

Problema Primal Lagrangiano:Variáveis de decisão:

xe,j =


0, caso contrário.

y{e′,e},j =


0, caso contrário.


51

Função objetivo:

max

{m∑j=1

∑e∈U

(ce,j + |U |∑

{e,f}∈δL(G)({e})

(λIV{e,f},j + λV{e,f},j) + λV Ie,j )xe,j

+m∑j=1

∑e∈U

(|U |λIIIe,j − λIj )y{e′,e},j

−m∑j=1

∑e∈U

(λII

|U |+ λIIIe,j + λV Ie,j )ze′,e,j +

m∑j=1

∑e∈U

λV Ie,j ze,e′,j

+m∑j=1

∑e∈U

∑{e,f}∈δL(G)({e})

(λV Ie,j − λIV{e,f},j)ze,f,j

−m∑j=1

∑e∈U

∑{e,f}∈δL(G)({e})

(λV{e,f},j + λV Ie,j )zf,e,j

+m∑j=1

λIj + λII

}

(6.1)

Restrições:

m∑j=1

xe,j = 1,∀e ∈ U (6.2)

2∑e∈U

dexe,j ≤ min

{D,

2(1 +B)

m

∑e∈U

de

}, ∀j ∈ {1, . . . ,m} (6.3)

2∑e∈U

dexe,j ≥2(1−B)

m

∑e∈U

de,∀j ∈ {1, . . . ,m} (6.4)

xe,j ∈ {0, 1}, ∀e ∈ U, j ∈ {1, . . . ,m} (6.5)

y{e′,e},j ∈ {0, 1},∀{e′, e} ∈ A′ \ A, j ∈ {1, . . . ,m} (6.6)

ze,f,j ∈ [0, |U |],∀{e, f} ∈ A′, j ∈ {1, . . . ,m} (6.7)

As restrições (6.2), (6.3), (6.4), (6.5), (6.6) e (6.7) são idênticas às restrições (5.8),(5.9), (5.10), (5.17), (5.18) e (5.19) da Seção 5.2, respectivamente. Como as restriçõesnão relacionam as variáveis xe,j com as variáveis y{e′,e},j e as variáveis ze,f,j, pode-se dividiro Problema Primal Lagrangiano em dois subproblemas:

Subproblema Primal Lagrangiano A:Variáveis de decisão:

52

xe,j =


0, caso contrário.

Função objetivo:

max

m∑j=1

∑e∈E

(ce,j + |U |∑

{e,f}∈δL(G)({e})

(λIV{e,f},j + λV{e,f},j) + λV Ie,j )xe,j

(6.8)

Restrições:

m∑j=1

xe,j = 1,∀e ∈ U (6.9)

2∑e∈U

dexe,j ≤ min

{D,

2(1 +B)

m

∑e∈U

de

}, ∀j ∈ {1, . . . ,m} (6.10)

2∑e∈U

dexe,j ≥2(1−B)

m

∑e∈U

de,∀j ∈ {1, . . . ,m} (6.11)

xe,j ∈ {0, 1}, ∀e ∈ U, j ∈ {1, . . . ,m} (6.12)

Subproblema Primal Lagrangiano B:Variáveis de decisão:

y{e′,e},j =


0, caso contrário.


53

Função objetivo:

max

{m∑j=1

∑e∈U

(|U |λIIIe,j − λIj )y{e′,e},j

−m∑j=1

∑e∈U

(λII

|U |+ λIIIe,j + λV Ie,j )ze′,e,j +

m∑j=1

∑e∈U

λV Ie,j ze,e′,j

+m∑j=1

∑e∈U

∑{e,f}∈δL(G)({e})

(λV Ie,j − λIV{e,f},j)ze,f,j

−m∑j=1

∑e∈U

∑{e,f}∈δL(G)({e})

(λV{e,f},j + λV Ie,j )zf,e,j

+m∑j=1

λIj + λII

}

(6.13)

Restrições:

y{e′,e},j ∈ {0, 1},∀{e′, e} ∈ A′ \ A, j ∈ {1, . . . ,m} (6.14)

ze,f,j ∈ [0, |U |],∀{e, f} ∈ A′, j ∈ {1, . . . ,m} (6.15)

O Subproblema Primal Lagrangiano A consiste em uma variante do Problema dasMúltiplas Mochilas, do inglês Multiple Knapsack Problem (MKP). Uma definição formaldo MKP é apresentada a seguir. Sejam ∈ Z∗+ o número de mochilas; D ∈ Z∗+ a capacidadede cada mochila; B ∈ [0, 1] o desbalanceamento máximo permitido para cada mochila;U = {e1, . . . , e|U |} o conjunto de itens. Associada a cada item e ∈ U há uma demandade ∈ Z+. Associado a cada item e ∈ U e a cada j ∈ {1, . . . ,m} há um lucro ce,j ∈ Z+

obtido ao se colocar o item e na j-ésima mochila. O objetivo do MKP consiste emdividir U em uma coleção U = {U1, . . . , Um} de m mochilas, maximizando o lucro total erespeitando a capacidade e o desbalanceamento máximo.

O Subproblema Primal Lagrangiano A apresenta subestrutura ótima, isto é, pode-seobter uma solução ótima para ele colocando-se um dos itens em uma das mochilas e, então,resolvendo-se o subproblema que consiste em colocar o restante dos itens nas mochilas comas capacidades residuais. Logo, o Subproblema Primal Lagrangiano A pode ser resolvidopor meio da programação dinâmica definida pela recorrência apresentada a seguir. SejaDmax = min

{D, (1 +B)d̄U

}a capacidade máxima de cada mochila; Dmin = (1 − B)d̄U

a demanda mínima de cada mochila; d̃Uj= Dmax − dUj

a capacidade residual de cadamochila; c̃e,j = ce,j + |U |

∑{e,f}∈δL(G)({e})

(λIV{e,f},j + λV{e,f},j) + λV Ie,j o lucro Lagrangiano obtido

ao se colocar o item e ∈ U na mochila Uj. Definimos o valor ótimo obtido ao se alocar

54

os i primeiros itens em mochilas com d̃Ujde capacidade residual DP (i, d̃U1 , . . . , d̃Um)

recursivamente da seguinte maneira:

DP (i, d̃U1 , . . . , d̃Um) =

−∞, se ∃Uj ∈ U(d̃Uj< 0);

−∞, se i = 0 ∧ ∃Uj ∈ U(d̃Uj> Dmax −Dmin);

0, se i = 0 ∧ ∀Uj ∈ U(0 ≤ d̃Uj≤ Dmax −Dmin);

mmaxj=1

{DP (i− 1, d̃U1 , . . . , d̃Uj

− 2d̃ei , . . . , d̃Um) + c̃ei,j

}caso contrário.

O valor ótimo obtido ao se colocar os i primeiros itens em mochilas com d̃Ujde capa-

cidade residual DP (i, d̃Um , . . . , d̃Um) é dado pelo máximo de se colocar o i-ésimo item namochila Uj e, então, colocar os i − 1 primeiros itens nas mochilas, para cada Uj ∈ U .Se alguma mochila Uj ∈ U teve sua capacidade excedida (dUj

> Dmax ⇒ −dUj<

−Dmax ⇒ Dmax − dUj< Dmax − Dmax ⇒ d̃Uj

< 0) ou se todas os itens foram colo-cados em algum mochila (i = 0) e alguma mochila Uj ∈ U não atingiu a demanda mínima(dUj

< Dmin ⇒ −dUj> −Dmin ⇒ Dmax − dUj

> Dmax − Dmin ⇒ d̃Uj> Dmax − Dmin),

então DP (i, d̃U1 , . . . , d̃Um) = −∞, de modo que uma solução válida sempre terá valormelhor.

O valor ótimo do Subproblema Primal Lagrangiano A é obtido computando-seDP (|U |, Dmax, . . . , Dmax). Porém, pode ser necessário resolver da ordem deO(|U |(Dmax)m)

subproblemas, o que, na prática, mostrou-se ineficaz. Logo, optou-se por resolver o Sub-problema Primal Lagrangiano A utilizando-se o Gurobi.

Como as restrições do Subproblema Primal Lagrangiano B apenas definem o domíniodas variáveis y{e′,e},j e ze,f,j, ele pode ser resolvido por inspeção da seguinte maneira:

y{e′,e},j =

1, se |U |λIIIe,j − λIj > 0,

0, caso contrário.∀e ∈ U, j ∈ {1, . . . ,m}

ze′,e,j =

|U |, seλII

|U |+ λIIIe,j + λV Ie,j < 0,


ze,e′,j =

|U |, se λV Ie,j > 0,


ze,f,j =

|U |, se λV Ie,j − λIV{e,f},j > 0,

0, caso contrário.∀e ∈ U, {e, f} ∈ δL(G)({e}), j ∈ {1, . . . ,m}

55

zf,e,j =

|U |, se λV{e,f},j + λV Ie,j < 0,

0, caso contrário.∀e ∈ U, {e, f} ∈ δL(G)({e}), j ∈ {1, . . . ,m}

6.3.2 GRASP

Feo e Resende (1995) apresentam o Procedimento de Busca Adaptativo Aleatório Guloso,do inglês Greedy Randomized Adaptive Search Procedure (GRASP), como uma meta-heurística de dois estágios. O primeiro estágio é responsável pela construção de umasolução inicial a partir de uma heurística construtiva gulosa-aleatória (Seção 6.1.1). Osegundo estágio realiza uma busca local no intuito de explorar a vizinhança da soluçãoinicial até atingir um ótimo local do espaço de soluções (Seção 6.1.3). Após certo númerode iterações, a melhor solução encontrada é retornada como a solução final da heurística.

Assis, Franca e Usberti (2014) obtiveram bons resultados ao empregar o GRASP pararesolver o MCRP, outro problema de distritamento similar ao CEDP.

No Algoritmo 11 apresenta-se o pseudo-código de um algoritmo GRASP para o CEDP.Primeiramente, na linha 2 inicia-se a melhor solução encontrada como uma solução vazia.Para cada iteração do laço das linhas 3 ∼ 14, na linha 4 constrói-se uma nova soluçãoutilizando-se a heurística construtiva gulosa-aleatória apresentada na Seção 6.1.1. Casoa solução atual não seja factível, na linha 6 tenta-se factibilizá-la utilizando-se o métodode factibilização apresentado na Seção 6.1.2. Se a solução atual for factível, na linha 9

tenta-se melhorá-la utilizando-se a heurística de busca local apresentada na Seção 6.1.3.Se a melhor solução ainda for vazia ou se a solução atual for melhor, na linha 11 atualiza-se a melhor solução encontrada pelo algoritmo. Por fim, na linha 15 retorna-se a melhorsolução encontrada pelo algoritmo.

56

Algoritmo 11 GRASP1: GRASP(m, D, B, G = (V,E), d, c, E = {E1, . . . , Em})2: E ← ∅;3: enquanto não atingiu critério de parada faça4: E ′ ← Heurística-Construtiva(m,D,B,G, d, c);5: se E ′ não for uma solução factível então6: E ′ ← Factibiliza-Solução(m,D,B,G, d, c, E ′);7: fim se8: se E ′ for uma solução factível então9: E ′ ← Heurística-de-Busca-Local(m,D,B,G, d, c, E ′);

10: se E = ∅ ∨ cE < cE ′ então11: E ← E ′;12: fim se13: fim se14: fim enquanto15: retorna E ;16: fim

57

Capítulo 7

Experimentos Computacionais

7.1 Geração de Instâncias

Um dos pontos mais importantes de uma comparação de metodologias de resolução de umproblema de otimização combinatória é o benchmark de instâncias no qual as metodologiasserão testadas. Embora o ideal fosse testar em um benchmark existente, no caso doCEDP isso não é possível, pois trata-se de um problema novo, de modo que não existeum benchmark na literatura (SILBERHOLZ; GOLDEN, 2010).

Instâncias do CEDP surgem de sua aplicação prática, isto é, de mapa reais. Logo, édesejável que o novo benchmark seja baseado em mapas reais. Porém, grande parte dosdados reais são proprietários e, portanto, de difícil acesso (REEVES, 1993; SILBERHOLZ;GOLDEN, 2010).

Um dos requisitos chave do benchmark que é especialmente importante no teste demeta-heurísticas é que grandes instâncias do CEDP devem ser testadas. Para instânciaspequenas, metodologias de resolução exata geralmente rodam em uma quantidade detempo razoável, ao mesmo tempo que oferecem a vantagem de garantir que uma soluçãoótima será encontrada. Testes de meta-heurísticas devem ser realizados com instânciasgrandes para os quais uma solução ótima não pode ser computada em uma quantidade detempo aceitável. Não é suficiente testar em instâncias pequenas do CEDP e extrapolar osresultados para instâncias maiores; algoritmos podem ter um desempenho diferente tantoem tempo de execução quanto em qualidade de solução em instâncias grandes do CEDP(SILBERHOLZ; GOLDEN, 2010).

Outro ponto crítico para a análise adequada das metodologias é classificar as instânciasdo CEDP que estão sendo testadas, o que pode ajudar pesquisadores da indústria com umdeterminado conjunto de dados a decidir qual metodologia de resolução funcionará melhorpara eles (SILBERHOLZ; GOLDEN, 2010). Deste modo, as instâncias do benchmarkcriado para o CEDP foram classificadas quanto à topologia T do grafo, ao número m dedistritos, ao fator de desbalanceamento máximo permitido B, à capacidade máxima D dos

58

distritos, à quantidade de vértices |V | do grafo e à densidade do grafo, isto é, à quantidadede arestas |E| do grafo. Foram geradas um total de 144 instâncias, utilizando os seguintes

valores: T ∈ {grade, aleatória}, m ∈ {5, 10}, B ∈ {1/2, 1}, D ∈ {(1 +B)

2d̄E , (1 + B)d̄E},

|V | ∈ {25, 49, 100} e |E| ∈ {|V | − 1,3|V | − 2

√|V | − 1

2, 2|V | − 2

√|V |} 1. Os valores ce,j

foram gerados aleatoriamente no intervalo [0,m|E| − 1] com distribuição uniforme.As instâncias com topologia grade foram geradas a partir de perturbações de grafos

grade n × n. Um grafo grade n × n é obtido dispondo-se n2 vértices nos pontos decoordenadas inteiras de um plano de dimensões n× n e, então, conectando-se os vérticesconsecutivos em cada linha e coluna, totalizando n2− 2n arestas. As arestas de um grafograde dividem o plano em quadrados, do mesmo modo que as ruas dividem os mapasreais em quadras. Porém, como os segmentos de ruas possuem tamanhos diferentes e,consequentemente, as quadras não são quadrados perfeitos, foi feita uma perturbação nografos grade com a finalidade de os tornarem mais realistas. Tal perturbação foi obtidaadicionando-se um valor aleatório no intervalo [0, 1/2] às coordenadas de cada vértice.Optou-se por um valor no intervalo [0, 1/2] e não no intervalo [0, 1] pois desta formaevita-se que haja uma discrepância muito grande na demanda das arestas, o que poderiaprovocar problemas de instabilidade numérica.

As instâncias com topologia aleatória foram criadas como subgrafos geradores de grafosaleatórios completos. Um grafo aleatório completo é obtido dispondo-se vértices aleatori-amente no plano, com distribuição uniforme, e, então, conectando-se todo par de vérticescom arestas. Assim como foi feito com as instâncias com topologia grade, tomou-se o cui-dado de não escolher arestas com demandas muito discrepantes ao computar-se o subgrafogerador.

Os dados das instâncias de benchmark são apresentados no Apêndice A.

7.2 Análise dos Resultados

As metodologias de resolução do CEDP, apresentadas no Capítulo 6, foram implemen-tadas em C++ e os programas compilados com o GCC versão 7.4.0, usando nível deotimização -O3. Para as metodologias exatas, apresentadas na Seção 6.2, foi utilizado oresolvedor GUROBI versão 8.11, definindo o número de threads para 1. Os experimen-tos computacionais foram executados em um computador com um processador Intel(R)Xeon(R) CPU E5-2420 com 12 núcleos de 1,90GHz e 15.360KB de cache e 32 GB dememória RAM. Para cada metodologia e instância testados, foi estipulado o tempo limitede uma hora de processamento. Os resultados obtidos são apresentados no Apêndice B.

1|E| = |V | − 1 correspondem a árvores, |E| = 2|V | − 2√|V | correspondem a grafos grade, e |E| =

3|V | − 2√|V | − 1

2correspondem a grafos híbridos, meio termo entre árvores e grafos grade

59

Para comparar as metodologias é necessário definir métricas de desempenho (SIL-BERHOLZ; GOLDEN, 2010). As métricas adotadas neste trabalho foram a quantidadede soluções factíveis e ótimas encontradas e o valor dos melhores limitantes duais e primaisobtidos.

As quantidades de soluções factíveis e de soluções ótimas obtidas por cada metodologiae para cada classe de instâncias estão compiladas nas tabelas 7.1 a 7.7. Pode-se notarque a metodologia GRASP é a mais robusta, tendo encontrado soluções factíveis paraquase todas as instâncias testadas, enquanto que a Heurística Lagrangiana obteve o piordesempenho, encontrando soluções factíveis para apenas 1/4 das instâncias testadas. Poroutro lado, apesar de terem encontrado soluções factíveis para pouco mais que metadedas instâncias testadas, as metodologias exatas encontraram soluções ótimas para cerca de1/3 das instâncias testadas, enquanto que a metodologia GRASP encontrou uma soluçãoótima para apenas uma instância.

Além disso, notou-se que todas as metodologias conseguiram melhores resultados paraas instâncias com menos vértices, com menos distritos, que admitem um maior desba-lanceamento e que têm capacidades máximas maiores. Como esperado, as metodologiasexatas obtiveram um desempenho muito melhor nas instâncias de menor porte, tendoencontrado soluções ótimas para a maioria das instâncias com |V | = 25 e soluções factí-veis para cerca de metade das instâncias com |V | = 49. Poucas soluções factíveis foramobtidas para as instâncias com |V | = 100. Com relação à topologia, observou-se que asmetodologias desempenharam um pouco melhor nas instâncias aleatórias, o que sugereque topologias grade, que são mais semelhantes às topologias reais, são mais difíceis de seresolver.

Tabela 7.1: Soluções Factíveis e Ótimas encontradas por cada Metodologia.Metodologia Soluções Factíveis Soluções Ótimas

Branch-and-Bound 75 (52,08%) 40 (27,78%)Branch-and-Cut 86 (59,72%) 44 (30,56%)GRASP 140 (97,22%) 1 (0,69%)Heurística Lagrangiana 36 (25,00%) 0 (0,00%)

Para analisar comparativamente os limitantes obtidos pelas metodologias, foram utili-zados os gráficos performance profiles, introduzidos por Dolan e Moré (2002). Performanceprofiles consistem nas funções de distribuição cumulativa de métricas de desempenho, cu-jos gráficos revelam as principais características de desempenho (DOLAN; MORÉ, 2002).As figuras 7.1 a 7.7 apresentam os performance profiles dos limitantes duais e primaisobtidos pelas metodologias para cada classe de instância. O limitante “Relaxação Linear”refere-se à relaxação do modelo ILP apresentado na Seção 5.2.

Pode-se notar que a metodologia exata B&B obteve os melhores limitantes duais eque a metodologia GRASP obteve os melhores limitantes primais, enquanto que a Heu-

60

Tabela 7.2: Soluções Factíveis e Ótimas encontradas para cada topologia.T Metodologia Soluções Factíveis Soluções Ótimas

Branch-and-Bound 32 (44,44%) 19 (26,39%)Branch-and-Cut 39 (54,17%) 20 (27,78%)GRASP 70 (97,22%) 1 (1,39%)grade

Heurística Lagrangiana 19 (26,39%) 0 (0,00%)Branch-and-Bound 43 (59,72%) 21 (29,17%)Branch-and-Cut 47 (65,28%) 24 (33,33%)GRASP 70 (97,22%) 0 (0,00%)aleatória

Heurística Lagrangiana 17 (23,61%) 0 (0,00%)

Tabela 7.3: Soluções Factíveis e Ótimas encontradas para cada valor de m.m Metodologia Soluções Factíveis Soluções Ótimas

Branch-and-Bound 44 (61,11%) 24 (33,33%)Branch-and-Cut 48 (66,67%) 24 (33,33%)GRASP 69 (95,83%) 0 (0,00%)5

Heurística Lagrangiana 22 (30,56%) 0 (0,00%)Branch-and-Bound 31 (43,06%) 16 (22,22%)Branch-and-Cut 38 (52,78%) 20 (27,78%)GRASP 71 (98,61%) 1 (1,39%)10


rística Lagrangiana obteve os piores limitantes primais e duais. A Heurística Lagrangianaencontrou limitantes duais até 7, 5 vezes piores que o melhor obtido e limitantes primaiscom apenas cerca de 40% do valor do melhor obtido. O desempenho ruim apresentadopela Heurística Lagrangiana deve-se ao fato de o Problema Primal Lagrangiano obtidona Seção 6.3.1 ser de difícil resolução, de modo que foram executadas poucas iterações dométodo do subgradiente impedindo sua convergência no tempo limite estabelecido.

Embora a metodologia B&B tenha, em geral, obtido melhores limitantes duais e pri-mais do que a metodologia B&C, nota-se que a situação se inverte para instâncias comalta densidade de arestas. Isto ocorre pois instâncias com alta densidade possuem grafoslinha de maior tamanho, aumentando o número de variáveis de decisão e de restrições domodelo ILP apresentado na Seção 5.2 e, consequentemente, impactando o desempenho dametodologia B&B. Reforçando o que já havia sido observado nas tabelas, nota-se que asmetodologias exatas desempenharam melhor em instâncias de menor porte, obtendo osmelhores limitantes primais para mais de 90% das instâncias com |V | = 25, mas obtendolimitantes primais para menos de 20% das instâncias com |V | = 100.

A Figura 7.8 apresenta as soluções obtidas para a instância grid-m5V25E40B05D05pelas metodologias B&B, B&C, GRASP e Heurística Lagrangiana com valores 5445, 5612,5380 e 4895, respectivamente. Já a Figura 7.9 apresenta a solução obtida para a instânciagrid-m10V100E140B05D05, que só conseguiu ser resolvida pela metodologia GRASP.

Analisando a Figura 7.8, pode-se notar que há uma semelhança estrutural nas soluções

61

Tabela 7.4: Soluções Factíveis e Ótimas encontradas para cada valor de B.B Metodologia Soluções Factíveis Soluções Ótimas

Branch-and-Bound 38 (52,78%) 17 (23,61%)Branch-and-Cut 40 (55,56%) 18 (25,00%)GRASP 70 (97,22%) 1 (1,39%)0,5

Heurística Lagrangiana 17 (23,61%) 0 (0,00%)Branch-and-Bound 37 (51,39%) 23 (31,94%)Branch-and-Cut 46 (63,89%) 26 (36,11%)GRASP 70 (97,22%) 0 (0,00%)1,0


Tabela 7.5: Soluções Factíveis e Ótimas encontradas para cada valor de D.D Metodologia Soluções Factíveis Soluções Ótimas

Branch-and-Bound 32 (44,44%) 17 (23,61%)Branch-and-Cut 36 (50,00%) 19 (26,39%)GRASP 68 (94,44%) 0 (0,00%)

(1 +B)

2d̄E

Heurística Lagrangiana 11 (15,28%) 0 (0,00%)Branch-and-Bound 43 (59,72%) 23 (31,94%)Branch-and-Cut 50 (69,44%) 25 (34,72%)GRASP 72 (100,00%) 1 (1,39%)(1 +B)d̄E


de melhor valor. Nas soluções obtidas pelas metodologias B&B e GRASP, as arestas docanto inferior esquerdo foram alocadas ao Distrito 1, enquanto que as arestas do cantosuperior direito foram alocadas ao Distrito 5. Logo, é possível que uma metodologia queutiliza as semelhanças estruturais entre instâncias, como Algoritmos Genéticos, tenhamum bom desempenho ao resolver o CEDP.

Embora os distritos obtidos sejam disjuntos (cada aresta está alocada a apenas umdistrito) pode-se notar que os distritos se cruzam nas soluções obtidas. Nota-se, porexemplo, que as arestas dos Distritos 1 e 6 se cruzam na região central do distritamentoda Figura 7.9. Tal fenômeno ocorre pois não foi levado em consideração o critério decompacidade dos distritos nesse trabalho. Compacidade é um critério de planejamentode um distritamento, onde um distrito é compacto se ele tiver um formato arredondado,não distorcido e sem buracos (KALCSICS, 2015).

62

Tabela 7.6: Soluções Factíveis e Ótimas encontradas para cada valor de |V |.|V | Metodologia Soluções Factíveis Soluções Ótimas

Branch-and-Bound 45 (93,75%) 38 (79,17%)Branch-and-Cut 47 (97,92%) 42 (87,50%)GRASP 45 (93,75%) 1 (2,08%)25




Tabela 7.7: Soluções Factíveis e Ótimas encontradas para cada valor de |E|.|E| Metodologia Soluções Factíveis Soluções Ótimas

Branch-and-Bound 25 (52,08%) 16 (33,33%)Branch-and-Cut 27 (56,25%) 16 (33,33%)GRASP 44 (91,67%) 1 (2,08%)|V | − 1

Heurística Lagrangiana 3 (6,25%) 0 (0,00%)Branch-and-Bound 27 (56,25%) 15 (31,25%)Branch-and-Cut 27 (56,25%) 16 (33,33%)GRASP 48 (100,00%) 0 (0,00%)

3|V | − 2√|V | − 1

2Heurística Lagrangiana 13 (27,08%) 0 (0,00%)Branch-and-Bound 23 (47,92%) 9 (18,75%)Branch-and-Cut 32 (66,67%) 12 (25,00%)GRASP 48 (100,00%) 0 (0,00%)2|V | − 2

√|V |


Figura 7.1: Performance Profiles dos Limitantes.

63

Figura 7.2: Performance Profiles dos Limitantes para cada topologia.

64

Figura 7.3: Performance Profiles dos Limitantes para cada valor de m.

65

Figura 7.4: Performance Profiles dos Limitantes para cada valor de B.

66

Figura 7.5: Performance Profiles dos Limitantes para cada capacidade.

67

Figura 7.6: Performance Profiles dos Limitantes para cada valor de |V |.

68

Figura 7.7: Performance Profiles dos Limitantes para cada densidade.

69

Figura 7.8: Soluções encontradas para a instância grid-m5V25E40B05D05.

70

Figura 7.9: Solução encontrada para a instância grid-m10V100E140B05D05.

71

Capítulo 8

Considerações Finais

Os objetivos principais deste projeto, conforme apresentados no Capítulo 3, consistemem estudar formalmente o CEDP, analisando sua complexidade e propondo modelos ma-temáticos e metodologias de resolução e, também, realizar experimentos computacionaispara comparar o desempenho das metodologias.

No Capítulo 4, foi realizada uma análise formal da complexidade do CEDP, demons-trando que o problema pertence à classe NP-completo e, portanto, é de difícil resolução.No Capítulo 5, foram apresentados dois modelos ILP distintos para o CEDP e, no Ca-pítulo 6, foram propostas metodologias de resolução exatas, baseadas no modelos ILP, emetodologias de resolução meta-heutísticas para o CEDP.

No Capítulo 7, ao analisar os resultados dos experimentos computacionais, constatou-se que a metodologia GRASP obteve o melhor desempenho, enquanto que a HeurísticaLagrangiana obteve o pior desempenho. Além disso, observou-se que há uma semelhançaestrutural entre as melhores soluções obtidas para uma mesma instância, e que os distritosobtidos não são compactos, podendo ocorrer cruzamentos entre eles.

Como trabalhos futuros, sugere-se que se estude outras formulações matemáticas paraCEDP, investigando, por exemplo, formas de quantificar a compacidade dos distritos paraincluir este critério no planejamento do distritamento, de forma a evitar que ocorramcruzamentos. Sugere-se também, realizar uma análise poliédrica do CEDP, com o intuitode se descobrir boas desigualdades válidas que possam ser utilizadas pelos métodos exatos.Quanto às metodologias meta-heurísticas, sugere-se analisar metodologias para o CEDPque se aproveitem das semelhanças estruturais entre as soluções, como, por exemplo,Algoritmos Genéticos.

O código-fonte das implementações das metodologias propostas, o benchmark de ins-tâncias utilizado e os resultados obtidos podem ser acessados em <https://github.com/luishpmendes/mastersproject>.

https://github.com/luishpmendes/mastersproject

https://github.com/luishpmendes/mastersproject

72

Referências Bibliográficas

ASSIS, L. S. de; FRANCA, P. M.; USBERTI, F. L. A redistricting problem appliedto meter reading in power distribution networks. Computers & OperationsResearch, Elsevier, v. 41, p. 65–75, 2014. ISSN 0305-0548. Disponível em:<http://www.sciencedirect.com/science/article/pii/S0305054813002086>.

BAZARAA, M. S.; JARVIS, J. J. Linear programming and network flows. New York,NY: John Wiley & Sons, 1977. ISBN 0471060151.

BEASLEY, J. E. Lagrangian relaxation. In: REEVES, C. R. (Ed.). ModernHeuristic Techniques for Combinatorial Problems. New York, NY, USA: JohnWiley & Sons, Inc., 1993. p. 243–303. ISBN 0-470-22079-1. Disponível em:<http://dl.acm.org/citation.cfm?id=166648.166660>.

BEINEKE, L. W. Characterizations of derived graphs. Journal of CombinatorialTheory, Elsevier, v. 9, n. 2, p. 129–135, 1970. ISSN 0021-9800. Disponível em:<http://www.sciencedirect.com/science/article/pii/S0021980070800199>.

BERTSIMAS, D.; TSITSIKLIS, J. N. Introduction to Linear Optimization. Belmont,MA: Athena Scientific, 1997. v. 6. (Athena scientific series in optimization and neuralcomputation, v. 6). ISBN 1886529191.

CORMEN, T. H. et al. Introduction to Algorithms. 3rd. ed. Cambridge, MA: The MITpress, 2009. ISBN 978-0-262-03384-8.

DIESTEL, R. Graph theory. 4th. ed. Berlin: Springer Publishing Company, Incorporated,2010. (Graduate texts in mathematics). ISBN 9783642142789.

DOLAN, E. D.; MORÉ, J. J. Benchmarking optimization software with performanceprofiles. Mathematical Programming, Springer, v. 91, n. 2, p. 201–213, Jan 2002. ISSN1436-4646. Disponível em: <https://doi.org/10.1007/s101070100263>.

EDMONDS, J.; JOHNSON, E. L. Matching, Euler tours and the Chinese postman.Mathematical Programming, Springer, v. 5, n. 1, p. 88–124, Dec 1973. ISSN 1436-4646.Disponível em: <https://doi.org/10.1007/BF01580113>.

FEO, T. A.; RESENDE, M. G. C. Greedy randomized adaptive search procedures.Journal of Global Optimization, Springer, v. 6, n. 2, p. 109–133, Mar 1995. ISSN1573-2916. Disponível em: <https://doi.org/10.1007/BF01096763>.

GAREY, M. R.; JOHNSON, D. S. Computers and Intractability: A Guide to the Theoryof NP-Completeness. New York, NY: W.H. Freeman & Co., 1979. ISBN 9780716710455.

HARARY, F. Graph theory. Reading, MA, 1969. (Addison-Wesley series in mathematics).

http://www.sciencedirect.com/science/article/pii/S0305054813002086

http://dl.acm.org/citation.cfm?id=166648.166660

http://www.sciencedirect.com/science/article/pii/S0021980070800199

https://doi.org/10.1007/s101070100263

https://doi.org/10.1007/BF01580113

https://doi.org/10.1007/BF01096763

73

KALCSICS, J. Districting Problems. In: LAPORTE, G.; NICKEL, S.; GAMA,F. Saldanha da (Ed.). Location Science. Cham: Springer International Publishing,2015. p. 595–622. ISBN 978-3-319-13111-5. Disponível em: <https://doi.org/10.1007/978-3-319-13111-5_23>.

KUHN, H. W. The hungarian method for the assignment problem. Naval ResearchLogistics Quarterly, Wiley Online Library, v. 2, n. 1-2, p. 83–97, 1955. Disponível em:<https://onlinelibrary.wiley.com/doi/abs/10.1002/nav.3800020109>.

MANBER, U. Introduction to Algorithms: a creative approach. Reading, MA:Addison-Wesley Longman Publishing Co., Inc., 1989. v. 4. ISBN 0-201-12037-2.

MAZIERO, L. P.; USBERTI, F. L.; CAVELLUCCI, C. O problema do ciclo dominante.In: SBPO XLVII Proceedings–Brazilian Symposium of Operations Research. [s.n.], 2015.Disponível em: <http://cdsid.org.br/sbpo2015/wp-content/uploads/2015/08/142930.pdf>.

MENDES, L. H. P.; USBERTI, F. L. Heurísticas para o Problema do Ciclo Dominantecom Coleta de Prêmios. 2017. Disponível em: <http://www.sbpo2017.iltc.br/pdf/169094.pdf>.

NEMHAUSER, G. L.; WOLSEY, L. A. Integer and Combinatorial Optimization.Wiley-Interscience, 1988.

REEVES, C. R. Evaluation of heuristic performance. In: REEVES, C. R. (Ed.).Modern Heuristic Techniques for Combinatorial Problems. New York, NY, USA:John Wiley & Sons, Inc., 1993. p. 304–315. ISBN 0-470-22079-1. Disponível em:<http://dl.acm.org/citation.cfm?id=166648.166660>.

SILBERHOLZ, J.; GOLDEN, B. Comparison of metaheuristics. In: GENDREAU,M.; POTVIN, J.-Y. (Ed.). Handbook of Metaheuristics. 2nd. ed. Springer PublishingCompany, Incorporated, 2010. p. 625–640. ISBN 978-1-4419-1663-1. Disponível em:<https://link.springer.com/content/pdf/10.1007/978-1-4419-1665-5.pdf>.

SZWARCFITER, J. L. Grafos e Algoritimos Computacionais. 2nd. ed. Rio de Janeiro,RJ: Campus, 1986. ISBN 8570013418.

WOLSEY, L. Integer Programming. New York, NY: John Wiley & Sons, 1998.(Wiley-Interscience Series in Discrete Mathematics and Optimization). ISBN9780471283669.

https://doi.org/10.1007/978-3-319-13111-5_23

https://doi.org/10.1007/978-3-319-13111-5_23

https://onlinelibrary.wiley.com/doi/abs/10.1002/nav.3800020109

http://cdsid.org.br/sbpo2015/wp-content/uploads/2015/08/142930.pdf

http://cdsid.org.br/sbpo2015/wp-content/uploads/2015/08/142930.pdf

http://www.sbpo2017.iltc.br/pdf/169094.pdf

http://www.sbpo2017.iltc.br/pdf/169094.pdf

http://dl.acm.org/citation.cfm?id=166648.166660

https://link.springer.com/content/pdf/10.1007/978-1-4419-1665-5.pdf

74

Apêndice A

Benchmark de Instâncias

Tabela A.1: Benchmark de Instâncias.

Instância T m B D |V ||E| =|U | =|U ′| − 1

|A| |A′|

grid-m5V25E24B05D05 grade 5 0,5 492 25 24 31 55grid-m5V25E24B05D10 grade 5 0,5 607 25 24 30 54grid-m5V25E24B10D05 grade 5 1,0 592 25 24 26 50grid-m5V25E24B10D10 grade 5 1,0 820 25 24 29 53grid-m5V25E32B05D05 grade 5 0,5 602 25 32 58 90grid-m5V25E32B05D10 grade 5 0,5 689 25 32 58 90grid-m5V25E32B10D05 grade 5 1,0 789 25 32 57 89grid-m5V25E32B10D10 grade 5 1,0 996 25 32 59 91grid-m5V25E40B05D05 grade 5 0,5 757 25 40 94 134grid-m5V25E40B05D10 grade 5 0,5 830 25 40 94 134grid-m5V25E40B10D05 grade 5 1,0 851 25 40 94 134grid-m5V25E40B10D10 grade 5 1,0 1073 25 40 94 134grid-m5V49E48B05D05 grade 5 0,5 910 49 48 66 114grid-m5V49E48B05D10 grade 5 0,5 1050 49 48 59 107grid-m5V49E48B10D05 grade 5 1,0 1127 49 48 58 106grid-m5V49E48B10D10 grade 5 1,0 1526 49 48 61 109grid-m5V49E66B05D05 grade 5 0,5 1171 49 66 128 194grid-m5V49E66B05D10 grade 5 0,5 1428 49 66 138 204grid-m5V49E66B10D05 grade 5 1,0 1522 49 66 130 196grid-m5V49E66B10D10 grade 5 1,0 1853 49 66 134 200grid-m5V49E84B05D05 grade 5 0,5 1525 49 84 214 298grid-m5V49E84B05D10 grade 5 0,5 1874 49 84 214 298

75

Tabela A.1: Benchmark de Instâncias (Continuação).


|A| |A′|

grid-m5V49E84B10D05 grade 5 1,0 1849 49 84 214 298grid-m5V49E84B10D10 grade 5 1,0 2490 49 84 214 298grid-m5V100E99B05D05 grade 5 0,5 1790 100 99 124 223grid-m5V100E99B05D10 grade 5 0,5 2152 100 99 137 236grid-m5V100E99B10D05 grade 5 1,0 1968 100 99 131 230grid-m5V100E99B10D10 grade 5 1,0 2969 100 99 129 228grid-m5V100E140B05D05 grade 5 0,5 2652 100 140 292 432grid-m5V100E140B05D10 grade 5 0,5 2952 100 140 291 431grid-m5V100E140B10D05 grade 5 1,0 2858 100 140 297 437grid-m5V100E140B10D10 grade 5 1,0 4270 100 140 289 429grid-m5V100E180B05D05 grade 5 0,5 3325 100 180 484 664grid-m5V100E180B05D10 grade 5 0,5 4058 100 180 484 664grid-m5V100E180B10D05 grade 5 1,0 3974 100 180 484 664grid-m5V100E180B10D10 grade 5 1,0 5273 100 180 484 664grid-m10V25E24B05D05 grade 10 0,5 219 25 24 28 52grid-m10V25E24B05D10 grade 10 0,5 257 25 24 30 54grid-m10V25E24B10D05 grade 10 1,0 283 25 24 28 52grid-m10V25E24B10D10 grade 10 1,0 415 25 24 30 54grid-m10V25E32B05D05 grade 10 0,5 315 25 32 56 88grid-m10V25E32B05D10 grade 10 0,5 373 25 32 62 94grid-m10V25E32B10D05 grade 10 1,0 351 25 32 57 89grid-m10V25E32B10D10 grade 10 1,0 498 25 32 57 89grid-m10V25E40B05D05 grade 10 0,5 371 25 40 94 134grid-m10V25E40B05D10 grade 10 0,5 456 25 40 94 134grid-m10V25E40B10D05 grade 10 1,0 432 25 40 94 134grid-m10V25E40B10D10 grade 10 1,0 596 25 40 94 134grid-m10V49E48B05D05 grade 10 0,5 446 49 48 59 107grid-m10V49E48B05D10 grade 10 0,5 534 49 48 58 106grid-m10V49E48B10D05 grade 10 1,0 479 49 48 63 111grid-m10V49E48B10D10 grade 10 1,0 796 49 48 63 111grid-m10V49E66B05D05 grade 10 0,5 644 49 66 131 197grid-m10V49E66B05D10 grade 10 0,5 738 49 66 132 198grid-m10V49E66B10D05 grade 10 1,0 847 49 66 131 197

76



|A| |A′|

grid-m10V49E66B10D10 grade 10 1,0 1047 49 66 132 198grid-m10V49E84B05D05 grade 10 0,5 755 49 84 214 298grid-m10V49E84B05D10 grade 10 0,5 940 49 84 214 298grid-m10V49E84B10D05 grade 10 1,0 915 49 84 214 298grid-m10V49E84B10D10 grade 10 1,0 1238 49 84 214 298grid-m10V100E99B05D05 grade 10 0,5 905 100 99 129 228grid-m10V100E99B05D10 grade 10 0,5 1077 100 99 126 225grid-m10V100E99B10D05 grade 10 1,0 1075 100 99 132 231grid-m10V100E99B10D10 grade 10 1,0 1466 100 99 126 225grid-m10V100E140B05D05 grade 10 0,5 1322 100 140 285 425grid-m10V100E140B05D10 grade 10 0,5 1480 100 140 304 444grid-m10V100E140B10D05 grade 10 1,0 1593 100 140 294 434grid-m10V100E140B10D10 grade 10 1,0 2183 100 140 289 429grid-m10V100E180B05D05 grade 10 0,5 1664 100 180 484 664grid-m10V100E180B05D10 grade 10 0,5 2023 100 180 484 664grid-m10V100E180B10D05 grade 10 1,0 1991 100 180 484 664grid-m10V100E180B10D10 grade 10 1,0 2605 100 180 484 664random-m5V25E24B05D05 aleatória 5 0,5 248 25 24 37 61random-m5V25E24B05D10 aleatória 5 0,5 285 25 24 39 63random-m5V25E24B10D05 aleatória 5 1,0 260 25 24 32 56random-m5V25E24B10D10 aleatória 5 1,0 397 25 24 34 58random-m5V25E32B05D05 aleatória 5 0,5 359 25 32 84 116random-m5V25E32B05D10 aleatória 5 0,5 448 25 32 67 99random-m5V25E32B10D05 aleatória 5 1,0 419 25 32 66 98random-m5V25E32B10D10 aleatória 5 1,0 558 25 32 87 119random-m5V25E40B05D05 aleatória 5 0,5 453 25 40 103 143random-m5V25E40B05D10 aleatória 5 0,5 656 25 40 120 160random-m5V25E40B10D05 aleatória 5 1,0 507 25 40 147 187random-m5V25E40B10D10 aleatória 5 1,0 698 25 40 115 155random-m5V49E48B05D05 aleatória 5 0,5 507 49 48 74 122random-m5V49E48B05D10 aleatória 5 0,5 712 49 48 76 124random-m5V49E48B10D05 aleatória 5 1,0 629 49 48 71 119random-m5V49E48B10D10 aleatória 5 1,0 830 49 48 82 130

77



|A| |A′|

random-m5V49E66B05D05 aleatória 5 0,5 710 49 66 176 242random-m5V49E66B05D10 aleatória 5 0,5 847 49 66 181 247random-m5V49E66B10D05 aleatória 5 1,0 864 49 66 182 248random-m5V49E66B10D10 aleatória 5 1,0 1236 49 66 200 266random-m5V49E84B05D05 aleatória 5 0,5 993 49 84 282 366random-m5V49E84B05D10 aleatória 5 0,5 1118 49 84 296 380random-m5V49E84B10D05 aleatória 5 1,0 1006 49 84 263 347random-m5V49E84B10D10 aleatória 5 1,0 1358 49 84 279 363random-m5V100E99B05D05 aleatória 5 0,5 1032 100 99 147 246random-m5V100E99B05D10 aleatória 5 0,5 1333 100 99 163 262random-m5V100E99B10D05 aleatória 5 1,0 1306 100 99 174 273random-m5V100E99B10D10 aleatória 5 1,0 1512 100 99 169 268random-m5V100E140B05D05 aleatória 5 0,5 1581 100 140 409 549random-m5V100E140B05D10 aleatória 5 0,5 1747 100 140 385 525random-m5V100E140B10D05 aleatória 5 1,0 1876 100 140 378 518random-m5V100E140B10D10 aleatória 5 1,0 2533 100 140 404 544random-m5V100E180B05D05 aleatória 5 0,5 1908 100 180 669 849random-m5V100E180B05D10 aleatória 5 0,5 2297 100 180 639 819random-m5V100E180B10D05 aleatória 5 1,0 2371 100 180 654 834random-m5V100E180B10D10 aleatória 5 1,0 3095 100 180 652 832random-m10V25E24B05D05 aleatória 10 0,5 147 25 24 35 59random-m10V25E24B05D10 aleatória 10 0,5 168 25 24 46 70random-m10V25E24B10D05 aleatória 10 1,0 158 25 24 48 72random-m10V25E24B10D10 aleatória 10 1,0 219 25 24 34 58random-m10V25E32B05D05 aleatória 10 0,5 124 25 32 82 114random-m10V25E32B05D10 aleatória 10 0,5 196 25 32 75 107random-m10V25E32B10D05 aleatória 10 1,0 211 25 32 83 115random-m10V25E32B10D10 aleatória 10 1,0 318 25 32 73 105random-m10V25E40B05D05 aleatória 10 0,5 246 25 40 126 166random-m10V25E40B05D10 aleatória 10 0,5 286 25 40 128 168random-m10V25E40B10D05 aleatória 10 1,0 256 25 40 119 159random-m10V25E40B10D10 aleatória 10 1,0 304 25 40 122 162random-m10V49E48B05D05 aleatória 10 0,5 284 49 48 78 126

78



|A| |A′|

random-m10V49E48B05D10 aleatória 10 0,5 315 49 48 90 138random-m10V49E48B10D05 aleatória 10 1,0 293 49 48 78 126random-m10V49E48B10D10 aleatória 10 1,0 424 49 48 69 117random-m10V49E66B05D05 aleatória 10 0,5 329 49 66 170 236random-m10V49E66B05D10 aleatória 10 0,5 367 49 66 163 229random-m10V49E66B10D05 aleatória 10 1,0 359 49 66 157 223random-m10V49E66B10D10 aleatória 10 1,0 559 49 66 177 243random-m10V49E84B05D05 aleatória 10 0,5 493 49 84 286 370random-m10V49E84B05D10 aleatória 10 0,5 514 49 84 298 382random-m10V49E84B10D05 aleatória 10 1,0 495 49 84 283 367random-m10V49E84B10D10 aleatória 10 1,0 755 49 84 304 388random-m10V100E99B05D05 aleatória 10 0,5 546 100 99 158 257random-m10V100E99B05D10 aleatória 10 0,5 647 100 99 166 265random-m10V100E99B10D05 aleatória 10 1,0 657 100 99 154 253random-m10V100E99B10D10 aleatória 10 1,0 786 100 99 157 256random-m10V100E140B05D05 aleatória 10 0,5 750 100 140 384 524random-m10V100E140B05D10 aleatória 10 0,5 879 100 140 373 513random-m10V100E140B10D05 aleatória 10 1,0 953 100 140 408 548random-m10V100E140B10D10 aleatória 10 1,0 1180 100 140 369 509random-m10V100E180B05D05 aleatória 10 0,5 984 100 180 686 866random-m10V100E180B05D10 aleatória 10 0,5 1142 100 180 647 827random-m10V100E180B10D05 aleatória 10 1,0 1161 100 180 659 839random-m10V100E180B10D10 aleatória 10 1,0 1472 100 180 659 839

79

Apêndice B

Resultados Obtidos

Tabela B.1: Limitantes Duais.

Instância Rel. Lin. B&B B&C Heur. Lagr.grid-m5V25E24B05D05 2230,69 1857 1857 10858grid-m5V25E24B05D10 2314,34 1765 1765 10854grid-m5V25E24B10D05 2423,95 1999 1999 10584grid-m5V25E24B10D10 2390,00 1916 1916 10844grid-m5V25E32B05D05 4276,10 3871 3871 21817grid-m5V25E32B05D10 4340,00 3834 3834 21882grid-m5V25E32B10D05 4113,00 3475 3475 21527grid-m5V25E32B10D10 4498,00 4122 4122 22168grid-m5V25E40B05D05 6303,61 5767 5674 37178grid-m5V25E40B05D10 6838,21 6344 6306 37723grid-m5V25E40B10D05 6472,00 5853 5821 37358grid-m5V25E40B10D10 6693,00 6267 6267 37579grid-m5V49E48B05D05 9339,21 7678 7692 44856grid-m5V49E48B05D10 9314,05 7456 7439 43494grid-m5V49E48B10D05 9694,00 7712 7720 43684grid-m5V49E48B10D10 9562,00 7288 7288 44128grid-m5V49E66B05D05 18072,20 16005 16180 95158grid-m5V49E66B05D10 18758,00 16488 16597 98492grid-m5V49E66B10D05 17681,00 16156 16116 95303grid-m5V49E66B10D10 17735,00 15925 15777 96413grid-m5V49E84B05D05 29641,90 28067 27703 171775grid-m5V49E84B05D10 29309,00 26972 26703 171443grid-m5V49E84B10D05 29932,00 28200 27903 172066grid-m5V49E84B10D10 29370,00 27061 26855 171504

80

Tabela B.1: Limitantes Duais (Continuação).Instance Rel. Lin. B&B B&C Heur. Lagr.

grid-m5V100E99B05D05 41386,00 31201 35991 188110grid-m5V100E99B05D10 41768,00 33470 37085 193640grid-m5V100E99B10D05 40840,00 31103 34959 190336grid-m5V100E99B10D10 41572,00 32065 33703 190276grid-m5V100E140B05D05 82991,00 73051 75889 441957grid-m5V100E140B05D10 81332,00 72075 72828 439738grid-m5V100E140B10D05 82666,00 74138 74077 444432grid-m5V100E140B10D10 82130,00 72989 75048 439416grid-m5V100E180B05D05 139230,00 130078 131096 810996grid-m5V100E180B05D10 138202,00 129607 131039 809968grid-m5V100E180B10D05 134442,00 125912 127060 806208grid-m5V100E180B10D10 136794,00 127393 129108 808560grid-m10V25E24B05D05 5069,15 4239 4126 19008grid-m10V25E24B05D10 5241,04 4500 4500 19428grid-m10V25E24B10D05 5233,28 4618 4618 19224grid-m10V25E24B10D10 5217,00 4684 4684 19412grid-m10V25E32B05D05 9409,37 8380 8386 36740grid-m10V25E32B05D10 9248,63 8509 8509 37374grid-m10V25E32B10D05 9433,03 8429 8429 36930grid-m10V25E32B10D10 9073,16 8436 8436 36569grid-m10V25E40B05D05 14204,30 13080 12910 60778grid-m10V25E40B05D10 14555,40 13494 13342 61226grid-m10V25E40B10D05 14616,10 13587 13336 61288grid-m10V25E40B10D10 14499,00 13589 13589 61190grid-m10V49E48B05D05 21077,60 17946 19305 78019grid-m10V49E48B05D10 20667,70 17356 18972 77441grid-m10V49E48B10D05 21121,40 17394 18906 78838grid-m10V49E48B10D10 21390,00 17209 19294 79140grid-m10V49E66B05D05 39267,00 34827 35907 160336grid-m10V49E66B05D10 40155,20 36236 36672 161488grid-m10V49E66B10D05 39159,10 35244 35886 160266grid-m10V49E66B10D10 40146,00 36430 36379 161531grid-m10V49E84B05D05 64318,80 59424 59938 276552grid-m10V49E84B05D10 64575,30 59318 59864 276831grid-m10V49E84B10D05 64366,80 59040 60668 276627

81


grid-m10V49E84B10D10 64289,00 59490 59548 276568grid-m10V100E99B05D05 89196,90 70009 84875 335392grid-m10V100E99B05D10 89790,70 71060 79226 334819grid-m10V100E99B10D05 88567,00 70881 83146 335973grid-m10V100E99B10D10 87856,00 68241 75357 332892grid-m10V100E140B05D05 177313,00 156188 162034 727634grid-m10V100E140B05D10 179053,00 155534 161894 740044grid-m10V100E140B10D05 179242,00 156982 163592 734633grid-m10V100E140B10D10 177178,00 157064 162584 729769grid-m10V100E180B05D05 292361,00 266147 271771 1290000grid-m10V100E180B05D10 295944,00 271548 276063 1290000grid-m10V100E180B10D05 295657,00 268882 273667 1290000grid-m10V100E180B10D10 296745,00 268528 274885 1290000random-m5V25E24B05D05 2351,06 1908 1908 11571random-m5V25E24B05D10 2371,00 2006 2006 11785random-m5V25E24B10D05 2416,00 1993 1993 11158random-m5V25E24B10D10 2323,00 2035 2035 11257random-m5V25E32B05D05 4302,00 3737 3737 25172random-m5V25E32B05D10 3972,56 3445 3445 22666random-m5V25E32B10D05 4051,32 3650 3650 22615random-m5V25E32B10D10 4313,00 3943 3943 25567random-m5V25E40B05D05 7065,00 6497 6270 39391random-m5V25E40B05D10 6741,58 6373 6234 41782random-m5V25E40B10D05 6626,00 6199 6120 45992random-m5V25E40B10D10 6703,00 6357 6357 40949random-m5V49E48B05D05 9794,59 7925 8104 46846random-m5V49E48B05D10 9452,15 7226 7741 46897random-m5V49E48B10D05 9239,31 7632 7841 45725random-m5V49E48B10D10 9869,00 7925 7820 48467random-m5V49E66B05D05 18604,10 17227 16921 108368random-m5V49E66B05D10 18129,50 17036 16739 109214random-m5V49E66B10D05 18679,00 17482 16937 110029random-m5V49E66B10D10 18131,00 16984 16723 114233random-m5V49E84B05D05 29922,10 28964 28395 194903random-m5V49E84B05D10 29220,00 27854 27411 198906

82


random-m5V49E84B10D05 30061,00 28691 28344 188659random-m5V49E84B10D10 28079,00 26517 25984 192053random-m5V100E99B05D05 41198,00 32196 33956 197023random-m5V100E99B05D10 40032,00 31509 33448 202200random-m5V100E99B10D05 41333,00 31645 35798 207857random-m5V100E99B10D10 41141,00 33523 36370 205685random-m5V100E140B05D05 83563,40 76930 77095 508044random-m5V100E140B05D10 80103,00 74012 73434 491149random-m5V100E140B10D05 80449,00 75013 74228 487575random-m5V100E140B10D10 84342,00 77879 78187 506028random-m5V100E180B05D05 134795,00 130396 130036 939761random-m5V100E180B05D10 137121,00 132223 131332 920487random-m5V100E180B10D05 134093,00 128795 127404 928259random-m5V100E180B10D10 133849,00 128082 127552 926575random-m10V25E24B05D05 5254,58 4511 4511 19890random-m10V25E24B05D10 5335,56 4902 4902 21057random-m10V25E24B10D05 5330,45 4789 4789 21239random-m10V25E24B10D10 5146,00 4771 4771 19725random-m10V25E32B05D05 9071,52 8412 8222 39747random-m10V25E32B05D10 9287,48 8420 8307 39068random-m10V25E32B10D05 9232,61 8491 8401 40058random-m10V25E32B10D10 9283,00 8502 8502 38830random-m10V25E40B05D05 14595,60 13682 13477 66377random-m10V25E40B05D10 14733,30 14117 13920 66854random-m10V25E40B10D05 14535,80 13635 13605 65208random-m10V25E40B10D10 14627,60 13586 13458 65795random-m10V49E48B05D05 20836,10 17435 18662 81470random-m10V49E48B05D10 20960,70 18345 19006 83896random-m10V49E48B10D05 21347,90 18235 19215 81974random-m10V49E48B10D10 21060,00 17460 18716 79967random-m10V49E66B05D05 39544,20 35818 36309 170921random-m10V49E66B05D10 39406,40 36514 36599 168946random-m10V49E66B10D05 39194,70 35703 36051 167179random-m10V49E66B10D10 39553,00 36429 36519 172818random-m10V49E84B05D05 64255,50 60744 60375 300671

83


random-m10V49E84B05D10 64329,00 60028 59911 304832random-m10V49E84B10D05 63766,60 59886 59012 299220random-m10V49E84B10D10 63580,00 59599 59000 306099random-m10V100E99B05D05 87578,20 71783 78305 345262random-m10V100E99B05D10 88458,00 69654 82674 349324random-m10V100E99B10D05 88696,80 69608 83487 344809random-m10V100E99B10D10 89127,00 71198 83795 346439random-m10V100E140B05D05 178541,00 161384 165548 784296random-m10V100E140B05D10 177864,00 161527 164799 777495random-m10V100E140B10D05 175966,00 158899 166195 795169random-m10V100E140B10D10 176565,00 159357 166742 773956random-m10V100E180B05D05 292912,00 274866 274976 1430000random-m10V100E180B05D10 291333,00 273924 273314 1400000random-m10V100E180B10D05 293658,00 276934 276103 1410000random-m10V100E180B10D10 293257,00 276641 277573 1410000

Tabela B.2: Limitantes Primais.

Instância B&B B&C GRASP Heur. Lagr.grid-m5V25E24B05D05 1857 1857 - -grid-m5V25E24B05D10 1765 1765 1733 1524grid-m5V25E24B10D05 1999 1999 1804 -grid-m5V25E24B10D10 1916 1916 1883 -grid-m5V25E32B05D05 3871 3871 3693 -grid-m5V25E32B05D10 3834 3834 3658 -grid-m5V25E32B10D05 3475 3475 3250 2954grid-m5V25E32B10D10 4122 4122 3939 3494grid-m5V25E40B05D05 5445 5612 5380 4895grid-m5V25E40B05D10 6298 6298 6040 5239grid-m5V25E40B10D05 5821 5821 5464 4793grid-m5V25E40B10D10 6267 6267 5954 -grid-m5V49E48B05D05 6221 - 6946 -grid-m5V49E48B05D10 7240 7240 6840 -grid-m5V49E48B10D05 - 7302 7135 -grid-m5V49E48B10D10 7288 7288 7028 -grid-m5V49E66B05D05 14227 - 13946 -

84

Tabela B.2: Limitantes Primais (Continuação).Instância B&B B&C GRASP Heur. Lagr.

grid-m5V49E66B05D10 14587 - 14423 13900grid-m5V49E66B10D05 - - 14921 -grid-m5V49E66B10D10 - 13755 13532 10577grid-m5V49E84B05D05 - - 25488 -grid-m5V49E84B05D10 - 23528 24132 20926grid-m5V49E84B10D05 - 27487 25345 -grid-m5V49E84B10D10 - 19947 24020 21431grid-m5V100E99B05D05 - - 26958 -grid-m5V100E99B05D10 28914 - 30958 -grid-m5V100E99B10D05 - - 27619 -grid-m5V100E99B10D10 - - 28582 -grid-m5V100E140B05D05 - - 61094 -grid-m5V100E140B05D10 - 55883 59813 56932grid-m5V100E140B10D05 - - 63294 -grid-m5V100E140B10D10 - - 61943 50125grid-m5V100E180B05D05 - - 111812 -grid-m5V100E180B05D10 - - 112933 -grid-m5V100E180B10D05 107677 - 104848 -grid-m5V100E180B10D10 - 100870 106120 -grid-m10V25E24B05D05 - - - -grid-m10V25E24B05D10 4500 4500 4500 -grid-m10V25E24B10D05 4618 4618 4579 -grid-m10V25E24B10D10 4684 4684 4289 4097grid-m10V25E32B05D05 8260 8260 7765 -grid-m10V25E32B05D10 8509 8509 8284 -grid-m10V25E32B10D05 8429 8429 8191 6016grid-m10V25E32B10D10 8436 8436 8398 7044grid-m10V25E40B05D05 - 12390 12326 -grid-m10V25E40B05D10 13342 13342 13069 -grid-m10V25E40B10D05 13332 13336 12918 -grid-m10V25E40B10D10 13589 13589 13158 10948grid-m10V49E48B05D05 - - 16162 -grid-m10V49E48B05D10 - - 16447 -grid-m10V49E48B10D05 - 16524 16003 -grid-m10V49E48B10D10 16904 16759 16572 -

85


grid-m10V49E66B05D05 28015 - 32051 -grid-m10V49E66B05D10 - 30164 33328 -grid-m10V49E66B10D05 - 28859 32309 -grid-m10V49E66B10D10 - 34997 33081 -grid-m10V49E84B05D05 - - 53208 51089grid-m10V49E84B05D10 50906 - 54351 -grid-m10V49E84B10D05 - - 53453 -grid-m10V49E84B10D10 - 48506 55168 47265grid-m10V100E99B05D05 - - 62081 -grid-m10V100E99B05D10 - - 63997 -grid-m10V100E99B10D05 - - 64753 -grid-m10V100E99B10D10 - - 61998 -grid-m10V100E140B05D05 - - 133106 -grid-m10V100E140B05D10 - - 131017 -grid-m10V100E140B10D05 - - 127485 -grid-m10V100E140B10D10 - - 133224 -grid-m10V100E180B05D05 - - 226602 -grid-m10V100E180B05D10 - 207332 231025 -grid-m10V100E180B10D05 - - 226210 -grid-m10V100E180B10D10 - - 226391 206521random-m5V25E24B05D05 1908 1908 1895 -random-m5V25E24B05D10 2006 2006 1853 -random-m5V25E24B10D05 1993 1993 - -random-m5V25E24B10D10 2035 2035 1972 1881random-m5V25E32B05D05 3737 3737 3649 3291random-m5V25E32B05D10 3445 3445 3280 -random-m5V25E32B10D05 3650 3650 3223 -random-m5V25E32B10D10 3943 3943 3834 3340random-m5V25E40B05D05 6270 6270 6080 -random-m5V25E40B05D10 6234 6234 6174 5465random-m5V25E40B10D05 6120 6120 5932 -random-m5V25E40B10D10 6357 6357 6167 5114random-m5V49E48B05D05 7688 7386 7438 -random-m5V49E48B05D10 6874 6851 6798 -random-m5V49E48B10D05 6599 6650 - -

86


random-m5V49E48B10D10 7787 7787 7508 -random-m5V49E66B05D05 16507 16524 15967 14732random-m5V49E66B05D10 - 16160 15843 -random-m5V49E66B10D05 - 16751 15024 -random-m5V49E66B10D10 16723 16723 15498 -random-m5V49E84B05D05 - 28208 27432 -random-m5V49E84B05D10 25360 26954 26124 22036random-m5V49E84B10D05 27394 27600 26184 -random-m5V49E84B10D10 - 24313 23879 22049random-m5V100E99B05D05 - - 28444 -random-m5V100E99B05D10 - 23431 27197 -random-m5V100E99B10D05 - - 27865 -random-m5V100E99B10D10 - - 30683 -random-m5V100E140B05D05 67044 - 66977 -random-m5V100E140B05D10 66307 61740 67020 63162random-m5V100E140B10D05 - - 62804 -random-m5V100E140B10D10 69406 - 68583 -random-m5V100E180B05D05 - 108530 120286 108617random-m5V100E180B05D10 123877 - 122510 -random-m5V100E180B10D05 - - 114330 -random-m5V100E180B10D10 122349 - 116840 -random-m10V25E24B05D05 4511 4511 4483 -random-m10V25E24B05D10 4902 4902 4845 -random-m10V25E24B10D05 4789 4789 4734 -random-m10V25E24B10D10 4771 4771 4514 -random-m10V25E32B05D05 8222 8222 8120 6826random-m10V25E32B05D10 8307 8307 8273 -random-m10V25E32B10D05 8399 8401 8046 -random-m10V25E32B10D10 8502 8502 8411 -random-m10V25E40B05D05 - 13277 13139 -random-m10V25E40B05D10 13904 13920 13899 -random-m10V25E40B10D05 13605 13605 13173 -random-m10V25E40B10D10 13368 13458 13148 11453random-m10V49E48B05D05 - - 16355 -random-m10V49E48B05D10 - - 17073 -

87


random-m10V49E48B10D05 - 16927 17035 -random-m10V49E48B10D10 17237 16990 16954 -random-m10V49E66B05D05 27238 - 32110 -random-m10V49E66B05D10 31860 - 33761 -random-m10V49E66B10D05 33781 - 32219 -random-m10V49E66B10D10 - 34976 33776 -random-m10V49E84B05D05 - 48080 55751 -random-m10V49E84B05D10 51230 48349 55532 47872random-m10V49E84B10D05 - - 54673 45232random-m10V49E84B10D10 52870 57656 55716 48369random-m10V100E99B05D05 - - 61570 -random-m10V100E99B05D10 - - 63077 -random-m10V100E99B10D05 - - 61753 -random-m10V100E99B10D10 - - 64619 -random-m10V100E140B05D05 - - 139271 -random-m10V100E140B05D10 - - 143937 -random-m10V100E140B10D05 - - 138426 -random-m10V100E140B10D10 - - 137610 -random-m10V100E180B05D05 - - 245788 222528random-m10V100E180B05D10 - 214886 246100 207068random-m10V100E180B10D05 - - 242123 -random-m10V100E180B10D10 246332 226240 241862 -

Tabela B.3: GAPs de Otimalidade.

Instância B&B B&C GRASP Heur. Lagr.grid-m5V25E24B05D05 0,00% 0,00% - -grid-m5V25E24B05D10 0,00% 0,00% 1,85% 15,81%grid-m5V25E24B10D05 0,00% 0,00% 10,81% -grid-m5V25E24B10D10 0,00% 0,00% 1,75% -grid-m5V25E32B05D05 0,00% 0,00% 4,82% -grid-m5V25E32B05D10 0,00% 0,00% 4,81% -grid-m5V25E32B10D05 0,00% 0,00% 6,92% 17,64%grid-m5V25E32B10D10 0,00% 0,00% 4,65% 17,97%grid-m5V25E40B05D05 4,21% 1,10% 5,46% 15,91%grid-m5V25E40B05D10 0,13% 0,13% 4,40% 20,37%

88

Tabela B.3: GAPs de Otimalidade (Continuação).Instância B&B B&C GRASP Heur. Lagr.

grid-m5V25E40B10D05 0,00% 0,00% 6,53% 21,45%grid-m5V25E40B10D10 0,00% 0,00% 5,26% -grid-m5V49E48B05D05 23,42% - 10,54% -grid-m5V49E48B05D10 2,75% 2,75% 8,76% -grid-m5V49E48B10D05 - 5,61% 8,09% -grid-m5V49E48B10D10 0,00% 0,00% 3,70% -grid-m5V49E66B05D05 12,50% - 14,76% -grid-m5V49E66B05D10 13,03% - 14,32% 18,62%grid-m5V49E66B10D05 - - 8,01% -grid-m5V49E66B10D10 - 14,70% 16,59% 49,16%grid-m5V49E84B05D05 - - 8,69% -grid-m5V49E84B05D10 - 13,49% 10,65% 27,61%grid-m5V49E84B10D05 - 1,51% 10,09% -grid-m5V49E84B10D10 - 34,63% 11,80% 25,31%grid-m5V100E99B05D05 - - 15,74% -grid-m5V100E99B05D10 15,76% - 8,11% -grid-m5V100E99B10D05 - - 12,61% -grid-m5V100E99B10D10 - - 12,19% -grid-m5V100E140B05D05 - - 19,57% -grid-m5V100E140B05D10 - 28,97% 20,50% 26,60%grid-m5V100E140B10D05 - - 17,04% -grid-m5V100E140B10D10 - - 17,83% 45,61%grid-m5V100E180B05D05 - - 16,34% -grid-m5V100E180B05D10 - - 14,76% -grid-m5V100E180B10D05 16,93% - 20,09% -grid-m5V100E180B10D10 - 26,29% 20,05% -grid-m10V25E24B05D05 - - - -grid-m10V25E24B05D10 0,00% 0,00% 0,00% -grid-m10V25E24B10D05 0,00% 0,00% 0,85% -grid-m10V25E24B10D10 0,00% 0,00% 9,21% 14,33%grid-m10V25E32B05D05 1,45% 1,45% 7,92% -grid-m10V25E32B05D10 0,00% 0,00% 2,72% -grid-m10V25E32B10D05 0,00% 0,00% 2,91% 40,11%grid-m10V25E32B10D10 0,00% 0,00% 0,45% 19,76%grid-m10V25E40B05D05 - 4,20% 4,74% -

89


grid-m10V25E40B05D10 0,00% 0,00% 2,09% -grid-m10V25E40B10D05 0,03% 0,00% 3,24% -grid-m10V25E40B10D10 0,00% 0,00% 3,28% 24,12%grid-m10V49E48B05D05 - - 11,04% -grid-m10V49E48B05D10 - - 5,53% -grid-m10V49E48B10D05 - 5,27% 8,69% -grid-m10V49E48B10D10 1,80% 2,69% 3,84% -grid-m10V49E66B05D05 24,32% - 8,66% -grid-m10V49E66B05D10 - 20,13% 8,73% -grid-m10V49E66B10D05 - 22,12% 9,08% -grid-m10V49E66B10D10 - 3,95% 9,97% -grid-m10V49E84B05D05 - - 11,68% 16,31%grid-m10V49E84B05D10 16,52% - 9,14% -grid-m10V49E84B10D05 - - 10,45% -grid-m10V49E84B10D10 - 22,64% 7,83% 25,86%grid-m10V100E99B05D05 - - 12,77% -grid-m10V100E99B05D10 - - 11,04% -grid-m10V100E99B10D05 - - 9,46% -grid-m10V100E99B10D10 - - 10,07% -grid-m10V100E140B05D05 - - 17,34% -grid-m10V100E140B05D10 - - 18,71% -grid-m10V100E140B10D05 - - 23,14% -grid-m10V100E140B10D10 - - 17,89% -grid-m10V100E180B05D05 - - 17,45% -grid-m10V100E180B05D10 - 30,97% 17,54% -grid-m10V100E180B10D05 - - 18,86% -grid-m10V100E180B10D10 - - 18,61% 30,02%random-m5V25E24B05D05 0,00% 0,00% 0,69% -random-m5V25E24B05D10 0,00% 0,00% 8,26% -random-m5V25E24B10D05 0,00% 0,00% - -random-m5V25E24B10D10 0,00% 0,00% 3,19% 8,19%random-m5V25E32B05D05 0,00% 0,00% 2,41% 13,55%random-m5V25E32B05D10 0,00% 0,00% 5,03% -random-m5V25E32B10D05 0,00% 0,00% 13,25% -random-m5V25E32B10D10 0,00% 0,00% 2,84% 18,05%

90


random-m5V25E40B05D05 0,00% 0,00% 3,13% -random-m5V25E40B05D10 0,00% 0,00% 0,97% 14,07%random-m5V25E40B10D05 0,00% 0,00% 3,17% -random-m5V25E40B10D10 0,00% 0,00% 3,08% 24,31%random-m5V49E48B05D05 3,08% 7,30% 6,55% -random-m5V49E48B05D10 5,12% 5,47% 6,30% -random-m5V49E48B10D05 15,65% 14,77% - -random-m5V49E48B10D10 0,42% 0,42% 4,16% -random-m5V49E66B05D05 2,51% 2,40% 5,97% 14,86%random-m5V49E66B05D10 - 3,58% 5,66% -random-m5V49E66B10D05 - 1,11% 12,73% -random-m5V49E66B10D10 0,00% 0,00% 7,90% -random-m5V49E84B05D05 - 0,66% 3,51% -random-m5V49E84B05D10 8,09% 1,70% 4,93% 24,39%random-m5V49E84B10D05 3,47% 2,70% 8,25% -random-m5V49E84B10D10 - 6,87% 8,82% 17,85%random-m5V100E99B05D05 - - 13,19% -random-m5V100E99B05D10 - 34,48% 15,85% -random-m5V100E99B10D05 - - 13,57% -random-m5V100E99B10D10 - - 9,26% -random-m5V100E140B05D05 14,75% - 14,86% -random-m5V100E140B05D10 10,75% 18,94% 9,57% 16,26%random-m5V100E140B10D05 - - 18,19% -random-m5V100E140B10D10 12,21% - 13,55% -random-m5V100E180B05D05 - 19,82% 8,11% 19,72%random-m5V100E180B05D10 6,02% - 7,20% -random-m5V100E180B10D05 - - 11,44% -random-m5V100E180B10D10 4,25% - 9,17% -random-m10V25E24B05D05 0,00% 0,00% 0,62% -random-m10V25E24B05D10 0,00% 0,00% 1,18% -random-m10V25E24B10D05 0,00% 0,00% 1,16% -random-m10V25E24B10D10 0,00% 0,00% 5,69% -random-m10V25E32B05D05 0,00% 0,00% 1,26% 20,45%random-m10V25E32B05D10 0,00% 0,00% 0,41% -random-m10V25E32B10D05 0,02% 0,00% 4,41% -

91


random-m10V25E32B10D10 0,00% 0,00% 1,08% -random-m10V25E40B05D05 - 1,51% 2,57% -random-m10V25E40B05D10 0,12% 0,00% 0,15% -random-m10V25E40B10D05 0,00% 0,00% 3,28% -random-m10V25E40B10D10 0,67% 0,00% 2,36% 17,51%random-m10V49E48B05D05 - - 6,60% -random-m10V49E48B05D10 - - 7,45% -random-m10V49E48B10D05 - 7,73% 7,04% -random-m10V49E48B10D10 1,29% 2,77% 2,98% -random-m10V49E66B05D05 31,50% - 11,55% -random-m10V49E66B05D10 14,61% - 8,15% -random-m10V49E66B10D05 5,69% - 10,81% -random-m10V49E66B10D10 - 4,15% 7,85% -random-m10V49E84B05D05 - 25,57% 8,29% -random-m10V49E84B05D10 16,95% 23,91% 7,89% 25,15%random-m10V49E84B10D05 - - 7,94% 30,47%random-m10V49E84B10D10 11,59% 2,33% 5,89% 21,98%random-m10V100E99B05D05 - - 16,59% -random-m10V100E99B05D10 - - 10,43% -random-m10V100E99B10D05 - - 12,72% -random-m10V100E99B10D10 - - 10,18% -random-m10V100E140B05D05 - - 15,88% -random-m10V100E140B05D10 - - 12,22% -random-m10V100E140B10D05 - - 14,79% -random-m10V100E140B10D10 - - 15,80% -random-m10V100E180B05D05 - - 11,83% 23,52%random-m10V100E180B05D10 - 27,19% 11,06% 31,99%random-m10V100E180B10D05 - - 14,03% -random-m10V100E180B10D10 12,30% 22,28% 14,38% -

Documents

LuisHenriquePauletiMendes …repositorio.unicamp.br/.../Mendes_LuisHenriquePauleti_M.pdf · 2020. 2. 17. · Ficha catalográfica Universidade Estadual de Campinas Biblioteca do Instituto