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

Çizelge 2.2. ETD_ARP için literatür taraması

YIL	YAZARLAR	ÇÖZÜM YÖNTEMİ	EK KISITLAR
1989	Min	Sezgisel	-
1992	Halse	Sezgisel	-
2001	Dethloff	Sezgisel	-
2005	Nagy ve Salhi	Sezgisel	-
2005	Crispim ve Brandao	Sezgisel	Rota Uzunluğu (RU), Çok Depolu (ÇD)
2006	Chen ve Wu	Sezgisel	-
2006	Montané ve Galvao	Sezgisel	RU
2006	Ropke ve Pisinger	Sezgisel	ZP
2007	Bianchessi ve Righini	Sezgisel	-
2009	Ai ve Kachitvichyanukul	Sezgisel	-
2009	Zachariadis ve ark.	Sezgisel	-
2009	Gajpal ve Abad	Sezgisel	-
2010	Çatay	Sezgisel	-
2010	Zachariadis ve ark.	Sezgisel	-
2010	Subramanian ve ark.	Sezgisel	-
2011	Zachariadis ve Kiranoudis	Sezgisel	-
2011	Fan	Sezgisel	ZP
2011	Subramanian ve ark.	Kesin Algoritma	-
2012	Wang ve Chen	Sezgisel	-
2012	Tasan ve Gen	Sezgisel	-
2012	Zachariadis ve Kiranoudis	Sezgisel	-
2013	Göksal ve ark.	Sezgisel	-
2013	Liu ve ark.	Sezgisel	ZP
2013	Hezer ve Kara	Sezgisel	-

ZB_ARP’de olduğu gibi ETD_ARP için de yapılan çalışmaların da hemen hemen tamamı sezgisel çalışmalardır. Tanımlarından da anlaşılacağı gibi ETD_ARP, ÖDST_ARP ve KTD_ARP’nin genel halidir. Dolayısıyla, ETD_ARP için geliştirilen bir matematiksel model, doğrudan ya da küçük değişiklikler ile ÖDST_ARP ve KTD_ARP için kullanılabilir (Karaoglan, 2009). Tez çalışmasının bundan sonraki kısmında, daha önce birlikte çalışılmamış olan ve ETD_ARP ve ZB_ARP kısıtlarını da içeren ZB_ETD_ARP için bir matematiksel model önerilecektir.

3. MATERYAL VE YÖNTEM

Bu bölümde çalışmada kullanılan materyal ve yöntemler hakkında bilgiler verilmiştir.

3.1. Materyal
Bu bölümde öncelikli olarak ARP ile ilgili genel bilgiler verilerek ARP’nin çeşitlerinden bahsedilecektir. Daha sonrasında ZB_ARP ve TD_ARP hakkında tanımlar ve açıklayıcı bilgiler sunulmaktadır.
3.1.1. Araç rotalama problemi (ARP)
ARP, coğrafi olarak dağınık merkezlere bir veya birden fazla depodan servis etmek üzere görevlendirilen araçların optimum dağıtım ve toplama rotalarının planlanması problemleridir (Toth ve Vigo, 2002a)

ARP, ilk olarak 1959 yılında Dantzig ve Ramser tarafından yapılan bir çalışma ile literatürde yerini almıştır. Dantzig ve Ramser çalışmalarında, bir gerçek hayat uygulamasını ele almışlar ve servis istasyonlarına benzin dağıtım problemi için bir matematiksel model geliştirmişlerdir. Araç rotalama probleminde her araç bir rota olarak düşünülmektedir. Dolayısıyla hangi müşterinin hangi araç tarafından hizmet göreceği kararını rotalama, söz konusu müşterinin atandığı rotada hangi sırada hizmet göreceği kararını ise çizelgeleme problemi olarak tanımlayan çalışmalar da bulunmaktadır.

Klasik araç rotalama probleminin varsayımları şöyle sıralanabilir:

• 
  Müşteri talepleri bilinmektedir,
  
