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

No description available.

Massive infrastructure networks such as electric power, natural gas, or water systems play a pivotal role in everyday human lives. Development and operation of these networks is extremely capital-intensive. Moreover, security and reliability of these networks is critical. This work identifies and addresses a diverse class of computationally challenging and time-critical problems pertaining to these networks. This dissertation extends the state of the art on three fronts. First, general proofs of uniqueness for network flow problems are presented, thus addressing open problems. Efficient network flow solvers based on energy function minimizations, convex relaxations, and mixed-integer programming are proposed with performance guarantees. Second, a novel approach is developed for sample-efficient training of deep neural networks (DNN) aimed at solving optimal network dispatch problems. The novel feature here is that the DNNs are trained to match not only the minimizers, but also their sensitivities with respect to the optimization problem parameters. Third, control mechanisms are designed that ensure resilient and stable network operation. These novel solutions are bolstered by mathematical guarantees and extensive simulations on benchmark power, water, and natural gas networks. / Doctor of Philosophy / Massive infrastructure networks play a pivotal role in everyday human lives. A minor service disruption occurring locally in electric power, natural gas, or water networks is considered a significant loss. Uncertain demands, equipment failures, regulatory stipulations, and most importantly complicated physical laws render managing these networks an arduous task. Oftentimes, the first principle mathematical models for these networks are well known. Nevertheless, the computations needed in real-time to make spontaneous decisions frequently surpass the available resources. Explicitly identifying such problems, this dissertation extends the state of the art on three fronts: First, efficient models enabling the operators to tractably solve some routinely encountered problems are developed using fundamental and diverse mathematical tools; Second, quickly trainable machine learning based solutions are developed that enable spontaneous decision making while learning offline from sophisticated mathematical programs; and Third, control mechanisms are designed that ensure a safe and autonomous network operation without human intervention. These novel solutions are bolstered by mathematical guarantees and extensive simulations on benchmark power, water, and natural gas networks.

Origin-Destination (O-D) trip tables represent the demand-supply information of each directed zonal-pair in a given region during a given period of time. The effort of this research is to develop a linear programming methodology for estimating O-D trip tables based on observed link volumes. In order to emphasize the nature of uncertainty in the data and in the problem, the developed model permits the user's knowledge of path travel time to vary within a band-width of values, and accordingly modifies the user-optimality principle. The data on the observed flows might also not be complete and need not be perfectly matched. In addition, a prior trip table could also be specified in order to guide the updating process via the model solution. To avoid excessive computational demands required by a total numeration of all possible paths between each O-D pair, a Column Generation Algorithm (CGA) is adopted to exploit the special structures of the model. Based on the known capacity of each link, a simple formula is suggested to calculate the cost for the links having unknown volumes. An indexed cost is introduced to avoid the consideration of unnecessary passing-through-zone paths, and an algorithm for solving the corresponding minimum-cost-path problem is developed. General principles on the design of an object-oriented code are presented, and some useful programming techniques are suggested for this special problem. Some test results on the related models are presented and compared, and different sensitivity analyses are performed based on different scenarios. Finally, several research topics are recommended for future research. / Master of Science

本文主要目的在說明如何將線型規劃(Linear Programming)理論應用在網路分析(Network Analysis)上，實際上網路流量(Network Flow)問題為線型規劃之特別類型，其所形成之線型規劃式，由於其限制式(Constrants)之係數矩陣具有單調(Unimodular)性質，故當限制式之需求向量(requirements vector)為整數行向量時，則有最佳之整數解，此為構成網路流量問題具有整數最佳解之基本特性。 由於網路流量問題為線型規劃之特別類型，故解決網路流量問題之簡捷方法很多，如本文第二章求最大流量所用之標示法，求最短系列所用之標示法，以及求最低成本流量所用之基本對合法(Primal-Dual Approach)等皆偽解網路流量問題之最佳方法，然本文何以要將線型規劃之理論應用在網路分析上，其目的一方面說明其應用之特性，另一方面說明如用線型規劃之電子計算機程式來解這方面問題時當更為迅速正確。 本文之重心在線型規劃對網路流量問題之應用，故線型規劃之理論不再敘述，本文第一章為導言，第二章說明網路模型以及解網路流量問題之簡捷方法，第三章列舉一般網路流量問題，第四章說明線型規劃在網路分析上之應用，第五章係取某公司之交通問題做為研究之對象，此實例僅屬於諸網路流量問題中之某一問題，當然有關其它網路流量問題之賓際例子也很多，因限於時間及實例之不易獲得等問題，故未能一一舉例討論。 本文幸蒙指導老師田長模教授熱心指導，並蒙企管所所長楊必立教授之支持方得順利完成，謹於此深表謝意。惟筆者學識淺陋，疏漏之處，實恐難免，敬希先進及讀者多加指正，不勝感激。

