Le développement de structures de réseau efficaces pour le transport de marchandises est fondamental sur le marché mondial actuel. Les demandes doivent être traitées rapidement, répondre aux besoins des clients dans les meilleurs délais, les congestions et les retards doivent être minimisés, les émissions de CO2 doivent être contrôlés et des coûts de transport moins élevés doivent être proposés aux clients. La structure hub-and-spoke est un modèle de réseau courant utilisé à la fois dans le transport régional comme dans le transport intercontinental, permettant une économie d'échelle grâce aux consolidations opérées au niveau des noeuds hub. Mais, les retards, les congestions et les longs délais de livraison sont des inconvénients de ce type de réseau. Dans cette thèse, un nouveau concept, "sub-hub", est ajouté à la structure du réseau classique hub-and-spoke. Dans les modèles de réseau proposés, une économie d'échelle et des chemins alternatifs plus courts sont mis en oeuvre, en minimisant ainsi le coût de transport et le délai de livraison. Le sub-hub est vu comme un point de connexion entre deux routes distinctes de régions voisines. Des transbordements sans passer par les noeuds hub sont possibles au niveau des sub-hubs. Des congestions peuvent ainsi être évitées et, par conséquent, les retards associés sont ainsi minimisés. Quatre modèles de programmation linéaire en nombres entiers binaires du problème de la localisation de hubs et de routage sont développés dans cette thèse. Des réseaux avec sub-hub et des réseaux sans sub-hub prenant en compte des routes circulaires entre hubs ou des connexions directes entre hubs sont ainsi comparées. Ces modèles sont composés de quatre sous-problèmes (localisation, allocation, conception de service et routage) qui rendent complexe la recherche de solutions. Une approche cutting plane est testée pour résoudre de petites instances de problème tandis qu'une recherche à voisinage variable avec décomposition (VNDS) composée de méthodes exactes (matheuristic) a été développée pour résoudre de grandes instances. Le VNDS mis en oeuvre, explore chaque sous-problème avec différents opérateurs. Des gains importants dans la fonction objective sont observés par les modèles avec sub-hub confirmant ainsi le développement de réseaux plus compétitifs. / The development of efficient network structures for freight transport is a major concern for the current global market. Demands need to be quickly transported and should also meet the customer needs in a short period of time. Traffic congestions and delays must be minimized, since CO2 emissions must be controlled and affordable transport costs have to be offered to customers. Hub-and-spoke structure is a current network model used by both regional and intercontinental transportation, which offers an economy of scale for aggregated demands inside hub nodes. However, delays, traffic congestions and long delivery time are drawbacks from this kind of network. In this thesis, a new concept, which is called "sub-hub", is proposed to the classic hub-and-spoke network structure. In the proposed network models, economy of scale and shorter alternative paths are implemented, thus minimizing the transport cost and delivery time. The sub-hub proposal can be viewed as a connection point between two routes from distinct and close regions. Transshipments without the need to pass through hub nodes are possible inside sub-hubs. This way, congestions can be avoided and, consequently, delays are minimized. Four binary integer linear programming models for hub location and routing problem were developed in this thesis. Networks with sub-hub and networks without sub-hub taking into account circular hub routes or direct connections between hubs are compared. These models are composed of four sub-problems (location, allocation, service design and routing), which hinders the solution. A cutting plane approach was used to solve small instances of problem, while a Variable Neighborhood Decomposition Search (VNDS) composed of exact methods (matheuristic) was developed to solve large instances. The VNDS was used to explore each sub-problem by different operators. Major benefits are provided by models with sub-hub, thus promoting the development of more competitive networks.

