T. C. Selçuk üNİversitesi fen biLİmleri enstiTÜSÜ

Çizelge 3.1. ZB_ARP için literatür taraması

YIL	YAZARLAR	ÇÖZÜM YÖNTEMİ	MODELLEME YAKLAŞIMI
1989	Malandraki, C.	Kesin Algoritma	Zamana Bağlı Adımsal Ulaşım Süresi Fonksiyonu (ZBAUSF)
1991	Ahn ve Shin	Sezgisel	ZBAUSF
1992	Malandraki ve Daskin	Sezgisel	ZBAUSF
1992	Hill ve Benton	Sezgisel	ZBAUSF
1996	Malandraki ve Dial	Sezgisel	ZBAUSF
2000	Park, Y.B.	Sezgisel	ZBAUSF
2001	Jung ve Hanghani	Sezgisel	ZBAUSF
2003	Ichoua ve ark.	Sezgisel	Zamana Bağlı Hız Fonksiyonu (ZBHF)
2004	Fleischmann ve ark.	Sezgisel	ZBHF
2005	Haghani ve Jung	Sezgisel	ZBHF
2006	Chen ve ark.	Sezgisel	ZBHF
2007	Woensel ve ark.	Sezgisel	ZBHF
2008	Woensel ve ark.	Sezgisel	ZBHF
2008	Xin ve ark.	Sezgisel	ZBHF
2008	Hashimoto ve ark.	Sezgisel	ZBHF
2008	Donati ve ark.	Sezgisel	ZBHF
2009	Kuo ve ark.	Sezgisel	ZBHF
2009	Soler ve ark.	Sezgisel	ZBHF
2009	Zhang ve ark.	Sezgisel	ZBHF
2009	Jabali ve ark.	Sezgisel	ZBHF
2010	Duan ve ark.	Sezgisel	ZBHF
2010	Kuo, Y.	Sezgisel	ZBHF
2011	Figliozzi, M.A.	Sezgisel	ZBHF
2011	Liu ve ark.	Sezgisel	ZBHF
2011	Balseiro ve ark.	Sezgisel	ZBHF
2012	Figliozzi, M.A.	Sezgisel	ZBHF
2012	Kritzinger ve ark.	Sezgisel	ZBHF
2013	Dabia ve ark.	Kesin Algoritma	ZBHF
2014	Koç ve Karaoğlan	Kesin Algoritma	ZBHF
2014	Mousavipour ve Hojjati	Sezgisel	ZBHF
2014	Zhang ve ark.	Sezgisel	ZBHF
2015	Johar ve ark.	Sezgisel	ZBHF

Zaman bağımlı ulaşım süreleri ilk kez Malandraki ve Daskin (1989,1992) tarafından, ZB_ARP ve Zaman Bağımlı Gezgin Satıcı Problemi (ZB_GSP) üzerinde ele alınmıştır. Gezgin satıcı problemi araç sayısının bir ve araç kapasitesinin sonsuz olduğu ARP olarak kabul edilebilir. Bu çalışmada, “Zamana Bağlı Adımsal Ulaşım Süresi Fonksiyonu; ZBAUSF (stepwise travel time function)” kullanılmış, düğümler için zaman pencereleri dikkate alınmış ve müşterilerde beklemelere izin verilmiştir. Problemlerin çözümü için matematiksel model, dal-kesme algoritması ve aç gözlü sezgiseli (greedy heuristic) önerilmiş ve düğüm sayısının 10 ile 25 arasında değiştiği test problemleri çözülmüştür.

Ahn ve Shin (1991), çalışmalarında ZB_ZP_ARP için kazanç, başlangıç ve yerel iyileştirme algoritmalarını kullanmışlardır.

Hill ve Benton (1992) tarafından yapılan bir çalışmada ise aracın bir düğümden çıkış zamanına bağlı olarak ulaşım süresi yerine hız değeri kullanılmıştır. Buna ek olarak hız sürelerinin tahminine yönelik de bir çalışma ortaya konmuştur. Problemin çözümü için sezgisel bir yöntem geliştirilmiştir. Bu çalışmada, 5 müşteriden oluşan bir ZB_ARP ve bu probleme benzerlik gösteren bir problem olan zaman bağımlı çok satıcılı GSP çözülmüştür.

