[pt] Os problemas advindos da área de logística de transportes, em especial no que diz respeito ao uso racional de frotas de veículos, são amplamente estudados na área de otimização combinatória. A natureza intrinsicamente combinatorial desses problemas sugere que boa parte deles pode ser formulada e resolvida como um problema de programação linear inteira. Contudo, a maioria dos algoritmos atualmente disponíveis não consegue encontrar, em tempos computacionais aceitáveis, a solução ótima para instâncias de porte razoável. O sucesso desses algoritmos tem sido limitado, em parte devido ao fato dos mesmos não explorarem avanços recentes na área de programação linear inteira. Algumas dessas novas técnicas e suas aplicações a problemas de roteamento de veículos são o objeto de estudo desta dissertação. Primeiro são apresentadas as técnicas básicas de decomposição de problemas de programação linear e linear inteira e de geração de colunas. A resolução de problemas de programação linear inteira neste contexto é tratada em seguida, com a descrição do algoritmo branch-and-bound e das variações branch-and-cut, branch-and-price e branch-and- cut-and-price. Em seguida são descritos problemas de roteamento onde essa metodologia foi aplicada. Inicialmente, é apresentado o problema de roteamente do veículos com restrição de capacidade, o PRVC. Em seguida são apresentados problemas de roteamento de veículos com janela de tempo e frota heterogenea. Para cada problema, descrevemos como as técnicas descritas acima foram aplicadas e os resultados computacionais para um grande número de instâncias. Finalmente, no último capítulo, mostramos um caso real da aplicação do problema de roteamento de veículos com janela de tempo e frota heterogênea, que é o caso do problema de distribuição de jornais numa grande empresa de comunicação do Rio de Janeiro. / [en] Optimization techniques have an important role in Transportation Logistics. The combinatorial nature of several problems related to this area seggests integer programming as a natural approach to solve them. Nevertheless, there are many cases in which instances of reasonable size are still beyond the resolution capability of the algotithms presented in the literature. The sucess of the known algotithms have therefore been limited partly to the fact that most of them have not incorporated any recent relevant advances in the combinatorial optimization field. Some of these new techniques and their applications are the main subject of this dissertation. Firstly, basic decomposition techniques for linear and integer programming problems, as well as the relates column generation approach are addressed. This is followed by the presentation of a reformulation technique for linear and integer programming, which is alternative to the well known Dantzig-Wolfe master program. The new possibilities arousing from this approach are explored and the resulting consequences to the standard branch-and-bound algotithm and its variations branch-and- cut, branch-and-prince and branch-and-cut-and-price are presented. Later, routing problems where this methodology was applied were addressed with the capacitated vehicle routing problems - CVRP and followed by vehicle routing problems with time windows and heterogeneous fleet. For each problem, it is described how the techniques mentioned above were reported. Finally, in the last time windows and heterogeneous fleet, which is the case of a newspaper distribution in a major communication company in Rio de Janeiro.

[pt] Uma das tarefas mais importantes na indústria de exploração e produção de petróleo é a discriminação litológica. Uma das principais fontes de informação para subsidiar a discriminação e caracterização litológica é a perfilagem que é corrida no poço. Porém, na grande maioria dos trabalhos os perfis utilizados na discriminação litológica são apenas aqueles disponíveis no domínio dos poços. Para que modelos de discriminação litológica possam ser extrapolados para além do domínio dos poços, faz-se necessário a utilização de características que estejam presentes tanto nos poços como fora deles. As características mais utilizadas para realizar esta integração rocha-perfil-sísmica são os atributos elásticos. Dentre os atributos elásticos o que mais se destaca é a impedância. O objetivo desta dissertação foi a utilização da programação genética como modelo classificador de atributos elásticos para a discriminação litológica. A proposta se justifica pela característica da programação genética de seleção e construção automática dos atributos ou características utilizadas. Além disso, a programação genética permite a interpretação do classificador, uma vez que é possível customizar o formalismo de representação. Esta classificação foi empregada como parte integrante do fluxo de trabalho estatístico e de física de rochas, metodologia híbrida que integra os conceitos da física de rochas com técnicas de classificação. Os resultados alcançados demonstram que a programação genética atingiu taxas de acertos comparáveis e em alguns casos superiores a outros métodos tradicionais de classificação. Estes resultados foram melhorados com a utilização da técnica de substituição de fluídos de Gassmann da física de rochas. / [en] One of the most important tasks in the oil exploration and production industry is the lithological discrimination. A major source of information to support discrimination and lithological characterization is the logging raced into the well. However, in most studies the logs used in the lithological discrimination are only those available in the wells. For extrapolating the lithology discrimination models beyond the wells, it is necessary to use features that are present both inside and outside wells. One of the features used to conduct this rock-log-seismic integration are the elastic attributes. The impedance is the elastic attribute that most stands out. The objective of this work was the utilization of genetic programming as a classifier model of elastic attributes for lithological discrimination. The proposal is justified by the characteristic of genetic programming for automatic selection and construction of features. Furthermore, genetic programming allows the interpretation of the classifier once it is possible to customize the representation formalism. This classification was used as part of the statistical rock physics workflow, a hybrid methodology that integrates rock physics concepts with classification techniques. The results achieved demonstrate that genetic programming reached comparable hit rate and in some cases superior to other traditional methods of classification. These results have been improved with the use of Gassmann fluid substitution technique from rock physics.