A presente pesquisa aborda um problema de programação de veículos rico, em que a característica mais importante é a demanda de múltiplas embarcações para atendimento a uma única tarefa. Trata-se de uma aplicação real do setor de apoio marítimo \"offshore\", das embarcações que fazem o reboque e o lançamento de linhas de ancoragem de sondas de perfuração e unidades de produção. Como método de solução, aplicaram-se duas heurísticas com uma abordagem híbrida que incluem uma inserção baseada em programação linear inteira, visando a minimização do custo total da operação, dentro de um tempo de processamento aceitável. / This research deals with a rich vehicle scheduling problem, having as the most important feature the demand of multiple vessels per task. It is a real problem present in the oil industry related to the vessels that undertake the towing and the launching of mooring lines of drilling and production units. As a solution method, two heuristics with a hybrid approach were applied which include an insertion based on integer linear programming, aiming at minimizing the total cost of the operation, within an acceptable processing time.

O Problema de Balanceamento e Sequenciamento de Linhas de Montagem com Tempos de Setup dependentes da Sequência (SUALBSP, em inglês Setup Assembly Line Balancing and Scheduling) envolve a atribuição de tarefas às estações de trabalho e o sequenciamento destas tarefas dentro da estação à qual foi atribuída. Trabalhos anteriores propuseram soluções heurísticas com excelentes resultados, porém o uso de métodos exatos, por meio de algum resolvedor de Programação Inteira Mista, tem apresentado desempenhos decepcionantes, pois contém um subproblema NP-hard em todas as estações. Enquanto o modelo de Scholl, Boysen e Fliedner (2013) minimiza prioritariamente o número de estações, o modelo proposto neste trabalho parte da premissa que este é um dado definido. A partir de uma estimativa inicial de número de estações, processa-se o modelo com o objetivo de distribuir as tarefas e minimizar o tempo total de estação, que é o segundo objetivo do modelo original. Se este processamento for infactível, incrementa-se o número de estações em uma unidade e reprocessa-se o modelo até se encontrar um resultado factível. Experimentos computacionais em 101 instâncias de dados confirmam o bom desempenho da abordagem proposta, sem qualquer prejuízo à qualidade da solução. Portanto, os resultados apresentados demonstram que há espaço para estudos futuros a partir do uso de matheurísticas. / The Setup Assembly Line Balancing and Scheduling Problem (SUALBSP) involves the assigning of tasks to workstations and the sequencing of these tasks within the station to which they are assigned. Previous work has proposed heuristic solutions with excellent results, but the use of exact methods, by some Mixed-Integer Programming solver, has shown disappointing performance, because it contains an NP-hard sub problems in every station. While the model proposed by Scholl, Boysen and Fliedner (2013) primarily minimizes the numbers of stations, our model assumes it as a parameter. From an initial estimate of the number of stations, we process the model for allocating tasks and minimize station times, which is the second objective of the original model. If this processing is infeasible, we increase the number of stations by one unit and we reprocess the model to find a feasible result. Computational experiments in 101 instances of data set confirm the good performance of the proposed approach, without harming the quality of the solution. Therefore, the results show that there are opportunities for future studies based on the use of matheuristics.

