[pt] Tema: Este estudo investiga o Problema de Roteamento de Inventário (IRP) no contexto do Gerenciamento de Inventário pelo Fornecedor (VMI), uma prática comum na cadeia de suprimentos onde os fornecedores assumem a responsabilidade pela reposição. O IRP, um problema combinatório estudado amplamente há quase 40 anos, engloba três subproblemas distintos: programação de entregas, gerenciamento de estoque e roteamento de veículos. Problema: Apesar de sua idade, o IRP continua a atrair a atenção da indústria e da academia. O recente décimo segundo Desafio de Implementação DIMACS dedicou uma categoria ao IRP, e entre os benchmarks comumente utilizados, 401 instâncias ainda não possuem soluções ótimas, especialmente no desafiador subconjunto de instâncias grandes. Hipótese e Justificativa: O framework HGS proposto por Vidal et al. (2012) surgiu como uma ferramenta proeminente utilizada por várias equipes de forma satisfatória na competição. No entanto, até onde sabemos, o framework HGS não foi testada para o IRP. Este estudo propõe uma solução que combina o framework HGS com uma estratégia de busca local eficiente, o método NSIRP proposto por Diniz et al. (2020), para abordar o IRP. Metodologia: Implementamos a solução proposta e comparamos seu desempenho com 21 abordagens existentes, utilizando os benchmarks da literatura. Resumo dos Resultados: Nossa abordagem identificou 79 novas Melhores Soluções Conhecidas (BKS) dentre 1100 instâncias. Se aplicada sob as mesmas regras da competição DIMACS, nossa solução teria garantido o primeiro lugar. Contribuições e Impactos: Este trabalho contribui para o desenvolvimento contínuo de soluções para o IRP, oferecendo uma abordagem eficiente e competitiva que pode inspirar futuras pesquisas e aplicações práticas no campo do gerenciamento de estoque e roteamento de veículos. / [en] Theme: This study investigates the Inventory Routing Problem (IRP) within the context of Vendor-Managed Inventory (VMI), a prevalent supply chain practice where suppliers assume responsibility for replenishment. The IRP, a combinatorial problem that has been widely studied for almost 40 years, encompasses three distinct subproblems: delivery scheduling, inventory management, and vehicle routing. Problem: Despite its age, the IRP continues to attract industry and academia attention. The recent 12th DIMACS Implementation Challenge dedicated a track to the IRP, and among the commonly used benchmarks, 401 instances still lack optimal solutions, particularly in the challenging Large instance subset. Hypothesis and Justification: The HGS framework proposed by Vidal et al. (2012) emerged as a prominent tool used successfully by numerous teams in the competition. However, to the best of our knowledge, the HGS framework has not been tested for the IRP. This study proposes a method combining the HGS framework with an efficient local search strategy, namely NSIRP proposed by Diniz et al. (2020), to tackle the IRP. Methodology: We implemented the proposed method and compared its performance to 21 existing methods using the literature benchmarks. Summary of Results: Our approach identified 79 new Best Known Solutions (BKS) out of 1100 instances. If applied under the same rules as the DIMACS competition, our method would have secured the first place. Contributions and Impacts: This work contribute to the ongoing development of IRP methods, offering an efficient and competitive approach that may inspire further research and practical applications in the realm of inventory management and vehicle routing.

