[pt] Como em toda grande empresa da indústria de óleo e gás, fortemente integrada e altamente rentável, várias são as oportunidades de buscar e encontrar processos logísticos com reais possibilidades de otimização e melhoria. Neste tipo de companhia, encontramos diversas cadeias de suprimento subjacentes ao processo, que por seu porte e complexidade, seriam consideradas principais em diversas outras indústrias ou ramos de serviços. Neste contexto, a presente dissertação se propõe a analisar as etapas e percalços para implantação e manutenção de um software de roteirização como ferramenta para planejamento de frota e rota de transporte de funcionários em regime de turno de uma refinaria. O cenário escolhido para o piloto é uma refinaria de grande porte do estado do Rio de Janeiro. O estudo revisa a bibliografia existente, descreve as principais etapas de coleta e tratamento de dados, mede através do software TRANSCAD as distâncias das rotas propostas e verifica se o potencial ganho obtido em relação à solução em análise justificaria a aquisição de uma ferramenta para este fim. / [en] As in many big oil and gas companies, there are a lot of opportunities to search and find logistics processes with real possibilities for optimization and improvement. In this kind of company there are some supply chains, that are not core chains wich could be considered as main chains in many other industries or service areas due to their size and complexity. Regarding that issue, the present work proposes to analyze the steps and problems related to launching and maintaining a routing software as a solution for vehicle fleet planning and refinery s employees transportation routing. A big refinery placed in Rio de Janeiro state is the chosen scenario. This study reviews the present literature on the theme, describes the main steps on this research and data treatment, uses the software TRANSCAD to measure de length of the proposed routes and finds out if the potential gain with the software solution justifies the acquisition of this tool.

[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] Desde a sua origem, as abordagens a problemas de Otimização Combinatória polarizam-se entre métodos exatos e heurísticos. Recentemente, porém, estratégias que combinam ambos os métodos têm sido propostas para os mais variados problemas, apresentando resultados promissores. Nesse contexto, destacam-se os conceitos de vizinhaças de bola e elipsoidal, que realizam buscas em relação a uma ou mais soluções de referência. Este trabalho estuda a aplicação de tais vizinhanças para o Problema de Roteamento de Veículos com Restrição de Capacidade (CVRP), sobre o algoritmo de Branch-and-Cut-and-Price Robusto. Experimentos foram realizados e seus resultados analisados. / [en] Since its inception, approaches to Combinatorial Optimization were polarized between exact and heuristic methods. Recently, however, strategies that combine both methods have been proposed for various problems, showing promising results. In this context, the concepts of ball and ellipsoidal neighborhood appear, which perform a search regarding one or more reference solutions. This work studies the application of such neighborhoods for the Capacitated Vehicle Routing Problem (CVRP), using the Robust Branchand- Cut-and-Price algorithm. Experiments were made and its results were analyzed.