O Problema de Balanceamento e Sequenciamento de Linhas de Montagem com Tempos de Setup dependentes da Sequência (SUALBSP, em inglês Setup Assembly Line Balancing and Scheduling) envolve a atribuição de tarefas às estações de trabalho e o sequenciamento destas tarefas dentro da estação à qual foi atribuída. Trabalhos anteriores propuseram soluções heurísticas com excelentes resultados, porém o uso de métodos exatos, por meio de algum resolvedor de Programação Inteira Mista, tem apresentado desempenhos decepcionantes, pois contém um subproblema NP-hard em todas as estações. Enquanto o modelo de Scholl, Boysen e Fliedner (2013) minimiza prioritariamente o número de estações, o modelo proposto neste trabalho parte da premissa que este é um dado definido. A partir de uma estimativa inicial de número de estações, processa-se o modelo com o objetivo de distribuir as tarefas e minimizar o tempo total de estação, que é o segundo objetivo do modelo original. Se este processamento for infactível, incrementa-se o número de estações em uma unidade e reprocessa-se o modelo até se encontrar um resultado factível. Experimentos computacionais em 101 instâncias de dados confirmam o bom desempenho da abordagem proposta, sem qualquer prejuízo à qualidade da solução. Portanto, os resultados apresentados demonstram que há espaço para estudos futuros a partir do uso de matheurísticas. / The Setup Assembly Line Balancing and Scheduling Problem (SUALBSP) involves the assigning of tasks to workstations and the sequencing of these tasks within the station to which they are assigned. Previous work has proposed heuristic solutions with excellent results, but the use of exact methods, by some Mixed-Integer Programming solver, has shown disappointing performance, because it contains an NP-hard sub problems in every station. While the model proposed by Scholl, Boysen and Fliedner (2013) primarily minimizes the numbers of stations, our model assumes it as a parameter. From an initial estimate of the number of stations, we process the model for allocating tasks and minimize station times, which is the second objective of the original model. If this processing is infeasible, we increase the number of stations by one unit and we reprocess the model to find a feasible result. Computational experiments in 101 instances of data set confirm the good performance of the proposed approach, without harming the quality of the solution. Therefore, the results show that there are opportunities for future studies based on the use of matheuristics.

O Problema de Balanceamento e Sequenciamento de Linhas de Montagem com Tempos de Setup dependentes da Sequência (SUALBSP, em inglês Setup Assembly Line Balancing and Scheduling) envolve a atribuição de tarefas às estações de trabalho e o sequenciamento destas tarefas dentro da estação à qual foi atribuída. Trabalhos anteriores propuseram soluções heurísticas com excelentes resultados, porém o uso de métodos exatos, por meio de algum resolvedor de Programação Inteira Mista, tem apresentado desempenhos decepcionantes, pois contém um subproblema NP-hard em todas as estações. Enquanto o modelo de Scholl, Boysen e Fliedner (2013) minimiza prioritariamente o número de estações, o modelo proposto neste trabalho parte da premissa que este é um dado definido. A partir de uma estimativa inicial de número de estações, processa-se o modelo com o objetivo de distribuir as tarefas e minimizar o tempo total de estação, que é o segundo objetivo do modelo original. Se este processamento for infactível, incrementa-se o número de estações em uma unidade e reprocessa-se o modelo até se encontrar um resultado factível. Experimentos computacionais em 101 instâncias de dados confirmam o bom desempenho da abordagem proposta, sem qualquer prejuízo à qualidade da solução. Portanto, os resultados apresentados demonstram que há espaço para estudos futuros a partir do uso de matheurísticas. / The Setup Assembly Line Balancing and Scheduling Problem (SUALBSP) involves the assigning of tasks to workstations and the sequencing of these tasks within the station to which they are assigned. Previous work has proposed heuristic solutions with excellent results, but the use of exact methods, by some Mixed-Integer Programming solver, has shown disappointing performance, because it contains an NP-hard sub problems in every station. While the model proposed by Scholl, Boysen and Fliedner (2013) primarily minimizes the numbers of stations, our model assumes it as a parameter. From an initial estimate of the number of stations, we process the model for allocating tasks and minimize station times, which is the second objective of the original model. If this processing is infeasible, we increase the number of stations by one unit and we reprocess the model to find a feasible result. Computational experiments in 101 instances of data set confirm the good performance of the proposed approach, without harming the quality of the solution. Therefore, the results show that there are opportunities for future studies based on the use of matheuristics.

