Ulaştırma ve Lojistik Kongreleri

Makarna Endüstrisinde Araç Rotalama Problemleri

Nilgün Moralı
Prof. Dr., Hasan Kalyoncu Üniversitesi, Gaziantep, Türkiye

Gülcemal Acar
Hasan Kalyoncu Üniversitesi, Gaziantep, Türkiye

Makarna, birçok ülkede üretimi yapılan yaygın olarak tüketilen, uzun süreli saklama ömrüne sahip olan bir gıda maddesidir.  Makarna çalışma hayatının yoğunluğuna dayalı olarak, yapımı ve tüketimi  hızlı olan günümüzde yaygınlaşması ile üretiminin artmasıyla makarna ön plana çıkmaktadır. Böylelikle tedarik zincirinin dallarından biri olan dağıtım ağı devreye girmektedir. Günümüzde teknolojinin hızlı gelişmesi ve taşımacılık alanında müşteri taleplerinin kısa zamanda, minimum maliyetle  karşılanması da büyük bir önem kazanmaktadır.  Bunu karşılayabilmek için Araç Rotalama Problemleri  (ARP) bu tür sorunların çözümünde kullanılan bir karmaşık optimizasyon problemidir.Gezgin satıcı problemi (GSP), n adet şehir arasındaki mesafelerin bilindiği durumda, şehirlerin her birine yalnız bir kez uğramak şartıyla, başlangıç noktasına geri dönülmesi esasına dayalı, tur boyunca kat edilen toplam yolun en kısa olduğu şehir sıralamasının (optimal rota) bulunmasının amaçlandığı bir problemdir. Dağıtım, rotalama, kuruluş yeri belirleme, planlama, lojistik gibi problemlerde geniş bir uygulama alanına sahip olan gezgin satıcı problemi, aynı zamanda optimizasyon alanında, araştırmacılar tarafından üzerinde uzun yıllardır çalışmalar yapılan NP-hard (çözümü zor) sınıfında yer alan bir problemdir.

Gezgin Satıcı probleminin çözümü;

• Başlangıç için seçilebilecek n tane şehir vardır.
• Bu şehirlerden birisi başlangıç noktası olacağı için, satıcı n-1 farklı şehirde satış yapabilir.
• İkinci şehire geçince satıcının satış yapabileceği şehir sayısı n-2 olur.

Buradan yola çıkılarak satıcının n! değişik tur arasından seçimi olacaktır ARP, temeli gezgin satıcı problemlerine dayanmaktadır. Bir veya birkaç depodan müşterilere ürün dağıtımı ve toplanması olarak nitelendirlebilir. ARP’de çoğu zaman müşteri  talepleri, araç kapasiteleri ve zaman gibi kısıtlamalarla karşı karşıya kalınabilir. ARP, sınırlı kapasiteye sahip araçların depodan başlayarak belirli bir rota üzerine dağılmış bütün müşterilere en az maliyetlle ve en hızlı şekilde dağıtımı yapılacak rotaların oluşturulmasıdır. Bir noktadan başka bir noktaya gidilmesi için kullanılabilecek en kısa yolun seçilmesi maliyeti minimuma indirmeyi amaçlamaktadır. Büyük kapasiteli firmalarda coğrafi yapının ve müşterinin büyüklüğünden dolayı dağıtım maliyetleri de artacaktır (Tatar 1993: 100 - 101). Firmaların taşıma maliyetlerini etkileyen ulaşım türleri arasında kara, deniz, hava ve demiryolu olduğu gibi boru hatlarından da söz etmek mümkündür (Tatar, 1992: 52).

Günümüzde araç rotalama probleminin uygulanabileceği birçok alan bulunmaktadır. Örneğin;

• Süt dağıtma ve toplama
• Havaalanlarında yolcu ve yük taşıması
• Banka ve ATM ‘lere para dağıtımı
• Çöp toplama
• Posta, kargo dağıtımı
• Depolardan ürün dağıtımı
• İnsani yardım lojistiği vb.

Araç rotalama problemleri  bu şekilde birçok alanda uygulanabilir ve milyonlarca dolar tasarrufu elde edilebilir.  Dağıtım esnasındaki en küçük değişiklik veya  mesafe kısıtı bile büyük bir ölçüde değişikliklere sebep olabilir.  Bu yüzden bu zamana kadar bu problem üzerinde çok durulmuş ve iyi bir çözüm yöntemi bulabilmek için sürekli geliştirilmiştir.Kapasite kısıtlı araç rotalama problemi (KK-ARP), NP-zor problemi sınıfında yer almaktadır. Gerçek hayatta uygulandığı zaman kesin yöntemlerle çözüldüğü zaman net bir çözüm bulunmamaktadır. KKARP’de  her aracın belirli bir kapasitesi vardır ve önceden müşteri talepleri önceden bilinmektedir. Araçlar depodan başlayarak müşteriye gider ve daha sonrasında tekrar  depoya geri dönerler.  Müşteri talepleri bölünmemektedir.  Her bir talep noktasına tek bir araç hizmet vermektedir. Periyodik araç rotalama problemi (P-ARP), belirli bir dönemin üretim planlaması yapılmaktadır ve bu süreçte müşteriler birçok kez hizmet talep edebilirler.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.  ARP günlük hayatta çok fazla karşılaşılan bir problemdir.  Bu yüzden ARP ve çeşitleri için birçok çözüm yöntemleri üzerinde sürekli çalışılmaktadır.  Çözüm yöntemleri; kesin çözüm yöntemleri ve sezgisel yöntemler olarak iki farklı gruba ayrılabilir. Kesme düzlemi;  kesin çözüm yöntemlerinin bir alt dalı olarak nitelendirilir. 1959 senesinde Gemory tarafından tam sayılı çözümler geliştirilmiştir. Doğrusal programlama ile çözümü yapılan probleme kesme adlı kısıtlar eklenir ve problem tekrar çözülür. Bu kıstlar ile tam sayılı çözümler elde edilmesi hedeflenir. İstenilen tam sayı durumu sağlanmamış ise yeni kısıtlar eklenerek tam sayı durumu elde edilene kadar çözüme devam edilir.Bu çalışmada özel sektörden seçilen bir makarna fabrikasının taşımacılık problemlerine cevap verilebilecek nitelikte sonuçlar amaçlanmıştır. Üretimi yapılan malların müşterilere dağıtımı için kat ettikleri toplam mesafe ve sürenin minimuma indirilmesi için varış noktalarını ve her müşteri için alternatif güzergahlar belirlenmiştir. Model belirlenirken öncelikle müşterilerin talepleri,araç kapasiteleri göz önünde bulundurulmaktadır.  Bu aşamada da çözüm yöntemleri için Dantzing ve Ramser’in yöntemi, Clarke ve Wright tasarruf algoritması ve kesme  düzlemi kullanılmaktadır. Bununla birlikte fabrikada ne kadar maliyet tasarrufu yapılabileceği incelenmektedir.Belirtilen sebeplerden dolayı ilk olarak problemle ilgili olan ARP ve çeşitlerinden bahsedilerek daha sonrasında çözüm yöntemleri ele alınacaktır. İkinci bölümde,  müşteri talepleri, araç kapasiteleri ve güzergahlar belirlenirken faydalanabilecek yöneylem araştırmalarına, matematiksel modellere yer verilmiştir.

Anahtar Kelimeler: Makarna Endüstrisi, Gezgin Satıcı Problemleri, Araç Rotalama Problemleri