• 
  Talepler tek bir depodan karşılanmaktadır,
  

• 
  Dağıtım söz konusudur,
  
• 
  Araçlar homojen özelliktedir ve depoda hazır halde beklemektedir,
  
• 
  Depo ile müşteriler arasındaki ulaşım süreleri sabit ve bilinmektedir,
  
• 
  Bir müşteriye yalnızca bir araç hizmet sunar,
  
• 
  Araçların başlangıç ve bitiş düğümleri depodur.
  

Bu varsayımlar ışığında, ARP’de birden çok amaç fonksiyonu kullanılabilir. Bunlardan bazıları şunlardır:

• 
  Araçların sabit maliyetlerine, kat ettiği toplam mesafeye ya da seyahat süresine bağlı olan toplam taşıma maliyetlerini en küçüklemek,
  
• 
  Tüm müşterilere hizmet etmek için gerekli olan toplam araç sayısını en küçüklemek,
  
• 
  Müşterilere parçalı dağıtım yapılmasından kaynaklanan cezaları en küçüklemektir.
  

Araç rotalama problemleri sahip olduğu kısıtlara göre farklı türlere sahiptir ve NP-Zor problemlerdir. Problemi çözmek için gerekli olan hesaplama gücü problemin boyutuyla birlikte üstel olarak artar.

3.1.2 Araç Rotalama Problemi ve Çeşitleri

ARP genel olarak dağıtım ve/veya toplama faaliyetlerinin yönetimiyle uğraşan problemler bütünüdür. Bu konuda verilecek olan kararlar, mevcut araç filosunun yani kaynakların nasıl kullanılacağı ile ilgilidir. Kaynakların verimli kullanılmasıyla taleplerin ihtiyaçlar doğrultusunda etkin bir şekilde karşılanması beklenir. Bu amaçla mevcut araçlar için rotalar tanımlanmaktadır. Şekil 3.1’de bir ARP modelinin şekilsel gösterimi verilmiş olup, numaralandırılmış düğümler müşterileri temsil etmektedir.


Şekil 3.1. ARP’nin Şekilsel Gösterimi
Klasik ARP’nin çözümü her rotanın depodan başlayarak yine depoda son bulduğu ve her müşteriye yalnızca birer defa uğrama kısıtının sağlandığı rotalar kümesidir. Bunun yanında problemin türüne göre bazı yan kısıtların da eklenmesi gerekebilir. En yaygın olan yan kısıtlar; kapasite kısıtı, bir rotada olabilecek en fazla talep noktası kısıtı, bir rotadaki aracın toplam süre kısıtı, talep noktalarına hizmetin başlanabileceği zaman penceresi kısıtı, bir talep noktasının başka bir talep noktasından önce ziyaret edilmesinin gerektiği öncelik kısıtlarıdır (Laporte, 1992).

Bu kısıtlara ve pratik hayattaki uygulama alanlarına göre ARP çeşitli şekillerde sınıflandırılmıştır. Bu sınıflandırma Şekil 3.2’deki gibidir.

Şekil 3.2. Araç Rotalama Probleminin Çeşitleri
Şekil 3.2’de gösterilen ARP çeşitleri kısaca şöyle özetlenebilir:

3.1.2.1. Kısıtlarına göre ARP

Bu alt bölümde ARP için çeşitli kısıtların göz önüne alındığı durumlar için bir sınıflandırma yapılmıştır. Buna göre dokuz farklı problem tipi mevcuttur.

1. 
   Kapasite kısıtlı ARP (KK_ARP): ARP’nin en yaygın türüdür. Literatürde KK_ARP ile ilgili yapılan pek çok çalışma mevcuttur. KK_ARP’de her aracın belirli bir kapasitesi vardır ve müşteri talepleri önceden bilinmektedir. KK_ARP’nin en basit halinde ise her aracın kapasitesi birbirine eşittir. Araçlar depodan harekete başlayarak yine depoya dönerler. Müşteri taleplerinin parçalanması söz konusu değildir.
   

