We consider the lower-bounded facility location (LBFL) problem (, also known as load-balanced facility location), which is a generalization of uncapacitated facility location (UFL) problem where each open facility is required to serve a minimum number of clients. More formally, in the LBFL problem, we are given a set of clients Ɗ , a set of facilities Ƒ, a non-negative facility-opening cost f_i for each i ∈ Ƒ, a lower bound M, and a distance metric c(i,j) on the set Ɗ ∪ Ƒ, where c(i,j) denotes the cost of assigning client j to facility i. A feasible solution S specifies the set of open facilities F_S ⊆ Ƒ and the assignment of each client j to an open facility i(j) such that each open facility serves at least M clients. Our goal is to find feasible solution S that minimizes ∑_{i ∈ F_S} f_i + ∑_j c(i,j). The current best approximation ratio for LBFL is 550. We substantially advance the state-of-the-art for LBFL by devising an approximation algorithm for LBFL that achieves a significantly-improved approximation guarantee of 83.

We consider the lower-bounded facility location (LBFL) problem (, also known as load-balanced facility location), which is a generalization of uncapacitated facility location (UFL) problem where each open facility is required to serve a minimum number of clients. More formally, in the LBFL problem, we are given a set of clients Ɗ , a set of facilities Ƒ, a non-negative facility-opening cost f_i for each i ∈ Ƒ, a lower bound M, and a distance metric c(i,j) on the set Ɗ ∪ Ƒ, where c(i,j) denotes the cost of assigning client j to facility i. A feasible solution S specifies the set of open facilities F_S ⊆ Ƒ and the assignment of each client j to an open facility i(j) such that each open facility serves at least M clients. Our goal is to find feasible solution S that minimizes ∑_{i ∈ F_S} f_i + ∑_j c(i,j). The current best approximation ratio for LBFL is 550. We substantially advance the state-of-the-art for LBFL by devising an approximation algorithm for LBFL that achieves a significantly-improved approximation guarantee of 83.

Discrete location analysis is one of the most widely studied branches of operations research, whose applications arise in a wide variety of settings. This thesis describes a powerful new approach to facility location problems - that of message passing inference in probabilistic graphical models. Using this framework, we develop new heuristic algorithms, as well as a new approximation algorithm for a particular problem type. In machine learning applications, facility location can be seen a discrete formulation of clustering and mixture modeling problems. We apply the developed algorithms to such problems in computer vision. We tackle the problem of motion segmentation in video sequences by formulating it as a facility location instance and demonstrate the advantages of message passing algorithms over current segmentation methods.

[pt] A distribuição de produtos nos segmentos varejistas é, além de processo básico do negócio, um processo estratégico para o posicionamento das organizações em um mercado caracterizado pelo consumo impulsivo, ou seja, é preciso estar sempre à disposição do consumidor e pelo menor preço disponível no mercado. Para atender estas restrições torna-se fundamental uma excelente abordagem ao mercado sob o foco de maximização das margens de lucro e um posicionamento crescente de vendas. A Cargill S/A com a visão de ganhar mercado de seus concorrentes na Região Nordeste identificou a necessidade de redução de preços ao consumidor, sem prejudicar suas margens de lucro e aumentar a velocidade do seu atendimento na Região. Para atendimento a estas perspectivas estratégicas da empresa em relação ao mercado alimentício de óleos especiais no Nordeste foi elaborado um Estudo de Viabilidade Logístico para atendimento à Região. A dissertação apresenta a descrição de um Estudo de Viabilidade. Onde os objetivos concentram-se em: definir a localização de em Centro de Distribuição através de formulações matemáticas, a escolha de prestadores de serviços logísticos através da utilização do método AHP e análise comparativa de custos através de ferramenta analítica de custos de distribuição. Também são apresentados resultados como: redução de 9,63% do custo de distribuição de produtos, redução de 75,42% de transit time para entrega de produtos ao cliente final e definição de operadores logísticos para transportes e armazenagem de produtos. / [en] The distribution of products in the retail segments is, beyond basic process of the business, a strategically process for the positioning of the organizations in a market characterized for the impulsive consumption, that is, it is necessary to be always to the disposal of the consumer and for the lesser available price in the market. To take care of these restrictions one becomes basic an excellent boarding the market under the focus of maximizes of the profit edges and an increasing positioning of sales. Cargill S/A with the vision to gain market of its competitors in the Northeast Region identified the necessity of reduction of prices to the consumer, without harming its edges of profit and increasing the speed of its attendance in the Region. For attendance to these strategically perspectives of the company in relation to the nourishing north-eastern special oil market a Logistic Feasibility study for attendance to the Region was elaborated. The text presents the description of a Feasibility study. Where the objectives are concentrated in: to define the localization of in Center of Distribution through mathematical formularizations, the choice of rendering of logistic services through the use of method AHP and comparative analysis of costs through analytical tool of distribution costs. Also they are presented resulted as: reduction of 9,63% of the cost of distribution of products, reduction of 75,42% of transit time for delivery of products to the final customer and definition of logistic operators for transports and storage of products.