[pt] A natureza intrinsicamente combinatorial de muitos problemas advindos da área de logística de transportes, em especial aqueles que dizem respeito ao uso racional de frotas de veículos, sugere que boa parte dos mesmos pode ser formulada e resolvida como um problema de programação linear inteira. Contudo, a maioria dos algoritmos até o momento disponíveis não consegue encontrar, em tempos computacionais aceitáveis, a solução ótima para instâncias de porte razoável. O objeto de estudo desta tese é a exploração de técnicas mais recentes da área de programação linear inteira e suas aplicações a problemas de roteamento de veículos. A primeira parte da tese descreve, além das técnicas básicas de decomposição de problemas de programação linear e linear inteira e de geração de colunas, uma proposta de reformulação de problemas de programação linear inteira alternativa àquela que gera o tradicional problema mestre de Dantzig-Wolfe, geralmente utilizados em abordagens por geração de colunas. A resolução de problemas de programação linear inteira neste contexto é tratada em seguida, com a descrição do algoritmo branch-and-bound e das variações branch-and-cut, branch-and-price e branch-and-cut-and-price. Na segunda parte da tese, inicialmente, é apresentada a técnica denominada de Geração Projetada de Colunas e sua aplicação ao problema de Roteamento de Veículos com Restrição de Capacidade. Em seguida é abordada a resolução do problema de Roteamento de Veículos sobre Arcos, através de sua transformação ao primeiro problema citado e uso de um algoritmo branch-and- cut-and-price. Finalmente, é proposto um novo problema na área de redistribuição de veículos de aluguel, para o qual é proposta uma formulação segundo uma abordagem por geração de colunas. São apresentados, ainda, procedimentos para a geração de colunas e resultados computacionais obtidos com um algoritmo branch-and-price para essa formulação. / [en] Optimization techniques have an important role in Transportation Logistics. The combinatorial nature of the problems related to this area suggests integer programming as a natural approach to their resolution. Nevertheless there are many cases where even instances of reasonable size still beyond the resolution capability of the current known algorithms. The success of the known algorithms have therefore been limited. This can be justified by the fact the most of them leave important recent advances in the combinatorial optimization field unexplored. Some of these new techniques and their applications are the main subject of this thesis. In the first part, the basic decomposition techniques for linear and integer programming problems as well as the related column generation approach is addressed. This is followed by the presentation of a reformulation technique for linear and integer programming which is alternative to the well known Dantzig-Wolfe master program. The new possibilities coming from this approach are explored and the resulting consequences to the standard branch-and- bound algorithm and its variations branch-and-cut, branch-and- price and branchand- cut-and-price are presented. The second part of this text addresses the application of the metodologies described in part one to routing problems where capacity constraints are considered. First, a techinque named Projected Column Generation is described in the context of the Capacitated Vehicle Routing Problem. Then, it is presented a new transformation from the Capacitated Arc Routing Problem to the Capacitated Vehicle Routing Problem as well as a tailored branch-and-cut-and-price to solve this problem. Finally, a new problem in vehicle redistrubution is described together with a column generation approach for its resolution. Computational results for all applications are presented.

