Modularity Density Maximization is a graph clustering problem which avoids the resolution limit degeneracy of the Modularity Maximization problem. This thesis aims at solving larger instances than current Modularity Density heuristics do, and show how close the obtained solutions are to the expected clustering. Three main contributions arise from this objective. The first one is about the theoretical contributions about properties of Modularity Density based prioritizers. The second one is the development of eight Modularity Density Maximization heuristics. Our heuristics are compared with optimal results from the literature, and with GAOD, iMeme-Net, HAIN, BMD- heuristics. Our results are also compared with CNM and Louvain which are heuristics for Modularity Maximization that solve instances with thousands of nodes. The tests were carried out by using graphs from the “Stanford Large Network Dataset Collection”. The experiments have shown that our eight heuristics found solutions for graphs with hundreds of thousands of nodes. Our results have also shown that five of our heuristics surpassed the current state-of-the-art Modularity Density Maximization heuristic solvers for large graphs. A third contribution is the proposal of six column generation methods. These methods use exact and heuristic auxiliary solvers and an initial variable generator. Comparisons among our proposed column generations and state-of-the-art algorithms were also carried out. The results showed that: (i) two of our methods surpassed the state-of-the-art algorithms in terms of time, and (ii) our methods proved the optimal value for larger instances than current approaches can tackle. Our results suggest clear improvements to the state-of-the-art results for the Modularity Density Maximization problem.

A presente pesquisa considera o problema de programação de uma frota de embarcações de lançamentos de dutos, conhecidas como Pipe Layer Support Vessel (PLSVs), as quais fazem parte da frota de apoio marítimo de uma operação offshore. As embarcações do tipo PLSVs são responsáveis pelas tarefas de lançamento de dutos submarinos, que escoam a produção dos poços de petróleo, e pela interligação destes dutos à infraestrutura submarina. A programação da frota deve atender uma demanda de serviço conhecida, em um horizonte de médio prazo, respeitando restrições operacionais, visando minimizar o atraso ponderado total das tarefas ou evitar que existam atrasos. Foi desenvolvido um método para estimar o valor da solução ótima do problema, baseado na técnica de relaxação Lagrangiana, e um conjunto de heurísticas para gerar soluções viáveis para o problema. / This research considers the problem of scheduling a fleet of specialized vessels used for launching pipes and connecting them to the subsea infrastructure, in an offshore oil production environment. The Pipe Layer Support Vessels (PLSV) must be scheduled such that the demand is fully attended within the planning horizon, observing other operational constraints, with the purpose of minimizing the total weighted tardiness. The solution method is based on constructive and local search heuristics. Bounds on the optimal solution were derived by a Lagrangean relaxation algorithm.