This dissertation studies models for locating facilities in time varying demand environments. We describe the characteristics of the time varying demand that motivate the analysis of our location models in terms of total demand and the change in value and location of the demand of each customer. The first part of the dissertation is devoted to the dynamic location model, which determines the optimal time and location for establishing capacitated facilities when demand and cost parameters are time varying. This model minimizes the total cost over a discrete and finite time horizon for establishing, operating, and closing facilities, including the transportation costs for shipping demand from facilities to customers. The model is solved using Lagrangian relaxation and Benders? decomposition. Computational results from different time varying total demand structures demonstrate, empirically, the performance of these solution methods. The second part of the dissertation studies two location models where relocation of facilities is not allowed and the objective is to determine the optimal location of capacitated facilities that will have a good performance when demand and cost parameters are time varying. The first model minimizes the total cost for opening and operating facilities and the associated transportation costs when demand and cost parameters are time varying. The model is solved using Benders? decomposition. We show that in the presence of high relocation costs of facilities (opening and closing costs), this model can be solved as a special case by the dynamic location model. The second model minimizes the maximum regret or opportunity loss between a robust configuration of facilities and the optimal configuration for each time period. We implement local search and simulated annealing metaheuristics to efficiently obtain near optimal solutions for this model.

A destructive earthquake is anticipated to occur in Istanbul in the near future. The effects of this earthquake on human, infrastructure and economy are anticipated to be enormous. The Metropolitan Municipality of Istanbul has initiated a disaster plan to mitigate the effects of the disaster. Locating disaster response facilities to execute post-disaster activities and relief operations is a part of this plan. In this study, we address the disaster response and relief facility location problem for Istanbul. Our aim is to study the situation and provide insights on the effects of the number of facilities and their locations. We propose a two-stage distribution system that utilizes existing public facilities as well as the new facilities to be established. We develop a mathematical model that tries to minimize the average distance to the population who need relief services while opening a small number of facilities. We analyze the trade-offs between these two objectives under various circumstances and present the results.

This report presents an optimization of the allocation of maintenance resources for Air Navigation Service (ANS) equipment of which LFV is responsible for the maintenance. The purpose the authors have worked after is to research ways of minimizing travelling time linked to maintenance visits for ANS equipment, this report includes the suggestions where the maintenance facilities should be placed in order to minimize the total travelling time. The report describes the problem background and presents the customer, LFV. It includes a chapter on some of the theories used for facility location and routing, and also presents methods for reducing the total travelling time used for maintenance visits annually. The authors have worked with a given set of airports in Sweden. Information about the general work with maintenance as well as the annual demand of maintenance, including the frequency of visits, for each airport included in this project was received by Pär Oberger, the task expert and contact at LFV for this report. A model for facility location based on the p-median model have been created and used when solving the problem, it was written in AMPL and solved with the CPLEX solver. The model was modified with two additional constraints regulating the minimum annual working time and the maximum distance for one-way travelling. The authors deems that a solution with five facilities is better since the benefit of additional facilities, in term of lower total distance, do not compensate for the assumed cost of establishing them.

Discrete location analysis is one of the most widely studied branches of operations research, whose applications arise in a wide variety of settings. This thesis describes a powerful new approach to facility location problems - that of message passing inference in probabilistic graphical models. Using this framework, we develop new heuristic algorithms, as well as a new approximation algorithm for a particular problem type. In machine learning applications, facility location can be seen a discrete formulation of clustering and mixture modeling problems. We apply the developed algorithms to such problems in computer vision. We tackle the problem of motion segmentation in video sequences by formulating it as a facility location instance and demonstrate the advantages of message passing algorithms over current segmentation methods.

