Volvo GTO in Umeå is the largest production unit for cabs of Volvo’s heavy trucks. Currently, the company has three external storage facilities around the Umeå region used for storage of steel coils, pressing tools, and production material. A project regarding the construction of a new logistics center has been initiated, with the aim of combining the current storage facilities into one. This in order to make the logistics flows more efficient, while decreasing costs and emissions. The creation of a new logistics center served as a starting point for this thesis. Emphasis has been placed on determination of optimal inventory levels of steel coils, which is the main component in their production of cabs. The primary aim was to minimize costs while ensuring a sufficient stock available for all coils. To accomplish this, both an optimization model and a simulation model have been developed in order to ascertain optimal order quantities and appropriate safety stock levels based on required service levels. These quantities and safety stocks have later been used to determine the size of the storage area in the logistics center. A significant aspect of this project involved the generation of input data corresponding to demand. Leveraging the resampling technique multivariate moving block bootstrapping on historical demand data from last year has enabled the creation of realistic demand scenarios. The conclusions drawn from the study is that the optimal inventory levels are strongly dependent on anticipated future demand, as evidenced by the different scenarios. Important to state is that the calculations made are based solely on demand variability and not on other crucial factors, such as lead time variability. Future investigations of optimal inventory levels should incorporate additional parameters to obtain a more comprehensive understanding for the management of the inventory system. / Volvo GTO i Umeå är den största produktionsenheten för Volvos hyttproduktion till tunga lastbilar. I dagsläget har Volvo GTO tre externa lagerlokaler i Umeåområdet, som används till lagring av stålcoils, pressverktyg och produktionsmaterial. Ett projekt gällande ett nytt logistikcenter har initierats, som syftar till att slå samman nuvarande lagerlokaler till en. Detta för att skapa mer effektiva logistikflöden, samtidigt som kostnader och utsläpp minskar. Skapandet av ett nytt logistikcenter utgör utgångspunkten för detta projekt. Tyngdpunktenhar legat på att fastställa optimala lagernivåer för stålcoils, vilka utgör huvudkomponenten i Volvos hyttproduktion. Den primära målsättningen var att minimera kostnader och samtidigt säkerställa att tillräckligt med lager finns tillgängligt för samtliga stålcoils. För att uppnå detta skapades både en optimeringsmodell och en simuleringsmodell för att fastställa optimala orderkvantiteter och lämpliga säkerhetslagernivåer, baserat på nödvändiga servicenivåer. Dessa orderkvantiteter och säkerhetslagernivåer användes senare vid bestämning av storleken på lagerytan i logistikcentret. En betydande del av detta arbete utgjordes av generering av indata motsvarande efterfrågan. Nyttjande av återsamplingsmetoden multivariate moving block bootstrapping gjord på historisk data över efterfrågan år 2023 har möjliggjort skapandet av realistiska efterfrågescenarier. Slutsatser som dras från studien är att de optimala lagernivåerna är strikt beroende av den förväntade framtida efterfrågan, vilket visas i de olika scenarierna. Viktigt att poängtera är att beräkningarna gjorda enbart är baserade på variation i efterfrågan och inte på andra avgörande faktorer, såsom variationer i ledtider. Framtida utredningar av optimala lagernivåer bör inkludera ytterligare parametrar för att erhålla en mer övergripande och rättvis förståelse för hanteringen av lagersystemet.

This dissertation details an algorithm to solve the Intratheater Airlift Operations Problem (IAOP) using advanced tabu search. A solution to the IAOP determines the routes and assignment of customer requests to a fleet of aircraft over a given time horizon. This problem and other variants comprise an ongoing challenge for United States Air Force (USAF) planners who manage detailed logistics throughout many theaters of operations. Attributes of the IAOP include cargo time windows, multiple cargo types, multiple vehicle cargo bay configurations, vehicle capacity, route duration limits, and port capacities. The IAOP multi-criteria objective embraces several components with the primary goal of satisfying as much of the demand as possible while minimizing cost. The algorithm is extended to allow split load deliveries of customer requests, allowing a shipment to be split into two or more sub-loads which are delivered separately to the customer. The split load relaxation, while significantly increasing the complexity of the problem, allows for possible improvement in the solution. The necessary changes to the model and algorithm are detailed, providing a foundation to extend any local search algorithm solving a vehicle routing problem to allow split loading. Results allowing split loading are presented and compared with results without split loading. The algorithm is also extended to include a rolling time horizon. Starting from a solution found at a previous time step, the algorithm is limited on how the solution can be modified. This reflects the reality of operations in which near-term plans are locked as they approach and enter execution while longer-term plans are continually updated as new information arrives. / text