O tema de roteamento de veículos é de grande importância na literatura e tem sido amplamente estudada pela sua importância para muitas indústrias. Com a evolução na literatura, mais características foram adicionadas para torná-lo mais próximo de situações reais. Alinhado com esta tendência, este trabalho aborda o problema de roteamento de veículos quando há a terceirização da frota que realiza as entregas. Uma forma de cobrança do frete é por meio de custos escalonados, que são calculados de acordo com o tipo de veículo e a distância percorrida, com valores fixos para cada faixa de distância. Embora seja uma forma comum de trabalho na indústria, nenhum trabalho focado nesta característica foi encontrado na literatura. Este problema é o problema de roteamento de veículos com frota mista, janelas de tempo e custos escalonados (FSMVRPTWSC). Ao abordar este problema, este trabalho apresenta um modelo de programação linear inteira mista que é avaliado em um cenário real da indústria. Além disso, três heurísticas de inserção sequencial são propostas para lidar com problemas maiores. Estes métodos são examinados por meio de testes computacionais em 168 problemas de referência gerados para este problema. Os experimentos numéricos mostram que os métodos são robustos e eficientes, apresentando um bom desempenho em conjuntos de problemas com diversas características. / The theme of vehicle routing is of great importance in the literature and has been widely studied for its relevance to many industries and, throughout the literature, more characteristics have been added to make it closer to real situations. Aligned with this trend, this paper addresses the vehicle routing problem when there is outsourcing of the fleet that delivers goods. One form of freight charging is by scaled costs, which are calculated according to the type of vehicle and the distance traveled, with fixed values for each distance range. Though it is a common form of work in the industry, no work focused on this characteristic was found in the literature. This problem is the fleet size and mix vehicle routing problem with time windows and scaled costs (FSMVRPTWSC). In approaching this problem, this paper presents a mixed integer linear programming model that is evaluated under a real situation scenario. Furthermore, three sequential insertion heuristics are proposed in order to deal with larger problems. These methods are examined through a computational comparative study in 168 benchmark problems generated for this problem. The numerical experiments show that the methods are robust and efficient, performing well in different problem sets.

Submitted by JOSIANE SANTOS DE OLIVEIRA (josianeso) on 2018-01-31T14:48:27Z No. of bitstreams: 1 Roberto da Silva Araujo_.pdf: 903723 bytes, checksum: ae702a685139c36126c0bfef5f707282 (MD5) / Made available in DSpace on 2018-01-31T14:48:27Z (GMT). No. of bitstreams: 1 Roberto da Silva Araujo_.pdf: 903723 bytes, checksum: ae702a685139c36126c0bfef5f707282 (MD5) Previous issue date: 2017-10-31 / Nenhuma / Neste trabalho é apresentado um Algoritmo Híbrido (AH) aplicado ao Problema de Roteamento de Veículos com Múltiplos Depósitos e Frota Heterogênea (PRVMDFH). Um conjunto de clientes é atendido por um número fixo de veículos de diferentes tamanhos, por múltiplos depósitos, sujeito a restrições da capacidade do veículo. As meta-heurísticas utilizadas na construção do AH são o Algoritmo Genético (AG) e a Busca Tabu (BT). O AG usa operadores de cruzamento Mapeado Parcialmente (PMX), Cromossomo de Duas Partes (TCX) e de Ordem (OX), o operador de mutação Troca e o Algoritmo de Busca Local (ABL). A BT usa os métodos de Troca, Retirada e Inserção e Deslocamento. São analisadas as políticas de diversificação no ABL e a intensificação com as estratégias de geração de vizinhança na BT. São utilizados conjuntos de dados padrões de problemas testes, para executar os algoritmos propostos. Os resultados obtidos, comparados a outros autores, apresentaram boas soluções para diferentes tamanhos de problemas testes. / This paper presents a Hybrid Algorithm (AH) applied to the Problem of Vehicle Routing with Multiple-Deposit and Heterogeneous Fleet (MDFHPRV). A number of customers are served with a fixed number of vehicles of different sizes by multi-depot, subject to capacity constraints of the vehicle. The meta-heuristics used in AH construction are Genetic Algorithm (GA) and Tabu Search (BT). The AG uses Partial Mapped Crossover (PMX), Two Part Chromosome Crossover (TCX) and Order Crossover (OX) operators, the Exchange mutation operator, and the Local Search Algorithm (ABL). BT uses the Exchange, Retrieve, and Insertion and Displacement methods. Diversification policies was analyzed in the ABL and the intensification with the neighborhood generation strategies in BT. Standard sets of test problems are used to execute the proposed algorithms. The obtained results, compared to other authors, presented good solutions for different sizes of test problems.

