T.C.
KARA HARP OKULU
SAVUNMA BİLİMLERİ ENSTİTÜSÜ
HAREKAT ARAŞTIRMASI ANA BİLİM DALI
ANA DAĞITIM ÜSSÜ YER SEÇİM PROBLEMLERİ VE BİR
KAMU KURUMU İÇİN GERÇEK BİR ANA DAĞITIM ÜSSÜ YER
SEÇİM PROBLEMİ
YÜKSEK LİSANS TEZİ
Hazırlayan
Sinan AYGÜN
Tez Danışmanı
Dr. Erkan KÖSE
Eş Danışman
Yrd. Doç. Dr. Hakan Soner APLAK
ANKARA - 2014
TEZ TANITIM FORMU
TEZİN TARİHİ : 12.06.2014
TEZİN TİPİ : Yüksek Lisans Tezi
TEZİN BAŞLIĞI : Ana dağıtım üssü yer seçim problemleri ve bir kamu kurumu
için gerçek bir ana dağıtım üssü yer seçim problemi.
TEZİN YAPILDIĞI BİRİM : Kara Harp Okulu Savunma Bilimleri Enstitüsü
Harekat Araştırması Ana Bilim Dalı
SPONSOR KURULUŞ : DAĞITIM LİSTESİ : Kara Harp Okulu Savunma Bilimleri Enstitüsü Tez
Hazırlama, Onay, Dağıtım ve Muhafaza Esasları Kılavuzunda Belirtilen
Yerlere
TEZİN ÖZETİ : Bu çalışmada, bir kamu kurumuna yönelik gerçek bir ana
dağıtım üssü yer seçim problemi ele alınmıştır. Literatürde yapılan inceleme
neticesinde, problemi tüm karakteristikleri ile çözebilecek bir matematiksel
modele rastlanmamıştır. Kurumun talepleri ve problemin gereksinimlerinden
yola çıkılarak, literatürde yer alan, kapasite kısıtlı ve çok atamalı yapıya sahip
Ana Dağıtım Üssü (ADÜ) yer seçim problemlerine yeni boyut kazandırılmıştır.
Bu çalışmada literatürde yer alan çalışmalardan farklı olarak, ADÜ olarak
seçilmeyen
kaynak-varış
çiftleri
arasındaki
akışlarda
ADÜ
kullanma
zorunluluğu gevşetilmiş ve ADÜ olarak seçilen düğümlerin kapasitelerinin hem
ADÜ, hem de ADÜ olarak seçilmeyen düğümlerden gelen akışlardan
etkilenmesi sağlanmıştır.
Çalışmada ele alınan problemin çözümü için, ADÜ olarak seçilmeyen
düğümler arasında direkt gidişe müsaade eden iki farklı matematiksel model
önerilmiş ve bu modeller GAMS IDE 2.0.34.19 yazılımı ile kodlanıp, CPLEX
10.1 çözücüsü ile çözdürülmüştür. Her iki model için, makul çözüm zamanları
ile en iyi çözümlere ulaşıldığı görülmüştür.
ANAHTAR KELİMELER : Tesis yer seçim problemi, Ana dağıtım üssü yer
seçim problemi, Matematiksel modelleme.
SAYFA SAYISI : 115
GİZLİLİK DERECESİ : Tasnif Dışı
T.C.
KARA HARP OKULU
SAVUNMA BİLİMLERİ ENSTİTÜSÜ
HAREKAT ARAŞTIRMASI ANA BİLİM DALI
ANA DAĞITIM ÜSSÜ YER SEÇİM PROBLEMLERİ VE BİR
KAMU KURUMU İÇİN GERÇEK BİR ANA DAĞITIM ÜSSÜ YER
SEÇİM PROBLEMİ
YÜKSEK LİSANS TEZİ
Hazırlayan
Sinan AYGÜN
Tez Danışmanı
Dr. Erkan KÖSE
Eş Danışman
Yrd. Doç. Dr. Hakan Soner APLAK
ANKARA - 2014
KARA HARP OKULU
SAVUNMA BİLİMLERİ ENSTİTÜSÜ MÜDÜRLÜĞÜNE
Sinan AYGÜN’ün, “Ana dağıtım üssü yer seçim problemleri ve bir
kamu kurumu için gerçek bir ana dağıtım üssü yer seçim problemi”
konulu tez çalışması, jürimiz tarafından HAREKAT ARAŞTIRMASI Ana
Bilim Dalında YÜKSEK LİSANS tezi olarak kabul edilmiştir.
Başkan --------------------------------Prof. Dr. Cevriye GENCER
Üye
---------------------------------Doç. Dr. H. Ediz ATMACA
Üye
-------------------------------Dr. Erkan KÖSE
(Danışman)
ONAY
Yukarıdaki imzaların, adı geçen öğretim üyelerine ait olduğunu onaylarım.
... / ... / 2014
Önder Haluk TEKBAŞ
Prof. Dr.
Enstitü Müdürü
TEŞEKKÜR
Başta Kara Harp Okulu Komutanı Tümgeneral Yılmaz UYAR olmak
üzere Kara Harp Okulu Komutanlığı’na, bu çalışmanın vücuda gelmesinde
engin tecrübeleri ile bana yol gösteren ve bir eğitmenden daha öte bir ilgi ile
destek olan tez danışmanım Dr. P. Alb. Erkan KÖSE’ ye ve çok kıymetli
yardım ve önerilerini esirgemeyen eş danışmanım Yrd. Doç. Dr. İs. Alb.
Hakan Soner APLAK’ a, tez çalışmam süresince bana destek olan Tnk. Kur.
Bnb. Nuri BÜYÜKYAZICI’ya, Enstitüye ilk adımımı bastığım andan itibaren
bana yol gösteren, hiçbir konuda desteğini esirgemeyen, çok saygıdeğer
Anabilim Dalı Başkanım Dr. Müh. Bnb. Özkan BALİ’ ye teşekkürlerimi
sunmayı bir borç bilirim.
Hayatım boyunca örnek aldığım ve varlığıyla gurur duyduğum sevgili
babam Süleyman AYGÜN’ e, beni cesaretlendiren ve eğitimim için hiç bir
fedakarlıktan kaçınmayan annem Emine AYGÜN’ e, başarılarımla sevinen,
üzüntülerimle üzülen, eğitimim süresince bana hep destek veren, anlayış
gösteren sevgili eşim Ezgi AYGÜN’e ve kızım Naz AYGÜN’e minnettarım.
Son olarak, gerek derslerde, gerek Kara Harp Okulu’na oryantasyon
sürecimde, gerekse tez çalışmamda desteklerini, ilgi ve alakalarını
esirgemeyen değerli sınıf arkadaşlarım Mustafa AĞDAŞ ve Haydar BALLI’ya
şükranlarımı sunarım.
i
T.C.
KARA HARP OKULU
SAVUNMA BİLİMLERİ ENSTİTÜSÜ
HAREKAT ARAŞTIRMASI ANA BİLİM DALI
ANKARA 2014
ANA DAĞITIM ÜSSÜ YER SEÇİM PROBLEMLERİ VE BİR
KAMU KURUMU İÇİN GERÇEK BİR ANA DAĞITIM ÜSSÜ
YER SEÇİM PROBLEMİ
YÜKSEK LİSANS TEZİ
Sinan AYGÜN
ÖZET
Ana Dağıtım Üssü (ADÜ) yer seçim problemleri, son 25 yıldır
yerleşim teorisinin önemli bir araştırma alanı haline gelmiştir. Bunda modern
taşımacılık ve telekomünikasyon sistemlerinde topla-dağıt ağ yapılarının
kullanımının büyük rolü vardır. Topla- dağıt ağ yapısında, merkezi konumda
olan bir tesis, toplama ve dağıtma noktası olarak hizmet verir. Toplama ve
dağıtma noktası olarak kullanılan bu merkez “ana dağıtım üssü” olarak
isimlendirilir. Topla-dağıt ağ sistemlerinde tüm başlangıç-varış noktası
arasındaki akışlar doğrudan bağlantı hatları ile değil, ölçek ekonomisinden
yararlanmak amacıyla ADÜ’lerde toplanır ve yine ADÜ’ler üzerinden varış
noktalarına gönderilir. Böylece, daha az sayıda bağlantı hattı ve daha düşük
maliyetlerle, daha çok noktaya erişim sağlamak mümkün olur.
Bu çalışmada, dönemsel olarak çalışanlarının bir bölümünü
hattının
Erzincan-Elazığ-Diyarbakır-Mardin
batısındaki
illerden
hattın
doğusundaki illere, hattın doğusundaki illerden hattın batısındaki illere ve
hattın doğusundaki iller arasında taşıtması gereken bir kamu kurumuna
yönelik gerçek bir ana dağıtım üssü yer seçim problemi ele alınmıştır.
ii
Literatürde yapılan inceleme neticesinde, problemi tüm karakteristikleri ile
çözebilecek bir matematiksel modele rastlanmamıştır. Kurumun talepleri ve
problemin gereksinimlerinden yola çıkılarak, literatürde yer alan, kapasite
kısıtlı ve çok atamalı yapıya sahip ADÜ yer seçim problemlerine yeni boyut
kazandırılmıştır. Bu çalışmada literatürde yer alan çalışmalardan farklı olarak
ADÜ olarak seçilmeyen kaynak-varış çiftleri arasındaki akışlarda ADÜ
kullanma zorunluluğu gevşetilmiş ve ADÜ olarak seçilen düğümlerin
kapasitelerinin hem ADÜ, hem de ADÜ olarak seçilmeyen düğümlerden
gelen akışlardan etkilenmesi sağlanmıştır.
Çalışmada ele alınan problemin çözümü için, ADÜ olarak seçilmeyen
düğümler arasında direkt gidişe müsaade eden iki farklı matematiksel model
önerilmiştir. Birinci matematiksel model: çok atamalı, kapasite kısıtlı, ADÜ
olarak seçilmeyen düğümler arasında direkt gidişe müsaade eden, ADÜ
sayısının model tarafından belirlendiği, düğümler arasındaki mesafelerde
üçgensel eşitsizliğin bulunmadığı ADÜ yer seçim problemi şeklindedir. İkinci
matematiksel model ise: birinci matematiksel modelden farklı olarak, ADÜ
sayısının kullanıcı tarafından belirlendiği p-ADÜ medyan problemi şekildedir.
Geliştirilen matematiksel modeller, GAMS IDE 2.0.34.19 yazılımı ile
kodlanmış ve CPLEX 10.1 çözücüsü kullanılarak makul çözüm zamanlarıyla
en iyi çözümlere ulaşılmıştır.
Anahtar Kelimeler : Tesis yer seçim problemi, Ana dağıtım üssü yer seçim
problemi, Matematiksel modelleme.
Tez Yöneticisi
: Dr. Erkan KÖSE
Sayfa Sayısı
: 115
iii
T.C.
TURKISH MILITARY ACADEMY
DEFENSE SCIENCE INSTITUTE
DEPARTMENT OF OPERATION RESEARCH
ANKARA 2014
HUB LOCATION PROBLEMS AND A REAL HUB LOCATION
PROBLEM FOR A PUBLIC INSTITUTION
MASTER THESIS
Sinan AYGÜN
ABSRACT
For the last twenty five years, hub location problems have become
an important research area in the Settlement Theory. In this theory, the use
of hub and spoke network structure has a major role in modern transportation
and telecommunication systems. In the hub and spoke network structure, a
facility that is located centrally serves as a collection and distribution point.
This center used as a collection and distribution point is called “hub”. In hub
and spoke systems, flows among all origin-destination pairs are not
conducted by direct connection lines, but instead by means of collecting hubs
and are sent to the destinations again via hubs for the purpose of taking
advantages of the economies of scale. Thus, it becomes possible to provide
connections to more points with less lines and costs.
In this study, a real hub location problem is studied for a public
institution that has to dispatch a part of their employees from the geographical
line located on the west side of the cities of Erzincan, Elazığ, Diyarbakır and
Mardin to the east side of the cities of the same line, from the east side of the
cities of the line to the west side of the cities of the same line and among the
cities to located on the east of the same geographical line.
iv
As a result of the survey in the literature, a mathematical model that
can solve the problem with all its characteristics is not found. On the basis of
the institutions’ demands and the problems’ requirements, a new dimension
has been provided to the capacitated multiple allocation hub location
problems which have significance in the literature. In this study, unlike the
studies conducted in the literature, obligation to use hubs among the origindestination pairs that are unselected hub is relaxed and the capacities of
nodes that are selected as hubs are provided to be affected by the flows both
from the hubs and the spokes.
For the solution of the problem addressed in this study, two different
mathematical models have been proposed which allow direct flows among
the spokes. The first mathematical model is in the form of hub location
problem with multiple allocations, capacity limited, allowing direct flows
among the spokes, determining the number of hubs selected by the model,
not having triangular inequalities in the distances among the nodes. The
second mathematical model, unlike the first one, is in the form of p-hub
median problem in which the selected number of hubs is determined by the
user. Developed mathematical models are encoded with the GAMS IDE
2.0.34.19 software and best solutions have been reached by using CPLEX
10.1 solver with optimum solution times.
Keywords
: Facility Location Problems, Hub Location Problems,
Mathematical Modelling.
Advisor
: Dr. Erkan KÖSE
Number of Pages : 115
v
İÇİNDEKİLER
TEŞEKKÜR..................................................................................................i
İÇİNDEKİLER ............................................................................................ vi
TABLOLAR LİSTESİ ................................................................................ viii
ŞEKİLLER LİSTESİ ...................................................................................x
KISALTMALAR LİSTESİ ........................................................................... xi
GİRİŞ ......................................................................................................... 1
BİRİNCİ BÖLÜM
LİTERATÜR ARAŞTIRMASI
1. TESİS YERİ SEÇİMİ PROBLEMLERİ ................................................. 5
2. ANA DAĞITIM ÜSSÜ YER SEÇİM PROBLEMLERİ ........................... 8
a. İlk Çalışmalar................................................................................... 9
b. Tanımı ve Sınıflandırılması............................................................ 10
c. p-ADÜ Medyan Problemi Konusunda Literatür Araştırması .......... 13
d. Sabit Maliyetli ADÜ Yer Seçim Problemi Konusunda Literatür
Araştırması ........................................................................................ 23
e. P-ADÜ Merkez Problemi Konusunda Literatür Araştırması ........... 31
f. ADÜ Kapsama Problemi Konusunda Literatür Araştırması ........... 34
İKİNCİ BÖLÜM
ADÜ YER SEÇİM PROBLEMLERİNİN TEMEL MATEMATİKSEL
MODELLERİ
1. TEK ADÜ YER SEÇİM PROBLEMİ ................................................... 37
2. P-ADÜ MEDYAN PROBLEMİ ............................................................ 38
a. Tek Atamalı p-ADÜ Medyan Problemi ........................................... 38
vi
b. Çok Atamalı p-ADÜ Medyan Problemi .......................................... 42
3. SABİT MALİYETLİ ADÜ YER SEÇİM PROBLEMİ ............................ 45
a. Kapasite Sınırı Olmayan ADÜ Yer Seçim Problemi ...................... 45
b. Kapasite Sınırı Olan ADÜ Yer Seçim Problemi ............................. 47
4. P-ADÜ MERKEZ PROBLEMİ ............................................................ 53
5. ADÜ KAPSAMA PROBLEMİ ............................................................. 55
ÜÇÜNCÜ BÖLÜM
UYGULAMA
1. PROBLEMİN TANIMI ........................................................................ 58
2. MATEMATİKSEL MODEL ................................................................. 64
a. Kümeler ......................................................................................... 65
b. Girdi Değerleri ve Sabitler.............................................................. 67
b. Karar Değişkenleri ......................................................................... 69
ç. Matematiksel Model ....................................................................... 72
c. Birinci Modelin Sonuçları ............................................................... 76
d. İkinci Modelin Sonuçları................................................................. 84
DÖRDÜNCÜ BÖLÜM
SONUÇ VE ÖNERİLER
1. SONUÇ.............................................................................................. 98
2. ÖNERİLER ...................................................................................... 101
KAYNAKÇA ........................................................................................... 103
EKLER ................................................................................................... 115
vii
TABLOLAR LİSTESİ
Sayfa
Tablo-1: ADÜ Yer Seçim Problemleri Sınıflandırma Kriterleri .................. 12
Tablo-2: Tek Atamalı p-ADÜ Medyan Problemi İçin Yapılan Çalışmalar . 19
Tablo-3: Çok Atamalı p-ADÜ Medyan Problemi İçin Yapılan Çalışmalar . 22
Tablo-4: Kapasite Sınırı Olmayan Sabit Maliyetli Tek ve Çok Atamalı ADÜ
Yer Seçim Problemi İçin Yapılan Çalışmalar............................................ 27
Tablo-5: Kapasite Sınırı Olan Tek ve Çok Atamalı ADÜ Yer Seçim Problemi
İçin Yapılan Çalışmalar ............................................................................ 31
Tablo-6: p-ADÜ Merkez Problemi İçin Yapılan Çalışmalar ...................... 34
Tablo-7: ADÜ Kapsama Problemi İçin Yapılan Çalışmalar ...................... 36
Tablo-8: Hattın Batısında Kullanılan Havaalanları ve Hangi İllerden Sevk
Edilen Personelin Bu Havaalanlarını Kullanacağını Gösteren Çizelge .... 59
Tablo-9 : Hattın Doğusunda Kullanılan Havaalanları ve Hangi İllerden Sevk
Edilen Personelin Bu Havaalanlarını Kullanacağını Gösteren Çizelge .... 61
Tablo-10 : Aday ADÜ Konumundaki Havaalanları ................................... 66
Tablo-11: Birinci Matematiksel Modelin Çözümü Sonucunda Seçilen
ADÜ’ler ve ADÜ’lerin Hangi İller Tarafından Kullanılacağını Gösteren
Çizelge ..................................................................................................... 77
Tablo-12 : Örnek Güzergahlar ................................................................. 81
Tablo-13
:
ADÜ
Kullanmadan
Direkt
Gidişe
Müsaade
Edilen
Güzergahlar ............................................................................................. 83
Tablo-14: Her Bir p Değeri İçin Seçilen ADÜ’ler, Amaç Fonksiyon Değerleri
ve Çözüm Süreleri ................................................................................... 85
Tablo-15: p=21 İçin ADÜ Olarak Seçilen İller ve Diğer İllerin Hangi ADÜ’leri
Kullanacağını Gösteren Çizelge.............................................................. 88
Tablo 16 : p=21 İçin Örnek Güzergahlar .................................................. 93
viii
Tablo-17: p=21 İçin ADÜ Kullanmadan Direkt Gidişe Müsaade Edilen
Güzergahlar ............................................................................................. 95
ix
ŞEKİLLER LİSTESİ
Sayfa
Şekil-1: ADÜ Yer Seçim Problemleri Genel Şebeke Gösterimi .................. 2
Şekil-2: Alfred Weber’in Yerleşim Teorisi Problemi .................................... 5
Şekil-3: ADÜ Yer Seçim Probleminde Toplama-Dağıtım Süreci .............. 11
Şekil-4: Tek (a) ve Çok (b) Atamalı ADÜ Yer Seçim Problemi Örnek Ağ
Yapıları .................................................................................................... 13
Şekil-5: Problemde Yer Alan Muhtemel Yollar ve Karar Değişkenlerinin
Görevleri .................................................................................................. 70
x
KISALTMALAR LİSTESİ
ADÜ
: Ana Dağıtım Üssü
CHLP
: Capacitated Hub Location Problem
CMAHLP
: Capacitated Multiple Allocation Hub Location Problem
CMApHLP
: Capacitated Multiple Allocation p Hub Location Problem
UHLP
: Uncapacitated Hub Location Problem
UMAHLP
: Uncapacitated Multiple Allocation Hub Location Problem
xi
GİRİŞ
Tesis yeri seçim problemi gerçek hayatta oldukça fazla karşılaşılan
optimizasyon problemlerinden birisidir. İster kamu kurumu isterse özel sektör
kuruluşu olsun neredeyse tüm organizasyonlar bu problem ile karşı karşıya
kalmaktadır. Kamu kurumları hizmet kalitesini artırmak maksadıyla hizmet
noktalarını (okullar, hastaneler, acil servis binaları vb.) en iyi konumlara
yerleştirmeye çalışırken, özel sektör kuruluşları, rakiplerine oranla avantaj elde
etmek için, üretim merkezleri, satış noktaları ve depoların yerleri ile ilgili kritik
kararlar vermek durumunda kalmaktadır (Bastı, 2012). Kamu kurumlarının yer
seçim kararlarında esas motivasyon hizmet iken, özel sektörde esas amaç
kardır.
Genel olarak tesis yer seçim problemleri n adet tesisin m adet konuma
(n<m) taşıma maliyetlerinin minimize edilecek şekilde yerleştirilmesi konusu ile
ilgilenmektedir (Tavakkoli ve Shayan, 1998). Tanımı biraz daha açacak
olursak; tesis yer seçim problemleri; bir grup hizmet veren tesisin bazı kısıtlar
göz
önünde
bulundurularak,
müşterilerin
(talep
noktası)
taleplerinin
karşılanması maliyetlerini minimum düzeye indirecek şekilde uygun konumlara
yerleştirilmesini ve her bir müşterinin hizmet veren tesislere atanmasını
kapsayan problemlerdir (Bastı, 2012).
Tesis yer seçim problemlerinin, literatürde farklı açılardan birçok
sınıflandırmaya tabi tutulduğu görülmektedir. Bu sınıflandırmalardan bir tanesi
Current ve arkadaşları tarafından yapılan ve tesis yer seçim problemlerini 8
ana başlık halinde inceleyen sınıflandırmadır. Bu sekiz ana başlık, küme
kapsama, maksimum kapsama, p-merkez, p-dağılım, p-medyan, sabit
maliyetli tesis yeri seçim, maksimum toplam ve ana dağıtım üssü yer seçim
problemleri olarak ifade edilebilir (Current vd. , 2001).
Bu çalışmada yukarıda yer alan sekiz ana başlıktan biri olan ana
dağıtım üssü (ADÜ) yer seçim problemleri ele alınmaktadır. Ana dağıtım üssü
yer seçim problemi, yerleşim teorisinin göreceli yeni ve gelişen araştırma
1
alanlarından birisidir. Ana dağıtım üssü yer seçim problemi, insanların,
eşyaların veya bilginin gerekli kaynak ve varış çiftleri arasındaki hareketlerini
içerir (Farahani vd. ,2013).
ADÜ’ler çoktan-çoğa dağıtım sistemlerinde toplama, sınıflandırma ve
aktarma noktası olarak hizmet veren özel tesislerdir. Tüm kaynak-varış noktası
arasındaki akışlar doğrudan birbirleri arasında değil, bunun yerine, ölçek
ekonomisinden faydalanmak amacıyla ADÜ’lerde toplanır ve yine ADÜ’ler
üzerinden varış noktalarına gönderilir. Bu sayede daha az bağlantı hattı ve
daha düşük maliyetlerle daha çok noktaya erişim sağlanmış olur.
Aynı kaynak noktasından çıkarak farklı noktalara dağıtımı yapılacak
akışlar ile farklı kaynak noktalarından çıkarak aynı noktaya dağıtımı yapılacak
akışlar ADÜ’lerde yük birleştirmesine tabi tutulur. Bu yük birleştirmeleri
doğrudan ADÜ-ADÜ arası olabileceği gibi, kaynak noktasından ADÜ’ye,
ADÜ’den de varış noktasına şeklinde de olabilir (Alumur ve Kara, 2008). Şekil
1’de, 15 düğüme sahip ve bu 15 düğümden 3 tanesi ADÜ olarak seçilmiş örnek
bir şebeke gösterilmiştir (Daskin, 1995). Şebekedeki bağlantılar ADÜ şebeke
yapısını açıklamaktadır.
Şekil-1: ADÜ Yer Seçim Problemleri Genel Şebeke Gösterimi
ADÜ yer seçim problemi, kaynak ve varış noktaları arasında ADÜ’lerin
yerleştirilmesi ve talep noktalarının ADÜ’lere atanmasıyla ilgilenir. Bu problem
2
iki alt problemi kapsar. Bunlar, ADÜ yer seçimi ve düğüm noktalarının
belirlenen ADÜ’lere atanmasıdır (Bryan ve O’Kelly, 1999).
Bu çalışmada, dönemsel olarak çalışanlarının bir bölümünü ErzincanElazığ-Diyarbakır-Mardin hattının batısındaki illerden hattın doğusundaki
illere, hattın doğusundaki illerden hattın batısındaki illere ve hattın
doğusundaki iller arasında taşıtması gereken bir kamu kurumuna yönelik
gerçek bir ana dağıtım üssü yer seçim problemi ele alınmıştır. Problemde,
çalışanlar, hem kara hem de havayolu ile taşınabilmektedir. Güvenlik nedeni
ile bazı yollar arasında kara yolu taşımacılığının maliyeti çok yüksektir. Bu
problem, temel olarak yürürlükte olan sistemin ihtayaçlara tam ve ekonomik
olarak cevap verememesinden kaynaklanmaktadır.
ADÜ yer seçim problemlerinin çözümü için geliştirilen matematiksel
modellerin, ele alınan problemin temel karakteristiklerini karşılamada yetersiz
kaldığı görülmüştür. Bu çalışmada, ele alınan problemin yapısına uygun
olarak, literatürde yer alan ADÜ yer seçim problemlerine yeni bir boyut
kazandırılmıştır.
Problem, şebekedeki düğümler arasındaki mesafelerde üçgensel
eşitsizliğin olmadığı, kesikli uzayda yer alan, çok atamalı, ADÜ olarak
seçilmeyen kaynak-varış çiftleri arasındaki akışlarda ADÜ kullanmadan direkt
gidişe müsaade eden, ADÜ olarak seçilen düğümlerin kapasitelerini, hem
ADÜ, hemde ADÜ olarak seçilmeyen düğümlerden gelen akışıların etkilediği
ADÜ yer seçim problemi olarak tasarlanmıştır. Çalışmada, literatürde yer alan
sabit maliyetli, çok atamalı, kapasite kısıtlı yapıya sahip bir matematiksel
modelden (Marin, 2005a) hareketle, problemin gereksinimlerine özgü iki yeni
matematiksel model geliştirilmiştir.
Problemin
çözümü
için
iki farklı
matematiksel model geliştirilmesi ile, yönetime farklı seçenekler için karar
verme imkanı sunulmuştur.
Birinci matematiksel model yardımıyla şu sorulara cevaplar aranmıştır:
3
 Sistemde kaç adet ADÜ açılmalıdır?
 ADÜ’ler nerelere açılmalıdır?
 Mevcut sistemde kullanılan hangi ADÜ’ler kapatılmalıdır?
 ADÜ olarak seçilmeyen düğümler hangi ADÜ’lere atanmalıdır?
 Hangi düğümler arasında ADÜ kullanmadan direkt gidişe müsaade
edilmelidir?
İkinci matematiksel model yardımıyla, kullanıcı tarafından belirlenen
değişik ADÜ sayıları için (p=2,3,..,42), sistemde kaç adet ADÜ açılması hariç,
yukarıda yer alan sorulara cevaplar aranmıştır.
Literatürde, ADÜ yer seçim problemleri ile ilgili pek çok çalışmaya
rastlamak mümkündür. Bu çalışmayı diğerlerinden ayıran yönleri:
 Eğer daha ekonomik ise, ADÜ olarak seçilmeyen kaynak-varış
çiftleri arasındaki akışlarda, ADÜ kullanmadan direkt gidişe müsaade edilmesi,
 ADÜ olarak seçilen düğümlerin kapasitesini hem ADÜ’ lerden
gelen, hem de ADÜ olarak seçilmeyen düğümlerden gelen akışların
etkilemesi,
 ADÜ olarak seçilen düğümlerin sabit kuruluş maliyetine sahip
olmaması,
 Tasarlanan şebekedeki düğümler arasındaki mesafelerde üçgensel
eşitsizliğin bulunmamasıdır.
Çalışmanın bundan sonraki bölümünde, Tesis yeri seçimi problemleri
ve ADÜ yer seçim problemleri ile ilgili literatür araştırması yer almaktadır. İkinci
bölümde, ADÜ yer seçim problemleri ile ilgili temel matematiksel modeller
incelenmiştir. Üçüncü bölümde, çalışmaya konu olan problem detaylı olarak
açıklanmış ve problemin çözümü için geliştirilen matematiksel modeller detaylı
olarak tanıtılmıştır. Bu bölümde ayrıca, geliştirilen matematiksel modellerin,
GAMS IDE 2.0.34.19 yazılımı ve CPLEX 10.1 çözücüsü vasıtasıyla elde edilen
çözümlerine yer verilmiştir. Çalışmanın son bölümünde elde edilen sonuçlar
değerlendirilmiş ve müteakip çalışmalar için teklifler sunulmuştur.
4
BİRİNCİ BÖLÜM
LİTERATÜR ARAŞTIRMASI
1. TESİS YERİ SEÇİMİ PROBLEMLERİ
Tesis yerleşim teorisi geniş bir literatüre sahiptir. Bu teori resmi olarak
ilk defa 1909 yılında Alfred Weber tarafından tek bir deponun birkaç müşteri
ile
arasındaki
toplam
mesafeyi
minimize
etmek
amacıyla,
nasıl
yerleştirileceğine dair Şekil 2’de şematik olarak gösterilen problemin çözümü
ile başlamıştır (Owen ve Daskin, 1998). Ancak, bazı bilim adamları, tesis
yerleşim teorisi ile ilgili ilk çalışmaların 17’nci yüzyılın başlarında Pierre de
Fermat, Evagelistica Torricelli ve Battista Cavallieri tarafından ortaya konulan
temel öklit uzayı ortanca problemi ile başladığını söylemektedir (Farahani vd.
,2009).
Şekil-2: Alfred Weber’in Yerleşim Teorisi Problemi
Tesis yeri seçimi problemleri, taşıma maliyetlerinin en aza indirilmesi
maksadıyla n adet tesisin m adet konuma yerleştirilmesi problemi olarak
tanımlanmaktadır
(Tavakkoli
ve
Shayan,
1998).
Yapılan
başka
bir
tanımlamaya göre tesis yeri seçimi problemleri, uzay içerisinde yer alan
dağıtılmış müşteriler kümesini ve bu müşterilerin taleplerini karşılayacak olan
tesisler kümesini içerir. Dahası, müşteriler ve tesisler arasındaki uzaklıklar,
zaman veya maliyetler, belirlenen bir ölçüm sistemiyle ölçülür. Problemin
5
sonucunda cevaplanması gereken sorular ise; toplam maliyeti minimize etmek
maksadıyla hangi tesislerin açılacağı ve hangi müşterilerin hangi tesis veya
tesislerden hizmet alacağıdır (M. T. Melo vd. , 2009).
Tesis yeri seçim problemlerini karakterize eden 4 adet bileşen vardır
(C. S. ReVelle, H. A. Eiselt, 2005). Bu bileşenler;
- Noktalara veya rotalara yerleştirildiği farz edilen müşteriler,
- Yerleştirilecek olan tesisler,
- Müşteri ve tesislerin yerleştirildiği uzay,
- Müşteriler ve tesisler arasındaki uzaklıkları gösteren ölçüm birimidir.
Tesis yeri seçimi problemleri için, amaç fonksiyonları, kısıtlar, müşteri
sayıları ve tipleri, tesis sayıları ve tipleri, çözüm metotları ve problemin sahip
olduğu diğer niteliklere göre çok çeşitli sınıflandırmalar yapılabilir. Literatürde
farklı sınıflandırmalarla karşılaşmak mümkündür. Bunların en kapsamlıları
Owen ve Daskin (1998), Current vd. (2001), Klose ve Drexl (2004) ve Arabani
ve Farahani (2012)’nin yapmış oldukları sınıflandırmalardır.
Aşağıda, Current vd. (2001) tarafından mesafeler göz önüne alınarak
yapılan ve 8 başlıkta incelenen sınıflandırmaya ve bunlardan ilk yedisi için kısa
tanımlarına yer verilmiştir. Çalışmaya konu teşkil eden ADÜ yer seçim
problemleri ise, ayrı bir başlık altında detaylı olarak ele alınmıştır. Bu
sınıflandırmada Current vd. , sıralamadaki ilk 4 başlığı maksimum mesafeye,
son 4 başlığı ise toplam mesafeye göre incelemiştir. Bunlar;
a. Küme kapsama,
b. Maksimum kapsama,
c. P-Merkez,
d. P-Dağılım,
e. P-Medyan,
f. Sabit maliyetli tesis yeri seçimi,
g. Maksimum toplam,
h. Ana dağıtım üssü yer seçimi problemidir.
6
a. Küme Kapsama Problemleri:
Küme kapsama probleminde amaç, belli bir kapsama seviyesini
sağlayan yer seçimi kararı maliyetini minimize etmektir (Owen ve Daskin,
1998).
b. Maksimum Kapsama Problemleri:
Maksimum kapsama problemleri, önceden belirlenmiş sayıda
hizmet veren tesis sayısı kısıtı ile maksimum sayıda talep noktasını kapsamayı
amaçlayan problem olarak tanımlanmaktadır (Current vd. ,2001).
c. P-Merkez Problemleri:
P merkez problemleri, maksimumun minimumu problemleri olarak
bilinmektedir. Amaç, herhangi bir talep noktası ile o talep noktasına en yakın
tesis arasındaki maksimum mesafeyi minimize etmektir (Owen ve Daskin,
1998).
d. P-Dağılım Problemleri:
Yukarıda yapılan tanımlamalarda talep noktaları ve yeni tesisler
arasındaki mesafelerden bahsedilmiştir. Ayrıca tesise yakın olmak, istenilen
bir durumdur. P-Dağılım problemleri, yukarıdaki problemlerden iki şekilde
ayrılır. Birincisi, problemin sadece yeni tesisler arasındaki mesafelerle
ilgilenmesi, ikincisi ise, amacın, herhangi iki tesis arasındaki minimum
mesafenin maksimize edilmeye çalışılmasıdır (Current vd. , 2001).
e. P-Medyan Problemleri:
P medyan problemi, n adet düğümden meydana gelen bir şebeke
üzerinde p adet tesisin en az maliyet oluşturacak şekilde yerleştirilmesi ve
7
yerleştirilecek olan bu tesislerden hangi talep noktalarının hizmet alacağının
belirlenmesidir (Sule, 2001).
f. Sabit Maliyetli Tesis Yeri Seçim Problemleri:
Bu problem tipinde amaç, tesis kurulum ve ulaşım masraflarını
minimize etmektir. Model, bu amacı gerçekleştirirken tesislerin optimal
yerlerine ve açılacak olan tesis sayısına karar verir. Aynı zamanda talep
noktalarının hangi tesislerden hizmet alacağını da belirler. Problemde, tesisler
kapasite kısıtlıdır ve talep noktaları kendisine en yakın tesislere atanmazlar
(Current vd. , 2001).
g. Maksimum Toplam Problemi:
Maksimum toplam problemleri, p adet tesisin yerini belirlemeye
çalışırken, talep noktaları ile tesisler arasındaki toplam talep ağırlıklı mesafeyi
maksimize etmeyi amaçlayan problemlerdir (Current vd. , 2001).
2. ANA DAĞITIM ÜSSÜ YER SEÇİM PROBLEMLERİ
Ana dağıtım üsleri, çoktan-çoğa dağıtım sistemlerinde toplama,
sınıflandırma ve aktarma noktası olarak hizmet veren özel tesislerdir. Tüm
kaynak-varış noktası arasındaki akışlar doğrudan birbirleri arasında değil,
bunun yerine, ölçek ekonomisinden faydalanmak amacıyla ana dağıtım
üslerinde toplanır ve yine ana dağıtım üsleri üzerinden varış noktalarına
gönderilir. Bu sayede daha az bağlantı hattı ile daha düşük maliyetlerle daha
çok noktaya erişim sağlanmış olur. Aynı kaynak noktasından çıkarak farklı
noktalara dağıtımı yapılacak akışlar ile farklı kaynak noktalarından çıkarak
aynı noktaya dağıtımı yapılacak akışlar ana dağıtım üslerinde yük
birleştirmesine tabi tutulurlar. Bu yük birleştirmeleri doğrudan ADÜ-ADÜ arası
olabileceği gibi kaynak noktasından ADÜ’ ye, ADÜ’ den de varış noktasına
şeklinde de olabilir (Alumur ve Kara, 2008).
8
“ADÜ yer seçim problemleri” son 25 yıldır yerleşim teorisinin önemli bir
araştırma
alanı
haline
gelmiştir.
Bunda
modern
taşımacılık
ve
telekomünikasyon sistemlerinde topla-dağıt ağ yapılarının kullanımının büyük
rolü vardır. ADÜ yer seçim problemlerinin pek çok sektörde uygulaması
görülmektedir. Özellikle havayolu taşımacılığı, posta ve kargo dağıtım
hizmetleri,
acil
hizmetler
sektörü
ve
telekomünikasyon
alanlarında
kullanılmaktadır (Özger, 2008).
a. İlk Çalışmalar
Ağ ana dağıtım üssü yer seçim problemini işaret eden ilk çalışmayı
yapan her ne kadar Goldman (1969) olarak bilinse de, ADÜ yer seçim problemi
ilk olarak O’Kelly (1986) tarafından ortaya konulmuştur (O’Kelly, 1986). O’Kelly
(1986) bu çalışma da düzlemsel yerleşim problemlerine yönelik model
geliştirmiştir. Yazar bu çalışmada, bir ve iki ADÜ bulunan temel modelleri
ortaya koymuştur. O’Kelly (1986) her başlangıç-varış çifti için doğrudan
atamalarla oluşacak bağlantı sayısının, akışların ADÜ’ ler üzerinden
gönderilmesi durumunda azalacağına dikkat çekmiş ve ADÜ oluşturmada
maliyet parametrelerini incelemiştir (O’Kelly, 1986).
ADÜ yer seçim problemi ile ilgili ilk matematiksel model, hava yolu
taşımacılığı ağıyla ilgili çalışmasıyla O’Kelly (1987) tarafından sunulmuştur
(Alumur ve Kara, 2008). O’Kelly (1987) bu problemi, minimum toplam problemi
olarak ifade etmiştir.
O’Kelly, Sivil Havacılık Kurulu (Civil Aeronautics Board (CAB))
tarafından 1970 yılına ait tutulan 25 ABD şehri arasındaki havayolu yolcu
taşımacılığı ile ilgili bir veri seti oluşturmuştur. Daha sonra bu veri seti hemen
hemen her ADÜ yer seçim problemi çalışan araştırmacı tarafından
kullanılmıştır ve CAB veri seti olarak referans gösterilmiştir. Bir başka çok
kullanılan veri seti ise Avustralya posta servisi veri setidir (AP) ve ilk olarak
Ernst ve Krishnamoorthy (1996) tarafından kullanılmıştır. AP veri seti
Avustralya, Sidney’e ait posta bölgelerini tanımlayan ve 200 düğümden oluşan
9
bir veri setidir. AP veri setinin, CAB veri setinden düğüm sayısının fazla olması
dışındaki en önemli farkı, AP veri setinde düğümler arasındaki akışların
simetrik olmamasıdır (Mayer ve Wagner, 2002).
ADÜ yer seçim problemleriyle ilgili ilk çalışmalar düşünüldüğünde,
O’Kelly’nin geliştirdiği karesel amaç fonksiyonuna sahip matematiksel model
kritik bir role sahiptir (O’Kelly, 1987, 1992). Daha sonra Campbell ADÜ yer
seçim problemleriyle ilgili benzer amaç fonksiyonlarına sahip birçok
matematiksel model önermiştir (Campbell, 1994b, 1996). Ayrıca, Aykin (1990)
akışa dayalı atama yaklaşımı ile ve Klincewicz (1991) hem akışa hem
mesafeye bağlı atama prosüdürü ile alanın genişlemesinde kritik rol
oynamışlardır (Aykin, 1990, 1994, 1995a, 1995b; Klincewicz, 1991, 1992).
b. Tanımı ve Sınıflandırılması
“Ana dağıtım üssü yer seçim problemi” genel anlamıyla ana
dağıtım üslerinin seçilmesi ve ana dağıtım üssü olmayan noktaların ana
dağıtım üslerine atanmasını içeren yerleştirme atama problemidir (Mayer ve
Wagner, 2002).
Ana dağıtım üssü yer seçim problemi, yerleşim teorisinin yeni çıkan ve
gelişen araştırma alanlarından birisidir. Bu problem, insanların, eşyaların veya
bilginin gerekli kaynak ve varış noktası çiftleri arasındaki hareketlerini içerir.
Ana dağıtım üsleri kaynak ve varış düğümleri arasındaki bağlantı hatlarının
sayısının azaltılması amacıyla kullanılır. Örneğin, k adet düğüme sahip ve
ADÜ içermeyen bir şebeke, kaynak ve varış düğümleri arasında k (k-1) adet
bağlantıya sahiptir, oysaki bu şebekede kaynak ve varış noktaları dışında
kalan 1 düğüm, kaynak ve varış noktalarını bağlamak için seçilirse, kaynak ve
varış noktalarını bağlamak için kullanılacak olan bağlantı sayısı 2 (k-1) olur
(Farahani vd. , 2013).
Ana dağıtım üssü yerleşim problemi iki alt problemi kapsar (Bryan ve
O’Kelly, 1999). Bunlar;
10
(1) ADÜ yer seçimi,
(2) Düğüm noktalarının belirlenen ADÜ’lere atanmasıdır.
Bazı çalışmalar ADÜ yerleştirme-atama probleminin sadece atama
kısmıyla ilgilenmiştir. Optimal atamalar ADÜ yer seçimlerinden, optimal ADÜ
yer seçimleri de atama kararlarından etkileneceğinden, ADÜ ağ yapısı
tasarımında yer seçimi ve atama problemleri birlikte ele alınmalıdır (Daskin,
1995).
Genel bir problem, birbirleri arasındaki akışların değiştiği n şehri içerir.
İlgili n şehirden p tanesi ADÜ olarak atanır ve kabul, elleçleme, yeniden
dağıtım için birleştirme ve dağıtım merkezi olarak kullanılır. İkinci adımda ise,
düğümler, ilgili ADÜ’lere atanır. i. kaynak noktasından j. varış noktasına olan
akış, atanan ADÜ’ler aracılığıyla i’den j’ye rotalanır (Kara ve Tansel, 2003).
Şekil-3’te ADÜ yer seçim probleminde toplama-dağıtım süreci gösterilmiştir
(Ermiş ve Ülengin, 2006).
Şekil-3: ADÜ Yer Seçim Probleminde Toplama-Dağıtım Süreci
ADÜ yer seçim problemi konusunda yapılan çalışmalar genellikle şu
üç kabul üzerine inşa edilmiştir (Alumur ve Kara, 2008):
 ADÜ ağ yapısı, her ADÜ çifti arasında bağlantı olacak şekilde tam