abstract: In this thesis, a single-level, multi-item capacitated lot sizing problem with setup carryover, setup splitting and backlogging is investigated. This problem is typically used in the tactical and operational planning stage, determining the optimal production quantities and sequencing for all the products in the planning horizon. Although the capacitated lot sizing problems have been investigated with many different features from researchers, the simultaneous consideration of setup carryover and setup splitting is relatively new. This consideration is beneficial to reduce costs and produce feasible production schedule. Setup carryover allows the production setup to be continued between two adjacent periods without incurring extra setup costs and setup times. Setup splitting permits the setup to be partially finished in one period and continued in the next period, utilizing the capacity more efficiently and remove infeasibility of production schedule. The main approaches are that first the simple plant location formulation is adopted to reformulate the original model. Furthermore, an extended formulation by redefining the idle period constraints is developed to make the formulation tighter. Then for the purpose of evaluating the solution quality from heuristic, three types of valid inequalities are added to the model. A fix-and-optimize heuristic with two-stage product decomposition and period decomposition strategies is proposed to solve the formulation. This generic heuristic solves a small portion of binary variables and all the continuous variables rapidly in each subproblem. In addition, the case with demand backlogging is also incorporated to demonstrate that making additional assumptions to the basic formulation does not require to completely altering the heuristic. The contribution of this thesis includes several aspects: the computational results show the capability, flexibility and effectiveness of the approaches. The average optimality gap is 6% for data without backlogging and 8% for data with backlogging, respectively. In addition, when backlogging is not allowed, the performance of fix-and-optimize heuristic is stable regardless of period length. This gives advantage of using such approach to plan longer production schedule. Furthermore, the performance of the proposed solution approaches is analyzed so that later research on similar topics could compare the result with different solution strategies. / Dissertation/Thesis / Masters Thesis Industrial Engineering 2015

In this paper, we introduce two algorithms to address the two-echelon capacitated location-routing problem (2E-CLRP). We introduce a branch-and-cut algorithm based on the solution of a new two-index vehicle-flow formulation, which is strengthened with several families of valid inequalities. We also propose an adaptive large-neighbourhood search (ALNS) meta-heuristic with the objective of finding good-quality solutions quickly. The computational results on a large set of instances from the literature show that the ALNS outperforms existing heuristics. Furthermore, the branch-and-cut method provides tight lower bounds and is able to solve small- and medium-size instances to optimality within reasonable computing times.

The Capacitated Arc Routing Problem has many applications in real life. The aim of this problem is to minimize the total cost at fulfilment of the requirements of arcs. The Capacitated Arc Routing Problem is an extension of the Chinese Postman Problem, which is a special type of the Vehicle Routing Problems. In this thesis is explained the issue of the Chinese Postman Problem and its extensions at first. Subsequently the applications of mathematical models are illustrated on a model example. However these mathematical models, which are searching the optimal solution, do not use so much in reality. Therefore the randomized heuristic algorithm for solving these problems is suggested and programmed in this thesis. Subsequently this heuristic was applied to case study of garbage collection in Podebrady city.

In this dissertation, we introduce new families of valid inequalities for general linear mixed integer programs (MIPs) and second-order conic MIPs (SOCMIPs) and establish several theoretical properties and computational effectiveness of these inequalities. First we introduce the mixed n-step mixed integer rounding (MIR) inequalities for a generalization of the mixing set which we refer to as the n-mixing set. The n-mixing set is a multi-constraint mixed integer set in which each constraint has n integer variables and a single continuous variable. We then show that mixed n-step MIR can generate multi-row valid inequalities for general MIPs and special structure MIPs, namely, multi- module capacitated lot-sizing and facility location problems. We also present the results of our computational experiments with the mixed n-step MIR inequalities on small MIPLIB instances and randomly generated multi-module lot-sizing instances which show that these inequalities are quite effective. Next, we introduce the n-step conic MIR inequalities for the so-called polyhedral second-order conic (PSOC) mixed integer sets. PSOC sets arise in the polyhedral reformulation of SOCMIPs. We first introduce the n-step conic MIR inequality for a PSOC set with n integer variables and prove that all the 1-step to n-step conic MIR inequalities are facet-defining for the convex hull of this set. We also provide necessary and sufficient conditions for the PSOC form of this inequality to be valid. Then, we use the aforementioned n-step conic MIR facet to derive the n-step conic MIR inequality for a general PSOC set and provide conditions for it to be facet-defining. We further show that the n-step conic MIR inequality for a general PSOC set strictly dominates the n-step MIR inequalities written for the two linear constraints that define the PSOC set. We also prove that the n-step MIR inequality for a linear mixed integer constraint is a special case of the n-step conic MIR inequality. Finally, we conduct a polyhedral study of the triplet formulation for the single row facility layout problem (SRFLP). For any number of departments n, we prove that the dimension of the triplet polytope (convex hull of solutions to the triplet formulation) is n(n - 1)(n - 2)/3. We then prove that several valid inequalities presented in Amaral (2009) for this polytope are facet-defining. These results provide theoretical support for the fact that the linear program solved over these valid inequalities gives the optimal solution for all instances studied by Amaral (2009).

