Nas últimas décadas, diversas propostas de técnicas e de processos visando aumentar a sustentabilidade da agricultura ganharam evidência. Tais propostas geram novos modelos de planejamento em que devem ser considerados aspectos técnicos e ecológicos de produção, bem como o acesso de pequenos agricultores familiares ao mercado consumidor. Neste tipo de planejamento da produção, a rotação de culturas desempenha um papel fundamental, pois contribui para a manutenção dos recursos produtivos, para a minimização do uso de recursos não-renováveis e para o controle biológico da população de herbívoros, patógenos e plantas espontâneas. Nesta tese abordamos dois problemas de Programação de Rotação de Culturas (PRC) focados na produção de base sustentável de hortaliças: o problema de PRC com restrições de Adjacências (PRC-A) e o problema de PRC com atendimento da Demanda (PRC-D). O planejamento da produção de hortaliças é complexo pois envolve, em geral, um grande número de culturas com limitações específicas quanto à época de plantio e com períodos de cultivo e produtividades muito variáveis. A programação de rotação de culturas para as áreas de plantio é formulada como um modelo de otimização 01 e, para os dois problemas, em cada programação considera se tanto aspectos técnicos (época de plantio e colheita etc.) quanto ecológicos (adubação verde, pousio etc.). No problema PRC-A o objetivo é a maximização da ocupação das áreas produtivas em que as restrições de plantio são estendidas às áreas adjacentes. Como a formulação matemática para o problema tem, em geral, um número muito grande de restrições e variáveis, com matriz de restrições esparsa e bloco-diagonal, o modelo é reformulado com a Decomposição DantzigWolfe, o que permitiu sua resolução por procedimentos baseados em geração de colunas, heurísticos e exatos. No problema PRC-D desejase suprir a demanda de um conjunto de hortaliças tendo-se disponível um conjunto de áreas heterogêneas. As culturas passíveis de plantio, bem como as suas produtividades, dependem da área considerada. O problema foi formulado como um modelo de otimização linear em que cada variável está associada a uma programação de rotação de culturas. O modelo contém potencialmente um número grande de programações de rotação e é resolvido por geração de colunas. Experimentos computacionais usando instâncias baseadas em dados reais confirmam a eficácia dos modelos e das metodologias propostos para os problemas / Over the last decades, various proposals for techniques and processes to increase agricultural sustainability have been put forward. These proposals bring new planning models in which technical and ecological production aspects must be considered, as well as the access of small farmers to the consumer market. In this type of agricultural production planning, crop rotation plays a fundamental role as it contributes to maintaining productive resources, to reducing the use of non-renewable resources, and to biologically controlling the population of herbivores, pathogens and spontaneous plants. In this thesis, two problems concerning the Crop Rotation Schedule (CRS) focusing on sustainable production vegetables are addressed: the problem of the CRS having Adjacent constraints (CRS-A) and the problem of the CRS under Demand constraints (CRS-D). Production planning of vegetables is complex as it generally involves a large number of crop species having specific limitations regarding the planting season and very varied production times and productivity. The crop rotation schedule problem is formulated as an optimization model 0-1, and for both problems, in each schedule technical (planting and harvesting season etc.) and ecological (green manure, fallow etc.) aspects are considered. Concerning the CRS-A problem, the aim is to maximize the occupation of cropping areas in which planting constraints are extended to adjacent areas. As the mathematical formulation for the problem generally has a large number of restrictions and variables and the structure of the constraint matrix of the problem is sparse and block-diagonal, the model has been reformulated using the Dantzig-Wolfe Decomposition strategy, which has enabled the use of a heuristic and exact procedures based on the column generation approach for its resolution. In the CRS-D problem, the aim is to meet the market demands for vegetables having a set of heterogeneous cropping areas available. The potential planting crops, as well as their productivity, depend on the considered cropping area. The problem is formulated as an optimization linear model in which each variable is associated to a crop rotation schedule. The model may include a large number of rotation schedules and is solved by the column generation approach. Computational experiments using instances based on real-world data confirm the efficiency of models and methodologies proposed for the problems