Malandraki ve Dial, 1996 yılında yaptıkları çalışmalarında ZB_GSP için dinamik programlama yaklaşımı geliştirmişlerdir. Bu çalışmada, geliştirilen yöntem ile değişik ulaşım süresi fonksiyonları kullanılabileceği ifade edilmesine rağmen sadece ZBAUSF kullanılmıştır.

Park (2000), iki kriterli zaman ve alan bağımlı araç çizelgeleme problemini dikkate almıştır. Amaç toplam operasyon süresinin en küçüklenmesi ve toplam ağırlığın en küçüklenmesidir. Problem için karma tamsayılı doğrusal programlama formülasyonu oluşturmuş ve çözüm için iki kriterli kazanç algoritmasını önermiştir.

Jung ve Haghani (2001), çalışmalarında ZB_ARP için bir matematiksel model ve bir genetik algoritma önermişlerdir. Önerilen genetik algoritma küçük boyutlu test problemleri için 33 problemin sadece 2’sinde eniyi çözüme ulaşamamışken en büyük sapma %5’den küçük çıkmıştır. Büyük boyutlu problemler çözüldüğünde ise kesin çözümle genetik algoritma ile elde edilen sezgisel çözüm arasındaki en büyük sapma ve en büyük alt sınır değeri %7’den küçük çıkmıştır.

ZB_ARP için literatürde yer alan ilk çalışmalarda “Zamana Bağlı Adımsal Ulaşım Süresi Fonksiyonu (ZBAUSF)” kullanılmıştır. Bu durum aracın daha hızlı gidebileceği zaman aralığına kadar müşterilerde beklemesine izin veren varsayımı içermektedir ancak bu varsayım pratik hayata pek uygun değildir. Örneğin, Şekil 2.1 ve Şekil 2.2’ye göre 4. zaman diliminde çıkış yapan bir araç bir sonraki düğüme 8. zaman biriminde ulaşacaktır. Ancak araç 6. zaman diliminde çıkış yapmış olsaydı 7. zaman diliminde bir sonraki düğüme varmış olacaktı. Bu durumda araç daha erken bir zaman diliminde çıkmasına rağmen daha geç bir zaman diliminde hedefine ulaşmış olacaktı.

Şekil 2.1. Çıkış zamanına bağlı ulaşım süreleri


Şekil 2.2. Çıkış zamanına bağlı ulaşım sürelerine göre varış zamanları

Literatürde FIFO (First In First Out) olarak adlandırılan ve düğümden ne kadar erken çıkılırsa diğer düğüme o kadar erken varılacağı anlayışına dayalı bu durumu sağlamak amacıyla iki yaklaşım gerçekleştirilmiştir. Bunlar (Koç, 2012);

1. Aracın daha erken gidebileceği bir sonraki zaman dilimine kadar müşteride bekletilmesi: Şekil 2.1’deki örnekte 4. zaman diliminde çıkış yapmaya hazır olan aracın 6. zaman dilimine kadar bekletilmesi bu yaklaşıma örnek olarak verilebilir. İşini bitiren aracın müşteride bekletilmesinin söz konusu olmadığı ve pratikte de karşılaşılmayan bir durum olduğu için bu yaklaşım birçok araştırmacı tarafından eleştirilmektedir.

2. FIFO özelliğini sağlayacak düzeltme fonksiyonlarının geliştirilmesi: Bu yaklaşımda ulaşım süresi fonksiyonunun adımsal yapısı parçalı doğrusal yapıya dönüştürülmektedir. Bu dönüşüme göre, ardışık zaman dilimleri arasındaki geçiş noktalarının ± ∆ genişliğinde kalan bölümü için α + βt düzeltmesi yapılmaktadır ki fonksiyonun FIFO özelliğini sağlaması için β ≥ -1 olması gerekmektedir (Balseiro ve ark., 2011). Şekil 2.3’de bu yaklaşım örnek üzerinde gösterilmektedir. Bu yaklaşımda, ulaşım sürelerinin gerçek değerleri yerine yaklaşık değerlerini vereceği için sonuçta ya yerel en iyi ya da uygun olmayan çözümlere ulaşılma riski ile karşılaşılmaktadır. Ayrıca her zaman β ≥ -1 şartını sağlayacak fonksiyonlarla karşılaşamama ihtimali de bulunmaktadır (örneğin zaman aralıklarının dar ve ulaşım süreleri arasındaki farkın büyük olması gibi).

