[pt] Esta tese define os problemas das p-medianas conectadas e o de localização de facilidades não-capacitadas conectadas. Possíveis aplicações incluem problemas de planejamento regional e o projeto de redes de telecomunicações ou de transporte. Para o primeiro problema, duas formulações de programação linear inteira são apresentadas e comparadas. Um destes modelos é adaptado para o segundo problema. Para o problema das p-medianas conectadas, algoritmos aproximados são desenvolvidos. Uma estratégia de busca local híbrida é proposta. Para acelerar as iterações do algoritmo de busca local, idéias como circularidade, melhoria iterativa e o descarte de vizinhos são incorporadas. Heurísticas GRASP e VNS são desenvolvidas incluindo a utilização de um filtro com o objetivo de diminuir os tempos de processamento e do procedimento de reconexão por caminhos com o objetivo de melhorar a qualidade das soluções encontradas. Diversos testes são realizados comparando-se esses algoritmos. Os resultados mostraram a necessidade de se executar um passo adicional de pós-otimização às heurísticas GRASP e VNS propostas. / [en] In this work, the connected p-median and the connected facility location problems are defined. Applications arise in regional planning, design of telecommunications and transportation networks. For the first problem, two integer linear programming formulations are proposed. Adaptations are made in one of these formulations and are used to model the second problem. Approximation algorithms to solve the connected p-median problem are developed. A hybrid local search strategy is proposed. In order to speed up the local search iterations, ideas as circularity, first- improving strategy and discard neighbors are incorporated. A GRASP algorithm and a VNS heuristic are also proposed. A filter is used to reduce the computational time required and a path-relinking is applied to improve the results found. Computational experiments to compare the algorithms are reported. To improve these results, it is applied a post-optimization step to the GRASP and VNS heuristics.

[pt] Nesta tese são propostos modelos e algoritmos aproximados para o Problema da Árvore Geradora de Custo Mínimo com Restrição de Diâmetro (AGMD). Este problema modela tipicamente aplicações em projetos de redes de computadores onde todos os vértices devem comunicar-se entre si a um custo mínimo, garantindo um certo nível de serviço. Os modelos propostos por Achuthan e Caccetta para o AGMD são reforçados através da introdução de restrições válidas. Uma relaxação lagrangeana é proposta para o modelo de multifluxo básico de Gouveia e Magnanti. Essa relaxação é utilizada para o desenvolvimento de heurísticas lagrangeanas. Adaptações são realizadas nas heurísticas construtivas propostas por Deo e Abdalla, e por Raidl e Julstrom. São propostas ainda quatro estratégias de busca local, uma heurística do tipo GRASP e outra híbrida. São obtidos limites superiores a menos de 2% do ótimo para as classes de instâncias usadas nos trabalhos de Gouveia e Magnanti, e de Santos, Lucena e Ribeiro. Além disto, obteve-se os melhores resultados conhecidos até o presente momento para 11 instâncias de grafos completos usadas por Raidl, Julstrom e Gruber. / [en] In this work, models and approximation algorithms to solve the Diameter Constrained Minimum Spanning Tree Problem (AGMD) are proposed. This problem typically models network design applications where all vertices must communicate with each other at a minimum cost, while meeting a given quality requirement. The formulations proposed by Achuthan and Caccetta are strengthened with valid inequalities. A lagrangean relaxation is proposed for the multicommodity flow model developed by Gouveia and Magnanti. Adaptations are made in the constructive heuristics proposed by Deo and Abdalla and by Raidl and Julstrom. Four local search procedures, a GRASP algorithm and a hybrid heuristic are proposed. Upper bounds within 2% of the optimal solution values are obtained for the two classes of instances used by Gouveia and Magnanti and by Santos, Lucena and Ribeiro. Moreover, stronger upper bounds are reported for 11 instances in complete graphs used by Raidl, Julstrom and Gruber

