This dissertation explores mathematical programming optimization models and algorithms for routing and scheduling ships in a maritime transportation system. Literature surveyed on seaborne transportation systems indicates that there is a scarcity of research on ship routing and scheduling problems. The complexity and the overwhelming size of a typical ship routing and scheduling problem are the primary reasons that have resulted in the scarcity of research in this area. The principal thrust of this research effort is focused at the Kuwait Petroleum Corporation (KPC) Problem. This problem is of great economic significance to the State of Kuwait, whose economy has been traditionally dominated to a large extent by the oil sector. Any enhancement in the existing ad-hoc scheduling procedure has the potential for significant savings. A mixed-integer programming model for the KPC problem is constructed in this dissertation. The resulting mathematical formulation is rather complex to solve due to (1) the overwhelming problem size for a typical demand contract scenario, (2) the integrality conditions, and (3) the structural diversity in the constraints. Accordingly, attempting to solve this formulation for a typical demand contract scenario without resorting to any aggregation or partitioning schemes is theoretically complex and computationally intractable. Motivated by the complexity of the above model, an aggregate model that retains the principal features of the KPC problem is formulated. This model is computationally far more tractable than the initial model, and consequently, it is utilized to construct a good quality heuristic solution for the KPC problem. The initial formulation is solved using CPLEX 4.0 mixed integer programming capabilities for a number of relatively small-sized test cases, and pertinent results and computational difficulties are reported. The aggregate formulation is solved using CPLEX 4.0 MIP in concert with specialized rolling horizon solution algorithms and related results are reported. The rolling horizon solution algorithms enabled us to handle practical sized problems that could not be handled by directly solving the aggregate problem. The performance of the rolling horizon algorithms may be enhanced by increasing the physical memory, and consequently, better solutions can be extracted. The potential saving and usefulness of this model in negotiation and planning purposes strongly justifies the acquisition of more computing power to tackle practical sized test problems. An ad-hoc scheduling procedure that is intended to simulate the current KPC scheduling practice is presented in this dissertation. It is shown that results obtained via the proposed rolling horizon algorithms are at least as good, and often substantially better than, results obtained via this ad-hoc procedure. / Ph. D.

De acordo com Babu et al. (2015), o carvão mineral é um importante recurso natural devido à sua aplicação em várias atividades econômicas, como geração de energia, produção de aço, fabricação de cimento e produção de combustível líquido. Em função do custo e da baixa qualidade do carvão brasileiro (não coqueificável, na maioria das reservas, com elevado teor de cinzas e baixo poder calorífico), como apontado por Süffert (1997), as empresas brasileiras dos setores siderúrgico e termoelétrico necessitam importar este insumo, por via marítima. O desafio no planejamento da logística de suprimento desta matéria prima é garantir o abastecimento ao mínimo custo de estoque e de espera dos navios. A garantia de abastecimento passa por uma programação adequada da chegada e descarga dos navios. Quando a descarga de navios é uma operação gargalo, é necessário maior cuidado com a programação de recebimento, de maneira com que não haja atrasos, que causem a falta de produto, nem em muita antecipação, que podem significar excessivos tempo de fila para recebimento do material por falta de área para estocagem. Com o objetivo de se programar adequadamente a chegada de navios, de forma a evitar filas muito grandes e desabastecimento foi proposto um modelo de programação de chegada de navios, com base nos dados do complexo de Pecém. Este modelo proposto utilizou um buffer de tempo pré-determinado, que foi testado e validado através de simulação, com objetivo de minimizar os atrasos, de forma que possam ser absorvidos por um estoque de segurança, e as antecipações, de forma que não haja risco de falta de área de estocagem. / According to Babu et al. (2015), coal is an important natural resource due to its application in various economic activities, such as power generation, steel production, cement manufacturing and liquid fuel production. Due to the cost and low quality of Brazilian coal (not coking, in most reserves, with high ash content and low calorific value), as pointed out by Süffert (1997), Brazilian companies in the steel and thermoelectric sectors need to import this input, by sea. The challenge in planning the logistics of supply of this raw material is to guarantee the supply at the minimum cost of inventory and waiting of the ships. The supply guarantee is subject to adequate scheduling of arrival and unloading of ships. When ship unloading is a bottleneck operation, greater care is required with the scheduling of receipt, so that there are no delays, which cause the lack of product, or in much anticipation, that can mean excessive queue time for receiving the shipment material for lack of storage area. In order to properly program, the arrival of ships, in order to avoid very large queues and shortage, a model for the arrival of ships was proposed, based on data from the Pecém complex. This proposed model used a pre-determined time buffer, which was tested and validated through simulation, in order to minimize the delays, so that they can be absorved by a security stock, and the anticipations, so that there is no risk lack of storage area.

