Geri Dön

Heuristics for a continuous multi-facility location problem with demand regions

Talep alanları düşünülerek sürekli düzlemde çok tesisli yer seçimi problemi için sezgisel yöntemler

  1. Tez No: 341016
  2. Yazar: DERYA DİNLER
  3. Danışmanlar: YRD. DOÇ. DR. MUSTAFA KEMAL TURAL, YRD. DOÇ. DR. CEM İYİGÜN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2013
  8. Dil: İngilizce
  9. Üniversite: Orta Doğu Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Yöneylem Araştırması Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 114

Özet

Bu çalışmada sürekli düzlemde çok tesisli yer seçimi problemi üzerinde çalışılmıştır. Fakat problemde talep noktaları yerine talep alanları düşünülmüştür. Her talep alanında sonlu ya da sonsuz sayıda talep noktası olabilir. Bir tesisin servis sunacağı nokta kendisine atanmış olan talep alanının herhangi bir yerinde bulunabilir. Bu çalışmada kısmi atamaya izin verilmemekte ve her talep alanı yalnızca bir tesise atanabilmektedir. Üzerinde çalıştığımız problem kısaca şu şekilde ifade edilebilir: servis sunulması gereken m tane talep alanı varken, q tane tesis yerini talep alanları ve atanmış oldukları tesisler arasındaki maksimum uzaklıkların karelerini en azlayacak şekilde bulmak ve talep alanlarını bulunan tesislere atamak. Herhangi bir alan istenen herhangi bir kesinlik seviyesinde bir poligona benzetilebildiği için bu çalışmada talep alanlarının kapalı poligonlar olduğu varsayılmıştır. Çalışmamızda ilk olarak tek ve çok tesisli yer seçimi problemleri için matematiksel programlama formülasyonları önerdik. Tek tesisli yer seçimi problemini polinom zamanda çözülebilen ikinci dereceden konik programlama (SOCP) formülasyonu ile modelledik. Çok tesisli yer seçimi problemi için karışık tamsayılı ikinci dereceden konik programlama formülasyonu kullandık. Bu formülasyon zayıf bir formülasyondur ve orta büyüklükteki problemleri bile çözememektedir. Bu yüzden çok tesisli büyük yer seçimi problemlerini çözebilmek için sezgisel yöntemler önerdik. Talep alanları poligon olduğunda kullanabilen 3 tane sezgisel yöntem geliştirdik. Ayrıca talep alanlarının kenarları koordinat eksenlerine paralel dikdörtgensel alanlar olduğu durum için özel bir sezgisel yöntem geliştirdik. Sezgisel yöntemlerimizi hem çözüm kaliteleri hem de çözüm süreleri bakımından karşılaştırdık.

Özet (Çeviri)

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 allocate regions to the facilities so as to minimize the sum of squares of the maximum Euclidean distances of the demand regions to the facility locations they are assigned to. We assume that the regions are closed polygons as any region can be approximated within any desired accuracy with a polygon. We first propose mathematical programming formulations of single and multiple facility location problems. The single facility location problem is formulated as a second order cone program (SOCP) which can be solved in polynomial time. The multiple facility location problem is formulated as a mixed integer SOCP. This formulation is weak and does not even solve medium-size problems. We therefore propose heuristics to solve larger instances of the problem. We develop three heuristics that work when the regions are polygons. When the demand regions are rectangles with sides parallel to coordinate axes, a special heuristic is developed. We compare our heuristics in terms of both solution quality and computational time.

Benzer Tezler

  1. A multi-level continuous minimax location problem with regional demand

    Bölgesel talepli çok seviyeli sürekli minimax yer seçimi problemi

    AMIN FARIDYAHYAEI

    Yüksek Lisans

    İngilizce

    İngilizce

    2017

    Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    Assist. Prof. Dr. MUSTAFA KEMAL TURAL

  2. Solution approaches for single source capacitated multi facility weber problem

    Tek kaynaklı kapasiteli sürekli düzlemde çoklu yer seçimi problemi için çözüm yaklaşımları

    HALUK DAMGACIOĞLU

    Yüksek Lisans

    İngilizce

    İngilizce

    2014

    Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. CEM İYİGÜN

  3. Lagrangean heuristics for the capacitated multi-facility location allocation problem

    Sığa kısıtlı yer seçimi-taşıma problemlerinin çözümü için lagrange gevşetmesi tabanlı sezgisel yöntemler

    BUKET AVCI

    Yüksek Lisans

    İngilizce

    İngilizce

    2007

    Endüstri ve Endüstri MühendisliğiBoğaziçi Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF.DR. KUBAN ALTINEL

  4. Location-allocation problems with multi-commodity flows: Exact and approximate solution methods

    Çok mallı yerleşim-dağıtım problemleri: Kesin ve yaklaşık çözüm yöntemleri

    MEHMET HAKAN AKYÜZ

    Doktora

    İngilizce

    İngilizce

    2011

    Endüstri ve Endüstri MühendisliğiBoğaziçi Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. TEMEL ÖNCAN

    PROF. İ. KUBAN ALTINEL

  5. Montaj hattı dengeleme

    Assembly line balancing

    MURAT UZMEN

    Yüksek Lisans

    Türkçe

    Türkçe

    1990

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    PROF. DR. GÖNÜL YENERSOY