Generalization of restricted planar location problems : unified meta-heuristics for single facility case

Download
index.pdf
2013
Farham, Mohammad Saleh
Show full item record
174
views
79
downloads
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 or penalty can be thought of the cost of risks taken when passing through the region or the cost of purchasing license or special equipment in order to be able to pass through the region. In this study we show that the restricted planar location problem with congested regions having fixed traveling costs maintains generality over two most studied related location problems in the literature, namely restricted planar facility location problems with forbidden regions and barriers. It is shown that this problem is non-convex and nonlinear under Euclidean distance metric; hence using heuristic approaches is reasonable. We propose three meta-heuristic algorithms, namely simulated annealing, evolutionary algorithm, and particle swarm optimization based on variable neighborhood search to solve the problem. The proposed algorithms are applied on test instances taken from the literature and the favorable computational results are presented.
Heuristic algorithms., Heuristic programming., Business logistics., Materials management.
http://etd.lib.metu.edu.tr/upload/12615417/index.pdf
https://hdl.handle.net/11511/22375
Graduate School of Natural and Applied Sciences, Thesis

Suggestions

Solution approaches for single-source capacitated multi facility weber problem
Damgacıoğlu, Haluk; İyigün, Cem; Department of Industrial Engineering (2014)
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 ...
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...
A branch and bound algorithm to minimize the total flow time for m-machine permutation flowshop problems
Chung, CS; Flynn, J; Kirca, O (Elsevier BV, 2002-10-11)
The m-machine permutation flowshop problem with the total flow-time objective is a common scheduling problem, which is known to be NP-hard for m greater than or equal to 2. In this article, we develop a branch and bound algorithm to solve both the weighted and unweighted version of this problem. Our algorithm incorporates a new machine-based lower bound and a dominance test for pruning nodes. Computational experiments suggest that the algorithm can handle test problems with n less than or equal to 15. It al...
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...
Heuristics for a continuous multi-facility location problem with demand regions
Dinler, Derya; Tural, Mustafa Kemal; İyigün, Cem; Department of Operational Research (2013)
We consider a continuous multi-facility location problem where the demanding entities are regions in the plane instead of points. Each region may consist of a finite or an infinite number of points. The service point of a station can be anywhere in the region that is assigned to it. We do not allow fractional assignments, that is, each region is assigned to exactly one facility. The problem we consider can be stated as follows: given m demand regions in the plane, find the locations of q facilities and allo...
Citation Formats
M. S. Farham, “ Generalization of restricted planar location problems : unified meta-heuristics for single facility case,” M.S. - Master of Science, Middle East Technical University, 2013.
METU IIS - Integrated Information Service open@metu.edu.tr