Made available in DSpace on 2014-12-17T15:48:00Z (GMT). No. of bitstreams: 1 GustavoAS_DISSERT.pdf: 3060399 bytes, checksum: 659289bc757f2443a1b6902094747b13 (MD5) Previous issue date: 2012-02-27 / This work approaches the Scheduling Workover Rigs Problem (SWRP) to maintain the wells of an oil field, although difficult to resolve, is extremely important economical, technical and environmental. A mathematical formulation of this problem is presented, where an algorithmic approach was developed. The problem can be considered to find the best scheduling service to the wells by the workover rigs, taking into account the minimization of the composition related to the costs of the workover rigs and the total loss of oil suffered by the wells. This problem is similar to the Vehicle Routing Problem (VRP), which is classified as belonging to the NP-hard class. The goal of this research is to develop an algorithmic approach to solve the SWRP, using the fundamentals of metaheuristics like Memetic Algorithm and GRASP. Instances are generated for the tests to analyze the computational performance of the approaches mentioned above, using data that are close to reality. Thereafter, is performed a comparison of performance and quality of the results obtained by each one of techniques used / O trabalho em quest?o aborda o Problema da Programa??o das Sondas de Produ??o (PPSP) para atender os po?os de um campo de petr?leo. Embora de dif?cil resolu??o, ele ? de extrema import?ncia econ?mica, t?cnica e ambiental. Uma formula??o matem?tica deste problema ? apresentada, assim como desenvolvida uma abordagem algor?tmica. O problema abordado pode ser considerado como o de encontrar o melhor escalonamento de atendimento aos po?os pelas sondas, levando em considera??o a minimiza??o da composi??o dos custos relativos ?s sondas e da perda total da produ??o de petr?leo associada aos po?os que est?o aguardando por atendimento. Tal problema assemelha-se ao Problema de Roteamento de Ve?culos (PRV), que ? classificado como pertencente ? classe de problemas NP-Dif?cil. O objetivo da presente pesquisa ? desenvolver uma abordagem algor?tmica para resolver o PPSP, utilizando os fundamentos de metaheur?sticas como o Algoritmo Mem?tico e o GRASP. Inst?ncias s?o geradas para a realiza??o dos testes computacionais para an?lise do desempenho das abordagens acima citadas, utilizando dados que se aproximam da realidade. A partir da?, ? realizada uma compara??o de desempenho e qualidade dos resultados obtidos por cada uma das t?cnicas utilizadas

Submitted by Izabel Franco (izabel-franco@ufscar.br) on 2016-10-06T17:59:08Z No. of bitstreams: 1 DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T13:51:08Z (GMT) No. of bitstreams: 1 DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T13:51:14Z (GMT) No. of bitstreams: 1 DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5) / Made available in DSpace on 2016-10-20T13:51:20Z (GMT). No. of bitstreams: 1 DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5) Previous issue date: 2016-03-21 / Não recebi financiamento / Vehicle routing problems occur in many practical situations where the pickup and/or delivery of goods is required. In this context, the present research aims to contribute to the study of logistic operations that arise in companies that deliver products on a regular basis to customers in densely populated urban areas. The problem consists in designing minimal cost daily routes serving the maximal number of customers. To this end, the crew of each vehicle comprise multiple deliverymen as means to reduce service times. Based on a case study in a drinks producer and distributor in the state of São Paulo, it is proposed a mixed integer linear programming model that comprise costs with own and chartered vehicles and the number of deliverymen, and various operational constraints such as time windows in customers, multiple daily trips, time limitations for the circulation of some vehicle types in specific areas, compatibility between vehicles and customers, maximum load in each vehicle, maximum route time and minimum load for the realization of a second trip. Results obtained by solving the model with real instances through exact (branch&cut), heuristic (constructive, local search, GRASP and Simulated Annealing) and hybrid (GRASP and branch&cut) approaches demonstrate the good quality of the generated solutions, and indicate the potential of application of some of these methods in practice. / Problemas de roteamento de veículos ocorrem em diversas situações práticas onde se faz necessária a distribuição e/ou coleta de produtos. Nesse contexto, a presente pesquisa visa o estudo das operações logísticas presentes em empresas que entregam produtos em base regular a clientes localizados em áreas urbanas de alta densidade demográfica. O problema consiste na obtenção de rotas de mínimo custo visando o atendimento do maior número de clientes da carteira diária. Para tal, a tripulação de cada veículo pode contemplar múltiplos entregadores para redução dos tempos de serviço. Com base em um estudo de caso em uma distribuidora de bebidas do interior do Estado de São Paulo, é proposto um modelo de programação linear inteira mista que considera custos com frota própria e fretada e com o número de entregadores, e diversas restrições operacionais, tais como janelas de tempo em clientes, múltiplas viagens diárias, limitações de horários de circulação de tipos de veículos, compatibilidade entre veículos e clientes, capacidade máxima de carga a ser transportada em cada veículo, tempo máximo de rota e carga mínima para realização da segunda viagem. Resultados da resolução do modelo para instâncias reais por meio de abordagens exatas (branch&cut), heurísticas (construtiva, busca local, GRASP e Simulated Annealing) e híbrida (GRASP e branch&cut), demonstram a boa qualidade das soluções geradas, e evidenciam o potencial de uso dessas metodologias na prática.