O presente trabalho trata do planejamento da movimentação de contêineres vazios ao longo de um conjunto de portos, buscando o balanceamento entre as demandas e ofertas dos mesmos em todos os portos ao menor custo, e considerando as restrições de capacidade de transporte dos modais envolvidos. Para isso será adotado um modelo de fluxo em rede multi-produto para representar o sistema de movimentação de contêineres vazios e que servirá de base para o desenvolvimento de uma formulação matemática, a qual, implementada através de uma ferramenta computacional de otimização, determina os fluxos de vazios no sistema. A verificação do modelo proposto deu-se através de testes em problemas reduzidos de movimentação de vazios, assim como em um problema cujos resultados foram publicados na literatura. Os resultados sugeriram a adequabilidade e confiabilidade do modelo proposto que pode, então, ser aplicado a um problema real da empresa de navegação Hamburg Süd, tendo seus resultados comparados aos resultados fornecidos pela mesma. / This dissertation deals with the empty containers movement planning throughout a set of ports, aiming the balancing between the demands and supplies in all the ports at minimal cost, and considering the capacity constraints of the transport modes considered. A multi-commodity network flow model will be adopted to represent the empty containers movement system. This model supports the development of a mathematical formulation which, through a computational optimization tool, determines the flows of empty containers throughout the system. The verification of the proposed model was given through tests in reduced problems, as well as in a problem which results had already been published in literature. The results had suggested the adequateness and trustworthiness of the proposed model, which could, then, be applied to a real problem of the navigation company Hamburg Süd, and the results could be compared with the ones given by the company.

Esta pesquisa aborda o problema de alocação de jatos executivos compartilhados para casos em que a demanda diária é variável. É proposta uma ferramenta auxiliar de planejamento de uma empresa de operação de jatos compartilhados. São apresentadas as características principais do tipo de negócio que formam o problema estudado neste trabalho. Consideram-se os aspectos de uma empresa que administra jatos de propriedade compartilhada. O cliente adquire uma cota de uma aeronave e quando solicita uma viagem, com poucas horas de antecedência, a empresa deve garantir a realização do voo em uma aeronave da categoria adquirida. Também é de responsabilidade da empresa a gestão da tripulação, o reposicionamento da frota e a manutenção das aeronaves Este trabalho apresenta o desenvolvimento de uma ferramenta para auxiliar na tomada de decisões estratégicas que envolvem a escolha dos locais de base de operação e o dimensionamento da frota. A metodologia de solução é composta de um modelo de simulação e um de otimização. O modelo de simulação utiliza o método de Monte Carlo para obtenção da demanda de voos dia a dia que gera uma programação de clientes a atender. Os dados da simulação são então estruturados como um problema de fluxo em rede de mínimo custo e é realizada a alocação ótima das aeronaves. A ferramenta foi construída em ambiente de planilha eletrônica Microsoft Excel e aplicada em um caso prático de jatos executivos compartilhados com múltiplas bases. Foram testadas diversas configurações de bases e políticas operacionais como frota homogênea, frota heterogênea e frota alugada. Os resultados da ferramenta permitem determinar o impacto que a escolha das bases de operação tem no tamanho da frota e no reposicionamento de aeronaves. A metodologia mostrou-se robusta e, em tempo adequado, a ferramenta encontrou a solução ótima para cada configuração testada. / This research deals with the problem of scheduling jets with fractional ownership in cases where the demand varies daily. It has been devised a tool to support the planning phase of a company that operates shared jets. The main characteristics of the fractional shared market are presented in this manuscript and the research was developed under the point of view of a provider of fractional ownership. A client becomes a partial owner of an aircraft of a specific model and is entitled to a certain amount of flight hours. When the client requests a flight, usually only a few hours ahead, the fractional provider must guarantee that an aircraft of the requested model is available to the owner at the requested time and place. The provider is responsible for all the operational considerations, including managing the crew and having a well-maintained fleet. This work presents the development of a tool to help making decisions involving the choice of the operational bases and the size of the fleet. The solution methodology is composed of a simulation and a optimization model. Monte Carlo simulation is the method used to obtain the daily flight demand. The results of the simulation are structured as a minimum cost network flow problem to solve optimally the fleet allocation. This tool has been built in a Microsoft Excel spreadsheet environment and applied to a case of fractional jets with multiple bases. Several configurations and operational policies have been tested, such as operations with homogenous fleet, with heterogeneous fleet and with rented fleet. The results provided by the tool allow the user to evaluate the impact that the choice of the operational bases has on the size of the fleet and on the redeployment of the aircrafts. The methodology presented itself as adequate and the developed tool was able to solve optimally, in acceptable time, the problem for each case.