[pt] Este trabalho apresenta uma ferramenta de suporte à programação literária. Para seu desenvolvimento foi criado um framework de prestação dos serviços básicos requeridos por este tipo de ferramenta. Desenvolvido segundo uma arquitetura que o tornou flexível, via uma linguagem de extensão para definição de macros; eficiente, via um núcleo em C++ otimizado para realizar as operações a nível de caracter; e portável, graças a uma implementação em C/C++ padrão, o framework se mostrou adequado aos objetivos propostos. O desenvolvimento sobre este framework validou as soluções adotadas, resultando em uma ferramenta de ótimo desempenho. / [en] This thesis presents a support tool for literate programming.Its development was preceded by a research of the basic facilites usually required for programs of this class. After that, a framework has been developed to offer those facilites. The framework was developed in standard C++, in such away that would guarantee its portability. Its effciency is due to an optimzed kernel which performs all character-level operations, and a well defined application program interface(API)assures its fexibility.On top of this framework an access layer has been created using a confi- guration language. This layer allows that, through small programs written in the configuration language, a user can adapt the tool for diferent literate programming styles like modular or WWW-enabled documentation.

[pt] Métodos que combinam estratégias normalmente encontradas em algoritmos metaeurísticos com técnicas para resolver problemas de programação inteira mista (MIP) têm apresentado ótimos resultados nos últimos anos. Este trabalho propõe dois novos algoritmos nessa linha: um algoritmo que faz pós-processamento nas soluções encontradas pelo resolvedor MIP. Os dois algoritmos utilizam um novo tipo de vizinhança, chamada de vizinhança elipsoidal, que possui fortes semelhanças com as técnicas de relinking de algoritmos PR e que neste trabalho é generalizada e extendida para múltiplas soluções. O problema generalizado de alocação (GAP) é usado para os experimentos. São testados também um resolvedor MIP puro (ILOG CPLEX versão 11) e um algoritmo branch and price que utiliza as heurísticas RINS e guided dives. Os algoritmos testados são comparados entre e com heurísticas específicas para o GAP. Os resultados são satisfatórios e indicam que as vizinhanças elipsoidais conseguem frequentemente melhorar as soluções encontradas pelo resolvedor MIP, encontrando a melhor solução para algumas instâncias. / [en] Methods that mix strategies usually found in metaheristic algorithms with techniques to solve mixed integer programming problems (MIPs) have had great results over the past few years. This wprk proposes two new algorithms in this philosophy: one is based on the Path Relink (PR) metaheuristc, while the other one is a simple algorithm that does post-processing in the solutions found by the MIP solver. Both algorithms use a new neighborhood structure, called ellipsoidal neighborhood, that has strong resemblances with the relinking step from PR algorithms and that, in this work, is generalized and extended for multiple solutions. The generalized assignment problem (GAP) is used for the computational experiments. Also tested are MIP solver (ILOG CPLEX version 11) and a branch and price algorithm that uses the RINS and guides dives heuristics. The tested algorithms are compared among themselves and with GAP-specific heuristics. The results are satisfactory and show that the ellipsoidal neighborhood can frequently improve the solutions found by the MIP solver, even finding the best result for some instances.