Made available in DSpace on 2015-05-08T14:53:38Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 3056611 bytes, checksum: e73001b52f3f37e092e742b4d599ce04 (MD5) Previous issue date: 2014-02-14 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / This dissertation deals with the Pollution-Routing Problem (PRP), a Vehicle Routing Problem (VRP) with environmental considerations, recently introduced in the literature by Bekta ¸s e Laporte (2011). The objective is to minimize operational and environmental costs while respecting route-load constraints and service time windows. Costs are based on driver wages and fuel consumption, which depends on many factors, such as travel distance and vehicle load. Vehicle speeds are additional decision variables of the problem which complement routing decisions. They impact the total cost, the travel times between the locations, and thus the set of feasible routes. We propose a hybrid method that combines a local search-based metaheuristic with an exact approach and a recursive speed-optimization algorithm. Moreover, two other green VRP variants, the Fuel Consumption VRP (FCVRP) and the Energy Minimizing VRP (EMVRP), are addressed. The results obtained compare very favorably with those found in the literature, and many new improved solutions are reported. / Esta dissertação lida com o Pollution-Routing Problem (PRP), i.e. um Problema de Roteamento de Veículos (PRV) com considerações ambientais, recentemente introduzido na literatura por Bekta¸s e Laporte (2011). O objetivo consiste na minimização dos custos operacionais e ambientais, respeitando as restrições de carga dos veículos e janelas de tempo dos clientes. O custo é baseado no salário dos motoristas e no consumo de combustível, que depende de diversos fatores, como distância percorrida e carga transportada. As velocidades dos veículos são variáveis de decisão adicionais que complementam as decisões de roteamento. Tais velocidades interferem diretamente no custo total, nos tempos de viagem, bem como no conjunto de rotas viáveis. Uma abordagem híbrida que combina uma metaheurística baseada em busca local com uma abordagem exata e um algoritmo recursivo para otimizar as velocidades é proposta para solucionar o problema. Além do PRP, outras duas variantes do PRV com considerações ambientais são tratadas: o PRV considerando consumo de combustível e o PRV com minimização de energia. Os resultados obtidos se mostraram bastante favoráveis quando comparados com os melhores da literatura, e diversas soluções melhoradas são reportadas.

En réponse aux contraintes économiques, au problème du vieillissement de la population et aussi à la volonté des patients de se faire soigner dans le milieu familial, l’Hospitalisation À Domicile (HAD) prend de plus en plus d’ampleur. Dans ce travail de recherche, nous nous intéressons aux établissements d’hospitalisation à domicile, parmi les différentes problématiques qui existent dans ce domaine, nous étudions le problème de routage et de planification des personnels.Nous développons tout d’abord un modèle de programmation linéaire en nombres entiers qui permet de formuler clairement les contraintes du problème.Nous présentons par la suite, une matheuristique permettant de résoudre le problème défini sur une journée de planification. Nous développons également une variante de notre matheuristique sur un horizon de 14 jours. Cette dernière prend en considération plusieurs contraintes en plus de celles considérées pour la planification sur une journée. Enfin, nous introduisons un problème de réoptimisation de routage et de la planification des personnels pour l’hospitalisation à domicile et présentons quelques approches de résolutions. Ces différentes méthodes combinent des heuristiques, la programmation dynamique et la programmation mathématique. / Home health care (HHC), i.e., visiting and nursing patients athome, is a growing sector in the medical care system. There fore, the optimal scheduling of the health care staffs arises. The objective of this problem consists in constructing routes and rosters for the staffs while optimizing costs. We propose an integer linear programming formulation (ILP) that clearly formulate the constraints of the problem. We present a matheuristic to solve the daily routing and rostering problem. We also develop a variant of our matheuristic defined for a period of 14 days. It takes into account several constraints in addition to those considered in the daily planning. Finally, we introduce the problem of reoptimizing the routing and rostering staffs and we give some ideas to solve this problem. These methods combine heuristic algorithms, dynamic programming and mathematical programming.