Linear optimization tools are used to solve many problems that arise in our day-to-day lives. The linear optimization models and methodologies help to find, for example, the best amount of ingredients in our food, the most suitable routes and timetables for the buses and trains we take, and the right way to invest our savings. We would cite many other situations that involves linear optimization, since a large number of companies around the world base their decisions in solutions which are provided by the linear optimization methodologies. In this thesis, we propose theoretical and computational developments to improve the performance of important linear optimization methods. Namely, we address simplex type methods, interior point methods, the column generation technique and the branch-and-price method. In simplex-type methods, we investigate a variant which exploits special features of problems which are formulated in the general form. We present a novel theoretical description of the method and propose how to efficiently implement this method in practice. Furthermore, we propose how to use the primal-dual interior point method to improve the column generation technique. This results in the primal-dual column generation method, which is more stable in practice and has a better overall performance in relation to other column generation strategies. The primal-dual interior point method also oers advantageous features which can be exploited in the context of the branch-and-price method. We show that these features improves the branching operation and the generation of columns and valid inequalities. For all the strategies which are proposed in this thesis, we present the results of computational experiments which involves publicly available, well-known instances from the literature. The results indicate that these strategies help to improve the performance of the linear optimization methodologies. In particular for a class of problems, namely the vehicle routing problem with time windows, the interior point branch-and-price method proposed in this study was up to 33 times faster than a state-of-the-art implementation available in the literature / Ferramentas de otimização linear são usadas para resolver diversos problemas do nosso dia-a- dia. Os modelos e as metodologias de otimização linear ajudam a obter, por exemplo, a melhor quantidade de ingredientes na nossa alimentação, os horários e as rotas de ônibus e trens que tomamos, e a maneira certa para investir nossas economias. Muitas outras situações que envolvem otimização linear poderiam ser aqui citadas, já que um grande número de empresas em todo o mundo baseia suas decisões em soluções obtidas pelos métodos de otimização linear. Nesta tese, são propostos desenvolvimentos teóricos e computacionais para melhorar o desempenho de métodos de otimização linear. Em particular, serão abordados métodos tipo simplex, métodos de pontos interiores, a técnica de geração de colunas e o método branch-and-price. Em métodos tipo simplex, é investigada uma variante que explora as características especiais de problemas formulados na forma geral. Uma nova descrição teórica do método é apresentada e, também, são propostas técnicas computacionais para a implementação eciente do método. Além disso, propõe-se como utilizar o método primal-dual de pontos interiores para melhorar a técnica de geração de colunas. Isto resulta no método primal-dual de geração de colunas, que é mais estável na prática e tem melhor desempenho geral em relação a outras estratégias de geração de colunas. O método primal-dual de pontos interiores também oferece características vantajosas que podem ser exploradas em conjunto com o método branch-and-price. De acordo com a investigação realizada, estas características melhoram a operação de ramificação e a geração de colunas e de desigualdades válidas. Para todas as estratégias propostas neste trabalho, são apresentados os resultados de experimentos computacionais envolvendo problemas de teste bem conhecidos e disponíveis publicamente. Os resultados indicam que as estratégias propostas ajudam a melhorar o desempenho das metodologias de otimização linear. Em particular para uma classe de problemas, o problema de roteamento de veículos com janelas de tempo, o método branch-and-price de pontos interiores proposto neste estudo foi até 33 vezes mais rápido que uma implementação estado-da-arte disponível na literatura

Le problème de routage de véhicules avec fenêtres de temps et routes multiples (MTVRPTW) est une généralisation du problème de routage de véhicules avec fenêtres de temps (VRPTW). Dans le MTVRPTW, on autorise un véhicule à effectuer plusieurs routes durant une période de planification, ce qui permet d'optimiser les transports lorsque le nombre de véhicules est limité et peu élevé. Nous proposons dans cette thèse la première méthode exacte permettant de résoudre ce problème. Notre modélisation prend la forme d'un problème de couverture des clients dont les variables sont des routes. Des contraintes d'exclusion mutuelle expriment la disponibilité des véhicules. Nous utilisons la Génération de Colonnes, avec un sous-problème effectuant, par programmation dynamique, une recherche de plus court chemin élémentaire contraint en ressources. Notre méthode de programmation dynamique tient compte des dépendances de plusieurs ressources grâce à la notion de label représentatif, et est ainsi plus efficace qu'une approche classique. La méthode de Génération de Colonnes est incluse dans un schéma de Branch and Price composé de deux types de branchement, l'un basé sur les arcs, l'autre sur la résolution d'un VRPTW. Nous avons mis en place diverses méthodes accélératrices spécifiques du MTVRPTW. Nous donnons les résultats de l'algorithme sur les instances de Solomon. Des résultats issus de méthodes exactes étaient disponibles dans la littérature pour le MTVRPTW avec durée limite sur les routes. Nous avons proposé un nouvel algorithme plus performant, et basé sur nos méthodes, pour cette variante du problème. / The multi-trip vehicle routing problem with time windows (MTVRPTW) is a generalization of the vehicle routing problem with time windows (VRPTW). In the MTVRPTW, one vehicle can perform several trips during a planning period. This allows optimizing the transport when the number of vehicles is limited and small.We propose here the first exact method for solving this problem.Our model is designed as a coverage problem for customers where the variables are trips. Mutual exclusion constraints express the availability of vehicles. We use a column generation scheme in which the sub-problem is an elementary shortest path problem with resource constraints (ESPPRC). Our dynamic programming method for ESPPRC takes into account dependencies of several resources through the concept of representative label. It is thus more efficient than a conventional approach. The column generation method is included in a Branch and Price scheme with two types of branching. One is based on arc selection, and the other on solving a VRPTW. We have implemented various accelerating methods which are specific to MTVRPTW. We give the results of our algorithm on Solomon instances.Results from exact methods were available in the literature for the MTVRPTW with time limit on the trips. We proposed a new and more efficient algorithm, based on our methods, to solve this variant of the problem.