KK_ARP aşağıdaki kriterleri sağlamak koşulu ile araç rotalarının tasarlanmasından oluşur (Santos ve ark., 2010):

• 
  Her bir talep noktasına tek bir araç tarafından hizmet verilmelidir,
  

• 
  Her bir rota depodan başlayıp depoda son bulmalıdır,
  
• 
  Bir aracın hizmet verdiği bütün talep noktalarının toplam talebi aracın kapasitesini aşmamalıdır,
  
• 
  Toplam araç rotalama maliyeti minimize edilmelidir.
  

2. 
   Mesafe kısıtlı ARP (MK_ARP): MK_ARP’de her aracın gidebileceği belirli bir mesafe kısıtı söz konusudur. KK_ARP’de her bir rota için olan kapasite kısıtı yerini maksimum mesafe ya da maksimum zaman kısıtına bırakır (Toth ve Vigo, 2002a).
   

MK_ARP’de rotalara atanmış her aracın kat edebileceği belirli bir toplam mesafe olmalıdır. Bu durum gerçek bir dağıtım probleminde taşınan ürünün cinsinden, araç veya sürücü kısıtlarından dolayı söz konusu olabilir. Eğer taşınan ürünün uzun süre taşıma nedeniyle bozulabilmesi söz konusuysa, ya da araç kullanıcısının sürekli olarak belirli bir süreden daha fazla yolculuk yapamaması söz konusu ise bu kısıt eklenmelidir (Dursun, 2009).

3. 
   Zaman pencereli ARP (ZP_ARP): ZP_ARP’de klasik ARP’den farklı olarak her müşteriye uğranılması gereken belirli zaman aralıkları vardır. Belirli bir zamanda depodan çıkan bir araç müşteriye ulaşmak için belirli bir seyahat süresi geçirmekte ve müşteri için belirli bir süre hizmet verilmektedir. Her müşteri için belirli olan bu servisler o müşterinin içerisinde bulunduğu zaman penceresi içinde başlamalı ve hizmet verilmelidir. Eğer müşteriye erken ulaşılması söz konusu ise zaman penceresine kadar beklemeye izin verilmektedir. Banka teslimatları, posta teslimatı, endüstriyel atık toplama, okul servis aracı rotalama ve çizelgeleme vb. ZP_ARP’nin günlük hayatta karşılaşılan örneklerindendir.
   

Zaman Pencereli ARP iki alt sınıfa ayrılmaktadır Bunlar (Badeau ve ark., 1997);

1. 
   Sıkı Zaman Pencereli ARP (Hard Time Windows VRP): Eğer bir araç, müşterinin söz konusu zaman penceresinin başlangıcından önce müşteriye ulaşmışsa zaman penceresi başlayana kadar beklemek durumundadır. Zaman penceresinin bitişinden sonra servis verilememektedir.
   
2. 
   Esnek Zaman Pencereli ARP (Soft Time Windows VRP): Esnek Zaman Pencereli ARP’de ise müşterilere ilgili zaman pencerelerinin dışında hizmet verilebilmektedir, fakat bu durumda bir ceza maliyeti söz konusudur.
   

4. 
   Bölünmüş talepli ARP (BT_ARP): ARP’nin bu çeşidinde bir müşterinin talepleri birden fazla araç tarafından temin edilebilmekte, yani bir müşteriye farklı araçlar tarafından birden fazla uğranabilmektedir (Koç, 2012). BT_ARP’de en az bir müşterinin talebi araç kapasitesinden büyük olmalıdır. ARP’yi BT_ARP’ye dönüştürmenin kolay bir yolu, her müşteri siparişini daha küçük olan ve bölünemeyen siparişlere ayırarak, dağıtımların parçalanmasına izin vermektir.
   

