We introduce two online models for the vertex k-center and the vertex k-median problems. Clients (i.e., graph vertices) and their corresponding links (i.e., graph edges) are revealed sequentially, determining the topology of a graph over time. Clients are revealed by an adversary to an online algorithm that selects existing graph vertices on which to open facilities; once open, a facility cannot be removed or relocated. We define two models: an online algorithm may be restricted to open a facility only at the location of the most recent client or at the location of any existing client. We examine these models on three classes of graphs under two types of adversaries. We establish lower bounds on the respective competitive ratios attainable by any online algorithm for each combination of model, adversary, and graph class. Finally, we describe algorithms whose competitive ratios provide corresponding upper bounds on the best competitive ratios achievable.

In this thesis, we generalize a set of facility location models within a two-stage robust optimization framework by assuming each demand is only known to lie within a continuous and bounded uncertainty region. Our approach involves discretizing each uncertainty region into a set of finite scenarios, each of which represents a potential location where the demand may be realized. We show that the gap between the optimal values of the theorized continuous uncertainty problem and our discretized model can be bounded by a function of the granularity of the discretization. We then propose a solution technique based on row-and-column generation, and compare its performance with existing solution methods. Lastly, we apply our robust location models to the problem of ambulance positioning using cardiac arrest location data from the City of Toronto, and show that hedging against demand location uncertainty may help decrease EMS response times to cardiac arrest emergencies.

In this thesis, we generalize a set of facility location models within a two-stage robust optimization framework by assuming each demand is only known to lie within a continuous and bounded uncertainty region. Our approach involves discretizing each uncertainty region into a set of finite scenarios, each of which represents a potential location where the demand may be realized. We show that the gap between the optimal values of the theorized continuous uncertainty problem and our discretized model can be bounded by a function of the granularity of the discretization. We then propose a solution technique based on row-and-column generation, and compare its performance with existing solution methods. Lastly, we apply our robust location models to the problem of ambulance positioning using cardiac arrest location data from the City of Toronto, and show that hedging against demand location uncertainty may help decrease EMS response times to cardiac arrest emergencies.

We introduce two online models for the vertex k-center and the vertex k-median problems. Clients (i.e., graph vertices) and their corresponding links (i.e., graph edges) are revealed sequentially, determining the topology of a graph over time. Clients are revealed by an adversary to an online algorithm that selects existing graph vertices on which to open facilities; once open, a facility cannot be removed or relocated. We define two models: an online algorithm may be restricted to open a facility only at the location of the most recent client or at the location of any existing client. We examine these models on three classes of graphs under two types of adversaries. We establish lower bounds on the respective competitive ratios attainable by any online algorithm for each combination of model, adversary, and graph class. Finally, we describe algorithms whose competitive ratios provide corresponding upper bounds on the best competitive ratios achievable.

The views expressed in this thesis are those of the author and do not reflect the official policy or position of the Department of Defense or the U.S. Government. / Determining the best base stationing for military units can be modeled as a capacitated facility location problem with sole sourcing and multiple resource categories. Computational experience suggests that cross decomposition, a unification of Benders Decomposition and Lagrangean relaxation, is superior to other contemporary methods for solving capacitated facility location problems. Recent research extends cross decomposition to pure integer prograrnming problems with explicit application to capacitated facility location problems with sole sourcing; however, this research offers no computational experience. This thesis implements two cross decomposition algorithms for the capacitated facility location problem with sole sourcing and compares these decomposition algorithms with branch and bound methods. For some problems tested, cross decomposition obtains better solutions in less time; however, cross decomposition does not always perform better man branch and bound due to the time required to obtain the cross decomposition bound that is theoretically superior to other decomposition bounds.

The capacitated facility location problem is a well known problem in combinatorial optimization and operations research. In it, we are given a set of clients and a set of possible facility locations. Each client has a certain demand that needs to be satisfied from open facilities, without exceeding their capacity. Whenever we open a facility we incur in a corresponding opening cost. Whenever demand is served, we incur in an assignment cost; depending on the distance the demand travels. The goal is to open a set of facilities that satisfy all demands while minimizing the total opening and assignment costs. In this thesis, we present two novel LP-based approximation algorithms for the capacitated facility location problem. The first algorithm is based on LP-rounding techniques, and is designed for the special case of the capacitated facility location problem where capacities are uniform and assignment costs are given by a tree metric. The second algorithm follows a primal-dual approach, and works for the general case. For both algorithms, we obtain an approximation guarantee that is linear on the size of the problem. To the best of our knowledge, there are no LP-based algorithms known, for the type of instances that we focus on, that achieve a better performance.

No description available.

The area of facilities location covers a wide variety of problems involving both public and private sector applications. To date, the study of location problems has been restricted primarily to deterministic formulations of the problem. The present research effort investigates the effect of random variation on the location decision. Three location problems are considered: the single facility location problem, the multifacility location problem, and the emergency service location problem. The first two problems treated are defined as the generalized Weber problem, where the concern is to locate one or more new facilities in the plane relative to several existing facilities such that the expected total cost of item movements is minimized. The total cost function is considered to be a linear function of either the expected rectilinear or the Euclidean distance, as well as a quadratic function of the expected Euclidean distance. In the generalized Weber problem the locations of the existing facilities and the item movement between facilities are considered to be random variables. Two expected total cost formulations are presented; the first involves the product of the random variables, weight and distance; the second involves the random sum of each individual distance traveled. For each formulation, possible applications are discussed, theoretical properties are developed, and a solution procedure is provided. Each algorithm is programmed and optimal solutions are obtained for several example problems. A comparison between the probabilistic and deterministic solutions is provided. Both discretely and continuously distributed random variables are treated; however, for the case of continuously distributed random variables, the normal distribution is emphasized. Both constrained and unconstrained formulations are considered. In formulating the emergency service facilities location problems which are studied, random variation is assumed to be present due to the assumption that the location of an incident is a random variable occurring uniformly over a given region. Both discrete space and continuous space formulations are considered. For the discrete case, a covering criterion is employed and the deterministic equivalent problem is solved as a set cover problem. For the continuous case, the problem is solved as a location-allocation problem. In all formulations, the rectilinear norm is used to measure the distance traveled. An example is solved for each case to illustrate the impact of probabilistic aspects on the location decision. / Ph. D.

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.