The United States Navy Meteorology and Oceanography (METOC) community routes ships for weather evasion using advanced meteorological modeling and satellite data, but lacks a tool to enable fewer ship routers to make better routing decisions faster. Limited resources and rising costs are impacting the frequency and duration of current naval operations. The Commander, Naval Meteorology and Oceanography Command has ordered the community to find efficiencies and automation possibilities in order to meet lower manning levels, reduce waste, and increase savings. Outside of the Navy, Ocean Systems Incorporated in Alameda, CA developed the Ship Tracking and Routing System (STARS) software package to calculate optimum sea routes based on weather model data. However, METOC ship routers are reluctant to adopt this complex software. To help solve this, we modeled Optimum Track Ship Routing (OTSR) for U.S. Navy warships using a network graph of the Western Pacific Ocean. A binary heap version of Dijkstra's algorithm determines the optimum route given model generated wind and seas input. We test the model against recent weather data to verify the model's performance, and to historical divert route recommendations in order to validate against routes developed by OTSR personnel.

Thesis (M.S. in Operations Research)--Naval Postgraduate School, March 2008. / Thesis Advisor(s): Wood, R. Kevin. "March 2008." Includes bibliographical references (p. 37-38). Also available online.

Thesis (M.S. in Operations Research)--Naval Postgraduate School, June 2005. / Thesis Advisor(s): Gerald G. Brown. Includes bibliographical references (p. 73-74). Also available online.

Thesis (Ph. D.)--Industrial and Systems Engineering, Georgia Institute of Technology, 2005. / I. A. Karimi, Committee Member ; Shabbir Ahmed, Committee Member ; Faiz Al-Khayyal, Committee Chair Chelsea (Chip) C. White III, Committee Member ; Earl Barnes, Committee Member. Includes bibliographical references.

This thesis describes a stochastic ship routing problem with inventory management. The problem involves finding a set of least costs routes for a fleet of ships transporting a single commodity when the demand for the commodity is uncertain. Storage at consumption and supply ports is limited and inventory levels are monitored in the model. Consumer demands are at a constant rate within each time period in the deterministic problem, and in the stochastic problem, the demand rate for a period is not known until the beginning of that period. The demand situation in each time period can be described by a scenario tree with corresponding probabilities. Several possible solution approaches for solving the problem are studied in the thesis. This problem can be formulated as a mixed integer programming (MIP) model. However solving the problem this way is very time consuming even for a deterministic problem with small problem size. In order to solve the stochastic problem, we develop a decomposition formulation and solve it using a Branch and Price framework. A master problem (set partitioning with extra inventory constraints) is built, and the subproblems, one for each ship, involve solving stochastic dynamic programming problems to generate columns for the master problem. Each column corresponds to one possible tree of schedules for one ship giving the schedule for the ship for all demand scenarios. In each branch-and-bound node, the node problem is solved by iterating between the master problem and the subproblems. Dual variables can be obtained solving the master problem and are used in the subproblems to generate the most promising columns for the master problem. Computational results are given showing that medium sized problems can be solved successfully. Several extensions to the original model are developed, including a variable speed model, a diverting model, and a model which allows ships to do extra tasks in return for a bonus. Possible solution approaches for solving the variable speed and the diverting model are presented and computational results are given.

This research deals with chemical transport Problems involving maritime pick up from and delivery to storage tanks that are continuously filled and drained. More specifically, we developed decision technology to determine the efficient use of multi compartment bulk ships to transport chemical products while ensuring continuous production with no stock-outs, so that the inventory level of chemical products in storage tanks are maintained between prescribed upper and lower stock levels during the planning horizon. Due to the nature of the products, it is impossible to carry more than two products without these being separated into dedicated compartments of the ships. We need to decide how much of each product to carry, on which ship, subject to the conditions that all harbors must have sufficient product to meet demand, and the stock levels of the products cannot exceed the inventory capacity of that harbor. We have formulated this ship-routing problem as a combined multi-ship pickup-delivery problem with inventory constraints. The original problem is a large-scale non-convex mixed-integer programming problem. All non-convexities involved weighted sums of products of two variables, one of which is binary and the other is continuous but bounded. We have shown that the structure gives rise to an equivalent large-scale linear mixed-integer programming problem (MILP). We studied the underlying structure of the MILP and developed a solution strategy by Lagrangian relaxation method for this large scale MILP with special structure. We also devised heuristic methods that are fast and find a good solution and conducted numerical studies that show how good does the heuristic solution compared to the dual bounds.

Thesis (Ph.D)--Industrial and Systems Engineering, Georgia Institute of Technology, 2007. / Committee Chair: Al-Khayyal, Faiz; Committee Member: Barnes, Earl; Committee Member: Johnson, Ellis; Committee Member: Karimi, IA; Committee Member: Sokol, Joel.

Thesis (Ph. D.)--Industrial and Systems Engineering, Georgia Institute of Technology, 2008. / Professor Michael D. Meyer, Committee Member ; Professor Ozlem Ergun, Committee Chair ; Professor Ellis Johnson, Committee Member ; Professor George L. Nemhauser, Committee Member ; Professor H. Venkateswaran, Committee Member.

Thesis. 1978. Ph.D.--Massachusetts Institute of Technology. Dept. of Ocean Engineering. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING / Includes bibliographical references. / by H.T. Chen. / Ph.D.

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