serimlidir,
 ADÜ’ler arası bağlantıda maliyet azaltma faktörü (∝) kullanılarak
ölçek ekonomisinden faydalanılır,
 ADÜ olmayan düğümler arasında direkt bağlantıya izin verilmez.
11
Bazı çalışmalarda bu kabuller gevşetilmiş olmakla birlikte, aksi
belirtilmedikçe bu kabuller geçerlidir.
ADÜ yer seçim probleminin özünde kaynak, varış ve potansiyel ADÜ
noktalarının tanımlandığı n adet düğüm noktasından oluşan bir ağ yapısı söz
konusudur. Problemin temel parametreleri; her kaynak-varış çifti arasındaki
akış, birim taşıma maliyeti (maliyet, zaman, mesafe vb.) ve ADÜ’ler arasındaki
taşımalarda ölçek ekonomisinden faydalanmak amacıyla kullanılan maliyet
azaltma faktörü (∝)’dür (O’Kelly ve Miller, 1994).
Ana dağıtım üssü yer seçim problemleri aşağıdaki kriterlere göre
sınıflandırılabilir (Farahani ve Hekmatfar, 2009: 246-247).
Tablo-1: ADÜ Yer Seçim Problemleri Sınıflandırma Kriterleri
Kesikli(Aday ana dağıtım üssü noktaları belirli
düğümler üzerinde olabilir)
Sürekli(Aday ana dağıtım üssü noktaları
düzlemde veya uzayda olabilir).
Mini-Max (Kaynak ve varış noktaları arasındaki
maksimum taşıma maliyeti minimize edilmeye
çalışılır)
Min-Toplam (Ana dağıtım üslerinin kurulma
maliyeti ve ana dağıtım üssü olmayan noktaların
ana dağıtım üslerine atanma maliyeti toplamı
minimize edilmeye çalışılır)
Eksojen (Kaç adet ana dağıtım üssü seçileceği
önceden bellidir)
Endojen (Kaç adet ana dağıtım üssü seçileceği
önceden belli değildir ve çözüm sonucunda
ortaya çıkar)
Tek ana dağıtım üssü
Birden fazla ana dağıtım üssü
Kapasiteli
Kapasitesiz
Maliyetsiz
Sabit maliyetli
Değişken maliyetli
Tek ana dağıtım üssüne(Tek atamalı)
Birden fazla ana dağıtım üssüne(Çok atamalı)
Maliyetsiz
Sabit Maliyetli
Değişken Maliyetli
Çözüm Alanı
Amaç Fonksiyon Tipi
Kaç Adet ADÜ Kurulacağına Karar Verme
ADÜ Sayısı
ADÜ Kapasitesi
ADÜ Kurma Maliyeti
ADÜ Olmayan Düğümlerin ADÜ’lere
Atanması
ADÜ Olmayan Düğümlerden ADÜ’lere
Bağlantı Maliyeti
Tablo-1’de açıklanan kriterler ışığında literatür incelendiğinde ADÜ yer
seçim problemleri ile ilgili en temel sınıflandırmanın Campbell (1994b)
tarafından yapıldığı görülmektedir. Campbell ADÜ yer seçim problemlerini 4’e
ayırmıştır (Campbell, 1994b). Bunlar;
12
-
P-ADÜ Medyan Problemi,
-
Sabit Maliyetli ADÜ Yer Seçim Problemi,
-
P-ADÜ Merkez Problemi,
-
ADÜ Kapsama Problemidir.
Çalışmanın bundan sonraki kısmında, yukarıda yer alan ADÜ yer
seçim problemleri ayrıntılı olarak tanıtılmış ve literatürde bu problemlerle ilgili
günümüze kadar yapılmış olan çalışmalara yer verilmiştir.
c. p-ADÜ Medyan Problemi Konusunda Literatür Araştırması
Serim üzerinde yerleştirme (network location) problemlerindendir
ve en yaygın tesis yerleşimi problemlerinden biri haline gelmiştir. Genellikle
fabrika, depo, postahane, okul, kamu binalarının yerleştirilmesi durumlarında
ortaya çıkar. Küme analizi gibi çalışmalarda da uygulaması görülür.
p–ADÜ medyan problemlerinin amacı, n talep noktaları olmak üzere,
kaynak-varış çiftleri arsındaki istenilen akışın rotalanması ve yerleştirilecek
olan ADÜ sayısının (p) belirlenebilmesi için gerekli olan toplam taşıma
maliyetini (zaman, uzaklık vb.) minimize etmektir (Alumur ve Kara, 2008).
p-ADÜ medyan problemlerinde atamalar tek ve çok atamalı olmak
üzere iki farklı şekilde yapılır. Aşağıda tek ve çok atamalar için örnek bir ADÜ
yer seçim problemi gösterilmiştir (Özger ve Oktal, 2008). Bu örnek tüm ADÜ
yer seçim problemleri için geçerlidir.
Şekil-4: Tek (a) ve Çok (b) Atamalı ADÜ Yer Seçim Problemi Örnek Ağ
Yapıları
13
Şekil-4’te i ve j düğüm noktalarını, h ADÜ’leri göstermektedir. Tek
atamalı yapıda örneğin i1 düğümü tek bir ADÜ’ye (h1 ) atanırken çok atamalı
yapıda i1 düğümü 1’den fazla ADÜ’ye (h1 veh2 ) atanmıştır (Özger ve Oktal,
2008).
(1) Tek Atamalı p-ADÜ Medyan Problemi Literatür Araştırması
Tek atamalı p-ADÜ Medyan problemi için ilk matematiksel model
O’Kelly (1987) tarafından geliştirilmiştir. Bu model, amaç fonksiyonu karesel
olduğundan doğrusal olmayan bir yapıya sahiptir.
Tek atamalı p-ADÜ medyan problemi ilgili ilk doğrusal tamsayılı model
Campbell (1994b) tarafından geliştirilmiştir. Çalışmada ayrıca talep noktasıADÜ bağlantıları arasında bir bağlantı hattının açılması için minimum akış eşik
değeri ve sabit maliyetler dikkate alınmıştır. Akış eşik değeri, i-j arasında
bağlantı hattının açılması için gerekli olan en az akış değerini ifade etmektedir.
Bu
sayede
bağlantı
hattı
sayısı
kısıtlanmıştır.
İdeal
durumda
doğrusallaştırılmış tamsayı modeli ile tamsayı çözümler elde edilir (bu
problemde tamsayı değişkenler ADÜ’lerin seçiminde kullanılmaktadır). Ancak
problemin boyutu büyüdükçe tamsayı çözüm elde etmek zorlaşır. Bu amaçla
“tamsayı gevşetmesi” uygulanır. Campbell (1994b)’nin modeline tamsayı
gevşetmesi uygulandığında tamsayı olmayan sonuçlar elde edilmekte ve çok
sayıda kısmi ADÜ ortaya çıkmaktadır (Bryan ve O’Kelly, 1999; Skorin-Kapov
vd. ,1996).
Skorin-Kapov vd. (1996), Campbell (1994b)’nin modeline tamsayı
gevşetmesi uygulandığında çok sayıda tam sayı olmayan sonuçlar elde
edildiğini belitmişler ve bunu giderebilmek için tek atamalı p-ADÜ medyan
problemi için yeni bir karışık tamsayılı model önermişlerdir. Skorin-Kapov vd.
(1996) tek atamalı p-ADÜ medyan problemi için optimal çözümün elde
edilmeye çalışıldığı ilk çalışmayı ortaya koymuşlardır (Skorin-Kapov vd. ,
1996).
14
O’Kelly vd. (1996), akışların simetrik olduğu kabulü ile problemin
boyutunu küçültecek yeni bir matematiksel model geliştirmiştir. Bu çalışmanın
önemli bir yönü, çalışmada, ADÜ’ler arası taşımada kullanılan maliyet azaltma
faktörünün çözüm sonuçları üzerine etkisinin araştırılmış olmasıdır.
Ernst ve Krishnamoorthy (1996), daha geniş ve karmaşık problemlerin
çözümü için daha az sayıda değişken ve kısıtın yer aldığı farklı bir doğrusal
tamsayılı model geliştirmiştir. Modelde ana dağıtım üsleri arası transferler, çok
ürünlü akış problemi olarak kabul edilmiştir. Burada her ürün belirli bir
düğümden çıkan trafik akışını temsil etmektedir. Ayrıca yazarlar bu çalışmada,
Avustralya posta servisinin, toplama ve dağıtım için her bir maliyet azaltma
faktörünü nasıl kullandığını modellemiş ve gözlemlemiştir.
Ebery (2001) tarafından tek atamalı p-ADÜ medyan problemi için
O(n2 ) değişken ve O(n2 ) kısıt içeren yeni bir model önerilmiştir. Bu model
literatürde yer alan daha önceki modellerden daha az sayıda değişken
kullanmaktadır, fakat bu modelin, yapılan karşılaştırma sonucunda, Ernst ve
Krishnamoorthy (1996) tarafından önerilen modelin çözüm zamanından çok
daha uzun bir çözüm zamanı gerektirdiği belirlenmiştir.
Elhedhli ve Hu (2005), ADÜ’lerdeki tıkanıklığı göz önüne alarak tek
atamalı p-ADÜ medyan problemi için doğrusal olmayan konveks maliyet
fonksiyonlu bir amaç fonksiyonu geliştirmiştir. Kısmi doğrusal fonksiyonlar
kullanarak modeli doğrusallaştırmış ve Lagrange gevşetmesi uygulamıştır. Bu
çalışma ile, CAB veri seti kullanılarak yapılan diğer çalışmalara kıyasla, topladağıt ağ yapısına yeni ve daha gerçekçi bir yaklaşım ortaya konmuştur.
Yaman (2009), tek atamalı p-ADÜ medyan ağını üç seviyede
incelemiştir. Birinci seviye ADÜ’lerin merkez ADÜ’lere, ikinci seviye, talep
düğümlerinin ADÜ’lere ve üçüncü seviye, talep düğümlerinin merkez ADÜ’lere
bağlanmasıdır. Amaç, teslim süresi kısıtları doğrultusunda hizmet kalitesini
arttırmaktır. Yazar, zaman sınırlaması olan hiyerarşik tek atamalı p-ADÜ
15
medyan problemi için yeni bir karışık tamsayılı model önermiştir. Yazar
modellerini CAB ve Türkiye ağı veri setleriyle test etmiştir.
Puerto vd. (2011), tek atamalı sıralı p-ADÜ medyan problemi için
karışık tamsayılı bir model geliştirmişler ve modeli dal sınır kesme tabanlı bir
algoritma ile optimal olarak çözmüşlerdir.
Yaman ve Elloumi (2012), star şebeke yapısına sahip tek atamalı pADÜ medyan problemi için karışık tamsayılı bir model geliştirmiş ve problemi
optimal olarak çözmüşlerdir.
p-ADÜ medyan problemi NP-zor’dur. ADÜ’lerin konumları sabitlense
bile, problemin atama kısmı NP-zor kalmaya devam eder (Kara, 1999). Bu
kapsamda p-ADÜ medyan problemlerinin optimal çözümüne ulaşmak zordur.
Optimizasyon yazılımları ile küçük boyutlu problemlerin çözümü
mümkün olmakla birlikte, büyük boyutlu problemleri çözmede bu yazılımlar
yetersiz kalmaktadır. Bu yüzden sezgisel ve meta sezgisel çözüm yöntemleri
geliştirilmiştir. Amaç fonksiyonunun alt ve üst sınırlarının belirlenmesi ve bu
sınırların mümkün olduğu kadar dar aralıklarda olması optimal çözüme
ulaşılmakta çözüm süresini kısaltan etkendir. Bu nedenle çalışmalarda
özellikle alt ve üst sınırların belirlenmesine yönelik sezgiseller geliştirilmiştir
(Alumur ve Kara, 2008).
Aşağıdaki bölümde tek atamalı p-ADÜ medyan probleminin çözümüne
yönelik yapılan sezgisel ve metasezgisel çalışmalar ele alınmıştır.
Tek atamalı p-ADÜ medyan problemine yönelik olarak ilk sezgiseller
O’Kelly (1987) tarafından sunulmuştur (HEUR1 ve HEUR2). Her iki sezgisel
de tüm ihtimallerin sıralanması ve düğüm noktalarının en yakın ADÜ’ye
atanması yaklaşımına dayanır. Birinci sezgiselde (HEUR1); talep noktaları en
yakın ADÜ’ye atanır. İkinci sezgiselde (HEUR2) ise; bir talep noktasına en
16
yakın iki ADÜ seçilerek en düşük toplam maliyeti sağlayan ADÜ’ye atama
yapılır. Bu sezgiseller CAB veri setinin çözümünde kullanılmışlardır.
Aykin (1990)’e göre bu yaklaşım, ADÜ yer seçimi ve ataması
problemlerinde en iyi sonucu vermez. Bu eksikliğin giderilmesi için Yazar,
akışa dayalı atama yaklaşımını önermiştir.
Klincewicz (1991,1992) tek atamalı p-ADÜ medyan probleminin
çözümüne yönelik çeşitli sezgiseller önermiştir. Klincewicz (1991), O’Kelly
(1987)’nin ortaya koyduğu üst sınır yaklaşımını iyileştirmek amacıyla sadece
mesafeye bağlı değil, hem akışlara hem mesafeye dayalı atama prosedürü
geliştirmiş ve O’Kelly (1987)’nin sezgiselinden daha etkin sonuçlar elde
etmiştir. Klincewicz (1991)’in geliştirdiği değiştirme (exchange) sezgiselinde,
düğüm noktaları ADÜ ve ADÜ olmayan düğümler kümesi olmak üzere 2
kümeye ayrılır. İlk olarak düğümler ADÜ’lere atanır ve amaç fonksiyonu değeri
belirlenir. Bundan sonraki aşamada ADÜ olmayan düğümler ile ADÜ’ler
arasında değiştirme yapılır, amaç ilk aşamada elde edilen amaç fonksiyonu
değerinden daha düşük maliyet elde etmektir. Böylece optimal çözümü veren
ADÜ yerleştirmesi ve düğümlerin bu ADÜ’lere atanmaları gerçekleştirilir.
Diğer bir çalışmasında Klincewicz (1992), tabu arama ve GRASP
sezgisellerini sunmuştur. Her iki sezgisel de talep noktalarının en yakın
ADÜ’ye atanması kuralına göre geliştirilmiştir. Yine bu sezgisellerin
performanslarının test edilmesinde, CAB verisi ve 52 talep noktası ile 10’a
kadar çıkan ADÜ sayısının kullanıldığı daha kapsamlı bir veri seti
kullanılmıştır.
Tek atamalı p-ADÜ medyan problemi için bir başka tabu arama
sezgiseli de Skorin-Kapov ve Skorin-Kapov (1994), tarafından geliştirilmiştir.
CAB veri setinin kullanıldığı bu çalışmadan elde edilen sonuçlar O’Kelly
(1987)’nin (HEUR1 ve HEUR2) sezgiselleri ve Klincewicz (1992)’in tabu arama
sezgiseli ile karşılaştırılmıştır. Sonuçların daha etkin olmasına rağmen atama
kısmı için daha uzun çözüm zamanına ihtiyaç duyduğu gözlenmiştir.
17
O’Kelly vd. (1995), mesafelerin üçgen eşitsizliğini desteklediği
varsayımına dayalı, amaç fonksiyonundaki karesel yapıyı doğrusallaştırmak
amacıyla bir alt sınır belirleme tekniği sunmuşlardır. Bu yöntemi kullanarak
yazarlar, Skorin-Kapov ve Skorin-Kapov (1994)’in tabu arama sezgiseliyle
çözdüğü problemin sınırları arasındaki farkın azaldığını tespit etmiştir. Küçük
problemlerde (10-15 düğüm) ortalama farkın %3.3, büyük problemlerde (2025 düğüm) %5.9’a düştüğü belirtilmiştir.
Çok atamalı p-ADÜ medyan probleminin çözümü tek atamalı p-ADÜ
medyan probleminin optimal çözümüne alt sınır sağladığı yaklaşımdan yola
çıkarak, Campbell (1996), iki yeni sezgisel (MAXFLO ve ALLFLO) önermiştir.
Bu sezgisellerde yerleşim kararı aynı olmakla beraber, atama için farklı kurallar
geliştirilmiştir.
Ernst ve Krishnamoorthy (1996), tavlama benzetimi sezgiseli ile dal ve
sınır algoritmasına dayalı bir sezgisel algoritma geliştirmiştir. Bu çalışmada
doğrusal programlama tabanlı dal ve sınır algoritmasında kullanılacak üst
sınırlar, tavlama benzetimi sezgiseli ile belirlenmektedir. Yazarlar çalışmayı
hem çözüm kalitesi hem de çözüm süresi bakımından Skorin-Kapov ve SkorinKapov (1994)’un tabu arama sezgiseliyle karşılaştırılabilir bulmuştur. Ayrıca
çalışmayı CAB ve AP veri setleriyle de test etmiş ve 50’den fazla düğüm
noktasının olduğu problemlerin çözümünde yöntem başarılı olamamıştır.
Smith vd. (1996), modifiye edilmiş Hopfield sinir ağları yöntemini Tek
atamalı p-ADÜ medyan probleminin çözümü için uyarlamıştır. Çalışmada,
daha az sayıda değişken ve kısıt gerektirdiğinden, O’Kelly (1987)’nin karesel
tamsayılı modeli kullanılmıştır. Yazarlar, CAB veri setini kullanarak Ernst ve
Krishnamoorthy (1996)’nin tavlama benzetimi yönteminin sonuçları ile
geliştirdikleri
yöntemin
sonuçlarını
karşılaştırmıştır.
Çalışmada
çeşitli
çözücülerin performansları da karşılaştırılmıştır. Ayrıca Hopfield sinir ağı
yönteminin tavlama benzetimi yöntemi ile karşılaştırılabilir düzeyde olduğu
belirtilmiştir.
18
Pirkul ve Schilling (1998), alt ve üst sınırları makul bir sürede belirleyen
etkin bir lagrange gevşetmesi yöntemi geliştirmiştir. Bunun yanında alt
problemlerin biri için kesme kısıtı geliştirilmiştir. Yazarlar o tarihe kadar
sezgisel bir yöntemle elde edilebilen optimal sonuca en yakın uzaklık değerini
elde etmişlerdir. Ulaştıkları ortalama uzaklık %0,048 ve maksimum uzaklık ise
%1dir.
ADÜ yer seçim problemleri ile ilgili 1987 yılından günümüze çeşitli
modeller geliştirilmiş ve bu modellerin çözümü için çeşitli sezgisel ve meta
sezgisel yöntemler, modeller üzerine uygulanmıştır. Yukarıda bu çalışmaların
bir kısmı açıklanmaya çalışılmıştır. Tablo-2’de tek atamalı p-ADÜ medyan
problemleri ile ilgili günümüze kadar yapılan çalışmaların özeti sunulmuştur.
Tablo-2: Tek Atamalı p-ADÜ Medyan Problemi İçin Yapılan Çalışmalar
Yıl
1987
1990
Yazarlar
O’Kelly
Aykin
1991
Klincewicz
1992
1994b
1996
Klincewicz
Campbell
Skorin-Kapov ve
Skorin-Kapov
O’Kelly vd.
Campbell
Ernst ve
Krishnamoorhy
O’Kelly vd.
1996
Skorin-Kapov vd.
1996
1997
Smith vd.
Sohn ve Park
Ernst ve
Krishnamoorthy
Pirkul ve Schilling
Sohn ve Park
Sohn ve Park
Abdinnour-Helm
Ebery
Eldedhli ve Hu
Chen
Kratica vd.
Randall
He vd.
Yaman
Limbourg ve Jourquin
Takano ve Arai
Ilic vd.
Puerto vd.
Yaman ve Elloumi
1994
1995
1996
1996
1998b
1998
1998
2000
2001
2001
2005
2007
2007
2008
2009
2009
2009
2009
2010
2011
2012
Yaklaşım
Karesel tamsayılı program, HEUR1 ve HEUR2 sezgiselleri.
Optimal atamayı bulan bir prosedür
Tek atamalı p-ADÜ medyan probleminin çözümüne yönelik
sezgisel yöntemler
Tabu arama ve GRASP sezgiselleri
İlk doğrusal tamsayılı model
Tabu arama sezgiseli
Alt sınır tekniği
MAXFLO ve ALLFLO sezgiselleri
Yeni matematiksel model, Tavlama benzetimi sezgiseli, dal ve
sınır tekniği
Simetrik akış verisi için yeni model
Sıkı doğrusal programlama gevşetmesi için yeni bir
matematiksel model
Modifiye edilmiş Hopfield sinir ağı sezgiseli
İki ADÜ yerleşim problemi
En kısa yol tabanlı dal ve sınır algoritması
Lagrange gevşetmesi sezgiseli
Simetrik maliyetler ve atama problemi için yeni bir model
Üç ADÜ atama problemi
Tavlama benzetimi sezgiseli
p=2 ve p=3 için yeni model
ADÜ’lerdeki yoğunluğu minimize eden matematiksel model
Tabu arama ve tavlama benzetimi sezgiselleri
Genetik algoritma (GAHUB1 VE GAHUB2)
Karınca kolonisi sezgiseli
Karesel tamsayılı model
3 seviyeli hiyerarşik model
Akış tabanlı sezgisel
Genetik algoritma
Genel değişken komşuluk araştırması
Karesel tamsayılı model
Karesel tamsayılı model
19
(2) Çok Atamalı p-ADÜ Medyan Problemi Literatür Araştırması
Çok atamalı problemlerde, her talep noktası, gelen ve giden
akışları birden fazla ADÜ’’ye gönderebilir, dolayısıyla her talep noktası birden
fazla ADÜ’ye atanabilir (Alumur ve Kara, 2008).
Çok atamalı p-ADÜ medyan probleminin ilk doğrusal tamsayılı modeli,
Campbell (1992) tarafından geliştirilmiştir. Bu model, 0-1 karma tamsayılı
doğrusal bir modeldir.
Campbell (1994b), bağlantı hatlarında kapasite sınırının olmadığı, her
kaynak varış çifti arasındaki toplam akışın minimum maliyetli ADÜ üzerinden
gerçekleştiği ve tüm Xijkm değişkenlerinin 0-1 olduğu modellerin optimal
çözümünün olduğunu belirtmiştir. Böylece Xijkm değişkenlerini tamsayı olarak
kısıtlamaya gerek kalmamıştır. Yazar, ayrıca, çok atamalı P-ADÜ medyan
problemini, akış eşik değerlerini ve bağlantı hatları için sabit maliyetleri dikkate
alarak doğrusal tamsayılı program olarak modellemiştir.
Skorin-Kapov vd. (1996), Campbell (1994b)’nin geliştirdiği modelde
yer alan bazı kısıtları, bu kısıtların toplanmış formlarıyla yer değiştirerek yeni
karışık tamsayılı bir model geliştirmişlerdir. Bu model, n’ler ikil değişken olmak
üzere, (n4 + n) değişken ve (2n3 + n2 + 1) doğrusal kısıt içerir. Bu modele
doğrusal programlama gevşetmesi uygulanmış ve CAB veri seti kullanılarak
yapılan uygulamaların büyük bir kısmı tamsayılı sonuçlar vermiştir. Doğrusal
programlama gevşetmesinin tamsayılı sonuçlar vermediği durumlarda ise
yazarlar, optimal sonucu elde edebilmek için kesin sayımlı ağaç araması
yöntemini kullanmışlardır. Bu ağaç araması normal olarak çok az sayıda ağaç
düğümlerini içermektedir.
Ernst ve Krishnamoorthy (1998a), daha önce kendilerinin Ernst ve
Krishnamoorthy (1996) geliştirmiş olduğu tek atamalı modeli temel alarak, çok
atamalı p-ADÜ medyan problemi için yeni bir model önermişlerdir. Bu model,
n’ler ikil değişken olmak üzere (2n3 + n2 + n) değişken ve (4n2 + n + 1)
20
doğrusal kısıt içerir. Ayrıca Ernst ve Krishnamoorthy (1998a), bu modelin,
Skorin –Kapov vd. (1996) geliştirmiş olduğu modelden daha etkili bir model
olduğunu göstermişlerdir.
Campbell (1996), çok atamalı p-ADÜ medyan problemi için açgözlü
değiştirme sezgiselini önermiştir.
Ernst ve Krishnamoorthy (1998a), optimal sonuçlar elde edebilmek
için, doğrusal programlama tabanlı dal sınır metodunu sunmuşlar, aynı
zamanda aykırı eşitsizlikler tanımlayarak ve bunları doğrusal programlamaya
ekleyerek, alt sınırı güçlendirmişlerdir. Yazarlar, ayrıca iki adet sezgisel
önermişlerdir. Bunlardan birincisi en kısa yol tabanlı sezgisel, ikincisi ise tam
sayımlama sezgiselidir. Önerilen iki sezgisel de ADÜ ‘lerin yerlerinin
sabitlenmesi ve her düğüm çifti arasındaki akışın, düğümlere en yakın ADÜ’ler
vasıtasıyla gerçekleşmesi prensibiyle çalışmaktadır. Her iki sezgisel için CAB
ve AP veri setleri kullanılmış ve sonuçları ortaya konulmuştur.
Aynı yıl, yazarlar Ernst ve Krishnamoorthy (1998b), hesaplama
zamanı açısından daha etkili olan bir başka dal sınır algoritması ortaya
koymuşlardır. Bu çalışmada doğrusal programlama gevşetmesi çözmek
yerine, en kısa yol problemlerini çözerek alt sınırlar elde etmişlerdir. Yeni
geliştirilen bu dal sınır algoritması, aynı yazarlar tarafından (1998a) geliştirilen
doğrusal programlama tabanlı dal sınır algoritmasından, tutarlı bir şekilde çok
daha iyi bir performans sergilemiş, önceki algoritmadan 500 kez daha hızlı
çalışmış ve çok daha az bellek kullanmıştır. Yazarlar, geliştirdiği bu yeni
algoritma ile literatürde daha önce çalışılmış olan tüm problemlerden daha
geniş çaplı problemler için kesin sonuçlar bulmuşlardır. Örnek olarak 200
düğümlü ve 3 ADÜ’lü problemi 632 saniyede çözebilmişlerdir. Fakat AP veri
seti içindeki 100 düğümlü ve p>5 ve 200 düğümlü p>3 problemlerini kabul
edilebilir bir hesaplama zamanında çözememişlerdir.
Boland vd. (2004), Ernst ve Krishnamoorthy (1998a) tarafından
önerilen modelin bellek gereksinimi ve hesaplama zamanı açısından hızlı
21
olmasına rağmen alt sınır belirleme açısından zayıf olduğunu belirtmişlerdir.
Yazarlar bu zayıflığı giderebilmek için, optimal çözüm tekniklerinin, önişlem
teknikleri geliştirme ve kısıt sıkılaştırma gibi özelliklerini tanımlamışlardır. Bu
çalışmalarını çok atamalı p-ADÜ medyan problemine uyguladıklarında kısıtları
sıkılaştırmanın bazı sonuçların iyileştirilmesi adına küçümsenemeyecek
derecede önemli etkiler yaptığını tespit etmişlerdir.
Campbell (2009), seyahat süresi kısıtlı iki yeni model önermiştir.
Kuzey Amerika’daki karayolu taşımacılık hizmeti ağını içeren ve hizmet
düzeyinin her kaynak-varış çifti arasındaki maksimum seyahat süresi kısıtı ile
kısıtlandığı bir problem üzerinden CPLEX çözücü ile modeli çözmüştür. Ayrıca
modeli CAB veri setiyle de test etmiştir.
Tablo-3’te çok atamalı p-ADÜ medyan problemlerine ait günümüze
kadar yapılan çalışmaların özeti sunulmuştur.
Tablo-3: Çok Atamalı p-ADÜ Medyan Problemi İçin Yapılan Çalışmalar
Yıl
Yazarlar
Yaklaşım
Karesel tamsayılı model, HEUR1 ve HEUR2
sezgiselleri.
İlk doğrusal tamsayılı model
Akış eşik değerlerini ve bağlantı hatları için sabit
maliyetleri dikkate alan yeni bir model
Hırslı-değişim (Greedy-Interchange) sezgiseli
1987
O’Kelly
1992
Campbell
1994b
Campbell
1996
Campbell
1996
O’Kelly vd.
1996
Skorin-Kapov vd.
1998a
Ernst ve Krishnamoorthy
1998b
Ernst ve Krishnamoorthy
1998
Sohn ve Park
1999
Sasaki vd.
2004
Boland vd.
Simetrik akış verisi için yeni model
Yeni bir matematiksel model (Doğrusal programlama
gevşetmesi)
Doğrusal programlama gevşetmesine dayalı sayımlama
algoritması ve iki sezgisel
En kısa yol problemi çözüm tekniklerine dayanan dal ve
sınır algoritması
En kısa yol tabanlı algoritma
1-durmalı (1-stop) çok atamalı p-ADÜ medyan problemi
ve çözüm yöntemi
Önişlem teknikleri ve kısıt sıkılaştırması
2009
Campbell
Yeni bir karma tamsayılı model
2009
Eiselt ve Marianov
Sezgisel konsantrasyon prosedürü
2010
Çetiner vd.
Tekrarlı sezgisel (Iterative heuristic )
2011
Ishfaq ve Sox
Tabu arama sezgiseli
2012
Ishfaq ve Sox
2012
Lin vd.
2012
Garcia vd.
Tabu arama sezgiseli
Kapasite sınırlaması olan çok atamalı p-ADÜ medyan
problemi için genetik algoritma
Dal ve kesme tabanlı karışık tamsayılı model
2013
Kratica
Elektromanyetik benzetimli sezgisel
2014
Peiro vd.
Kapasite kısıtsız r atamalı problem için yeni bir sezgisel
22
d. Sabit Maliyetli ADÜ Yer Seçim Problemi Konusunda Literatür
Araştırması
P-ADÜ medyan probleminde ADÜ sayısı p ile ifade edilen ve
modeli geliştiren tarafından belirlenen bir parametredir. Sabit maliyetli ADÜ yer
seçim problemlerinde ise ADÜ sayısı karar değişkeni olarak yer almakta ve
çözüm sonucunda belirlenmektedir. Ve yine p-ADÜ medyan probleminde ADÜ
açma maliyeti dikkate alınmamaktadır.
Sabit maliyetli ADÜ yer seçim problemleri “kapasite sınırı olan” ve
“kapasite sınırı olmayan” ADÜ yer seçim problemleri olmak üzere iki ayrı
başlıkta ele alınmaktadır. Aşağıdaki bölümde öncelikle kapasite sınırı olmayan
ADÜ yer seçim problemleri, (UHLP: Uncapacitated Hub Location Problem)
ardından kapasite sınırı olan ADÜ yer seçim problemleri (CHLP: Capacitated
Hub Location Problem) incelenmiştir.
p-ADÜ medyan problemine benzer şekilde bu problem tipleri için de
tek ve çok atamalı yapılar söz konusudur.
(1) Kapasite Sınırı Olmayan ADÜ Yer Seçim Problemi Literatür
Araştırması
P-ADÜ medyan probleminde ADÜ açma sabit maliyetleri gözardı
edilmiştir. O’Kelly (1992a), ADÜ sayısını karar değişkeni yaparak, sabit
maliyetli tek atamalı ADÜ yer seçim problemini tanımlamıştır. Bu problemi
karesel tamsayılı programlama ile modellemiştir. Çalışmalarda ADÜ açma
maliyeti “sabit maliyet (fixed cost)” olarak yer almaktadır.
Tek/çok atamalı ve kapasite kısıtlı/kapasite kısıtsız ADÜ yer seçim
problemleri için ilk doğrusal programlama modelleri, Campbell (1994b)
tarafından sunulmuştur.
23
Kapasite kısıtsız tek atamalı ADÜ yer seçim problemiyle ilgili birçok
çalışma
mevcuttur.
Abdinnour-Helm
ve
Venkataramanan
(1998),
şebekelerdeki çok ürünlü akış fikri temeline dayalı yeni bir karesel tamsayılı
model sunmuşlardır. Yazarlar daha sonra alt sınırları elde etmek için temel
şebeke yapısını kullanan dal sınır prosedürüyle bu modeli çözmüşlerdir. Dal
sınır algoritması problemi optimal olarak çözebilmek için hatırı sayılır bir
zamana ihtiyaç duyduğundan, yazarlar problemi hızlı ve etkili bir şekilde
çözebilmek için genetik bir algoritma önermişlerdir.
Abdinnour-Helm (1998), genetik algoritma ve tabu araştırmasının
karışımı olan yeni bir sezgisel metod önermiştir. Bu sezgiselde öncelikle ADÜ’
lerin sayısına ve yerleşim yerlerine karar vermek için genetik algoritma
kullanılmış, daha sonra optimal atamaları bulan tabu araştırması sezgiseline
başlangıç çözümü oluşturabilmek için her talep noktası en yakın ADÜ ye
atanmıştır. Yazar daha sonra CAB veri setini kullanarak kendi hibrit sezgiseli
ile
Abdinnour-Helm
ve
Venkataramanan
(1998)’ın
genetik algoritma
sonuçlarını karşılaştırmış ve kendi hibrit sezgiselinin çok daha iyi sonuçlar
verdiğini tespit etmiştir.
Topçuoğlu vd. (2005), kapasite kısıtsız tek atamalı ADÜ yer seçim
problemleri için yeni bir genetik algoritma önermişlerdir. Yazarlar, CAB ve AP
veri
setlerini
kullanılarak
yaptığı
karşılaştırmalar
neticesinde,
kendi
geliştirdikleri algoritmanın, Abdinnour-Helm (1998) tarafından geliştirilen hibrit
algortimaya göre çözüm kalitesi ve hesaplama zamanı bakımından daha üstün
olduğunu göstermişlerdir.
Cunha ve Silva (2007), aynı problem için genetik algoritma ve tavlama
benzetimi sezgisellerine dayalı melez bir sezgisel geliştirmiştir. Bu çalışmada
maliyet azaltma faktörü (∝), ADÜ’ler arasındaki toplam yük miktarı ile
değişebilmektedir.
Bu problem tipi için başka bir sezgisel de Chen (2007) tarafından
önerilmiştir. Bu sezgisel, tavlama benzetimi metodu, tabu listesi ve geliştirme
24
prosedürleri temeline dayanmaktadır. Yazar, geliştirdiği yöntemin, Topçuoglu
vd. (2005) tarafından geliştirilen yönteme göre çözüm zamanı ve kalitesi
açısından daha üstün olduğunu göstermiştir.
Çalışmanın bundan sonraki bölümünde kapasite sınırı olmayan çok
atamalı ADÜ yer seçim problemleri (UMAHLP: Uncapacitated Multiple
Allocation Hub Location Problem) için yapılan çalışmalar incelenmiştir.
Kapasite sınırı olmayan çok atamalı ADÜ yer seçim problemleri ile ilgili
ilk doğrusal model Campbell (1994b) tarafından sunulmuştur.
Klincewicz (1996), çok atamalı kapasite kısıtsız ADÜ yer seçim
problemleri için, dal sınır bakış açısıyla eşlenik artışa dayalı bir algortima
geliştirmiştir. Çalışmada ADÜ’ler, daha önceden belirlenen potansiyel ADÜ’ler
arasından seçilmiş ve çözüm algoritması CAB veri setiyle test edilmiştir.
Mayer ve Wagner (2002), kapasite sınırı olmayan çok atamalı ADÜ
yer seçim probleminin çözümüne yönelik “Hublocater” adını verdikleri yeni bir
dal-sınır yöntemi geliştirmiştir. Hublocater’ın en önemli avantajı alt sınırın elde
edilmesidir. Alt sınırın avantajı ise, dal sınır algoritması için gerekli olan
hesaplama zamanını azaltmasıdır. Yazarlar, Hublocater’ı, CAB ve AP veri
setlerinde CPLEX çözücü kullanarak Klincewicz (1996)’in çalışmasıyla
karşılaştırmış ve geliştirdikleri algoritmanın Klincewicz (1996) tarafından
geliştirilen algoritmaya göre daha iyi sonuçlar vermesine rağmen, CPLEX
çözücüsünün her zaman en iyi performansı sergileyemediğine dikkat
çekmişlerdir.
Kapasite sınırı olmayan çok atamalı ADÜ yerleşim problemi için bir
diğer çalışma Hamacher vd. (2004) tarafından sunulmuştur. Çalışmada
kısıtları farklılaştırılan yeni bir çok yüzlü model önerilmiştir.
Kısıt farklılaştırması yaklaşımını kullanarak Marin (2005b), kapasite
sınırlaması olmayan çok atamalı ADÜ yerleşim problemi için sırtçantası
25
probleminin bazı çok yüzlü özelliklerini uygulayarak bir gevşet ve kes
algoritması geliştirmiştir.
Marin vd. (2006), daha önceki formülüzasyonların genel bir hali olan
ve üçgensel eşitsizlik maliyet yapısı varsayımını gevşeten yeni bir model
önermişlerdir. Yazarlar bazı çokyüzlü sonuçları kullanarak kısıt sayısını
azaltmış ve kısıtları sıkılaştırmışlardır. Bu model öncekilere göre en üstün
modeldir.
Canovas vd. (2007), eşlenik artış tekniğine dayalı bir sezgisel
geliştirmiştir. Geliştirilen sezgisel, dal ve sınır algoritması ile birlikte
kullanılmıştır ve dal ve sınır algoritmasında kullanılmak üzere alt sınırları
belirlemektedir. Çalışma, CAB ve AP veri setleri üzerinde test edilmiştir.
Yazarlar çalışmada 120 düğümlü ağlar için çözüm bulunabildiğini belirtmiştir
ki, kapasite sınırı olmayan çok atamalı ADÜ yerleşim problemi için o tarihe
kadar elde edilen en iyi hesaplama sonuçlarıdır.
Silva ve Cunha (2009), kapasite sınırı olmayan tek atamalı ADÜ
yerleşim problemine yönelik iki aşamalı ve üç farklı çoklu-başlangıç tabu
arama sezgiseli ile bütünleşik bir tabu arama sezgiseli sunmuştur.
Çalışmalarını CAB ve AP veri setleriyle test eden yazarlar, sonuçların diğer
çalışmalarla karşılaştırılabilir olduğunu belirtmiştir.
Tablo-4’te kapasite kısıtı olmayan tek ve çok atamalı ADÜ yer seçim
problemi ile ilgili günümüze kadar yapılan çalışmaların özeti sunulmuştur.
26
Tablo-4: Kapasite Sınırı Olmayan Sabit Maliyetli Tek ve Çok Atamalı ADÜ
Yer Seçim Problemi İçin Yapılan Çalışmalar.
Atama
Şekli
Yıl
Yazarlar
Çalışmalar
1992a
1994b
O’Kelly
Campell
Abdinnour-Helm ve
Venkataramanan
1998
Abdinnour-Helm
2005
Topçuoğlu vd.
2007
Cunha ve Silva
2007
Chen
2009
2009
Yang
Alumur vd.
2009
Silva ve Cunha
2009
2009
2009
O’Kelly
Contreras vd.
Filipovic vd.
2009
Iwasa vd.
2010
2010
2010
2011
2012
Contreras vd.
Han
Lin
Catanzaro vd.
Alumur vd.
Karesel tamsayılı model
İlk doğrusal tamsayılı model
Dal ve sınır yöntemi ile yeni karesel model ve genetik
algoritmaya dayalı sezgisel
Genetik algoritma ve tabu araması yöntemlerine
dayanan bir melez sezgisel
Genetik algoritmaya dayalı sezgisel
Genetik algoritma ve tavlama benzetimi
sezgisellerine dayalı melez bir sezgisel
Tavlama benzetimi ve tabu aramasına dayalı bir
melez sezgisel
1-ADÜ Karışık tamsayılı model
Tamsayılı model
İki aşamalı ve üç farklı çoklu-başlangıç tabu arama
sezgiseli ile bütünleşik bir tabu arama sezgiseli
Tamsayılı model
Lagrange gevşetmesi yöntemi
Genetik algoritmaya dayalı sezgisel
Lagrange gevşetmesi tabanlı rastgele yakınlaştırma
algoritması (en yakın komşu algoritması)
Karışık tamsayılı model
Tamsayılı model ve tabu arama sezgiseli
Karışık tamsayılı model
Dal ve kesme algoritması
Stokastik programlama
Yıl
Yazarlar
Çalışmalar
1994b
1996
Campell
Klincewicz
1996
Skorin-Kapov vd.
2002
2004
2004
Mayer ve Wagner
Boland vd.
Hamacher vd.
2005b
Marin
2006
2006
2007
Marin vd.
Camargo vd.
Gelareh ve Nickel
2007
Canovas vd.
2007
2008
2009
Wagner
Camargo vd.
Camargo vd.
2009
Camargo vd.
2010
Gelareh vd.
2011a
Contreras vd.
2011c
2011
2011
2011
2012
2013
Contreras vd.
Gelareh and Nickel
Vasconcelos vd.
Vidovic vd.
Alumur vd.
Oktal ve Ozger
İlk doğrusal tamsayılı model
Dal ve sınır algoritması
Yeni bir matematiksel model (Doğrusal programlama
gevşetmesi)
Dal ve sınır algoritması (Hublocater)
Önişlem prosedürü ve kısıt sıkılaştırma
Çok yüzlü bir model
Gevşetme ve kesme algoritması (Relax and cut
algorithm)
Yeni bir matematiksel model
Benders ayrışım algoritması
Benders ayrışım algoritması
Dal ve sınır algoritması ve eşlenik artış tekniğine
dayalı bir sezgisel
Kümeleme (Genetik algoritma ve Tabu araması)
Benders ayrışım algoritması
Benders ayrışım algoritması
Genelleştirilmiş Benders ayrışım algoritması tabanlı
doğrusal olmayan karışık tamsayılı programlama
Karışık tamsayılı doğrusal programlama (Lagrange
ayrışım yöntemi)
Monte Carlo simülasyonu tabanlı bir algoritma ve
Benders ayrışım algoritması
Geliştirilmiş Benders ayrışım algoritması
Benders ayrışım algoritması
Tamsayılı model
Karışık tamsayılı model
Stokastik programlama
Karışık tamsayılı model
Tek Atamalı
1998
Çok Atamalı
Atama
Şekli
27
(2) Kapasite Sınırı Olan ADÜ Yer Seçim Problemi Literatür
Araştırması
Aykin (1994), kapasite kısıtlı, sabit maliyetli ADÜ yer seçim
problemini ortaya koymuştur. Yazar problemi, ana dağıtım üssü olmayan
noktalar arasında da direk bağlantıya izin vererek modellemiş, ayrıca bu
problemin çözümüne yönelik olarak alt sınırların lagrange gevşetmesi
yöntemiyle elde edildiği bir dal ve sınır algoritması geliştirmiştir.
Aykin (1995a) belirlenmiş p adet ADÜ için sabit maliyetli yer seçim
problemi üzerine çalışmıştır. Çalışmasında iki farklı yer seçim problemini
karşılaştırmıştır. Gevşek (non-strict) olarak adlandırdığı birinci yaklaşımını,
sıralama (enumeration) yöntemiyle modelleyerek çözmüştür. Bu yaklaşım için
ayrıca bir hırslı-değiştirme sezgiseli de önermiştir. İkinci yaklaşımı ise, gevşek
olmayan olarak tanımlamıştır.
Ernst ve Krishnamoorthy (1999), kapasite kısıtlı, tek atamalı ADÜ yer
seçim problemi için iki yeni model önermişlerdir. Bu modeller, daha önce pADÜ medyan problemi için geliştirilmiş olan karışık tamsayılı modelin modifiye
edilmiş halleridir. Bu modellerde, kapasite kısıtı sadece ADÜ’lere ADÜ
olmayan noktalardan direkt gelişler için uygulanmıştır. Kapasite açıklaması
posta servis uygulamalarında, ADÜ’lerin dağıtım kapasitelerini göstermek için
sıkça kullanılmaktadır.
Ernst ve Krishnamoorthy (1999), kapasite kısıtlı, tek atamalı ADÜ yer
seçim problemi için iki sezgisel önermişlerdir. Bu sezgisellerden birincisi
tavlama benzetimi tabanlı, ikincisi ise rastgele iniş tabanlıdır. Yazarlar ayrıca
bu sezgiseller vasıtasıyla elde ettikleri üst sınırları kullanarak, doğrusal
programlama tabanlı dal sınır metodu vasıtasıyla optimal çözümler elde
etmişlerdir. Daha sonra dal sınır algoritmasının performansını arttırmak
maksadıyla bazı önişlem adımları sunmuşlardır. Algoritma, CAB veri seti sabit
maliyet ve kapasiteleri içermediğinden, sadece AP veri setiyle test edilmiştir.
28
Labbe vd. (2005), kapasite kısıtlı, tek atamalı ADÜ yer seçim
probleminin çokyüzlü özelliklerini incelemiş ve bu sonuçlara dayalı olarak
dallandırma ve kesme algoritması ortaya koymuştur. Çalışmada her düğümün
kapasitesinin o düğüme gelen ve düğümden çıkan trafiğin toplamına eşit
olduğu kabul edilmiştir.
Costa vd. (2007), kapasite sınırı olan tek atamalı ADÜ yer seçim
problemine iki amaçlı bir yaklaşım önermiştir. ADÜ’ler üzerinden sağlanan
akışın
kapasite
kısıtı
kullanılarak
sınırlandırılması
yerine,
yazarlar,
matematiksel modelin amaç fonksiyonunda değişiklik yaparak çok amaçlı bir
yapı oluşturmuştur. Yazarlar, BSAHLP-1 ve BSAHLP-2 adını verdikleri iki
model geliştirmiştir. Her iki modelde de ilk amaç, toplam taşıma maliyetinin ve
ADÜ açma sabit maliyetinin minimize edilmesidir. BSAHLP-1 için ikinci amaç,
toplam işlem süresinin minimize edilmesi iken, BSAHLP-2 modeli için ikinci
amaç, ADÜ’lerdeki maksimum işlem süresinin minimize edilmesidir. Yazarlar,
pareto optimal çözümleri bulmak için tekrarlı bir çözüm prosedürü önermiştir.
Çalışmanın bundan sonraki bölümünde kapasite sınırı olan çok
atamalı ADÜ yer seçim problemleri (CMAHLP: Capacitated Multiple Allocation
Hub Location Problem) için yapılan çalışmalar incelenmiştir.
Ebery vd. (2000), kapasite kısıtlı ADÜ yer seçim problemini, çok
atamalı olarak düşünmüşlerdir. Ortaya koydukları model, kapasite kısıtları ve
yerleştirilecek olan ADÜ’lerin sayısında kısıtlama olmaması dışında, Ernst ve
Krishnamoorthy (1998a) tarafından önerilen çok atamalı P-ADÜ medyan
probleminin
modeline
benzemektedir.
Çalışmada,
üst
sınırların
belirlenmesinde en kısa yol problemi çözüm tekniklerine dayanan bir sezgisel
ile bütünleştirilmiş doğrusal programlamaya dayalı bir dal ve sınır çözüm
prosedürü sunulmuştur. Yazarlar çalışmada kapasite kısıtlı çok atamalı ADÜ
yer seçim problemini posta dağıtım ağı için düşünmüşler, seçilecek olan
ADÜ’lerin kapasitesini, yalnızca postaları toplama aşamasının etkileyeceğini
söylemişler ve çalışmalarında iki farklı model sunmuşlardır.
29
Sasaki ve Fukushima (2003), Kapasite sınırlaması olan 1-durmalı çok
atamalı ADÜ yer seçim problemine yönelik bir model sunmuştur. Bu modelde
hem ADÜ’ler, hem de ayrıtlar için kapasite sınırı uygulanmıştır. Bu problemin
çözümüne yönelik olarak, alt ve üst sınırların, lagrange gevşetmesiyle elde
edildiği bir dal ve sınır algoritması geliştirilerek, CAB verisi ile test edilmiştir.
Boland vd. (2004), kapasite kısıtlı ve kapasite kısıtsız çok atamalı ADÜ
yer seçim problemlerinin optimal çözümlerinin bazı özelliklerini özetlemişlerdir.
Yazarlar, hali hazırdaki karışık tamsayılı doğrusal programlama modellerine
doğrusal programlama gevşetmesi geliştirebilmek için, optimal çözümlerin
incelenmesi neticesinde buldukları sonuçlara dayanarak, önişlem prosedürleri
ve sıkılaştırma kısıtları geliştirmişlerdir. Ayrıca yazarlar problemin kapasite
kısıtlı versiyonunun hesaplama zamanını geliştirebilmek için akış kapsama
kısıtları kullanmışlar ve çözüm zamanını kısaltmışlardır.
Marin (2005a), çok atamalı, kapasite kısıtlı ADÜ yer seçim problemleri
için, Ebery vd. (2000) tarafından geliştirilen model ile aynı fikre dayanarak, yeni
bir model önermiştir.
Tablo-5’te kapasite kısıtlı çok atamalı ADÜ yer seçim problemi ile ilgili
günümüze kadar yapılan çalışmaların özeti sunulmuştur.
30
Tablo-5: Kapasite Sınırı Olan Tek ve Çok Atamalı ADÜ Yer Seçim Problemi
İçin Yapılan Çalışmalar
Atama Şekli
Yıl
1994b
Yazarlar
Campell
1994
Aykin
1995a
Aykin
2005
Ernst ve
Krishnamoorthy
Labbe vd.
2008
Costa vd.
2008
2009
2009
2010a
2010b
2010
2011
2012
Yıl
1994b
Randall
Contreras vd.
Randall vd.
Correia vd.
Correia vd
Lin ve Lee
Kratica vd.
Camargo ve
Miranda
Taghipourian vd.
Yazarlar
Campell
2000
Ebery vd.
2003
Sasaki ve
Fukushima
2004
Boland vd.
2005a
Marin
2007
Rodriguez vd.
Rodriguez-Martin
ve SalazarGonzalez
Gelareh ve
Pisinger
Tek Atamalı
1999
2012
Çok Atamalı
Atama Şekli
2008
2011
2013
Sender ve Clausen
Çalışmalar
İlk tamsayılı model
Doğrudan bağlantılara izin veren
yeni bir matematiksel model
Önceden belirlenen sayıda ADÜ’ye
doğrudan bağlantıya izin veren yeni
bir matematiksel model
Yeni matematiksel model, iki
sezgisel ve dal ve sınır algoritması
Dal ve sınır algoritması
Toplam maliyeti ve hizmet süresini
minimize eden iki amaçlı
matematiksel model
Karınca kolonisi optimizasyonu
Lagrange gevşetmesi
Metasezgisel algoritma
Karışık tamsayılı model
Tamsayılı model
Lagrange gevşetmesi
Karışık tamsayılı model
Genelleştirilmiş Benders ayrışım
algoritması
Bulanık karışık tamsayılı model
Çalışmalar
İlk doğrusal tamsayılı model
Yeni matematiksel model, bir
sezgisel ve dal ve sınır algoritması
Dal ve sınır algoritması, 1-durmalı
ADÜ yerleşim problemi için
matematiksel model
Önişlem prosedürü ve kısıt
sıkıştırma
Yeni matematiksel model ve alt ve
üst sınırları doğrusal programlama
gevşetmesiyle belirlendiği dal ve
sınır algoritmasına dayalı bir
sezgisel
Tavlama benzetimi
Karışık tamsayılı model (dal ve
kesme algoritması tabanlı)
Karışık tamsayılı model
Yeni sezgiseller ve Almanya
uygulaması
e. P-ADÜ Merkez Problemi Konusunda Literatür Araştırması
P-ADÜ merkez problemi, p-merkez problemine benzer ve minmax
tipinde bir problem çeşididir. Problemin ilk matematiksel modeli Campbell
(1994b), tarafından sunulmuştur. Campbell (1994b), çalışmasında p-ADÜ
merkez problemlerinin üç farklı tipini tanımlamıştır.
31
 Herhangi bir kaynak-varış çiftinin maksimum maliyetinin minimize