Les terminaux à conteneurs utilisent les nouvelles technologies (EDI, RFID et GPS) pour échanger des données avec leurs partenaires, pour localiser les conteneurs et leurs équipements dans le terminal, et pour automatiser des tâches. Dans cette thèse, nous montrons comment ces informations peuvent être utilisées dans la gestion des opérations.La première partie utilise les informations sur les volumes annoncés pour affecter des ressources internes dans le but de minimiser le retard global au terminal. Nous représentons cette problématique à l'aide d'un problème de flot que nous implémentons comme programme linéaire mixte. Une étude de cas est réalisée pour un terminal du Grand Port Maritime de Marseille. En outre, nous combinons le problème d'affectation de ressources avec le dimensionnement d'un système de rendez-vous. Ceci permet de minimiser le retard global.La deuxième partie utilise les informations sur les conteneurs à retirer et leurs emplacements pour optimiser le déstockage. Le but est de retirer tous les conteneurs d'une rangée en minimisant le nombre de repositionnements parasites. Nous améliorons un modèle binaire, proposons une approche exacte de type branch and price - avec un sous-problème binaire et deux variantes d'un sous-problème énumératif - et en dérivons une approche heuristique - avec un sous-problème heuristique. L'approche exacte ne résout que les petites instances ; l'approche heuristique obtient des résultats satisfaisants mais devra être améliorée. Nous nous intéressons aussi à la version dynamique du problème où les informations sur les conteneurs à retirer arrivent petit à petit et comparons différentes stratégies de repositionnement. / Container terminals use intelligent freight technologies (e.g., EDI, RFID and GPS) to exchange data with their partners, to locate containers and equipment within the terminal, and to automate tasks. This thesis illustrated, via two examples, how this data may be used to optimize operations at the terminal.The first part uses information on announced volumes to allocate internal handling equipment. The objective is to minimize overall delays at the terminal. The problem is represented as a network flow problem and implemented as a linear mixed integer programming model. A case study for a terminal at the Grand Port Maritime de Marseille is carried out. We also showed that combining the allocation problem with the dimensioning of a truck appointment system may reduce overall delays at the terminal. The second part uses information on announced container retrievals and container positions to improve retrieval operations. The objective is to retrieve containers from a bay in a given sequence with a minimum number of parasite relocations. We improve an existing binary programming model and introduce an exact branch and price approach - with a binary subproblem and two variants of an enumerative subproblem - and a heuristic branch and price approach - with a heuristic subproblem. The exact approach solves only small instances; the heuristic approach performs well on several instances, but should be improved further. We also deal with a dynamic version of the problem where the retrieval order becomes revealed over time and evaluate different relocation strategies for this case.

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

