Araç Rotalama Problemi (ARP), bir merkezden coğrafi olarak dağılmış çeşitli talep noktalarına dağıtım veya toplama rotalarının, araç filosunun kat ettiği toplam mesafeyi minimize edilecek şekilde bulunmasdir. Araç Rotalama Problemi, Tedarik Zincirinde ve aynı zamanda Tedarik Zincirinin parçası olarak Lojistikte yer alan ana karar alanlarından olan taşıma ile doğrudan ilişkilidir. Gerçek dünya uygulamalarında birçok değişik kısıtlar ve farklılıklar Araç Rotalama Problemlerinde çeşitliliği de beraberinde getirmiş, literatürde ve uygulamalarda farklı özellik ve kısıtlara sahip Araç Rotalama Problemlerinin incelenmesine yol açmıştır.
Araç Rotalama Problemi, en az maliyetle verilen belirli sayıda noktayı dolaşmayı sağlamayı hedefleyen bir kombinasyonel eniyileme problemidir. Çözümü için birçok alanda kullanılmakta olan çok sayıda sezgisel algoritma geliştirilmiştir. Sezgisel algoritmaların geliştirilmesinin nedeni Araç Rotalama probleminin NP-hard (herhangi bir algoritmayla optimal sonuca ulaşılamayan problem) olmasından kaynaklanmaktadır. Rota Planlamayı polinom zamanda optimize etmek güçtür ve sezgisel algoritmalar yardımıyla optimum yakın sonuçlar bulunabilmektedir.
Aslında Rota Planlama probleminin optimum sonucunu bulmak teorik olarak mümkündür. Fakat problem kombinasyonel olduğu için talep noktalarının 15-20’yi geçmesi durumunda optimuma ulaşmak mevcut teknoloji ile zorlaşmaktadır.
Araç Rotalama Problemleri şirketlerin ihtiyaçlarına göre farklılık göstermektedir. En büyük farklılık, problemin Açık ve Kapalı uçlu olmasıdır. Yani yollanan aracın tekrar merkeze geri dönmesi ya da dönmemesidir. Diğer bir farklılık, Geri Toplaması olan Rotalama Problemidir. Literatürde Milk Run olarak geçer. Milk Run, dağıtımla birlikte aynı zamanda aynı yerden toplama yapılmasıdır.
Bunun dışında, Araçların farklı kapasitelere sahip olması, birden fazla merkez deponun bulunması, aynı mağaza/müşteriye birden fazla aracın gitmesi, talebin belirsiz olması (marketler) gibi durumlar da söz konusudur.
Bir Araç Rotalama Probleminde çeşitli amaç fonksiyonları olabilir?
Minimum Kilometre : Araçların en kısa mesafeyi kat ederek ürün ya da hizmeti müşteri/mağazaya ulaştırmasıdır.
Minimum Zaman : En kısa mesafeye çok benzerdir. Çoğu durumda en kısa mesafeyle aynı sonucu verir. Fakat mikro dağıtım yapılıyorsa bu değişkenlik gösterebilir.
Minimum CO2 emisyonu: Minimum kilometreye çok benzerdir. Kullanılan araçların hepsi aynı ise aynı sonucu verir. Araçlar değişiklik gösterirse farklılaşır.
Minimum Araç Sayısı : Araçların kapasitelerinin (hacim ya da ağırlık) en verimli şekilde kullanarak en az sayıda araç kullanılmasını sağlar. Genelde araç başına ücret verildiği ya da boş gitmenin cezası olduğu durumlarda kullanılır.
Rota Planlama probleminin temel bileşenleri aşağıdaki gibidir.
- Kaç kamyon kullanılmalı?
- Hangi mağazalara hangi kamyon atanmalı?
- Her kamyonun mağaza sıralaması nasıl olmalı?
Bir işletme ve bu işletmenin 40 mağazası olduğunu varsayalım. Bu mağazalara maksimum 7 araç kullanarak günlük sevkiyat yapıldığını ve araçların rota planlamasının optimizasyonla yapılmak istendiğini düşünelim.
Hangi mağazalara hangi kamyon atanmalı?
Bu işletmede ortalama her bir araç 5-6 mağazaya sevkiyat yapmaktadır. Eğer tüm araçlar 5 mağazaya sevkiyat dağıttığını düşünürsek her bir aracın hangi mağazaları içereceği 40’ın 5’li kombinasyonu şeklinde olacaktır.
Kombinasyon bir nesne grubu içerisinden sıra gözetmeksizin yapılan seçimlerdir. Nesne grubunun tekabül ettiği kümenin alt kümeleri olarak da tanımlanabilir. Çünkü alt kümelerde sıra önemli değildir.
Bir A kümesinin herhangi bir alt kümesine A kümesinin bir kombinasyonu denir. Mesela 52 iskambil kartı arasından seçilen dört kart, kartları seçme sırası önemli olmadığından bir kombinasyon problemidir. (Wikipedia)
Bizim problemimizdeki tüm ihtimaller C(40,5) şeklinde olacaktır.
Birkaç örnek yazacak olursak,
Bu yaptığımız hesaplamalar neden bir rotalama probleminin optimizasyon ile çözülmesinin çok zor olduğunu anlatmak içindir.
Kombinasyon her bir araç için 5 mağaza olması durumundaki tüm ihtimalleri verir. Bu aşamada klasik ARP’de olan kısıtları hatırlamakta fayda vardır.
Araç kapasiteleri : Her bir aracın bir kapasitesi vardır. Kapasiteyi en verimli kullanmak gerekir. Bazı durumlarda boş göndermeniz durumunda ceza ödemek zorunda kalırsınız.
Zaman kısıtları : Mağazaların, müşterilerin gönderdiğiniz ürün ya da hizmeti almak için zaman kısıtları mevcuttur. Örneğin bir AVM’de ise saat 10:00’dan önce ürünleri kabul etmek isteyecektir.
Yol kısıtları (Köprü Kısıtları) : Kullanılmayan yollar, saatlik kapalı yollar (Köprüler vs.), belli araçların giremeyeceği yollar gibi.
Araç kullanım süreleri: Aracın bir günde maksimum kaç saat kullanılabilecğeini gösterir.
Bu kısıtlara göre yukarıda hesapladığımız ihtimaller azalabilir. Örneğin; 3, 4, 7, 8, 9 nolu mağazaların demandlerinin toplamı bir kamyonun kapasitesinden büyük ise bu rut otomatik olarak elenir.
Her kamyonun mağaza sıralaması nasıl olmalı?
Elemlerin ardından elimizdeki ihtimaller sadece hangi kamyona hangi mağazaların konu olacağını vermektedir. Bu araç dolulukları ile ilgilidir. ARP’deki en önemli amaç fonksiyonlarından biri olan minumum kilometrenin sağlanması için her bir ihtimalin içindeki mağazaların sıralamalarının denenmesi gerekir.
Bu da Permütasyon anlamına gelmektedir.
Matematikte permütasyon, her sembolün sadece bir veya birkaç kez kullanıldığı sıralı bir dizidir.
1’den 10’a kadar olan doğal sayıları içeren n elemanlı kümede r = 4 olarak alınırsa permütasyonların sayısı {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} kümesinden sırayı da gözetmek suretiyle oluşturulabilecek dört değişik elemanlı kümelerin sayısını ifade eder. (Wikipdia)
Bizim yukarıda oluşturduğumuz her bir 40’ın 5’li kombinasyonların permütasyonlarını bulmalı ve bunların mesafelerini ölçmeli ve bunların da en düşük mesafeli olanlarını seçmeliyiz.
Örneğin yukarıda oluşturduğumuz kombinasyonlardan 1, 2, 3, 4, 5’in permütasyonlarını bulalım.
Sonuç olarak bu problemde 40 mağazanın 5’erli olarak araçlara yerleştirilmesi sonucundaki değişken sayısı;
Bu durumda bile problemin bir çözümü olabilir. Fakat aynı araca 5’ten fazla mağaza/müşteri konu olabilir. Aşağıda bir araca konu olan mağaza/müşteri sayısı bulunmaktadır. Rakamları gördükten sonra neden bu problemin optimizasyonla çözülemeyeceğini siz de anlayacaksınız.
Mağaza sayısı arttığı zaman problem çok daha zorlaşmakta ve karar değişken sayısı çözülemeyecek kadar artmaktadır.
Bu sebeple ARP probleminin çözümü için, literatürde optimizasyon yerine çeşitli heuristic (sezgisel) ve metaheuristic (ileri-sezgisel) yöntemler ortaya çıkmıştır. Bu yöntemler doğru uygulandığında optimuma çok yakın sonuçlar verebilmektedir.
Bir sonraki yazımızda bu yöntemleri ve LC Waikiki’nin Rota Planlama problemini nasıl çözdüğünü anlatmaya çalışacağım.