O Problema de Escalonamento de Médicos (Physician Scheduling Problem) consiste em atribuir tarefas a médicos num horizonte de planejamento respeitando regras laborais, contratuais e de preferências pessoais de modo a satisfazer a demanda de serviços de um hospital. O problema lida majoritariamente com o objetivo de maximizar o atendimento dos requisitos de preferência pessoal, respeitando as restrições laborais e organizacionais. Sobre esta classe de problemas, vários métodos de resolução e suas variantes têm sido propostos na literatura. Ademais, mais características têm sido agregadas ao problema, tornando-o mais complexo e deste modo fazendo-se mais necessária a aplicação de métodos mais elaborados para a sua resolução. Neste trabalho são estudados, reformulados e propostos métodos de resolução baseados em programação matemática para tratar o problema de escalonamento acíclico de médicos em departamento de emergência de hospitais. O primeiro modelo tem como objetivo a minimização da soma ponderada dos desvios das restrições de distribuição. O segundo modelo tem como objetivo, a minimização do máximo dos desvios obtidos nas restrições de distribuição, a fim de se obter escalas mais equilibradas entre os médicos. Foram também propostas heurísticas baseadas na formulação matemática cujos resultados não foram competitivos com as dos modelos. Os modelos foram testados sobre um conjunto de instâncias fictícias resultantes de uma mescla entre instâncias benchmark e características do problema. Os resultados computacionais demonstram que formulação ponderada obteve solução ótima para grande parte das instâncias, embora os limitantes inferiores tenham sido majoritariamente fracos. Em relação ao segundo modelo, soluções ótimas não foram obtidas e os limitantes inferiores foram igualmente fracos. Relativamente a qualidade das escalas, o segundo modelo teve melhor comportamento comparando ao modelo de somas ponderadas. Dada a qualidade das soluções, nota-se a viabilidade da solução baseada em técnicas de otimização em detrimento da manual, pois esta ainda é mais suscetível de erros e acarreta um alto tempo para obtenção de solução. / The Physician Scheduling Problem consists in task assignment to physicians in a planning horizon considering a set of organizational rules, work regulations and individual preferences in order to satisfy an hospital wards work demand. The aim is to find a schedule which maximizes the satisfaction of individual preferences requirements while meeting work regulations and organizational rules. A plethora of solution methods and its variants have been proposed in the literature to solve this class of problem. Moreover, more features have been aggregated to the problem turning it into a more complex and thus estimulating the application of more elaborated methods to its decision. In this work we study, reshape and propose decision methods based in mathematical programming to handle non-ciclic physician scheduling problem in emergency wards. The first formulation targets the minimization of the weighted sum of distribution constraints deviations. The second formulation targets the minimization of the maximum deviations obtained at the distribution constraints aiming more balanced schedules between the physicians. Mathematical formulation heuristics were also proposed and the findings were not satisfactory as they were not competitive with the model. Experiments with our models were performed over a set of dummy instances, as result a of a mixture of benchmark instances and the considered problems features. From our experiments we have found that optimal solutions were obtained through the weighted sum model, despite the poor lower bounds. On the other hand, for the second model, no optimal solution was found and poor lower bounds were similarly obtained. Regarding to the schedules quality, the min-max model had a better performance comparing to the weighted sum model. Given the solutions quality we can assume that optimization based techniques are sustainable comparing to manual, because the latter is prone to errors and omissions and also critical in terms of solutions achievement time.

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2017-02-21T16:58:53Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Dissertação_SilviaVersaoFinal.pdf: 3562807 bytes, checksum: d273ad6c061161f899cab3d232a82a79 (MD5) / Made available in DSpace on 2017-02-21T16:58:54Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Dissertação_SilviaVersaoFinal.pdf: 3562807 bytes, checksum: d273ad6c061161f899cab3d232a82a79 (MD5) Previous issue date: 2016-08-01 / FACEPE / Contexto: A fase de especificação de requisitos é fundamental no processo de desenvolvimento de software. O uso de cenários é bastante popular para especificar requisitos, por serem descritos em linguagem natural. No entanto, a linguagem natural dá margem a requisitos ambíguos, incompletos e inconsistentes, o que vai de encontro com os objetivos da fase de especificação de requisitos. Nesse sentido, uma técnica baseada em Cenário & LEL (Language Extended Lexicon), chamada de C&L, pode ser a solução adequada, pois LEL é um glossário que define um conjunto de palavras que pertencem a um domínio e que devem ser usadas para descrever os cenários. Assim, C&L é considerada uma técnica de cenários baseada em linguagem natural controlada que ajuda a minimizar os problemas previamente mencionados, além de poder ser utilizada para criar casos de teste de forma mais sistemática. Objetivo: Neste trabalho, são propostas duas abordagens: a primeira abordagem usa regras de mapeamento para derivar modelos statechart a partir de C&L visando verificar a completude e consistência desses cenários e a segunda usa heurísticas para obter sistematicamente casos de teste a partir de modelos statechart. Método: A pesquisa apresentada nessa dissertação seguiu a abordagem de Engenharia para definir as regras de mapeamento e as heurísticas que, por sua vez, foram avaliadas empiricamente. Resultados: As regras de mapeamento apoiam a derivação de statechart a partir de C&L. As heurísticas apoiam a derivação de casos de teste a partir dos modelos statechart. Foi realizado um experimento para comparar o número de erros de incompletude e inconsistência detectados pelos grupos experimental e controle e o tempo gasto pelos grupos para detectar esses erros. Também foi verificado se os statecharts gerados através da aplicação das regras de mapeamento possuem grau de corretude e semelhança. Foi realizada uma avaliação qualitativa das heurísticas utilizadas para derivar os casos de teste, com o intuito de saber se as heurísticas foram utilizadas corretamente, se estão claras e são fáceis de usar. Conclusões: Os resultados do experimento mostram que o número de erros de incompletude detectados pelo grupo experimental foi superior ao número obtido pelo grupo controle e em relação aos erros de inconsistência não houve diferença entre quantidade de erros detectados pelos dois grupos. Além disso, a média do tempo gasto para identificar erros de incompletude e inconsistência pelo grupo experimental foi ligeiramente superior a média do tempo gasto pelo grupo controle. Em relação ao grau de corretude, dentre os modelos gerados pelo grupo experimental, existe um que apresenta o maior grau de corretude com 85,7%. No entanto, o grau de semelhança entre os modelos é considerado de “baixa semelhança”. O resultado da avaliação qualitativa mostrou que os participantes concordaram que as regras de mapeamento e as heurísticas são compreensíveis e fáceis de utilizar. Também foi observado que as heurísticas foram usadas de maneira correta na derivação dos casos de teste. / Context: The requirements specification phase is fundamental in the software development process. The use of scenarios is quite popular to specify requirements because they are described in natural language. However, natural language gives rise to ambiguous, incomplete and inconsistent requirements, jeopardizes the objectives of the requirements specification phase. In this context, a technique based on Scenarios and LEL (Language Extended Lexicon), called C&L, may be an appropriate solution because LEL is a glossary that defines a set of words that belong to a domain and should be used to describe the scenarios. Thus, C&L is a scenario technique based on controlled natural language that helps to minimize the problems previously mentioned, and can be used to create test cases in a more systematic way. Objective: In this study, two approaches are proposed: the first approach uses mapping rules to derive statechart models from C & L in order to verify the completeness and consistency of these scenarios and the second uses heuristics to systematically derive test cases from statechart models. Method: The research presented in this work follows the engineering approach to define the mapping rules and heuristics that, in turn, were empirically evaluated. Results: Mapping rules support the derivation of statechart from C & L. Heuristics support the derivation of test cases from statechart models. An experiment was conducted to compare the number of incompleteness and inconsistency errors detected by the experimental and control the groups and the time spent by groups to detect these errors. Also it was verified whether the statecharts generated by the application of the mapping rules have degree of correctness and likeness. A qualitative evaluation of the heuristics used to derive the test cases was made, in order to know whether the heuristics were correctly used and if they are clear and easy to use. Conclusions: The results of the experiment show that the number of incompleteness errors detected by the experimental group was higher than the number obtained by the control group, and in relation to inconsistency errors, there was no difference among the number of errors detected by the two groups. Furthermore, the average time spent to identify incompleteness and inconsistency errors by the experimental group was slightly higher than the average time spent by the control group. In relation to the degree of correctness among the models generated by the experimental group, there is one that has the highest degree of correctness with 85.7%. However, the degree of similarity between the models is considered "low similarity”. The result of the qualitative evaluation showed that the participants agreed that the mapping rules and heuristics are comprehensible and easy to use. It was also observed that the heuristics were used correctly in the derivation of test cases.

FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgico / Neste trabalho avaliamos mÃtodos heurÃsticos e exatos para o Problema de Particionamento de Conjuntos (PPC). Realizamos testes computacionais com heurÃsticas lagrangeanas baseadas em algoritmos gulosos, busca tabu e mÃtodo de otimizaÃÃo pelo subgradiente. Os resultados obtidos, comparados com os da literatura, comprovam a eficiÃncia de nossas heurÃsticas na obtenÃÃo de limites inferiores e superiores de boa qualidade, em tempo computacional razoÃvel, para instÃncias da literatura. Utilizamos um esquema de Branch and Bound para tentar resolver instÃncias do PPC ÃÂotimalidade e para comprovar a qualidade dos resultados alcanÃados por nossas heurÃsticas. / In this work we evaluate both exact and heuristic methods for the set partitioning problem (SPP). These heuristics are based on greedy algorithms, tabu search and subgradient optimization. Computational experiments performed on benchmark instances of the problem indicate that our heuristics are competitive with existing ones from the literature in obtaining both lower and upper bounds of good quality in reasonable execution time. We use a Branch and Bound algorithm that allows to prove optimality of solutions obtained by our heuristics for a large set of benchmark instances of the SPP. Thus, we show that our heuristics are efficient in obtaining feasible solutions of good quality for this problem.