edilmesi.
 Herhangi bir tek bağlantıdaki (kaynaktan ADÜ’ye, ADÜ’den ADÜ’ye
ve ADÜ’den talep noktasına) akış için maksimum maliyetin minimize
edilmesi.
 Bir ADÜ ve bir kaynak-varış çifti arasındaki akışın maksimum
maliyetinin minimize edilmesi.
Campbell (1994b)’a göre, p-ADÜ merkez probleminin ilk tipi, kolay
bozulan ya da süreye duyarlı ürünler içeren ADÜ sistemleri için önemlidir. İkinci
tip problem için bir örnek ise, ADÜ yer seçimi için uygun olan ve ısıtma ve
soğutma gibi koruma ve işlem gerektiren ürünlerdir. Başka bir örnekte sürekli
bir servis sisteminde, zamana bağlı olan araç sürücüleridir. Üçüncü tip problem
için, ikinci tip problemler için verilen örneklere benzer tipteki fakat ADÜ-ADÜ
bağlantıları arasında bazı özel niteliklere sahip olanları örnek verilebilir.
Campbell (1994b), p-ADÜ merkez problemlerinin her üç tipinin tek ve çok
atamalı versiyonları için modeller sunmuştur.
Kara ve Tansel (2000), tek atamalı p-ADÜ merkez problemi için çeşitli
doğrusal modeller sunmuşlardır. Yazarlar Campbell (1994b)’in 1.Tip
probleminin (herhangi bir kaynak-varış çifti arasındaki maksimum uzaklık veya
mesafenin minimizasyonu) doğrusallaştırılması için 3 farklı yaklaşım ve bir
yeni matematiksel model sunmuştur. Yeni modelin CPLEX çözücü kullanılarak
yapılan çözümünde 3 farklı doğrusallaştırma yönteminden de üstün sonuçlar
elde edilmiştir. Yeni modelde n2 sayıda ikil olmak üzere, (n2 + 1) adet
değişken ve (n3+n2+n+1) adet doğrusal kısıt yer almaktadır. Ayrıca yazarlar
bu çalışmada problemin NP-zor olduğunu ispatlamıştır.
Ernst vd. (2002a), tek atamalı p-ADÜ merkez problemi için yeni bir
model geliştirmiştir. Yazarlar bu modelde rk adında yeni bir değişken
tanımlamış ve bu değişkeni ADÜ k ve ADÜ k’ya atanan düğümler arasındaki
maksimum toplama/dağıtma maliyeti olarak açıklamışlardır. Bu model (n2 )
sayıda ikil olmak üzere, (n2+n+1) sayıda değişken ve (3n2+n+1) sayıda
32
doğrusal kısıt içerir. Önerilen bu model, Kara ve Tansel (2000) tarafından
önerilen modele göre n sayıda fazla değişken içerse de, modeldeki doğrusal
kısıt sayısı daha azdır. CPLEX çözücü vasıtasıyla CAB ve AP veri seti
kullanılarak yapılan karşılaştırmalar neticesinde, Ernst vd. (2002a) tarafından
önerilen modelin, hesaplama zamanı açısından, Kara ve Tansel (2000)
tarafından önerilen modelden daha üstün olduğu görülmüştür.
Baumgartner (2003), Ernst vd. (2002a) tarafından önerilen modelin
çokyüzlü özelliklerini keşfetmiş ve dal ve kesme algoritması önermiştir.
Hamcher ve Meyer (2006), p-ADÜ merkez problemlerinin çözümü için,
ADÜ kapsama problemlerinin ikil arama ile çözümünü önermiştir.
Tek atamalı p-ADÜ merkez problemi için ilk sezgisel Pamuk ve Sepil
(2001), tarafından sunulmuştur. Yazarlar çalışmada kabul edilebilir çözüm
zamanı içerisinde yerleştirme-atama kararları üretmek için tek-değiştirme
(single-exchange) sezgiseli önermiş ve yerel optimum da kalma olasılığını
azaltmak için geliştirdikleri temel algoritma üzerine tabu araması algoritması
uygulamıştır.
Ernst vd. (2002a), ayrıca çok atamalı p-ADÜ merkez problemi üzerine
de çalışmıştır. Problemin NP-zor olduğunu ispatlamış ve 2 yeni model
sunmuşlardır. Ayrıca hem tek atamalı hem de çok atamalı P-ADÜ merkez
problemleri için birer sezgisel önermişlerdir. Çok atamalı versiyon için ayrıca,
Ernst ve Krishnamoorthy (1998b) tarafından çok atamalı P-ADÜ ortanca
problemi için geliştirilen algoritmaya çok benzer olan, en kısa yol tabanlı dal
sınır algoritması geliştirilmiştir.
Ernst vd. (2002b), ADÜ’lerin yerleri sabitken, tek atamalı p-ADÜ
merkez probleminin atama alt problemi üzerine çalışmışlardır. Bu problemin
NP-zorluğunu
ispat
etmişler
ve
problem
için
doğrusal
bir
model
geliştirmişlerdir. Ayrıca yazarlar “5” sezgisel algoritma önermişler ve bu
algoritmaların en kötü durumlardaki performanslarını analiz etmişlerdir.
33
Tablo-6’da p-ADÜ merkez problemleri ile ilgili günümüze kadar
yapılmış çalışmaların bir özeti sunulmuştur.
Tablo-6: p-ADÜ Merkez Problemi İçin Yapılan Çalışmalar
Yıl
Yazarlar
1994b
Campell
2000
Kara ve Tansel
2001
Kara ve Tansel
2001
Pamuk ve Sepil
2002a
Ernst vd.
2002b
Ernst vd.
2007
Yaman vd.
Yaklaşım
Farklı tip p-ADÜ merkez problemleri için ilk matematiksel
modeller
Tek atamalı p-ADÜ merkez problemi için çeşitli doğrusal
modeller ve problemin NP-zor olduğunun ispatlanması
Tek ve çok atamalı minimum toplam, minimaks ve
kapsama modelleri, tek atamalı minimaks probleminin NPzor olduğunun ispatlanması.
Tek-atamalı p-ADÜ merkez problemi için ilk sezgisel tekdeğiştirme sezgiseli üzerine tabu arama algoritması
Tek ve çok atamalı p-ADÜ merkez problemleri için yeni
modeller, birer yeni sezgisel ve dal ve sınır algoritması,
çok atamalı p-ADÜ merkez probleminin NP-zor olduğunun
ispatlanması.
Çok atamalı p-ADÜ merkez problemi atama alt problemi
için yeni model ve beş sezgisel, tek atamalı p-ADÜ
merkez problemi atama alt probleminin NP-zor olduğunun
ispatlanması.
Son nokta ADÜ yerleşim problemi
2006
Hamacher ve Meyer
İkil arama algoritması BS(HcoP)
2006
Kratica ve Stanimirovic
2007
Campbell vd.
2007
Juette vd.
2009
Gavriliouk
2009
Calik vd.
2009
Meyer vd.
2009
Ernst vd.
2009
Sim vd.
2012
Yaman ve Elloumi
Genetik algoritma
Kapasiteli ve kapasitesiz atama altproblemlerin her ikisi
için de yeni matematiksel model
Çok yüzlü analiz
Tek-atamalı p-ADÜ merkez problemi için toplama
(aggregation) tabanlı sezgisel
Tek-atamalı p-ADÜ merkez problemi için tabu arama
sezgiseli
Tek-atamalı p-ADÜ merkez problemi için iki aşamalı
algoritma (Dal ve sınır algoritması ile karınca kolonisi
optimizasyonu)
Tek ve çok atamalı p-ADÜ merkez problemleri için yeni
karışık tamsayılı modeller ve probleminin NP-zor
olduğunun ispatlanması.
İhtimal kısıtları dahil edilmiş stokastik tek atamalı p-ADÜ
merkez problemi
Karışık tamsayılı model
2013
Yang vd.
Yeni bir bulanık model
2013
Bashiri vd.
Bulanık problem için genetik algoritma
2014
Yang vd.
Bulanık problem için doğrusal olmayan model
f. ADÜ Kapsama Problemi Konusunda Literatür Araştırması
Kapsama problemlerinde, tüm talep noktalarını belirli bir hizmet
seviyesinde kapsayacak en az sayıdaki hizmet verecek tesisin belirlenmesi
amaçlanmaktadır. P-merkez ADÜ problemindeki gibi, Campell (1994b),
ADÜ’ler için üç kapsama kriteri tanımlamıştır:
34
 k ve m yolu üzerinden i’den j’ye maliyet, belirlenen bir değeri
geçmezse,
 k ve m yolu üzerinden i’den j’ye her bağlantı için maliyet belirlenen
bir değeri geçmezse,
 Her başlangıç-ana üs ve ana üs-varış yeri bağlantısı ayrık
belirlenmiş değerlerle karşılaştırılırsa,
başlangıç-varış çifti (i,j), m ve k ana üsleri tarafından kapsanır.
ADÜ küme kapsama problemi, ADÜ açma maliyetini minimize etmek
maksadıyla, ADÜ’leri tüm düğümleri kapsayacak şekilde yerleştirme
problemidir. Maksimum ADÜ kapsama problemi ise, yerleştirmek için verilen
belirli sayıda ADÜ ile maksimum sayıda talep noktasını kapsama problemidir
(Alumur ve Kara, 2008). Campbell (1994b), her iki tip problem için ilk karışık
tamsayılı modelleri sunmuştur.
Kara ve Tansel (2003), tek atamalı ADÜ küme kapsama problemini
çalışmış ve problemin NP-zor olduğunu ispatlamıştır. Yazarlar yeni bir model
sunmanın yanında, orijinal karesel model için üç farklı doğrusallaştırma
yapmış
ve
karşılaştırmışlardır.
Ayrıca
geliştirdikleri
yeni
modelin
performansının, daha önceki tüm doğrusal modellerden daha iyi olduğunu
belirtmişlerdir.
Ernst vd. (2005), tek atamalı ADÜ küme kapsama problemi için yeni
bir model sunmuşlardır. Bu model Ernst vd. (2002a) tarafından P-ADÜ merkez
problemi için sunulan modele benzemektedir. Yazarlar, yeni modeli Kara ve
Tansel (2003) tarafından ortaya konulan modelle karşılaştırabilmek için Kara
ve Tansel (2003)’in modelinde yer alan kısıtları, toplanmış halleriyle yer
değiştirmiş ve Kara ve Tansel (2003)’in modelini güçlendirmişlerdir. Daha
sonra yapılan karşılaştırmada Ernst vd. (2005) tarafından sunulan modelin,
Kara ve Tansel (2003)’in güçlendirilmiş modelinden işlem zamanı açısından
daha iyi performans sergilediği belirlenmiştir.
35
Ayrıca, Ernst vd. (2005), çok atamalı ADÜ küme kapsama problemi
üzerine de çalışmışlar ve problem için iki yeni model ve kesin sayım yöntemi
önermişlerdir.
Çalık vd. (2008), tek atamalı ADÜ kapsama problemi üzerine tamsayılı
bir model önermiştir. Çalışmada ADÜ’leri yerleştirmek ve ADÜ’ler arasındaki
bağlantıları kurmak amaçlanmıştır. Aynı çalışmada yazarlar birde tabu arama
algoritması önermişlerdir.
Wagner (2008), tek ve çok atamalı ADÜ kapsama problemlerinin her
ikisi için de yeni modeller önermiştir. Bu modeller önişlem prosedürüne tabi
tutularak, Kara ve Tansel (2003)’in modelinden daha az kısıt ve değişken
sayısı elde edilmiştir. Daha sonra bazı kısıtlar toplanarak modelin geliştirilmesi
sağlanmıştır.
Tablo-7’de ADÜ kapsama problemleri ile ilgili günümüze kadar
yapılmış çalışmaların bir özeti sunulmuştur.
Tablo-7: ADÜ Kapsama Problemi İçin Yapılan Çalışmalar
Yıl
Yazarlar
Yaklaşım
1994b
Campell
ADÜ kapsama probleminin değişik yapıları
2003
Kara ve Tansel
Tek atamalı ADÜ probleminin çeşitli doğrusal modelleri
2005
Ernst vd.
Kapsama yarıçapı β ile yeni model
2006
Hamacher ve Meyer
2007
Tan ve Kara
2008
Wagner
2008b
Alumur ve Kara
2008
Qu ve Weng
2009
Çalık vd.
2011
Mohammadi vd.
2011
Karimi ve Bashiri
2013
Mohammadi vd.
Tek ve çok atamalı ADÜ problemleri için modeller
Kargo dağıtım sistemleri için en son varılan ADÜ kapsama
modeli
Tek ve çok atamalı ADÜ kapsama probleminin her ikisi
için yeni matematiksel modeller
Türkiye kargo dağıtım sistemi için ADÜ kapsama modeli
Kapasite sınırı olmayan çok atamalı ADÜ kapsama
problemi üzerinde servis akışlarını maksimum yapacak
optimal p sayısını bulan maksimum kapsama modeli
Kapasite sınırı olmayan tek atamalı ADÜ kapsama
problemi için tabu arama sezgiseli
Tek atamalı ADÜ kapsama problemi için genetik algoritma
Kapasite sınırı olmayan tek ve çok atamalı ADÜ kapsama
problemi için sezgisel algoritmalar
Belirsizli koşullarında stokastik, çok amaçlı, çok modlu
ulaştırma için ADÜ kapsama modeli
36
İKİNCİ BÖLÜM
ADÜ YER SEÇİM PROBLEMLERİNİN TEMEL MATEMATİKSEL
MODELLERİ
1. TEK ADÜ YER SEÇİM PROBLEMİ
Tek ana dağıtım üssü yer seçim problemi ile ilgili ilk matematiksel
model O’Kelly (1987) tarafından sunulmuştur ve bu model yalnızca bir ADÜ
içerir. Matematiksel modelin,
Varsayımları;

Amaç fonksiyonu tipi: Minimum toplam,

Çözüm uzayı: Kesikli ve sonlu,

ADÜ sayısı “1”,

Bütün düğümler birbirleri ile tam bağlı,