Crew pairing and vehicle routing are combinatorial optimization problems that have been studied for many years by researchers worldwide. The aim of this research work is to investigate effective methods for solving large scale crew pairing problems and vehicle routing problems. In the airline industry, to address the complex nature of crew pairing problems, we propose a duty tree method followed by a primal-dual subproblem simplex method. The duty tree approach captures the constraints that apply to crew pairings and generate candidate pairings taking advantage of various proposed strategies. A huge number of legal pairings are stored in the duty tree and can be enumerated. A set partitioning formulation is then constructed, and the problem is solved using a primal-dual subproblem simplex method tailored to the duty tree approach. Computational experiments are conducted to show the effectiveness of the methods. We also present our efforts addressing the capacitated vehicle routing problem (CVRP) that is the basic version of many other variants of the problem. We do not attempt to solve the CVRP instances that have been solved to optimality. Instead, we focus on investigating good solutions for large CVRP instances, with particular emphasis on those benchmark problems from the public online library that have not yet been solved to optimality by other researchers and determine whether we can find new best-known solutions. In this research, we propose a route network that can store a huge number of routes with all routes being legal, a set partitioning formulation that can handle many columns, and the primal-dual subproblem simplex method to find a solution. The computational results show that our proposed methods can achieve better solutions than the existing best-known solutions for some difficult instances. Upon convergence of the primal-dual subproblem simplex method on the giant-tour based networks, we use the near optimal primal and dual solution as well as solve the elementary shortest path problem with resource constraints to achieve the linear programming relaxation global optimal solution.

Simultaneous lot-sizing and scheduling problem is the problem to decide what products to be produced on which machine and in which order, as well as the quantity of each product. Problems of this type are hard to solve. Therefore, they were studied for years, and a considerable number of papers is published to solve different lotsizing and scheduling problems, specifically real-case problems. This work proposes a Real-Coded Genetic Algorithm (RCGA) with a new chromosome representation to solve a non-identical parallel machine capacitated lot-sizing and scheduling problem with sequence dependent setup times and costs, machine cost and backlogging. Such a problem can be found in real world production line at furniture manufacturer in Sweden. Backlogging is an important concept in this problem, and it is often ignored in the literature. This study implements three different types of crossover; one of them has been chosen based on numerical experiments. Four mutation operators have been combined together to allow the genetic algorithm to scan the search area and maintain genetic diversity. Other steps like initializing of the population and a reinitializing process have been designed carefully to achieve the best performance and to prevent the algorithm from trapped into the local optimum. The proposed algorithm is implemented and coded in MATLAB and tested for a set of standard medium to large-size problems taken from the literature. A variety of problems were solved to measure the impact of different characteristics of problems such as the number of periods, machines, and products on the quality of the solution provided by the proposed RCGA. To evaluate the performance of the proposed algorithm, the average deviation from the lower bound and runtime for the proposed RCGA are compared with three other algorithms from the literature. The results show that, in addition to its high computational speed, the proposed RCGA outperforms the other algorithms for non-identical parallel machine problems, while it is outperformed by the other algorithms for problems with the more identical parallel machine. The results show that the different characteristics of problem instances, like increasing setup cost, and size of the problem influence the quality of the solutions provided by the proposed RCGA negatively.