[pt] A indústria de transporte marítimo é essencial para o comércio internacional. No entanto, no despertar da crise financeira de 2008, essa indústria foi severamente atingida. Nessas ocasiões, empresas de transporte só são capazes de obter lucro se suas frotas forem roteadas de forma eficaz. Neste trabalho, nós estudamos uma classe de problemas de roteamento de navios relacionados ao Pickup and Delivery Problem with Time Windows. Para resolver esses problemas, nós introduzimos um método heurístico e um exato. O método heurístico é uma meta-heurística híbrida com uma vizinhança larga baseada em set partitioning, enquanto o método exato é um algoritmo de branch-and-price. Nós conduzimos experimentos em um conjunto de instâncias baseadas em rotas de navios reais. Os resultados obtidos mostram que nossos algoritmos superam as metodologias estado da arte. Em seguida, nós adaptamos o conjunto de instâncias para modelar um problema de roteamento de navios no qual a velocidade em cada segmento de rota é uma variável de decisão, e o consumo de combustível por unidade de tempo é uma função convexa da velocidade e carga do navio. A fim de resolver esse novo problema de roteamento de navios com otimização de velocidade, nós estendemos nossa meta-heurística para encontrar decisões de velocidade ótimas em toda avaliação de solução vizinha de uma busca local. Nossos experimentos demonstram que essa abordagem pode ser altamente rentável, e que requer apenas um aumento moderado de recursos computacionais. / [en] The shipping industry is essential for international trade. However, in the wake of the 2008 financial crisis, this industry was severely hit. In these times, transportation companies can only obtain profit if their fleet is routed effectively. In this work, we study a class of ship routing problems related to the Pickup and Delivery Problem with Time Windows. To solve these problems, we introduce a heuristic and an exact method. The heuristic method is a hybrid metaheuristic with a set-partitioning-based large neighborhood, while the exact method is a branch-and-price algorithm. We conduct experiments on a benchmark suite based on real-life shipping segments. The results obtained show that our algorithms largely outperform the state-of-the-art methodologies. Next, we adapt the benchmark suite to model a ship routing problem where the speed on each sailing leg is a decision variable, and fuel consumption per time unit is a convex function of the ship speed and payload. To solve this new ship routing problem with speed optimization, we extend our metaheuristic to find optimal speed decisions on every local search move evaluation. Our computational experiments demonstrate that such approach can be highly profitable, with only a moderate increase in computational effort.

[pt] Clusterização desempenha um papel importante em data mining, sendo útil em muitas áreas que lidam com a análise exploratória de dados, tais como recuperação de informações, extração de documentos e segmentação de imagens. Embora sejam essenciais em aplicações de data mining, a maioria dos algoritmos de clusterização são métodos ad-hoc. Eles carecem de garantias na qualidade da solução, que em muitos casos está relacionada a uma convergência prematura para um mínimo local no espaço de busca. Neste trabalho, abordamos o problema de clusterização a partir da perspectiva de otimização, onde propomos um algoritmo genético híbrido para resolver o problema Minimum Sum-of-Squares Clustering (MSSC, em inglês). A meta-heurística proposta é capaz de escapar de mínimos locais e gerar soluções quase ótimas para o problema MSSC. Os resultados mostram que o método proposto superou os resultados atuais da literatura – em termos de qualidade da solução – para quase todos os conjuntos de instâncias considerados para o problema MSSC. / [en] Clustering plays an important role in data mining, being useful in many fields that deal with exploratory data analysis, such as information retrieval, document extraction, and image segmentation. Although they are essential in data mining applications, most clustering algorithms are adhoc methods. They have a lack of guarantee on the solution quality, which in many cases is related to a premature convergence to a local minimum of the search space. In this research, we address the problem of data clustering from an optimization perspective, where we propose a hybrid genetic algorithm to solve the Minimum Sum-of-Squares Clustering (MSSC) problem. This meta-heuristic is capable of escaping from local minima and generating near-optimal solutions to the MSSC problem. Results show that the proposed method outperformed the best current literature results - in terms of solution quality - for almost all considered sets of benchmark instances for the MSSC objective.

[pt] Esta dissertação apresenta novos algoritmos aproximados e uma abordagem exata para a resolução de um problema de correspondência inexata de grafos. O problema considerado é o de correspondência entre um grafo representando um modelo genérico e outro representando dados a serem reconhecidos. Assumi-se que o grafo dos dados possui mais vértices que o do modelo. A motivação para o estudo desse problema vem de problemas de reconhecimento de cenas, que consistem na caracterização dos objetos envolvidos em uma determinada cena, assim como das relações existentes entre eles. Uma aplicação para este problema na área de reconhecimento de imagens médicas é a de efetuar-se o reconhecimento de estruturas 3D do cérebro humano, a partir de imagens obtidas por ressonância magnética. Tais imagens são previamente processadas por algum método de segmentação automática e o processo de reconhecimento consiste na busca da correspondência estrutural entre a imagem e um modelo genérico, tipicamente definido como um atlas de imagens médicas. Foram propostos novos algoritmos aproximados, tais como um algoritmo construtivo guloso aleatorizado, um procedimento de reconexão de caminhos e um GRASP que combina estes com uma técnica de busca local. Além disso, foi proposta uma formulação original do problema como um problema de programação linear inteira, que permitiu a resolução de algumas instâncias de forma exata. / [en] This dissertation presents new approximation algorithms and an exact approach to the solution of an inexact graph matching problem. The problem consists in finding the best match between a generic model graph and a graph representing an image, the latter with more nodes than the former. The motivation for studying this problem comes from a scene recognition problem, which consists in characterizing objects involved in a given scene and the relationships between them. An application of this problem appears in the analysis of medical images and consists in recognizing 3-dimensional structures in the human brain using images obtained by magnetic resonance. Such images must be previously processed by an automatic segmentation method and the recognition process consists in the search of an structural matching between the image and a generic model, typically defined as an atlas of medical images. New heuristics are proposed, such as a greedy randomized construction algorithm, a path relinking procedure and a GRASP heuristic that combines them with a local search technique. Furthermore, an original integer formulation of the problem based on integer multicommodity flows is proposed, which makes possible the exact solution of medium- sized instances.