Submitted by Marlene Santos (marlene.bc.ufg@gmail.com) on 2017-11-17T16:18:59Z No. of bitstreams: 2 Dissertação - Denner Monteiro de Carvalho - 2017.pdf: 49512193 bytes, checksum: dce0c13146977219335b29250e4960d7 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-11-20T10:11:34Z (GMT) No. of bitstreams: 2 Dissertação - Denner Monteiro de Carvalho - 2017.pdf: 49512193 bytes, checksum: dce0c13146977219335b29250e4960d7 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-11-20T10:11:34Z (GMT). No. of bitstreams: 2 Dissertação - Denner Monteiro de Carvalho - 2017.pdf: 49512193 bytes, checksum: dce0c13146977219335b29250e4960d7 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-09-28 / The present work presents the development of a computational tool for the optimization of processes in the elaboration of electromechanical projects of conventional electricity distribution networks. The current process of elaboration of distribution network projects that has significant topographical interferences is slow and depends on software with a technological lag that requires post processing of the data to generate the final project, besides demanding specific technical knowledge and too much elaboration time. This elaboration time, as well as the errors occurred in the post-processing stage, hinder the approval process of the projects in the electric power concessionaires, and delay the connection of final consumers. For modeling the process, the typologies of the terrain where the network path is to be determined through surveys of the topographic data are verified first. Afterwards, mechanical forces and stresses are observed in each type of electromechanical structure, defining the minimum mounting distances in compliance with related technical norms, as well as incident variables such as wind speed and mechanical variations of the conductors during the operation. The modeling of the decision variables is applied a recursive heuristic method with the application of the Hill Climbing optimization method, which sweeps the entire line defined by topography, performing the mechanical evaluations and calculations with the optimization of technical budget criteria, generating uniform solutions and Automated. The tool obtained is developed in Web platform with friendly interface and updated, and can be used through any browser. The software, besides providing the elaboration of the project with embedded normative criteria, can be easily used for project analysis, providing integrated visualization of the planialtimetric profiles through Google Maps, optimizing the process of visual evaluation. / O presente trabalho apresenta o desenvolvimento de um método computacional destinado à otimização de processos na elaboração de projetos eletromecânicos de redes de distribuição convencional de energia elétrica. O processo atual de elaboração de projetos de redes de distribuição que possui interferências topográficas é lento e depende de softwares com defasagem tecnológica que necessitam de pós processamento dos dados para gerar o projeto final, além de demandar conhecimento técnico específico e demasiado tempo de elaboração. Esse tempo de elaboração, bem como os erros ocorridos na etapa de pós processamento, dificultam o processo de aprovação dos projetos nas concessionárias de energia elétrica, e atrasam a ligação dos consumidores finais. Para modelagem do processo, são verificados primeiramente as tipologias do terreno onde se deseja definir o caminhamento da rede através de levantamentos dos dados topográficos. Após, são observados os esforços e solicitações mecânicas pontualmente em cada tipo de estrutura eletromecânica, definindo as distâncias mínimas de montagem em observância às normas técnicas relacionadas, e também, variáveis incidentes como a velocidade do vento e variações mecânicas dos condutores durante a operação. Realizada a modelagem das variáveis de decisão é aplicado um método heurístico recursivo com a aplicação do método de otimização Hill Climbing, que varre toda a linha definida pela topografia, realizando as avaliações e cálculos mecânicos com a otimização de critérios técnicos orçamentários, gerando soluções uniformizadas e automatizadas. O método computacional é desenvolvido em plataforma Web com interface amigável e atualizada, podendo ser utilizada através de um navegador qualquer. O software além de proporcionar a elaboração do projeto com critérios normativos embutidos, pode ser facilmente utilizada para análise de projetos, proporcionando visualização integrada dos perfis planialtimétricos através Google Maps, otimizando o processo de avaliação visual.