Linear optimization tools are used to solve many problems that arise in our day-to-day lives. The linear optimization models and methodologies help to find, for example, the best amount of ingredients in our food, the most suitable routes and timetables for the buses and trains we take, and the right way to invest our savings. We would cite many other situations that involves linear optimization, since a large number of companies around the world base their decisions in solutions which are provided by the linear optimization methodologies. In this thesis, we propose theoretical and computational developments to improve the performance of important linear optimization methods. Namely, we address simplex type methods, interior point methods, the column generation technique and the branch-and-price method. In simplex-type methods, we investigate a variant which exploits special features of problems which are formulated in the general form. We present a novel theoretical description of the method and propose how to efficiently implement this method in practice. Furthermore, we propose how to use the primal-dual interior point method to improve the column generation technique. This results in the primal-dual column generation method, which is more stable in practice and has a better overall performance in relation to other column generation strategies. The primal-dual interior point method also oers advantageous features which can be exploited in the context of the branch-and-price method. We show that these features improves the branching operation and the generation of columns and valid inequalities. For all the strategies which are proposed in this thesis, we present the results of computational experiments which involves publicly available, well-known instances from the literature. The results indicate that these strategies help to improve the performance of the linear optimization methodologies. In particular for a class of problems, namely the vehicle routing problem with time windows, the interior point branch-and-price method proposed in this study was up to 33 times faster than a state-of-the-art implementation available in the literature / Ferramentas de otimização linear são usadas para resolver diversos problemas do nosso dia-a- dia. Os modelos e as metodologias de otimização linear ajudam a obter, por exemplo, a melhor quantidade de ingredientes na nossa alimentação, os horários e as rotas de ônibus e trens que tomamos, e a maneira certa para investir nossas economias. Muitas outras situações que envolvem otimização linear poderiam ser aqui citadas, já que um grande número de empresas em todo o mundo baseia suas decisões em soluções obtidas pelos métodos de otimização linear. Nesta tese, são propostos desenvolvimentos teóricos e computacionais para melhorar o desempenho de métodos de otimização linear. Em particular, serão abordados métodos tipo simplex, métodos de pontos interiores, a técnica de geração de colunas e o método branch-and-price. Em métodos tipo simplex, é investigada uma variante que explora as características especiais de problemas formulados na forma geral. Uma nova descrição teórica do método é apresentada e, também, são propostas técnicas computacionais para a implementação eciente do método. Além disso, propõe-se como utilizar o método primal-dual de pontos interiores para melhorar a técnica de geração de colunas. Isto resulta no método primal-dual de geração de colunas, que é mais estável na prática e tem melhor desempenho geral em relação a outras estratégias de geração de colunas. O método primal-dual de pontos interiores também oferece características vantajosas que podem ser exploradas em conjunto com o método branch-and-price. De acordo com a investigação realizada, estas características melhoram a operação de ramificação e a geração de colunas e de desigualdades válidas. Para todas as estratégias propostas neste trabalho, são apresentados os resultados de experimentos computacionais envolvendo problemas de teste bem conhecidos e disponíveis publicamente. Os resultados indicam que as estratégias propostas ajudam a melhorar o desempenho das metodologias de otimização linear. Em particular para uma classe de problemas, o problema de roteamento de veículos com janelas de tempo, o método branch-and-price de pontos interiores proposto neste estudo foi até 33 vezes mais rápido que uma implementação estado-da-arte disponível na literatura

[pt] Serviços Médicos de Emergência (SME) proveem ajuda essencial a pessoas em situações de emergência, através de atendimento com primeiros socorros e transporte para unidades de saúde. Sistemas SME devem utilizar da melhor maneira possível seus recursos limitados de atendimento. Esse desafio já foi amplamente estudado por pesquisadores, na forma de problemas de roteamento de veículos, tanto estáticos quanto dinâmicos. No presente trabalho, estudamos um problema estático de roteamento de ambulâncias, cujo objetivo é minimizar o tempo ponderado de espera dos pacientes. O problema considera também o tempo acumulado de espera, restrições de compatibilidade de ambulâncias a serviços, seleção de pacientes, redirecionamento de ambulâncias e redistribuição de ambulâncias. Implementamos um algoritmo exato usando Branch and Price e uma formulação do problema como uma Partição de Conjuntos, usando código aberto. Estudamos os resultados obtidos com esse algoritmo e os comparamos com métodos heurísticos online estudados anteriormente. Para tal, utilizamos dados obtidos do SAMU da cidade do Rio de Janeiro. Os resultados possibilitam a avaliação do valor de informação perfeita nesse contexto e proveem resultados comparativos para embasar o futuro desenvolvimento de algoritmos online. / [en] Emergency Medical Service (EMS) systems provide life-saving support to people in emergency situations via first aid treatment and emergency transport to medical facilities. Such systems must strive to make the best use of their limited resources; they have thus been studied in the context of static and dynamic vehicle routing problems. In this work, we study a static ambulance routing problem aiming to minimize the weighted sum of patients waiting time while considering ambulance compatibility, patients priorities, ambulance redirection, and ambulance reassignment. We implement an exact Branch-andPrice algorithm over a Set Partitioning Formulation, study the results of this algorithm, and compare them to previously studied online heuristics using data from Rio de Janeiro s public SAMU system. The results obtained allow us to assess the value of perfect information in such systems, providing a comparative baseline for subsequent developments of online algorithms.

