The efficient organization of waste collection systems based on bins located along the streets involves the solution of several tactical optimization problems. In particular, the bin configuration and sizing at each collection site as well as the service frequency over a given planning horizon have to be decided. In this context, a higher service frequency leads to higher routing costs, but at the same time less or smaller bins are required, which leads to lower bin allocation investment costs. The bins used have different types and different costs and there is a limit on the space at each collection site as well as a limit on the total number of bins of each type that can be used. In this paper we consider the problem of designing a collection system consisting of the combination of a vehicle routing and a bin allocation problem in which the trade-off between the associated costs has to be considered. The solution approach combines an effective variable neighborhood search metaheuristic for the routing part with a mixed integer linear programming-based exact method for the solution of the bin allocation part. We propose hierarchical solution procedures where the two decision problems are solved in sequence, as well as an integrated approach where the two problems are considered simultaneously. Extensive computational testing on synthetic and real-world instances with hundreds of collection sites shows the benefit of the integrated approaches with respect to the hierarchical ones.

We present a hybrid optimization algorithm for mixed-integer linear programming, embedding both heuristic and exact components. In order to validate it we use the periodic vehicle routing problem (PVRP) as a case study. This problem consists of determining a set of minimum cost routes for each day of a given planning horizon, with the constraints that each customer must be visited a required number of times (chosen among a set of valid day combinations), must receive every time the required quantity of product, and that the number of routes per day (each respecting the capacity of the vehicle) does not exceed the total number of available vehicles. This is a generalization of the well-known vehicle routing problem (VRP). Our algorithm is based on the linear programming (LP) relaxation of a set-covering-like integer linear programming formulation of the problem, with additional constraints. The LP-relaxation is solved by column generation, where columns are generated heuristically by an iterated local search algorithm. The whole solution method takes advantage of the LP-solution and applies techniques of fixing and releasing of the columns as a local search, making use of a tabu list to avoid cycling. We show the results of the proposed algorithm on benchmark instances from the literature and compare them to the state-of-the-art algorithms, showing the effectiveness of our approach in producing good quality solutions. In addition, we report the results on realistic instances of the PVRP introduced in Pacheco et al. (2011) [24] and on benchmark instances of the periodic traveling salesman problem (PTSP), showing the efficacy of the proposed algorithm on these as well. Finally, we report the new best known solutions found for all the tested problems. (authors' abstract)

Dans ce travail nous considérons des problèmes de planification de production sur plusieurs sites avec transport de produits entre ces sites. L’objectif est de synchroniser les deux problèmes (planification et transport) et de construire une solution globale. Le système de production sur chaque site est modélisé comme un problème de Capacitated Lot-Sizing où nous travaillons avec stock et ressources. Le transport de produits entre les sites se ramène à une version simplifiée du Vehicle Routing Problem où le temps est discrétisé. D’abord nous proposons un modèle linéaire en nombres entiers que nous appelons le « Lot-Sizing and Vehicle Routing Problem » (LSVRP). Puis nous présentons deux cas particuliers : le Single-item LSVRP (SLSVRP) et le Single-level LSVRP (1-LSVRP). Les problèmes sont traités ici par six heuristiques que nous avons développé. Quatre de ces méthodes sont des heuristiques qui utilisent la programmation en nombres entiers et prennent en compte la relaxation linéaire de quelques variables du problème. Elles s’appuient sur l’exploration partielle de l’arbre de décision et la fixation de variables. Les deux autres sont spécifiques pour les cas particuliers. La première, qui traite le S-LSVRP, est basée sur la propagation des ordres de production sur chaque site. Puis à chaque itération elle calcule le plan de transport compatible et essaie d’améliorer la solution en modifiant la production sur les sites. L’autre méthode consiste en une relaxation lagrangienne qui travaille sur une modélisation du 1-LSVRP en un problème de flot. Des résultats numériques et des analyses sont présentés pour évaluer l’efficacité de ces heuristiques. / In this work we consider some problems of scheduling both a production distributed on several sites and the transportation of items between those sites. By doing so, the objective is to synchronize the two components and to build a better overall solution. The production system on each site is modeled as a Capacitated Lot-Sizing Problem where stock both on resources and produced items is available. The inter-site items transportation is a simplified version of the Vehicle Routing Problem where time is discretized. We first propose a mixed integer linear programming formulation that we call “The Lot-Sizing and Vehicle Routing Problem” (LSVRP). Then we present two particular cases : The Single-item LSVRP (S-LSVRP) and The Single-level LSVRP (1-LSVRP). All those cases are treated here by the six heuristics we develloped. Four of those methods are MIP based heuristics and take in account the the linear relaxation of some variables of the problem. They rely on partial decision tree exploration along with variable fixing. The other two are specifics for the two particular cases. The one who treats the S-LSVRP is based on production order propagation over the sites. Then, at each iteration, it computes a compatible transportation schedule and it tries to improve the solution by modifying the production on the sites. The other method consists in a lagrangian relaxation that works with an adaptation of the 1-LSVRP into a flow problem. Computational results and analysis are presented to evaluate the efficiency of those heuristics.

Nesta tese apresentamos duas estratégias para resolver o problema de job-shop flexível com o objetivo de minimizar o makespan. A primeira estratégia utiliza um algoritmo branch and cut (B&C) e a segunda abordagens matheuristics. O algoritmo B&C utiliza novas classes de inequações válidas, originalmente formulada para o problema de job-shop e estendida para o problema em questão. Para que as inequações válidas sejam eficientes, o modelo proposto por Birgin et al, (2014) (A milp model for an extended version of the fexible job shop problem. Optimization Letters, Springer, v. 8, n. 4, 1417-1431), é reformulado (MILP-2). A segunda estratégia utiliza as matheuristcs local branching e diversification, refining and tight-refining. Os experimentos computacionais mostraram que a inclusão dos planos de corte melhoram a relaxação do modelo MILP-2 e a qualidade das soluções. O algoritmo B&C reduziu o gap e o número de nós explorados para uma grande quantidade de instâncias. As abordagens matheuristics tiveram um excelente desempenho. Do total de 59 instâncias analisadas, somente em 3 problemas a resolução do modelo MILP-1 obteve melhores resultados do que as abordagens matheuristcs / This thesis proposes two approaches to solve the flexible job-shop scheduling problem to minimize the makespan. The first strategy uses a branch and cut algorithm (B&C) and the second approach is based on matheuristics. The B&C algorithm uses new classes of valid inequalities, originally formulated for job-shop scheduling problems and extended to the problem at hand. The second approach uses the matheuristics local branching and diversification, refining and tight-refining. For all valid inequalities to be effective, the precedence variable based model proposed by Birgin et al, (2014) (A milp model for an extended version of the fexible job shop problem. Optimization Letters, Springer, v. 8, n. 4, 1417-1431), is reformulated (MILP-2). The computational experiments showed that the inclusion of cutting planes tightened the linear programming relaxations and improved the quality of solutions. B&C algorithm reduced the gap value and the number of nodes explored in a large number of instances. The matheuristics approaches had an excellent performance. From 59 instances analized, MILP-1-Gurobi showed better results than matheuristics approaches in only 3 problems

L’interconnexion croissante dans les systèmes de transports a conduit à la modélisation de nouvelles contraintes, dites contraintes de synchronisation, dans les problèmes de tournées de véhicules. Dans cette thèse, nous nous intéressons à deux cas dans lesquels ce type de problématiques apparaît. Dans un premier temps, nous proposons une méthode heuristique pour un problème à deux échelons rencontré pour la distribution de marchandises en ville. Dans un second temps, nous étudions l’intégration d’un cross-dock dans des tournées de collectes et livraisons. Une première contribution à ce sujet concerne le problème de tournées de véhicules avec cross-docking, et une seconde contribution intègre, en plus, des contraintes de ressources au cross-dock dans le problème de routage. Une méthode pour un problème de chargement 3D, étudié lors d’un stage doctoral en entreprise, est également présentée. / Transportation systems are more and more interconnected, this has lead to a new kind of constraints, called synchronization constraints, in vehicle routing problems. In this thesis, we study two cases in which this type of constraints arises. First, we propose a heuristic method for a two-echelon problem arising in City Logistics. Second, we study the integration of a cross-dockin pickup and delivery vehicle routing problems. To that end we propose a matheuristic for the vehicule routing problem with cross-docking, and we propose an extension of this problem that integrates specific resource synchonization constraints arising at the cross-dock. A method for a 3D loading problem is also presented.

Nesta tese apresentamos duas estratégias para resolver o problema de job-shop flexível com o objetivo de minimizar o makespan. A primeira estratégia utiliza um algoritmo branch and cut (B&C) e a segunda abordagens matheuristics. O algoritmo B&C utiliza novas classes de inequações válidas, originalmente formulada para o problema de job-shop e estendida para o problema em questão. Para que as inequações válidas sejam eficientes, o modelo proposto por Birgin et al, (2014) (A milp model for an extended version of the fexible job shop problem. Optimization Letters, Springer, v. 8, n. 4, 1417-1431), é reformulado (MILP-2). A segunda estratégia utiliza as matheuristcs local branching e diversification, refining and tight-refining. Os experimentos computacionais mostraram que a inclusão dos planos de corte melhoram a relaxação do modelo MILP-2 e a qualidade das soluções. O algoritmo B&C reduziu o gap e o número de nós explorados para uma grande quantidade de instâncias. As abordagens matheuristics tiveram um excelente desempenho. Do total de 59 instâncias analisadas, somente em 3 problemas a resolução do modelo MILP-1 obteve melhores resultados do que as abordagens matheuristcs / This thesis proposes two approaches to solve the flexible job-shop scheduling problem to minimize the makespan. The first strategy uses a branch and cut algorithm (B&C) and the second approach is based on matheuristics. The B&C algorithm uses new classes of valid inequalities, originally formulated for job-shop scheduling problems and extended to the problem at hand. The second approach uses the matheuristics local branching and diversification, refining and tight-refining. For all valid inequalities to be effective, the precedence variable based model proposed by Birgin et al, (2014) (A milp model for an extended version of the fexible job shop problem. Optimization Letters, Springer, v. 8, n. 4, 1417-1431), is reformulated (MILP-2). The computational experiments showed that the inclusion of cutting planes tightened the linear programming relaxations and improved the quality of solutions. B&C algorithm reduced the gap value and the number of nodes explored in a large number of instances. The matheuristics approaches had an excellent performance. From 59 instances analized, MILP-1-Gurobi showed better results than matheuristics approaches in only 3 problems

[pt] No cenário atual da economia mundial, é essencial aumentar a integração entre os diferentes atores da cadeia de suprimentos das empresas, reduzindo custos operacionais e melhorando a eficiência. O roteamento de navios é parte imprescindível dessa integração no comércio marítimo global, sendo objeto de estudo de muitos autores. Neste trabalho, apresentamos diferentes metodologias para resolver variantes do Problema de Roteamento Marítimo com Estoques. Esse problema envolve um grande número de variáveis e é computacionalmente complexo de ser resolvido. Nossa principal motivação é resolver um caso real de roteamento de navios de uma grande empresa do setor de Óleo e Gás, obtendo soluções de alta qualidade em tempos computacionais plausíveis e melhorando os resultados atuais da empresa. Todas as metodologias desenvolvidas são baseadas em uma combinação de uma meta-heurística com um modelo matemático de programação linear. Uma das principais diferenças entre as metodologias está no modelo matemático para resolver o problema de estoque, onde testamos abordagens de tempo discreto e tempo contínuo. As outras diferenças dizem respeito ao número de produtos avaliados (único ou múltiplos produtos) e à meta-heurística usada (heurística de busca local com um fator de probabilidade de Simulated Annealing ou Hybrid Variable Neighborhood Search). Para a metodologia que utiliza um modelo de tempo discreto, os resultados são satisfatórios, com violações baixas e pontuais do estoque em um tempo computacional aceitável. Para a metodologia que utiliza um modelo de tempo contínuo, os resultados são ainda melhores, uma vez que, em reduzido tempo computacional, as violações de estoque permanecem baixas ou inexistentes, dependendo do cenário avaliado e da meta-heurística utilizada. Os resultados obtidos neste trabalho são notáveis e permitem sua aplicação prática em casos reais. / [en] In the current scenario of the world economy, it is essential to increase the integration between the different players in the companies supply chain, reducing operational costs, and improving efficiency. Ship routing is a substantial part of this integration regarding global maritime commerce, being the object of study by many authors. In this work, we present different methodologies to solve variants of the Maritime Inventory Routing Problem. This problem involves a large number of variables and is a computationally complex problem to solve. Our primary motivation is to solve a ship routing real case of a large company in the Oil and Gas sector, achieving high-quality solutions in plausible processing times and improving companies current results. All developed methodologies are based on a metaheuristic combination with a linear mathematical model. One of the main differences between the methodologies lies in the mathematical model to solve the inventory problem, where we tested discrete-time and continuous-time approaches. Other differences concern the number of evaluated products (single or multi-product) and the metaheuristic used (local search heuristics with a Simulated Annealing probability factor or Hybrid Variable Neighborhood Search). For the methodology using the discretetime model, the results are satisfactory, with low and punctual inventory violations in an acceptable computational time. For the methodology using the continuous-time model, the results are better once, in reduced computational time, inventory violations remain low or non-existent, depending on the scenario evaluated and the metaheuristic used. The results obtained in this work are remarkable and allow its practical application for real cases.

[pt] A exploração e produção (EeP) offshore de óleo e gás envolve várias operações complexas e importantes, como perfuração, avaliação, completação e manutenção de poços. A maioria dessas tarefas requer o uso de sondas, um recurso custoso e escasso que as companhias de petróleo precisam planejar e programar corretamente. Na literatura, este problema é chamado de Programação de Sondas. Todavia, existem poucos estudos relacionados aos poços marítimos e às atividades de perfuração e nenhum destes com funções objetivo e restrições realistas, como orçamento. Por isso, muitas empresas de petróleo têm fortes dificuldades no planejamento das sondas, resultando em grandes custos para elas. Com o objetivo de preencher essa lacuna, esta dissertação estuda um problema de programação de sondas em uma empresa petroleira e propõe um método híbrido para determinar a frota de sondas e seu cronograma, que minimize o orçamento da empresa. Dois modelos de programação matemática – um para minimização das sondas e outro para minimizar seu orçamento com variações da unidade de tempo utilizada (dia ou semana) – e várias heurísticas – usando algoritmos de busca local e variable neighborhood descent (VND) com três estruturas de vizinhança e duas estratégias de busca (first e best improvemment) e métodos construtivos- foram desenvolvidos e testados em duas instâncias (uma pequena e uma grande), baseadas em dados reais da empresa do caso de estudo. As três estruturas de vizinhanças são baseadas em movimentos de insert, uma delas não permite alterar as datas de alocação das tarefas na solução inicial, outra permite adiar tarefas e a última as posterga.Os resultados indicaram a dificuldade no desempenho dos modelos matemáticos nas grandes instâncias e uma forte capacidade das heurísticas para encontrar soluções similares com muito menos esforço computacional. Na instância pequena, o modelo exato para minimizar o orçamento encontrou soluções um pouco melhores que a heurística (diferença de entre 0,4 por cento e 5,6 por cento), embora necessitando de mais esforço computacional, principalmente os modelos com unidades de tempo em dias. Porém, na instância maior, as soluções da programação matemática possuíram altos gap (mais de 11 por cento) e altos tempos computacionais (pelo menos 12 horas), tendo o modelo matemático mais completo sido incapaz de encontrar soluções inteiras viáveis ou limites inferiores depois de mais de um dia rodando. Enquanto isso, as heurísticas foram capazes de encontrar soluções similares ou até melhores (desvios de -6 por cento e 14 por cento em relação a melhor solução exata) em um tempo muito menor, tendo 70 das 156 heurísticas desenvolvidas superado os modelos matemáticos. Além disso, os melhores resultados heurísticos foram utilizando algoritmos de variable neighborhood descent (VND) com estruturas de vizinhanças que realizavam movimentos de insert de tarefas em sondas existentes ou novas e permitiam postergar ou adiantar as tarefas das sondas. A abordagem hibrida foi comparada também com uma abordagem puramente heurística, tendo a primeira obtido melhores resultados. Por fim, os resultados demonstram que o método híbrido proposto combinando o modelo matemático que minimiza o número de sondas com as heurísticas de busca local é uma ferramenta de suporte a decisão rápida e prática, com potencial para reduzir milhões de dólares para as empresas petroleiras do mercado offshore, com capacidade para encontrar cronogramas próximos da solução ótima com pouco esforço computacional, mesmo em instâncias grandes onde a maioria dos métodos exatos é muito complexa e lenta. / [en] The offshore exploration and production (EandP) of Oil and Gas involves several complex and important operations and relies, mostly, in the use of rigs, a scarce and costly resource that oil companies need to properly plan and schedule. In the literature, this decision is called the Rig Scheduling Problem (RSP). However, there is not any study related to offshore wells and drilling activities with realistic objective functions. Aiming to fulfill this gap, this dissertation studies a rig scheduling problem of a real offshore company and proposes a matheuristic approach to determine a rigs fleet and schedule that minimizes the budget. Two mathematical models – one for rigs fleet minimization and another one that minimizes the rigs budget – and several heuristics – using local search (LS) and variable neighborhood descent (VND) algorithms with three neighborhood structures and also constructive methods – were developed and tested in two instances based on real data of the studied company. In the small instance, the programming model found slightly better solutions than the heuristic, despite requiring more computational effort. Nevertheless, in the large instance, the mathematical programming solutions present large gaps (over 11 percent) and an elevated computational time (at least 12 hours), while the heuristics can find similar (or even better) solutions in a shorter time (minutes), having 70 of 156 heuristics outperformed the mathematical models. Last, the matheuristic combination of the simplest mathematical model with the heuristics has found the best known solutions (BKS) of the large instance with a moderate computational effort.

A geração de quadros de horários escolares é um problema clássico de otimização que tem sido largamente estudado devido a sua importâncias prática e teórica. O problema consiste em alocar um conjunto de aulas entre professor-turma em períodos de tempo pré-determinados, satisfazendo diferentes tipos de requisitos. Devido a natureza combinatória do problema, a resolução de instâncias médias e grandes torna-se uma tarefa desafiadora. Quando recursos são escassos, mesmo uma solução factível pode ser difícil de ser encontrada. Várias técnicas tem sido propostas na literatura científica para resolver o problema de geração de quadros de horários escolares, no entanto, métodos robustos ainda não existem. Visto que o uso de métodos exatos, como por exemplo, técnicas de programação matemática, não podem ser utilizados na prática, para resolver instâncias grandes da realidade, meta-heurísticas e meta-heurísticas híbridas são usadas com frequência como abordagens de resolução. Nesta pequisa, são desenvolvidas técnicas que combinam programação matemática e heurísticas, denominadas mateheurísticas, para resolver de maneira eficiente e robusta algumas variações de problemas de geração de quadros de horários escolares. Embora neste trabalho sejam abordados problemas encontrados no contexto de instituições brasileiras, os métodos propostos também podem ser aplicados em problemas similares oriundo de outros países. / The school timetabling is a classic optimization problem that has been extensively studied due to its practical and theoretical importance. It consists in scheduling a set of class-teacher meetings in a prefixed period of time, satisfying requirements of different types. Given the combinatorial nature of this problem, solving medium and large instances of timetabling to optimality is a challenging task. When resources are tight, it is often difficult to find even a feasible solution. Several techniques have been developed in the scientific literature to tackle the high school timetabling problem, however, robust solvers do not exist yet. Since the use of exact methods, such as mathematical programming techniques, is considered impracticable to solve large real world instances, metaheuristics and hybrid metaheuristics are the most used solution approaches. In this research we develop techniques that combine mathematical programming and heuristics, so-called matheuristics, to solve efficiently and in a robust way some variants of the high school timetabling problem. Although we pay special attention to problems arising in Brazilian institutions, the proposed methods can also be applied to problems from different countries.

A geração de quadros de horários escolares é um problema clássico de otimização que tem sido largamente estudado devido a sua importâncias prática e teórica. O problema consiste em alocar um conjunto de aulas entre professor-turma em períodos de tempo pré-determinados, satisfazendo diferentes tipos de requisitos. Devido a natureza combinatória do problema, a resolução de instâncias médias e grandes torna-se uma tarefa desafiadora. Quando recursos são escassos, mesmo uma solução factível pode ser difícil de ser encontrada. Várias técnicas tem sido propostas na literatura científica para resolver o problema de geração de quadros de horários escolares, no entanto, métodos robustos ainda não existem. Visto que o uso de métodos exatos, como por exemplo, técnicas de programação matemática, não podem ser utilizados na prática, para resolver instâncias grandes da realidade, meta-heurísticas e meta-heurísticas híbridas são usadas com frequência como abordagens de resolução. Nesta pequisa, são desenvolvidas técnicas que combinam programação matemática e heurísticas, denominadas mateheurísticas, para resolver de maneira eficiente e robusta algumas variações de problemas de geração de quadros de horários escolares. Embora neste trabalho sejam abordados problemas encontrados no contexto de instituições brasileiras, os métodos propostos também podem ser aplicados em problemas similares oriundo de outros países. / The school timetabling is a classic optimization problem that has been extensively studied due to its practical and theoretical importance. It consists in scheduling a set of class-teacher meetings in a prefixed period of time, satisfying requirements of different types. Given the combinatorial nature of this problem, solving medium and large instances of timetabling to optimality is a challenging task. When resources are tight, it is often difficult to find even a feasible solution. Several techniques have been developed in the scientific literature to tackle the high school timetabling problem, however, robust solvers do not exist yet. Since the use of exact methods, such as mathematical programming techniques, is considered impracticable to solve large real world instances, metaheuristics and hybrid metaheuristics are the most used solution approaches. In this research we develop techniques that combine mathematical programming and heuristics, so-called matheuristics, to solve efficiently and in a robust way some variants of the high school timetabling problem. Although we pay special attention to problems arising in Brazilian institutions, the proposed methods can also be applied to problems from different countries.