Esta tese realiza um estudo a respeito da confiança do investidor estrangeiro no Brasil, identificando teórica e empiricamente os aspectos jurídicos elementares à sua formação. A pesquisa tem como intuito analisar o papel do Direito tanto na geração quanto na proteção à confiança nutrida pelos investidores no País. Faz-se assim um percurso teórico que discute os pressupostos relacionados à racionalidade do homem econômico, sendo apresentadas algumas linhas críticas do paradigma de escolha racional. Dentre tais linhas, a Economia Comportamental é escolhida como opção metodológica do trabalho por fornecer uma visão alternativa para o estudo de tomada de decisão. Assim, com base no programa pesquisa Heuristics and Biases (H&B), fundado por Daniel Kahneman e Amos Tversky, avalia-se o processo de formação da confiança no Brasil. A revisão de literatura interdisciplinar busca fornecer alicerce teórico para o estudo empreendido, ao explorar a dificuldade e a abstração do conceito. A tese, no campo jurídico, (i) contrapõe as noções de confiança e boa-fé, (ii) discute como se dá a tutela da confiança pelo Direito brasileiro e (iii) destaca aspectos da regulação dos investimentos estrangeiros capazes de tutelar ou promover a confiança. A pesquisa empírica realizada ao final do trabalho aplica o H&B à análise do Direito, destacando as variáveis jurídicas consideradas essenciais à confiança do investidor no Brasil e analisando dissonâncias cognitivas a este respeito entre residentes e não residentes. / This thesis investigates foreign investors trust in Brazil, aiming at identifying theoretically and empirically its elementary aspects. It also intends to analyze the role played by Law at the creation and preservation of investors trust. From a theoretical standpoint, it discusses the rationality assumptions attributed to the economic man and reports alternative approaches for decision making other than rational choice. The work applies Behavioral Economics methodology, more specifically the Heuristics and Biases program, founded by Daniel Kahneman and Amos Tversky. The thesis also reviews interdisciplinary literature on trust, exploring the elusiveness of its concept. In addition, from a legal research perspective, it (i) compares the notions of trust and good-faith; (ii) discusses the legal grounds for trust protection under local law and (iii) points out regulatory mechanisms deemed capable of protecting or promoting trust. The empirical research presented at the end of the thesis illustrates how H&B may be applied to the analysis of Law, by assessing its role at promoting investors trust as well as assessing cognitive dissonances found among resident and non residents.

Esta pesquisa trata o Problema de Programação de Tripulantes (PPT), presente no planejamento operacional das empresas aéreas. O principal objetivo do PPT é atribuir o conjunto de tripulantes requeridos para a operação dos voos de uma malha aérea de maneira a minimizar o custo total da tripulação, levando em conta a legislação pertinente e a satisfação dos tripulantes. O PPT é normalmente dividido na literatura em dois subproblemas independentes, modelados e resolvidos sequencialmente: Problema de Determinação de Viagens (PDV) e Problema de Atribuição de Escalas (PAE). Esta decomposição não incorpora os atributos (disponibilidade, qualificação, senioridade e preferências individuais) dos tripulantes de forma global, o que não permite uma estimativa real de custo e afeta a qualidade da solução final. O estado da arte envolve a solução integrada do PPT, eliminando a necessidade de se resolver inicialmente o PDV e permitindo a obtenção de uma solução mais realista. O PPT, no entanto, é de natureza combinatória. Assim sendo, esta pesquisa propõe e explora modelos baseados em programação linear inteira e em heurísticas para a solução integrada do PPT. Essas heurísticas incorporam fundamentos da meta-heurística GRASP, da heurística de economias de Clarke e Wright e da heurística day-by-day. Os modelos foram testados com sucesso para a solução de instâncias baseadas na malha real de três empresas aéreas brasileiras. / This doctoral research treats the Crew Scheduling Problem (CSP), as part of the airlines operational planning. The CSP consists of optimally assigning the required crew members to planned flights, in such a way that it minimizes the total cost of the aircrew, taking into consideration the proper legislation and the satisfaction of the crew members. The CSP is usually divided into two independent subproblems, modeled and solved sequentially: Crew Pairing Problem (CPP) and Crew Rostering Problem (CRP). This decomposition does not incorporate all the crew members attributes (availability, qualification, seniority and individual preferences), which does not lead to a real cost estimate and affects the quality of the final solution. The state of the art involves the integrated solution of CSP, without solving the CPP at first and providing a more realistic solution. The CSP, however, has a combinatorial nature. This research proposes and explores models based on integer linear programming and on heuristics to solve the CSP in an integrated way. These heuristics incorporate GRASP metaheuristic, Clarke and Wright savings heuristic and day-by-day heuristic. The models were successfully tested to solve instances related to the networks of three Brazilian airlines.

