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


Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2013

Öğrenci: MOHAMMAD SALEH FARHAM

Eş Danışman: CEM İYİGÜN, HALDUN SÜRAL

Özet:

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.