As technology geometries have shrunk to the deep sub-micron (DSM) region, the chip density and clock frequency of FPGAs have increased significantly. This makes computer-aided design (CAD) for FPGAs very important and challenging. Due to the increasing demands of portable devices and mobile computing, low power design is crucial in CAD nowadays. In this dissertation, we present a framework to optimize power consumption for technology mapping onto FPGAs. We propose a low-power technology mapping scheme which is able to predict the impact of choosing a subnetwork covering on the ultimate mapping solution. We dynamically update the power estimation for a sequence of options and choose the one that yields the least power consumption. This technique outperforms the best low-power mapping algorithms reported in the literature. We further extend this work to generate mapping solutions with optimal delay. We also propose placement algorithms to optimize the performance of the placed circuit. Net cluster based methodology is designed to ensure closely connected nets will be routed in the same region. Net cluster is obtained by clique partitioning on the net dependency graph. Net positions and consequent cell positions are computed with a force-directed approach which drags nets connected to closer positions. We further study the performance-driven placement problem for high level synthesis. We use the Automatic Design Instantiation (AUDI) high level synthesis system to generate a register-transistor level (RTL) netlist. This RTL netlist is fed into a CAD tool for physical synthesis. We do not necessarily go through the entire physical design process which is usually quite time-consuming. Instead, we have created an accurate wirelength/timing estimator working on the floorplan. If the estimated timing information does not meet the constraints, a guidance is generated and provided to AUDI system. The guidance consists of the estimated timing information and instructions to produce a new netlist in order to improve the performance. Finally the circuit is placed and routed on a satisfying design. This performance-driven placement framework yields better results as compared to a commercial CAD tool.

With recent and continuing advances in bioinformatics, the volume of sequence data has increased tremendously. Along with this increase, there is a growing need to develop efficient algorithms to process such data in order to make useful and important discoveries. Careful analysis of genomic data will benefit science and society in numerous ways, including the understanding of protein sequence functions, early detection of diseases, and finding evolutionary relationships that exist among various organisms. Most sequence analysis problems arising from computational genomics and evolutionary biology fall into the class of NP-complete problems. Advances in exact and approximate algorithms to address these problems are critical. In this thesis, we investigate a novel graph theoretical model that deals with fundamental evolutionary problems. The model allows incorporation of the evolutionary operations ``insertion', ``deletion', and ``substitution', and various parameters such as relative distances and weights. By varying appropriate parameters and weights within the model, several important combinatorial problems can be represented, including the weighted supersequence, weighted superstring, and weighted longest common sequence problems. Consequently, our model provides a general computational framework for solving a wide variety of important and difficult biological sequencing problems, including the multiple sequence alignment problem, and the problem of finding an evolutionary ancestor of multiple sequences. In this thesis, we develop large scale combinatorial optimization techniques to solve our graph theoretical model. In particular, we formulate the problem as two distinct but related models: constrained network flow problem and weighted node packing problem. The integer programming models are solved in a branch and bound setting using simultaneous column and row generation. The methodology developed will also be useful to solve large scale integer programming problems arising in other areas such as transportation and logistics.

abstract: Carbon Capture and Storage (CCS) is a climate stabilization strategy that prevents CO2 emissions from entering the atmosphere. Despite its benefits, impactful CCS projects require large investments in infrastructure, which could deter governments from implementing this strategy. In this sense, the development of innovative tools to support large-scale cost-efficient CCS deployment decisions is critical for climate change mitigation. This thesis proposes an improved mathematical formulation for the scalable infrastructure model for CCS (SimCCS), whose main objective is to design a minimum-cost pipe network to capture, transport, and store a target amount of CO2. Model decisions include source, reservoir, and pipe selection, as well as CO2 amounts to capture, store, and transport. By studying the SimCCS optimal solution and the subjacent network topology, new valid inequalities (VI) are proposed to strengthen the existing mathematical formulation. These constraints seek to improve the quality of the linear relaxation solutions in the branch and bound algorithm used to solve SimCCS. Each VI is explained with its intuitive description, mathematical structure and examples of resulting improvements. Further, all VIs are validated by assessing the impact of their elimination from the new formulation. The validated new formulation solves the 72-nodes Alberta problem up to 7 times faster than the original model. The upgraded model reduces the computation time required to solve SimCCS in 72% of randomly generated test instances, solving SimCCS up to 200 times faster. These formulations can be tested and then applied to enhance variants of the SimCCS and general fixed-charge network flow problems. Finally, an experience from testing a Benders decomposition approach for SimCCS is discussed and future scope of probable efficient solution-methods is outlined. / Dissertation/Thesis / Masters Thesis Industrial Engineering 2017