Made available in DSpace on 2016-08-18T12:52:12Z (GMT). No. of bitstreams: 1 DISSERTACAO_ALLAN KASSIO BECKMAN SOARES DA CRUZ.pdf: 3904761 bytes, checksum: fcf2b0e10224d47b174664dcde46f7b8 (MD5) Previous issue date: 2015-06-02 / In recent years within the emerged game development tools and methodologies that try define, practical and theoretically, the practices for the creative process of game design (SALEN; ZIMMERMAN, 2012). These tools and methodologies often xclude and end up to be more difficult the job of game designer. Factors such as playful interaction,rules and culture are relevant to the development of a good game. This master s thesis uses as a study object the board games and aims to create a set of heuristics that are able to assess the rules of any board game. To achieve this goal was established a methodology that trasnform the rule of these games in an interaction model that can be evaluated by computer systems assessment methodologies as the heuristics of Nielsen (1994). Originally the Nielsen heuristics have been proposed and developed for sability evaluation in computer systems interfaces. We proposes an analysis and redesign in order to specialize these heuristics to use in the evaluation rules of board games. Heuristics pass through redesign process from literature, considerations and models generated on the rules found in each tested game, and analysis of existing rules in these games through inspection method using heuristics Nielsen (1994). The results indicate the viability of using generated heuristics for the evaluating of usability of the board games rules. / Nos últimos anos dentro da área de desenvolvimento de jogos surgiram ferramentas e metodologias que tentam por vezes de forma prática e por vezes de forma teórica definir as práticas do processo criativo do design de jogos (SALEN; ZIMMERMAN, 2012). Essas ferramentas e metodologias muitas vezes se excluem e acabam tornando mais difícil o trabalho do designer de jogos. Fatores como interação lúdica, regras e cultura são relevantes para o desenvolvimento de um bom jogo. Este trabalho utiliza como objeto de estudo os jogos de tabuleiro e tem como objetivo a criação de um conjunto de heurísticas que sejam capazes de avaliar as regras de qualquer jogo de tabuleiro. Para alcançar esse objetivo foi criada uma etodologia que transforma a regra desses jogos em um modelo de interação passível de ser avaliado por metodologias de avaliação de sistemas computacionais como as heurísticas de Nielsen (1994). Originalmente as heurísticas de Nielsen foram propostas e desenvolvidas para avaliação de usabilidade em interfaces de sistemas computacionais.No decorrer do trabalho propõe-se uma análise e redesenho de forma a especializar essas heurísticas para emprego na avaliação de regras de jogos de tabuleiros. As heurísticas passam pelo processo de redesenho a partir de levantamento bibliográfico, considerações e modelos gerados sobre as regras encontradas em cada jogo testado, além da análise das regras existentes nesses jogos através de método de inspeção utilizando as heurísticas de Nielsen (1994) e as eurísticas geradas durante o redesenho. Os resultados apontam para a viabilidade da utilização das heurísticas geradas para a avaliação de usabilidade das regras de jogos de tabuleiro.

