Submitted by Mariana Dornelles Vargas (marianadv) on 2015-06-01T12:45:08Z No. of bitstreams: 1 otimizacao_niveis.pdf: 2029201 bytes, checksum: a40cd7a9e26627e3677b30cfdb0cdd33 (MD5) / Made available in DSpace on 2015-06-01T12:45:08Z (GMT). No. of bitstreams: 1 otimizacao_niveis.pdf: 2029201 bytes, checksum: a40cd7a9e26627e3677b30cfdb0cdd33 (MD5) Previous issue date: 2011 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Em um contexto empresarial, a competitividade entre companhias de um mesmo ramo de atividade se torna mais presente a cada dia que passa. Empresas estruturadas de forma enxuta em termos de custo podem ter maior vantagem competitiva sobre seus concorrentes. Reduzir custos é, portanto, um objetivo almejado por todas as organizações. A gestão e controle de estoques de produtos é um problema presente em diversas empresas e organizações. Diversos custos estão associados a este problema. O volume monetário relacionado é bastante grande. Assim, quanto melhor for o processo de controle e gerenciamento de estoques de uma empresa, menor será o custo para manutenção dos mesmos. Este trabalho propõe uma ferramenta para otimização dos níveis de estoque de uma rede varejista, considerando características como lucratividade, custos e atendimentos às demandas. Isto é feito através do uso de um método previsor baseado em Suavização Exponencial com Sazonalidade Multiplicativa, um módulo Otimizador baseado na metaheurística Guided Local Search, além de um Simulador Discreto Determinístico. A ferramenta conta com uma série de parâmetros que permitem a criação de diferentes cenários relativos ao sistema de estocagem da rede varejista. Os resultados obtidos durante a fase de experimentação da ferramenta demonstram sua capacidade de encontrar soluções para o problema de níveis de estoque de forma satisfatória, além de possibilitar a criação de cenários alternativos à realidade observada no sistema físico. / Competitiveness is an element that increases on a daily basis considering nowadays businesses. Companies with more efficient structures in terms of costs have an important advantage when compared to their competitors. This greatly motivates companies to reduce costs. Inventory control is an existing problem in many companies and organizations. Many types of costs are associated to this problem. Also, the amount of money involved in inventory maintenance is very considerable. So, the better the inventory control process is, the lower the costs related to it will be. This paperwork proposes a tool to optimize inventory levels on a retailer company, considering profit, costs and service level attendance. This is done by using a Forecasting Method called Exponential Smoothing with Multiplicative Seasonality, an Optimizer based on the Guided Local Search metaheuristic and a Discrete Deterministic Simulator. This tool uses a series of parameters in order to allow users to create different scenarios. The results obtained with the conducted experiments show that the tool is capable of finding good solutions to the problem of inventory levels, as well as creating alternative scenarios to operate the inventory system..