[pt] O problema de roteamento de veículos escolares, do inglês School Bus Routing Problem (SBRP), trata de planejar as rotas de uma frota de veículos para locomover os alunos dos pontos de embarque até suas respectivas escolas. O SBRP é um caso especial do problema de roteamento de veículos, do inglês Vehicle Routing Problem (VRP) e é conhecido por ser um problema NP-difícil. A maior parte da literatura referente ao SBRP se concentra, principalmente, em modelos matemáticos para resolver o problema de roteamento aplicando restrições da vida real. Já em relação à geocodificação dos endereços das escolas e alunos, bem como a busca de distâncias e tempos de deslocamentos reais, estas também são pontos de vital importância, visto que as distâncias reais se diferem da euclidiana e geodésica principalmente em áreas rurais, região de estudo deste trabalho. Neste contexto, uma metodologia é proposta para o problema, junto com um protótipo para automatizar os procedimentos necessários para à obtenção de informações, cuja a aplicação, a partir de um cenário real no contexto brasileiro, é apresentada e dividida em oito fases: definir abrangência, geocodificar o endereço de escolas, alunos e pontos de embarque, definir as características, calcular a distância e o tempo de percurso, montar o banco de dados georreferenciado e de veículos, aplicar uma ferramenta para a obtenção das rotas, geoespacilizar as rotas e elaborar diagnóstico. A proposta é testada aplicando uma ferramenta para a obtenção das rotas que utiliza a meta-heurística Adaptative Large Neighborhood Search (ALNS) para resolver instâncias do VRP. Desta forma, uma das contribuições do estudo consiste no georreferenciamento das unidades escolares estaduais, estando as informações presentes na plataforma do Google Maps para visualização do público. No estudo são localizados e roteados 150 alunos de 7 unidades escolares da cidade de Nova Friburgo. O resultado apresenta valores consistentes e satisfatórios, demonstrando economia média de 41,62 por cento nos custos praticados nas rotas. / [en] The School Bus Routing Problem (SBRP) deals with planning the routes of a fleet of vehicles to move the students from boarding points to their respective schools. The SBRP is a special case of Vehicle Routing Problem (VRP) and is known to be an NP-hard problem. Most of the SBRP literature focuses, mainly, on mathematical models to solve the routing problem by applying real-life restrictions. Regarding the geocoding of the addresses of schools and students, as well as the search for distances and times of real displacements, are also points of vital importance, since the actual distances differ from the euclidean and geodesic ones mainly in rural areas, study region this work. In this context, a methodology is proposed for the problem, along with a prototype to automate the procedures required to obtain information, whose application, based on a real scenario in the Brazilian context is presented, divided into eight phases: to define scope, to geocode the address of schools, student and boarding points, to define the characteristics, to calculate the distance and travel time, to set the georeferenced database and vehicles, to apply a tool to obtain the routes, to geospatialize the routes and elaborate diagnosis. The proposal is tested by applying a tool to obtain routes using the Adaptive Large Neighborhood Search (ALNS) meta-heuristic to solve VRP instances. Thus, one of the contributions of the study consists in the georeferencing of the state school units, with the information present in the Google Maps platform for public viewing. In the study, 150 students from 7 school units in the city of Nova Friburgo were located. The result presents consistent and satisfactory values, demonstrating savings of 41.62 percent in the costs practiced on th routes.

