11 |
Online problems in facility locationMehrabidavoodabadi, Saeed 22 August 2012 (has links)
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.
|
12 |
Robust Facility Location under Demand Location UncertaintySiddiq, Auyon 28 November 2013 (has links)
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.
|
13 |
Robust Facility Location under Demand Location UncertaintySiddiq, Auyon 28 November 2013 (has links)
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.
|
14 |
Online problems in facility locationMehrabidavoodabadi, Saeed 22 August 2012 (has links)
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.
|
15 |
Facility Location Using Cross DecompositionJackson, Leroy A. 12 1900 (has links)
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.
|
16 |
LP-based Approximation Algorithms for the Capacitated Facility Location ProblemBlanco Sandoval, Marco David January 2012 (has links)
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.
|
17 |
Analysis of AM Hub Locations for Hybrid Manufacturing in the United StatesStrong, Danielle B. 24 May 2017 (has links)
No description available.
|
18 |
Probabilistic formulations of some facility location problemsAly, Adel Ahmed 11 May 2010 (has links)
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.
|
19 |
Message Passing Algorithms for Facility Location ProblemsLazic, Nevena 09 June 2011 (has links)
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.
|
20 |
[en] PROPOSAL OF LOGISTICS MODEL FROM THE FOOD INDUSTRY TO ATTENDENCE NORTHEAST REGION / [pt] PROPOSTA DE REDESENHO LOGÍSTICO DA INDÚSTRIA DE ALIMENTOS PARA ATENDIMENTO À REGIÃO NORDESTEADIEMIR HORTEGA MEDEIROS 11 November 2008 (has links)
[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.
|
Page generated in 0.1341 seconds