[pt] As decisões de cunho operacional tomadas no dia-a-dia das atividades de programação de movimentação de petróleo têm um forte impacto sobre o custo total desta cadeia de suprimentos. O desafio das áreas que tomam estas decisões diárias é elaborar uma programação de movimentação com o menor custo, com um alto nível de confiança e que seja factível para um determinado horizonte de tempo. Neste contexto, a utilização de programação matemática na programação de refinarias, dutos e terminais da cadeia de petróleo e derivados vem atraindo atenção crescente da indústria de petróleo. Este trabalho apresenta uma formulação matemática baseada em Programação Linear Inteira Mista (MILP) para o problema da movimentação de petróleo de um terminal até uma refinaria. No caso estudado, a movimentação acontece através de navios que descarregam seu produto no terminal de São Francisco do Sul, localizado no Estado de Santa Catarina, passando pelo duto OSPAR até chegar a seu destino final – a Refinaria de Araucária (REPAR), localizada no Estado do Paraná. Os principais resultados do modelo são a programação do sequenciamento de qual navio irá atracar no terminal, qual petróleo será descarregado e qual o volume e tipo de petróleo que será bombeado no duto para chegar a refinaria. O objetivo do modelo é minimizar os custos operacionais tomando-se em consideração o atendimento à demanda da refinaria, restrições de capacidade, disponibilidade de petróleo, manutenção dos estoques da refinaria e o bombeio ou não durante o período conhecido como horosazonal. Cenários testados com dados fornecidos pela Petrobras demonstram que através dos resultados do modelo é possível definir se há necessidade de utilizar o duto durante o horário de ponta ou não, garantindo a contratação de energia previamente junto às concessionárias, evitando desta forma o pagamento de multas, reduzindo um custo evitável. A partir dos resultados numéricos, ficou comprovado que o modelo pode gerar uma programação de movimentação de petróleo otimizada, em cenários de uma semana e um mês, ou indicar que não existe programação viável para tal cenário. / [en] The operational decisions of crude oil scheduling activities taken on a daily basis have a strong influence upon the overall supply chain cost. The challenge is to create a crude oil schedule that minimizes the total cost, and at the same time is feasible considering a limited scheduling horizon. The use of mathematical programming for the oil industry has increasingly drawn attention. This study presents a mathematical programming model based on mixed integer linear programming (MILP) for the crude oil scheduling of a system connecting a terminal to a refinery. On the case studied, the transfer occurs through tankers that unload their crude oil on the São Francisco do Sul terminal, located at Santa Catarina state, going through the OSPAR pipeline until it reaches its final destiny – Araucaria refinery (REPAR), located at Paraná state. The main results of the model are the scheduling of ships at the terminal, the scheduling of the pipeline and stocks levels at the terminal and at the refinery. The main goal of this model is to minimize the cost involved in operation, meeting the refinery demand, oil supply, capacity constraints, and the maintenance of refinery crude oil stock levels. This formulation was applied to real scenarios, with time-horizon from a week to a month, and was effectively solved with the proposed solution approach.

[pt] Esta pesquisa tem por objetivo conceber um sistema de apoio à decisão ao centro de controle operacional no gerenciamento do tráfego ferroviário. O sistema consiste na resolução de conflitos entre trens. Esta pesquisa justifica- se devido à deficiência encontrada pelos controladores de tráfego na tomada de decisões. Atualmente, as prioridades dos trens são pré-estabelecidas e, a partir da análise de um gráfico feito à medida que os eventos ocorrem, o planejamento do despacho de trens é realizado. As prioridades podem ser modificadas ao longo do dia, a partir de alguma ordem superior. Assim, existe a necessidade do desenvolvimento de um novo sistema que auxilie os controladores de tráfego na determinação da melhor solução para os conflitos entre trens. Inicialmente, foram realizados os levantamentos bibliográficos e de dados. Na revisão bibliográfica, foram analisados o sequenciamento de trens, condições de ultrapassagem e de cruzamentos e modelos de programação de trens. Em seguida, foi aplicada uma heurística proposta por Leal (2003) desenvolvida a partir da formulação de Szpigel (1972) e implementada em um programa de computador, na linguagem delphi. Esta heurística apresenta uma solução para os conflitos entre trens. A aplicação foi baseada nos dados fornecidos pela empresa MRS logística, situada em Juiz de Fora (MG). A partir da solução gerada por Leal (2003), foi desenvolvido um gráfico no Excel, utilizando a linguagem visual basic, onde são analisadas as programações dos trens com a solução dos conflitos. O objetivo final desta pesquisa é sugerir uma ferramenta de auxílio para o gerenciamento do tráfego ferroviário, contribuindo para a evolução e eficiência das ferrovias no Brasil. / [en] The objective of this research is to conceive a decision support system for the operational control center in the railroad traffic management. The system consists of the resolution of conflict between trains. The justification of this research is due to the deficiency founded by controllers of traffic in the decisions making. Currently, the trains priorities are previously established and, through the analysis of a done graph to the measure that the events go happening, these priorities can be modified. Thus, there is the necessity of the development of a new system which helps the controllers in the determination of the best alternative. Initially, the bibliographical surveys and the data-collectings had been made. In the bibliographic revision, the sequenciament of trains, ultraticket and crossing conditions, and trains programming models had been analyzed. The next step was the application of an heuristic developed by Leal (2003), based in the formularization of Szpigel (1972), and implemented in a computer program, in the Delphi language, showing the solution of conflicts between trains. The application was based in the data of MRS logistic company, situated in Juiz De Fora (MG). From the solution generated for Leal (2003), a graph in the excel was developed, using visual basic language, and shows the programmings of the trains with conflits solution. The final objective is to suggest a tool for helping the railroad traffic management, contributing for the evolution and efficiency of the railroads in Brazil.