O tema de roteamento de veículos é de grande importância na literatura e tem sido amplamente estudada pela sua importância para muitas indústrias. Com a evolução na literatura, mais características foram adicionadas para torná-lo mais próximo de situações reais. Alinhado com esta tendência, este trabalho aborda o problema de roteamento de veículos quando há a terceirização da frota que realiza as entregas. Uma forma de cobrança do frete é por meio de custos escalonados, que são calculados de acordo com o tipo de veículo e a distância percorrida, com valores fixos para cada faixa de distância. Embora seja uma forma comum de trabalho na indústria, nenhum trabalho focado nesta característica foi encontrado na literatura. Este problema é o problema de roteamento de veículos com frota mista, janelas de tempo e custos escalonados (FSMVRPTWSC). Ao abordar este problema, este trabalho apresenta um modelo de programação linear inteira mista que é avaliado em um cenário real da indústria. Além disso, três heurísticas de inserção sequencial são propostas para lidar com problemas maiores. Estes métodos são examinados por meio de testes computacionais em 168 problemas de referência gerados para este problema. Os experimentos numéricos mostram que os métodos são robustos e eficientes, apresentando um bom desempenho em conjuntos de problemas com diversas características. / The theme of vehicle routing is of great importance in the literature and has been widely studied for its relevance to many industries and, throughout the literature, more characteristics have been added to make it closer to real situations. Aligned with this trend, this paper addresses the vehicle routing problem when there is outsourcing of the fleet that delivers goods. One form of freight charging is by scaled costs, which are calculated according to the type of vehicle and the distance traveled, with fixed values for each distance range. Though it is a common form of work in the industry, no work focused on this characteristic was found in the literature. This problem is the fleet size and mix vehicle routing problem with time windows and scaled costs (FSMVRPTWSC). In approaching this problem, this paper presents a mixed integer linear programming model that is evaluated under a real situation scenario. Furthermore, three sequential insertion heuristics are proposed in order to deal with larger problems. These methods are examined through a computational comparative study in 168 benchmark problems generated for this problem. The numerical experiments show that the methods are robust and efficient, performing well in different problem sets.

