Almost everywhere, routing plays an important role in everyday life. This thesis consists of three parts, each studying different applications where routing decisions are coordinated with other decisions. A common denominator in all applications is that an intelligent utilization of a fleet of vehicles is crucial for the performance of the system. In the first part, routing and inventorymanagement decisions are coordinated, in the second part, routing decisions concerning different modes of transportation are coordinated with inventory management, and in the third part, location decision and routing are coordinated. In the first part, an application concerning waste management is presented. Many industries generate garbage, and instead of handling the waste disposal themselves, other companies, specialized in garbage collection, handle the disposal. Each industry rents containers from a company to be used for waste, and the garbage collection companies handle the collection. The industries buy a service including one or more containers at the industry and the garbage collection companies are obliged to make sure that the containers never become overfull. The idea is that the industries buy this service and in return, the garbage collection company can plan the collection so that the overall cost and the number of overfull containers is minimized. Two models for the problem facing the garbage collection company are proposed. The first is solved using a Lagrangean relaxation approach on a flow based model, and the second is solved using Benders decomposition on a column based model. The second part investigates a distribution chain management problem taken from the Swedish pulp industry. Given fixed production plans at the mills, and fixed customer demands, the problem is to minimize the distribution cost. Unlike many other models for marine distribution chains, the customers are not located at the harbors. This means that the model proposed also incorporates the distribution planning from the harbors to the customers. All customers are not served from the harbors; some are served directly from the mills using trucks and trains to distribute the pulp, and these decisions are also included. The problem is modeled as a mixed integer linear program and solved using a branch and price scheme. Due to the complexity of the problem, the solution strategy is divided into two phases, where the first emphasizes the generation of schedules for the vessels operated by the company, while the second deals with the chartering of vessels on the spot market. In the third part, routing is combined with location decisions in the location-routing problem. Special emphasis is given to strategic management where decision makers must make location, capacity and routing decisions over a long planning period. The studied application comes fromstrategic schoolmanagement, where the location and capacity of the schools as well as their catchment areas are under consideration. The problem is modeled as a mixed integer linear program. The computational study shows the importance of incorporating a routing component allowing multiple visits, as well as the danger of having a too short planning period.

[pt] A organização da operação do transporte marítimo pode ser descrita dentre três modelos: liner, industrial ou tramp. No setor de tramp, armadores buscam otimizar os lucros através de ganhos de capacidade e redução de custos, ao mesmo tempo em que atendem às demandas e às restrições colocadas pelos clientes, muitas vezes baseadas em contratos. O roteamento de navios se torna um tema relevante dado que disponibilidade e confiabilidade de datas são um grande diferencial, ainda mais no atual contexto de alta oferta de navios tramp no mercado e, consequentemente, fretes mais baixos. Assim, o objetivo desse trabalho é apresentar um modelo de programação inteira mista visando a maximização do lucro de viagens pertencentes a uma específica rota geográfica de uma empresa tramp. O problema trabalhado nessa dissertação é do tipo pick-up e delivery (coleta e entrega) com janelas de tempo, múltiplas cargas a bordo, frota heterogénea, cargas fracionadas entre navios, velocidades de navegação variáveis e termos de tempo de trânsito garantidos. Utilizando-se da otimização Branch-and-Bound, o modelo é comparado com programações mensal real feita de maneira empírica por profissionais experientes dessa empresa em que o modelo matemático gera soluções com reduções de até 7 por cento dos custos totais e desafiando paradigmas estabelecidos pelos programadores quando da realização do roteamento e programação dos navios. Tendo em vista tais resultados, o modelo se apresentou como oportunidade de implementação e melhoria do processo de programação dos navios e do nível de serviço junto aos clientes. / [en] The organization of the maritime transport operation can be defined among three models: liner, industrial or tramp. In the tramp sector, shipowners seek to optimize profits through capacity gains and cost savings, while meeting the demands and constraints placed by customers, often based on contracts. Vessel routing becomes as availability and reliability of dates is a great differential, especially in the current context of a high supply of tramp vessels in the market and, consequently, lower freight rates. Thus, the hereby objective is to present a mixed integer programming model aiming to maximize the profit of all voyages belonging to a specific geographical route of a tramp company. The problem solved with in this work can be defined as of pick-up and delivery with time windows, multiple cargoes on board, heterogeneous fleet, split loads, variable sailing speeds and guaranteed transit time terms. Using Branch-and-Bound optimization, the model is compared to actual monthly routing planning made empirically by experienced professionals of that company and the mathematical model generates solutions with reductions of up to 7 percent of total costs and challenging programmers established paradigms when routing and programming vessels. In view of these results, the model presented itself as an opportunity to be implemented and improve the vessel routing and planning process and level of service to customers.