5. 
   Çok depolu ARP (ÇD_ARP): Klasik ARP problemlerinde ve literatürde bulunan çoğu çalışmada mevcut depo sayısının tek olduğu kabul edilmektedir. ÇD_ARP’ de ise birden fazla depoya izin verilmektedir. Bu problemde depoların ve müşterilerin konumları önceden bilinmektedir ve her depo tüm müşterilerin toplam taleplerini karşılayabilecek kapasiteye sahiptir. Bu problemde her araç hareket ettiği depoya geri dönmek durumundadır. Birden fazla deposu olan bir dağıtım şirketinin araç rotalaması yapılmakta ise çok depolu olma durumunu yapılan modele ilave etmek gerekecektir. ÇD_ARP, NP-zor bir problemdir ve en iyi çözümün elde edilebileceği verimli bir yöntem bulunmamaktadır (Ho ve ark., 2008).
   

6. 
   Topla-dağıt ARP (TD_ARP): Tesislerden müşterilere gerçekleştirilen taşıma işlemleri ile birlikte müşterilerden de tesislere toplama işlemlerinin aynı araçlarla gerçekleştirildiği problemler olarak tanımlanan TD_ARP son yıllarda üzerinde sıkça çalışılan bir problem türü olmuştur. Tez çalışması kapsamında olan TD_ARP çalışmanın sonraki bölümünde daha detaylı olarak incelenecektir.
   

7. 
   Periyodik ARP (P_ARP): ARP’nin bir başka çeşidi olan P_ARP’de belirli bir dönemin planı yapılmaktadır ve müşteriler bu süreçte birden çok kez hizmet alabilirler. Daha sonrasında ise problem her müşteri için ziyaret kombinasyonunun eş zamanlı seçiminden ve planlama dönemi için araç rotalarını oluşturmaktan ibarettir. Müşterilere yapılacak servis sayısı müşterilerin talep miktarlarına, stok alanlarına göre değişmektedir.
   

Bu problem sınıfı bakkaliye, içecek endüstrisi, atık toplama gibi alanlarda ortaya çıkmaktadır (Hemmelmayr ve ark., 2009).

8. 
   Stokastik ARP (S_ARP): S_ARP klasik ARP’nin, problem elemanlarından bir ya da birkaçının rassal olduğu durumlarda karşılaşılan bir problem çeşididir.
   

S_ARP’nin 3 farklı türü vardır (Ekizler, 2011);

• 
  Stokastik müşteriler: Her i müşterisi p_i olasılığı ile vardır, 1-p_i olasılığıyla yoktur.
  
• 
  Stokastik talepler: Her müşterinin talebi, rassal bir değişkendir.
  
• 
  Stokastik zamanlar: Servis zamanları ve dolaşım zamanları rassal değişkenlerdir.
  

STK_ARP’nin çözümü için geliştirilen bir yöntemde iki aşamalı çözüm kullanılır. Önce rassal değişkenlerin gerçekleşme değerleri bilinmeden bir ilk çözüm belirlenir. İkinci adımda ise, rassal değişkenlerin değerleri bilindiğinde düzeltici bir işlem yapılabilir.

9. 
   Zaman bağımlı ARP (ZB_ARP): ARP için yapılan çalışmaların çok büyük bir kısmında düğümler arası ulaşım süresinin sabit alındığı görülmektedir. Ancak, şehir içi taşımacılıkta gün içerisinde taşımacılık yapan araçların hızı ve buna bağlı olarak da ulaşım süreleri kullanılan yol ve yolun kullanıma başlama zamanına bağlı olarak değişiklik göstermektedir. Bu problem literatürde ZB_ARP olarak adlandırılmaktadır. ZB_ARP problemi çalışmanın ikinci bölümünde daha detaylı olarak incelenmiştir.
   

3.1.2.2. Yolların durumuna göre ARP
Yolların durumuna göre ARP iki nokta arasındaki yol mesafelerinin geliş ve gidiş yönüne göre aynı kalıp kalmamasına göre ikiye ayrılmaktadır:

1. 
   Simetrik ARP (S_ARP): Klasik ARP’de bir düğümden diğerine gidiş ve dönüş mesafeleri birbirine eşit kabul edilir. Bu tür problemler literatürde S_ARP olarak adlandırılmaktadır.
   

