[pt] A alta complexidade do processo logístico de transporte ferroviário de carga, propicia um ambiente favorável para o desenvolvimento de ferramentas de apoio à decisão que possibilitam uma melhor utilização dos recursos envolvidos. Neste trabalho é apresentado um modelo de programação inteira original para o Problema da Alocação ótima de Vagões e Locomotivas no curto prazo (PAVL). Esse problema consiste em determinar a movimentação de vagões (carregados e vazios) e locomotivas na malha de maneira a maximizar o retorno obtido pela demanda atendida no período considerado. Além disso, é apresentada uma extensão para esse modelo onde se permite atrasar ou adiantar trens no primeiro dia do horizonte de planejamento. Esse problema foi resolvido de maneira ótima ou quase ótima em tempo razoável, tanto em termos acadêmicos como para sua utilização prática. São apresentados o problema, a formulação do modelo, as técnicas de pré-processamento utilizadas, assim como resultados computacionais de instâncias reais. / [en] The complexity of the logistic process in railway freight transportation provides a natural environment for the development of decision support tools that allow the companies to make a more efficient use of their resources. In this work we present an original integer programming model for the Cars and Locomotives short-term Allocation Problem. This problem consists in determining the movement of the cars (loaded and empty) and locomotives on the railway network in order to maximize the profit obtained with the requested demand in the given period. We also present an extension of the model in which certain delays and anticipations of trains on the first day of the period are allowed. For all instances tested, this problem was solved to optimality or near-optimality in a reasonable time, either for academic or practical purposes. We present a description of the problem, the mathematical formulation, the preprocessing techniques used, as well as the computational results obtained.

[pt] A organização lógica de data centers recai principalmente na questão estratégica de distribuir os serviços nos equipamentos de forma que os custos operacionais sejam os menores possíveis. Além desses custos, devem ser considerados outros aspectos que envolvem a interdependência de seus serviços internos e a distribuição entre suas localidades, visando assim melhorar a qualidade de seu produto aos seus clientes. Este trabalho explora o problema de atribuição de processos a máquinas do desafio ROADEF de 2012 pelos métodos de programação inteira e geração de colunas. Apresenta estratégias para lidar com as dificuldades numéricas encontradas. Na geração de colunas, analisa técnicas para acelerar a convergência, por meio de resolver o mestre restrito após cada variável, geração prévia de colunas e estabilização das variávies duais. Ao final do trabalho, são comparados os resultados obtidos com os melhores resultados oficiais. / [en] A data center logic organization lies mainly by the strategic decision on how distribute services between machines, so the operational costs should be the smallest as possible. Beside those costs, must also consider the interdependence of their own services, the distribution between their localities, to improve the quality of their product to their customers. This work explores the challenge ROADEF 2012 machine assignment problem by the means of integer programming and column generation. Shows strategies to address numeric issues. At column generation, it analyzes techniques to speed up the convergence, by solving after each variable adiction, a previous generation of columns and stabilization of duals variables. At the end of the work, it compares the results obtained are compared with the best official results.

