Planar p-center problem with tchebychev distance

Abstract

ÖZET TCHEBYCHEV UZAKLIKLI YÜZEYEL P-MERKEZ PROBLEMİ Dilek Yılmaz Endüstri Mühendisliği, Yüksek Lisans Danışman: Doç. Barbaros Tansel Eylül 1994 p-Merkez problemi, p tesisi talepleri karşılamak üzere en uzak talep ve ona en yakm tesis arasındaki uzaklık en küçüklenecek şekilde yerleştirme modelidir. Acil hizmet tesisleri ( itfaiye, hastane vb.) genellikle bu tarzda yerleştirilirler. Bu tez çalışmasında, Tchebychev uzaklıklı yüzeyel p-merkez problemi ele alınır. Problem NP- Zordur. Birtakım polinom çözümlü halleri belirliyor ve polinom çözümlü alt problemleri kullanan bir dallama algoritması sunuyoruz. Ayrıca, literatürdeki ağaç serimlerdeki p-merkez problemi ikil problemi çalışmalarının ışığı altında bir ikil problem öneriyoruz. Anahtar Sözcükler: p-Merkez, r-Kaplama, İkil Problem

ABSTRACT PLANAR P-CENTER PROBLEM WITH TCHEBYCHEV DISTANCE Dilek Yılmaz M.S. in Industrial Engineering Advisor: Assoc. Prof. Barbaros Tansel September, 1994 The p-center problem is a model for locating p facilities to serve clients so that the distance between a farthest client and its closest facility is minimized. Emergency service facilities such as fire stations, hospitals and police stations are most of the time located in this manner. In this thesis, the planar p-center problem with Tchebychev distance is studied. The problem is known to be NP- Hard. We identify certain polynomial time solvable cases and give an efficient branching method which makes use of polynomial time methods in subproblem solutions whenever possible. In addition, a dual ^problem is posed in light of the existing duality theory on tree networks. Keywords: p-Center, r-Cover, Duality IV