2. 
   Asimetrik ARP (A_ARP): Bazı durumlarda ARP’de yer alan x ve y noktaları için x noktasından y noktasına gitmek için gerekli olan mesafe, y noktasından x noktasına olan mesafeye eşit olamayabilir. Bu tip ARP’de araçların ilk olarak hangi müşteriye gideceği önem kazanmakta, bu da rotanın dönüş yönünü saptayarak rota mesafesinin hesaplanmasını belirlemektedir.
   

3.1.2.3. Rotalama durumlarına göre ARP
ARP, rotaların bir depoda başlayıp aynı depoda sona ermesi veya aracın depodan bağımsız olarak seyir güzergâhının en son müşteride bitirilebilmesi durumlarına göre açık ve kapalı uçlu olmak üzere ikiye ayrılır.

1. 
   Açık uçlu ARP (AU_ARP): AU_ARP’de, araçlar klasik araç rotalama probleminde olduğu gibi, son servis noktasından sonra depoya dönmezler. Bu tip problemlerde, rotalar merkez depo ile başlamakta, talep noktası ile sona ermektedir. Araç rotalama probleminin bu türü literatürde yaklaşık yirmi yıl öncesinde görülmesine rağmen, ancak son yıllarda araştırmacıların dikkatini çekmiştir (Li ve ark., 2007).
   

AU_ARP genellikle araç kiralama sistemleri için uygundur. Müşteri araca sadece gidiş için para ödemektedir. Kiralanan aracın son gidiş noktasından sonra nereye gideceği, müşteri tarafından dikkate alınmaz ve dönüş planlaması yapılmaz.

2. 
   Kapalı uçlu ARP (KU_ARP): KU_ARP’de oluşturulan rotaların hepsi bir işletme biriminde başlayıp, aynı birimde sonlandırılmalıdır. Literatürdeki çalışmalar çoğunlukla KU_ARP ile yapılmakta olup, test problemleri KU_ARP için mevcut olduğundan geliştirilen yöntemler KU_ARP üzerinden birbiriyle kıyaslanmaktadır.
   

Taşıma araçları özel olduğu zaman aynı başlangıç ve bitiş noktası olan problemlerle sıkça karşılaşılır. Dağıtım kamyonlarının depodan perakendecilere dağıtım yapıp dönmesi, nakliye araçlarının depodan müşteriye oradan tekrar depoya dönmesi veya okul otobüsleri, gazete dağıtım araçları veya çöp araçlarının hareketleri de bu problem tipindedir. Bu tip problemler, farklı başlangıç ve hedef noktası olan problemlerin farklı bir türüdür. Amaç, noktaların en az ulaşma süresi ve toplam mesafeyle ziyaret edilmesini sağlayacak sırayı bulmaktır (Alkan, 2003).

3.1.2.4. Çevre durumuna göre ARP
Araç rotalama problemleri dinamik ve statik olmak üzere de iki sınıfa ayrılabilir.

1. 
   Dinamik ARP (D_ARP): D_ARP’de yer alan “dinamik” yaklaşımı karar verici için dinamik olarak araç rotaları ve çizelgelenmesi için gerekli bilgilerin açığa çıkmasını ifade etmektedir.
   

D_ARP’nin gerçek hayata uyan birçok örneği sıralanabilir. Gezgin Tamirci (Travelling Repairmen) problemi en çok çalışılan D_ARP örneklerinden biridir. Bir elektrik şirketinin elektrik tedarikindeki ani kesintileri tamir için ev ev dolaşan tamircisi buna bir örnek teşkil edebilir (Larsen, 2001)

2. 
   Statik_ARP (S_ARP): S_ARP müşterilerin bilgilerinin bilindiği durumda, araç filolarının müşteri kümesini toplam zaman ve toplam uzaklık olarak en az maliyetle rotalanmasıdır (Montemanni ve ark., 2002).
   