ADÜ olarak seçilmeyen düğümlerin yalnızca bir ADÜ’ye atanabildiği,

Seçilecek ADÜ sayısı bilinen (eksojen),

ADÜ kuruluş maliyeti olmayan,

ADÜ kapasite kısıtı olmayan,

Tüm karar değişkenleri 0,1 tamsayı şeklinde,
Girdileri;
wij : i ve j düğümleri arasındaki akış miktarı,
cij : i ve j düğümleri arasındaki bir birimlik akış maliyeti şeklinde,
Karar Değişkenleri;
xj : j düğümünün ADÜ olup olmadığı (0,1 tamsayı),
yij : i düğümünün j ADÜ’süne atanıp atanmadığı (0,1 tamsayı) şeklinde
tanımlanmıştır.
37
Bu tanımlamalara göre tek ana dağıtım üssü yer seçim problemi ile
ilgili matematiksel model aşağıda gösterildiği gibidir.
MODEL 1
Min∑i ∑j ∑k wik (cij + cjk )yij ykj
s.t. ∑j xj = 1
yij − xj ≤ 0
∀i, j,
xj = 0,1
∀j,
yij = 0,1
∀i, j,
Bu model, amaç fonksiyonu karesel olduğundan, doğrusal olmayan bir
yapıya sahiptir. Modelde amaç fonksiyonu, toplam taşıma maliyetini minimize
etmektedir. İlk kısıt sadece bir ADÜ seçildiğini, ikinci kısıt ise i düğümünün,
yalnızca, j düğümünün ADÜ olması durumunda j düğümüne atanabileceğini,
son iki kısıt ise, karar değişkenlerinin 0,1 tamsayı olduğunu ifade etmektedir.
2. P-ADÜ MEDYAN PROBLEMİ
a. Tek Atamalı p-ADÜ Medyan Problemi
Tek atamalı p-ADÜ Medyan problemi için ilk matematiksel model
O’Kelly (1987) tarafından geliştirilmiştir. Matematiksel modelin,
Varsayımları;

Amaç fonksiyon tipi: Minimum toplam,

Çözüm uzayı: Kesikli ve sonlu,

Tüm düğümler birbirleriyle ile tam bağlı,

Seçilecek ADÜ sayısı bilinen (eksojen),

ADÜ olmayan iki düğüm arasında, ADÜ kullanmadan direkt akış olmayan,

ADÜ olarak seçilmeyen düğümlerin yalnızca bir ADÜ’ye atanabildiği,

ADÜ kuruluş maliyeti olmayan,

ADÜ kapasite kısıtı olmayan,

Tüm karar değişkenleri 0,1 tamsayı şeklinde,
38
Girdileri;
Modelin girdileri MODEL1’ de tanımlandığı şekildedir. Bu girdilerin dışında,
α : Ölçek ekonomisinden yararlanmak maksadıyla, ADÜ’ler arasındaki
akışlarda kullanılan maliyet azaltma faktörü (0 ≤ α ≤ 1),
p : Seçilecek ADÜ sayısı şeklinde,
Karar Değişkenleri;
xik : i düğümünün k ADÜ’süne atanıp atanmadığı (0,1 tamsayı),
xkk : k düğümünün ADÜ olup olmadığı (0,1 tamsayı) şeklinde tanımlanmıştır.
Tek atamalı p-ADÜ Medyan problemi için ilk matematiksel modelin
genel gösterimi aşağıdaki gibidir.
MODEL 2
Min ∑i ∑k wij (∑k xik cik + ∑m xjm cjm + α ∑k ∑m xik xjm ckm )
(1)
s.t. (n-p+1)xkk − ∑i xik ≥ 0
∀k,
(2)
∑k xik = 1
∀i,
(3)
∑k xkk = p ,
xik ∊ {0,1}
(4)
∀i, k,
(5)
Bu model, amaç fonksiyonu karesel olduğundan doğrusal olmayan bir
yapıya sahiptir. Amaç fonksiyonu (1), toplam taşıma maliyetini minimize eder.
(3) ve (5) kısıtları, her düğümün sadece bir ADÜ’ye atanmasını, (2) kısıtı,
atamaların sadece ADÜ’lere yapılmasını sağlar. ADÜ sayısı, (4) kısıtı ile
sınırlandırılmıştır.
Ayrıca, atamaların sadece ADÜ’lere yapılmasını sağlayan (2) kısıtının
yerine aşağıdaki (6) kısıtı yazılabilir (Alumur ve Kara, 2008).
xij ≤ xjj
∀i, j,
39
(6)
Bu problem tipi için ilk doğrusal tamsayılı model ise, Campbell (1994b)
tarafından geliştirilmiştir. Campbell’in modelinde (n2 + n) sayıda ikil olmak
üzere toplam (n4 + n2 + n) değişken ve (n4 + 2n2 + n + 1) sayıda doğrusal
kısıt yer almaktadır.
Skorin-Kapov vd. (1996), Campbell (1994b)’nin modeline tamsayı
gevşetmesi uygulandığında çok sayıda tam sayı olmayan sonuçlar elde
edildiğini belitmişler ve bunu giderebilmek için tek atamalı p-ADÜ medyan
problemi için yeni bir karışık tamsayılı bir model önermişlerdir. Matematiksel
modelin,
Varsayımları;
Modelin varsayımları, karar değişkenlerinin 0,1 tamsayı olması zorunluluğu
dışında, MODEL 2’de tanımlandığı şekilde,
Girdileri;
cijkm = i-j-k-m arasındaki birim taşıma maliyeti olmak üzere,
cijkm = cik + cmj + αckm
diğer girdiler MODEL 2’ de tanımlandığı şekilde,
Karar Değişkenleri;
xijkm = i noktasından j noktasına gitmekte olan akışın k ve m ADÜ’lerini
kullanım oranı,
Diğer karar değişkenleri MODEL 2’de tanımlandığı şekildedir.
Bu tanımlamalara göre Skorin-Kapov vd. (1996) tarafından önerilen
matematiksel model aşağıdaki gibidir.
MODEL 3
Min ∑i ∑j ∑k ∑m wij xijkm cijkm
(7)
s.t. (3) - (6)
∑m xijkm = xik
∀i, j, k,
40
(8)
∑k xijkm = xjm
∀i, j, m,
xijkm ≥ 0
∀i, j, k, m,
(9)
(10)
Modelde amaç fonksiyonu (7), toplam taşıma maliyetini minimize eder.
(8) ve (9) kısıtları ile tüm akışlar ADÜ’ler üzerinden gönderilir. Bu modelde,
(n2 ) ikil değişken, (n4 + n2 ) değişken, (2n3 + n2 + n + 1) doğrusal kısıt ortaya
çıkmıştır.
Ernst ve Krishnamoorthy (1996), daha geniş ve karmaşık problemlerin
çözümü için daha az sayıda değişken ve kısıtın yer aldığı farklı bir doğrusal
tamsayılı model geliştirmiştir. Matematiksel modelin,
Varsayımları;
Modelin varsayımları, MODEL 3’te tanımlandığı şekilde,
Girdileri;
χ : toplama için maliyet azaltma faktörü (ana dağıtım üssü olmayan düğümden
ana dağıtım üssüne),
α: transfer için maliyet azaltma faktörü (ana dağıtım üssünden ana dağıtım
üssüne),
 : dağıtım için maliyet azaltma faktörü (ana dağıtım üssünden ana dağıtım
üssü olmayan düğüme),
Oi = ∑j Wij , i düğümünden çıkan toplam akış miktarı,
Di = ∑i Wij , i düğümüne gelen toplam akış miktarı,
Diğer girdiler MODEL 1’de tanımlandığı şekilde,
Karar Değişkenleri;
i
Ykl
: k ve l ana dağıtım üsleri arasında rotalanan i ürünün toplam akış miktarı,
Diğer karar değişkenleri MODEL 2 ‘de tanımlandığı şekildedir.
41
Bu tanımlamalara göre Ernst ve Krishnamoorthy (1996) tarafından
önerilen matematiksel model aşağıdaki gibidir.
MODEL 4
i
Min ∑i ∑k Cik X ik (χOi + δDi ) + ∑i ∑k ∑l α Ckl Ykl
(11)
s.t. (3) – (6),
i
i
∑l Ykl
− ∑l Ylk
= Oi Xik − ∑j Wij Xjk
∀i, k,
(12)
i
Ykl
≥0
∀i, k, l,
(13)
Amaç fonksiyonu (11) toplam taşıma maliyetini minimize eder. (12)
kısıtı akış dengeleme kısıtıdır. Model (n2 ) ikil olmak üzere, (n3 + n2 ) değişken
ve (2n2 + n + 1) doğrusal kısıt ihtiva eder.
b. Çok Atamalı p-ADÜ Medyan Problemi
Çok atamalı p-ADÜ medyan probleminin ilk doğrusal tamsayılı
modeli Campbell (1992) tarafından geliştirilmiştir. Matematiksel modelin,
Varsayımları;
Modelin
varsayımları
MODEL
3’ün
varsayımları
ile
büyük
ölçüde
örtüşmektedir. Fakat bu model çok atamalı yapıya sahip olduğundan, ADÜ
olmayan düğümler birden fazla ADÜ’ye atanabilir (en az bir ADÜ) ve karar
değişenleri karışık tamsayılıdır.
Girdileri;
Modelin girdileri, MODEL 3’te tanımlandığı şekilde,
Karar Değişkenleri;
Karar değişkenleri MODEL 2 ve MODEL 3’te tanımlandığı şekildedir.
Bu tanımlamalara göre çok atamalı p-ADÜ medyan problemi için
önerilen matematiksel model aşağıdaki gibidir.
42
MODEL 5
Min (7)
s.t. (4), (5) ve (10)
∑k ∑m Xijkm = 1
∀i, j,
(14)
Xijkm ≤ Xkk
∀i, j, k, m,
(15)
Xijkm ≤ Xmm
∀i, j, k, m,
(16)
Campbell (1992), daha önce açıklanmış olan (4),(5),(10) kısıtları ve (7)
amaç fonksiyonuna yukarıdaki (14), (15), (16) kısıtlarını ekleyerek modeli
oluşturmuştur. (14) kısıtı akışların bir ADÜ çifti üzerinden gönderilmesini, (15)
ve (16) kısıtları akışların ADÜ’ler üzerinden gönderilmesini sağlar. Bu model,
0-1 karma tamsayılı doğrusal bir modeldir. Modelde, (n4 + n) sayıda değişken
ve (2n4 + n2 + 1) sayıda kısıt vardır.
Ernst ve Krishnamoorthy (1998a), daha önce kendilerinin Ernst ve
Krishnamoorthy (1996) geliştirmiş olduğu tek atamalı modeli temel alarak, çok
atamalı p-ADÜ medyan problemi için yeni bir model önermişlerdir.
Matematiksel modelin,
Varsayımları;
Modelin varsayımları, MODEL 5’in varsayımları ile aynı olup, karar
değişkenleri tamsayı,
Girdileri;
Modelin girdileri, MODEL 1’de tanımlandığı şekilde,
Karar Değişkenleri;
zik : i kaynak noktasından çıkıp k ADÜ’süne giden akış miktarı,
xlji : i kaynak noktasından çıkan ve l ADÜ’sü üzerinden j düğümüne giden akış
miktarı,
43
i
Ykl
: i kaynak noktasından çıkan, k ve l ADÜ lerini kullanarak j ye giden akış
miktarı,
Hk : k düğümü ADÜ olarak belirlenmişse “1”,diğer durumlarda “0” olan ikil
değişken şeklindedir.
Bu tanımlamalara göre çok atamalı p-ADÜ medyan problemi için Ernst
ve Krishnamoorthy (1998a) tarafından önerilen matematiksel model aşağıdaki
gibidir.
MODEL 6
i
Min∑i[ ∑k χCik Zik + ∑k ∑l αCkl Ykl
+ ∑l ∑j Clj Xlji ]
(17)
s.t. ∑k Hk = p
(18)
∑k Zik = Oi
∀i,
(19)
∑l Xlji = Wij
∀i, j,
(20)
i
i
i
∑l Ykl
− ∑j Xkj
− ∑l Ylk
− Zik = 0
∀i, k,
(21)
Zik ≤ Oi Hk
∀i, k,
(22)
∑i Xlji ≤ Dj Hi
∀l, j,
(23)
Hk ∊ {0,1}
∀i, k,
(24)
i
Ykl
, Xlji , Zik ≥ 0
∀i, j, k, l,
(25)
Amaç fonksiyonu (17) toplam taşıma maliyetini minimize eder. (18)
kısıtı, ADÜ sayısını p sayısı ile kısıtlar. (19) ve (22) kısıtları, kaynak
noktasından çıkan tüm akışların ilk olarak ADÜ lere gitmesini sağlar. (20) ve
(23) kısıtları, akışların ADÜ’lerden varış noktasına varmasını sağlar. (21) kısıtı,
akış dengeleme kısıtıdır ve akış kaybını engeller. Bu model, n’ler ikil değişken
olmak üzere (2n3 + n2 + n) değişken ve (4n2 + n + 1) doğrusal kısıt içerir.
44
3. SABİT MALİYETLİ ADÜ YER SEÇİM PROBLEMİ
Sabit maliyetli ADÜ yer seçim problemleri “kapasite sınırı olan” ve
“kapasite sınırı olmayan” ADÜ yer seçim problemleri olmak üzere iki ayrı
başlıkta ele alınmaktadır. Aşağıdaki bölümde kapasite sınırı olmayan ADÜ yer
seçim problemleri, (UHLP: Uncapacitated Hub Location Problem) ve kapasite
sınırı olan ADÜ yer seçim problemleri (CHLP: Capacitated Hub Location
Problem) ile ilgili temel matematiksel modeller incelenmiştir.
p-ADÜ medyan problemine benzer şekilde bu problem tipleri için de
tek ve çok atamalı yapılar söz konusudur.
a. Kapasite Sınırı Olmayan ADÜ Yer Seçim Problemi
O’Kelly (1992a), ADÜ sayısını karar değişkeni yaparak, sabit
maliyetli tek atamalı ADÜ yer seçim problemini tanımlamıştır. Matematiksel
modelin,
Varsayımları;

Amaç fonksiyon tipi: Minimum toplam,

Çözüm uzayı: Kesikli ve sonlu,

Tüm ADÜ’ler birbirleriyle tam bağlı,

ADÜ olarak seçilmeyen düğümlerin yalnızca bir ADÜ’ye atanabildiği,

Seçilecek ADÜ sayısı model tarafından belirlenen (endojen),

ADÜ olmayan iki düğüm arasında, ADÜ kullanmadan direkt akış olmayan,

ADÜ kuruluş maliyeti olan,

ADÜ kapasite kısıtı olmayan,

Tüm karar değişkenleri 0,1 tamsayı şeklinde,
Girdileri;
Oi = ∑j Wij , i düğümünden çıkan toplam akış miktarı,
Di = ∑i Wij , i düğümüne gelen toplam akış miktarı,
45
Fj : j düğümünde ADÜ açmanın sabit maliyeti,
α: transfer için maliyet azaltma faktörü (ana dağıtım üssünden ana dağıtım
üssüne),
Modelin diğer girdileri, MODEL 1’de tanımlandığı şekilde,
Karar Değişkenleri;
Karar değişkenleri, MODEL 1’de tanımlandığı şekildedir. Bu tanımlamalara
göre matematiksel model aşağıdaki gibidir.
MODEL 7
Min ∑i ∑k Xik Cik (Oi + Di ) + ∑j ∑m Xjm ∑i ∑k Xik (αWij Ckm ) + ∑j Xjj Fj
(26)
s.t. (3), (5) ve (6),
Bu model, amaç fonksiyonu karesel olduğundan, doğrusal olmayan bir
yapıya sahiptir. Amaç fonksiyonunun (26) bu şekilde düzenlenmesiyle j
düğümünün ADÜ olması durumunda, ADÜ açma maliyeti de dikkate alınmış
olur. Çalışmalarda ADÜ açma maliyeti “sabit maliyet (fixed cost)” olarak yer
almaktadır.
Çalışmanın bundan sonraki bölümünde kapasite sınırı olmayan çok
atamalı ADÜ yer seçim problemi için (UMAHLP: Uncapacitated Multiple
Allocation Hub Location Problem) temel matematiksel model incelenmiştir.
Kapasite sınırı olmayan çok atamalı ADÜ yer seçim problemleri ile ilgili
ilk doğrusal model Campbell (1994b) tarafından sunulmuştur. Matematiksel
modelin,
Varsayımları;
Modelin varsayımları, MODEL 7’nin varsayımları ile aynı olup, karar
değişkenleri karışık tamsayı ve ADÜ olmayan düğümler birden fazla ADÜ’ye
atanabilek (en az bir ADÜ) şekilde,
46
Girdileri;
cijkm = i-j-k-m arasındaki birim taşıma maliyeti olmak üzere,
cijkm = cik + cmj + αckm
Fj : k düğümünde ADÜ açmanın sabit maliyeti,
wij : i ve j düğümleri arasındaki akış miktarı şeklinde,
Karar Değişkenleri;
Modelin karar değişkenleri, MODEL 3’te tanımlandığı şekildedir.
Bu tanımlamalara göre Campbell (1994b) tarafından önerilen
matematiksel model aşağıdaki gibidir. Modelin kısıtları daha önce açıklandığı
şekildedir.
MODEL 8
Min∑i ∑j ∑k ∑m Wij Xijkm Cijkm + ∑k Fk X kk
(27)
s.t. (5), (14)-(16),
0 ≤ Xijkm ≤ 1
∀i, j, k, m,
(28)
b. Kapasite Sınırı Olan ADÜ Yer Seçim Problemi
Ernst ve Krishnamoorthy (1999), kapasite kısıtlı, tek atamalı ADÜ
yer seçim problemi için iki yeni model önermişlerdir. Bu modeller, daha önce
p-ADÜ medyan problemi için geliştirilmiş olan karışık tamsayılı modelin
modifiye edilmiş halleridir. Bu modellerden, kısıt ve değişken sayısı açısından
en iyisi aşağıda sunulmuştur. Matematiksel modelin,
Varsayımları;

Amaç fonksiyon tipi: Minimum toplam,

Çözüm uzayı: Kesikli ve sonlu,

Tüm ADÜ’ler birbirleriyle tam bağlı,
47

ADÜ olarak seçilmeyen düğümlerin yalnızca bir ADÜ’ye atanabildiği,

Seçilecek ADÜ sayısı model tarafından belirlenen (endojen),

ADÜ olmayan iki düğüm arasında, ADÜ kullanmadan direkt akış olmayan,

ADÜ kuruluş maliyeti olan,

ADÜ kapasite kısıtı olan,

Tüm karar değişkenleri tamsayı şeklinde,
Girdileri;
Γk : k düğümünün kapasitesi,
Diğer girdiler, MODEL 4’ te tanımlandığı şekilde,
Karar Değişkenleri;
i
Ykl
: k ve l ana dağıtım üsleri arasında rotalanan i ürünün toplam akış miktarı,
Diğer karar değişkenleri MODEL 2’de tanımlandığı şekildedir.
Bu tanımlamalara göre Ernst ve Krishnamoorthy (1999) tarafından
önerilen matematiksel model aşağıdaki gibidir.
MODEL 9
i
Min∑i ∑k Cik X ik (χOi + δDi ) + ∑i ∑k ∑l αCkl Ykl
+ ∑k Fk Xkk
(29)
s.t. (3), (5), (6), (12), (13)
∑i Oi Xik ≤ Γk Xkk ∀k,
(30)
(30) kısıtı kapasite kısıtıdır. Kapasite kısıtı sadece ADÜ’lere ADÜ
olmayan noktalardan direkt gelişler için uygulanmıştır. Kapasite açıklaması
posta servis uygulamalarında, ADÜ’lerin dağıtım kapasitelerini göstermek için
sıkça kullanılmaktadır.
Çalışmanın bundan sonraki bölümünde kapasite sınırı olan çok
atamalı ADÜ yer seçim problemleri (CMAHLP: Capacitated Multiple Allocation
Hub Location Problem) ile ilgili matematiksel modeller incelenmiştir.
48
Ebery vd. (2000), kapasite kısıtlı ADÜ yer seçim problemini, çok
atamalı olarak düşünmüşlerdir. Yazarlar çalışmada kapasite kısıtlı çok atamalı
ADÜ yer seçim problemini posta dağıtım ağı için tasarlamışlar, seçilecek olan
ADÜ’lerin kapasitesini, yalnızca postaları toplama aşamasının etkileyeceğini
söylemişlerdir. Çalışmada iki farklı model sunulmuştur. Birinci matematiksel
modelin,
Varsayımları;

Amaç fonksiyon tipi: Minimum toplam,

Çözüm uzayı: Kesikli ve sonlu,

Tüm ADÜ’ler birbirleriyle tam bağlı,

ADÜ olmayan düğümlerin birden fazla ADÜ’ye (en az bir ADÜ) atanabildiği,

Seçilecek ADÜ sayısı model tarafından belirlenen (endojen),

ADÜ olmayan iki düğüm arasında, ADÜ kullanmadan direkt akış olmayan,

ADÜ kuruluş maliyeti olan,

ADÜ kapasite kısıtı olan,

Tüm karar değişkenleri tamsayı şeklinde,
Girdileri;
cij : i düğümünden j düğümüne bir birimlik akış maliyeti,
wij : i düğümünden j düğümüne akış miktarı,
Fk : k ADÜ’sünün sabit kuruluş maliyeti,
Γ :k ADÜ’sünün kapasitesi şeklinde,
Karar Değişkenleri;
zik : i düğümünden, k ADÜ’süne akış miktarı,
i
Ykl
: i düğümünden çıkıp, k ve l ADÜ’lerini vasıtasıyla giden akış miktarı,
X lji : i düğümünden çıkıp l ADÜ’sü vasıtasıyla j düğümüne giden akış miktarı,
Hk : k düğümü ADÜ olarak seçildiyse “1”, diğer durumlarda “0” değerini alan ikil
değişken şeklindedir.
Bu tanımlamalara göre matematiksel model aşağıdaki gibidir.
49
MODEL 10
i
Min∑i[χ ∑k Cik Zik + α ∑k ∑l Ckl Ykl
+ δ ∑l ∑j Clj Xlji ] + ∑k Fk Hk
(31)
s.t.∑k Zik = ∑j Wij
∀i,
(32)
∑l Xlji = Wij
∀i, j,
(33)
∑i Zik ≤ Γk Hk
∀k,
(34)
i
i
i
∑l Ykl
+ ∑j Xkj
− ∑l Ylk
− Zik = 0 ∀i, k,
(35)
Zik ≤ ∑j Wij Hk
∀i, k,
(36)
∑i Xlji ≤ ∑i Wij Hl
∀l, j,
(37)
i
Xlji , Ykl
, Zik ≥ 0, Hk ∊ {0,1}
∀i, j, k, l
(38)
Modelde amaç fonksiyonu (31), toplam taşıma maliyetini minimize
ederken, seçilen ADÜ’lerin kuruluş maliyetlerini de hesaplamaya katar. (32)
kısıtı, i düğümünden çıkan tüm akışın k ADÜ’süne gitmesini sağlar. (33) kısıtı,
i den çıkan ve j ye gitmesi gereken her akışın j ye gitmesini sağlar. (34) kısıtı,
i den çıkan ve k ADÜ’süne giden toplam akışın, k ADÜ’nün kapasitesini
geçmemesini sağlar. Bu kısıtta ADÜ’lerin kapasitesini yalnızca ADÜ olarak
seçilmeyen düğümlerden gelen akışlar etkiler. ADÜ’lerden gelen akışlar k
ADÜ’sünün kapasitesini etkilemez. (35) kısıtı, akış dengeleme kısıtıdır.(36),
(37) kısıtları, akışların ADÜ’ler vasıtasıyla gitmesini sağlar. Bu model (n3 )
değişkene sahiptir. İkinci matematiksel modelin,
Varsayımları;
Modelin varsayımları, MODEL 10 ile aynı şekilde,
Girdileri;
Modelin girdileri, MODEL 10 ile aynı şekilde,
Karar Değişkenleri;
Modelin karar değişkenleri, MODEL 10 ile aynıdır fakat Zik karar değişkeni
olarak kullanmamıştır.
50
Bu tanımlamalara göre matematiksel model aşağıdaki gibidir.
MODEL 11
i
Min∑i ∑k ∑l(χ Cik + αCkl )Ykl
+ ∑i ∑j ∑l δClj Xlji + ∑k Fk Hk
(39)
s.t.∑l X lji = Wij
∀i, j,
(40)
i
∑i ∑l Ykl
≤ Γk Hk
∀k,
(41)
i
∑i ∑k Ykl
≤ ∑i ∑j Wij Hl
∀l,
(42)
i
∑k Ykl
= ∑j Xlji
∀i, l,
(43)
i
Xlji , Ykl
≥ 0,
∀i, j, k, l
(44)
Hk ∊ {0,1}
Modelde
(2n3 + n)
adet
değişken
ve
(2n2 + 2n)
adet
kısıt
bulunmaktadır. Bu model MODEL 10’a göre, daha az kısıta (yaklaşık yarısı
kadar) sahiptir.
Marin (2005a), çok atamalı, kapasite kısıtlı ADÜ yer seçim problemleri
için, Ebery vd. (2000) tarafından geliştirilen model ile aynı fikre dayanarak, yeni
bir model önermişlerdir. Matematiksel modelin,
Varsayımları;

Amaç fonksiyon tipi: Minimum toplam,

Çözüm uzayı: Kesikli ve sonlu,

Tüm ADÜ’ler birbirleriyle tam bağlı,

ADÜ olmayan düğümlerin birden fazla ADÜ’ye (en az bir ADÜ) atanabildiği,

Seçilecek ADÜ sayısı model tarafından belirlenen (endojen),

ADÜ olmayan iki düğüm arasında, ADÜ kullanmadan direkt akış olmayan,

ADÜ kuruluş maliyeti olan,

ADÜ kapasite kısıtı olan,

Tüm karar değişkenleri tamsayı,

Düğümler arasındaki mesafe, zaman vb. girdiler arasında üçgensel
eşitsizliğin var olma durumu gevşetilmiş şekilde,
51
Girdileri;
Modelin girdileri, MODEL 10 ile aynı şekilde,
Karar Değişkenleri;
amj : m düğümünün ADÜ, j düğümünün ADÜ olmadığı durumda, m
düğümünden j düğümüne giden akış miktarı,
bkmj : k ve m düğümlerinin ADÜ, j düğümünün ADÜ olmadığı durumda, k ve m
ADÜ’lerini kullanıp j düğümüne giden akış miktarı,
cikj : k düğümünün ADÜ, i ve j düğümlerinin ADÜ olmadığı durumda i
düğümünden çıkıp k ADÜ’sünü kullanarak j düğümüne giden akış miktarı,
Yk : k düğümünün ADÜ olduğu durumda “1”, diğer durumlarda “0” değerini alan
ikil değişken,
Fk : k ADÜ’ sünün sabit kuruluş maliyeti şeklindedir.
Bu
tanımlamalara
göre
Marin
(2005a)
tarafından
önerilen
matematiksel model aşağıdaki gibidir.
MODEL 12
Min∑m ∑j Ɣdmj amj + ∑k ∑m ∑j αdkm bkmj + ∑i ∑k ∑j βdik cikj + ∑k Fk Yk
s.t. ∑m amj + ∑m bmjj + ∑m cmjj = Dj
∀j,
(45)
aij + ∑k bikj + ∑k cikj = Wij + ∑k bkij + ∑k ckij
∀i, ∀j ≠ i,
(46)
∑k bkmj + ∑k ckmj ≤ (Dj − Wmj )Ym
∀j, ∀m ≠ j,
(47)
∑k bkjj + ∑k ckjj = Dj Yj
∀j,
(48)
cikj ≤ Wij Yk
∀i, j, k,
(49)
∑k cikj = Wij (1 − Yi )
∀i, j,
(50)
∑m bkmj ≤ Wkj + ∑i cikj
∀k, j,
(51)
∑i ∑j cikj ≤ Γk Yk
∀k,
(52)
bjmj = 0
∀j, ∀m ≠ j,
(53)
bkkj = 0
∀j, ∀k ≠ j,
(54)
52
ckkj = 0
∀j, k,
(55)
ajj = 0
∀j,
(56)
Yk ∊ {0,1}
∀k,
bkmj , cikj , amj ≥ 0
∀i, j, k, m,
Modelde (45) kısıtı, j düğümünün talebinin karşılandığını garanti eder.
(46) kısıtı, akış dengeleme kısıtıdır. (47) kısıtı, sadece m düğümünün ADÜ
olduğu durumda bkmj değişkeninin değer alabilmesini sağlar. (48) kısıtı,
sadece j düğümünün ADÜ olması durumunda bkjj değişkeninin değer
alabilmesini sağlar. (49) kısıtı, sadece k düğümünün ADÜ olması durumunda
cjkj değişkeninin değer alabilmesini sağlar. (50) kısıtı, i düğümünün ADÜ
olması durumunda cjkj değişkeninin değer alamamasını yani “0” olmasını
sağlar. (51) kısıtı, akışların ikiden fazla ADÜ gezmesini engeller. (52) kısıtı,
kapasite kısıtıdır. Fakat bu kısıtta ADÜ olarak seçilen düğümlerin kapasitesini
yalnızca ADÜ olmayan düğümlerden gelen akışlar etkiler.(53), (54), (55) ve
(56) kısıtları modelde değer almaması istenen gereksiz değişkenler için
yazılmış olan kısıtlardır.
4. P-ADÜ MERKEZ PROBLEMİ
P-ADÜ merkez problemi, p-merkez problemine benzer ve minmax
tipinde bir problem çeşididir. Problemin ilk matematiksel modeli Campbell
(1994b), tarafından sunulmuştur. Matematiksel modelin,
Varsayımları;

Amaç fonksiyon tipi: Maksimumun minimumu,

Çözüm uzayı: Kesikli ve sonlu,

Tüm ADÜ’ler birbirleriyle tam bağlı,

Seçilecek ADÜ sayısı model tarafından belirlenen (endojen),

ADÜ olmayan iki düğüm arasında, ADÜ kullanmadan direkt akış olmayan,

ADÜ kuruluş maliyeti olmayan,
53

ADÜ kapasite kısıtı olmayan,

Karar değişkenleri karışık tamsayı tamsayı şeklinde,
Girdileri;
α : Ölçek ekonomisinden yararlanmak maksadıyla, ADÜ’ler arasındaki
akışlarda kullanılan maliyet azaltma faktörü (0 ≤ α ≤ 1),
p : Seçilecek ADÜ sayısı,
cijkm : i-j-k-m arasındaki birim taşıma maliyeti olmak üzere,
cijkm = cik + cmj + αckm
wij : i ve j düğümleri arasındaki akış miktarı şeklinde,
Karar Değişkenleri;
zijkm : i düğümünden j düğümüne giden ve k, m aday ADÜ’lerini kullanan akış
miktarı,
xj : j düğümünün ADÜ olarak seçilip seçilmemesi (gevşetilmiş olarak)
şeklindedir.
Bu tanımlamalara göre Campbell (1994b) tarafından önerilen matematiksel
model aşağıdaki gibidir.
MODEL 13
Min Max {cijkm wij zijkm }
s.t. ∑k xk = p,
(57)
∑k ∑m zijkm = 1
∀i, j,
(58)
zijkm ≤ xk
∀i, j, k, m,
(59)
zijkm ≤ xm
∀i, j, k, m,
(60)
0 ≤ xk ≤ 1
∀k,
(61)
0 ≤ zijkm ≤ 1
∀i, j, k, m,
(62)
Amaç fonksiyonu, her kaynak-varış çifti arasındaki maksimum taşıma
maliyetini minimize eder. (57) kısıtı, seçilecek ADÜ sayısını p ile sınırlar. (58)
54
kısıtı, her kaynak varış çiftinin bir ADÜ çiftine atanmasını garanti eder. (59) ve
(60) kısıtları, i düğümünden j düğümüne olan akışın, k ve m düğümlerinin ADÜ
olarak seçilmesi durumunda bu düğümlere atanabilmesini sağlar. (61) ve (62)
kısıtları ile karar değişkenleri gevşetilmiştir.
5. ADÜ KAPSAMA PROBLEMİ
ADÜ kapsama problemi ile ilgili ilk modeller Campbell (1994b)
tarafından sunulmuştur. Campbell (1994b) çalışmasında iki farklı model
önermiştir. Bu modeller, ADÜ küme kapsama yer seçim ve ADÜ maksimum
kapsama yer seçim modelleridir. ADÜ küme kapsama yer seçim probleminde
matematiksel modelin,
Varsayımları;

Amaç fonksiyon tipi: Minimum toplam,

Çözüm uzayı: Kesikli ve sonlu,

Tüm ADÜ’ler birbirleriyle tam bağlı,

Seçilecek ADÜ sayısı model tarafından belirlenen (endojen),

ADÜ olmayan iki düğüm arasında, ADÜ kullanmadan direkt akış olmayan,

ADÜ kuruluş maliyeti olan,

ADÜ kapasite kısıtı olmayan,

Karar değişkenleri karışık tamsayı tamsayı şeklinde,
Girdileri;
Fk ∶ k ADÜ’sünün sabit kuruluş maliyeti,
Cijkm :i kaynak noktasından j varış noktasına k ve m ADÜ’leri vasıtasıyla transfer
maliyeti,
γij : i kaynak noktasından j varış noktasına maksimum ulaşım maliyeti,
Cijkm ≤ γij (i, j kaynak-varış çiftleri k ve m ADÜ’leri tarafından kapsanır),
vijkm : k ve m ADÜ’leri i, j kaynak-varış çiftini kapsaması şeklinde,
55
Karar Değişkenleri;
Modelin karar değişkenleri, MODEL 13 ile aynı şekildedir.
Bu tanımlamalara göre matematiksel model aşağıdaki gibidir.
MODEL 14
Min ∑ 