Made available in DSpace on 2015-04-11T14:02:47Z (GMT). No. of bitstreams: 1 Andre Ricardo Melo Araujo.pdf: 3722790 bytes, checksum: 1876d821e1e927795304f1c1ee7bbb67 (MD5) Previous issue date: 2013-03-01 / FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas / Wireless Sensor Network (WSN) is a special kind of ad hoc networks composed of devices capable of processing, storing, sensing the environment, and transmitting data via wireless communication interface. The sensor nodes have several limitations, among them the capacity of energy because to the reduced size. For this reason, many searches have been done with a view to improving the energy consumption of sensor nodes. This work aims to address the Problem of Coverage, Clustering and Routing with Mobile Sink (PCAR-SM, in portuguese Problema de Cobertura, Agrupamento e Roteamento com Sorvedouro Móvel) in WSN with mobile sink consisting of: given a set of sensor nodes and a monitoring area, develop algorithms to find the best subset of sensor nodes to cover the monitoring area, group them in a smaller number of clusters and find the shortest route to mobile sink navigate. The PCAR-SM is a strategy used to reduce the energy consumption of sensor nodes, data collisions, interference and redundant data in networks with high concentration of sensor nodes per area. The purpose of this paper is to solve each problem separately and together, in order to evaluate the impact of each problem on the other. The Coverage Problem has been solved with two metaheuristics: an Genetic Algorithm (GA) and a Greedy Randomized Adaptive Search Procedure (GRASP) algorithm. In the latter we used two representations of solution: (a) representation by sensor, where each element of the solution vector represents a sensor node that must be switched on or off; (b) representation by demand, where each element of the solution vector represents a demand point will indicate which sensor node cover it. The AG uses only the representation by demand. The computational results for Coverage Problem used the benchmark of Beasley s OR Library and it was possible seen that the GRASP with representation by demand achieved better results than the GA and the GRASP with representation by sensor when the optimization criterion is to minimize the total cost of each sensor node used in the solution. For Clustering Problem was created approach of virtual grids. In this approach, we divide the area into grids and clusters are formed by a set of adjacent grids (maximum 5 grids in group) forming a cross schematic. The aim of the problem is to minimize the number of clusters in the area. With this approach, we can model the Clustering Problem as a Set Cover Problem (SCP) without overlapping (an element does not belong to more than one set), which was treated by a greedy heuristic called Greedy Clustering Algorithm (GCA). The virtual grids proved to be a good solution because it is simple to identify a node which grid it belongs. Its simplicity also makes it a appropriate method for a distributed version. The Routing Problem of sink was modeled as the Travelling Salesman Problem (TSP), where the mobile sink part of a corner of the monitoring area, runs through the area visiting all clusters and returns to the starting point. For this, we propose two greedy approaches based on nearest neighbor, the Routing Greedy Algorithm - Center (RGA-C) and Routing Greedy Algorithm - Border (RGA-B). The route of the sink was also solved by a heuristic based on algorithm Centralized Spatial Partitioning (CSP). In CSP approach, the route is fixed and reminds the movement of a snake. The results show that fixed route produces a path with smaller size compared to the greedy heuristic for TSP. We analyze also the PCAR-SM, creating heuristic strategies. The union of the Clustering Problem and Routing Problem proved more beneficial in relation to the size of the sink s route. The union of Coverage Problem and Clustering Problem only proved beneficial when the communication radius was about 3,9 times greater than the sensing radius. Our results show that solve problems together allows some changes in the algorithms will lead to better results. / As Redes de Sensores Sem Fio (RSSFs) são um tipo especial de redes ad hoc constituídas por dispositivos capazes de processar, armazenar, sensoriar o ambiente e transmitir dados via interface de comunicação sem fio, denominados nós sensores. Os nós sensores possuem várias limitações, dentre elas, a capacidade de energia devido ao tamanho reduzido. Por isto, muitas pesquisas foram feitas tendo em vista a melhoria no consumo de energia dos nós sensores. Este trabalho tem como objetivo tratar o Problema de Cobertura, Agrupamento e Roteamento com Sorvedouro Móvel (PCAR-SM) em RSSF com nó sorvedouro móvel, que consiste em: dado um conjunto de nós sensores e uma área de monitoramento, desenvolver algoritmos para encontrar o melhor subconjunto de nós sensores que cubra a área de monitoramento, juntá-los no menor número de grupos possíveis e encontrar a menor rota para um nó sorvedouro móvel percorrer. O PCAR-SM é uma estratégia utilizada para diminuir o consumo de energia dos nós sensores, a colisão de dados, as interferências e os dados redundantes em redes com alta concentração de nós sensores por área. A proposta deste trabalho é resolver cada problema separadamente e em conjunto, de modo a avaliar o impacto de cada problema na solução do outro. O Problema de Cobertura foi resolvido com duas metaheurísticas: um Algoritmo Genético (AG) e um algoritmo Greedy Randomized Adaptive Search Procedure (GRASP). Neste último foram utilizadas duas representações de solução: (a) representação por sensor, onde cada elemento do vetor de solução representa um nó sensor que estará ligado ou desligado; (b) representação por demanda, onde cada elemento do vetor de solução representa um ponto de demanda no qual indicará qual o nó sensor o cobre. O AG utiliza apenas a representação por demanda. Os resultados computacionais para o Problema de Cobertura utilizaram o benchmark da Beasley s OR Library e foi possível constatar que o GRASP com representação por demanda obteve melhores resultados que o AG e o GRASP com representação por sensor quando o critério de otimização é minimizar a soma total dos custos de cada nó sensor utilizado na solução. Para o Problema de Agrupamento foi criada uma abordagem de grades virtuais. Nesta abordagem dividimos a área em grades e os grupos são formados por um conjunto de grades adjacentes (no máximo 5 grades) formando um esquema de cruz. O objetivo do problema é minimizar o número de grupos na área. A partir desta abordagem, pode-se modelar o Problema de Agrupamento como um Problema de Cobertura de Conjuntos (PCC) sem sobreposição (um elemento não pertence a mais de um conjunto), que foi tratada por uma heurística gulosa denominada Greedy Clustering Algorithm (GCA). Os grades virtuais provou ser uma boa solução por ser simples para um nó identificar a qual grade ele pertence. Sua simplicidade ainda o torna uma método adequado para uma versão distribuída. O Problema de Roteamento do nó sorvedouro foi modelado como o Problema do Caixeiro Viajante (PCV), onde o nó sorvedouro móvel parte de um canto da área de monitoramento, percorre a área visitando todos os grupos e retorna ao ponto inicial. Para isto, propomos duas abordagens gulosas baseadas no vizinho mais próximo, o Routing Greedy Algorithm - Center (RGA-C) e o Routing Greedy Algorithm - Border (RGA-B). A rota do nó sorvedouro também foi resolvida por uma heurística baseada no algoritmo Centralized Spatial Partitioning (CSP). Na abordagem CSP, a rota é fixa e lembra o movimento de uma cobra. Os resultados mostram que a rota fixa gera um percurso com tamanho menor em comparação com as heurísticas gulosas para o PCV. Analisamos, ainda, o PCAR-SM, criando estratégias heurísticas. Aunião dos Problema de Agrupamento e Roteamento, provou ser mais benéfica em relação ao tamanho da rota do nó sorvedouro, já a união do Problema de Cobertura com o Problema de Agrupamento só mostrou ser benéfica quando o raio de comunicação era aproximadamente 3, 9 vezes maior que o raio de sensoriamento. Nossos resultados, mostram que resolver os problemas em conjunto permite que algumas mudanças nos algoritmos levem a melhores resultados.