O presente trabalho realiza o estudo e aplicação de um algoritmo de branch-and-price para a resolução de um problema de escalonamento de compressores. O problema é ligado à produção petrolífera, o qual consiste em definir um conjunto de compressores a serem ativados para fornecer gas de elevação a um conjunto de poços, atendendo toda demanda e minimizando os custos envolvidos. O problema é caracterizado por uma função objetivo não-convexa que é linearizada por partes de forma a ser formulada como um problema de programação inteira mista. A abordagem de geração de colunas é baseada na decomposição de Dantzig-Wolfe e apresenta melhores limitantes inferiores em relação à relaxação linear da formulação compacta. O branch-and-price é comparado ao solver CPLEX, sendo capaz de encontrar a solução ótima em menor tempo para um conjunto de instâncias, bem como melhores soluções factíveis para instâncias maiores em um período de tempo limitado. / This work presents the study and application of a branch-and-price algorithm for solving a compressor scheduling problem. The problem is related to oil production and consists of defining a set of compressors to be activated, supplying the gas-lift demand of a set of wells and minimizing the associated costs. The problem has a non-convex objective function, to which a piecewise-linear formulation has been proposed. This dissertation proposes a column generation approach based on the Dantzig-Wolfe decomposition, which achieves tighter lower bounds than the straightforward linear relaxation of the piecewise-linear formulation. The column generation was embedded in a branch-and-price algorithm and further compared with CPLEX, obtaining optimal solutions in lesser time for a set of instances. Further, the branch-and-price algorithm can find better feasible solutions for large instances under a limited processing time.

We propose a novel branch-and-price (B&P) approach to solve the maximum weighted independent set problem (MWISP). Our approach uses clones of vertices to create edge-disjoint partitions from vertex-disjoint partitions. We solve the MWISP on sub-problems based on these edge-disjoint partitions using a B&P framework, which coordinates sub-problem solutions by involving an equivalence relationship between a vertex and each of its clones. We present test results for standard instances and randomly generated graphs for comparison. We show analytically and computationally that our approach gives tight bounds and it solves both dense and sparse graphs quite quickly.

Résumé Dans cette thèse, nous étudions la gestion des blocs opératoires, et plus particulièrement la planification et l’ordonnancement de ces blocs. Le choix d’études de ce secteur hospitalier est lié au fait qu’il est réputé comme un lieu hautement stratégique dans un établissement hospitalier, surtout en terme de coûts. Il est dès lors utile de s’intéresser à l’optimisation de l’utilisation des ressources hospitalières. Etant donné que l’optimisation du fonctionnement des blocs opératoires est un problème vaste et complexe, nous nous focalisons sur deux sous-problèmes déjà réputés difficiles : la planification et l’ordonnancement des interventions chirurgicales. Ce sont des problèmes centrés sur la programmation opératoire et dont l’objectif est d’obtenir un programme opératoire réalisable et efficace du bloc. Les problèmes de planification sont premièrement formalisés comme des modèles mathématiques en nombres entiers et puis résolus par des procédures heuristiques et par un « Branch-and-Price » basés sur la génération de colonnes qui est utilisée pour résoudre les relaxations linéaires des modèles concernés afin de trouver les bornes inférieures. Les modèles d’ordonnancement sont traités comme des variantes de modèles de « flow shop » hybride à deux étages et résolus par des algorithmes génétiques hybrides. Finalement, nos modèles ont été testés et validés sur un cas réel. ABSTRACT This thesis presents our studies on the operating theatre management, especially on the operating theatre planning and scheduling problem in case that this surgical sector is always regarded as the kernel in a hospital in terms of the expenditure. Therefore, it’s necessary to optimize the assignment of hospital resources in the operating theatre. Since this type of problem is extremely complex, we concentrate on just two sub-problems that are also considered difficult ones by researchers: the surgical cases planning and scheduling problem, which aim to make a surgical cases programming with an objective of obtaining a realizable and efficient surgical cases operating schedule. At first the weekly planning problems of surgical cases are formulated as a mathematical integer programming, and then they are solved by heuristic procedures and Branch-and-Price one. All these procedures are based on the column generation procedure, which is used to solve the linear relaxation of each model for a lower bound. The scheduling models are treated as variants of hybrid two-stage flow shop problem and are solved by proposed hybrid genetic algorithms. Finally, our models are tested and validated in a real case.