Nesta tese propõe-se um método heurístico para o problema de Projeto de Rede da Cadeia de Suprimentos (Supply Chain Network Design) considerando vários aspectos de relevância prática, tais como: fornecedores e matérias-primas, localização e operação de instalações, atribuição de Centros de Distribuição (CD), e grande número de clientes e produtos. Uma eficiente abordagem heurística de duas fases é proposta para a obtenção de soluções viáveis para os problemas, que inicialmente é modelado como um Programa Linear Inteiro Misto (PLIM) de grande escala. Na fase de construção, uma estratégia de Linear Programming Rounding é aplicada para se obter os valores iniciais para as variáveis de localização inteira do modelo. Simultaneamente, um método Multi-start foi desenvolvido para gerar soluções iniciais diversificadas para cada nova iteração da heurística de Rounding. Na segunda fase, dois procedimentos de Busca Local foram desenvolvidos no sentido de melhorar a solução fornecida pelo método de Rounding. Implementamos duas diferentes abordagens de Busca Local: remoção-inserção e troca. Uma técnica de Busca Tabu para orientar o procedimento de Busca Local para explorar os diferentes espaços de soluções foi desenvolvida. As formulações e algoritmos foram implementados na linguagem C++ utilizando ferramentas de otimização da COIN-OR. O método de solução foi experimentado em instâncias geradas aleatoriamente, com tamanhos diferentes em termos do número de parâmetros, tais como o número de produtos, zonas de clientes, CDs e fábricas considerando um sistema logístico de quatro níveis. As implementações computacionais mostram que o método de solução proposto obteve resultados satisfatórios quando comparados com a literatura. Para validar este método heurístico também foi usado em um caso realista, com base em dados de uma empresa de borracha que está reestruturando sua cadeia de suprimentos devido ao projeto de uma nova uma nova fábrica e produção de novos produtos. A abordagem heurística proposta revelou-se adequada para aplicação prática em um caso real de uma indústria multicommodity em um contexto determinístico. / In this thesis we propose a heuristic method for the Supply Chain Network Design (SCND) problem considering several aspects of practical relevance: suppliers and raw materials, location and operation facilities, distribution center (DC) assignments, and large numbers of customers and products. An efficient two-phase heuristic approach is proposed for obtaining feasible solutions to the problems, which is initially modeled as a large-scale Mixed Integer Linear Program (MILP). In the construction phase, a linear programming rounding strategy is applied to obtain initial values for the integer location variables in the model. Simultaneously, a Multi-start method was developed to generate diversified initial solutions from each new iteration in the rounding heuristic. In the second phase, two Local Search procedures were developed towards to improve the solution provided by the rounding method. We implemented two different Local Search approaches: removal-insertion and exchange. A Tabu Search technique was developed to guide the Local Search procedure to explore the different spaces of solutions. The formulations and algorithms were implemented in C++ code language using the optimization engine COIN-OR. The solution method was experimented in randomly generated instances, with different sizes in terms of the number of parameters, such as number of products, customer zones, DCs, and factories considering a four-echelon logistic system. The computational implementations show that the solution method proposed obtained satisfactory results when compared to the literature review. To validate this heuristic method was also used in a realistic case, based on data from a rubber company that is restructuring its supply chain due to the overture of a new factory, producing new products. The proposed heuristic approach proved appropriate to practical application in a realistic case of a multi commodity industry in a deterministic context.

Currently, one of the main research problems in Structural Bioinformatics is associated to the study and prediction of the 3-D structure of proteins. The 1990’s GENOME projects resulted in a large increase in the number of protein sequences. However, the number of identified 3-D protein structures have not followed the same growth trend. The number of protein sequences is much higher than the number of known 3-D structures. Many computational methodologies, systems and algorithms have been proposed to address the protein structure prediction problem. However, the problem still remains challenging because of the complexity and high dimensionality of a protein conformational search space. This work presents a new computational strategy for the 3-D protein structure prediction problem. A first principle strategy which uses database information for the prediction of the 3-D structure of polypeptides was developed. The proposed technique manipulates structural information from the PDB in order to generate torsion angles intervals. Torsion angles intervals are used as input to a genetic algorithm with a local-search operator in order to search the protein conformational space and predict its 3-D structure. Results show that the 3-D structures obtained by the proposed method were topologically comparable to their correspondent experimental structure.

Modularity Density Maximization is a graph clustering problem which avoids the resolution limit degeneracy of the Modularity Maximization problem. This thesis aims at solving larger instances than current Modularity Density heuristics do, and show how close the obtained solutions are to the expected clustering. Three main contributions arise from this objective. The first one is about the theoretical contributions about properties of Modularity Density based prioritizers. The second one is the development of eight Modularity Density Maximization heuristics. Our heuristics are compared with optimal results from the literature, and with GAOD, iMeme-Net, HAIN, BMD- heuristics. Our results are also compared with CNM and Louvain which are heuristics for Modularity Maximization that solve instances with thousands of nodes. The tests were carried out by using graphs from the “Stanford Large Network Dataset Collection”. The experiments have shown that our eight heuristics found solutions for graphs with hundreds of thousands of nodes. Our results have also shown that five of our heuristics surpassed the current state-of-the-art Modularity Density Maximization heuristic solvers for large graphs. A third contribution is the proposal of six column generation methods. These methods use exact and heuristic auxiliary solvers and an initial variable generator. Comparisons among our proposed column generations and state-of-the-art algorithms were also carried out. The results showed that: (i) two of our methods surpassed the state-of-the-art algorithms in terms of time, and (ii) our methods proved the optimal value for larger instances than current approaches can tackle. Our results suggest clear improvements to the state-of-the-art results for the Modularity Density Maximization problem.