De acordo com Babu et al. (2015), o carvão mineral é um importante recurso natural devido à sua aplicação em várias atividades econômicas, como geração de energia, produção de aço, fabricação de cimento e produção de combustível líquido. Em função do custo e da baixa qualidade do carvão brasileiro (não coqueificável, na maioria das reservas, com elevado teor de cinzas e baixo poder calorífico), como apontado por Süffert (1997), as empresas brasileiras dos setores siderúrgico e termoelétrico necessitam importar este insumo, por via marítima. O desafio no planejamento da logística de suprimento desta matéria prima é garantir o abastecimento ao mínimo custo de estoque e de espera dos navios. A garantia de abastecimento passa por uma programação adequada da chegada e descarga dos navios. Quando a descarga de navios é uma operação gargalo, é necessário maior cuidado com a programação de recebimento, de maneira com que não haja atrasos, que causem a falta de produto, nem em muita antecipação, que podem significar excessivos tempo de fila para recebimento do material por falta de área para estocagem. Com o objetivo de se programar adequadamente a chegada de navios, de forma a evitar filas muito grandes e desabastecimento foi proposto um modelo de programação de chegada de navios, com base nos dados do complexo de Pecém. Este modelo proposto utilizou um buffer de tempo pré-determinado, que foi testado e validado através de simulação, com objetivo de minimizar os atrasos, de forma que possam ser absorvidos por um estoque de segurança, e as antecipações, de forma que não haja risco de falta de área de estocagem. / According to Babu et al. (2015), coal is an important natural resource due to its application in various economic activities, such as power generation, steel production, cement manufacturing and liquid fuel production. Due to the cost and low quality of Brazilian coal (not coking, in most reserves, with high ash content and low calorific value), as pointed out by Süffert (1997), Brazilian companies in the steel and thermoelectric sectors need to import this input, by sea. The challenge in planning the logistics of supply of this raw material is to guarantee the supply at the minimum cost of inventory and waiting of the ships. The supply guarantee is subject to adequate scheduling of arrival and unloading of ships. When ship unloading is a bottleneck operation, greater care is required with the scheduling of receipt, so that there are no delays, which cause the lack of product, or in much anticipation, that can mean excessive queue time for receiving the shipment material for lack of storage area. In order to properly program, the arrival of ships, in order to avoid very large queues and shortage, a model for the arrival of ships was proposed, based on data from the Pecém complex. This proposed model used a pre-determined time buffer, which was tested and validated through simulation, in order to minimize the delays, so that they can be absorved by a security stock, and the anticipations, so that there is no risk lack of storage area.

[pt] Empresas de exploração de petróleo e gás offshore frequentemente precisam lidar com problemas relacionados ao uso eficiente de seus recursos. Neste trabalho, abordamos um problema de programação de navios associado à logística offshore de petróleo e gás – O Problema de Programação de Embarcações do tipo Pipe-Laying support Vessel (PLSVSP). Essas embarcações são especialmente projetadas para realizar conexões de dutos entre poços de petróleo submarinos e plataformas de produção. A conexão de dutos é a última etapa a ser executada para permitir a drenagem do óleo e iniciar a produção em um poço. No PLSVSP, o objetivo é antecipar a conclusão de poços mais produtivos. O problema pode ser visto como uma variante de um problema de programação de lotes com máquinas paralelas idênticas e tempos de configuração não antecipados por família para minimizar o total weighted completion time. Nessa analogia, embarcações são as máquinas, poços são as tarefas e lotes são as viagens executadas por PLSVs, definindo quais poços devem ser conectados a cada saída do porto. Foram desenvolvidas diversas abordagens de otimização para resolver as variantes determinística e estocástica do problema. Para a variante determinística, desenvolvemos métodos híbridos e uma metaheurística capazes de melhorar as soluções desenvolvidas por formulações MIP puras e lidar com o PLSVSP. Para a variante estocástica, foi desenvolvida uma simheurística utilizando simulação de Monte Carlo incorporada, considerando incertezas nas durações das conexões e nas datas de chegada dos oleodutos no porto. Os resultados mostram uma melhora significativa no custo das soluções quando lidam com incertezas em comparação com soluções geradas por um método determinístico. O uso da simulação em uma estrutura metaheurística mostrou-se uma abordagem promissora, capaz de lidar com o problema estocástico, com pouco esforço computacional extra necessário. / [en] Offshore oil and gas exploration companies frequently need to deal with problems related to the efficient use of their resources. In this work, we address a ship scheduling problem associated with offshore oil and gas logistics – The Pipe Laying Support Vessel Scheduling Problem (PLSVSP). These vessels are specially designed to perform pipeline connections between sub-sea oil wells and production platforms. The connections are the last step to be performed to allow the oil draining, starting production in a well. The PLSVSP objective is to anticipate the completion of the most productive wells. The problem can be seen as a variant of a batch scheduling problem with identical parallel machines and non-anticipatory family setup times to minimize the total weighted completion time. In this analogy, vessels are machines, wells are jobs, and batches are voyages executed by PLSVs, defining which wells to connect each time it leaves the port. We developed several optimization approaches to solve the deterministic and stochastic variants of the problem. For the deterministic problem, we developed hybrid methods and a metaheuristic that outperformed the pure MIP formulations, being practical to deal with the PLSVSP. A simheuristic using embedded Monte Carlo simulation was developed for the stochastic variant of the problem, considering uncertainties in the connection duration and the arrival dates of pipelines at the port. The results show a significant improvement in the solutions dealing with uncertainties compared to solutions generated by a deterministic method. The use of simulation within a metaheuristic framework proved to be a promising approach, being able to deal with the stochastic problem, with little extra computational effort required.