A presente pesquisa aborda um problema de roteirização e programação de veículos incorporando uma nova restrição operacional: a requisição simultânea de múltiplos veículos para atendimento da demanda. Trata-se de uma característica encontrada em operações de apoio à exploração de petróleo \"offshore\", em que mais de uma embarcação é requerida para executar tarefas de reboque e lançamento de linhas de ancoragem. Esta imposição, somada às restrições de janela de tempo, precedência entre tarefas, autonomia das embarcações e atendimento integral da demanda, configuram este problema. A programação é orientada pela minimização dos custos variáveis da operação e dos custos associados ao nível de serviço no atendimento. Este problema é uma variação do problema clássico de roteirização e programação de veículos com janela de tempo, de classe NP-Difícil. Nesta pesquisa, propõe-se modelar e resolver o problema em escala real por meio do algoritmo \"branch and cut\" acoplado às heurísticas de busca em vizinhança \"local branching\" e \"variable neighborhood search\". Para gerar as soluções iniciais será empregado o método \"feasibility pump\" e uma heurística construtiva. / This research focuses a fleet scheduling problem with new operational constraints: each task requiring multiple types of vehicles simultaneously. This kind of operation occurs in offshore exploitation and production sites, when more than one vessel is needed to accomplish the tugging and mooring of oil platforms. Other constraints are maintained such as time windows, precedence between tasks, route duration and the demand attendance. The solution schedules are cost oriented, which encompasses the routing variable costs and the customer service costs. This is a variation of the classical fleet routing and scheduling, which is an NP-Hard problem. This research aims to solve the real scale problem through a combined use of branch and cut strategy with local search algorithms such as local branching and variable neighborhood search. An efficient heuristic rule will be used in order to generate initial solutions using the feasibility pump method.

The issues of global warming and climate change are a worldwide concern and the UK government has committed itself to major reductions in CO2 emissions, the most significant of the six greenhouse gases. Road transport currently accounts for about 22% of total UK emissions of CO2, and has been steadily rising. Therefore, initiatives are required to try and reduce the gas emissions in this sector. The aim of this research has been to develop a computer based vehicle routing model that calculates the overall amount of CO2 emitted from road journeys, as well as time and distance. The model has been used to examine a number of delivery strategies to assess how CO2 emissions vary. The aim has not been to produce new mathematical theories, but to produce an innovative basis for routing which will provide new information and knowledge about how CO2 emissions vary for different minimisation and congestion criteria. The approach used in this research brings together elements from transportation planning and environmental modelling combined with logistics based vehicle routing techniques. The model uses a digitised road network containing predicted traffic volumes, to which speed flow formulae are applied so that a good representation of speed can be generated on each of the roads. This means that the model is uniquely able to address the issue of congestion in the context of freight vehicle routing. It uses driving cycle data to apply variability to the generated speeds to reflect acceleration and deceleration so that fuel consumption, and therefore CO2, can be estimated. Integrated within the model are vehicle routing heuristics to enable routes to be produced which minimise the specified criterion of time, distance or CO2. The results produced by the model show that there is a potential to reduce CO2 emissions by about 5%. However, when other transport externalities are considered overall benefits are dependent on road traffic volumes.

The issues of global warming and climate change are a worldwide concern and the UK government has committed itself to major reductions in CO2 emissions, the most significant of the six greenhouse gases. Road transport currently accounts for about 22% of total UK emissions of CO2, and has been steadily rising. Therefore, initiatives are required to try and reduce the gas emissions in this sector. The aim of this research has been to develop a computer based vehicle routing model that calculates the overall amount of CO2 emitted from road journeys, as well as time and distance. The model has been used to examine a number of delivery strategies to assess how CO2 emissions vary. The aim has not been to produce new mathematical theories, but to produce an innovative basis for routing which will provide new information and knowledge about how CO2 emissions vary for different minimisation and congestion criteria. The approach used in this research brings together elements from transportation planning and environmental modelling combined with logistics based vehicle routing techniques. The model uses a digitised road network containing predicted traffic volumes, to which speed flow formulae are applied so that a good representation of speed can be generated on each of the roads. This means that the model is uniquely able to address the issue of congestion in the context of freight vehicle routing. It uses driving cycle data to apply variability to the generated speeds to reflect acceleration and deceleration so that fuel consumption, and therefore CO2, can be estimated. Integrated within the model are vehicle routing heuristics to enable routes to be produced which minimise the specified criterion of time, distance or CO2. The results produced by the model show that there is a potential to reduce CO2 emissions by about 5%. However, when other transport externalities are considered overall benefits are dependent on road traffic volumes.