In maritime transportation, liner shipping accounts for over 60\% of the value of goods shipped. However, very limited literature is available on the study of various problems in liner shipping. In this thesis we focus on problems related to this industry. Given a set of cargo to be transported, a set of ports and a set of ships, a common problem faced by carriers in liner shipping is the design of their service network. We develop an integrated model to design service network for the ships and to route the available cargo, simultaneously. The proposed model incorporates many relevant constraints, such as the weekly frequency constraint on the operated routes, and emerging trends, such as obtaining benefits from transshipping cargo on two or more service routes, that appear in practice but have not been considered previously in literature. Also, we design exact and heuristic algorithms to solve the integer program efficiently. The proposed algorithms integrate the ship scheduling problem, a tactical planning level decision, and the cargo routing problem, an operational planning level decision, and provide good overall solution strategy. Computational experiments indicate that larger problem instances, as compared to the literature, can be solved using these algorithms in acceptable computational time. Alliance formation is very common among global liner carriers however a quantitative study of liner alliances is missing from literature. We provide a mathematical framework for the quantitative study of these alliances. For the formation of a sustainable alliance, carriers need to agree on an overall service network and resolve issues concerning distribution of benefits and costs among the members of the alliance. We develop mechanisms to design a collaborative service network and to manage the interaction among the carriers through the allocation of profits in a fair way. The mechanism utilizes inverse optimization techniques to obtain resource exchange costs in the network. These costs provide side payments to the members, on top of the revenue generated by them in the collaborative solution, to motivate them to act in the best interest of the alliance while satisfying their own self interests.

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

[pt] Este estudo apresenta um modelo de programação inteira mista para a roteirização de navios com controle de estoque nos portos para a movimentação de múltiplos produtos com uma frota heterogênea. O modelo contempla a possibilidade de transformação de produtos dentro de navios, o que representa uma flexibilidade para o modelo optar por qual produto utilizar para atender um cliente com demanda com qualidade flexível. Esta habilidade não foi encontrada em nenhum outro estudo. Ele também combina o atendimento de demandas obrigatórias com opcionais. O modelo então é aplicado em um caso real de movimentação de derivados escuros de petróleo em uma empresa de petróleo brasileira, cujo modelo atual utilizado apresenta problemas que dificultam seu uso. Devido ao longo tempo que leva para obter a solução ótima para estes tipos de modelos, são utilizadas as matheurísticas de relax-and-fix e fix-and-optimize para obter soluções boas em um tempo reduzido. São apresentados experimentos computacionais em uma série de cenários para validar a qualidade das soluções encontradas pelos métodos propostos, testando diferentes configurações e discretizações de tempo. Os resultados apresentados comprovam a superioridade dos métodos em comparação com o modelo matemático puro. O modelo proposto apresentou grande potencial de substituir o modelo atual da empresa e para alcançar a melhoria pretendida na programação dos navios. / [en] This dissertation presents a mixed integer program model to solve a ship routing and scheduling with stock control in ports, also known as maritime inventory routing. This model considers a heterogeneous fleet, carrying multiples products. It also has the ability to transform one product into another inside ships. This aspect allows the model to choose which product it wishes to deliver to a client with a less restrict quality specification in his demand. No model presented in other studies has this capability. Another possibility covered by this model is to combine mandatory demands with optional ones. The model is applied to a real case of maritime transportation of dirty oil products in a Brazilian oil company, whose current model has a series of small problems that hinders its use. Due to the long time it takes to get the optimal solution, the relax-and-fix and fix-andoptimize heuristics are used to get good solutions in a reduced time. With the use of computational experiments in a series of scenarios, it has proved the quality of the solutions found by the proposed methods, testing different configurations and discretizations of time. The results presented prove the superiority of the methods in comparison to the pure mathematical model. The proposed model has shown great potential to replace the current one and to achieve the improvement for the ship routing intended by the company.

This thesis introduces a new model formulation to solve routing and scheduling problems, with the main applications in answering routing and scheduling problems faced by a sea-cargo shipping company and a railroad company. For the work in sea-cargo routing and scheduling, we focus on the tramp shipping operation. Tramp shipping is a demand-driven type of shipping operation which does not have fixed schedules. The schedules are based on the pickup and download locations of profitable service requests. Given set of products distributed among a set of ports, with each product having pickup and download time windows and a destination port, the problem is to find the schedule for a fleet of ships that maximizes profit over a specified time horizon. The problem is modeled as a Mixed Integer Non-Linear Program and reformulated as an equivalent Mixed Integer Linear Program. Three heuristic methods, along with computational results, are presented. We also exploit the special structure enjoyed by our model and introduce an upper-bounding problem to the model. With a little modification, the model is readily extendable to reflect soft time windows and inter-ship cargo-transfers. The other part of our work deals with train routing and scheduling. A typical train shipment consists of a set of cars having a common origin and destination. To reduce the handling of individual shipments as they travel, shipments are grouped into blocks. The problem is that given sets of blocks to be carried from origins to destinations, construct the most cost effective train routes and schedules and determine block-to-train assignments, such that the number of block transfers (block swaps) between trains, the number of trains used, and some other cost measures are minimized. Incorporating additional precedence requirements, the modeling techniques from the shipping research are employed to formulate a mixed integer nonlinear program for this train routing and scheduling problem. Computational results are presented.