S.t. zijkm ≤ X k
∀i, j, k, m,
(63)
zijkm ≤ Xm
∀i, j, k, m,
(64)
∑k ∑m vijkm zijkm ≥ 1
∀i, j,
(65)
0 ≤ Xk ≤ 1
∀k,
(66)
0 ≤ zijkm ≤ 1
∀i, j, k, m,
(67)
Amaç fonksiyonu, toplam ADÜ yer seçim maliyetini minimize eder.
(65) kısıtı, bütün kaynak-varış çiftlerinin en az bir kez kapsandığını garanti
eder. Diğer kısıtlar MODEL 13’te açıklandığı şekildedir.
ADÜ maksimum kapsama yer seçim probleminin matematiksel
modelinin,
Varsayımları;
Modelin varsayımları, amaç fonksiyonunun maksimumun minimumu
olması, seçilecek ADÜ sayısının bilinmesi (eksojen) ve sabit kuruluş
maliyetinin olmaması dışında MODEL 14 ile aynıdır.
Girdileri;
hij : i kaynak noktasından, j varış noktasına akış talebi,
vijkm : k ve m ADÜ’leri i, j kaynak-varış çiftini kapsaması,
p: seçilecek ADÜ sayısı şeklinde,
56
Karar Değişkenleri;
Modelin karar değişkenleri, MODEL 13 ile aynı şekildedir.
Bu tanımlamalara göre matematiksel model aşağıdaki gibidir.
MODEL 15
Max ∑i ∑j ∑m hij zijkm vijkm
∑k X k = p
(68)
∑k ∑m zijkm = 1
∀i, j,
(69)
zijkm ≤ Xk
∀i, j, k, m,
(70)
zijkm ≤ Xm
∀i, j, k, m,
(71)
0 ≤ Xk ≤ 1
∀k,
(72)
0 ≤ zijkm ≤ 1
∀i, j, k, m,
(73)
Amaç fonksiyonu, kapsama talep miktarını maksimize eder. Diğer
kısıtlar MODEL 13’te açıklandığı şekildedir.
57
ÜÇÜNCÜ BÖLÜM
UYGULAMA
1. PROBLEMİN TANIMI
Bu çalışmada, bir kamu kurumuna ait gerçek bir ana dağıtım üssü yer
seçim problemi ele alınmıştır. Bu problem, mevcut sistemin ihtiyaçlara tam ve
ekonomik
olarak
cevap
verememesinden
kaynaklanmaktadır.
Kamu
kurumunun üst yöneticileri ile yapılan görüşmeler neticesinde, mevcut sistemin
ihtiyaca etkin olarak cevap veremediği, daha kullanışlı ve bilimsel tabanlı bir
sistem arzu edildiği anlaşılmıştır.
Kamu kurumu, dönemsel olarak, çalışanlarının bir bölümünü ErzincanElazığ-Diyarbakır-Mardin hattının batısındaki illerden hattın doğusundaki illere,
hattın doğusundaki illerden hattın batısındaki illere ve hattın doğusundaki iller
arasında güvenli bir şekilde sevk etmesi gerekmektedir. Problemde, çalışanlar,
hem kara hem de hava yolu ile taşınabilmektedir. Güvenlik nedeni ile bazı yollar
arasında kara yolu taşımacılığının maliyeti çok yüksektir. Belirlenen hattın
batısındaki iller arası personel sevkiyatı çalışanların kendi imkanları ile
gerçekleştirilmektedir ve kapsam dışı bırakılmıştır.
Hali hazırda işletilmekte olan sistemde, çalışanlar, gidecekleri noktalara
kurumun belirlediği güzergahlara göre, sadece kara yolunu ya da hava yolunu
veya kara yolu ve hava yolunu birlikte kullanarak gidebilmektedir. Sistemde,
belirlenen hattın batısındaki “12” ilin havaalanı ile doğusundaki “9” ilin havaalanı
kullanılmaktadır. Hava yolu ile sevk edilecek personelin bulunduğu şehre göre
hangi
hava
alanını
kullanması
gerektiği
kurum
tarafından
önceden
belirlenmiştir. Belirlenen hattın doğusundan batısına, batısından doğusuna ve
doğusundan doğusuna gidecek olan çalışanların hangi güzergahı kullanacakları
kurum tarafından belirlenmekte ve seyahat planlaması yapılmaktadır.
58
Bu durumu örnekler ile açıklayacak olursak; Ankara’dan Ağrı’ya gidecek
olan bir çalışan, Ankara’dan Ağrı’ya direkt olarak hava yolu ile gitmektedir.
Kırıkkale’den Ağrı’ya gidecek olan bir çalışan, Kırıkkaleden Ankara’ya kara yolu
ile buradan Ağrı’ya hava yolu ile gitmektedir. Afyon’dan Hakkari’ye gidecek olan
bir çalışan öncelikle kara yolu ile Ankara’ya oradan hava yolu ile Van’a, oradan
kara yolu ile Hakkari’ye gitmektedir. Kars’tan Hakkari’ye gidecek olan bir çalışan
Kars’tan Ankara’ya hava yolu ile, Ankara’dan Van’a hava yolu ile, Van’dan
Hakkari’ye kara yolu ile gitmektedir.
Hava yolu ile sevk edilecek personelin bulunduğu şehre göre hangi
hava alanını kullanması gerektiği kurum tarafından önceden belirlenmiştir.
Tablo-8’de belirlenen hattın batısında, Tablo-9’da ise hattın doğusunda bulunan
havaalanları ve hangi illerden sevk edilen personelin bu havaalanlarını
kullanacağı gösterilmiştir.
Tablo-8: Hattın Batısında Kullanılan Havaalanları ve Hangi İllerden Sevk
Edilen Personelin Bu Havaalanlarını Kullanacağını Gösteren Çizelge
İller
S.Nu.
1.
ADANA
2.
GAZİANTEP
3.
KAHRAMANMARAŞ
4.
KARAMAN
5.
KAYSERİ
6.
KİLİS
7.
MERSİN
8.
NİĞDE
9.
OSMANİYE
10.
AFYONKARAHİSAR
11.
AKSARAY
12.
ANKARA
13.
BARTIN
14.
BOLU
15.
ÇANKIRI
16.
ESKİŞEHİR
17.
18.
19.
KARABÜK
KASTAMONU
KIRIKKALE
20.
KIRŞEHİR
21.
KONYA
22.
KÜTAHYA
23.
NEVŞEHİR
24.
YOZGAT
25.
ZONGULDAK
Biniş Yapılacak Havaalanları
ADANA
ANKARA
59
Tablo-8’in devamı : Hattın Batısında Kullanılan Havaalanları ve Hangi
İllerden Sevk Edilen Personelin Bu Havaalanlarını Kullanacağını Gösteren
Çizelge
İller
S.Nu.
Biniş Yapılacak Havaalanları
26.
ANTALYA
27.
BURDUR
28.
ISPARTA
29.
AMASYA
30.
SİVAS
SİVAS
31.
TOKAT
TOKAT
32.
HATAY
HATAY
33.
BİLECİK
34.
BURSA
35.
ÇANAKKALE
36.
DÜZCE
37.
EDİRNE
38.
İSTANBUL
39.
KIRKLARELİ
40.
KOCAELİ
41.
SAKARYA
42.
TEKİRDAĞ
43.
YALOVA
44.
BALIKESİR
45.
AYDIN
46.
DENİZLİ
47.
İZMİR
48.
MANİSA
49.
MUĞLA
50.
UŞAK
51.
ÇORUM
52.
GİRESUN
53.
ORDU
54.
RİZE
55.
SAMSUN
56.
SİNOP
57.
TRABZON
58.
URFA
59.
ADIYAMAN
60.
MALATYA
ANTALYA
MERZİFON
İSTANBUL
İZMİR
SAMSUN
DİYARBAKIR
ELAZIĞ
60
Tablo-9 : Hattın Doğusunda Kullanılan Havaalanları ve Hangi İllerden Sevk
Edilen Personelin Bu Havaalanlarını Kullanacağını Gösteren Çizelge
İller
S.Nu.
Biniş Yapılacak Havaalanları
1.
IĞDIR
IĞDIR
2.
ERZURUM
3.
AĞRI
4.
KARS
5.
ARDAHAN
6.
BİTLİS
7.
MUŞ
8.
HAKKARİ
9.
VAN
10.
SİİRT
11.
BATMAN
12.
ŞIRNAK
ŞIRNAK
13.
BİNGÖL
BİNGÖL
ERZURUM
AĞRI
KARS
MUŞ
VAN
BATMAN
. Kurum yönetimiyle yapılan görüşme neticesinde, yönetimin, mevcut
sisteme ilişkin sorgulanmasını istediği temel hususlar şu şekilde belirlenmiştir:
 Kurum tarafından tespit edilmiş havaalanı sayısının doğru olup
olmadığı,
 Kurum tarafından tespit edilmiş olan havaalanı yerlerinin doğru
olup olmadığı,
 Sistemin ekonomik şekilde işletilip işletilmediği,
 Havaalanı bulunmayan ya da havaalanı bulunup kullanılmayan
illerdeki
çalışanların
uygun
yerlere
doğru
olarak
yönlendirilip
yönlendirilmedikleri,
 Kurum tarafından havaalanlarında yapılan personel birleştirme
işlemlerinin doğru olup olmadığı,
 Kurum tarafından belirlenen seyahat güzergahlarının doğru olup
olmadığı,
 Kara yolu ve hava yolu kullanım güzergahlarının doğru olup
olmadığı,
Daha sonra, kurum yönetiminin, tasarlanan sistem için istekleri tespit
edilmiştir. Bu istekler şu şekilde sıralanmıştır:
61
- Çalışanların tamamının mümkün olduğunca hava yolu ile taşınması,
- Batıdaki illerden, Erzincan, Elazığ, Diyarbakır ve Mardin illerine kara
yolu ile taşıma yapılabilmesi,
- Batıdaki illerden, Erzincan, Elazığ, Diyarbakır, Mardin illerinin
doğusunda bulunup bu illlere komşu olan ve kurumun müsaade ettiği illere kara
yolu ile taşıma yapılabilmesi,
- Belirlenen hattın doğusunda bulunan ve kara yolu ile gidişin güvenli
olduğu iller arasında kara yolu ile taşıma yapılabilmesi,
- Maliyet avantajı elde etmek için çalışanların gidecekleri noktalara
bireysel olarak tarifeli uçaklarla gönderilmesi yerine belirlenen havaalanlarında
toplanıp, uçak kiralama yöntemi ile toplu olarak taşınmaları istenmektedir.
Problemin çözümü için kurum yönetiminin istekleri doğrultusunda
kapasite kısıtlı, çok atamalı (seçilecek ADÜ sayısının model tarafından
belirlendiği) ve kapasite kısıtlı, çok atamalı p-ADÜ medyan (seçilecek ADÜ
sayısının
belli
olduğu)
olmak
üzere
iki
farklı
matematiksel
model
oluşturulmuştur. Kapasite kısıtlı, çok atamalı model yardımıyla aşağıdaki
sorulara cevap aranmıştır:
- Bir sevk döneminde taşıtılması gereken personelin hangi vasıta ve
hangi güzergahı kullanarak sevk edileceği.
- Hangi havaalanlarının ADÜ olarak kullanılacağı ve hangi illerin bu
ADÜ’lere atanacağı.
- Sistemin
kaç
adet
ADÜ
vasıtasıyla
en
ekonomik
şekilde
işletilebileceği.
- Hangi iller arasında ADÜ kullanmadan direkt gidişe müsaade
edileceği.
Kapasite kısıtlı, çok atamalı p-ADÜ medyan modeli yardımıyla da
aşağıdaki sorulara cevap aranmıştır:
- Taşıma maliyet ve güzergahlarının farklı ADÜ sayıları için nasıl
değiştiği.
62
- Her bir alternatif ADÜ sayısı için, hangi havaalanlarının ADÜ olarak
kullanılacağı ve hangi illerin bu ADÜ’lere atanacağı.
- Hangi iller arasında ADÜ kullanmadan direkt gidişe müsaade
edileceği.
Problem, şebekedeki düğümler arasındaki mesafelerde üçgensel
eşitsizliğin olmadığı, kesikli uzayda yer alan, kapasite kısıtlı, çok atamalı, eğer
daha ekonomik ise ADÜ olarak seçilmeyen düğümler arasında direkt gidişe
müsaade edildiği; ADÜ yer seçim problemi olarak tasarlanmıştır.
Literatürde yer alan matematiksel modellerin problemin temel
karakteristiklerini karşılamada yetersiz kaldığı görülmüştür. Problemin yapısına
uygun olarak bir matematiksel geliştirmek için bu alandaki en önemli
çalışmalardan bir tanesi olan Alfredo Marin’in (2005a) “Formulating and solving
splittable capacitated multiple allocation hub location problems” adlı çalışması
esas alınmış ve modele yeni boyutlar kazandırılmıştır.
Marin (2005a) bu çalışmasında, posta dağıtım ağı problemini
düşünerek, şebekedeki düğümler arasındaki mesafelerde üçgensel eşitsizliğin
olmadığı, kapasite kısıtlı, çok atamalı ADÜ yer seçim problemleri için bir
matematiksel model önermiştir. Çalışmada, düğümler arasındaki mesafelerde
üçgensel eşitsizliğin bulunmadığı durumda, şebekedeki akışların ikiden fazla
ADÜ gezerek maliyetlerin yanlış hesaplanmasına sebep olacağını vurgulamış
ve posta dağıtım ağında, postaların ADÜ’lere ulaştığında tasnif edildiği ve bu
postalara birdaha işlem yapılmadığı düşüncesinden hareketle, ADÜ’lerin
kapasitelerini yalnızca ADÜ olmayan düğümlerden gelen akışların etkilediğini
belirtmiştir.
Bu çalışmada, ele alınan problemin yapısı gereği Marin (2005a)’in
geliştirdiği modeldeki kapasite kısıtından farklı olarak yeni bir kapasite kısıtı
geliştirilmiştir.
Problemde,
ADÜ’lerin
kapasiteleri
sadece
ADÜ
olarak
seçilmeyen düğümlerden gelen akışlardan değil, aynı zamanda ADÜ olarak
seçilen düğümlerden gelen akışlardan da etkilenmektedir.
63
Çalışmada aynı zamanda kaynak-varış çiftleri arasındaki akışlarda
ADÜ kullanma zorunluluğu gevşetilmiş ve ADÜ olarak seçilmeyen düğümler
arasındaki akışlarda ADÜ kullanmadan direkt gidişe müsaade eden yeni kısıtlar
geliştirilmiştir. Geliştirilen yeni kısıtlar vasıtasıyla;
 Batıdan, belirlenen hattın üzerinde bulunan illere olan akışların,
 Batıdan, belirlenen hattın üzerinde bulunan illere komşu olan ve
kurumun müsaade ettiği illere olan akışların,
 Belirlenen hattın doğusunda bulunan ve kurumun müsaade ettiği
iller arasındaki akışların,
ADÜ kullanmadan direkt olarak gerçekleşmesi sağlanmış, böylece akışların
daha fazla yol katederek fazla maliyete sebep olması engellenmiştir.
Örneğin; Ardahan ve Artvin illeri ADÜ olarak seçilmeyen iller olsun. Bu
durumda, eğer ADÜ olmayan düğümler arasındaki akışlarda mutlaka ADÜ
kullanma mecburuyeti olsaydı, bu iki il arasındaki akış, Ardahan-Kars (ADÜ
olarak seçilmiş)-Erzurum (ADÜ olarak seçilmiş)-Artvin, ya da Ardahan- Kars
(ADÜ olarak seçilmiş)-Artvin yolunu izleyecektir. ADÜ kullanma mecburiyetinin
gevşetilmesi ile bu akışın, eğer daha az maliyetli ise Ardahan-Artvin yolunu
kullanabilmesi ve akışın daha az maliyetle gerçekleşmesi sağlanmış olur.
2. MATEMATİKSEL MODEL
Varsayımlar;
 Amaç fonksiyon tipi: Minimum toplam,
 Çözüm uzayı: Kesikli ve sonlu,
 Tüm düğümler birbirleriyle ile tam bağlı,
 Seçilecek ADÜ sayısı: birinci matematiksel modelde model tarafından
belirlenen (endojen), ikinci matematiksel modelde karar verici tarafından
belirlenen (eksojen),
64
 ADÜ olmayan iki düğüm arasında, eğer daha ekonomik ise, ADÜ
kullanmadan direkt gidişe müsaade edilen,
 ADÜ olarak seçilmeyen düğümlerin birden fazla ADÜ’ye atanabildiği (çok
atamalı),
 ADÜ kuruluş maliyeti olmayan,
 ADÜ’ler kapasite kısıtlı (ADÜ’lerin kapasitelerinin hem ADÜ, hem de ADÜ
olarak seçilmeyen düğümlerden gelen akışlardan etkilendiği),
 Tüm karar değişkenleri karışık tamsayı,
 Kaynak-varış çiftleri arasındaki akışların en fazla iki ADÜ kullanarak
gerçekleştiği,
 Tüm akışların aynı gün içerisinde gerçekleştiği,
 Tüm ADÜ’ler arasında hava yolu ile transferin mümkün olduğu,
 Tüm düğümlerin aday ADÜ konumunda olmadığı,
Şeklindedir. Önerilen matematiksel modeller bu varsayımlar altında
çalışılmıştır.
Kurumun istekleri doğrultusunda oluşturulan matematiksel model ve
modelde yer alan değişken/parametre tanımlamaları aşağıda sunulmuştur:
a. Kümeler
Problemde “81” adet ili kapsayan tek bir küme (N) bulunmaktadır.
Dolayısıyla bütün indisler aynı küme içerisinde yer almakta ve aynı küme
içerisinden seçilmektedir. İller plaka kodları ile ifade edilmiştir. ADÜ yer seçim
problemlerinde, tüm düğümler aynı zamanda aday ADÜ durumundadır. Bu
çalışmada ise, “81” adet düğüm aday ADÜ konumunda değildir. Kurum,
personelinin mümkün olduğunca hava yolu ile taşıtılmasını istediğinden,
düğümler arasında yer alan ve anlaşma yapılan firmanın uçaklarının iniş ve
kalkış yapabildiği “42” adet havaalanı aday ADÜ olarak belirlenmiştir. Aday ADÜ
konumundaki havaalanları Tablo-10’da sunulmuştur.
65
Tablo-10 : Aday ADÜ Konumundaki Havaalanları
Plaka Kodu
1.
2.
4.
5.
6.
7.
10.
12.
16.
20.
21.
23.
24.
25.
27.
31.
32.
34.
35.
36.
37.
38.
41.
42.
43.
44.
46.
47.
48.
49.
50.
55.
56.
58.
59.
60.
61.
63.
65.
72.
73.
76.
İller
ADANA
ADIYAMAN
AĞRI
AMASYA
ANKARA
ANTALYA
BALIKESİR
BİNGÖL
BURSA
DENİZLİ
DİYARBAKIR
ELAZIĞ
ERZİNCAN
ERZURUM
GAZİANTEP
HATAY
ISPARTA
İSTANBUL
İZMİR
KARS
KASTAMONU
KAYSERİ
KOCAELİ
KONYA
KÜTAHYA
MALATYA
KAHRAMANMARAŞ
MARDİN
MUĞLA
MUŞ
NEVŞEHİR
SAMSUN
SİİRT
SİVAS
TEKİRDAĞ
TOKAT
TRABZON
ŞANLIURFA
VAN
BATMAN
ŞIRNAK
IĞDIR
66
b. Girdi Değerleri ve Sabitler
Girdi Değerleri
Wij : i kaynak noktasından j varış noktasına akış miktarı (i: 1,2,…,81; j:
1,2,…,81)
rij : i kaynak noktası ile j varış noktası arasındaki kara yolu mesafesi (i:
1,2,…,81; j: 1,2,…,81)
hij : i kaynak varış noktası ile j varış noktası arasındaki hava yolu
mesafesi (i: 1,2,…,81; j: 1,2,…,81)
Γk : k düğümünün kapasitesi
Sabitler
α : Transfer için maliyet azaltma faktörü (ana dağıtım üssünden ana
dağıtım üssüne), ADÜ yer seçim problemlerinde, ADÜ’ler arasındaki akışlarda
(transfer) ölçek ekonomisinden faydalanmak maksadıyla α adında ve değeri 01 arasında olan bir sabit kullanılmaktadır. Bu çalışmada α, kurum yetkilileri ile
yapılan görüşme neticesinde, anlaşma yapılan firmanın tarifeli uçak ücretleri ve
uçak kiralama fiyatları düşünülerek “0,6” olarak belirlenmiştir.
Ɣ : Dağıtım için maliyet azaltma katsayısı (ana dağıtım üssünden ana
dağıtım üssü olmayan varış noktasına), Ɣ katsayısı kurumun dağıtım
işlemlerinde kendi araçlarını kullanabilmesinden kaynaklanan maliyet azaltma
katsayısıdır ve kurumdan “0,8” olarak alınmıştır.
Ʊ : kara yolu ile taşıma için bir km’lik maliyet katsayısı. Bu katsayı,
kurumun mali yönetimi tarafından mevcut sistemde bir km’lik kara yolu
mesafesine karşılık bir kişi için ödenen ₺ cinsinden ücret miktarıdır ve kurumdan
0,09 ₺ olarak alınmıştır.
ɸ : hava yolu ile taşıma için bir km’lik maliyet katsayısı. Bu katsayı,
kurumun mali yönetimi tarafından mevcut sistemde bir km’lik hava yolu
mesafesine karşılık bir kişi için ödenen ₺ cinsinden ücret miktarıdır ve kurumdan
0,13 ₺ olarak alınmıştır.
67
Kurum, çalışanlarını, bir yıl içerisinde dört dönem halinde sevk
etmektedir. Çalışmada bir sevk dönemi ele alınmıştır. Bir dönemde sevk
edilecek çalışan miktarı ve hangi illerden çıkıp hangi illere, hangi sayılarda
gidecekleri (W ij değerleri) kurumdan alınan veriler yardımıyla belirlenmiştir.
Düğümler (iller) arası mesafeler (rij ve hij değerleri) Karayolları Genel
Müdürlüğü internet sayfasından alınmıştır ( Kara Yolları Genel Müdürlüğü [web],
2014). Uzaklıklar matrisi, kara yolu ve hava yolu taşımacılığı için iki farklı şekilde
düzenlenmiştir. Kara yolu taşımacılığı için oluşturulan uzaklıklar matrisinde,
kurum tarafından direkt gidilmesine müsaade edilmeyen iller arasındaki
mesafeler için, matrisin ilgili hücresine büyük ceza katsayıları girilmiş ve bu
gidişler engellenmiştir. Hava yolu taşımacılığı için oluşturulan uzaklıklar
matrisinde, havaalanı bulunmayan iller arasındaki mesafeler için, matrisin ilgili
hücresine büyük ceza katsayıları girilmiş ve bu gidişler engellenmiştir. Kara yolu
taşımacılığı maliyetleri (rij ) ve hava yolu taşımacılığı maliyetleri (hij ) sırasıyla,
ilgili uzaklık matrislerinin, kurum tarafından belirlenen bir km’lik kara yolu taşıma
maliyet katsayısı (Ʊ) ve bir km’lik hava yolu taşıma maliyet katsayısı (ɸ) ile
çarpılması sonucu belirlenmiştir.
Uzaklık matrislerinin ilgili hücrelerine girilmiş olan ceza sayıları
problemde mesafeler arasında yer alan üçgensel eşitsizliği bozmuş ve bazı
ilave işlemler yapılmasını gerektirmiştir. Oluşan bu durumun önemi ve
modellemeye etkisi aşağıda açıklanmaya çalışılmıştır.
ADÜ yer seçimi ile ilgili problemlerde üçgensel eşitsizlik önemli bir yere
sahiptir, dolayısıyla, tasarlanan problemde yer alan mesafe, maliyet gibi
girdilerin üçgensel eşitsizliği sağlaması ya da sağlamaması problemin
çözümünü ve modelin doğru maliyetleri hesaplamasını direkt ve önemli
derecede etkilemektedir. Literatürde yer alan çalışmaların büyük bir çoğunluğu,
problemde yer alan mesafe, maliyet vb. gibi girdilerin, üçgensel eşitsizlik
kuralına uygun olduğu varsayımına dayanmaktadır. Bu varsayım modelleme
aşamasında kolaylık sağlamaktadır.
68
Üçgensel eşitsizlik kuralının olmadığı, yani girdilerin üçgensel eşitsizliği
sağlamadığı
problemlerde
ise,
tasarlanan
modele,
maliyetleri
doğru
hesaplamasını ve ADÜ yer seçim problemlerinin temel varsayımlarından biri
olan, akışların en fazla iki ADÜ gezmesini sağlayacak kısıtlar eklemek
gerekmektedir. Bu çalışmada da kaynak-varış çiftleri arasındaki akışların en
fazla iki ADÜ gezerek gideceği noktaya ulaşmasını sağlamak için, Marin
(2005a) tarafından geliştirilmiş olan kısıtlar kullanılmıştır.
Sabit maliyetli ADÜ yer seçim problemlerinde, ADÜ olarak seçilen
düğümler sabit bir kuruluş maliyetine sahiptir. Bu çalışma, sabit maliyetli,
kapasite kısıtlı ADÜ yer seçim problemi olarak tasarlanmıştır. Ancak,
işletilmekte olan sistemde, kurumun havaalanı bulunan her ilde kurulmuş olan
ve halihazırda işleyen tesisleri vardır. Dolayısıyla, herhangi bir ilde bulunan
havaalanının ADÜ olarak seçilmesi durumunda, yeniden kuruluş maliyeti söz
konusu değildir. Mevcut durumda kullanılan bir tesisin ADÜ olarak seçilmemesi
durumunda ise, bu tesis kurum tarafından başka bir maksatla kullanılmaya
devam edeceği ve tesis kapatma maliyetinin oluşmayacağı değerlendirilmiştir.
Bu nedenle sabit kuruluş maliyeti problemin dışında bırakılmıştır.
b. Karar Değişkenleri
amj : m düğümünün ADÜ, j düğümünün ADÜ olmadığı durumda, m
düğümünden j düğümüne giden akış miktarı,
bkmj: k ve m düğümlerinin ADÜ, j düğümünün ADÜ olmadığı durumda,
k ve m ADÜ’lerini kullanıp j düğümüne giden akış miktarı,
cikj : k düğümünün ADÜ, i düğümünün ADÜ olmadığı durumda, i
düğümünden çıkıp k ADÜ’sünü kullanarak j düğümüne giden akış miktarı,
Yk : k düğümünün ADÜ olduğu durumda “1”, diğer durumlarda “0”
değerini alan ikil değişken,
eij : i ve j düğümlerinin ADÜ olmadığı durumda, i düğümünden j
düğümüne ADÜ kullanmadan direkt giden akış miktarı,
Modelde beş tip karar değişkeni bulunmaktadır. Birinci tip karar
değişkeni (a), başlangıç noktasının ADÜ, varış noktasının ADÜ olmayan düğüm
69
olduğu durumdaki akış miktarını belirtmektedir. İkinci tip karar değişkeni (b),
başlangıç noktasının ve ikinci düğümün ADÜ olduğu durumdaki akış miktarının
belirtmektedir. Üçüncü tip karar değişkeni (c), başlangıç noktasının ADÜ
olmayan düğüm, ikinci düğümün ADÜ olduğu durumdaki akış miktarını
belirtmektedir. Dördüncü tip karar değişkeni (e), başlangıç ve varış noktasının
ADÜ olmayan düğüm olduğu durumda, ADÜ kullanılmadan, kaynak
noktasından varış noktasına direkt giden akışı belirtmektedir. Beşinci tip karar
değişkeni (Y), bir düğüm ADÜ olarak seçildiğinde “1”, seçilmediğinde “0”
değerini alan ikil değişkendir. Problemde yer alması muhtemel tüm alternatif
yollar ve karar değişkenlerinin hangi durumlarda değer aldıkları Şekil-5 ‘te
sunulmuştur.

i


k

i

i

i
k
k
m

i
i
(2)

(3)
j
(4)
j
(5)
j



i
(1)
j

i
j
(6)
j
(7)
j
k

