LOJİSTİK PLANLAMA VE MODELLEME Dersi Ayrıt Tabanlı Araç Rotalama Problemleri soru detayı:

PAYLAŞ:

SORU:

Ayrıt tabanlı rotalama problemleriyle karşılaşılan durumlara ne gibi örnekler verilebilir?


CEVAP:

• Bir postacının karşılaştığı posta dağıtma problemi, ayrıt tabanlı rotalama problemidir. Postacı sabah dağıtacağı postalarını çantasına alarak yola çıkar. Kentin içinde dağıtımı yaparken geçtiği bir sokakta, sokak boyunca dağıtılması gereken postaları sahiplerine ulaştırır. Dolayısıyla postacı için bir sokaktan geçmek oradaki bütün müşterilere hizmet vermek anlamına gelir. O hâlde postacının hangi sokaklardan geçeceğini önceden belirlemesi gerekir ki bu bir rotalama problemidir. Bir kargo firmasının kent içindeki müşterilerine kargolarını ulaştırması da aynı şeydir.

• Kentlerde sabah vakti bakkallara gazete, süt, su vb. gibi günlük kullanımı olan malzemeleri dağıtan araçların karşılaştığı problem de ayrıt tabanlı rotalamadır. Araç bir caddeden geçerken müşterisi olan bütün bakkallara uğrar. Bu nedenle toplamda en az yolu gidecek şekilde hangi sokaklardan geçmesi gerektiğini belirlemeye çalışır. 

• Belediyelerin karşılaştığı çöp toplama problemi başka bir ayrıt tabanlı rotalama problemidir. Burada dağıtım değil toplama söz konusudur. Kent içinde her bir ev ortalama olarak belli miktarda çöp üretmektedir. Üretilen çöp miktarları mahallelerin karakterlerine göre ve nüfus yoğunluğuna bağlı olarak değişir ama kısa bir gözlemden sonra her bir sokakta ne kadar çöp birikeceği belirlenebilmektedir. Belediyeye ait çöp toplama araçları her gün şehrin sokaklarında çöpleri toplar ve çöp değerlendirme ya da imha merkezine götürür. Çöp toplama araçlarının taşıma kapasiteleri vardır ve bir sokaktan geçildiği zaman o sokaktaki bütün çöpler toplanır. Bu durumda bütün araçlar için toplamda en az yolu kat edecek ve araç kapasitelerini aşmayacak şekilde çöplerin toplanmasını sağlayacak araç rotalarının belirlenmesi gerekir. 

• Çok yoğun kar bir yağışından sonra yolların tekrar trafiğe açılması için yapılacak çalışma da ayrıt tabanlı rotalamaya girer. Kar temizleyen araçlarla açılması istenen bütün caddelerin ve sokakların temizlenmesi gerekir. Üstelik bu problemde bazı caddelerin trafik akışı nedeniyle önceliği vardır. Bu durumda caddeleri kardan temizlemek için eldeki kar temizleme araçlarının nasıl bir rota izlemesi gerektiğinin belirlenmesi gerekir. 

• Büyük bir alandaki çimlerin biçilmesi, ürün hasadının yapılması, geniş bir alanın temizlenmesi veya evin içindeki dağınıklığın toplanması gibi işler de ayrıt tabanlı rotalama sınıfına girer. Bu tip problemlerde öncelikle söz konusu alanın nasıl bir serim yapısı şeklinde tanımlanması gerektiğine karar vermek gerekir. Ondan sonra da problemin çözümü araştırılır. Bu aşamada, diğer ayrıt tabanlı rotalama problemlerinden farklı olarak küme kapsama veya en küçük örten ağaç (minimal spanning tree problem) gibi teknikler de kullanılmaktadır. 

• İlginç bir diğer uygulama da keşif robotlarının durumudur. Bunlar karada veya havada giden araçlar olabilir. Bir sahanın haritası çıkarılmak istendiğinde veya o saha gözlenmek istendiğinde oraya farklı yetenekte ve farklı sayıda keşif robotlarının gönderilmesi mümkündür. Haritası çıkarılacak sahanın sınırları biliniyor olabilir ya da uzayda olduğu gibi sınırlar bilinmiyor olabilir. Bu durumda robotların kendi enerji kapasitelerini doğru kullanarak (Yolda kalmayıp geri dönecek şekilde) alanın bir kısmına gidip haritayı çıkarması ve sonra başarıyla geri dönmesi gerekir. Bu durumda hangi robotun nasıl bir rota izlemesi gerektiğinin belirlenmesi, kapasiteli ayrıt rotalama problemi olur. Gelecekte uzayın haritalandırılmasında, deprem gibi bir afet sonrası oluşan yıkıntılar arasında canlı aranmasında, savaş anında bir cephenin gözlenmesi ve değişikliklerin raporlanması gibi konularda ve daha basit olarak, bir ortamın temizlenmesi gibi işlerde robotların kullanılması planlanmaktadır. Ve onlar için de rotaların, hem de duruma göre yeniden belirlenebilecek şekilde dinamik rotaların, oluşturulması gerekmektedir.