Dans cette thèse nous développons de nouvelles techniques pour résoudre les problèmes d'optimisation multi-critère. Ces problèmes se posent naturellement dans de nombreux domaines d'application (sinon tous) où les choix sont évalués selon différents critères conflictuels (coûts et performance par exemple). Contrairement au cas de l'optimisation classique, de tels problèmes n'admettent pas en général un optimum unique mais un ensemble de solutions incomparables, aussi connu comme le front de Pareto, qui représente les meilleurs compromis possibles entre les objectifs conflictuels. La contribution majeure de la thèse est le développement d'algorithmes pour trouver ou approximer ces solutions de Pareto pour les problèmes combinatoires difficiles. Plusieurs problèmes de ce type se posent naturellement lors du processus de placement et d'ordonnancement d'une application logicielle sur une architecture multi-coeur comme P2012, qui est actuellement développé par STMicroelectronics. / In this thesis we develop new techniques for solving multi-criteria optimization problems. Such problems arise naturally in many (if not all) application domains where choices are evaluated according to two or more conflicting criteria such as price vs. performance. Unlike ordinary optimization, such problems typically do not admit a unique optimum but a set of incomparable solutions, also known as the Pareto Front, which represent the best possible trade-offs between the conflicting goals. The major contribution of the thesis is the development of algorithms for finding or approximating these Pareto solutions for hard combinatorial problems that arise naturally in the process of mapping and scheduling application software on multi-core architectures such as P2012 which is currently being developed by ST Microelectronics.

No presente trabalho, é abordada a operação de transporte de cargas fracionadas, especificamente a determinação de quais linhas de transporte deverão ser ofertadas dentro de uma rede de terminais, de maneira a atender toda a demanda no nível de serviço desejado ao menor custo possível. Para tanto, é feita inicialmente uma descrição do problema de transporte de carga fracionada, seguido de uma revisão bibliográfica de trabalhos anteriores que já tenham abordado o tema. É então realizada a delimitação do escopo do estudo e a proposição de um modelo matemático em programação linear inteira-mista. Em seguida, é apresentado um algoritmo de resolução, consistindo na aplicação de uma heurística construtiva e uma heurística de melhoria, ambas embasadas na aplicação de caminhos mínimos com janelas de tempo a partir de custos marginais. O método é delineado para três versões do problema, estipuladas a partir de diferentes tratamentos à restrição de caminhos em formato de árvore dentro do sistema. Primeiramente, o algoritmo é aplicado a pequenas instâncias fictícias, realizando a comparação com a modelagem em programação linear inteira-mista proposta. Na maioria dos casos, não houve diferença nos valores de função objetivo encontrados, embora tenham sido identificados gaps grandes no processamento. Posteriormente, é realizada a aplicação a dados reais de uma transportadora brasileira. Para as três versões do problema, a redução de custos potencial identificada é significativa, com tempos de processamento similares ou menores do que o encontrado na literatura. Por fim, os resultados obtidos são discutidos sendo apresentadas considerações finais acerca do trabalho realizado e possíveis melhorias para pesquisas futuras. / At the present work, the operation of less-than-truckload (LTL) will be studied, more specifically the determination of which lines will be offered in a network of terminals. The service network design must attend all demands, respecting their deadlines while aiming cost reductions. The objective of this work is to propose algorithms to solve the service network design problem of LTL operations, reducing operation costs while respecting specified service levels. First, a brief introduction to the problem is made, and similar research is reviewed. Then the scope of the research is determined and a mathematical model of the problem in mixed-integer programming is presented. Next, an algorithm is proposed, consisting in a constructive heuristic followed by a local search. Both phases are based on finding minimum paths with time windows using marginal costs along the network. Three different versions of the problem are analyzed, shifting the approach given to the constraint of in-tree structure that shipments should follow in the network. The algorithm is firstly tested to small fictional instances, allowing comparison to the mixed programming model proposed earlier. No relevant differences between objective functions were found, even though substantial gaps values were identified during processing. A second test used a real dataset of a Brazilian LTL carrier. In all versions of the problem the operation cost reduction was promising, with processing times similar to the ones found in literature. The conclusion provides a discussion of the obtained results and recommendations for future research.