Orientadores: André Luiz Morelato França, Paulo Morelato França / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-20T08:47:23Z (GMT). No. of bitstreams: 1 Usberti_FabioLuiz_D.pdf: 2207082 bytes, checksum: 83078a448a40f75c373b989f9af006fb (MD5) Previous issue date: 2012 / Resumo:O problema de roteamento em arcos capacitado e aberto (open capacitated arc routing problem, OCARP) é um problema de otimização combinatorial NP-difícil em que, dado um grafo não-direcionado, o objetivo consiste em encontrar um conjunto de rotas de custo mínimo para veículos com capacidade restrita que atendam a demanda de um subconjunto de arestas. O OCARP está relacionado com o problema de roteamento em arcos capacitado (capacitated arc routing problem, CARP), mas difere deste pois o OCARP não possui um nó depósito e as rotas não estão restritas a ciclos. Aplicações da literatura para o OCARP são discutidas. Uma formula ção de programação linear inteira é fornecida junto com propriedades do problema. Uma metaheurística GRASP (greedy randomized adaptive search procedure) com reconexão por caminhos (path-relinking) é proposta e comparada com outras metaheurísticas bem-sucedidas da literatura. Algumas características do GRASP são: (i) ajuste reativo de parâmetros, cujos valores são estocasticamente selecionados com viés 'aqueles valores que produziram, em média, as melhores soluções; (ii) um filtro estatístico que descarta soluções iniciais caso estas tenham baixa probabilidade de superar a melhor solução incumbente; (iii) uma busca local infactível que gera soluções de baixo custo utilizadas para explorar fronteiras factíveis/infactíveis do espaço de soluções; (iv) a reconexão por caminhos evolutiva aprimora progressivamente um conjunto de soluções de elevada qualidade (soluções elites). Testes computacionais foram conduzidos com instâncias CARP e OCARP e os resultados mostram que o GRASP é bastante competitivo, atingindo os melhores desvios entre os custos das soluções e limitantes inferiores conhecidos. Este trabalho também propõe um algoritmo exato para o OCARP que se baseia no paradigma branch-and-bound. Três limitantes inferiores são propostos e um deles utiliza o método dos subgradientes para resolver uma relaxação lagrangeana. Testes computacionais comparam o algoritmo branch-and-bound com o CPLEX resolvendo um modelo reduzido OCARP de programa ção linear inteira. Os resultados revelam que o algoritmo branch-and-bound apresentou resultados melhores que o CPLEX no que diz respeito aos desvios entre limitantes e ao número de melhores soluções / Abstract: The Open Capacitated Arc Routing Problem (OCARP) is an NP-hard combinatorial optimization problem where, given an undirected graph, the objective is to find a minimum cost set of tours that services a subset of edges with positive demand under capacity constraints. This problem is related to the Capacitated Arc Routing Problem (CARP) but differs from it since OCARP does not consider a depot, and tours are not constrained to form cycles. Applications to OCARP from literature are discussed. An integer linear programming formulation is given, followed by some properties of the problem. A Greedy Randomized Adaptive Search Procedure (GRASP) with path-relinking (PR) solution method is proposed and compared with other successful metaheuristics. Some features of this GRASP with PR are (i) reactive parameter tuning, where the metaheuristic parameters values are stochastically selected biased in favor of those values which produced the best solutions in average; (ii) a statistical filter, which discards initial solutions if they are unlikely to improve the incumbent best solution; (iii) infeasible local search, where high-quality solutions, though infeasible, are used to explore the feasible/infeasible boundaries of the solution space; (iv) evolutionary PR, a recent trend in which a pool of elite solutions is progressively improved by relinking pairs of elite solutions. Computational tests were conducted for both CARP and OCARP instances, and results reveal that the GRASP with PR is very competitive, achieving the best overall deviation from lower bounds. This work also proposes an exact algorithm for OCARP, based on the branch-and-bound paradigm. Three lower bounds are proposed, one of them uses a subgradient method to solve a Lagrangian relaxation. The computational tests compared the proposed branch-and-bound with a commercial state-of-the-art ILP solver. Results reveal that the branch-and-bound outperformed CPLEX in the overall average deviation from lower bounds / Doutorado / Automação / Doutor em Engenharia Elétrica