Solution approaches for single-source capacitated multi facility weber problem

Download
index.pdf
2014
Damgacıoğlu, Haluk
Show full item record
284
views
269
downloads
Single Source Capacitated Multi Facility Location Problem (SSCMFLP) is a continuous location-allocation problem such that determining the locations of p facilities in the plane and allocations of n demand points to only one facility by considering the capacity restriction of each facility so as to minimize total transportation cost to satisfy n demand points from p facilities. In addition to Mixed Integer Non-Linear Programming formulation of the problem in the literature, we give a new formulation for the problem using Second Order Cone Programming. Since the problem is a variant of MWP well-known NP-hard planar location-allocation problem and it is easily reducible to MWP, SSCMWP is hard to solve and it can be classified in NPhard. Therefore, these two formulations do not solve the problem optimally even for small and medium size problems. Moreover, in this study, we propose three heuristics based on two phase location allocation algorithm iteratively to tackle the problem effectively and efficiently. We first find the initial locations of facilities by using Pdistance clustering algorithm. We solve allocation part with given locations by solving generalized assignment problem (GAP) and then by using new assignments we determine each facility location by using P-distance clustering algorithm iteratively. Our heuristics differ in solution approaches for GAP. we solve the problem optimally by using CPLEX. Since CPLEX is an exponential time solver, we give two alternative heuristics for CPLEX which are branch and bound heuristic and Very Large Scale Neighborhood Search (VLNS). We tested our heuristics’ performance by comparing results with each other and other heuristics in the literature on well-known test data for continuous location problems.
Facility management., Plant engineering., Heuristic algorithms., Branch and bound algorithms.
http://etd.lib.metu.edu.tr/upload/12617544/index.pdf
https://hdl.handle.net/11511/23753
Graduate School of Natural and Applied Sciences, Thesis

Suggestions

Generalization of restricted planar location problems : unified meta-heuristics for single facility case
Farham, Mohammad Saleh; Süral, Haldun; İyigün, Cem; Department of Industrial Engineering (2013)
A planar single facility location problem, also known as the Fermat–Weber problem, is to find a facility location such that the total weighted distance to a set of given demand points is minimized. A variation to this problem is obtained if there is a restriction coming from congested regions. In this study, congested regions are considered as arbitrary shaped polygonal areas on the plane where location of a facility is forbidden and traveling is charged with an additional fixed cost. The traveling fixed cost ...
A Multi-level continuous minimax location problem with regional demand
Faridyahyaei, Amin; Tural, Mustafa Kemal; Department of Industrial Engineering (2017)
The minimax facility location problem seeks for the optimal locations of the facilities in the plane so that the maximum Euclidean distance between the demanding entities (given points in the plane) and their corresponding nearest facilities is minimized. In the solutions, remote entities (irrespective of their weights) tend to pull the facilities toward themselves which may result in larger distances for the other entities. In this thesis, we consider a multi-level minimax location problem which allows som...
Solution methods for a min-max facility location problem with regional customers considering closest Euclidean distances
DOLU HASTÜRK, NAZLI; HASTÜRK, UMUR; Tural, Mustafa Kemal (Springer Science and Business Media LLC, 2020-03-01)
We study a facility location problem where a single facility serves multiple customers each represented by a (possibly non-convex) region in the plane. The aim of the problem is to locate a single facility in the plane so that the maximum of the closest Euclidean distances between the facility and the customer regions is minimized. Assuming that each customer region is mixed-integer second order cone representable, we firstly give a mixed-integer second order cone programming formulation of the problem. Sec...
The Weber problem in congested regions with entry and exit points
Farham, Mohammad Saleh; Süral, Haldun; İyigün, Cem (2015-10-01)
The Weber problem is about finding a facility location on a plane such that the total weighted distance to a set of given demand points is minimized. The facility location and access routes to the facility can be restricted if the Weber problem contains congested regions, some arbitrary shaped polygonal areas on the plane, where location of a facility is forbidden and traveling is allowed at an additional fixed cost. Traveling through congested regions may also be limited to certain entry and exit points (o...
An interactive solution approach for a bi-objective semi-desirable location problem
Karasakal, Esra (Springer Science and Business Media LLC, 2008-10-01)
In this study, we consider a semi-desirable facility location problem in a continuous planar region considering the interaction between the facility and the existing demand points. A facility can be defined as semi-desirable if it has both undesirable and desirable effects to the people living in the vicinity. Our aim is to maximize the weighted distance of the facility from the closest demand point as well as to minimize the service cost of the facility. The distance between the facility and the demand poi...
Citation Formats
H. Damgacıoğlu, “Solution approaches for single-source capacitated multi facility weber problem,” M.S. - Master of Science, Middle East Technical University, 2014.
METU IIS - Integrated Information Service open@metu.edu.tr