Şekil 2.3 FIFO özelliği olmayan ulaşım sürelerinin düzeltme fonksiyonu uygulaması
2003 yılında Ichoua ve arkadaşları tarafından yapılan çalışmaya kadar ZB_ARP üzerine yapılan çalışmalarda ZBAUSF kullanılmış ve FIFO özelliğini sağlamak amacıyla yukarda bahsedilen durumlar göz önüne alınmıştır. FIFO özelliğini en iyi şekilde sağlayan ve pratiğe oldukça yakın bir varsayım olan ZBHF yaklaşımı ise ilk kez Ichoua ve arkadaşları (2003) tarafından literatüre kazandırılmıştır. ZBHF yaklaşımında ZBAUSF’de olduğu gibi planlama periyodu zaman dilimlerine bölünmekte ve her düğüm için aracın çıkış zamanına bağlı bir hız fonksiyonu tanımlanmaktadır. Bu yaklaşım Şekil 2.4 ve Şekil 2.5’te gösterilmiştir.


Şekil 2.4 Çıkış zamanına bağlı hız


Şekil 2.5 Çıkış zamanına bağlı hıza göre varış süreleri
Şekil 2.4’te düğümler arası mesafenin 4 birim olduğu bir hat için çıkış zamanına bağlı hızlar, Şekil 2.5’te ise bu hızlara bağlı olarak bir sonraki düğüme varış zamanı gösterilmektedir. Bu şekillerden de görüldüğü gibi çıkış zamanı ne olursa olsun araç bir düğümden ne kadar erken çıkarsa bir sonraki düğüme o kadar erken ulaşmaktadır.

Ichoua ve ark. (2003), bu çalışmalarında gevşek zaman pencereli ZB_ARP’yi ele almış ve problemin çözümü için Tabu Arama (TA) sezgiseli geliştirmişlerdir. Gevşek zaman pencereli problemlerde her müşteri için bir zaman penceresi söz konusudur, ancak bu zaman penceresi dışında da, belirli bir ceza maliyetine katlanarak, müşteriye hizmet verilebilmektedir.

Fleischmann ve ark. (2004) tarafından yapılan bir çalışmada ise yine ZBAUSF kullanılmış ve FIFO özelliğini sağlamak amacıyla fonksiyon üzerinde düzeltme işlemleri gerçekleştirilmiştir. Bu çalışmada, ARP için geliştirilen basit sezgisel yöntemler (Kazanç Algoritması (Saving Algorithm), Sıralı Ekleme Algoritması (Sequentil Insertion Heuristic), vb.) ZB_ARP için uyarlanarak, Berlin şehrinin trafik sistemini içeren, 216 zaman aralığından oluşan bir gerçek hayat problemi ve 7 adet test problemi çözülmüştür.

Haghani ve Jung (2005), zaman bağımlı dinamik ARP (ZB_DARP) için bir genetik algoritma önermişlerdir. Araştırmacılar rassal olarak ürettikleri test problemlerini kullanmışlar ve önerilen genetik algoritmanın performansını, kesin sonuçlar ve bir alt sınırın sonuçlarıyla karşılaştırarak ölçmüşlerdir.

Chen ve ark.’nın 2006 yılında yaptıkları çalışmada ise dinamik zamanlı ZB_ARP ele alınmıştır. Bu problemde bazı müşterilerin talepleri planlama periyodunun başında bilinmekte, bazı müşterilerin talepleri ise planlama periyodu içerisinde ortaya çıkmaktadır. Böyle bir durumda, yeni talepler ortaya çıktığı zaman, araçların mevcut durumları da göz önüne alınarak, yeni bir dağıtım planı belirlemek gerekmektedir. Problem için bir matematiksel model ve sezgisel yöntem geliştirilmiştir. Geliştirilen matematiksel model ile herhangi bir deneysel çalışma yapılmazken sezgisel yöntem literatürden türetilen test problemleri ve gerçek hayat verisi kullanılarak test edilmiştir.

Woensel ve ark. (2007), trafik sıkışıklığını göz önüne alan kuyruk teorisine dayalı bir sezgisel yaklaşım geliştirmişlerdir. Önerilen yaklaşım oldukça gerçekçidir.

