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

Thesis Type: Postgraduate

Institution Of The Thesis: Orta Doğu Teknik Üniversitesi, Faculty of Engineering, Department of Industrial Engineering, Turkey

Approval Date: 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 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.