Made available in DSpace on 2016-06-02T19:52:13Z (GMT). No. of bitstreams: 1 DissJMRB.pdf: 944400 bytes, checksum: b37a0f175baab577681e6785f305edee (MD5) Previous issue date: 2005-06-23 / This project consists in the refinement of the tabu search adaptive approach HTSA (PUREZA, 1996) and the analysis of its performance when applied to the classical Vehicle Routing Problem and to the Vehicle Routing Problem with Time Windows. HTSA promotes the integration of intensification and diversification strategies through the systematic variation of the values of selected tabu parameters, mostly based on the analysis of search trajectory patterns. The development of new implementations based on tabu search (GLOVER, 1989; GLOVER & LAGUNA, 1997) is an interesting avenue of research since tabu search has offered new marks on solution quality in routing problems, usually outperforming other methods. The results obtained with the application of HTSA approach to a set of classical routing instances and to a set of routing with times windows instances indicate quality solutions within reasonable computational times when compared to the results provided by competitive methods in the literature. / O corrente projeto tem como objetivo o refinamento da abordagem adaptativa de busca tabu HTSA (PUREZA, 1996) e a verificação de seu desempenho quando aplicada ao Problema de Roteirização de Veículos clássico e ao Problema de Roteirização com Janelas de Tempo. A abordagem HTSA tem como objetivo a integração de estratégias de intensificação e diversificação, consistindo na variação sistemática de valores de parâmetros tabu selecionados e apoiada principalmente na análise de padrões da trajetória da busca. O desenvolvimento de novas abordagens baseadas na meta-heurística busca tabu (GLOVER, 1989; GLOVER & LAGUNA, 1997) é uma linha de pesquisa interessante uma vez que a busca tabu tem oferecido novas marcas em qualidade da solução em problemas de Roteirização de veículos e suas variantes, geralmente superando outros métodos. Os resultados obtidos com a aplicação da abordagem HTSA a instâncias de roteirização de veículos clássicas e com janela de tempo indicam soluções de qualidade em tempos computacionais razoáveis quando comparadas aos resultados de métodos competitivos da literatura.

A presente pesquisa aborda um problema de roteirização e programação de veículos incorporando uma nova restrição operacional: a requisição simultânea de múltiplos veículos para atendimento da demanda. Trata-se de uma característica encontrada em operações de apoio à exploração de petróleo \"offshore\", em que mais de uma embarcação é requerida para executar tarefas de reboque e lançamento de linhas de ancoragem. Esta imposição, somada às restrições de janela de tempo, precedência entre tarefas, autonomia das embarcações e atendimento integral da demanda, configuram este problema. A programação é orientada pela minimização dos custos variáveis da operação e dos custos associados ao nível de serviço no atendimento. Este problema é uma variação do problema clássico de roteirização e programação de veículos com janela de tempo, de classe NP-Difícil. Nesta pesquisa, propõe-se modelar e resolver o problema em escala real por meio do algoritmo \"branch and cut\" acoplado às heurísticas de busca em vizinhança \"local branching\" e \"variable neighborhood search\". Para gerar as soluções iniciais será empregado o método \"feasibility pump\" e uma heurística construtiva. / This research focuses a fleet scheduling problem with new operational constraints: each task requiring multiple types of vehicles simultaneously. This kind of operation occurs in offshore exploitation and production sites, when more than one vessel is needed to accomplish the tugging and mooring of oil platforms. Other constraints are maintained such as time windows, precedence between tasks, route duration and the demand attendance. The solution schedules are cost oriented, which encompasses the routing variable costs and the customer service costs. This is a variation of the classical fleet routing and scheduling, which is an NP-Hard problem. This research aims to solve the real scale problem through a combined use of branch and cut strategy with local search algorithms such as local branching and variable neighborhood search. An efficient heuristic rule will be used in order to generate initial solutions using the feasibility pump method.

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.