(8)
j
Şekil-5: Problemde Yer Alan Muhtemel Yollar ve Karar Değişkenlerinin
Görevleri
70
Yukarıdaki şekilde, ADÜ’ler kare ile, ADÜ olmayan düğümler ise daire
ile gösterilmiştir.
(1) numaralı alternatif yolda, başlangıç i düğümü ADÜ olmayan nokta,
k ve m düğümleri ADÜ, varış noktası olan j düğümü ise ADÜ olmayan noktadır.
i ve k düğümleri arasındaki akış cikj karar değişkeni ile ifade edilmiştir. cikj karar
değişkeni yalnızca başlangıç düğümünün ADÜ olmayan düğüm, ikinci düğümün
ADÜ olduğu durumda değer alabilmektedir. Aynı akışın devamı olan k ve m
düğümleri arasındaki akış bkmj karar değişkeni ile ifade edilmiştir. bkmj karar
değişkenini yalnızca birinci ve ikinci düğümün ADÜ olduğu durumda değer
alabilmektedir. Aynı yolun sonundaki m ve j düğümleri arasındaki akış amj karar
değişkeni ile ifade edilmiştir. amj karar değişkeni yalnızca birinci düğümün ADÜ,
ikinci düğümün ADÜ olmayan düğüm olduğu durumda değer alabilmektedir.
(2) numaralı alternatif yolda, i düğümü ADÜ olmayan düğüm, k düğümü
ADÜ, j düğümün ADÜ olmayan düğüm olduğundan, ilk akış cikj , ikinci akış akj
karar değişkeni ile ifade edilmiştir.
(3) numaralı alternatif yolda, i düğümü ADÜ olmayan düğüm, k ve j
düğümleri ADÜ olduğundan, ilk akış cikj , ikinci akış bkjj karar değişkeni ile ifade
edilmiştir.
(4) numaralı alternatif yolda, i düğümü ADÜ olmayan düğüm, j düğümü
ADÜ olduğundan, bu akış cijj karar değişkeni ile ifade edilmiştir.
(5) numaralı alternatif yolda, i ve j düğümleri ADÜ olmayan düğüm
olduğundan, bu akış eij karar değişkeni ile ifade edilmiştir.
(6) numaralı alternatif yolda, i ve j düğümleri ADÜ olduğundan, bu akış
bijj karar değişkeni ile ifade edilmiştir.
71
(7) numaralı alternatif yolda, i düğümü ADÜ, j düğümü ADÜ olmayan
düğüm olduğundan, bu akış aij karar değişkeni ile ifade edilmiştir.
(8) numaralı alternatif yolda, i ve k düğümleri ADÜ, j düğümü ADÜ
olmayan düğüm olduğundan, ilk akış bikj , ikinci akış akj karar değişkeni ile ifade
edilmiştir.
ç. Matematiksel Model
Birinci Matematiksel Model (CMAHLP)
Bu matematiksel model; kapasite kısıtlı ( ADÜ’lerin kapasitelerinin
hem ADÜ, hem de ADÜ olarak seçilmeyen düğümlerden gelen akışlardan
etkilendiği), çok atamalı, ADÜ olarak seçilmeyen düğümler arasında direkt
gidişe müsaade eden ADÜ yer seçim problemi olarak tasarlanmıştır.
Amaç Fonksiyonu
Min∑i ∑k ∑j Ʊ rik cikj + ∑k ∑m ∑j α ɸ hkm bkmj + ∑m ∑j Ɣ Ʊ rmj amj +
∑i ∑j Ʊ eij rij
Kısıtlar
∑m amj + ∑m bmjj + ∑m cmjj + ∑m emj = ∑i Wij
∀j,
(74)
eij + aij + ∑k bikj + ∑k cikj = Wij + ∑k bkij + ∑k ckij
∀i, ∀j ≠ i,
(75)
∑k bkmj + ∑k ckmj ≤ (∑i Wij − Wmj )Ym
∀j, ∀m ≠ j,
(76)
∑k bkjj + ∑k ckjj = ∑i Wij Yj
∀j,
(77)
cikj ≤ Wij Yk
∀i, j, k,
(78)
eij + ∑k cikj = Wij (1 − Yi )
∀i, j,
(79)
∑m bkmj ≤ Wkj + ∑i cikj
∀k, j,
(80)
∑i ∑j cikj + ∑i ∑j bikj ≤ Γk Yk
∀k,
(81)
72
eij ≤ Wij (1 − Yi )
∀i, j,
(82)
eij ≤ Wij (1 − Yj )
∀i, j,
(83)
bjmj = 0
∀j, ∀m ≠ j,
(84)
bkkj = 0
∀j, ∀k ≠ j,
(85)
ckkj = 0
∀j, k,
(86)
ajj = 0
∀j,
(87)
Yk ∊ {0,1}
∀k,
(88)
bkmj , cikj , amj , eij ≥ 0
∀i, j, k, m,
(89)
Modelin amaç fonksiyonu, bir ilden diğer ile en az bir, en fazla iki ADÜ
kullanarak veya ADÜ kullanmayarak giden akışlar için toplam taşıma maliyetini
minimize etmeyi hedeflemektedir. Amaç fonksiyonunun; birinci parçası, toplama
(ADÜ olmayan kaynak düğümünden ADÜ’ye) sürecini ifade etmekte ve cikj
karar değişkeni kara yolu maliyeti ile çarpılmaktadır. İkinci parçası, transfer
(ADÜ’den ADÜ’ye) sürecini ifade etmekte ve bkmj karar değişkeni hava yolu
maliyeti ve maliyet azaltma faktörü olan α ile çarpılmaktadır. Üçüncü parçası,
dağıtım (ADÜ’den ADÜ olmayan varış noktasına) sürecini ifade etmekte ve amj
karar değişkeni kara yolu maliyetine ilaveten Ɣ katsayısı ile çarpılmaktadır.
Dördüncü parçası, ADÜ olarak seçilmeyen düğümler arasında ADÜ
kullanmadan direkt gidişi ifade etmekte ve eij karar değişkeni kara yolu maliyeti
ile çarpılmaktadır.
(74) numaralı kısıt, her ildeki tüm şubelerin talebinin karşılandığını
garanti etmektedir. Kısıt bu işlemi, j düğümüne herhangi bir m düğümünden
gelebilecek muhtemel tüm akışları, tüm i düğümlerinden j düğümüne sevk edilen
akış miktarına eşitleyerek gerçekleştirir.
(75) numaralı kısıt akışları dengeler ve akış kaybını engeller. Kısıt bu
işlemi i düğümüne gelmesi ve çıkması muhtemel tüm akışları ifade ederek
gerçekleştirir. Kısıtın sağ tarafında, i düğümüne gelebilecek tüm muhtemel
73
akışlar, sol tarafında, i düğümünden çıkabilecek tüm muhtemel akışlar yer
almaktadır.
(76) numaralı kısıt, ADÜ’ler arası akışı (transfer) ifade eden bkmj karar
değişkenin, yalnızca k ve m düğümlerinin ADÜ olarak seçilmesi durumunda
değer almasını sağlar.
(77) numaralı kısıt, ADÜ’ler arası akışı (transfer) ifade eden bkjj karar
değişkeninin, yalnızca k ve j düğümlerinin ADÜ olarak seçilmesi durumunda
değer almasını sağlar.
(78) numaralı kısıt, ADÜ olmayan kaynak noktasından ADÜ’lere olan
akışı (toplama) ifade eden cikj karar değişkeninin yalnızca k düğümünün ADÜ
olarak seçilmesi durumunda değer almasını sağlar. (79) numaralı kısıt ise,
kaynak noktası olan i düğümünün ADÜ olarak seçilmesi durumunda cikj ve eij
karar değişkenlerinin değer almamasını sağlar. Bu iki kısıt vasıtasıyla cikj karar
değişkeni, yalnızca i düğümünün ADÜ olmayan düğüm, k düğümünün ADÜ
olduğu durumda değer alabilir.
(80) numaralı kısıt, herhangi bir kaynak-varış noktası arasındaki akışın
en fazla iki ADÜ’ye uğrayarak tamamlanmasını sağlar. Bu kısıt vasıtasıyla,
mesafeler arasında üçgensel eşitsizliğin olmamasından kaynaklanabilecek
ikiden fazla ADÜ gezme işlemi engellenmiş olur. Kısıt bu işlemi, ADÜ olarak
seçilen k ilinden çıkan akışlar toplamının üst sınırını kullanarak yapar. Böylece,
ADÜ olarak seçilen bir k iline, ADÜ olarak seçilen başka bir ilden akış geldiğinde
bu akış, amj dağıtım (ADÜ’den ADÜ olmayan varış noktasına) karar değişkeni
ile direkt olarak j iline gitmeye zorlanır.
(81) numaralı kısıt kapasite kısıtıdır. Havaalanı bulunan “42” ilde
kuruma ait bir veya birden fazla konaklama tesisi bulunmaktadır ve bu tesisler
belirli bir kapasiteye sahiptir. ADÜ olmaya aday düğümler için kapasiteler, o ilde
bulunan konaklama tesislerinin yatak kapasiteleri toplanarak hesaplanmıştır.
74
(81) numaralı kısıt, ADÜ olarak seçilen bir k düğümüne, ADÜ olarak seçilen ve
ADÜ olarak seçilmeyen tüm düğümlerden gelen akış toplamının, k düğümünün
kapasitesini geçmesini engeller.
(82) numaralı kısıt i düğümünün ADÜ olarak seçilmesi durumunda eij
karar değişkeninin değer almamasını, (83) numaralı kısıt j düğümünün ADÜ
olarak seçilmesi durumunda eij karar değişkeninin değer almamasını sağlar.
Başka bir ifadeyele (82) ve (83) numaralı kısıtlar eij karar değişkeninin yalnızca
i ve j düğümlerinin ADÜ olarak seçilmediği durumda değer alabilmesini sağlar.
(84), (85), (86) ve (87) numaralı kısıtlar, modelde yer alması mümkün
olmayan karar değişkenlerini “0” yapmak amacıyla yazılmış kısıtlardır.
(88) numaralı kısıt, Yk karar değişkeninin “0” ya da “1” değerini almasını
sağlar.
(89) numaralı kısıt, modelde yeralan tüm karar değişkenlerinin 0’dan
büyük ve tamsayılı değerler almasını sağlar.
İkinci Matematiksel Model (CMApHLP)
Bu matematiksel model, birinci matematiksel modelden farklı olarak pADÜ medyan problemi olarak tasarlanmıştır. Bu matematiksel model
vasıtasıyla, karar vericiye ADÜ sayısını belirleme imkanı tanınmıştır.
Amaç Fonksiyonu
Min∑i ∑k ∑j Ʊ rik cikj + ∑k ∑m ∑j α ɸ hkm bkmj + ∑m ∑j Ɣ Ʊ rmj amj +
∑i ∑j Ʊ eij rij
Kısıtlar
75
(74)-(89)
∑k Yk = p,
(90)
Modelde (90) numaralı kısıt vasıtasıyla seçilecek ADÜ sayısı
belirlenmektedir. Amaç fonksiyonu ve diğer tüm kısıtlar birinci matematiksel
modelde açıklandığı şekildedir. Kurum, bu matematiksel model vasıtasıyla,
değişik ADÜ sayılarına göre toplam taşıma maliyetlerinin ve atamaların nasıl
değiştiğini, aynı zamanda hangi iller arasında ADÜ kullanmadan direkt gidiş
olması gerektiğini görebilmektedir.
c. Birinci Modelin Sonuçları
Önerilen kapasite kısıtlı, çok atamalı (seçilecek ADÜ sayısının
model tarafından belirlendiği) birinci matematiksel model (CMAHLP), GAMS
IDE 2.0.34.19 yazılımı ile kodlanmış ve CPLEX 10.1 çözücüsü ile en iyi çözüme
ulaşılmıştır. Modelin 659.521 tamsayı değişkeni ve 7.995 kısıtı bulunmaktadır.
Modelin amaç fonksiyon değeri 1.964.973,8 ₺, çözüm süresi 91,58 sn’dir.
Çözüm sonucunda; aday ADÜ konumundaki “42” adet havaalanından
“35” tanesi model tarafından ADÜ olarak seçilmiştir. Halihazırda işletilmekte
olan sistemde kullanılan “21” adet havaalanından Diyarbakır ve Erzurum
havaalanlarının kullanılmaması, kalan “19” adet havaalanına ilave olarak,
Adıyaman, Bursa, Denizli, Gaziantep, Kastamonu, Kayseri, Kocaeli, Konya,
Malatya, Kahramanmaraş, Muğla, Nevşehir, Siirt, Trabzon, Şanlıurfa ve Batman
havaalanlarının kullanılması gerektiği sonucuna ulaşılmıştır.
Çözüm sonuçlarının tamamı incelendiğinde; farklı düğüm noktalarından
çıkarak aynı varış noktasına gidecek olan akışların ADÜ’lerdeki yük
birleştirmelerinin etkili bir şekilde yapıldığı görülmüştür.
Seçilen ADÜ’ler ve ADÜ’lerin hangi iller tarafından kullanılacağı Tablo11’de sunulmuştur.
76
Tablo-11: Birinci Matematiksel Modelin Çözümü Sonucunda Seçilen ADÜ’ler
ve ADÜ’lerin Hangi İller Tarafından Kullanılacağını Gösteren Çizelge
İller
Plaka Kodu
1
ADANA
21
DİYARBAKIR
33
MERSİN
47
MARDİN
51
NİĞDE
68
AKSARAY
70
KARAMAN
2
ADIYAMAN
21
DİYARBAKIR
25
ERZURUM
47
MARDİN
62
TUNCELİ
4
AĞRI
24
ERZİNCAN
25
ERZURUM
5
AMASYA
14
BOLU
18
ÇANKIRI
19
ÇORUM
24
ERZİNCAN
25
ERZURUM
57
SİNOP
62
TUNCELİ
67
ZONGULDAK
81
DÜZCE
6
ANKARA
3
AFYON
11
BİLECİK
14
BOLU
26
ESKİŞEHİR
54
SAKARYA
64
UŞAK
67
ZONGULDAK
81
DÜZCE
7
ANTALYA
15
BURDUR
12
BİNGÖL
21
DİYARBAKIR
25
ERZURUM
62
TUNCELİ
16
BURSA
10
BALIKESİR
17
ÇANAKKALE
Atandığı ADÜ
ADANA
ADIYAMAN
AĞRI
AMASYA
ANKARA
ANTALYA
BİNGÖL
BURSA
77
Tablo-11’in devamı : Birinci Matematiksel Modelin Çözümü Sonucunda
Seçilen ADÜ’ler ve ADÜ’lerin Hangi İller Tarafından Kullanılacağını Gösteren
Çizelge
İller
Plaka Kodu
20
DENİZLİ
9
AYDIN
23
ELAZIĞ
21
DİYARBAKIR
24
ERZİNCAN
29
GÜMÜŞHANE
47
MARDİN
62
TUNCELİ
69
BAYBURT
27
GAZİANTEP
79
KİLİS
80
OSMANİYE
31
HATAY
34
İSTANBUL
22
EDİRNE
39
KIRKLARELİ
59
TEKİRDAĞ
35
İZMİR
45
MANİSA
36
KARS
8
ARTVİN
25
ERZURUM
75
ARDAHAN
37
KASTAMONU
67
ZONGULDAK
74
BARTIN
78
KARABÜK
38
KAYSERİ
40
KIRŞEHİR
51
NİĞDE
70
KARAMAN
71
KIRIKKALE
41
KOCAELİ
54
SAKARYA
77
YALOVA
42
KONYA
3
AFYON
15
BURDUR
32
ISPARTA
64
UŞAK
43
KÜTAHYA
10
BALIKESİR
11
BİLECİK
Atandığı ADÜ
DENİZLİ
ELAZIĞ
GAZİANTEP
HATAY
İSTANBUL
İZMİR
KARS
KASTAMONU
KAYSERİ
KOCAELİ
KONYA
KÜTAHYA
78
Tablo-11’in devamı : Birinci Matematiksel Modelin Çözümü Sonucunda
Seçilen ADÜ’ler ve ADÜ’lerin Hangi İller Tarafından Kullanılacağını Gösteren
Çizelge
İller
Plaka Kodu
44
MALATYA
46
KAHRAMANMARAŞ
80
OSMANİYE
48
MUĞLA
49
MUŞ
13
BİTLİS
25
ERZURUM
50
NEVŞEHİR
68
AKSARAY
55
SAMSUN
24
ERZİNCAN
25
ERZURUM
57
SİNOP
62
TUNCELİ
56
SİİRT
13
BİTLİS
58
SİVAS
24
ERZİNCAN
25
ERZURUM
62
TUNCELİ
66
YOZGAT
60
TOKAT
18
ÇANKIRI
19
ÇORUM
24
ERZİNCAN
25
ERZURUM
71
KIRIKKALE
61
TRABZON
8
ARTVİN
24
ERZİNCAN
25
ERZURUM
28
GİRESUN
29
GÜMÜŞHANE
52
ORDU
53
RİZE
62
TUNCELİ
69
BAYBURT
63
ŞANLIURFA
21
DİYARBAKIR
47
MARDİN
62
TUNCELİ
Atandığı ADÜ
MALATYA
KAHRAMANMARAŞ
MUĞLA
MUŞ
NEVŞEHİR
SAMSUN
SİİRT
SİVAS
TOKAT
TRABZON
ŞANLIURFA
79
Tablo-11’in devamı : Birinci Matematiksel Modelin Çözümü Sonucunda
Seçilen ADÜ’ler ve ADÜ’lerin Hangi İller Tarafından Kullanılacağını Gösteren
Çizelge
İller
Plaka Kodu
65
VAN
13
BİTLİS
30
HAKKARİ
72
BATMAN
13
BİTLİS
21
DİYARBAKIR
47
MARDİN
73
ŞIRNAK
30
HAKKARİ
47
MARDİN
76
IĞDIR
Atandığı ADÜ
VAN
BATMAN
ŞIRNAK
IĞDIR
Tablo-11 incelendiğinde, matematiksel modelin, kaynak-varış çiftleri
arasındaki akışları, aday ADÜ konumundaki “42” adet havaalanından Balıkesir,
Diyarbakır, Erzincan, Erzurum, Isparta, Mardin ve Tekirdağ havaalanları
dışındaki “35” havaalanı (ADÜ) ile gerçekleştirdiği görülmektedir.
Kurumun hali hazırda kulanmış olduğu sistemde, ADÜ olarak
seçilmeyen tüm iller güzergah farkı olmaksızın yalnızca bir havaalanını
kullanmaktadır. Modelin sonuçlarında ise, ADÜ olarak seçilmeyen iller farklı
güzergahlar için farklı havaalanlarını kullanabilmektedir. Örneğin, ADÜ olarak
seçilmeyen Diyarbakır ili, ADÜ olarak seçilen Adana, Adıyaman, Bingöl, Elazığ,
Şanlıurfa ve Batman havaalanlarını kullanmaktadır. Diyarbakır ilindeki
çalışanlar, Konya’ya giderken Adana, Aydın’a giderken Adıyaman, Kars’a
giderken Bingöl, Bursa’ya giderken Elazığ, İzmir’e giderken Şanlıurfa, Iğdır’a
giderken Batman havaalanlarını kullanmaktadır. Sonuç olarak; aynı kaynak
noktasından çıkıp farklı varış noktalarına gidecek olan akışların aynı ADÜ’yü
kullanma zorunluluğu kaldırılmış ve yük birleştirmelerinin doğru ADÜ’lerde
yapılabilmesi sağlanmıştır.
Tablo-12’de model tarafından belirlenmiş olan “35” adet ADÜ’nün
herbiri için modelde yer alması muhtemel yolları gösterecek şekilde birer örnek
güzergah sunulmuştur.
80
Tablo-12 : Örnek Güzergahlar
Sıra
No
Çıkış
Noktası
İlk Atanacağı ADÜ
Varış Noktası
1
MERSİN
ADANA
AĞRI
2
ADIYAMAN
ADIYAMAN
BİTLİS
ADIYAMAN-BATMAN-BİTLİS
3
ERZURUM
AĞRI
AĞRI
ERZURUM-AĞRI
4
ÇANKIRI
AMASYA
HAKKARİ
ÇANKIRI-AMASYA-VAN-HAKKARİ
5
BİLECİK
ANKARA
ARDAHAN
BİLECİK-ANKARA-KARS-ARDAHAN
6
ANTALYA
ANTALYA
VAN
ANTALYA-VAN
7
TUNCELİ
BİNGÖL
AĞRI
TUNCELİ-BİNGÖL-AĞRI
8
BALIKESİR
BURSA
MUŞ
BALIKESİR-BURSA-MUŞ
9
AYDIN
DENİZLİ
BİTLİS
AYDIN-DENİZLİ-MUŞ-BİTLİS
10
TUNCELİ
ELAZIĞ
ANTALYA
TUNCELİ-ELAZIĞ-ANTALYA
11
GAZİANTEP
GAZİANTEP
IĞDIR
GAZİANTEP-IĞDIR
12
HATAY
HATAY
KARS
HATAY-KARS
13
KIRKLARELİ
İSTANBUL
VAN
14
MANİSA
İZMİR
HAKKARİ
15
ARDAHAN
KARS
KARS
ARDAHAN-KARS
16
KARABÜK
KASTAMONU
AĞRI
KARABÜK-KASTAMONU-AĞRI
17
KARAMAN
KAYSERİ
BİNGÖL
KARAMAN-KAYSERİ-BİNGÖL
18
SAKARYA
KOCAELİ
BİTLİS
SAKARYA-KOCAELİ-BİNGÖL-BİTLİS
19
ISPARTA
KONYA
IĞDIR
ISPARTA-KONYA-IĞDIR
20
KÜTAHYA
KÜTAHYA
AĞRI
KÜTAHYA-AĞRI
21
MALATYA
MALATYA
ARDAHAN
MALATYA-KARS-ARDAHAN
22
OSMANİYE
KAHRAMANMARAŞ
ERZURUM
OSMANİYE-KAHRAMANMARAŞ-ERZURUM
23
MUĞLA
MUĞLA
HAKKARİ
MUĞLA-ŞIRNAK-HAKKARİ
BİTLİS-MUŞ-ANKARA
Kullanılacak Güzergâh
MERSİN-ADANA-AĞRI
KIRKLARELİ-İSTANBUL-VAN
MANİSA-İZMİR-ŞIRNAK-HAKKARİ
24
BİTLİS
MUŞ
ANKARA
25
AKSARAY
NEVŞEHİR
AĞRI
26
SAMSUN
SAMSUN
MARDİN
27
BİTLİS
SİİRT
SİİRT
28
TUNCELİ
SİVAS
ANKARA
29
ÇANKIRI
TOKAT
DİYARBAKIR
30
ORDU
TRABZON
HAKKARİ
31
TUNCELİ
ŞANLIURFA
ŞANLIURFA
TUNCELİ-ŞANLIURFA
32
HAKKARİ
VAN
BİTLİS
HAKKARİ-VAN-BİTLİS
33
BİTLİS
BATMAN
ADANA
BİTLİS-BATMAN-ADANA
34
HAKKARİ
ŞIRNAK
ANTALYA
HAKKARİ-ŞIRNAK-ANTALYA
35
IĞDIR
IĞDIR
ANKARA
IĞDIR-ANKARA
AKSARAY-NEVŞEHİR-AĞRI
SAMSUN-MARDİN
BİTLİS-SİİRT
TUNCELİ-SİVAS-ANKARA
ÇANKIRI-TOKAT-DİYARBAKIR
ORDU-TRABZON-VAN-HAKKARİ
“3” numaralı güzergahta; Erzurumdan (ADÜ olmayan düğüm) Ağrı’ya
(ADÜ) gidecek olan kişiler direkt olarak kara yolu ile Ağrı’ya gitmektedir.
“5” numaralı güzergahta; Bilecik’ten (ADÜ olmayan düğüm) Ardahan’a
(ADÜ olmayan düğüm) gidecek olan kişiler ilk olarak kara yoluyla Ankara’ya
81
(ADÜ), oradan hava yoluyla Kars’a (ADÜ), oradan kara yoluyla Ardahan’a
gitmektedirler.
“13” numaralı güzergahta; Kırklareli’den (ADÜ olmayan düğüm) Van’a
(ADÜ) gidecek olan kişiler, ilk olarak kara yoluyla İstanbul’a (ADÜ), oradan hava
yoluyla Van’a gitmektedirler.
“23” numaralı güzergahta; Muğla’dan (ADÜ) Hakkari’ye (ADÜ olmayan
düğüm) gidecek olan kişiler, ilk olarak hava yoluyla Şırnak’a (ADÜ), oradan kara
yoluyla Hakkari’ye gitmektedirler.
“32” numaralı güzergahta; Hakkari’den (ADÜ olmayan düğüm) Bitlis’e
(ADÜ olmayan düğüm) gidecek olan kişiler, ilk olarak kara yoluyla Van’a (ADÜ),
oradan tekrar kara yoluyla Bitlis’e gitmektedirler.
“35” numaralı güzergahta; Iğdır’dan (ADÜ) Ankara’ya (ADÜ) gidecek
olan kişiler, direkt olarak hava yoluyla Ankara’ya gitmektedirler.
Yukarıda
açıklanan
örneklerin
ve
Tablo-12’de
yer
alan
tüm
güzergahların ortak yönü; ADÜ olmayan kaynak noktalarından çıkan akışlar
için, gidilecek varış noktasının ADÜ veya ADÜ olmamasına bakılmaksızın ilk
olarak bir ADÜ’ye atanması, ADÜ olan kaynak noktalarından çıkan akışlar için
ise, gidilecek olan varış noktasına ya direkt olarak gitmesi, ya da ilave bir ADÜ
kullanarak gitmesidir.
Tablo-13’te model sonucunda, sistemde yer alan hangi iller arasında
ADÜ kullanmadan direkt olarak kara yolu ile gidiş olacağı sunulmuştur. Tablo13’te yer alan tüm kaynak-varış noktaları ADÜ olarak seçilmeyen illerdir.
82
Tablo-13 : ADÜ Kullanmadan Direkt Gidişe Müsaade Edilen Güzergahlar
Kaynak Noktası
ARTVİN
DİYARBAKIR
ERZİNCAN
Varış Noktası
ERZİNCAN
ARTVİN-ERZİNCAN
ERZURUM
ARTVİN-ERZURUM
ARDAHAN
ARTVİN-ARDAHAN
MARDİN
DİYARBAKIR-MARDİN
TUNCELİ
DİYARBAKIR-TUNCELİ
ERZURUM
ERZİNCAN-ERZURUM
TUNCELİ
ERZİNCAN
ERZURUM
GİRESUN
ORDU
ERZURUM-MARDİN
ERZURUM-TUNCELİ
ARDAHAN
ERZURUM-ARDAHAN
ERZİNCAN
GİRESUN-ERZİNCAN
ERZURUM
GİRESUN-ERZURUM
GÜMÜŞHANE-ERZİNCAN
ERZURUM
GÜMÜŞHANE-ERZURUM
DİYARBAKIR
ARDAHAN
MARDİN-DİYARBAKIR
ERZURUM
MARDİN-ERZURUM
ORDU-ERZİNCAN
ERZURUM
ORDU-ERZURUM
DİYARBAKIR
ARDAHAN
ORDU-TUNCELİ
RİZE-DİYARBAKIR
RİZE-ARDAHAN
TUNCELİ-DİYARBAKIR
ERZİNCAN
TUNCELİ-ERZİNCAN
ERZURUM
TUNCELİ-ERZURUM
DİYARBAKIR
BAYBURT
GÜMÜŞHANE-TUNCELİ
ERZİNCAN
DİYARBAKIR
TUNCELİ
GİRESUN-TUNCELİ
ERZİNCAN
TUNCELİ
RİZE
ERZURUM-ERZİNCAN
MARDİN
TUNCELİ
MARDİN
ERZİNCAN-TUNCELİ
TUNCELİ
TUNCELİ
GÜMÜŞHANE
Kullanılacak Güzergah
BAYBURT-DİYARBAKIR
ERZİNCAN
BAYBURT-ERZİNCAN
ERZURUM
BAYBURT-ERZURUM
ERZİNCAN
ARDAHAN-ERZİNCAN
Tablo-13’te yer alan güzergahlardan koyu renkle belirtilmiş olanların
nasıl gerçekleştiği aşağıda açıklanmıştır.
Erzurum’dan (ADÜ olarak seçilmeyen düğüm) Erzincan’a (ADÜ olarak
seçilmeyen düğüm) gidecek olan bir çalışan, ADÜ kullanmadan, Erzurum’dan
kara yoluyla direkt olarak Erzincan’a gidebilmektedir.
83
Ordu’dan (ADÜ olarak seçilmeyen düğüm) Tunceli’ye (ADÜ olarak
seçilmeyen düğüm) gidecek olan bir çalışan, ADÜ kullanmadan, Ordu’dan kara
yoluyla direkt olarak Tunceli’ye gidebilmektedir.
Geleneksel ADÜ yer seçim problemlerinin temel varsayımlarından biri,
akışların mutlaka ADÜ kullanma zorunluluğudur. Bu zorunluluğun gevşetilmesi
ile elde edilmiş olan sonuçlar vasıtasıyla, en iyi çözüm için, çalışanların ADÜ
olarak seçilmeyen hangi kaynak-varış çiftleri arasında kara yolu ile münferit
olarak gönderilmesi gerektiği Tablo-13’te belirtilmiştir.
d. İkinci Modelin Sonuçları
p-ADÜ medyan yapısındaki (seçilecek ADÜ sayısının modelleyici
tarafından belirlendiği) ikinci matematiksel model (CMApHLP), GAMS IDE
2.0.34.19 yazılımı ile kodlanmış ve CPLEX 10.1 çözücüsü ile p=2, 3,…35
sayıları için en iyi çözümlere ulaşılmıştır. Bu modelden elde edilen çözümler
vasıtasıyla karar verici;
 Her bir ADÜ sayısı için seçilen ADÜ’lerin,
 ADÜ’lere olan atamaların,
 Taşıma maliyetlerinin,
 ADÜ kullanmadan kara yolu ile direkt gidişlerin her bir alternatif ADÜ
sayısına göre nasıl değiştiğini gözlemleyebilmektedir.
Tablo-14’te her bir p değeri için (2, 3,…35) seçilen ADÜ’ler, amaç
fonksiyon değerleri ve çözüm süreleri sunulmuştur. Birinci matematiksel model
en iyi çözümü “35” ADÜ seçerek elde etmiştir. İkinci matematiksel model’in p=35
seçilmesi durumundaki sonuçları birinci matematiksel modelin sonuçları ile
aynıdır ve ikinci matematiksel modelin amaç fonksiyon değeri p=35’ten sonra
kötüleşmektedir. Dolayısıyla seçilecek olan p değerleri karar vericiye alternatif
çözümler sunmak için “2” den “35” e kadar belirlenmiştir.
84
Tablo-14: Her Bir p Değeri İçin Seçilen ADÜ’ler, Amaç Fonksiyon Değerleri ve
Çözüm Süreleri
P Sayısı
Seçilen ADÜ’ler
Amaç
Fonksiyon
Değeri
(₺)
2
İSTANBUL,VAN
72.731.063,3
1332,425
3
AĞRI,İSTANBUL,ŞIRNAK
38.378.668,4
1374,757
4
ERZURUM,İSTANBUL,VAN,ŞIRNAK
20.785.236,1
5832,131
5
ANKARA,DİYARBAKIR,KARS,SİİRT,VAN
2.245.788,5
1770,567
6
DİYARBAKIR,ERZİNCAN,KARS,KOCAELİ, SİİRT,VAN
2.168.628,3
1815,257
7
DİYARBAKIR,ERZİNCAN,KARS,KOCAELİ,KONYA,
VAN,ŞIRNAK
2.126.488,3
1339,875
8
DİYARBAKIR,ERZİNCAN,KARS,KOCAELİ,KONYA,
MUŞ,VAN,ŞIRNAK
2.097.487,9
1844,155
9
ELAZIĞ,ERZİNCAN,KARS,KOCAELİ,KONYA,MUŞ,
ŞANLIURFA,VAN,ŞIRNAK
2.075.697,6
2593,69
10
ELAZIĞ,ERZİNCAN,KARS,KOCAELİ,KONYA,MUŞ,
ŞANLIURFA,VAN,BATMAN,ŞIRNAK
2.055.494,2
2915,62
11
ANKARA,ELAZIĞ,ERZİNCAN,KARS,KOCAELİ,
KONYA,MUŞ,ŞANLIURFA,VAN,BATMAN,ŞIRNAK
2.036.989,6
1323,50
12
ANKARA,ELAZIĞ,ERZİNCAN,KARS,KOCAELİ,
SAMSUN,KONYA,MUŞ,ŞANLIURFA,VAN,BATMAN,
ŞIRNAK
2.027.923,7
1435,56
13
ADIYAMAN,ANKARA,ELAZIĞ,ERZİNCAN,KARS,
KASTAMONU,KOCAELİ,KONYA,MUŞ,ŞANLIURFA,
VAN,BATMAN,ŞIRNAK
2.019.131,9
1468,37
14
ADIYAMAN,ANKARA,ELAZIĞ,ERZİNCAN,KARS,
KASTAMONU,KOCAELİ,KONYA,SAMSUN,MUŞ,
ŞANLIURFA,VAN,BATMAN,ŞIRNAK
2.011.854,7
1268,23
15
ADANA,ADIYAMAN,ANKARA,ELAZIĞ,ERZİNCAN,
KARS,KASTAMONU,KOCAELİ,KONYA,MUŞ,
SAMSUNŞANLIURFA,VAN,BATMAN,ŞIRNAK
2.004.863,2
1321,99
16
ADANA,ADIYAMAN,ANKARA,ELAZIĞ,ERZİNCAN,
İZMİR,KARS,KASTAMONU,KOCAELİ,KONYA,MUŞ,
SAMSUN,ŞANLIURFA,VAN,BATMAN,ŞIRNAK
1.998.869,1
1437,50
17
ADANA,ADIYAMAN,ANKARA,ANTALYA,ELAZIĞ,
ERZİNCAN,İZMİR,KARS,KASTAMONU,KAYSERİ,
KOCAELİ,MUŞ,SAMSUN,ŞANLIURFA,VAN,
BATMAN,ŞIRNAK
1.994.036,0
1514,41
18
ADANA,ADIYAMAN,AĞRI,ANKARA,ANTALYA,
ELAZIĞ,ERZURUM,İZMİR,KARS,KASTAMONU,
KAYSERİ,KOCAELİ,MUŞ,SAMSUN,ŞANLIURFA,
VAN,BATMAN,ŞIRNAK
1.989.843,6
1791,48
85
Çözüm
Süresi
(sn.)
Tablo-14’ün devamı: Her Bir p Değeri İçin Seçilen ADÜ’ler, Amaç Fonksiyon
Değerleri ve Çözüm Süreleri
P Sayısı
Seçilen ADÜ’ler
Amaç
Fonksiyon
Değeri
(₺)
19
ADANA,ADIYAMAN,AĞRI,ANKARA,ANTALYA,
ELAZIĞ,ERZURUM,İZMİR,KARS,KASTAMONU,
KAYSERİ,KOCAELİ,KONYA,MUŞ,SAMSUN,
ŞANLIURFA,VAN,BATMAN,ŞIRNAK
1.986.283,8
1852,73
20
ADANA,ADIYAMAN,AĞRI,ANKARA,ANTALYA,
BURSA,ELAZIĞ,ERZURUM,İZMİR,KARS,
KASTAMONU,KAYSERİ,KOCAELİ,KONYA,MUŞ,
SAMSUN,ŞANLIURFA,VAN,BATMAN,ŞIRNAK
1.983.085,6
1699,28
21
ADANA,ADIYAMAN,AĞRI,ANKARA,ANTALYA,
BURSA,DENİZLİ,ELAZIĞ,ERZURUM,İZMİR,KARS,
KASTAMONU,KAYSERİ,KOCAELİ,KONYA,MUŞ,
SAMSUN,ŞANLIURFA,VAN,BATMAN,ŞIRNAK
1.980.566,2
1264,65
22
ADANA,ADIYAMAN,ANKARA,ANTALYA,BİNGÖL,
BURSA,ERZİNCAN,İZMİR,KARS,KASTAMONU,
KAYSERİ,KOCAELİ,KONYA,MALATYA,MUŞ,
SAMSUN,TRABZON,ŞANLIURFA,VAN,BATMAN,
ŞIRNAK,IĞDIR
1.977.685,1
1241,96
23
ADANA,ADIYAMAN,ANKARA,ANTALYA,BİNGÖL,
BURSA,DENİZLİ,ERZİNCAN,İZMİR,KARS,
KASTAMONU,KAYSERİ,KOCAELİ,KONYA,MALATYA,
MUŞ,SAMSUN,TRABZON,ŞANLIURFA,VAN,
BATMAN,ŞIRNAK,IĞDIR
1.975.068,4
766,05
24
ADANA,ADIYAMAN,ANKARA,ANTALYA,BİNGÖL,
BURSA,DENİZLİ,ERZİNCAN,İZMİR,KARS,
KASTAMONU,KAYSERİ,KOCAELİ,KONYA,MALATYA,
MUŞ,SAMSUN,SİVAS,TRABZON,ŞANLIURFA,
VAN,BATMAN,ŞIRNAK,IĞDIR
1.973.391,3
808,20
25
ADANA,ADIYAMAN,AĞRI,AMASYA,ANKARA,
ANTALYA,BİNGÖL,BURSA,DENİZLİ,ELAZIĞ,
GAZİANTEP,İZMİR,KARS,KASTAMONU,KAYSERİ,
KOCAELİ,KONYA,MUŞ,SAMSUN,SİVAS,TRABZON,
ŞANLIURFA,VAN,BATMAN,ŞIRNAK
1.971.889,7
554,92
26
ADANA,ADIYAMAN,AĞRI,AMASYA,ANKARA,
ANTALYA,BİNGÖL,BURSA,DENİZLİ,ELAZIĞ,
GAZİANTEP,İZMİR,KARS,KASTAMONU,KAYSERİ,
KOCAELİ,KONYA,MUŞ,SAMSUN,SİVAS,TRABZON,
ŞANLIURFA,VAN,BATMAN,ŞIRNAK,IĞDIR
1.970.354,8
488,48
27
ADANA,ADIYAMAN,AĞRI,AMASYA,ANKARA,
ANTALYA,BİNGÖL,BURSA,DENİZLİ,ELAZIĞ,
GAZİANTEP,İZMİR,KARS,KASTAMONU,KAYSERİ,
KOCAELİ,KONYA,KÜTAHYA,MUŞ,SAMSUN,SİVAS,
TRABZON,ŞANLIURFA,VAN,BATMAN,ŞIRNAK,
IĞDIR
1.969.196,0
424,43
28
ADANA,ADIYAMAN,AĞRI,AMASYA,ANKARA,
ANTALYA,BİNGÖL,BURSA,DENİZLİ,ELAZIĞ,
GAZİANTEP,HATAY,İZMİR,KARS,KASTAMONU,
KAYSERİ,KOCAELİ,KONYA,KÜTAHYA,MUŞ,
SAMSUN,SİVAS,TRABZON,ŞANLIURFA,VAN,
BATMAN,ŞIRNAK,IĞDIR
1.968.043,7
333,54
86
Çözüm
Süresi
(sn.)
Tablo-14’ün devamı: Her Bir p Değeri İçin Seçilen ADÜ’ler, Amaç Fonksiyon
Değerleri ve Çözüm Süreleri
P Sayısı
Seçilen ADÜ’ler
Amaç
Fonksiyon
Değeri
(₺)
30
ADANA,ADIYAMAN,AĞRI,AMASYA,ANKARA,
ANTALYA,BİNGÖL,BURSA,DENİZLİ,ELAZIĞ,
GAZİANTEP,HATAY,İZMİR,KARS,KASTAMONU,
KAYSERİ,KOCAELİ,KONYA,KÜTAHYA,
KAHRAMANMARAŞ,MUĞLA,MUŞ,SAMSUN,SİVAS,
TRABZON,ŞANLIURFA,VAN,BATMAN,ŞIRNAK,
IĞDIR
1.966.614,3
210,07
31
ADANA,ADIYAMAN,AĞRI,AMASYA,ANKARA,
ANTALYA,BİNGÖL,BURSA,DENİZLİ,ELAZIĞ,
GAZİANTEP,HATAY,İSTANBUL,İZMİR,KARS,
KASTAMONU,KAYSERİ,KOCAELİ,KONYA,
KÜTAHYA,KAHRAMANMARAŞ,MUĞLA,MUŞ,
SAMSUN,SİVAS,TRABZON,ŞANLIURFA,VAN,
BATMAN,ŞIRNAK,IĞDIR
1.966.034,3
213,78
32
ADANA,ADIYAMAN,AĞRI,AMASYA,ANKARA,
ANTALYA,BİNGÖL,BURSA,DENİZLİ,ELAZIĞ,
GAZİANTEP,HATAY,İSTANBUL,İZMİR,KARS,
KASTAMONU,KAYSERİ,KOCAELİ,KONYA,
KÜTAHYA,KAHRAMANMARAŞ,MUĞLA,MUŞ,
SAMSUN,SİVAS,TOKAT,TRABZON,ŞANLIURFA,
VAN,BATMAN,ŞIRNAK,IĞDIR
1.965.620,2
155,56
33
ADANA,ADIYAMAN,AĞRI,AMASYA,ANKARA,
ANTALYA,BİNGÖL,BURSA,DENİZLİ,ELAZIĞ,
GAZİANTEP,HATAY,İSTANBUL,İZMİR,KARS,
KASTAMONU,KAYSERİ,KOCAELİ,KONYA,
KÜTAHYA,KAHRAMANMARAŞ,MUĞLA,MUŞ,
SAMSUN,SİİRT,SİVAS,TOKAT,TRABZON,
ŞANLIURFA,VAN,BATMAN,ŞIRNAK,IĞDIR
1.965.344,6
144,24
34
ADANA,ADIYAMAN,AĞRI,AMASYA,ANKARA,
ANTALYA,BİNGÖL,BURSA,DENİZLİ,ELAZIĞ,
GAZİANTEP,HATAY,İSTANBUL,İZMİR,KARS,
KASTAMONU,KAYSERİ,KOCAELİ,KONYA,
KÜTAHYA,MALATYA,KAHRAMANMARAŞ,MUĞLA,
MUŞ,SAMSUN,SİİRT,SİVAS,TOKAT,TRABZON,
ŞANLIURFA,VAN,BATMAN,ŞIRNAK,IĞDIR
1.965.136,5
116,11
35
ADANA,ADIYAMAN,AĞRI,AMASYA,ANKARA,
ANTALYA,BİNGÖL,BURSA,DENİZLİ,ELAZIĞ,
GAZİANTEP,HATAY,İSTANBUL,İZMİR,KARS,
KASTAMONU,KAYSERİ,KOCAELİ,KONYA,
KÜTAHYA,MALATYA,KAHRAMANMARAŞ,MUĞLA,
MUŞ,NEVŞEHİR,SAMSUN,SİİRT,SİVAS,TOKAT,
TRABZON,ŞANLIURFA,VAN,BATMAN,ŞIRNAK,
IĞDIR
1.964.973,8
109,12
87
Çözüm
Süresi
(sn.)
Tablo-14 incelendiğinde;
Amaç fonksiyon değerlerinin, kaynak-varış çiftleri arasındaki akışların
“2”, “3” ve “4” ADÜ ile gerçekleştirildiği durumlarda, diğer alternatiflerin amaç
fonksiyon değerlerine göre çok yüksek çıktığı, çözüm süreleri açısından
bakıldığında ise “4” ADÜ seçildiği durumun en uzun çözüm süresine sahip
olduğu ve p=23’ten sonra çözüm süresinin büyük oranda düşüş gösterdiği
görülmektedir.
Her bir alternatif için seçilen ADÜ’ler incelendiğinde, matematiksel
modelin Balıkesir, Isparta ve Tekirdağ havaalanlarını hiçbir p değeri için ADÜ
olarak seçmediği görülmektedir.
Belirlenen hattın doğusundaki Şırnak havaalanı “34” alternatifin
33’ünde, Van havaalanı ise 31’inde, hattın batısındaki Kocaeli havaalanı “34”
alternatifin 30’unda matematiksel model tarafından ADÜ olarak belirlenmiştir.
Dolayısıyla Şırnak, Van ve Kocaeli havaalanlarının kritik öneme sahip olduğu tespit
edilmiştir.
Tablo-15’te ikinci matematiksel modelde örnek p=21 için ADÜ olarak
seçilen iller ve diğer illerin hangi ADÜ’leri kullanacağı sunulmuştur.
Tablo-15: p=21 İçin ADÜ Olarak Seçilen İller ve Diğer İllerin Hangi ADÜ’leri
Kullanacağını Gösteren Çizelge
Plaka
Kodu
İller
1
ADANA
33
MERSİN
70
KARAMAN
51
NİĞDE
68
AKSARAY
21
DİYARBAKIR
24
ERZİNCAN
47
MARDİN
2
ADIYAMAN
21
DİYARBAKIR
46
KAHRAMANMARAŞ
47
MARDİN
62
TUNCELİ
Atandığı ADÜ
ADANA
ADIYAMAN
88
Tablo-15’in devamı: p=21 İçin ADÜ Olarak Seçilen İller ve Diğer İllerin Hangi
ADÜ’leri Kullanacağını Gösteren Çizelge
Plaka
Kodu
İller
4
AĞRI
76
IĞDIR
6
ANKARA
3
AFYON
11
BİLECİK
14
BOLU
24
ERZİNCAN
26
ESKİŞEHİR
43
KÜTAHYA
54
SAKARYA
64
UŞAK
67
ZONGULDAK
81
DÜZCE
7
ANTALYA
15
BURDUR
48
MUĞLA
16
BURSA
10
BALIKESİR
17
ÇANAKKALE
20
DENİZLİ
9
AYDIN
48
MUĞLA
23
ELAZIĞ
5
AMASYA
12
BİNGÖL
19
ÇORUM
21
DİYARBAKIR
24
ERZİNCAN
27
GAZİANTEP
31
HATAY
44
MALATYA
46
KAHRAMANMARAŞ
47
MARDİN
58
SİVAS
60
TOKAT
62
TUNCELİ
66
YOZGAT
79
KİLİS
80
OSMANİYE
Atandığı ADÜ
AĞRI
ANKARA
ANTALYA
BURSA
DENİZLİ
ELAZIĞ
89
Tablo-15’in devamı: p=21 İçin ADÜ Olarak Seçilen İller ve Diğer İllerin Hangi
ADÜ’leri Kullanacağını Gösteren Çizelge
Plaka
Kodu
İller
25
ERZURUM
5
AMASYA
8
ARTVİN
12
BİNGÖL
18
ÇANKIRI
19
ÇORUM
21
DİYARBAKIR
24
ERZİNCAN
28
GİRESUN
29
GÜMÜŞHANE
47
MARDİN
52
ORDU
53
RİZE
58
SİVAS
60
TOKAT
61
TRABZON
62
TUNCELİ
66
YOZGAT
69
BAYBURT
75
ARDAHAN
35
İZMİR
45
MANİSA
36
KARS
8
ARTVİN
75
ARDAHAN
76
IĞDIR
37
KASTAMONU
18
ÇANKIRI
67
ZONGULDAK
74
BARTIN
78
KARABÜK
38
KAYSERİ
18
ÇANKIRI
24
ERZİNCAN
40
KIRŞEHİR
50
NEVŞEHİR
51
NİĞDE
66
YOZGAT
68
AKSARAY
70
KARAMAN
71
KIRIKKALE
Atandığı ADÜ
ERZURUM
İZMİR
KARS
KASTAMONU
KAYSERİ
90
Tablo-15’in devamı: p=21 İçin ADÜ Olarak Seçilen İller ve Diğer İllerin Hangi
ADÜ’leri Kullanacağını Gösteren Çizelge
Plaka
Kodu
41
22
24
34
39
54
59
77
42
3
10
15
32
43
64
49
12
13
21
55
24
57
62
63
21
27
31
46
47
62
79
80
65
13
30
56
72
13
21
47
56
73
30
47
56
İller
Atandığı ADÜ
KOCAELİ
EDİRNE
ERZİNCAN
İSTANBUL
KIRKLARELİ
SAKARYA
TEKİRDAĞ
YALOVA
KONYA
AFYON
BALIKESİR
BURDUR
ISPARTA
KÜTAHYA
UŞAK
MUŞ
BİNGÖL
BİTLİS
DİYARBAKIR
SAMSUN
ERZİNCAN
SİNOP
TUNCELİ
ŞANLIURFA
DİYARBAKIR
GAZİANTEP
HATAY
KAHRAMANMARAŞ
MARDİN
TUNCELİ
KİLİS
OSMANİYE
VAN
BİTLİS
HAKKARİ
SİİRT
BATMAN
BİTLİS
DİYARBAKIR
MARDİN
SİİRT
ŞIRNAK
HAKKARİ
MARDİN
SİİRT
KOCAELİ
KONYA
MUŞ
SAMSUN
ŞANLIURFA
VAN
BATMAN
ŞIRNAK
91
Tablo-15
incelendiğinde,
matematiksel
modelin,
aday
ADÜ
konumundaki Amasya, Balıkesir, Bingöl, Diyarbakır, Erzincan, Gaziantep,
Hatay, Isparta, İstanbul, Kütahya, Malatya, Kahramanmaraş, Mardin, Muğla,
Nevşehir, Siirt, Sivas, Tekirdağ, Tokat, Trabzon, Iğdır havaalanlarını
kullanmadan kaynak-varış çiftleri arasındaki akışları gerçekleştirdiği ve en iyi
çözüme ulaştığı görülmektedir.
Kurum, işletilmekte olan sistemde “21” adet havaalanı kullanmaktadır.
p=21 seçilerek elde edilen ADÜ’lerin yerleri incelendiğinde;
 Kurumun halihazırda kullanmakta olduğu Adana, Ankara, Antalya,