As decisões operacionais de produção em uma indústria de fiação são planejadas na prática determinando soluções dos sub-problemas de dimensionamento e sequenciamento de lotes e da mistura de fardos de algodão. As tarefas são: definir o tamanho, a sequência, o tempo e alocação de cada lote de produção e quais fardos de algodão devem ser utilizados na produção. Por si só, os sub-problemas representam grandes desafios no planejamento da produção. Entretanto, para melhor representar o ambiente produtivo e alcançar custos de produção mais baixos, indústrias de processo, como as de fiação, procuram integrar mais e mais seus sub-problemas de planejamento. O objetivo dessa tese é apresentar modelos matemáticos e métodos de solução para auxiliar a tomada de decisão no nível operacional do planejamento da produção. Três formulações matemáticas para o dimensionamento e sequenciamento de lotes em um sistema de dois estágios com produção sincronizada são propostas. Um novo método baseado em programação matemática e metaheurísticas e também desenvolvida para a solucão desse sub-problema. Além disso, a integração das decisões relativas a matéria-prima (fardos de algodão) ao dimensionamento e sequenciamento de lotes é analisada. As novas formulações propostas representam de forma mais realista o problema de dimensionamento e sequenciamento de lotes da indústria de fiação e de indústrias de processo com ambiente produtivo similares. O método de solução encontra boas soluções para o problema e supera outros méodos similares presentes em softwares comerciais. Além disso, o método é geral o suficiente para a solução de outros problemas de otimização. O problema integrado de dimensionamento e sequenciamento de lotes e mistura comprovou que restrições relativas à qualidade dos fios influenciam os custos e viabilidade do planejamento da produção. O planejamento integrado dessas óperações trata o sistema considerando restrições que se relacionam, definindo planos de produção mais realistas / In the practice of a spinning industry, the operational decisions of the production planning are determined by the hierarchical solution of the lot-sizing and scheduling problem and the blending problem of the cotton bales. The tasks are: to define the size, sequence, timing and allocation of each production lot and to select which cotton bales are used for production. Each of these problems represents a large challenge in planning the production. However, in order to better represent the production environment and to reach lower production costs, process industries (as the spinning industry) are integrating more and more of the production sub-problems into the planning. The aim of this thesis is to propose novel mathematical models and solution methods to assist the decision maker to plan the production at the operational level. Three formulations for the synchronized two-stage lot sizing and scheduling are proposed. A new method based on mathematical programming and metaheuristics is also developed to solve this sub-problem. In addition, the integration of the lot sizing and scheduling with decisions related to the raw materials (cotton bales) is analyzed. The novel models represent a more realistic lot sizing and scheduling for the spinning industry and process industries of similar production environment. The solution method finds good solutions to the mentioned problem and outperforms other state-of-the-art methods incorporated in commercial softwares. Moreover, the method is general enough to solve other optimization problems. The integrated lot-sizing, scheduling and blending prove that constraints related to the yarn quality influence the costs and the feasibility of the production planning. The integrated planning of these operations approaches the system considering the constraint relationship and defines more realistic production plans

