[pt] Este trabalho apresenta uma aplicação prática do roteamento de navios com coleta-e-entrega e janelas de tempo para o alívio de plataformas de petróleos para exportação. Especificamente para este caso, os navios aliviadores fazem o transporte do petróleo de plataformas offshore diretamente para um terminal de transbordo, onde a carga será transferida para outro navio para ser exportado. Foram propostas adaptações a um modelo de programação linear inteira mista já existente, buscando descrever as peculiaridades deste processo e facilitar a sua resolução pelo método exato. O modelo foi testado com dados realísticos de uma empresa petrolífera e pode fornecer soluções de alta qualidade para testes com períodos de até 30 dias em um tempo de processamento computacional inferior a 10 minutos, estando assim adequado ao uso na rotina do programador de navios desta empresa. / [en] This study presents a practical application of ship routing with pickup-anddelivery and time windows for offloading operations in offshore oil platforms. Specifically in this case, the shuttle tankers transport crude oil from the offshore platforms directly to an onshore terminal, where the cargo will be transferred to another vessel to be exported. Adaptations to an existing mixed-integer linear programming model are proposed to better represent this process and facilitate its resolution by the exact method. The model was tested with realistic data from an oil and gas company and it can provide high-quality solutions for tests with periods up to 30 days, in a processing time of less than 10 minutes, thus being suitable for use in the routine of the company s ship programmer.

Made available in DSpace on 2016-06-02T19:52:05Z (GMT). No. of bitstreams: 1 6045.pdf: 14667118 bytes, checksum: f13a2c0983ea271f2e60ed298b158806 (MD5) Previous issue date: 2014-05-26 / Agência Nacional de Petróleo / This work studies the ship routing and scheduling problem in oil transportation from offshore platforms to inland terminals. It is motivated by a real situation in a Brazilian oil company. Brazil is one of the world's greatest oil producers and has around 80% of its oil explored in offshore mode. Thus, transportation costs play an important role in achieving operational excellence, and the recent growth trends for oil exploration in Brazil has transformed its operations and demanded agile and effective decision support systems for addressing the oil sector dynamism. This work's goal consists in developing and applying an optimization-based approach using a mixed integer linear programming model in real decision-making situations, along with a solution method based on mathematical programming (MIP-heuristics) in order to solve the model, such as relax-and-fix. The proposed model is inspired in a problem formulation for pickup and delivery with time windows (PDPTW) and heterogeneous fleet, where costs incurred for fuel consumption and fleet contracts is the objective function to be minimized. The pickup and delivery pairs are predetermined and the model's main decision refers to ship allocation to these pairs compounding a route. Furthermore, some additional constraints are modeled and proposed, such as terminal access and platform mooring limitation according to ship types, as well as product blend incompatibility. The model was implemented in a modeling language along with an optimizarion software. Computational experiments with the model and the heuristics are presented for different data sets supplied by the case study company. These experiments show the potential benefits of this approach for finding good solutions for the problem as well as the dificulty in finding solutions for realistic instances due to its NP-hard characteristics. / Este trabalho estuda o problema de roteirização e programação de navios que realizam o escoamento de petróleo das plataformas marítimas para terminais terrestres, motivado por uma situação real de uma empresa brasileira da indústria petrolífera. O Brasil é um dos maiores produtores mundiais de petróleo, e cerca de 80% de seu petróleo é explorado no mar. Dentro deste contexto, os custos de transporte desempenham um papel importante na busca pela excelência operacional e as tendências de crescimento da exploração de petróleo no Brasil têm tornado as operações mais complexas e demandantes de sistemas de apoio à decisão ágeis e eficazes que contemplem o dinamismo do setor petrolífero. O objetivo deste trabalho consiste em desenvolver e aplicar uma abordagem de otimização baseada em um modelo de programação linear inteira mista em situações reais de tomada de decisão, em conjunto com métodos de solução baseados em programação matemática (MIP-Heuristics) para resolver o modelo, como relax-and-fix. O modelo proposto é inspirado em uma formulação de problemas de coleta e entrega com janelas de tempo (pickup and delivery with time windows PDPTW) e frota heterogênea, no qual busca-se minimizar os custos decorrentes do consumo de combustível dos navios e contratos de afretamento. O modelo é do tipo origem-destino, no qual os pares coleta/entrega são pré-determinados e a decisão do modelo refere-se à alocação de navios para os diferentes pares, compondo uma rota. Além disso, são propostas restrições adicionais que contemplam limitações de acesso a terminais e de atracação em plataformas de acordo com os tipos de navio, além da incompatibilidade de mistura de produtos, entre outros. O modelo foi implementado utilizando uma linguagem de modelagem em conjunto com um software de otimização. Experimentos computacionais com o modelo e as heurísticas são apresentados para diferentes conjuntos de dados fornecidos pela empresa e comprovam o potencial das abordagens para encontrar boas soluções para o problema, mas também suas dificuldades para encontrar soluções para exemplares de tamanho realista, por tratar-se de um problema NP-difícil do ponto de vista de teoria de complexidade.