Woensel ve ark. 2008 yılında yaptıkları bir sonraki çalışmalarında zaman bağımlı ve kapasiteli ARP’yi çözmek için bir tabu arama algoritması geliştirmişlerdir. Seyahat zamanlarını belirlemek için kuyruk teorisine dayalı ve araç hacmiyle bağlantılı yaklaşımlar kullanmışlar, 32 ve 80 arasında değişen müşteri sayıları için problemleri çözmüşlerdir.

Xin ve ark. (2008) tarafından yapılan bir çalışmada ise ZBHF yaklaşımının kullanıldığı dinamik ve statik ZB_ARP için Genetik Algoritma (GA) önerilmiştir. Bu algoritmada, kromozom yapısı olarak permütasyon kodlama kullanılmış ve basit ayrıştırma yöntemleri kullanılarak kromozom gerçek çözüme dönüştürülmüştür.

Hashimoto ve ark. (2008) tarafından yapılan bir çalışmada ise ZBHF yaklaşımının kullanıldığı ZB_ZP_ARP için doğrusal olmayan bir matematiksel model ve Yinelemeli Yerel Arama (YYA, Iterated Local Search) yöntemi geliştirilmiştir. YYA yöntemi literatürden türetilen test problemleri üzerinde test edilmiştir. Deneysel çalışmalarda iyi sonuçlar elde edildiği raporlanmasına rağmen herhangi bir karşılaştırmalı sonuç sunulmamıştır.

Karınca Kolonisi Optimizasyonu (KKO) yöntemi, bir çok çalışmada kullanılmış ve başarılı sonuçlar vermiştir (Balseiro ve ark., 2011; Donati ve ark., 2008; Zhang ve ark., 2009; Liu ve ark., 2011).

Kuo ve ark. (2009) tarafından yapılan bir çalışmada ZBHF yaklaşımının kullanıldığı ZB_ARP ele alınmış ve problemin çözümü için TA algoritması geliştirilmiştir.

Soler ve ark. (2009), çalışmalarında ZB_ZP_ARP’yi değişik dönüşüm teknikleri ile Asimetrik Araç Rotalama Problemine (AARP) dönüştürmüş ve bilinen çözüm yöntemleri ile çözülebileceğine değinmişlerdir. Ancak, dönüşüm sonucunda elde ettikleri problemin çok büyük olması bu dönüşüm tekniğinin küçük boyutlu problemlerde bile kullanılabilirliğini zorlaştırmaktadır. Ayrıca çalışmada herhangi bir deneysel çalışma bulunmamaktadır.

Jabali ve ark., (2009), stokastik ZB_ARP’yi ele aldıkları çalışmalarında müşterilerde beklenmedik gecikmeleri ele almışlardır. Problemin çözümü için TA sezgiseli önermişler ve literatürden türettikleri test problemleri üzerinde deneysel çalışmalar gerçekleştirmişlerdir.

Duan ve ark., (2010) çalışmalarında rassal anahtarlamanın kullanıldığı GA geliştirmiş ve test problemleri üzerinde algoritmanın performansı test etmişlerdir.

Kuo (2010), tarafından yapılan çalışmada ise ZB_ARP’de harcanan yakıtın enküçüklenmesi için Tavlama Benzetimi (TB) algoritması geliştirilmiştir. Önerilen TB algoritması literatürden türetilen test problemleri üzerinde, literatürde daha önce kullanılan amaç fonksiyonları da (toplam rota uzunluğu ve toplam rota süresi) dikkate alınarak çözülmüş ve bu amaç fonksiyonları arasındaki ilişki incelenmiştir. Sonuç olarak, toplam rota uzunluğu ile toplam rota süresi birbirleri ile çelişmezken (birisinin amaç fonksiyonu değeri düşerken diğerinin ki de düşmekte), bu iki amaç fonksiyonunun toplam harcanan yakıt ile çeliştiği görülmüştür.

Figliozzi’nin (2011) yaptığı çalışma literatürde bu alanda yapılan ilk çalışmadır. ZB_ARP’de CO₂ salınımını analiz eden bir matematiksel model önerilmiştir. Sıkı zaman pencereli ZB_ARP’yi günlük trafik bilgileriyle ele alarak, CO₂ salınımı üzerindeki etkiyi bir gerçek hayat uygulaması yaparak ölçmüştür. Ölçümleri sonucunda trafik sıkışıklığının ve araç hızının, CO₂ salınımı üzerinde önemli etkileri olduğunu tespit etmiştir.