As decisões operacionais de produção em uma indústria de fiação são planejadas na prática determinando soluções dos sub-problemas de dimensionamento e sequenciamento de lotes e da mistura de fardos de algodão. As tarefas são: definir o tamanho, a sequência, o tempo e alocação de cada lote de produção e quais fardos de algodão devem ser utilizados na produção. Por si só, os sub-problemas representam grandes desafios no planejamento da produção. Entretanto, para melhor representar o ambiente produtivo e alcançar custos de produção mais baixos, indústrias de processo, como as de fiação, procuram integrar mais e mais seus sub-problemas de planejamento. O objetivo dessa tese é apresentar modelos matemáticos e métodos de solução para auxiliar a tomada de decisão no nível operacional do planejamento da produção. Três formulações matemáticas para o dimensionamento e sequenciamento de lotes em um sistema de dois estágios com produção sincronizada são propostas. Um novo método baseado em programação matemática e metaheurísticas e também desenvolvida para a solucão desse sub-problema. Além disso, a integração das decisões relativas a matéria-prima (fardos de algodão) ao dimensionamento e sequenciamento de lotes é analisada. As novas formulações propostas representam de forma mais realista o problema de dimensionamento e sequenciamento de lotes da indústria de fiação e de indústrias de processo com ambiente produtivo similares. O método de solução encontra boas soluções para o problema e supera outros méodos similares presentes em softwares comerciais. Além disso, o método é geral o suficiente para a solução de outros problemas de otimização. O problema integrado de dimensionamento e sequenciamento de lotes e mistura comprovou que restrições relativas à qualidade dos fios influenciam os custos e viabilidade do planejamento da produção. O planejamento integrado dessas óperações trata o sistema considerando restrições que se relacionam, definindo planos de produção mais realistas / In the practice of a spinning industry, the operational decisions of the production planning are determined by the hierarchical solution of the lot-sizing and scheduling problem and the blending problem of the cotton bales. The tasks are: to define the size, sequence, timing and allocation of each production lot and to select which cotton bales are used for production. Each of these problems represents a large challenge in planning the production. However, in order to better represent the production environment and to reach lower production costs, process industries (as the spinning industry) are integrating more and more of the production sub-problems into the planning. The aim of this thesis is to propose novel mathematical models and solution methods to assist the decision maker to plan the production at the operational level. Three formulations for the synchronized two-stage lot sizing and scheduling are proposed. A new method based on mathematical programming and metaheuristics is also developed to solve this sub-problem. In addition, the integration of the lot sizing and scheduling with decisions related to the raw materials (cotton bales) is analyzed. The novel models represent a more realistic lot sizing and scheduling for the spinning industry and process industries of similar production environment. The solution method finds good solutions to the mentioned problem and outperforms other state-of-the-art methods incorporated in commercial softwares. Moreover, the method is general enough to solve other optimization problems. The integrated lot-sizing, scheduling and blending prove that constraints related to the yarn quality influence the costs and the feasibility of the production planning. The integrated planning of these operations approaches the system considering the constraint relationship and defines more realistic production plans

Cette thèse a pour but d’apporter des solutions méthodologiques pour la mutualisation des transports entre les fournisseurs et les plateformes de la grande distribution. Cette mutualisation permet en effet de réduire les coûts, les émissions de CO2, et d’augmenter la qualité de service. Elle est organisée autour d’un réseau de plateformes de cross-docking appelées Centres de Routage Collaboratifs, développé par la société 4S Network. Nos travaux consistent à modéliser et résoudre à l’aide de techniques de recherche opérationnelle plusieurs problèmes d’optimisation du transport dans le réseau mutualisé. Le verrou scientifique majeur est de résoudre conjointement un problème de plan de chargement (Service Network Design Problem) dans un réseau logistique national, et des problèmes de tournées de véhicules à une échelle régionale. Nous prenons en compte des contraintes additionnelles issues du monde industriel et les tarifs réellement pratiqués par les transporteurs, notamment des coûts non linéaires.Les problèmes d’optimisation résultants sont résolus au moyen de méthodes ditesmatheuristiques, c’est-à-dire combinant des approches exactes telles que la génération de colonnes et des approches (méta)heuristiques telles que la recherche tabou. Les algorithmes développés dans cette thèse ont donné lieu à unoutil logiciel aujourd’hui en exploitation chez 4S Network. / The main purpose of this PhD. thesis is to provide methodological solutions for a collaborative transport between suppliers and retail platforms. The outcomes of this collaboration are numerous:cost reduction, greenhouse gas emission reduction and higher quality of service. The network is structured around cross-docking platforms developed by the company 4S Network. We model and solve several optimization problems in this collaborative network, using operationsresearch techniques. The major scientific challenge is to simultaneously solve a Service Network Design Problem in a national logistics network and several Vehicle Routing Problems at regional level. We consider additional constraints and prevailing pricing arising from the carriers, in particular non-linear costs. The resulting optimization problems are solved by matheuristic methods, that combine exact approaches as column generation and (meta)heuristic approaches as tabu search. The algorithms developed in this thesis are the core functions of a software tool developed for 4S network.