<p>Games on graphs have become an indispensable tool in modern computer science. They provide powerful and expressive models for numerous phenomena and are extensively used in computer- aided verification, automata theory, logic, complexity theory, computational biology, etc.</p><p>The infinite games on finite graphs we study in this thesis have their primary applications in verification, but are also of fundamental importance from the complexity-theoretic point of view. They include parity, mean payoff, and simple stochastic games.</p><p>We focus on solving graph games by using iterative strategy improvement and methods from linear programming and combinatorial optimization. To this end we consider old strategy evaluation functions, construct new ones, and show how all of them, due to their structural similarities, fit into a unifying combinatorial framework. This allows us to employ randomized optimization methods from combinatorial linear programming to solve the games in expected subexponential time.</p><p>We introduce and study the concept of a controlled optimization problem, capturing the essential features of many graph games, and provide sufficent conditions for solvability of such problems in expected subexponential time.</p><p>The discrete strategy evaluation function for mean payoff games we derive from the new controlled longest-shortest path problem, leads to improvement algorithms that are considerably more efficient than the previously known ones, and also improves the efficiency of algorithms for parity games.</p><p>We also define the controlled linear programming problem, and show how the games are translated into this setting. Subclasses of the problem, more general than the games considered, are shown to belong to NP intersection coNP, or even to be solvable by subexponential algorithms.</p><p>Finally, we take the first steps in investigating the fixed-parameter complexity of parity, Rabin, Streett, and Muller games.</p>

This dissertation addresses problems arising in freight routing and scheduling where full truckload (FTL) and less-than-truckload (LTL) carriers are used to serve transportation needs. Each of the problems investigated in this dissertation tries to optimize/maximize consolidation to decrease system transportation costs by (1) carefully choosing the timing and path of freight and/or (2) introducing consolidation points. Approaches are proposed that enable effective planning and operation of freight routing and scheduling for large-scale transportation networks. Chapter 2 presents solution approaches for a shipper pickup and delivery planning problem faced by many large retailers to move freight from suppliers to distribution centers. Each shipment is moved either direct via a LTL carrier or possibly consolidated with other shipments and moved by one or two FTL routes. When using a FTL carrier, the shipper takes advantage of contracted lane rates that establish prices per mile for a truck operated between two locations that are significantly less than the comparable LTL price for shipping a full truckload. Consolidated FTL routes may each visit multiple shipment origins (supplier locations) and/or destinations (distribution center locations). Additionally, FTL routes may move shipments through a single crossdock facility en route. The challenge in this planning problem is to exploit as much as possible negotiated truckload lane rates and to judiciously make use of routes through crossdock facilities to consolidate shipments. The primary contributions of this section are that (1) an interesting new problem variant is introduced to the field of transportation and logistics that is important in practice and (2) the solution approach demonstrates that exploiting knowledge of the problem and solution structure to cleverly select subsets of path variables for evaluation during each iteration of an integer programming based local search heuristic is effective on path-based routing models. Chapter 3 evaluates how to route each customer shipment through a sequence of transfer terminals in a LTL carrier network. At each terminal stop, a shipment is unloaded from an inbound trailer and reloaded onto an outbound trailer. A load plan determines the specific sequence of terminal transfers to be used for freight moving between each origin and destination. The design of the load plan determines the linehaul transportation and handling costs required to serve customers. We develop an improved very large-scale neighborhood search heuristic for solving an integer programming model for load plan design. The main contributions of this section include (1) the investigation of the pros and cons of optimizing system-wide into a single destination versus optimizing freight for all destinations in a small region, and (2) a solution approach that can find load plans with costs 6 to 7\% lower than those used in practice, and can find 2.5 to 5\% additional cost savings using the same time budget when compared to an approach optimizing system-wide into a single destination. Chapter 4 addresses a strategic planning problem that extends the load plan design problem to consider terminal roles. We investigate two-stage approaches that first identify the set of transfer terminals and then develop the corresponding load plan. Computational results compare the terminals chosen as transfer facilities from the proposed integer programming based local search method with a traditional hub location formulation and a simple facility location formulation to depict the benefits gained from modeling additional information. The key contributions of this section are (1) the introduction of a new hub location problem variant incorporating freight dispatch timing and trailer transportation cost characteristics found in the LTL trucking industry and (2) a solution approach utilizing IP-based local search that demonstrates the importance of incorporating freight dispatch timing. Finally, Chapter 5 summarizes the main conclusions from this dissertation and discusses directions for further research.