[pt] As companhias petrolíferas dedicam grande esforço para manter sua rentabilidade e melhorar sua eficiência, principalmente frente às incertezas presentes neste negócio. As empresas que pretendem manter a competitividade precisam planejar suas operações cada vez melhor e com maior segurança. Em face destas oportunidades e desafios, foi proposta no âmbito desta tese uma abordagem estocástica para o problema de planejamento operacional de refinarias. Neste sentido foi desenvolvido um modelo não-linear (NLP) de programação estocástica com dois estágios. O modelo proposto representa os processos de natureza não-linear presentes em uma refinaria, como as transformações químicas e o cálculo de qualidade dos derivados. Devido ao elevado nível de complexidade do problema NLP formulado, foram avaliados cinco métodos de solução associados aos principais solvers comerciais. Uma metodologia de geração de cenários e medidas de qualidade para árvore de cenários também foram definidas para representar adequadamente as incertezas presentes neste problema. A abordagem estocástica proposta neste trabalho foi avaliada considerando dados reais de uma refinaria brasileira. Os resultados finais desta pesquisa devem proporcionar avanços no processo de planejamento operacional de refinarias, explorando a técnica de programação não-linear (NLP) e os novos solvers disponíveis para problemas do tipo NLP. Pretende-se também gerar contribuições na área de programação estocástica, definindo medidas de qualidade para árvore de cenários que permitam uma melhor representação das incertezas e consequentemente um melhor uso da abordagem estocástica. / [en] Oil companies make a great effort to maintain profitability and improve efficiency, especially given the uncertainties present in this business. Companies that intend to remain competitive need to plan their operations better and with greater safety. In light of these opportunities and challenges, this thesis proposes a stochastic approach to the refinery operational planning problem. In this sense, a two-stage nonlinear stochastic programming model (NLP) developed. The proposed model is intended to adequately represent nonlinear processes encountered in a refinery, such as chemical transformations and calculations of the properties of the oil derivatives. Due to the high level of complexity of the NLP problem formulated, five solution methods associated with major commercial solvers were evaluated. A methodology for generating scenarios and quality measures for scenarios tree were also defined to properly represent the uncertainties present in this problem. The stochastic approach proposed in the present study was evaluated based on actual data from a Brazilian refinery. The final results of this research should provide advances in the processes of refinery operational planning exploiting the technique of nonlinear programming (NLP) and new solvers available for NLP-type problems. Another objective was to generate contributions in the field of stochastic programming by defining quality measures for scenario trees that allow a better representation of uncertainties and, consequently, better use of the stochastic approach.