Submitted by Fernando Souza (fernandoafsou@gmail.com) on 2017-08-15T11:46:12Z No. of bitstreams: 1 arquivototal.pdf: 884446 bytes, checksum: 92314027dddef8365b4a2e655b65bd78 (MD5) / Made available in DSpace on 2017-08-15T11:46:13Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 884446 bytes, checksum: 92314027dddef8365b4a2e655b65bd78 (MD5) Previous issue date: 2016-05-20 / The Static Bike Rebalancing Problem (SBRP) is a recent problem motivated by the task of repositioning bikes among stations in a self-service bike-sharing systems. This problem can be seen as a variant of the one-commodity pickup and delivery vehicle routing problem, where multiple visits are allowed to be performed at each station, i.e., the demand of a station is allowed to be split. Moreover, a vehicle may temporarily drop its load at a station, leaving it in excess or, alternatively, collect more bikes (even all of them) from a station, thus leaving it in default. Both cases require further visits in order to meet the actual demands of such station. This work deals with a particular case of the SBRP, in which only a single vehicle is available and the objective is to nd a least-cost route that meets the demand of all stations and does not violate the minimum (zero) and maximum (vehicle capacity) load limits along the tour. Therefore, the number of bikes to be collected or delivered at each station should be appropriately determined in order to respect such constraints. This is a NP-Hard problem since it contains other NP-Hard problems as special cases, hence, using exact methods to solve it is intractable for larger instances. Several methods have been proposed by other authors, providing optimal values for small to medium sized instances, however, no work has consistently solved instances with more than 60 stations. The proposed algorithm to solve the problem is an iterated local search (ILS) based heuristic combined with a randomized variable neighborhood descent (RVND) as local search procedure. The algorithm was tested on 980 benchmark instances from the literature and the results obtained are quite competitive when compared to other existing methods. Moreover, the method was capable of nding most of the known optimal solutions and also of improving the results on a number of open instances. / O Problema do Rebalanceamento Est atico de Bicicletas (Static Bike Rebalancing Problem, SBRP) e um recente problema motivado pela tarefa de reposicionar bicicletas entre esta c~oes em um sistema self-service de compartilhamento de bicicletas. Este problema pode ser visto como uma variante do problema de roteamento de ve culos com coleta e entrega de um unico tipo de produto, onde realizar m ultiplas visitas a cada esta c~ao e permitido, isto e, a demanda da esta c~ao pode ser fracionada. Al em disso, um ve culo pode descarregar sua carga temporariamente em uma esta c~ao, deixando-a em excesso, ou, de maneira an aloga, coletar mais bicicletas (at e mesmo todas elas) de uma esta c~ao, deixando-a em falta. Em ambos os casos s~ao necess arias visitas adicionais para satisfazer as demandas reais de cada esta c~ao. Este trabalho lida com um caso particular do SBRP, em que apenas um ve culo est a dispon vel e o objetivo e encontrar uma rota de custo m nimo que satisfa ca as demandas de todas as esta c~oes e n~ao viole os limites de carga m nimo (zero) e m aximo (capacidade do ve culo) durante a rota. Portanto, o n umero de bicicletas a serem coletadas ou entregues em cada esta c~ao deve ser determinado apropriadamente a respeitar tais restri c~oes. Trata-se de um problema NP-Dif cil uma vez que cont em outros problemas NP-Dif cil como casos particulares, logo, o uso de m etodos exatos para resolv^e-lo e intrat avel para inst^ancias maiores. Diversos m etodos foram propostos por outros autores, fornecendo valores otimos para inst^ancias pequenas e m edias, no entanto, nenhum trabalho resolveu de maneira consistente inst^ancias com mais de 60 esta c~oes. O algoritmo proposto para resolver o problema e baseado na metaheur stica Iterated Local Search (ILS) combinada com o procedimento de busca local variable neighborhood descent com ordena c~ao aleat oria (randomized variable neighborhood descent, RVND). O algoritmo foi testado em 980 inst^ancias de refer^encia na literatura e os resultados obtidos s~ao bastante competitivos quando comparados com outros m etodos existentes. Al em disso, o m etodo foi capaz de encontrar a maioria das solu c~oes otimas conhecidas e tamb em melhorar os resultados de inst^ancias abertas.