This thesis is concerned with identifying the best decision among a set of possible decisions in the presence of uncertainty. We are primarily interested in situations where the objective function value at any feasible solution needs to be estimated, for example via a ``black-box' simulation procedure. We develop adaptive random search methods for solving such simulation optimization problems. The methods are adaptive in the sense that they use information gathered during previous iterations to decide how simulation effort is expended in the current iteration. We consider random search because such methods assume very little about the structure of the underlying problem, and hence can be applied to solve complex simulation optimization problems with little expertise required from an end-user. Consequently, such methods are suitable for inclusion in simulation software. We first identify desirable features that algorithms for discrete simulation optimization need to possess to exhibit attractive empirical performance. Our approach emphasizes maintaining an appropriate balance between exploration, exploitation, and estimation. We also present two new and almost surely convergent random search methods that possess these desirable features and demonstrate their empirical attractiveness. Second, we develop two frameworks for designing adaptive and almost surely convergent random search methods for discrete simulation optimization. Our frameworks involve averaging, in that all decisions that require estimates of the objective function values at various feasible solutions are based on the averages of all observations collected at these solutions so far. We present two new and almost surely convergent variants of simulated annealing and demonstrate the empirical effectiveness of averaging and adaptivity in the context of simulated annealing. Finally, we present three random search methods for solving simulation optimization problems with uncountable feasible regions. One of the approaches is adaptive, while the other two are based on pure random search. We provide conditions under which the three methods are convergent, both in probability and almost surely. Lastly, we include a computational study that demonstrates the effectiveness of the methods when compared to some other approaches available in the literature.

[pt] Em vários problemas de distribuição e logística, os produtos devem ser coletados em uma origem e entregues em um destino. Exemplos incluem o transporte de pessoas com deficiência, serviços de correio expresso, logística de suprimentos médicos, etc. O problema de roteamento abordado neste trabalho, conhecido como Traveling Salesman Problem with Pickup and Delivery (TSPPD), é da classe de problemas do caixeiro viajante com restrições de precedência. Neste problema, existe um mapeamento um-para-um entre coleta-entrega no qual cada cliente do tipo coleta possui um cliente do tipo entrega associado. Os clientes do tipo entrega somente podem ser visitados posteriormente à coleta associada. O TSPPD é um problema NP-difícil uma vez que generaliza o Traveling Salesman Problem (TSP). O TSP pode ser visto como um caso particular do TSPPD onde cada coleta coincide espacialmente com a respectiva entrega. As variantes com restrições de capacidade, janelas de tempo e diferentes políticas de carregamento têm recebido maior atenção na última década, embora ainda existam significantes avanços a serem realizados em termos de qualidades de soluções na versão básica do problema. Para resolver este problema, propomos um algoritmo meta-heurístico híbrido com vizinhanças largas exploradas eficientemente em O(n2). Nossos experimentos demonstram uma redução significativa no tempo computacional e também melhoria na qualidade de soluções previamente conhecidas na literatura. / [en] In various distribution and logistics issues, products must be collected at one source and delivered to a destination. Examples include disabled people transportation, express mail services, medical supplies logistics, etc. The routing problem addressed by this work, known as Traveling Salesman Problem with Pickup and Delivery (TSPPD), belongs to the class of traveling salesman problems with precedence constraints. In this problem, there is a one-to-one pickup-delivery mapping in which, for each pickuptype client, there is exactly one associated delivery-type client. Delivery clients can only be visited after the associated pickup. Since the TSPPD generalizes the TSP it is also a NP-hard problem, as the TSP is a particular casa of TSPPD where each pickup matches spatially with it s respective delivery. Variants with capacity constraints, time windows and different loading policies have received more attention in the last decade, although there are still significant advances to be made in terms of solution quality for the basic version of the problem. To solve this problem, we propose a hybrid metaheuristic algorithm with large neighborhoods efficiently explored in O(n2). Our experiments demonstrate a significant computational time reduction and also solutions quality improvement compared to the previous works.