S_ARP’de rotalama süreci başlamadan önce planlamacı tarafından planlanacak rotalarla ilgili tüm bilgilerin bilinmesi ve rotalar oluşturulduktan sonra rotalamaya ilişkin bilgilerin değişmemesi gerekir (Larsen, 2001). Literatürde çoğunlukla S_ARP üzerinde çalışmalar yapılmış olup bu problem Deterministik ARP olarak da karşımıza çıkmaktadır.
3.2. Metot
Bu bölümde öncelikle problem tanımı yapılarak problem için önerilen matematiksel model ve notasyonlar tanımlanmıştır.
3.2.1. Problem tanımı
ZB_ETD_ARP notasyonal olarak şu şekilde tanımlanabilir: bir şebeke olsun, tüm düğümler kümesini , depo düğümünü, müşteri kümesini ve düğümler arasındaki hatları tanımlamaktadır. ZB_ETD_ARP tanımlanan bu şebeke üzerinde aşağıdaki varsayımlar altında enküçük maliyetli rotaların tespiti problemidir.

• 
  Her müşteriye kesinlikle bir kez uğranmalı,
  
• 
  Bir rota depodan başlamalı ve tekrar depoda son bulmalı,
  
• 
  Rota üzerindeki müşterilerin dağıtım ve toplama talepleri toplamı araç kapasitesini geçmemeli,
  
• 
  Ulaşım süresi, gün içerisindeki zaman dilimlerine ve düğümler arasındaki uzaklığa bağlı olmalıdır.
  

Önerilen karma tamsayılı doğrusal programlama modelinde kullanılan problem girdileri ve değişkenler aşağıda verilmiştir:
Problem Girdileri

Q : araç kapasitesi

K : zaman dilimi kümesi ()

M : büyük bir sayı

: i düğümünün dağıtım talebi ()

: i düğümünün toplama talebi ()

: i düğümü ile j düğümü arasındaki uzaklık ()

: k diliminin başladığı zaman ()

: k diliminin bittiği zaman ()

: k dilimi içerisinde i düğümünden j düğümüne seyahat hızı ()

: i müşterisinin servis süresi ()
0-1 Karar Değişkenleri




Ek Karar Değişkenleri

: i düğümüne girmeden hemen önce araç üzerindeki dağıtılacak ürün miktarı

()

: i düğümünün çıkışında araçta toplanan ürün miktarı ()

: aracın i düğümüne giriş zamanı ()

: aracın i düğümünden çıkış zamanı ()

: eğer araç i düğümünden depoya dönüş yapıyorsa, rotanın depoya dönüş zamanı,

aksi halde “0” ()

: i düğümünden j düğümüne geçiş süresi ()
3.2.2. Matematiksel model
Bu bölümde ZB_ETD_ARP için geliştirilen doğrusal yapıya sahip yeni bir karma tamsayılı matematiksel model sunulmuştur.

Amaç Fonksiyonu
En küçük		(3.1)
Kısıtlar
		(3.2)
		(3.3)
		(3.4)
		(3.5)
		(3.6)
		(3.7)
		(3.8)
		(3.9)
		(3.10)
		(3.11)
		(3.12)
		(3.13)
		(3.14)
		(3.15)
		(3.16)
		(3.17)
		(3.18)
		(3.19)
		(3.20)
		(3.21)
		(3.22)
		(3.23)
		(3.24)
		(3.25)
		(3.26)
		(3.27)
		(3.28)
		(3.29)
Geçerli Eşitsizlikler
		(3.30)
		(3.31)
		(3.32)
		(3.33)

Matematiksel modelde amaç fonksiyonu (3.1) numaralı eşitlik ile belirtilmiştir. Amaç toplam rota süresinin enküçüklenmesidir.

(3.2) ve (3.3) numaralı kısıtlar ARP için geliştirilmiş genel atama kısıtlarıdır ve bir müşteriye mutlaka bir kere hizmet verilmesini garantilemekte, buna ek olarak düğümlerin girdi çıktı dengesini sağlamaktadır.