[pt] A busca pelo desenvolvimento sustentável tem como importante fator diferencial as fontes de energia renováveis. O biodiesel desponta como uma das alternativas mais relevantes, mas suas formas de obtenção no Rio de Janeiro não foram suficientemente investigadas. Este trabalho identifica a oportunidade da produção de biodiesel a partir de óleos residuais de fritura neste cenário, enfatizando os custos de transporte do óleo desde os principais produtores comerciais até a obtenção do biocombustível. O objetivo é avaliar os custos de forma a verificar a viabilidade do emprego desta alternativa. Para tanto, foram estudadas as diversas ferramentas de resolução do Problema de Roteamento de Veículos e foi proposto um algoritmo que visa à otimização dos custos. A formulação matemática utilizada baseia-se numa extensão de algoritmos clássicos, como o apresentado por Arenales et al. (2007), e nas equações desenvolvidas em Kallehauge (2006). Os resultados do modelo de roteamento, atrelados aos custos de produção, impostos e insumos, foram comparados com informações sobre a comercialização do biodiesel, comprovando sua viabilidade econômica. A consolidação dos dados obtidos aponta a produção de biodiesel a partir de óleo residual de fritura como viável, com custos logísticos equivalentes a R/tmp/aaaUFg8ya,19 por litro e custo final de R,22 por litro. / [en] The search for a sustainable development has in renewable energy sources an important differential factor. Biodiesel is one of the most important alternatives, but its obtainment forms in Rio de Janeiro have not been investigated enough. This work identifies the opportunity of biodiesel production from waste cooking oil in this scenery, emphasizing oil`s transport costs until factories, where it is possible to obtain biodiesel in its final form. The objective is to evaluate costs in order to verify viability of this alternative source of energy. Hence, this research analysed several tools for solving Vehicle Routing Problem and it proposes an algorithm that results in cost optimization. The adapted mathematic formulation is based in an extension of classic algorithms, like those presented by Arenales (2007), and in equations developed by Kallehauge (2006). The routing model results, linked to production, tributes and input costs, have been compared with information about biodiesel commercialization, verifying its economic viability. The data consolidation obtained indicates that the biodiesel production from waste cooking oil is viable, with logistic costs equal to R/tmp/aaaPLIh7a,19 per liter and final cost equal to R,22 per liter.

[pt] Na atualidade, as organizações públicas e privadas buscam otimizar seus processos de modo que, estes garantam a qualidade dos serviços e o retorno sobre o capital investido nas diversas operações que estão envolvidas. Com isso, as organizações que não se preocupam em desenhar seus processos com eficácia e eficiência, estarão sujeitas a falhas, onerando assim os custos de operação. O estudo em questão propõe uma política de atendimento às demandas de manutenção e a utilização de uma ferramenta de roteirização diária no desempenho das operações do setor de manutenção de uma universidade pública do estado de Minas Gerais. O Problema de Roteirização de Veículos (PRV), do inglês Vehicle Routing Problem (VRP), como é conhecido na literatura, é definido como o atendimento a pontos de demanda geograficamente dispersos, por intermédio de uma frota de veículos disponíveis que, em geral, partem e retornam a um depósito central. O PRV tem como objetivo encontrar rotas viáveis com um menor custo que respeite as restrições operacionais, como duração da jornada de trabalho, capacidade dos veículos, duração das rotas, entre diversas outras. No trabalho será proposta uma metodologia que sugere uma nova política de distribuição de profissionais e materiais necessários para realização dos atendimentos às demandas de manutenção das unidades internas e externas da universidade e faz uso de um software de solução do PRV para verificar o desempenho das políticas propostas. Os resultados do estudo para as estratégias propostas apresentaram reduções significativas, variando de 17,86 porcento a 66,27 porcento do custo mensal, além de oportunidades de ganhos operacionais frente ao cenário atual. Espera-se que o software de PRV seja utilizado na programação diária dos roteiros dos veículos do setor. / [en] Currently, public and private organizations seek to optimize their process-es in order to guarantee the quality of services and the return on capital invested in the various operations that are involved. As a result, organizations that are not concerned with designing their processes effectively and efficiently, will be sub-ject to failures, thus increasing operating costs. The study in question proposes a policy to meet maintenance demands and the use of a daily routing tool in the performance of operations in the maintenance sector of a public university in the state of Minas Gerais. The Problema de Roteamento de Veículos (PRV), from the English Vehicle Routing Problem (VRP), as it is known in the literature, is defined as the service to meet geographically dispersed demand points, through a fleet of available vehicles that, in general, depart and return to a central depot. The VRP aims to find viable routes at a lower cost that respects operational re-strictions, such as working hours, vehicle capacity, duration of routes, among others. In the work, a methodology will be proposed that suggests a new policy for the distribution of professionals and materials needed to fulfill the demands of maintenance of the university s internal and external units and makes use of a VRP solution software to verify the performance of the proposed policies. The results of the study for the proposed strategies showed significant reductions, varying from 17.86 percent to 66.27 percent of the monthly cost, in addition to opportunities for operational gains compared to the current scenario. It is expected that the VRP software will be used in the daily programming of the routes for vehicles in the sector.

[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.