Müşteri taleplerini en kısa zaman, en kısa yol veya en az maliyet gibi amaçlardan birini veya birkaçını en iyileyecek şekilde karşılayan araç rotalarının belirlenmesi günümüz işletmelerinin üzerinde durduğu problemlerden birisidir. Kamyon gönderme problemi olarak VRP ilk 1959 yılında Dantzig ve Ramser tarafından tanıtıldı (Toth ve Vigo, 2002). Yazarlar, sorunun çözümü için ilk matematiksel programlama denklemini ve algoritmik yaklaşımını önerdi. Çeşitli kısıtlamaları verilen araçlar için güzergah optimizasyonu araç rotalama sorununun (VRP) kökenidir. VRP standart versiyonu olan kapasite kısıtlı VRP (CVRP) kolay ifade edilen ama çözümü zor olandır. CVRP, bütün müşterilere hizmet vermek üzere tek bir depodan filodaki homojen araçların bir dizi teslimat problemidir ve amaç tüm müşterilere hizmet edilmeli ve filo tarafından kat edilen toplam mesafe en aza indirilmelidir. Her araç kapasite ve maliyet olarak benzerdir ve araçlar bir depodan ayrılmalı ve o depoya dönmelidir. Her müşterinin bilinen bir talep miktarı vardır ve tek bir aracın tek bir ziyaretiyle bu talep karşılanır.
Resim 1: Bir VRP problemi çözümü gösterimi
VRP’de araç filosu homojendir. VRP varsayımına göre; bir müşteri talebi, bir aracın bir ziyareti ile tatmin edilmelidir. Diğer bir deyişle, araçlar arasında bir müşteriye teslimatı bölmeye izin verilmez. Ancak ayrılabilir teslimat dağıtım strateji dağıtım maliyetlerini düşürebilir. Bu nedenle, bölümlenmemiş teslimat stratejisi genişletilerek VRP içine bölünmüş teslimat dahil edilerek etkisi incelenmelidir. VRP’de bölünmüş teslimatlara izin verilirse problem bölünmüş teslimatlı VRP (SDVRP) olarak adlandırılır.
“Her müşteri sadece bir araç tarafından ziyaret edilmelidir” yaklaşımının genişletilmesi olarak SDVRP, CVRP’nin genişletilmiş halidir. Müşteri isteklerinin bölümlenmesine izin verilmektedir Bununla birlikte, bu kısıtlama serbest bırakıldığında, arama alanı daha büyük bir hale gelir. Bu durumda optimum çözümü bulmak veya etkin çözüme ulaşmak çok zor hale gelir.
Tavlama benzetimi stratejisi, doğal ısıl işlemde uygulanan, malzemenin belirli bir sıcaklığa kadar ısıtılması, bu ısıda bir süre tutulması ve son olarak da belirli tekniklerle soğutulması sayesinde, temelde 3 aşamada malzemeye daha kararlı bir yapı kazandırma prosesinden esinlenerek geliştirilmiştir. Bu aşamada soğutma işlemi, elde edilmek istenen malzeme özelliklerine bağlı olarak farklı hızlarla, farklı oranlarla ve değişik şekillerde uygulanabilmektedir. Bu prosesin sezgisel bir teknik olarak optimizasyon problemlerinin çözümü üzerindeki ilk uygulamaları 1983 yılında Kirkpatrick ve arkadaşları tarafından yapılmıştır (Kirkpatrick, 1983).
Bu çalışmada temel olarak CVRP’nin tavlama benzetimi yardımıyla çözümü anlatılacaktır. Bunun için Java dilinde geliştirilmiş bir program kullanılmıştır. Uygulama ileriki bölümlerde detaylı bir şekilde tanıtılacaktır. Uygulama ile literatürde ifade edilen klasik CVRP çözülmektedir. Eğer araç kapasitesini aşan müşteri istekleri olduğunda sadece bu teslimatlar bölünerek gerekli müşteri ihtiyacı karşılanmaya çalışılmaktadır. Bir başka deyişle ihtiyaç çeşitli servis araçları arasında bölümlenmektedir. Bu çalışmada bu probleme SDVRP’den farklı olarak servis bölümlemeli (split service) CVRP (CVRPSS) demeyi uygun buldum. Resim 2’de problemin çözüm şeması sunulmuştur.
Resim 2: Resim 2: Servis bölümleme şeması
Servisi bölümlemek için uygulama 2 yaklaşımı desteklemektedir. Birinci yaklaşımda aracın tam kapasitesiyle müşterinin ihtiyaçları karşılanmakta yani depodan ilgili düğüme tam dolu araçla rota oluşmakta, en sonunda araç kapasitesini aşmayan kalan miktar ihtiyacı karşılanmaktadır. İkinci yaklaşımda ise ihtiyaç, müşteri ihtiyaçlarını karşılayabilecek servis araçlarına göre eşit olarak dağıtılıp karşılanmaktadır. Bu durumda depoya dönmeden önce araç kapasitesini aşmamak kaydıyla başka müşterilere de uğranma durumu söz konusu olabilmektedir. Her iki yaklaşımda da problem klasik CVRP’ye dönüştürülüp o şekilde çözüm bulunmaya çalışılmaktadır.
Resim 3: Birinci yaklaşım ile servis bölümleme örneği
Resim 4: İkinci yaklaşım ile servis bölümleme örneği