(3.4) numaralı kısıtlar her hat için, eğer hat kullanılıyorsa aracın seyahate mutlaka bir zaman diliminde başlayıp aynı ya da farklı bir zaman diliminde bitirmesini garantilemektedir.

(3.5–3.11) numaralı kısıtlar MTZ (Miller-Tucker-Zemlin) kapasite ve alt tur eleme kısıtlarıdır. Bu kısıtlar ilk olarak Gezgin Satıcı Problemi (GSP) için Miller ve ark. (1960) tarafından geliştirilmiş, Kulkarni ve Bhave (1985) tarafından ARP’ye uyarlanmış, Desrochers ve Laporte (1991) tarafından kuvvetlendirilmiş ve Kara ve ark. (2004) tarafından düzeltme yapılmıştır. (3.5) ve (3.6) numaralı kısıtlar bir rota üzerinde sırasıyla dağıtım ve toplama taleplerinin toplamlarının kapasiteyi geçmemesini sağlamakla beraber alt turların oluşmasını da engellemektedir. (3.7) - (3.11) numaralı kısıtlar yardımcı karar değişkenlerinin alt ve üst sınırlarını belirleyen kısıtlardır.

(3.12–3.15) numaralı kısıtlar düğümlere giriş ve çıkış zamanlarının, düğümler arası geçiş süreleri ile bağlantılı olmasını sağlamaktadır. (3.12) ve (3.13) numaralı kısıtlar tüm düğümlerden müşterilere giriş, (3.14) ve (3.15) numaralı kısıtlar ise müşteriden depoya dönüş sürelerini belirleyen kısıtlardır.

(3.16) – (3.19) numaralı kısıtlar, zaman dilimleri arasındaki geçişlerin araç hızıyla ve kat edilen mesafeyle bağlantılı olmasını sağlamaktadır. Burada tanımlanan ulaşım süresi hesaplama tekniği sadece ardışık zaman dilimleri için değil, ardışık olmayan zaman dilimleri için de geçerlidir. (3.16) numaralı kısıt aracın k zaman diliminde çıkıp aynı zaman diliminde bir sonraki müşteriye girişini, (3.17) numaralı kısıt ise aracın k zaman diliminde çıkıp daha büyük bir l zaman diliminde bir sonraki müşteriye girişini sağlamaktadır. (3.18) numaralı kısıt aracın k zaman diliminde müşteriden çıkıp aynı zaman diliminde depoya dönüşünü, (3.19) numaralı kısıt ise aracın k zaman diliminde müşteriden çıkıp daha büyük bir l zaman diliminde depoya dönüşünü sağlamaktadır.

(3.20) – (3.23) numaralı kısıtlar zaman dilimlerinin alt ve üst sınırlarının, aracın müşterilerden tüm düğümlere giriş ve çıkış zamanlarıyla bağlantılı olmasını, (3.24) ve (3.25) numaralı kısıtlar ise zaman dilimlerinin alt ve üst sınırlarının aracın müşteriden depoya dönüşü ile bağlantılı olmasını sağlamaktadır.

(3.26) numaralı kısıt, aracın müşteriden çıkış zamanının, müşteriye giriş zamanı ile müşteride geçirdiği servis zamanının toplamına eşit olmasını garantilemektedir.

(3.27) – (3.29) numaralı kısıtlar ise işaret kısıtlarıdır.

(3-30) – (3-33) numaralı kısıtlar ise, önerilen matematiksel modele eklenen geçerli eşitsizliklerdir. Bu eşitsizlikler, çözüm süresini kısaltmak için, matematiksel modellerdeki tamamlayıcı kısıtların gevşetilmesi ile elde edilen doğrusal modelin çözümü ile elde edilen çözümü (alt sınır) eniyi çözüme yaklaştırmak amacıyla kullanılmaktadır. Normal şartlar altında mevcut matematiksel modelin eniyi çözüme ulaşmasında herhangi bir etkisi olmayan bu kısıtlar, doğrusal gevşetme ile anlamlı hale gelmektedir. Geçerli eşitsizlikler, geliştirilen kesin algoritmalarda bazı kesirli ve eniyi olmayan çözümlerin çözüm uzayından atılmasında oldukça etkin matematiksel ifadelerdir.