Figliozzi (2012) sıkı ve esnek zaman pencereli problem için bir sezgisel algoritma geliştirmiştir. Çalışmada trafik sıkışıklığı için klasik araç hızlarını göz önüne alan yinelenebilir test problemleri önerilmiştir.

Kritzinger ve ark. (2012) gerçek dünya trafik bilgileri doğrultusunda Viyana şehri için bir değişken komşu arama sezgiseli önermişlerdir.

Dabia ve ark., 2013 yılında yapmış oldukları çalışmada ZB_AP_ARP için dal- fiyat algoritması geliştirmişlerdir. Amaç toplam bekleme sürelerini enküçüklemektir. Geliştirdikleri algoritmayı literatürde var olan test problemlerine zaman bağımlı kısıtlar ekleyerek çözmüşler ve 25 müşterili problemler için % 63, 50 müşterili problemler için % 38 ve 100 müşterili problemler için % 15 oranında başarılı sonuçlar elde etmişlerdir.

Koç ve Karaoğlan, ZB_ARP için doğrusal bir matematiksel model geliştirmişlerdir. Geliştirdikleri matematiksel modeli literatürde bulunan test problemleri ile çözerek üç farklı senaryo analizi gerçekleştirmişlerdir.

Mousavipour ve Hojjati 2014 yılında yapmış oldukları çalışmada ZB_ARP için trafik akışına dayalı bir matematiksel model önermişlerdir. Daha sonrasında ise parça sürüsü optimizasyonu (PSO) geliştirmişlerdir. Geliştirdikleri matematiksel model ve PSO yöntemini küçük ve orta boyutlu problemler için karşılaştırmışlardır.

Zhang ve ark., (2014) yaptıkları bu çalışmada ZB_ARP ve ETD_ARP problemleri için Tabu Arama ve Karınca Kolonisi Optimizasyonunu bütünleşik olarak kullanmışlardır. Bütünleşik algoritmanın bulduğu sonuçları KKO ve TA algoritmalarının çözümleriyle karşılaştırmışlar ve daha iyi çözümler bulmuşlardır.

Johar ve ark. (2015), yaptıkları çalışmada ZB_ARP için değişken komşu arama (DKA) ve TA algoritması geliştirmişlerdir. Geliştirdikleri bu sezgiselleri literatürdeki test problemleri ile karşılaştırmışlardır. Bu karşılaştırma sonucunda DKA algoritmasının daha iyi sonuçlar verdiği gözlemlenmiştir.

Yapılan literatür taraması sonucunda, FIFO özelliğini en iyi şekilde sağlayan ZBHF yaklaşımının kullanıldığı ZB_ARP için yapılan çalışmaların hemen hemen tamamında sezgisel yöntemler üzerinde yoğunlaşıldığı görülmektedir. Bu çalışmalarda geliştirilen matematiksel modeller de doğrusal olmayan bir yapıya sahiptir ki bu modellerle çok küçük boyutlu problemler bile çok uzun sürelerde çözülebilmektedir.

2.2. Topla- Dağıt Araç Rotalama Problemi (TD_ARP)
Tesislerden müşterilere yapılacak taşıma işlemleri ile birlikte müşterilerden tesislere toplama işlemlerinin de aynı araçlarla gerçekleştirildiği problemler olarak tanımlanan Topla-Dağıt ARP son yıllarda üzerinde çeşitli çalışmaların yapıldığı bir problem türü olmuştur. Pratikte birçok örneği bulunan TD_ARP, ARP’nin genelleştirilmiş bir halidir. Sağlık sisteminde, kanların merkezlerden hastanelere dağıtımı esnasında toplama kamplarından merkeze yeni kanların getirilmesi; otomotiv sektöründe, yedek parçaların bölge bayilerine dağıtımı esnasında kullanılmış parçaların geri dönüşüm için fabrikalara geri gönderilmesi; gıda sektöründe, günlük taze ürünlerin marketlere dağıtımı esnasında günü geçmiş ve bozulmuş ürünlerin geri toplanması, TD_ARP’ye örnek olarak verilebilir (Karaoglan, 2009).