Submitted by Silvana Teresinha Dornelles Studzinski (sstudzinski) on 2017-03-16T12:00:50Z No. of bitstreams: 1 Márcio Joel Barth_.pdf: 2194609 bytes, checksum: 0c1a7161c69d20257d7c5bbfd9340a30 (MD5) / Made available in DSpace on 2017-03-16T12:00:50Z (GMT). No. of bitstreams: 1 Márcio Joel Barth_.pdf: 2194609 bytes, checksum: 0c1a7161c69d20257d7c5bbfd9340a30 (MD5) Previous issue date: 2016-11-25 / PROCERGS - Companhia de Processamento de Dados do Estado do Rio Grande do Sul / Estudos sobre infraestrutura de redes têm sido realizados e aplicados em várias indústrias de serviços, tais como telecomunicações, distribuição de energia, água e mais recentemente para atendimento das necessidades de infraestrutura de cidades inteligentes que requerem soluções de infraestrutura híbridas. Entretanto, o planejamento de infraestrutura de redes em vários níveis e também com máxima cobertura, é um problema em aberto, pois, geralmente, a literatura apresenta soluções nas quais somente um nível é processado e os problemas são solucionados de forma individual. O planejamento da distribuição e conexão de equipamentos em vários níveis de uma infraestrutura de rede é uma tarefa árdua, pois é necessário avaliar a quantidade e a melhor distribuição geográfica de equipamentos em cada nível da rede, ou seja, no nível 1 são avaliadas as necessidades que atendem diretamente aos clientes, já o nível 2 atenderá as necessidades do nível 1, e que também sejam observados os níveis adjacentes. O resultado que um projetista obtém ao realizar manualmente o planejamento torna-se superficial, devido a inviabilidade de analisar todos os cenários que podem ser obtidos com as informações de quantidades e de distribuição dos equipamentos na região do projeto. Ainda mais complexo é alterar um nível já projetado, visto que é necessário rever a quantidade, localização e caminho entre os equipamentos, refazendo os cálculos do nível alterado, e, consequentemente, o nível anterior e todos os níveis subsequentes. Esta pesquisa apresenta um algoritmo baseado na metaheuristica de colônia de formigas, capaz de procurar por uma solução para o planejamento de infraestrutura de redes híbridas multiníveis capacitadas, resolvendo o problema de recobrimento e planejamento de redes de forma conjunta e obtendo resultados melhores na ordem de 20% no custo da solução quando comparado com outra solução que utiliza algoritmo genético. / Studies on network infrastructure have been used and applied in various service industries, such as telecommunications, power distribution, water, and more recently to meet the smart city infrastructure needs, that require hybrid infrastructure solutions. However, planning multilevel network infrastructures and also with maximum coverage is an open problem, since the literature generally presents solutions in which only one level is processed and problems solved individually. The distribution plan and equipment connection at various levels of a network infrastructure is a ardous task, it is necessary to evaluate the quantity and better geographical distribution of equipment at each level of the network, ie at level 1 are evaluated needs to meet directly to customers, since the level 2 from level 1 will meet the needs, and the adjacent levels are also observed. The result that a designer gets to manually carry out the planning becomes shallow due to impossibility of analyzing all scenarious that can be obtained with the amounts and distribution of information equipment in the project region. Even more complex is change a level already designed, since it is necessary to review the amount, location and path between devices, redoing the calculations of the modified level, and hence the previous level and all subsequent levels. This research presents an algorithm based on ant colony metaheuristics, capable of searching for a solution to the infrastructure planning of hybrid multilevel networks, solving the network planning and coverage problem together and obtaining better results in the order of 20% on the cost of the solution when compared to another solution using genetic algorithm.

The minimum set cover problem is, without question, among the most ubiquitous and well-studied problems in computer science. Its theoretical hardness has been fully characterized--logarithmic approximability has been established, and no sublogarithmic approximation exists unless P=NP. However, the gap between real-world instances and the theoretical worst case is often immense--many covering problems of practical relevance admit much better approximations, or even solvability in polynomial time. Simple combinatorial or geometric structure can often be exploited to obtain improved algorithms on a problem-by-problem basis, but there is no general method of determining the extent to which this is possible. In this thesis, we aim to shed light on the relationship between the structure and the hardness of covering problems. We discuss several measures of structural complexity of set cover instances and prove new algorithmic and hardness results linking the approximability of a set cover problem to its underlying structure. In particular, we provide: - An APX-hardness proof for a wide family of problems that encode a simple covering problem known as Special-3SC. - A class of polynomial dynamic programming algorithms for a group of weighted geometric set cover problems having simple structure. - A simplified quasi-uniform sampling algorithm that yields improved approximations for weighted covering problems having low cell complexity or geometric union complexity. - Applications of the above to various capacitated covering problems via linear programming strengthening and rounding. In total, we obtain new results for dozens of covering problems exhibiting geometric or combinatorial structure. We tabulate these problems and classify them according to their approximability.