Submitted by Franciele Moreira (francielemoreyra@gmail.com) on 2017-10-20T16:09:47Z No. of bitstreams: 2 Dissertação - Lorrany Cristina da Silva - 2017.pdf: 8394886 bytes, checksum: 9cc1461b937a65a8c50964b3dea86623 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-10-23T10:05:52Z (GMT) No. of bitstreams: 2 Dissertação - Lorrany Cristina da Silva - 2017.pdf: 8394886 bytes, checksum: 9cc1461b937a65a8c50964b3dea86623 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-10-23T10:05:52Z (GMT). No. of bitstreams: 2 Dissertação - Lorrany Cristina da Silva - 2017.pdf: 8394886 bytes, checksum: 9cc1461b937a65a8c50964b3dea86623 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-06-28 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Three different integer linear programming models for the Vehicle Routing Problem with Two-dimensional Loading Constraints are developed in this work. The version of the problem studied considers that the unloading of the rectangular items can respect or not the sequence of the clients visited on the route, that is, we solve the sequential and unrestricted versions of the problem. The first model deals with the problem completely, that is, with all constraints inserted at once. The second and third models are based, respectively, on a three- and two-index formulation. Separation routines are considered to detect violated inequalities related with packing on the second and third models, while the third model also considers cuts on connectivity and capacity. Computational experiments were carried out over instances of the literature with the quantity of customers ranging from 15 to 36 and items from 15 to 114, besides to consider the cases in which the cost of traversing an edge is integer and real. The models with cuts on demand were better in relation to the first model, besides being competitive when comparing with the results fromthe literature. The first model solved 4 of the 80 instances, the three-index model solved 7 and, the two-index model solved 53. On the sequential version, the adopted model solved 33 instances for the case with integer costs (and 37 for the case with real costs). In comparing with a recent heuristic from the literature, the best model was capable of tying in 48 instances in the unrestricted version and 24 in the sequential version. / Neste trabalho desenvolvem-se três modelos de programação linear inteira para o Problema de Roteamento de Veículos com Restrições de Empacotamento Bidimensional. A versão do problema estudado considera que o descarregamento dos itens retangulares pode respeitar (ou não) a sequência de clientes visitados na rota, ou seja, resolve-se as versões sequencial e irrestrita do problema. O primeiro modelo trata do problema de forma completa, isto é, com todas as restrições inseridas de uma só vez. O segundo e o terceiro modelo são baseados, respectivamente, em uma formulação de três e dois índices. Rotinas de separação são consideradas para detectar desigualdades violadas de empacotamento no segundo e no terceiro modelo, enquanto o último modelo considera também cortes de conectividade e capacidade. Experimentos computacionais foram realizados em instâncias da literatura com número de clientes variando de 15 a 36 e itens de 15 até 114, além de considerar os casos em que o custo da aresta é inteiro ou real. Os modelos com cortes sob demanda foram melhores em relação ao primeiro modelo, além de serem competitivos quando comparado com a literatura. O modelo completo encontrou a solução ótima em 4 das 80 instâncias, o modelo de três índices 7 e o modelo de dois índices 53. Na versão sequencial, o modelo adotado resolveu 33 instâncias para o custo inteiro (e 37 para o custo real). Na comparação com uma heurística recente da literatura, o melhor modelo conseguiu empatar em 48 instâncias na versão irrestrita e em 24 na versão sequencial.