[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] 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] Consideramos o Problema Quadrático da Mochila 0-1 (QKP), que consiste em maximizar uma função booleana quadrática sujeito a uma restrição de capacidade linear. O problema possui aplicações em várias áreas, como por exemplo, telecomunicações. engenharia financeira, problemas de localização e teoria dos grafos (clique máximo). Propomos um algoritmo de Branch-and-Bound para resolver exatamente QKP, baseado em Relaxação Lagrangeana. Inicialmente, linearizamos a formulação do problema acima, e em seguida, aplicamos a técnica de relax-and-cut dinamicamente à relaxação contínua do problema, utilizando algumas classes de desigualdades válidas. O método do subgradiente é usado neste processo. Propomos também uma nova heurística primal para QKP, que obtém soluções melhores do que heurísticas propostas anteriormente, encontrando a solução ótima em todas as instâncias que consideramos. A boa qualidade dos limites superior e inferior é traduzida em gap`s pequenos no nó raiz da árvore de enumeração (em geral, menor do que 1%, inclusive para instâncias difíceis). Isto, aliado a testes de fixação de variáveis, permite resolver exatamente QKP em poucos nós da árvore de enumeração. Introduzimos uma maneira de gerar instâncias aleatórias mais difíceis do que as instâncias na literatura. Apresentamos resultados computacionais para instâncias geradas aleatoriamente (instâncias da literatura, e as novas instâncias mais difíceis) para QKP de tamanhos e densidades diferentes; e também para instâncias conhecidas do problema de clique máxima. / [en] We consider the 0-1 Quadratic Knapsack Problem (QKP), which consists of maximizing a quadratic Boolean function subject to a linear capacity constraint. The problem has applications in several areas such as telecommunications, financial engineering, location problems, graph theory (Max Clique). We propose a Branch-and-Bound algorithm to solve the QKP to optimality based on lagrangian Relaxation. Initially, we linearize the formulation of the problem given above and then we relax-and-cut dinamicaly its continous relaxation using a few classes of valid inequalities. In the process the Subgradient Method is applied. We also propose a new primal heuristic for the QKP that has improved upon previous approaches, and finds an optimal solution for all of the instances we considered. The good quality of our upper and lower bounds is translated into small gaps at the root node of the enumeration tree (usually below 1%, even for difficult instances). That, coupled with tests for fixing variables, allowed optimality to be proven within only a few nodes of the enumeration tree. We provide a way to randomly generate instances of the QKP harder than those in the literature. We report computational results for randomly generated instances (the ones in the literature and the new harder ones) of QKP with different densities and sizes; and also for Known instances of Max Clique problems.

[pt] Com o advento do comércio eletrônico, o mercado passou a atuar cada vez mais intensamente através de suas fronteiras geográficas e, como consequência, as empresas necessitam constantemente de inovações e melhorias na gestão de suas operações para se manterem competitivas. Desta forma, encontrar soluções de fretes que consigam atender longas distâncias em um curto prazo pode ser tão decisivo quanto o fator custo, por isso, os estudos acadêmicos em otimização de rotas intermodais estão em contínua evolução para se aproximarem dos modelos reais. Nesse contexto, esta dissertação busca solucionar um problema de roteamento aeroterrestre de transporte de cargas, com linhas aéreas predeterminadas e frotas próprias e heterogêneas. Uma extensão do problema de roteamento de veículos é elaborada com a inclusão de arcos que representam as possíveis linhas aéreas. O modelo é aplicado em um resolvedor de Programação Linear Inteira Mista e, primeiramente, é realizado um teste de validação com demandas fictícias em todos os locais. Em seguida, o modelo é aplicado no planejamento real de um órgão governamental em três períodos distintos. São realizadas análises sobre a velocidade de solução; a decisão de utilizar o modal aéreo, terrestre ou intermodal; e sobre os ganhos do modelo. Em comparação com as rotas efetivamente realizadas, o modelo traz redução de 7 por cento a 55 por cento dos custos com transportes. Com esses resultados, conclui-se que é imprescindível que os detentores de frota própria de aeronaves e caminhões utilizem o modal aéreo apenas como atividades acessórias, ou seja, que estejam cumprindo outras missões em conjunto (transporte de passageiros, por exemplo), ou para atender locais remotos. / [en] With the advent of e-commerce, the market has started to act more and more intensively across its geographic borders and, as a consequence, companies constantly need innovations and improvements in the management of their operations in order to remain competitive. Thus, finding freight solutions that can serve long distances in the short term can be as decisive as the cost factor, for this reason, academic studies in intermodal routing optimization are continually evolving to approach real models. In this context, this thesis seeks to solve a problem of air-land cargo routing, with predetermined airlines and their own heterogeneous fleets. We elaborated an extension of the vehicle routing problem by including arcs that represent overhead lines. The model is applied to a Mixed Integer Linear Programming solver and, firstly, a validation test is performed with fictitious demands in all locations. It is then applied to the actual planning of a government agency in three different periods. We performed analyses on the solution speed; the decision to use the air, land or intermodal modal; and about the earnings of the model. In comparison with the routes actually carried out, the model reduces transport costs by 7 percent to 55 percent. With this results, it is concluded that it is essential that owners of their aircraft and trucks fleet use the air modal only as secondary activities, in other words, that they are fulfilling more missions together (transportation of passengers, for example), or to deliver to remote locations.

[pt] O Planejamento de Trens é de grande importância para o transporte de carga geral das ferrovias. O planejamento deve contemplar quais trens irão circular, suas frequências, quais as rotas atendidas e os vagões que irão compor cada trem. Na presente dissertação, é proposto um modelo de programação inteira mista para a otimização do Planejamento de Trens de Carga Geral, buscando minimizar os custos envolvidos na criação e operação dos trens. O modelo foi aplicado em uma ferrovia brasileira de transporte de cargas no planejamento de 12 períodos. O modelo foi rodado com tempo de processamento médio de 15 horas, tempo este considerado aceitável por se tratar de um problema tático que define os trens do próximo período de planejamento. Quando comparado com os dados reais, o modelo gerou uma redução média de 10,1 por cento nos custos de operação dos trens. O planejamento proposto gerou uma melhor utilização das conexões dos vagões para evitar a criação de trens com baixa ocupação, reduzindo assim os custos. Os resultados também proporcionaram aos planejadores de trens da ferrovia uma maior velocidade nas análises, que hoje são realizadas manualmente, possibilitando uma melhor visão de quais trens deveriam ser criados para os perfis de demanda de cada período. / [en] Train Planning is of great importance for the transportation of general carload in railroad. The planning must contemplate which trains should run, their frequencies, which routes will be served and the cars that will compose each train. In this dissertation, a mixed integer programming model is proposed to optimize the planning of general carloads trains, seeking to minimize the costs involved in the creation and operation of the trains. The model was applied to a Brazilian freight railway in the planning of 12 periods. The model was run with an average processing time of 15 hours, a time considered acceptable because it deals with a tactical problem that defines the trains of the next planning period. When compared to the actual data, the model generated an average reduction of 10.1 per cent in the costs of operating the trains. The proposed planning generated a better use of the wagon connections to avoid the creation of trains with low occupancy, thus reducing costs. The results also provided railroad train planners with greater speed in the analyzes, which today are carried out manually, allowing a better view of which trains should be created for the demand profiles of each period.

[pt] A importância do planejamento em logística ferroviária cresce a cada dia devido ao alto custo dos investimentos para o aumento da sua capacidade. Entretanto, planejar é uma atividade que exige uma representação suficientemente precisa da realidade estudada. Neste contexto, os modelos de programação matemática apresentam-se cada vez mais adequados. Isto decorre dos recentes avanços nos algoritmos e computadores disponíveis para sua resolução. Esta dissertação apresenta modelos e algoritmos para o planejamento ferroviário tático e estratégico, isto é feito estudando o Problema de Planejamento de Atendimento (PPA). Primeiramente este problema é considerado assumindo que toda a estrutura ferroviária está definida: a malha, a tração e os vagões disponíveis, os pátios para carga, descarga e transbordo, suas respectivas taxas de carga e descarga e as demandas previstas. Em seguida, a questão adicional de determinar os pátios onde paradas podem ser efetuadas é considerada. Finalmente, em uma terceira etapa, introduz-se a capacidade de se analisar os efeitos do congestionamento de trechos da malha e seu impacto nos tempos de circulação e na capacidade da estrutura logística. Modelos são apresentados para cada um dos níveis de complexidade do PPA. Algoritmos exatos e heurísticos e técnicas de pré- processamento, foram desenvolvidos para os tratamentos dos casos obtidos. Em todos os casos, foi possível resolver de maneira ótima ou quase ótima em tempo razoável, tanto em termos acadêmicos, como para a utilização prática. Resultados computacionais sobre um amplo conjunto de instâncias reais são apresentados. / [en] Planning in Railway Logistic is an activity with growing importance. This is due to the high costs of investment to increase the railway capacity. Nevertheless, planning in this context is a cumbersome task, since a precise representation is necessary to consider most relevant points in this activity. Mathematical programming is becoming one of the best ways derive precise representations and to solve them. This is due to the recent advances on algorithms and computers used in the resolution of mathematical programming problems. This dissertation presents models and algorithms for tactical and strategical railway planning what is done by studying a demand planning problem (PPA). First, this problem is considered assuming that all the railway structure is defined: the network, the locomotives and wagons available, the yards for loading and unloading with their respective rates, and the forecast of demands. Next, the question of deciding the yards to stop is considered. Finally, in a third step, the effect of congestion in parts of the network is introduced to the models. This allows analyzing the variation in the travel times and its consequence in the logistic structure capacity. Models are presented for all cases of the PPA. Exact and heuristic algorithms, as well as pre-processing techniques, are described for the problem resolution. In all cases, the resulting approach allowed to solve the problems optimally or quasioptimally in a reasonable computing time. Computational results are presented on a wide set of real world instances.

[pt] Uma maneira de localizar uma informação em uma base de dados grande e caótica como a Internet é utilizar um índice hierárquico que respeita alguma maneira de categorizar os dados. Exemplos desta hierarquia são os serviços de diretório, comuns em sites de busca. Porém, esta abordagem pode apresentar algumas desvantagens, como a necessidade de percorrer muitas páginas até chegar em uma informação muito acessada. Uma maneira de tratar este problema é o uso de hotlinks, hyperlinks adicionais que servem como atalho em uma busca. Estudamos algoritmos eficientes para atribuir hotlinks em um diretório web, de modo a reduzir o número máximo ou o número médio de acessos em uma busca. Fornecemos para o problema de minimização do número máximo de acessos um algoritmo (14/3)-aproximado e um algoritmo polinomial exato baseado em programação dinâmica. Por outro lado, para o problema de minimizar o número médio de acessos, adaptamos o algoritmo exato do problema anterior. Entretanto, este algoritmo adaptado é polinomial apenas para sites representados por árvores com altura O(log n). Por isso, introduzimos um parâmetro que permite ao usuário reduzir o tempo de execução em detrimento da qualidade da solução. Para este problema de minimizar o número médio de acessos, realizamos também experimentos comparando nosso algoritmo, um modelo em programação inteira, e alguns algoritmos propostos por outros autores. Introduzimos modificações práticas que melhoraram a performance do nosso algoritmo. / [en] An approach to search an information in a large and chaotic data base like the Internet is to use a hierarquical index regarding some categorization of the data. As an example, we have the web directories, usually found in search engines. However, this approach may have problems, as the need of visiting too many web pages to find a very accessed information. A way to address this problem is the use of hotlinks, which are hyperlinks added to the web site and used as shortcuts in a search. We studied efficient algorithms to assign hotlinks in web directories, in such a way to minimize the maximum or the average number of accesses to find an information. For the problem of minimizing the maximum number of accesses, we provide an (14/3)-approximation algorithm and an exact polinomial time algorithm based on dynamic programming. On the other hand, for the problem of minimizing the expected number of accesses, we adapted the previous exact algorithm. However, this adapted algorithm is polinomial only for web sites represented by trees with height O(log n). So, we introduce a parameter that allows the user to reduce the execution time under the cost of reducing the solution quality. For this problem of minimizing the expected number of accesses, we also made experiments comparing our algorithm, an integer programming model, and some algorithms proposed by other authors. We introduce pratical changes that improved the performance of our algorithm.

[pt] Problemas de transporte de cargas fracionadas são grandes candidatos para a aplicação de técnicas de otimização como forma de obter um melhor aproveitamento de recursos. Nesta dissertação, são apresentados modelos de programação inteira e os algoritmos desenvolvidos para a resolução adequada dos problemas estudados neste contexto. O foco é o planejamento da movimentação dos veículos para o atendimento das demandas ao longo de um período pré-definido. Diferentes formas de contratação dos veículos são consideradas, demandas possuem janelas de tempo para serem atendidas e podem compartilhar um mesmo veículo em um ou mais trechos do seu caminho até o destino. Conexões são permitidas, ou seja, uma demanda pode utilizar mais de um veículo para o seu atendimento, respeitando as capacidades operacionais dos centros de distribuição e coleta. Os objetivos abrangem o dimensionamento da frota, que possui um custo fixo, e o planejamento da operação ao longo do período. Este deve determinar quais demandas são transportadas por quais veículos em que instantes e em que trechos. O método de resolução proposto utiliza algoritmos para a construção e pré-processamento de grafos que representam o problema e permitem que a formulação como programa inteiro tenha uma resolução mais efciente. Além disso, o algoritmo correspondente resolve uma sequência de programas inteiros para obter soluções viáveis de qualidade para as diferentes versões do problema aqui considerado. Melhorias nos limites inferiores obtidos também são propostas. O código resultante foi testado em um conjunto de instâncias baseadas na operação de uma transportadora brasileira de grande porte. Resultados foram obtidos tanto para condições de utilização reais, isto é, com o tempo de execução limitado, como para testar os limites do método proposto. Em ambos os casos pôde-se obter soluções de alta qualidade comprovada. / [en] Less-than-truckload transportation problems are great candidates for the application of optimization techniques as a form to obtain a better exploitation of resources. This thesis introduces integer programming models and the developed algorithms for the proper resolution of the studied problems in this context. The focal point is the vehicle's dislocation planning for the ideal attendance of the demands during a certain time period. Different forms of vehicle contract are considered. There are time windows for the attendances and demands can share a same vehicle in one or more parts of its route until his destination. Connections are allowed, that is, demands can use more than one vehicle for its attendance, respecting the operational capacities of the centers (collection and distribution stations). The goals embraces the sizing of the proper fleet which has a fixed cost, and the operation's planning during the period. This one should determine which demands are transported by which vehicles in what instants and where on routes. The resolution's method proposed uses algorithms for the graph's construction and pre-processing which represents the problem and allows that the formulation, as an integer program, to have a resolution more efficient. Furthermore, the corresponding algorithm solves a sequence of integer programs to obtain feasible quality solutions for the differents versions of the considered problem. Improvements on the lower bounds gotten are also proposed. The resulting code was tested in a set of proposed instances that were based on the operation of an important brazilian trucking company . Results were acquired such for conditions of real utilization, in other words, with a limited time of execution, as to test the limits of the proposed method. In both cases, solutions of comproved high quality were obtained.