Made available in DSpace on 2015-05-08T14:53:16Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 1804871 bytes, checksum: 3742cf56fa1697798272feaab03570e7 (MD5) Previous issue date: 2011-03-31 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work presents a computational system that integrated with a WebGIS system, has the function to optimize the problems of facility location. System access is via a web browser and Internet connection, and aims to generate the array of actual distances between clients and facilitators. The system was applied to the problem of fnding points of collection and transmission, faced by the Brazilian electoral system in order to assist in decision making about the best locations for installation of such points. The order of the court is to minimize the sum of the total distances traveled, and also have the option to minimize the maximum distance. In this example of applicability of the treaty system was the P-median problem with GRASP. / Este trabalho apresenta um sistema computacional que, integrado com um sistema WebGIS, tem a função de otimizar os problemas de localização de medianas e cobertura. O acesso ao sistema se dá através de um navegador web e conexão com a internet e, se propõe a gerar a matriz de distâncias reais entre clientes e facilitadores. O Sistema foi aplicado ao problema de localização de pontos de coleta e transmissão, enfrentado pelo sistema eleitoral brasileiro, a fim de auxiliá-lo na tomada de decisão acerca dos melhores locais para instalação de tais pontos. O intuito do tribunal é minimizar o somatório das distâncias totais percorridas, bem como também ter a opção de minimizar a máxima distância percorrida. Para ilustrar a utilização do Sistema foi feita uma aplicação do mesmo no Tribunal Regional Eleitoral da Paraíba onde o mesmo conseguiu diminuir em, no mínimo, 23% o somatório da distância total percorrida dos locais de votação até os pontos de coleta e transmissão de votos e diminuir em 70% a distância máxima percorrida entre o local de votação e seu respectivo PCT. Neste exemplo de aplicabilidade do sistema foi tratado o problema P-mediana com a metaheurística GRASP que também foi testada em instâncias da biblioteca OR-Library e atingiu a solução ótima em mais de 62% dos casos.

The focus of this thesis is the development and solution of problems that simultaneously involve the planning of the location of facilities and transportation decisions from such facilities to consumers. This has been termed integrated distribution planning problems with practical application in logistics and manufacturing. In this integration, different planning horizons of short, medium and long terms are involved with the possibility of reaching sub-optimal decisions being likely when the planning horizons are considered separately. Two categories of problems were considered under the integrated distribution models. The first is referred to as the Step-Fixed Charge Location and Transportation Problem (SFCLTP). The second is termed the Fixed Charge Solid Location and Transportation Problem (FCSLTP). In these models, the facility location problem is considered to be a strategic or long term decision. The short to medium-term decisions considered are the Step-Fixed Charge Transportation Problem (SFCTP) and the Fixed Charge Solid Transportation Problem (FCSTP). Both SFCTP and FCSTP are different extensions to the classical transportation problem, requiring a trade-off between fixed and variable costs along the transportation routes to minimize total transportation costs. Linearization and subsequent local improvement search techniques were developed to solve the SFCLTP. The first search technique involved the development of a hands-on solution including a numerical example. In this solution technique, linearization was employed as the primal solution, following which structured perturbation logic was developed to improve on the initial solution. The second search technique proposed also utilized the linearization principle as a base solution in addition to some heuristics to construct transportation problems. The resulting transportation problems were solved to arrive at a competitive solution as regards effectiveness (solution value) compared to those obtainable from standard solvers such as CPLEX. The FCSLTP is formulated and solved using the CPLEX commercial optimization suite. A Lagrange Relaxation Heuristic (LRH) and a Hybrid Genetic Algorithm (GA) solution of the FCSLTP are presented as alternative solutions. Comparative studies between the FCSTP and the FCSLTP formulation are also presented. The LRH is demonstrated with a numerical example and also extended to hopefully generate improved upper bounds. The CPLEX solution generated better lower bounds and upper bound when compared with the extended LRH. However, it was observed that as problem size increased, the solution time of CPLEX increased exponentially. The FCSTP was recommended as a possible starting solution for solving the FCSLTP. This is due to a lower solution time and its feasible solution generation illustrated through experimentation. The Hybrid Genetic Algorithm (HGA) developed integrates cost relaxation, greedy heuristic and a modified stepping stone method into the GA framework to further explore the solution search space. Comparative studies were also conducted to test the performance of the HGA solution with the classical Lagrange heuristics developed and CPLEX. Results obtained suggests that the performance of HGA is competitive with that obtainable from a commercial solver such as CPLEX. / Thesis (PhD)--University of Pretoria, 2019. / Industrial and Systems Engineering / PhD / Unrestricted