[pt] A otimização combinatória (OC) está presente em inúmeras aplicações práticas (por exemplo, planejamento de produção, logística, etc.). Ao longo dos anos, OC e aprendizado de máquina (AM) surgiram, juntas, como uma área prospectiva de pesquisa para melhorar processos de tomada de decisão. Nesse contexto, há interesse em utilizar algoritmos de AM para melhorar métodos de OC. Por outro lado, como muitas tarefas de AM podem ser reformuladas como problemas de otimização, há um amplo interesse em utilizar métodos de OC para resolver esses problemas. Nesta tese, três estudos que conectam OC e AM em torno de duas aplicações importantes são conduzidos: o problema de roteamento de veículos capacitado (PRVC) e máquinas de vetores de suporte com perda em margem rígida (SVM-HML – do inglês support vector machines with hard-margin loss). No primeiro estudo, uma estratégia para explorar vizinhanças de busca local de alta ordem por mineração de padrões em duas meta-heurísticas estado da arte para o PRVC é proposta. Em um segundo estudo, também no contexto do PRVC, critérios de relacionamento para nós de clientes baseados em saídas de redes neurais em grafos são explorados. Com base nessas saídas, medidas de relação podem ser exploradas para orientar a busca local e estender operadores de cruzamento em um algoritmo genético estado da arte. Por fim, no terceiro estudo, uma abordagem eficiente de programação inteira mista baseada em cortes combinatórios de Benders e estratégias de amostragem são utilizadas para treinar modelos de SVM-HML de maneira mais eficiente. / [en] Combinatorial optimization (CO) is ubiquitous in myriad practical applications (e.g., production planning, scheduling, logistics, etc.). Over the years, CO and machine learning (ML) have emerged, together, as a prospective area of research for improving decision-making processes. There is interest to harness ML algorithms to improve existing CO methods. Conversely, since many ML tasks can be reformulated as optimization problems, there is broad interest in leveraging state-of-the-art CO methods for them. In this thesis, we conduct three studies that connect CO and ML around two important applications: the capacitated vehicle routing problem (CVRP) and support vector machines with hard-margin loss (SVM-HML). Our first study proposes a strategy to explore high-order local-search neighborhoods by pattern mining into two state-of-the-art metaheuristics for the CVRP. In a second study, also in the context of the CVRP, we exploit relatedness criteria for customer nodes using predictions from graph neural networks. We show that relatedness measures can be exploited to steer local search and extend crossover operators in a stateof- the-art genetic algorithm. Lastly, in a third study, we propose an efficient mixed-integer programming approach based on Combinatorial Benders cuts and sampling strategies for optimally training the SVM-HML.

[pt] Esta pesquisa trata de duas variantes do conhecido Problema de Roteirização de Veículos com Estoque (do inglês Inventory Routing Problem – IRP). O problema nasce num contexto de um sistema de Vendor Managed Inventory (VMI) no qual o fornecedor é responsável pela gestão de estoques do cliente. Tal problema é a junção dos problemas de transporte e gestão de estoques, que correspondem aos maiores custos em uma operação logística. Destarte este trabalho apresenta um modelo matemático para uma variante do IRP que considera que o fornecedor tem clientes dentro e fora do sistema de VMI. Este caso surge quando para alguns clientes não é interessante a realização do controle de seus estoques dentro do sistema de VMI, somente o atendimento de suas demandas. Além disto, o modelo contempla três diferentes tipos de políticas de gestão de estoques e é capaz de lidar com casos contendo vários períodos e vários veículos. Após sua elaboração, o modelo foi validado em instâncias do IRP, do Problema de Roteamento de Veículos (do inglês Capacitated Vehicle Routing Problem - CVRP) e instâncias próprias para a variante. Foram realizados também estudos sobre os impactos das diferentes políticas de gestão de estoques. Além do modelo matemático, foi desenvolvida uma meta-heurística híbrida que resolve uma variante do IRP considerando vários períodos e vários veículos. Cada movimento considerado durante a meta-heurística é divido em duas etapas, a primeira sendo a modificação da posição de um ou mais clientes nos veículos e períodos e uma segunda etapa que resolve de forma exata um Problema de Fluxo Máximo a Custo Mínimo para a atribuição ótima do volume de carga transportada para cada cliente por cada veículo em cada período. Esta abordagem é então testada em instâncias clássicas para esta variante do IRP, obtendo resultados que comprovam a eficiência do algoritmo. / [en] This research deals with two variants of the Inventory Routing Problem (IRP). This problem comes from the context of a Vendor Managed Inventory (VMI) system in which the vendor is responsible for managing the customer s inventory. It is the combination of transportation and inventory management problems, which correspond to the higher costs in a logistics operation. Hence, this paper presents a mathematical model for an IRP variant, in which the vendor has customers inside and outside the VMI system. This situation is presented when it is not interesting to manage the inventories of some clients within the VMI system, resulting only in meeting their demands. In addition, the model considers three different types of stock management policies and it can comprehend multiple periods and multiple vehicles. After its modelling, the model was validated using IRP instaces, the Vehicle Routing Problem (CVRP) and specific instances for this variant. The impacts of different inventory management policies were also analyzed. In addition to the mathematical model, a hybrid meta-heuristic was developed, which solves an IRP variant considering several periods and several vehicles. Each iteration of the metaheuristic is divided into two stages: the first is modifying the position of one or more customers attended by the vehicles and periods, and a second step that solves a Maximum Flow at Minimum Cost problem, to optimally assign the load volumes transported to each customer in each vehicle in each period. Then, this approach is tested in classical instances for this IRP variant, obtaining results that prove the efficiency of the algorithm.