[pt] A natureza incerta e a importância do mercado da soja para economia do Brasil são forças motrizes para melhorias no processo de planejamento da cadeia logística da soja. Esta tese apresenta um novo modelo matemático de programação estocástica para auxiliar no planejamento tático da cadeia logística da soja. Os principais componentes espaciais e temporais da indústria da soja, sob o ponto de vista do embarcador, são abordados no modelo. A função objetivo do modelo maximiza o lucro obtido com base na diferença entre a receita da venda de grãos, farelo e óleo de soja e os custos de transporte, processamento, armazenamento e venda de grãos, farelo e óleo de soja. As decisões relacionadas ao planejamento tático encontram-se dentro de um horizonte temporal de um ano. Aspectos inerentes aos contratos de transportes e de compra de soja em grão são incorporados no modelo. O modelo de programação estocástica proposto é linear de dois estágios com estrutura de recurso fixo. O modelo foi aplicado a um exemplo real com 21 pontos de origem, 11 silos, 6 fábricas de processamento, 5 pontos de mercado interno, 6 portos e 225 arcos de transportes, considerando 243 cenários, oriundos da combinação de quatro fontes de incertezas: preço de compra e venda da soja em grão, a demanda externa da soja em grão e a quebra de safra. / [en] The uncertain nature and importance of the soybean market for Brazils economy are driving forces for improvement in the planning process of soybeans supply chain. This thesis presents a new stochastic programming mathematical model to assist in tactical planning of the soybean logistics chain. The model was conceived as a tool to assist the decision making of any trader involved in this highly complex market. The main spatial and temporal components of the soybean industry are addressed in the model. The objective function of the model maximizes the profit achieved based on the difference between the revenue from the sale of grain, meal and oil and the costs of transportation, processing, storage and the sale of grain, meal and oil. The model is intended to be applied for decisions related to tactical planning within a time horizon of one year. Aspects related to transport and purchase of soybeans contracts are incorporated in the model. The stochastic programming model is linear of two-stage with fixed resource structure. The model was applied to a real example with 21 points of origin, 11 silos, 6 processing plants, 5 points of the internal market, 6 ports and 225 arcs of transport, considering 243 scenarios, derived from the combination of four sources of uncertainty: purchase price and sale price of soybeans, foreign demand of soybeans and crop failure.

[pt] Métodos de previsão são muito importantes para o desenvolvimento de diversas atividades no cotidiano produtivo de nossa sociedade. Vários modelos estatísticos são desenvolvidos até hoje, contudo possuem muitos pressupostos que devem ser seguidos com o intuito de se obter uma resposta aceitável. Modelos não estatísticos para prever séries temporais como os que envolvem Sistemas de Inferência Fuzzy (SIFs) fornecem uma descrição do processo de previsão por meio de regras linguísticas. Explora-se, nesta dissertação, o GPFIS-Forecast: versão do GPFIS - Sistema de Inferência Fuzzy Genético baseado em Programação Genética Multigênica - para previsão de série temporais univariadas. O modelo apresenta, em sua execução, quatro etapas básicas: Fuzzificação, Inferência, Defuzzificação e Avaliação. Em cada uma destas etapas, pode-se fazer uso de diferentes configurações, com implicações evidentes nos resultados finais. Este trabalho propõe o aperfeiçoamento do GPFIS-Forecast em duas vertentes principais:( i) aumentar a quantidade de possibilidades de configurações, avaliando se podem contribuir significativamente para a acurácia das previsões;(ii) adicionar informações complementares como alternativas para a interpretação do resultado do modelo, tendo como compromisso tanto a acurácia e quanto a interpretabilidade. Os estudos de caso demonstram que, em casos de séries temporais com pouca tendência, o GPFIS-Forecast apresenta uma acurácia entre as 10 melhores da competição NN3; quando há forte tendência, faz-se necessário o uso de pré-processamento, prejudicando a interpretabilidade do resultado. Os Limites de Previsão Fuzzy introduzidos neste trabalho agregam mais informação ao resultado da previsão pontual, apontando possíveis ajustes finais nas bases de regras de modelos com maior granularidade. / [en] Forecasting methods are very important for the development of various activities in everyday society. Several statistical models have been developed, but many assumptions must be made in order to obtain an acceptable response. Nonstatistical models for time series forecasting such as those involving systems Fuzzy Inference Systems (FIS) provide a description of the process through linguistic rules. This dissertation delves into GPFISForecast: a version of GPFIS - Fuzzy Inference System based on Multigene Genetic Programming - for univariate time series forecasting. This model consists of four basic stages: Fuzzification, Inference, Defuzzification and Evaluation. In each of these steps, different configurations will have distinct impacts on the results. This work proposes the improvement of GPFIS-Forecast along two main lines (i) increase the amount of possible configurations and assess their contribution to a better forecasting accuracy and (ii) add further information to the interpretation of results, keeping in mind both accuracy and interpretability. The case studies show that in the case of time series with small tendency, GPFIS-Forecast provides a good accuracy; when tendency is larger and pre-processing becomes necessary, interpretability is affected. The Fuzzy Forecasting Limits introduced here add more information to the result, pointing to possible adjustments to rule bases of models with greater granularity.