İzmir, Samsun, Elazığ, Erzurum, Ağrı, Kars, Muş, Van, Batman, Şırnak
havaalanlarının model tarafından da seçildiği;
 Amasya, Bingöl, Sivas, Tokat, Hatay, İstanbul, Diyarbakır, Iğdır
havaalanlarının ise model tarafından seçilmediği,
 Bu havaalanlarının yerine Adıyaman, Bursa, Denizli, Kastamonu,
Kayseri, Kocaeli, Konya, Şanlıurfa havaalanlarının ADÜ olarak seçildiği
görülmektedir.
Tablo-15, ADÜ’lerin kullanım yoğunluğu açısından incelendiğinde,
Erzurum ADÜ’sünün en fazla il tarafından kullanılan ADÜ olduğu göze
çarpmaktadır. Diğer önemli bir konu ise, birinci matematiksel modelin
sonuçlarında Erzurum ADÜ olarak seçilmezken, ikinci matematiksel modelin
sonuçlarında en fazla kullanılan ADÜ olarak seçilmesidir. Bunun sebebi; ADÜ
yer seçim problemlerinde atama kararlarının yer seçimlerinden, yer seçim
kararlarının da atama kararlarından önemli derecede etkilenmesidir.
Kurum, işletilmekte olan mevcut sistemin maliyetini söylemekten
kaçındığı için p=21 için oluşan toplam maliyeti mevcut sistemin ulaştırma
maliyetle karşılaştırmak mümkün olmamıştır.
Birinci matematiksel modelin sonuçları ile, ikinci matematiksel modelde
p=35 seçildiğinde elde edilen sonuçlar karşılaştırıldığında; her iki modelin aynı
92
amaç fonksiyon değerini bulduğu, aynı ADÜ’leri seçtiği, seçilen ADÜ’lere aynı
atamaları yaptığı ve kaynak-varış çiftleri arasındaki akışları aynı güzergahları
kullanarak gerçekleştirdiği görülmüştür.
Tablo-16’da karar vericinin isteği doğrultusunda model tarafından
belirlenmiş olan “21” adet ADÜ’nün herbiri için modelde yer alması muhtemel
yolları gösterecek şekilde birer örnek güzergah sunulmuştur.
Tablo 16 : p=21 İçin Örnek Güzergahlar
Sıra
No
Çıkış Noktası
İlk Atanacağı ADÜ
Varış Noktası
1.
MERSİN
ADANA
AĞRI
2.
ADIYAMAN
ADIYAMAN
BİTLİS
ADIYAMAN-BATMAN-BİTLİS
3.
ERZURUM
ERZURUM
AĞRI
ERZURUM-AĞRI
4.
BİLECİK
ANKARA
ARDAHAN
5.
KIRKLARELİ
KOCAELİ
VAN
KIRKLARELİ-KOCAELİ-VAN
6.
BALIKESİR
BURSA
MUŞ
BALIKESİR-BURSA-MUŞ
7.
AYDIN
DENİZLİ
BİTLİS
AYDIN-DENİZLİ-MUŞ-BİTLİS
8.
TUNCELİ
ELAZIĞ
ANTALYA
TUNCELİ-ELAZIĞ-ANTALYA
9.
AMASYA
AMASYA
ERZURUM
AMASYA-ERZURUM
10.
MUĞLA
ANTALYA
HAKKARİ
MUĞLA-ANTALYA-ŞIRNAK-HAKKARİ
11.
ARDAHAN
KARS
KARS
ARDAHAN-KARS
12
KARABÜK
KASTAMONU
AĞRI
KARABÜK-KASTAMONU-AĞRI
13.
KARAMAN
KAYSERİ
BİNGÖL
14.
HAKKARİ
VAN
BİTLİS
HAKKARİ-VAN-BİTLİS
15.
ISPARTA
KONYA
IĞDIR
ISPARTA-KONYA-AĞRI-IĞDIR
16.
IĞDIR
AĞRI
ANKARA
IĞDIR-AĞRI-ANKARA
17.
SAMSUN
SAMSUN
MARDİN
SAMSUN-MARDİN
18.
TUNCELİ
ŞANLIURFA
ŞANLIURFA
TUNCELİ-ŞANLIURFA
19.
HAKKARİ
VAN
BİTLİS
HAKKARİ-VAN-BİTLİS
20.
BİTLİS
BATMAN
ADANA
BİTLİS-BATMAN-ADANA
21.
HAKKARİ
ŞIRNAK
ANTALYA
Kullanılacak Güzergâh
MERSİN-ADANA-AĞRI
BİLECİK-ANKARA-ERZURUM-ARDAHAN
KARAMAN-KAYSERİ-ELAZIĞ-BİNGÖL
HAKKARİ-ŞIRNAK-ANTALYA
Örnek güzergahlar Tablo-12’de örnek olarak seçilip açıklanan kaynakvarış noktaları ile aynı olacak şekilde seçilmiş ve p=21 ile ADÜ sayısının model
tarafından belirlendiği yerleştirme-atama kararları arasındaki farklılıklar aşağıda
açıklanmıştır.
93
“3” numaralı güzergahta; Erzurumdan (ADÜ) Ağrı’ya (ADÜ) gidecek
olan kişiler direkt olarak hava yolu ile Ağrı’ya gitmektedir. Tablo-12’de aynı
güzergah kara yolu ile direkt gidiş olarak belirlenmiştir. Aradaki farkın sebebi,
Erzurum’un Tablo-16’da ADÜ, Tablo-12’de ADÜ olmayan düğüm olmasıdır.
“4” numaralı güzergahta; Bilecik’ten (ADÜ olmayan düğüm) Ardahan’a
(ADÜ olmayan düğüm) gidecek olan kişiler ilk olarak kara yoluyla Ankara’ya
(ADÜ), oradan hava yoluyla Erzurum’a (ADÜ), oradan kara yoluyla Ardahan’a
gitmektedirler.
Tablo-12’de
Bilecik-Ankara-Kars-Ardahan
güzergahı
kullanılmıştır. Aradaki fark, Tablo-12’de Ankara ve Kars ADÜ’lerinin, Tablo16’da Ankara-Erzurum ADÜ’lerinin kullanılmasıdır.
“5” numaralı güzergahta; Kırklareli’den (ADÜ olmayan düğüm) Van’a
(ADÜ) gidecek olan kişiler, ilk olarak kara yoluyla Kocaeli’ye (ADÜ), oradan
hava
yoluyla
Van’a
gitmektedirler.
Tablo-12’de
Kırklareli-İstanbul-Van
güzergahı kullanılmıştır. Aradaki fark, Tablo-12’de İstanbul-Van ADÜ’lerinin,
Tablo-16’da Kocaeli-Van ADÜ’lerinin kullanılmasıdır.
“10”
numaralı
güzergahta;
Muğla’dan
(ADÜ
olmayan
düğüm)
Hakkari’ye (ADÜ olmayan düğüm) gidecek olan kişiler, ilk olarak kara yoluyla
Antalya’ya (ADÜ), oradan hava yoluyla Şırnak’a (ADÜ), oradan kara yoluyla
Hakkari’ye
gitmektedirler.
Tablo-12’de
Muğla-Şırnak-Hakkari
güzergahı
kullanılmıştır. Aradaki fark, Muğlanın Tablo-12’de ADÜ, Tablo-15’te ADÜ olarak
seçilmemesinden kaynaklanmaktadır. Bu sebeple Tablo-16’da Muğla ilk olarak,
ADÜ olarak seçilen Antalya’ya atanmıştır.
“14” numaralı güzergahta; Hakkari’den (ADÜ olmayan düğüm) Bitlis’e
(ADÜ olmayan düğüm) gidecek olan kişiler, ilk olarak kara yoluyla Van’a (ADÜ),
oradan tekrar kara yoluyla Bitlis’e gitmektedirler. Tablo-12’de de aynı güzergah
kullanılmaktadır.
“16” numaralı güzergahta; Iğdır’dan (ADÜ) Ankara’ya (ADÜ) gidecek
olan kişiler, ilk olarak kara yoluyla Ağrı’ya (ADÜ), oradan
hava yoluyla
Ankara’ya gitmektedirler. Tablo-12’de Iğdır-Ankara güzergahı kullanılmıştır.
94
Aradaki
Iğdır’ın
fark,
Tablo-12’de
ADÜ,
Tablo-16’da
ADÜ
olarak
seçilmemesinden kaynaklanmaktadır. Bu sebeple Iğdır ilk olarak, ADÜ olarak
seçilen Ağrı’ya atanmıştır.
Yukarıda açıklanan örnek güzergahlar vasıtasıyla, ADÜ yer seçim
problemlerinde; ADÜ yer seçimlerinin atama kararlarını, atama kararlarının da
yer seçim kararlarını etkilediği gözler önüne serilmiş ve herhangi bir düğümün
ADÜ olarak seçilmesi ya da seçilmemesinin kullanılacak güzergahları nasıl
etkilediği açıklanmaya çalışılmıştır.
Tablo-17’de eksojen modelde p=21 seçilmesi durumunda, sistemde yer
alan hangi iller arasında ADÜ kullanmadan direkt olarak kara yolu ile gidiş
olacağı sunulmuştur. Tablo-17’de yer alan tüm kaynak-varış noktaları ADÜ
olmayan illerdir.
Tablo-17: p=21 İçin ADÜ Kullanmadan Direkt Gidişe Müsaade Edilen
Güzergahlar
Kaynak Noktası
AMASYA
ARTVİN
BİNGÖL
BİTLİS
ÇORUM
DİYARBAKIR
Varış Noktası
ERZİNCAN
AMASYA-TUNCELİ
ARDAHAN
ARTVİN-ARDAHAN
DİYARBAKIR
TUNCELİ
SİİRT
ERZİNCAN
GÜMÜŞHANE
BİNGÖL-DİYARBAKIR
BİNGÖL-TUNCELİ
BİTLİS-SİİRT
ÇORUM-ERZİNCAN
TUNCELİ
ÇORUM-TUNCELİ
BİNGÖL
DİYARBAKIR-BİNGÖL
MARDİN
DİYARBAKIR-MARDİN
TUNCELİ
DİYARBAKIR-TUNCELİ
AMASYA
ERZİNCAN-AMASYA
BOLU
GİRESUN
AMASYA-ERZİNCAN
TUNCELİ
ÇANKIRI
ERZİNCAN
Kullanılacak Güzergah
SAKARYA
ERZİNCAN-BOLU
ERZİNCAN-ÇANKIRI
ERZİNCAN-SAKARYA
SİVAS
ERZİNCAN-SİVAS
TOKAT
ERZİNCAN-TOKAT
TRABZON
ERZİNCAN-TRABZON
TUNCELİ
ERZİNCAN-TUNCELİ
ERZİNCAN
GİRSUN-ERZİNCAN
TUNCELİ
GİRESUN-TUNCELİ
ERZİNCAN
TUNCELİ
95
GÜMÜŞHANE-ERZİNCAN
GÜMÜŞHANE-TUNCELİ
Tablo-17’nin devamı: p=21 için ADÜ Kullanmadan Direkt Gidişe Müsaade
Edilen Güzergahlar
Kaynak Noktası
Varış Noktası
MARDİN
DİYARBAKIR
ORDU
ERZİNCAN
TUNCELİ
DİYARBAKIR
RİZE
ERZİNCAN
TUNCELİ
ARDAHAN
SİİRT
BİTLİS
SİNOP
TUNCELİ
SİVAS
TOKAT
TRABZON
TUNCELİ
ERZİNCAN
TUNCELİ
ERZİNCAN
TUNCELİ
ERZİNCAN
BAYBURT
MARDİN-DİYARBAKIR
ORDU-ERZİNCAN
ORDU-TUNCELİ
RİZE-DİYARBAKIR
RİZE-ERZİNCAN
RİZE-TUNCELİ
RİZE-ARDAHAN
SİİRT-BİTLİS
SİNOP-TUNCELİ
SİVAS-ERZİNCAN
SİVAS-TUNCELİ
TOKAT-ERZİNCAN
TOKAT-TUNCELİ
TRABZON-ERZİNCAN
TUNCELİ
TRABZON-TUNCELİ
AMASYA
TUNCELİ-AMASYA
BİNGÖL
TUNCELİ-BİNGÖL
DİYARBAKIR
ERZİNCAN
SİVAS
YOZGAT
Kullanılacak Güzergah
TUNCELİ-DİYARBAKIR
TUNCELİ-ERZİNCAN
TUNCELİ-SİVAS
TRABZON
TUNCELİ-TRABZON
ERZİNCAN
YOZGAT-ERZİNCAN
TUNCELİ
ERZİNCAN
YOZGAT-TUNCELİ
BAYBURT-ERZİNCAN
Aşağıda, Tablo-13’te yer alan direkt gidiş güzergahları ile Tablo-17’de
yer alan direkt gidiş güzergahlarının karşılaştırması yapılmıştır.
Tablo-13’te ADÜ olarak seçilmeyen “12” farklı kaynak noktasından,
ADÜ olarak seçilmeyen “6” farklı varış noktasına “31” kaynak-varış çifti arasında
kara yolu ile direkt gidiş bulunmaktadır. Tablo-17’de ise ADÜ olarak seçilmeyen
“20” farklı kaynak noktasından,
noktasına
ADÜ olarak seçilmeyen “15” farklı varış
“47” kaynak-varış çifti arasında kara yolu ile direkt gidiş
bulunmaktadır. Bu sonuçların ve değişik p sayılarının çözümlerinin incelenmesi
neticesinde; seçilen ADÜ sayısının azalmasının, direkt gidiş olan kaynak-varış
çift sayısının artmasına sebep olduğu gözlemlenmiştir.
96
Tablo-13’te Erzurum ve Ardahan arasında ADÜ kullanmadan direkt
gidişe müsaade edildiği görülmektedir. p=21 için Erzurum ADÜ olarak
seçildiğinden, Erzurum-Ardahan arasındaki ulaşım direkt olarak kara yolu ile
gidişten daha az maliyetli bir yol ile ADÜ kullanarak gerçekleştirilmektedir.
Tablo-13 ve Tablo-17’de yer alan kara yolu ile direkt gidişlerdeki varış
noktaları incelendiğinde ise, Tablo-13’te kaynak noktalarının herbirinden en
fazla “4” varış noktasına direkt gidiş var iken, Tablo-17’de bu sayının “8” varış
noktasına kadar çıktığı gözlemlenmiştir.
97
DÖRDÜNCÜ BÖLÜM
SONUÇ VE ÖNERİLER
1. SONUÇ
Yerleştirme ve atama problemlerinin özel bir çeşidi olan ana dağıtım
üslerinin (ADÜ) konumu (hub location) araştırmaları, son yıllarda yerleşim
teorisinin önemli bir araştırma alanı haline gelmiştir. Modern ulaştırma ve
iletişim sistemlerinin büyük bir kısmında ADÜ ağlarının kullanılması, bu
alandaki araştırmaların öneminin artmasına sebep olmuştur. Bu sistemler,
ölçek ekonomisinin söz konusu olduğu kaynak-varış çiftleri arasındaki seyahat
veya iletişim işlemlerinin ekonomik şekilde gerçekleşmesini sağlarlar.
ADÜ problemlerinde, birbirleriyle iletişim halinde olan düğümlerden
oluşmuş bir ağ söz konusudur. İletişimden kastedilen, bir çok kaynak-varış çifti
arasındaki akıştır. ADÜ’ler kaynak-varış çiftleri arasındaki akışlar için aktarma
ve birleştirme noktaları olarak hizmet verirler. Bir ADÜ, bir çok ayrı küçük akışı
daha büyük akışlara yönlendirir veya birleştirir. ADÜ yer seçim problemlerinin
ulaştırma (hava yolu ile seyahat, hava yolu ile nakliyat, bir gecelik dağıtım
sistemleri, posta dağıtımı, vs.) ve telekomünikasyon (bilgisayar iletişimi,
telefon
ağları
vs.)
alanlarında
bir
çok
uygulamaları
bulunmaktadır.
Günümüzde, bu alanlarda faaliyet gösteren birçok kurum ve kuruluş,
uygulamalarında, ADÜ ağ tasarımını etkin bir şekilde kullanmaktadır.
Bu çalışmada, dönemsel olarak çalışanlarının bir bölümünü belirli
noktalar arasında taşıtması gereken bir kamu kurumuna yönelik gerçek bir
ana dağıtım üssü yer seçim problemi ele alınmıştır. Bu problem, kamu kurumu
tarafından işletilmekte olan mevcut taşıma sisteminin, kurumun ihtiyaçlarına
tam ve ekonomik olarak cevap verememesinden kaynaklanmaktadır. Kurum
yönetimimin, yeni sistemden beklentilerinin ortaya konulmasını müteakip,
literatürde yapılan inceleme neticesinde, ADÜ yer seçim problemlerinin
çözümü için geliştirilen matematiksel modellerin ele alınan problemin temel
98
karakteristiklerini karşılamada yetersiz kaldığı görülmüştür. Bu çalışmada, ele
alınan problemin yapısına uygun olarak, literatürde yer alan ADÜ yer seçim
problemlerine yeni bir boyut kazandırılmıştır.
Problem, şebekedeki düğümler arasındaki mesafelerde üçgensel
eşitsizliğin olmadığı, kesikli uzayda yer alan, çok atamalı, ADÜ olarak
seçilmeyen kaynak-varış çiftleri arasındaki akışlarda ADÜ kullanmadan direkt
gidişe müsaade eden, ADÜ olarak seçilen düğümlerin kapasitelerini, hem
ADÜ, hemde ADÜ olarak seçilmeyen düğümlerden gelen akışıların etkilediği
ADÜ yer seçim problemi olarak tasarlanmıştır. Çalışmada, literatürde yer alan
sabit maliyetli, çok atamalı, kapasite kısıtlı yapıya sahip bir matematiksel
modelden (Marin, 2005a) hareketle, problemin gereksinimlerine özgü iki yeni
matematiksel model geliştirilmiştir. Geliştirilen matematiksel modellerin en
önemli farkı; birinci matematiksel modelde seçilecek ADÜ sayısının model
tarafından,
ikinci
matematiksel
modelde
ise
karar
verici
tarafından
belirlenmesidir. Birinci matematiksel model yardımıyla şu sorulara cevaplar
aranmıştır:
 Sistemde kaç adet ADÜ açılmalıdır?
 ADÜ’ler nerelere açılmalıdır?
 Mevcut sistemde kullanılan hangi ADÜ’ler kapatılmalıdır?
 ADÜ olarak seçilmeyen düğümler hangi ADÜ’lere atanmalıdır?
 Hangi düğümler arasında ADÜ kullanmadan kara yolu ile direkt
gidişe müsaade edilmelidir?
İkinci matematiksel model yardımıyla, kullanıcı tarafından belirlenen
değişik ADÜ sayıları için (p=2,3,..,42), sistemde kaç adet ADÜ açılması hariç,
yukarıda yer alan sorulara cevaplar aranmıştır.
Literatürde, ADÜ yer seçim problemleri ile ilgili pek çok çalışmaya
rastlamak mümkündür. Bu çalışmayı diğerlerinden ayıran yönleri:
99
 Eğer daha ekonomik ise, ADÜ olarak seçilmeyen kaynak-varış
çiftleri arasındaki akışlarda, ADÜ kullanmadan direkt gidişe müsaade edilmesi,
 ADÜ olarak seçilen düğümlerin kapasitesini hem ADÜ’ lerden
gelen, hem de ADÜ olarak seçilmeyen düğümlerden gelen akışların
etkilemesi,
 ADÜ olarak seçilen düğümlerin sabit kuruluş maliyetine sahip
olmaması,
 Tasarlanan şebekedeki düğümler arasındaki mesafelerde üçgensel
eşitsizliğin bulunmamasıdır.
Seçilecek ADÜ sayısının matematiksel model tarafından belirlendiği
birinci matematiksel modelin çözümü sonucunda; aday ADÜ konumundaki
“42” adet havaalanından “35” tanesi ADÜ olarak belirlenmiş ve en iyi çözüme
ulaşılmıştır. Aday ADÜ konumundaki Balıkesir, Diyarbakır, Erzincan, Erzurum,
Isparta, Mardin ve Tekirdağ havaalanları ise ADÜ olarak belirlenmemiştir.
Seçilecek ADÜ sayısının modelleyici tarafından belirlendiği ikinci
matematiksel modelin çözümü sonucunda; değişik ADÜ sayıları (p=2, 3,…,
35) için en iyi çözümler elde edilmiş ve kuruma değişik alternatifler için çözüm
önerileri sunulmuştur. Kurum; bu çözümler vasıtasıyla, her bir alternatif ADÜ
sayısı için seçilen ADÜ’lerin yerlerinin, ADÜ’lere olan atamaların ve ADÜ
olarak seçilmeyen iller arasında ADÜ kullanmadan kara yolu ile direkt gidişlerin
nasıl değiştiğini görebilmektedir.
Kamu kurumunun istekleri ve kurum yönetiminden elde edilen bilgiler
ışığında problemin çözümü için iki matematiksel model kullanılması, yönetime
farklı seçenekler için
karar verme
imkanı sunmuştur. Yönetim
bu
şeçeneklerden birisini tercih ederek kullanılacak havaalanı (ADÜ) sayısını
azaltabileceği ya da arttırabileceği gibi, matematiksel modelde kullanılan
verileri farklı sevkiyat dönemleri için değiştirerek kendi sonuçlarını elde
edebileceği değerlendirilmektedir.
100
Kurumdan, işletilmekte olan mevcut sistemin maliyeti doğru olarak
alınamadığından maliyet karşılaştırması yapılamamıştır.
Kurumun hali hazırda kullanmış olduğu sistemde, ADÜ olarak
seçilmeyen tüm iller, güzergah farkı gözetmeksizin sadece bir havaalanına
atanmaktadır. Geliştirilen matematiksel modellerin çözümlerinde ise, ADÜ
olarak
seçilmeyen
iller
farklı
güzergahlar
için
farklı
havaalanlarına
atanabilmektedir. Yani, aynı kaynak noktasından çıkıp farklı varış noktalarına
gidecek olan akışların aynı ADÜ’yü kullanma zorunluluğu kaldırılarak yük
birleştirmelerinin doğru ADÜ’lerde yapılabilmesi sağlanmıştır. Böylece, kurum,
doğru ADÜ’lerde doğru yük birleştirmeleri yaparak taşıma işlemlerini ekonomik
bir şekilde yapabilecektir.
Sonuç olarak;
İşletilmekte olan sistemde, mevcut taşıma işlemlerini gerçekleştirmek
için kullanılan havaalanları, diğer illerin hangi havaalanlarını kullanacağı ve
hangi iller arasında kara yolu ile taşıma yapılacağı, kurum yöneticilerinin
tecrübeleri vasıtasıyla herhangi bir nedene dayanmadan belirlenmiştir. Bu
çalışmada ise, kurumdan alınan bilgiler ve kurumun istekleri doğrultusunda
oluşturulan
matematiksel
modeller
yardımıyla
ekonomik,
doğru
ve
uygulanabilir kararlar için bilimsel tabanlı çözümler sunulmuştur.
2. ÖNERİLER
Bu çalışmada, ADÜ yer seçim problemlerine yeni bir bakış açısı
kazandırılması amaçlanmış ve şebekedeki düğümler arasındaki mesafelerde
üçgensel eşitsizliğin olmadığı, kesikli uzayda yer alan, çok atamalı, ADÜ olarak
seçilmeyen kaynak-varış çiftleri arasındaki akışlarda ADÜ kullanmadan direkt
gidişe müsaade eden, ADÜ olarak seçilen düğümlerin kapasitelerini, hem
ADÜ, hemde ADÜ olarak seçilmeyen düğümlerden gelen akışıların etkilediği
iki farklı matematiksel model önerilmiştir. Matematiksel modellerde kullanılan
101
akışlar deterministik olarak belirlenmiş ve akışların tamamının aynı zaman
diliminde gerçekleştiği kabul edilmiştir.
İleride yapılabilecek çalışmalara ilişkin aşağıda maddeler halinde
sıralanan önerileri sunmak mümkündür.

Matematiksel model, belirsizlik durumunun ortaya koyduğu
durumları içerecek şekilde stokastik olarak çalışılabilir. Böylece, problemin
gerçek karakteristiklerine çok daha yakın sonuçlar elde edilebilir.

Matematiksel modelin zaman pencereli olarak düşünülmesiyle,
ADÜ’lerin kapasitelerinin daha uygun şekilde kullanılması ve yerleştirme
atama kararlarının gerçeğe en yakın şekilde bulunabilmesi sağlanabilir.