Submitted by Alison Vanceto (alison-vanceto@hotmail.com) on 2017-01-24T10:38:55Z No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) / Approved for entry into archive by Camila Passos (camilapassos@ufscar.br) on 2017-02-08T10:50:29Z (GMT) No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) / Approved for entry into archive by Camila Passos (camilapassos@ufscar.br) on 2017-02-08T10:51:23Z (GMT) No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) / Made available in DSpace on 2017-02-08T10:51:33Z (GMT). No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) Previous issue date: 2016-04-01 / Outra / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / The object of this study is the routing and scheduling problem of vessels with pickup and delivery and time windows in the oil industry. A case study was performed in a Brazilian oil industry that produces crude oil in o shore platforms, that is, located in the ocean, and transports to the terminals located in the Brazilian coast. Then, it was proposed a mixed integer model to represent the problem adequately and for this, a detailed analysis of the real problem in order to know all its characteristics and consider some simplifying assumptions. Therefore, to the pickup and delivery problem with time windows present in the literature were aggregated other speci c restrictions of the case study, for example, multiple depots, ship mooring restrictions, exible draft and dynamic positioning. Besides that, the eet is heterogeneous related to capacity, LOA (length overall), dynamic positioning and velocity. In practice, in general there are no identical vessels. This problem can be represented as a combinatorial optimization model, which belongs to the NP-hard class and its solution is a challenging in practice depending on the size of the real problems. Then, were proposed several exact branch-and-cut methods based on models with 2 and 3-index variables for routing problems with pickup and delivery and time windows to solve speci cally the Brazilian oil industry problem. Finally, we proposed a branch-and-price method, which includes all characteristics of the problem in oil industry. In summary, the main contributions of this thesis are related to the study and modeling of this problem in practice, and the proposal and development of exact solution methods to solve it, based on branch-and-cut and branch-and-price. The performance of the mathematical model in optimization software and the exact methods were veri ed using a real data set provided by the company. Results show that these approaches may be e ective to solve problems of moderate size in real situations. / O objeto de estudo deste trabalho é o problema de roteamento e programação de navios com coleta e entrega e janelas de tempo na indústria petrolífera. Foi realizado um estudo de caso com uma empresa petrolífera brasileira que produz óleo cru em plataformas o shore, isto é, localizadas no oceano e os transporta até os terminais localizados na costa brasileira. Então, foi proposto um modelo de programação inteira mista para representar o problema adequadamente e para isso, foi necessária uma análise detalhada do problema real, com o intuito de conhecer todas as suas características e considerar hipóteses simpli cadoras. Desta maneira, ao problema de coleta e entrega e janelas de tempo da literatura foram agregadas outras restrições especí cas do problema do estudo de caso como, por exemplo, múltiplos depósitos, restrições de atracação dos navios, calado exível e posicionamento dinâmico. Além disso, a frota de navios é heterogênea em relação à capacidade, LOA (length overall ), posicionamento dinâmico e velocidade. Na prática, em geral não existem navios iguais. Este problema pode ser representado como um modelo de otimização combinatória que pertence à classe NP-difícil e sua solução é bastante desa adora na prática em função do tamanho dos problemas reais. Depois, foram propostos vários métodos do tipo branch-and-cut baseados em modelos com variáveis de 2 e 3-índices para problemas de roteamento com coleta e entrega e janelas de tempo para resolver especi camente o problema da empresa brasileira. E por m, foi proposto um método do tipo branch-and-price, o qual abrange todas as características do problema da indústria petrolífera. Em síntese, as principais contribuições desta tese referem-se ao estudo e modelagem deste problema na prática, e a proposta e desenvolvimento de métodos de solução exatos para resolvê-lo, baseados em branch-and-cut e branch-and-price. O desempenho do modelo matemático em softwares de otimização e também dos métodos exatos propostos foi veri cado usando-se exemplares reais fornecidos pela empresa. Os resultados mostram que essas abordagens podem ser efetivas para resolver problemas de tamanho moderado em situações reais.