[pt] A Petrobras, maior empresa de óleo e gás do Brasil e uma das maiores do mundo, possui mais de 94 porcento da sua produção proveniente de campos offshore. Na região Sudeste o transporte dos trabalhadores para as unidades marítimas de exploração e produção é realizado por modal aéreo, através de helicópteros afretados de médio a grande porte. Para atender ao grande número de voos, a Petrobras possui uma central de planejamento e programação de voos, cujo objetivo é construir escalas de atendimento eficientes, em relação ao uso de recursos e ao nível de serviço. Um dos desafios enfrentados é gerar, manualmente, programações dos voos em situações de ruptura do atendimento, como por exemplo quando ocorre interrupção de pousos e decolagens devido a condições meteorológicas adversas (exigindo que os voos sejam programados para horários posteriores aos previamente planejados). Nessa dissertação de mestrado, é proposta uma abordagem de programação estocástica para gerar a programação de voos offshore ótima do ponto de vista do nível de serviço, reduzindo os atrasos esperados nos voos. Considerando a característica combinatória dos problemas de agendamento, utilizou-se o método de Aproximação pela Média Amostral (SAA) para gerar os cenários do modelo de programação estocástica. Um modelo de Simulação de Eventos Discretos também foi desenvolvido para avaliar o nível de serviço das programações de voos geradas. Os resultados numéricos indicam que a abordagem estocástica pode reduzir atrasos imprevisíveis, que causam grande impacto nos passageiros e na cadeia de suprimentos. / [en] Petrobras, the largest oil and gas company in Brazil and one of the largest in the world, has more than 94 percent of its production from offshore fields. In the Southeast region, workers are transported to offshore exploration and production units by air, using medium size to large size chartered helicopters. To serve the large number of flights, Petrobras has a flight planning and scheduling center, with the objective of building efficient service scales, related to the use of resources and the level of service. One of the challenges faced is to generate, manually, flight schedules in situations of disruption of service, such as when there is an interruption of landings and takeoffs due to adverse weather conditions (requiring that flights be scheduled for times after those previously planned). In this master s thesis, a stochastic programming approach is proposed to generate the optimal offshore flight schedule from the service level point of view, reducing expected flight delays. Considering the combinatorial characteristic of scheduling problems, the Sample Average Approximation (SAA) method was used to generate the scenarios of the stochastic programming model. A Discrete Event Simulation model was also developed to evaluate the service level of the generated flight schedules. The numerical results indicate that the stochastic approach can reduce unpredictable delays, which have a major impact on passengers and the supply chain.

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