Literatürde yapılan incelemede, ADÜ yer seçim problemleri ve
araç rotalama problemlerinin birlikte düşünüldüğü bir matematiksel modele
rastlanmamıştır. Bu iki tip problemin birlikte düşünülmesiyle, büyük bir taşıma
ağı problemi için matematiksel modeller geliştirilebilir.
102
KAYNAKÇA
ABDİNNOUR-HELM, Sue. “A Hybrid Heuristic for the Uncapacitated Hub
Location Problem” European Journal of Operational Research, 106 (2),
1998, 489–499.
ABDİNNOUR-HELM, Sue. “Using Simulated Annealing to Solve the P-Hub
Median Problem” International Journal of Physical Distribution &
Logistics Management, 31 (3), 2001, 203–220.
ABDİNNOUR-HELM, S. ve M.A. VENKATARAMANAN. “Solution Approaches
to Hub Location Problems” Annals of Operations Research, 78, 1998, 31–
50.
ALUMUR, S. ve B. Y. Kara. “Network Hub Location Problems: The State of the
Art” European Journal of Operational Research, 190(1), 2008, 1-21.
ALUMUR, S. A., B. Y. KARA. ve O. E. KARASAN. “The Design of Single
Allocation Incomplete Hub Networks” Transportation Research Part B:
Methodological, 43(10), 2009, 936-951.
ALUMUR, S. A., B. Y. KARA. ve O. E. KARASAN. “Multimodal Hub Location
and Hub Network Design” Omega, 40(6), 2012, 927–939.
AYKİN, Turgut. “On a Quadratic İnteger Program for the Location of Interacting
Hub Facilities” European Journal of Operational Research, 46 (3), 1990,
409–411.
AYKİN, Turgut. “Lagrangean Relaxation Based Approaches to Capacitated
Hub-and-Spoke Network Design Problem” European Journal of Operational
Research, 79 (3), 1994, 501–523.
AYKİN, Turgut. “Networking Policies for Hub-and-Spoke Systems with
Application to the Air Transportation System” Transportation Science, 29 (3),
1995a, 201–221.
AYKİN, Turgut. “The Hub Location and Routing Problem” European Journal
of Operational Research, 83, 1995b, 200–219.
BASHİRİ, Mahdi. ve diğerleri “Modeling Fuzzy Capacitated P-Hub Center
Problem and a Genetic Algorithm Solution” Applied Mathematical
Modelling, 37(5), 2013, 3513-3525.
BASTI, Mehmet. “P-Medyan Tesis Yeri Seçim Problemi ve Çözüm
Yaklaşımları” Online Academic Journal of Information Technology, 3 (7),
2012.
103
BOLAND, Natashia. ve diğerleri “Preprocessing and Cutting for Multiple
Allocation Hub Location Problems” European Journal of Operational
Research, 155 (3), 2004, 638–653.
BRYAN, D.L. ve M.E. O’KELLY. “Hub-and-Spoke Networks in Air
Transportation: An Analytical Review” Journal of Regional Science, 39(2),
1999, 275–295.
CALİK, Hatice ve diğerleri “A Tabu-Search Based Heuristic for the Hub
Covering Problem Over Incomplete Hub Networks” Computers and
Operations Research, 36, 2009, 3088–3096.
CAMPBELL, James. F. “Location and Allocation for Distribution Systems with
Transshipments and Transportation Economies of Scale” Annals of
Operations Research, 40, 1992, 77–99.
CAMPBELL, James. F. “A Survey of Network Hub Location” Studies in
Locational Analysis, 6, 1994a, 31–49.
CAMPBELL, James. F. “Integer Programming Formulations of Discrete Hub
Location Problems” European Journal of Operational Research, 72, 1994b,
387–405.
CAMPBELL, James. F. “Hub Location and the
Problem” Operations Research, 44(6), 1996, 923-935.
P-Hub
Median
CAMPBELL, James. F. “Hub Location for Time Definite Transportation”
Computers and Operations Research, 36, 2009, 3107–3116.
CAMPBELL, James. F. ve diğerleri “The P-Hub Center Allocation Problem”
European Journal of Operational Research, 176 (2), 2007, 819–835.
CÁNOVAS, Lazaro. ve diğerleri “Solving the Uncapacitated Multiple Allocation
Hub Location Problem by Means of a Dual-Ascent Technique” European
Journal of Operational Research, 179(3), 2007, 990-1007.
CATANZARO, Daniele. ve diğerleri “A Branch-and-Cut Algorithm for the
Partitioning-Hub Location-Routing Problem” Computers & operations
research, 38(2), 2011, 539-549.
ÇETİNER, Selim. ve diğerleri “Hubbing and Routing in Postal Delivery
Systems” Annals of Operations Research, 181(1), 2010, 109-124.
CHEN, Jeng Fung. “A Hybrid Heuristic for the Uncapacitated Single Allocation
Hub Location Problem” Omega, 35(2), 2007, 211-220.
104
CONTRERAS, Ivan. ve diğerleri “Lagrangean Relaxation for the Capacitated
Hub Location Problem with Single Assignment.” OR spectrum, 31(3), 2009,
483-505.
CONTRERAS, Ivan. ve diğerleri “The Tree of Hubs Location
Problem” European Journal of Operational Research, 202(2), 2010, 390400.
CONTRERAS, Ivan. ve diğerleri “Stochastic Uncapacitated Hub
Location” European Journal of Operational Research, 212(3), 2011b, 518528.
CONTRERAS, Ivan. ve diğerleri “Benders Decomposition for Large-Scale
Uncapacitated Hub Location” Operations Research, 59(6), 2011c, 14771490.
CORREİA, Isabel. ve diğerleri “Single-Assignment Hub Location Problems
with Multiple Capacity Levels” Transportation Research Part B:
Methodological, 44(8), 2010a, 1047-1066.
CORREİA, Isabel. ve diğerleri “The Capacitated Single-Allocation Hub
Location Problem Revisited: A Note on a Classical Formulation” European
Journal of Operational Research, 207(1), 2010b, 92-96.
COSTA, Maria. ve diğerleri “Capacitated Single Allocation Hub Location
Problem-a
Bi-Criteria
Approach”
Computers
&
Operations
Research, 35(11), 2008, 3671-3695.
CUNHA, Claudio ve M. R. Silva. “A Genetic Algorithm for the Problem of
Configuring a Hub-and-Spoke Network for a Ltl Trucking Company in Brazil”
European Journal of Operational Research, 179(3), 2007, 747-758.
DASKIN, M. ,J. CURRENT ve D. SCHILLING. 3 Discrete Network Location
Models. Facility Location: Applications and Theory, Springer-Verlag Berlin
Heidelberg New Tork, 81, 2002.
DASKIN, Mark.
University,1995.
Network
and
discrete
location.
Northwestern
DE CAMARGO, R. S., ve G. MİRANDA. “Single Allocation Hub Location
Problem Under Congestion: Network Owner and User Perspectives” Expert
Systems with Applications, 39(3), 2012, 3385-3391.
DE CAMARGO, R. S. “A Hybrid Outer-Approximation/Benders Decomposition
Algorithm for the Single Allocation Hub Location Problem Under
Congestion” Operations Research Letters, 39(5), 2011, 329-337.
105
DE CAMARGO, R. S. ve diğerleri “Benders Decomposition for the
Uncapacitated Multiple Allocation Hub Location Problem” Computers &
Operations Research, 35(4), 2008, 1047-1064.
DE CAMARGO, R. S. ve diğerleri “Multiple Allocation Hub-and-Spoke Network
Design Under Hub Congestion” Computers & Operations Research, 36(12),
2009, 3097-3106.
DE CAMARGO, R. S. ve diğerleri “Benders Decomposition for Hub Location
Problems with Economies of Scale” Transportation Science, 43(1), 2009, 8697.
EBERY, Jamie. “Solving Large Single Allocation P-Hub Problems with Two or
Three Hubs” European Journal of Operational Research, 128 (2), 2001,
447–458.
EBERY, Jamie. ve diğerleri “The Capacitated Multiple Allocation Hub Location
Problem: Formulations and Algorithms” European Journal of Operational
Research, 120(3), 2000, 614-631.
EİSELT, H. A., & V. MARİANOV. “A Conditional P-Hlp with Attraction
Functions” Computers and Operations Research, 36(12), 2009, 3128–3135.
ELHEDHLİ, S. ve F. X. HU. “Hub-and-Spoke Network Design with
Congestion” Computers & Operations Research, 32(6), 2005, 1615-1632.
ERMİŞ, M. ve F. ÜLENGİN. “Merkez Üslerin Konumlandırılması Probleminin
Hopfield-Tank Yapay Sinir Ağları ile Çözülmesi” İTÜ Dergisi, 5(1), 2006, 228238.
ERNST, Andreas T. ve diğerleri “Uncapacitated Single and Multiple Allocation
P-Hub Center Problems” Computers and Operations Research, 36(7),
2009, 2230–2241.
ERNST, A.T., M. KRISHNAMOORTHY. “Efficient Algorithms for the
Uncapacitated Single Allocation P-Hub Median Problem” Location Science,
4 (3), 1996, 139–154.
ERNST, A.T., M. KRISHNAMOORTHY. “An Exact Solution Approach Based
on Shortest-Paths for P-Hub Median Problems” INFORMS Journal on
Computing, 10(2), 1998, 149-162.
ERNST, A.T., M. KRISHNAMOORTHY. “Exact and Heuristic Algorithms for
the Uncapacitated Multiple Allocation P-Hub Median Problem” European
Journal of Operational Research, 104(1), 1998a, 100–112.
106
ERNST, A.T., M. KRISHNAMOORTHY. “Solution Algorithms for the
Capacitated Single Allocation Hub Location Problem” Annals of Operations
Research, 86, 1999, 141-159.
ERNST, Andreas. ve diğerleri. “Uncapacitated Single and Multiple Allocation
P-Hub Center Problems” Unpublished Report, CSIRO Mathematical and
Information Sciences, Australia, 2002a.
ERNST, Andreas. ve diğerleri. “Heuristic Algorithms for the Uncapacitated Hub
Center Single Allocation Problem” Unpublished Report, CSIRO Mathematical
and Information Sciences, Australia, 2002b.
ERNST, Andreas. ve diğerleri. “Reformulations and Computational Results for
Uncapacitated Single and Multiple Allocation Hub Covering Problems”
Unpublished Report, CSIRO Mathematical and Information Sciences,
Australia, 2005.
FARAHANI, R. Z. ve M. HEKMATFAR. Facilities location: Concepts,
models, algorithms and case studies. Heidelberg: Springer-Verlag, 2009.
FARAHANİ, Reza Zanjirani. ve diğerleri “Hub Location Problems: A Review of
Models, Classification, Solution Techniques, and Applications” Computers &
Industrial Engineering, 64(4), 2013, 1096-1109.
FİLİPOVİC, Vladimir. ve diğerleri. GA inspired heuristic for uncapacitated
single allocation hub location problem. In J. Mehnen et al. (Eds.),
Applications of soft computing. AISC (Vol. 58, pp. 149–158). Berlin,
Heidelberg: Springer-Verlag, 2009.
GARCÍA, Sergio. ve diğerleri “New Formulation and a Branch-and-Cut
Algorithm for the Multiple Allocation P-Hub Median Problem” European
Journal of Operational Research, 220(1), 2012, 48–57.
GAVRİLİOUK, Elena O. “Aggregation in Hub Location Problems” Computers
and Operations Research, 36, 2009, 3136–3142.
GELAREH, S. ve S. NİCKEL. “A Benders Decomposition for Hub Location
Problems Arising in Public Transport.” Operations Research Proceedings
Part VI, 1, 2007, 129–134.
GELAREH, S. ve S. NİCKEL. “Hub Location Problems in Transportation
Networks” Transportation Research Part E, 47, 2011, 1092–1111.
GELAREH, Shahin. ve diğerleri “Liner Shipping Hub Network Design in a
Competitive Environment.” Transportation Research Part E, 46, 2010, 991–
1004.
107
GELAREH, S. ve D. PİSİNGER. “Fleet Deployment, Network Design and Hub
Location of Liner Shipping Companies” Transportation Research Part E, 47,
2011, 947–964.
HAMACHER, H. W. ve T. MEYER. Hub cover and hub center problems.
Working paper. Department of Mathematics, University of Kaiserslautern,
Gottlieb-Daimler-Strasse, 67663 Kaiserslautern, Germany, 2006.
HAMACHER, Horst W. ve diğerleri “Adapting Polyhedral Properties from
Facility to Hub Location Problems” Discrete Applied Mathematics, 145(1),
2004, 104-116.
HAN, Junghee. “A Traffic Grooming Problem Considering Hub Location for
Synchronous Optical Network-Wavelength Division Multiplexing Networks.”
Computers & Industrial Engineering, 59(1), 2010, 1-8.
HE, Xiaozheng. ve diğerleri. On the quadratic programming approach for
hub location problems. In W. Chaovalitwongse et al. (Eds.), Optimization
and logistics challenges in the enterprise. Springer optimization and its
applications, (Vol. 30, no. 2, pp. 211–228), 2009.
ILİĆ, Aleksandar, ve diğerleri “A General Variable Neighborhood Search for
Solving
the
Uncapacitated
Single
Allocation
P-Hub
Median
Problem” European Journal of Operational Research, 206(2), 2010, 289300.
ISHFAQ, R. ve C. R. SOX. “Design of Intermodal Logistics Networks with Hub
Delays” European Journal of Operational Research, 220(3), 2012, 629-641.
IWASA, Masaru. ve diğerleri “Approximation Algorithms for the Single
Allocation Problem in Hub-and-Spoke Networks and Related Metric Labeling
Problems” Discrete Applied Mathematics, 157(9), 2009, 2078-2088.
KARA, Bahar Yetiş, Modeling and analysis of issues in hub location
problems. Ph.D. Thesis, Bilkent University Industrial Engineering Department,
06800 Bilkent, Ankara, Turkey, 1999.
KARA, B. Y. ve B. C. TANSEL. “On the Single-Assignment P-Hub Center
Problem” European Journal of Operational Research, 125(3), 2000, 648655.
KARA, B. Y. ve B. C. TANSEL. “The Latest Arrival Hub Location Problem.”
Management Science, 47(10), 2001, 1408-1420.
KARA, B. Y. ve B. C. TANSEL. “The Single-Assignment Hub Covering
Problem: Models and Linearizations” Journal of the Operational Research
Society, 54(1), 2003, 59-64.
108
Kara Yolları Genel Müdürlüğü Web. 11 Mart 2014. <http://www. kgm.gov .tr /
Sayfalar/ KGM / SiteTr/Root/Uzakliklar.aspx.>
KARİMİ, H. ve M. BASHİRİ. “Hub Covering Location Problems with Different
Coverage Types” Scientia Iranica, 18(6), 2011, 1571-1578.
KLİNCEWICZ, John G. “Heuristics for the P-Hub Location Problem” European
Journal of Operational Research, 53(1), 1991, 25-37.
KLİNCEWICZ, John G. “Avoiding Local Optima in Thep-Hub Location Problem
Using Tabu Search and GRASP.” Annals of Operations Research, 40(1),
1992, 283-302.
KLİNCEWICZ, John G. “A Dual Algorithm for the Uncapacitated Hub Location
Problem” Location Science, 4(3), 1996, 173-184.
KRATICA, Jozef. ve diğerleri “Two Genetic Algorithms for Solving the
Uncapacitated Single Allocation P-Hub Median Problem” European Journal
of Operational Research, 182(1), 2007, 15-28.
KRATİCA, Jozef. “An Electromagnetism-Like Metaheuristic for the
Uncapacitated Multiple Allocation P-Hub Median Problem” Computers &
Industrial Engineering, 66(4), 2013, 1015-1024.
KRATİCA, Jozef. ve diğerleri “An Evolutionary-Based Approach for Solving a
Capacitated Hub Location Problem” Applied Soft Computing, 11(2), 2011,
1858-1866.
LABBÉ, Martine. “A Branch and Cut Algorithm for Hub Location Problems with
Single Assignment” Mathematical programming, 102(2), 2005, 371-405.
LİMBOURG, S. ve B. JOURQUİN. “Optimal Rail-Road Container Terminal
Locations on the European Network” Transportation Research Part E:
Logistics and Transportation Review, 45(4), 2009, 551-563.
LİN, Cheng Chang. “The Integrated Secondary Route Network Design Model
in the Hierarchical Hub-and-Spoke Network for Dual Express Services
” International Journal of Production Economics, 123(1), 2010, 20-30.
LİN, C. C ve S. C. LEE. “The Competition Game On Hub Network Design”
Transportation Research Part B: Methodological, 44(4), 2010, 618-629.
LİN, Cheng Chang. ve diğerleri “The Capacitated P-Hub Median Problem with
Integral Constraints: An Application to a Chinese Air Cargo Network” Applied
Mathematical Modelling, 36(6), 2012, 2777-2787.
109
MARIN, Alfredo. “Uncapacitated Euclidean Hub Location: Strengthened
Formulation, New Facets and a Relax-and-Cut Algorithm” Journal of Global
Optimization, 33(3), 2005, 393-422.
MARIN, Alfredo. “Formulating and Solving Splittable Capacitated Multiple
Allocation Hub Location Problems” Computers & operations
research, 32(12), 2005a, 3093-3109.
MARIN, Alfredo. “New Formulations for the Uncapacitated Multiple Allocation
Hub Location Problem” European Journal of Operational Research, 172(1),
2006, 274-292.
MAYER, G. ve B. WAGNER. “Hublocator: An Exact Solution Method for the
Multiple Allocation Hub Location Problem” Computers & Operations
Research, 29(6), 2002, 715-739.
MEYER, T., A. T. ERNST ve M. KRISHNAMOORTHY. “A 2-Phase Algorithm
for Solving the Single Allocation P-Hub Center Problem” Computers &
Operations Research, 36(12), 2009, 3143-3151.
MOHAMMADI, Mehrdad. ve diğerleri. “An M/M/C Queue Model for Hub
Covering Location Problem” Mathematical and Computer Modelling, 54(11),
2011, 2623-2638.
MOHAMMADI, Mehrdad. ve diğerleri. “Solving A New Stochastic Multi-Mode
Hub Covering Location Problem Considering Risk by a Novel Multi-Objective
Algorithm” Applied Mathematical Modelling, 37(24), 2013, 10053-10073.
O'KELLY, Morton E. “The Location of Interacting
Transportation science, 20(2), 1986, 92-106.
Hub
Facilities”
O'KELLY, Morton E. “Activity Levels at Hub Facilities in Interacting Networks”
Geographical Analysis, 18(4), 1986, 343-356.
O'KELLY, Morton E. “A Quadratic Integer Program for the Location of
Interacting Hub Facilities” European Journal of Operational
Research, 32(3), 1987, 393-404.
O'KELLY, Morton E. “Hub Facility Location with Fixed Costs” Papers in
Regional Science, 71(3), 1992, 293-306.
O'KELLY, Morton E. “A Clustering Approach to the Planar Hub Location
Problem” Annals of Operations Research, 40(1), 1992, 339-353.
O’KELLY, Morton E. “Rectilinear Minimax Hub Location Problems” Journal of
geographical systems, 11(3), 2009, 227-241.
110
O'KELLY, M. E. ve H. J. MILLER. “The Hub Network Design Problem: A
Review and Synthesis” Journal of Transport Geography, 2(1), 1994, 31-40.
O'KELLY, Morton. E. ve diğerleri “Lower Bounds for the Hub Location
Problem” Management Science, 41(4), 1995, 713-721.
O'KELLY, Morton E. ve diğerleri “Hub Network Design with Single and Multiple
Allocation: A Computational Study” Location Science, 4(3), 1996, 125-138.
OKTAL, H. ve A. OZGER. “Hub Location in Air Cargo Transportation: A Case
Study” Journal of Air Transport Management, 27, 2013, 1-4.
ÖZGER, Asuman. Havayolu Kargo Taşımacılığında Ana Dağıtım Üssü
Yerleşim Problemine Tamsayılı Model Yaklaşımı, Doktora Tezi, Anadolu
Üniversitesi, 2008.
ÖZGER, A. ve H. OKTAL. “Havayolu Kargo Taşımacılığında Kapasite Sınırı
Olmayan Çok Atamalı P-Ana Dağıtım Üssü Medyan Problemine Tamsayılı
Model Yaklaşımı” Journal of Aeronautics & Space Technologies/Havacilik
ve Uzay Teknolojileri Dergisi, 2009, 4(1).
PAMUK, F. S. ve C. SEPİL. “A Solution to the Hub Center Problem Via a
Single-Relocation Algorithm with Tabu Search” IIE Transactions, 33(5), 2001,
399-411.
PEİRÓ, Juanjo. ve diğerleri “Grasp for the Uncapacitated r-Allocation P-Hub
Median Problem” Computers & Operations Research, 43, 2014, 50-60.
PIRKUL, H. ve D. A. SCHİLLİNG. “An Efficient Procedure for Designing Single
Allocation Hub and Spoke Systems” Management Science, 44(12-part-2),
1996, 235-242.
PUERTO, J., A. B. RAMOS, ve A. M. RODRÍGUEZ-CHÍA. “Single-Allocation
Ordered Median Hub Location Problems” Computers & Operations
Research, 38(2), 2011, 559-570.
QU, B. ve K. WENG. “Path Relinking Approach for Multiple Allocation Hub
Maximal Covering Problem” Computers & Mathematics with
Applications, 57(11), 2009, 1890-1894.
RANDALL, M. German. “Solution Approaches for the Capacitated Single
Allocation
Hub
Location
Problem
Using
Ant
Colony
Optimization” Computational Optimization and Applications, 39(2), 2008,
239-261.
111
RANDALL, M. German. ve diğerleri, Extremal optimization for assignment
type problems. In A. Lewis et al. (Eds.), Biologically-inspired optimization
methods. SCI (Vol. 210, pp. 139–164). Berlin, Heidelberg: Springer-Verlag,
2009.
RODRİGUEZ, Victoria. ve diğerleri “Hub Location
Constraints” Transportation Research Part E:
Transportation Review, 43(5), 2007, 495-505.
Under Capacity
Logistics and
RODRİGUEZ-MARTİN, I. ve J. J. SALAZAR-GONZALEZ. “Solving a
Capacitated Hub Location Problem” European Journal of Operational
Research, 184(2), 2008, 468-479.
SASAKİ, M. ve M. FUKUSHİMA. “On The Hub-and-Spoke Model with Arc
Capacity Constraints” Journal of the Operations Research Society of
Japan-Keiei Kagaku, 46(4), 2003, 409-428.
SASAKİ, Mihiro. ve diğerleri “On the Selection of Hub Airports for an Airline
Hub-and-Spoke System” Computers & operations research, 26(14), 1999,
1411-1422.
SENDER, J. ve U. CLAUSEN. “Heuristics for Solving a Capacitated Multiple
Allocation Hub Location Problem with Application in German Wagonload
Traffic” Electronic Notes in Discrete Mathematics, 41, 2013, 13-20.
SİLVA, M. R. ve C. B. CUNHA. “New Simple and Efficient Heuristics for the
Uncapacitated Single Allocation Hub Location Problem” Computers &
Operations Research, 36(12), 2009, 3152-3165.
SİM, Thaddeus. ve diğerleri “The Stochastic P-Hub Center Problem with
Service-Level Constraints” Computers & Operations Research, 36(12),
2009, 3166-3177.
SKORİN-KAPOV, D. ve J. SKORİN-KAPOV. “On Tabu Search for the Location
of Interacting Hub Facilities” European Journal of Operational
Research, 73(3), 1994, 502-509.
SKORİN-KAPOV, Darko ve diğerleri “Tight Linear Programming Relaxations
of Uncapacitated P-Hub Median Problems” European Journal of
Operational Research, 94(3), 1996, 582-593.
SMİTH, Kate. ve diğerleri “Neural Versus Traditional Approaches to the
Location of Interacting Hub Facilities” Location Science, 4(3), 1996,155-171.
SOHN, J. ve S. PARK, S. “A Linear Program for the Two-Hub Location
Problem” European Journal of Operational Research, 100(3), 1997, 617622.
112
SOHN, J. ve S. PARK “Efficient Solution Procedure and Reduced Size
Formulations for P-Hub Location Problems” European Journal of
Operational Research, 108(1), 1998, 118-126.
SOHN, J. ve S. PARK. “The Single Allocation Problem in the Interacting ThreeHub Network” Networks, 35(1), 2000, 17-25.
TAGHİPOURİAN, Farzin. ve diğerleri “A Fuzzy Programming Approach for
Dynamic Virtual Hub Location Problem” Applied Mathematical
Modelling, 36(7), 2012, 3257-3270.
TAKANO, K. ve M. ARAI. “A Genetic Algorithm for the Hub-and-Spoke
Problem Applied to Containerized Cargo Transport” Journal of Marine
Science and Technology, 14(2), 2009, 256-274.
TAN, P. Z. ve B. Y. KARA. “A Hub Covering Model for Cargo Delivery
Systems” Networks, 49(1), 2007, 28-39.
TAVAKKOLİ-MOGHADDAİN, R. ve E. SHAYAN. “Facilities Layout Design by
Genetic Algorithms” Computers & industrial engineering, 35(3), 1998, 527530.
TOPCUOGLU, Haluk. ve diğerleri “Solving the Uncapacitated Hub Location
Problem Using Genetic Algorithms” Computers & Operations
Research, 32(4), 2005, 967-984.
VASCONCELOS, Adriano D. ve diğerleri “The Uncapacitated Hub Location
Problem in Networks Under Decentralized Management” Computers &
Operations Research, 38(12), 2011, 1656-1666.
VİDOVİĆ, Milorad. ve diğerleri “The P-Hub Model with Hub-Catchment Areas,
Existing Hubs, and Simulation: A Case Study of Serbian Intermodal
Terminals” Networks and Spatial Economics, 11(2), 2011, 295-314.
WAGNER, Bernd. “An Exact Solution Procedure for a Cluster Hub Location
Problem” European journal of operational research, 178(2), 2007, 391-401.
WAGNER, Bernd. “Model Formulations for Hub Covering Problems” Journal
of the Operational Research Society, 59(7), 2008, 932-938.
YAMAN, Hande. “The Hierarchical Hub Median Problem with Single
Assignment” Transportation Research Part B: Methodological, 43(6),
2009, 643-658.
YAMAN, H. ve S. ELLOUMI. “Star P-Hub Center Problem and Star P-Hub
Median Problem with Bounded Path Lengths” Computers & Operations
Research, 39(11), 2012, 2725-2732.
113
YANG, Kai. ve diğerleri “An Improved Hybrid Particle Swarm Optimization
Algorithm for Fuzzy p-Hub Center Problem” Computers & Industrial
Engineering, 64(1), 2013, 133-142.
YANG, Kai. ve diğerleri “Optimizing Fuzzy P-Hub Center Problem with
Generalized Value-at-Risk Criterion” Applied Mathematical Modelling, 2014.
YANG, Ta Hui. “Stochastic Air Freight Hub Location and Flight Routes
Planning” Applied Mathematical Modelling, 33(12), 2009, 4424-4430.
114
EKLER
EK-A
:
BİRİNCİ MATEMATİKSEL MODELİN GAMS KODU
EK-B
:
İKİNCİ MATEMATİKSEL MODELİN GAMS KODU
115
EK-A
BİRİNCİ MATEMATİKSEL MODELİN GAMS KODU
options limrow=1000,limcol=1000,iterlim=100000000,reslim=36000,optcr=0 ;
sets
i düğümler kümesi /1*81/ ;
alias (i,j) ;
alias (i,k) ;
alias (i,m) ;
table r(i,j) i den j ye karayolu mesafesi
table h(i,j) i den j ye havayolu mesafesi
table W(i,j) i den j ye akış miktarı
scalars
gama /0.8/
alfa /0.6/
kara /0.09/
hava /0.13/ ;
variables
a(m,j) m Hub’ından j spoke’una akış miktarı
b(k,m,j) k ve m hublarını kullanarak j noktasına giden akış miktarı
c(i,k,j) i spoke’undan çıkıp k hub’ını kullanarak j noktasına giden akış miktarı
Y(k) k hub’ının açılıp açılmaması
e(i,j) i den j ye hub kullanmadan direkt giden akış miktarı
z toplam taşıma maliyeti;
binary variables Y(k);
positive variables a(m,j),b(k,m,j),c(i,k,j),e(i,j) ;
equations
maliyet toplam taşıma maliyeti
eq1(j) j nin talebi karşılansın
eq2(i,j) akış dengeleme kısıtı
eq3(j,m) k ve m ADÜ iken b(k,m,j) değer alabilsin
eq4(j) k ve j ADÜ iken b(k,j,j) değer alabilsin
eq5(i,j,k) yalnızca k ADÜ iken c(i,k,j) değer alabilsin
eq6(i,j) i ADÜ iken c(i,k,j) ve e(i,j) değer almasın
eq7(k,j) akışlar en fazla iki ADÜ gezsin
eq8(k) k ADÜ’süne gelen akışlar k’nın kapasitesini geçmesin
eq9(j,m) gereksiz değişken değer almasın
eq10(j,k) gereksiz değişken değer almasın
eq11(j,k) gereksiz değişken değer almasın
eq12(j) gereksiz değişken değer almasın
eq13 hub olarak seçilmesin
A-1
EK-A’NIN DEVAMI
eq14 hub olarak seçilmesin
eq15 hub olarak seçilmesin
eq16 hub olarak seçilmesin
eq17 hub olarak seçilmesin
eq18 hub olarak seçilmesin
eq19 hub olarak seçilmesin
eq20 hub olarak seçilmesin
eq21 hub olarak seçilmesin
eq22 hub olarak seçilmesin
eq23 hub olarak seçilmesin
eq24 hub olarak seçilmesin
eq25 hub olarak seçilmesin
eq26 hub olarak seçilmesin
eq27 hub olarak seçilmesin
eq28 hub olarak seçilmesin
eq29 hub olarak seçilmesin
eq30 hub olarak seçilmesin
eq31 hub olarak seçilmesin
eq32 hub olarak seçilmesin
eq33 hub olarak seçilmesin
eq34 hub olarak seçilmesin
eq35 hub olarak seçilmesin
eq36 hub olarak seçilmesin
eq37 hub olarak seçilmesin
eq38 hub olarak seçilmesin
eq39 hub olarak seçilmesin
eq40 hub olarak seçilmesin
eq41 hub olarak seçilmesin
eq42 hub olarak seçilmesin
eq43 hub olarak seçilmesin
eq44 hub olarak seçilmesin
eq45 hub olarak seçilmesin
eq46 hub olarak seçilmesin
eq47 hub olarak seçilmesin
eq48 hub olarak seçilmesin
eq49 hub olarak seçilmesin
eq50 hub olarak seçilmesin
eq51 hub olarak seçilmesin
eq53(i,j) i ADÜ iken e(i,j) değer almasın
eq54(i,j) j ADÜ iken e(i,j) değer almasın ;
A-2
EK-A’NIN DEVAMI
maliyet..z=E=sum((m,j),gama*r(m,j)*kara*a(m,j))+sum((k,m,j),alfa*h(k,m)*hava*b(k,m,j))+sum((i,k,j),r(i,k)*kara*c(i,k,j)
)+sum((i,j),r(i,j)*kara*e(i,j));
eq1(j)..sum(m,a(m,j))+sum(m,b(m,j,j))+sum(m,c(m,j,j))+sum(m,e(m,j))=E=sum(i,W(i,j));
eq2(i,j)$(ord(i)<>ord(j))..a(i,j)+sum(k,b(i,k,j))+sum(k,c(i,k,j))+e(i,j)=E=W(i,j)+sum(k,b(k,i,j))+sum(k,c(k,i,j)) ;
eq3(j,m)$(ord(j)<>ord(m))..sum(k,b(k,m,j))+sum(k,c(k,m,j))=L=(sum(i,W(i,j))-W(m,j))*Y(m) ;
eq4(j)..sum(k,b(k,j,j))+sum(k,c(k,j,j))=E=(sum(i,W(i,j)))*Y(j);
eq5(i,j,k)..c(i,k,j)=L= W(i,j)*Y(k) ;
eq6(i,j)..sum(k,c(i,k,j))+e(i,j)=E=W(i,j)*(1-Y(i)) ;
eq7(k,j)..sum(m,b(k,m,j))=L=W(k,j)+sum(i,c(i,k,j)) ;
eq8(k)..sum((i,j),c(i,k,j))+sum((i,j),b(i,k,j))=L=G(k)*Y(k) ;
eq9(j,m)$(ord(m)<>ord(j))..b(j,m,j)=E=0 ;
eq10(j,k)$(ord(k)<>ord(j))..b(k,k,j)=E=0 ;
eq11(j,k)..c(k,k,j)=E=0 ;
eq12(j)..a(j,j)=E=0 ;
eq53(i,j)$(ord(i)<>ord(j))..e(i,j)=L=W(i,j)*(1-Y(i)) ;
eq54(i,j)$(ord(i)<>ord(j))..e(i,j)=L=W(i,j)*(1-Y(j)) ;
eq13..Y('3')=E=0 ;
eq14..Y('8')=E=0 ;
eq15..Y('9')=E=0 ;
eq16..Y('11')=E=0 ;
eq17..Y('13')=E=0 ;
eq18..Y('14')=E=0 ;
eq19..Y('15')=E=0 ;
eq20..Y('17')=E=0 ;
eq21..Y('18')=E=0 ;
eq22..Y('19')=E=0 ;
eq23..Y('22')=E=0 ;
eq24..Y('26')=E=0 ;
eq25..Y('28')=E=0 ;
eq26..Y('29')=E=0 ;
eq27..Y('30')=E=0 ;
eq28..Y('33')=E=0 ;
eq29..Y('39')=E=0 ;
eq30..Y('40')=E=0 ;
eq31..Y('45')=E=0 ;
eq32..Y('51')=E=0 ;
eq33..Y('52')=E=0 ;
eq34..Y('53')=E=0 ;
eq35..Y('54')=E=0 ;
eq36..Y('57')=E=0
A-3
EK-A’NIN DEVAMI
eq37..Y('62')=E=0 ;
eq38..Y('64')=E=0 ;
eq39..Y('66')=E=0 ;
eq40..Y('67')=E=0 ;
eq41..Y('68')=E=0 ;
eq42..Y('69')=E=0 ;
eq43..Y('70')=E=0 ;
eq44..Y('71')=E=0 ;
eq45..Y('74')=E=0 ;
eq46..Y('75')=E=0 ;
eq47..Y('77')=E=0 ;
eq48..Y('78')=E=0 ;
eq49..Y('79')=E=0 ;
eq50..Y('80')=E=0 ;
eq51..Y('81')=E=0 ;
model tasima /all/ ;
solve tasima using mip minimizing z ;
display a.l,b.l,c.l,Y.l,e.l ;
file sonuc/c:\GAMSTez\sonucPSİZ.txt/;
put sonuc;
*put system.ifile/;
*put system.date/;
*put system.time/;
put @15 "sure", @25 "z"/;
put @8 tasima.resusd, @20 z.l/;
put @1 "i",@13 "k", @25 "j", @46 "c"/;
loop((i,k,j),if(c.l(i,k,j)>0, put i.tl,k.tl,j.tl,c.l(i,k,j)/));
put @1 "k",@13 "m",@25 "j", @46 "b"/;
loop((k,m,j),if(b.l(k,m,j)>0, put k.tl,m.tl,j.tl,b.l(k,m,j)/));
put @1 "m",@13 "j", @34 "a"/;
loop((m,j),if(a.l(m,j)>0, put m.tl,j.tl,a.l(m,j)/));
put @1 "i",@13 "j", @34 "e"/;
loop((i,j),if(e.l(i,j)>0, put i.tl,j.tl,e.l(i,j)/));
put @1 "k", @23 "Y"/;
loop((k),if(Y.l(k)>0, put k.tl,Y.l(k)/));
putclose so
A-4
EK-B
İKİNCİ MATEMATİKSEL MODELİN GAMS KODU
options limrow=1000,limcol=1000,iterlim=100000000,reslim=36000,optcr=0 ;
sets
i düğümler kümesi /1*81/ ;
alias (i,j) ;
alias (i,k) ;
alias (i,m) ;
table r(i,j) i den j ye karayolu mesafesi
table h(i,j) i den j ye havayolu mesafesi
table W(i,j) i den j ye akış miktarı
scalars
gama /0.8/
alfa /0.6/
kara /0.09/
hava /0.13/ ;
variables
a(m,j) m Hub’ından j spoke’una akış miktarı
b(k,m,j) k ve m hublarını kullanarak j noktasına giden akış miktarı
c(i,k,j) i spoke’undan çıkıp k hub’ını kullanarak j noktasına giden akış miktarı
Y(k) k hub’ının açılıp açılmaması
e(i,j) i den j ye hub kullanmadan direkt giden akış miktarı
z toplam taşıma maliyeti;
binary variables Y(k);
positive variables a(m,j),b(k,m,j),c(i,k,j),e(i,j) ;
equations
maliyet toplam taşıma maliyeti
eq1(j) j nin talebi karşılansın
eq2(i,j) akış dengeleme kısıtı
eq3(j,m) k ve m ADÜ iken b(k,m,j) değer alabilsin
eq4(j) k ve j ADÜ iken b(k,j,j) değer alabilsin
eq5(i,j,k) yalnızca k ADÜ iken c(i,k,j) değer alabilsin
eq6(i,j) i ADÜ iken c(i,k,j) ve e(i,j) değer almasın
eq7(k,j) akışlar en fazla iki ADÜ gezsin
eq8(k) k ADÜ’süne gelen akışlar k’nın kapasitesini geçmesin
eq9(j,m) gereksiz değişken değer almasın
eq10(j,k) gereksiz değişken değer almasın
eq11(j,k) gereksiz değişken değer almasın
eq12(j) gereksiz değişken değer almasın
eq13 hub olarak seçilmesin
eq14 hub olarak seçilmes
B-1
EK-B’NİN DEVAMI
eq15 hub olarak seçilmesin
eq16 hub olarak seçilmesin
eq17 hub olarak seçilmesin
eq18 hub olarak seçilmesin
eq19 hub olarak seçilmesin
eq20 hub olarak seçilmesin
eq21 hub olarak seçilmesin
eq22 hub olarak seçilmesin
eq23 hub olarak seçilmesin
eq24 hub olarak seçilmesin
eq25 hub olarak seçilmesin
eq26 hub olarak seçilmesin
eq27 hub olarak seçilmesin
eq28 hub olarak seçilmesin
eq29 hub olarak seçilmesin
eq30 hub olarak seçilmesin
eq31 hub olarak seçilmesin
eq32 hub olarak seçilmesin
eq33 hub olarak seçilmesin
eq34 hub olarak seçilmesin
eq35 hub olarak seçilmesin
eq36 hub olarak seçilmesin
eq37 hub olarak seçilmesin
eq38 hub olarak seçilmesin
eq39 hub olarak seçilmesin
eq40 hub olarak seçilmesin
eq41 hub olarak seçilmesin
eq42 hub olarak seçilmesin
eq43 hub olarak seçilmesin
eq44 hub olarak seçilmesin
eq45 hub olarak seçilmesin
eq46 hub olarak seçilmesin
eq47 hub olarak seçilmesin
eq48 hub olarak seçilmesin
eq49 hub olarak seçilmesin
eq50 hub olarak seçilmesin
eq51 hub olarak seçilmesin
eq52 seçilecek hub sayısı p kadar olsun
eq53(i,j) i ADÜ iken e(i,j) değer almasın
eq54(i,j) j ADÜ iken e(i,j) değer almasın ;
B-2
EK-B’NİN DEVAMI
maliyet..z=E=sum((m,j),gama*r(m,j)*kara*a(m,j))+sum((k,m,j),alfa*h(k,m)*hava*b(k,m,j))+sum((i,k,j),r(i,k)*kara*c(i,k,j)
)+sum((i,j),r(i,j)*kara*e(i,j));
eq1(j)..sum(m,a(m,j))+sum(m,b(m,j,j))+sum(m,c(m,j,j))+sum(m,e(m,j))=E=sum(i,W(i,j));
eq2(i,j)$(ord(i)<>ord(j))..a(i,j)+sum(k,b(i,k,j))+sum(k,c(i,k,j))+e(i,j)=E=W(i,j)+sum(k,b(k,i,j))+sum(k,c(k,i,j)) ;
eq3(j,m)$(ord(j)<>ord(m))..sum(k,b(k,m,j))+sum(k,c(k,m,j))=L=(sum(i,W(i,j))-W(m,j))*Y(m) ;
eq4(j)..sum(k,b(k,j,j))+sum(k,c(k,j,j))=E=(sum(i,W(i,j)))*Y(j);
eq5(i,j,k)..c(i,k,j)=L= W(i,j)*Y(k) ;
eq6(i,j)..sum(k,c(i,k,j))+e(i,j)=E=W(i,j)*(1-Y(i)) ;
eq7(k,j)..sum(m,b(k,m,j))=L=W(k,j)+sum(i,c(i,k,j)) ;
eq8(k)..sum((i,j),c(i,k,j))+sum((i,j),b(i,k,j))=L=G(k)*Y(k) ;
eq9(j,m)$(ord(m)<>ord(j))..b(j,m,j)=E=0 ;
eq10(j,k)$(ord(k)<>ord(j))..b(k,k,j)=E=0 ;
eq11(j,k)..c(k,k,j)=E=0 ;
eq12(j)..a(j,j)=E=0 ;
eq53(i,j)$(ord(i)<>ord(j))..e(i,j)=L=W(i,j)*(1-Y(i)) ;
eq54(i,j)$(ord(i)<>ord(j))..e(i,j)=L=W(i,j)*(1-Y(j)) ;
eq13..Y('3')=E=0 ;
eq14..Y('8')=E=0 ;
eq15..Y('9')=E=0 ;
eq16..Y('11')=E=0 ;
eq17..Y('13')=E=0 ;
eq18..Y('14')=E=0 ;
eq19..Y('15')=E=0 ;
eq20..Y('17')=E=0 ;
eq21..Y('18')=E=0 ;
eq22..Y('19')=E=0 ;
eq23..Y('22')=E=0 ;
eq24..Y('26')=E=0 ;
eq25..Y('28')=E=0 ;
eq26..Y('29')=E=0 ;
eq27..Y('30')=E=0 ;
eq28..Y('33')=E=0 ;
eq29..Y('39')=E=0 ;
eq30..Y('40')=E=0 ;
eq31..Y('45')=E=0 ;
eq32..Y('51')=E=0 ;
eq33..Y('52')=E=0 ;
eq34..Y('53')=E=0 ;
eq35..Y('54')=E=0 ;
eq36..Y('57')=E=0 ;
eq37..Y('62')=E=0 ;
B-3
EK-B’NİN DEVAMI
eq38..Y('64')=E=0 ;
eq39..Y('66')=E=0 ;
eq40..Y('67')=E=0 ;
eq41..Y('68')=E=0 ;
eq42..Y('69')=E=0 ;
eq43..Y('70')=E=0 ;
eq44..Y('71')=E=0 ;
eq45..Y('74')=E=0 ;
eq46..Y('75')=E=0 ;
eq47..Y('77')=E=0 ;
eq48..Y('78')=E=0 ;
eq49..Y('79')=E=0 ;
eq50..Y('80')=E=0 ;
eq51..Y('81')=E=0 ;
eq52..sum(k,Y(k))=E=21 ; (ÖRNEK OLARAK 21 YAZILMIŞTIR, BU SAYI İSTEĞE GÖRE DEĞİŞTİRİLEBİLİR)
model tasima /all/ ;
solve tasima using mip minimizing z ;
display a.l,b.l,c.l,Y.l,e.l ;
file sonuc/c:\GAMSTez\sonucPSİZ.txt/;
put sonuc;
*put system.ifile/;
*put system.date/;
*put system.time/;
put @15 "sure", @25 "z"/;
put @8 tasima.resusd, @20 z.l/;
put @1 "i",@13 "k", @25 "j", @46 "c"/;
loop((i,k,j),if(c.l(i,k,j)>0, put i.tl,k.tl,j.tl,c.l(i,k,j)/));
put @1 "k",@13 "m",@25 "j", @46 "b"/;
loop((k,m,j),if(b.l(k,m,j)>0, put k.tl,m.tl,j.tl,b.l(k,m,j)/));
put @1 "m",@13 "j", @34 "a"/;
loop((m,j),if(a.l(m,j)>0, put m.tl,j.tl,a.l(m,j)/));
put @1 "i",@13 "j", @34 "e"/;
loop((i,j),if(e.l(i,j)>0, put i.tl,j.tl,e.l(i,j)/));
put @1 "k", @23 "Y"/;
loop((k),if(Y.l(k)>0, put k.tl,Y.l(k)/));
putclose sonuc;
B-4
Download

ana dağıtım üssü yer seçim problemleri ve bir