TD_ARP’nin temel varsayımları aşağıda özetlenmiştir:

1. Her müşteriye kesinlikle bir kez uğranmalı,

2. Bir rota depodan başlamalı ve tekrar depoda son bulmalı,

3. Rota üzerinde, aracın topladığı ve dağıtacağı yük miktarı araç kapasitesini geçmemelidir.

Ayrıca TD_ARP’de bir müşteriden toplanan ürünün diğer bir müşteriye dağıtımı söz konusu değildir. Yani bütün talepler ya depodan müşteriye ulaştırılmakta ya da müşteriden depoya taşınmaktadır (Nagy ve Salhi, 2005).

Bu varsayımlar altında TD_ARP’nin 3 farklı türü bulunmaktadır. Bunlar;

1. Önce dağıt sonra topla araç rotalama problemi (ÖDST_ARP): Bu problemde müşteriler dağıtım (linehaul) ve toplama (backhaul) müşterileri olmak üzere iki gruba ayrılır. Araçların dağıtım planının önce dağıtım yapılacak olan müşterilere daha sonra toplama yapılacak müşterilere uğrayıp depoya dönecek şekilde yapılması ÖDST_ARP olarak adlandırılabilir (Parragh ve ark., 2008)

Her grup yalnızca dağıtım veya yalnızca toplama müşterilerinden oluşmalıdır. Her rotada eğer varsa toplama yapılacak müşterilere, dağıtım yapılacak müşterilere uğrandıktan sonra uğranılmalıdır. Bu çeşit bir rota oluşturmak aslında uygulamadaki zorunluluklardan doğmaktadır. Gerçek hayatta özellikle tır gibi arkadan yükleme-boşaltma yapılabilen araçlarda, araç içindeki malların yer değiştirmesi, taşınması ve yeniden düzenlenmesi güç ise; önce dağıtım yapılacak müşterilere uğranarak malların dağıtılması, daha sonra toplama yapılacak müşterilere uğranarak malların toplanması gerekliliği ortaya çıkar. Ana depolardan marketlere sebze-meyve dağıtımından sonra üreticilerden yeni ürünlerin depoya taşınması bu problem tipine örnek olarak verilebilir.

2. Karma topla- dağıt araç rotalama problemi (KTD_ARP): ÖDST_ARP’de müşteri öncelikleriyle ilgili yapılan varsayımın kaldırılması ile elde edilen problem tipidir. Yani her rotada, öncelik olmaksızın dağıtım ve toplama müşterileri istenilen sırada karışık olarak ziyaret edilebilir. KTD_ARP tipindeki problemlerde araç kapasitesinin kontrolü daha karmaşıktır. Çünkü rotada ilerleyen aracın yükü dalgalanmaktadır. Araç içerisinde yeniden yüklemenin mümkün olduğu durum için geçerli bir problem tipidir. Hizmet sektöründe, depodan müşterilere kargolar dağıtılırken diğer müşterilerden depoya götürülmek üzere kargoların toplanması; sağlık sektöründe, kanların merkezlerden hastanelere dağıtımı esnasında toplama kamplarından merkeze yeni kanların götürülmesi bu problem tipine örnek olarak verilebilir.

3. Eş zamanlı topla- dağıt araç rotalama problemi (ETD_ARP): TD_ARP’nin daha önce bahsedilen iki türünde müşteriler ya toplama ya da dağıtım müşterisi olabilmekteyken, ETD_ARP’de ise müşteriler aynı anda hem dağıtım hem de toplama müşterisi olabilirler. Böyle bir durumda araç müşteriye önce verilecek ürünü bırakmakta sonra toplanacak ürünü almaktadır. Gıda sektöründe, içeceklerin marketlere bırakıldıktan sonra aynı marketten boş şişelerin geri dönüşüm amaçlı toplanması (Ropke ve Pisinger, 2006); otomotiv sektöründe, yedek parçaların bölge bayilerine dağıtımı esnasında kullanılmış parçaların geri dönüşüm için fabrikalara geri gönderilmesi bu problem tipine örnek olarak verilebilir.

Tez çalışmasında kullanılacak olan ETD_ARP için literatürde yapılmış çalışmalar sentezlenerek Çizelge 2.2.’de kronolojik sırada özetlenmiştir.