4. ARAŞTIRMA SONUÇLARI VE TARTIŞMA

Bu bölümde deney tasarımı ve bu deney sonucunda elde edilen sonuçlara yer verilmiştir.
4.1. Deney tasarımı
Bir önceki bölümde önerilen matematiksel modelin etkinliğini araştırmak amacıyla Solomon’un (1987) 25 müşterilik test kümesi ve Ichoua ve ark. (2003) tarafından kullanılan seyahat hızı matrisi göz önüne alınarak ZB_ETD_ARP için toplamda 112 adet yeni test problemi üretilmiştir. Bu test kümesinde müşteriler [100x100]’lük yüzey üzerinde değişik yerleşim parametrelerine göre yerleştirilmiştir. Altı farklı problem tipi tanımlanmıştır; R₁, R₂, C₁, C₂, RC₁, RC₂.

Bu parametrelere göre R tipi problemlerde müşteriler tamamen rassal, C tipi problemlerde müşteriler belirli bölgelerde kümelenerek, RC tipi problemlerde ise müşterilerin bir kısmı rassal kalan kısmı ise belirli bölgelerde kümelenerek yerleştirilmiştir. 1. ve 2. tip problemler ise dağıtım ve toplama taleplerinin Angelelli ve Mansini (2002) tarafından önerilen talep ayırma yöntemine göre oluşturulmuştur. Ayırılmış orijinal talep değerleri dağıtım talebi olarak kabul edilmekte, toplama talebi ise müşteri numarasının tek ya da çift olmasına göre değişmektedir. Eğer i çift ise , eğer i tek ise olarak kabul edilmiştir. Bu ayırma işlemlerinde olduğu durum 1. tip problem ise 2. tip problem olarak alınmıştır.

Seyahat hızları düşük, orta ve yüksek hızda olmak üzere üç kategoride tanımlanmıştır. Bir iş günü üç zaman dilimine bölünmüş ve her zaman dilimine rassal olarak bir araç hız değeri atanmıştır.

Performans ölçütü olarak Yüzde Sapma Değeri (YSD) kullanılmıştır. Bu değer, matematiksel modelden elde edilen üst sınırın (), yine matematiksel modelden elde edilen alt sınırdan () uzaklığını göstermektedir. Bu değer “0”a ne kadar yakın olursa

elde edilen sonuç eniyi çözüme o kadar yakın olmaktadır. YSD değeri şu şekilde hesaplanmaktadır.

Önerilen matematiksel model “GAMS” ara yüzünde kodlanmış ve matematiksel model çözücüsü olarak “CPLEX 10.2” kullanılmıştır. Bütün koşumlarda çözücünün varsayılan parametre seviyeleri kullanılmıştır. Her bir koşum “Intel Xeon E5-1650 (6 Core) 3.2 Ghz” hızında “16 GB” ara belleğe sahip, “Windows 7” işletim sistemi ile çalışan bilgisayarlarda gerçekleştirilmiştir. Bütün koşumlar 1 saat (3600 saniye) çözüm süresi ile sınırlandırılmıştır.

4.2. Deneysel sonuçlar
Deneysel çalışmalara göre elde edilen genel sonuçlar Çizelge 4.1 - 4.6’da sırasıyla R₁, R₂, C₁, C₂, RC₁, RC₂ tipi test problemleri için sunulmaktadır. Bu çizelgelerde ilk sütün problem adını, ikinci ve üçüncü sütunlar matematiksel model çözücüsünden elde edilen üst ve alt sınırı, son iki sütun ise sırasıyla Yüzde Sapma Değeri (YSD)’ni ve çözüm süresini göstermektedir.