Lojistik Planlama Ve Modelleme Dersi 6. Ünite Sorularla Öğrenelim

Ayrıt tabanlı rotalama problemleri ve düğüm tabanlı rotalama problemlerinin farkları nelerdir?

Ayrıt tabanlı rotalama problemi dendiğinde kastedilen şey, gezginin veya aracın tanımlanmış serimdeki ayrıtları ziyaret etmesi zorunluluğunun olmasıdır. Her ayrıttan en az bir kere geçme zorunluluğu, problemi düğüm tabanlı rotalama problemlerinden tümüyle ayırır. İki problem türü sanki birbirlerine benziyormuş gibi görünse de bu, şekilsel bir benzerliktir. Yoksa hem problem yapısı açısından, hem de çözüm açısından aralarında ciddi farklar vardır. Ancak önceki bölümde açıklanan serim kuramıyla ilgili temel tanımların hepsi, bu problemler için de geçerlidir.

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

• 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.

Euler kimdir ve Euler turu ne anlama gelir?

Leonhard Euler 1707-1783 yılların yaşamış büyük bir matematikçi ve bilim insanıdır. Konuk profesör olarak gittiği ve şimdi Litvanya sınırları içinde kalan Königsberg kentinde hâlkın kendilerine Pazar günü eğlencesi olarak yaptığı “Her köprüden sadece bir kere geçme ve tekrar başladığı yere dönme” oyunu dikkatini çeker. Euler problemi çözmek için serim yapısını icat eder. Bu problem sonradan literatüre Königsberg köprüleri problemi olarak girmiştir ve serim kuramının başlangıcı sayılır. Her ayrıttan sadece bir kez geçerek yine başlangıç noktasına dönen tura, Euler turu denir. Bir serimde eğer Euler turu varsa toplamda gidilen yol, bütün ayrıt değerlerinin toplamı kadar olur. Ama her serimde Euler turu olmaz. Euler, bir serimde Euler turunun olup olmayacağını kolayca anlaşılması için bir yöntem önermiştir. Her bir düğüme bağlı ayrıt sayısı o düğümün derecesi olarak isimlendirilir. Euler bir serimde Euler turu olması için serimdeki bütün düğümlerin derecelerinin çift sayı olması gerektiğini ispatlamıştır. Aslında Euler turu zekâ sorularının olduğu dergilerde sorulan “Kaleminizi kaldırmadan ve başladığınız noktaya dönecek şekilde aşağıdaki şekli çizebilir misiniz?” şeklindeki soruların da cevabıdır.

Ayrıt tabanlı rotalama problemleri kaça ayrılır?

Ayrıt tabanlı rotalama problemleri de tıpkı düğüm tabanlı rotalama problemleri gibi özelliklerine göre faklı isimlerle anılırlar. En temel 3 problem, Çinli postacı problemi, çoklu Çinli postacı problemi ve kapasiteli ayrıt rotalama problemidir.

Çinli Postacı Problemi (Chinese Postman Problem-CPP) nedir?

1 gezginin olduğu ve gezgin için kapasite sınırının olmadığı durumdur. Gezgin ilgili ayrıtların hepsinden en az bir kez geçmek zorundadır. Tur devamlılığını sağlamak için zorunlu olarak bir ayrıttan birkaç defa geçilmesi söz konusu olabilir. İşte bu yüzden toplamda en az mesafeyi kat edecek şekilde fazladan geçilmesi gereken ayrıtların hangileri olması gerektiği belirlenmeye çalışılır. Yani bir Çinli postacı probleminin çözümü sonucunda bulunacak rotanın toplam uzunluğu en ez Euler turu kadar olmak zorundadır. Problemde gezginin yola çıktığı ve geri döneceği bir merkez düğüm tanımlansa da, çözüm sonrasında her ayrıt gezilmiş olacağı için merkezin neresi olduğunun da çok önemi yoktur. Bu problem, ilk defa bir Çinli bilim insanı tarafından tanımlandığı için Çinli postacı problemi adını almıştır. Gerçek hayattaki postacının turu buna iyi bir örnektir.

Çoklu Çinli Postacı Problemi (k-Chinese Postman Problem-kCPP) nedir?

k tane gezginin olduğu ve gezginler için kapasite sınırının olmadığı durumdur. Bu problem tıpkı çoklu gezgin satıcı problemi gibidir. Serimde k tane gezgin vardı ve her ayrıtın mutlaka bir gezgin tarafından ziyaret edilmesi gerekir. Amaç, toplamda en az mesafenin kat edilmesini sağlayacak şekilde gezginlerin rotalarını belirlemektir. Gezginlerin turları birbirleriyle kesişebilir. Aslında bu problem için Çinli postacı probleminin genel hâli de denebilir. Bir mahalledeki postaların çok sayıda postacı tarafından dağıtılması buna iyi bir örnek olur.

Kapasiteli Ayrıt Rotalama Problemi (Capacitated Arc Routing Problem-CARP) nedir?

k tane aracın ve araçların da kapasite sınırlarının olması hâlinde ortaya çıkan rotalama problemidir. Çözümü kolaylaştırmak için genellikle araçların türdeş olduğu varsayılır. Ama bu durumda bile problem çok karmaşıktır ve eniyi çözümünü bulmak kolay olmaz. Özellikle alt turların engellenmesine dönük olarak yazılan kısıtlar nedeniyle, 20 düğümlü küçük boyutlu problemlerde bile eniyi çözümün bulunamadığı durumlarla karşılaşılabilmektedir. Günümüzde çözülmesi en zor rotalama problemi olarak kabul edilmektedir. Öte yandan en sık karşılaşılan rotalama problemi olduğu da söylenebilir. Çöp veya özel amaçlı atıkların toplanması, bakkallara su ve gazete dağıtılması ve lojistik firmalarının şehir içi paket dağıtımlarını yapması gibi problemler hep bu gruba girer. Ortam temizleyen robotların da karşılaştığı problem kapasiteli ayrıt rotalama problemidir. Çünkü temizlik robotlarının hem temizlik kapasitesi hem de enerji kısıtı nedeniyle çalışma süresi kapasitesi vardır. Bir ortamın k tane temizlik robotu ile temizlenmesi hedeflendiğinde, bu kapasite kısıtlarına dikkat ederek robotların rotalarını belirlemek gerekir. 

Boş geçiş ve boş geçiş maliyeti nedir?

Aracın sadece tur devamlılığını sağlamak için gerekmediği hâlde bir ayrıttan fazladan geçmesine boş geçiş denir. Boş geçiş fazladan enerji kullanımına neden olacağı için istenmez. Örneğin ortam haritası çıkaracak bir robot için enerjisini harcamasına neden olan 2 unsur vardır. İlki hareketi sağlamak için gerekli enerji, ikincisi harita çıkarmak için kullanılan cihazların, sensörlerin harcadığı enerjidir. Robot harita çıkarılması istenen bir yerden geçerken bu enerjilerin her ikisini de harcar. Ama sadece tur devamlılığını sağlamak için zorunlu olarak geçtiği yerde sensörlerini kapatarak enerji tasarrufu sağlasa da hareket için enerji harcamak zorunda kalır. İşte gereksiz yere harcanan bu enerjiye boş geçiş maliyeti denir.

Kırsal Postacı Problemi (Rural Postman Problem-RPP) nedir?

Bu problem serimdeki bütün ayrıtlara uğrama zorunluluğunun olmadığı durumda ortaya çıkar. Varsayınız ki bir kargo şirketi olarak bütün şehir dağıtım bölgeniz içinde ama o gün dağıtılacak ürünlerin müşterileri sadece bazı yerlerde bulunuyor, diğer ayrıtlara uğramanız gerekmiyor. Bu durumda serimdeki bütün düğümlerden geçmenin bir gereği yoktur. Sadece ilgili olanlardan ve tur devamlılığının gerektirmesi nedeniyle diğer bazılarından geçmek yeterli olur. İşte bu gibi durumlarda ortaya çıkan probleme kırsal postacı problemi denmektedir. Geçilmesi zorunlu olan ayrıtlara gerekli ayrıtlar denir ve problem gerekli ayrıtlardan en az bir kere geçmeyi sağlayacak şekilde rotaların belirlenmesi şeklinde ifade edilir. Amerika ve Avustralya’nın kırsal bölgelerinde birbirlerinden uzakta konumlanmış çiftlikler olması ve her zaman hepsine gitmek gerekmemesi nedeniyle ortaya çıkan bu problem, kırsaldaki yerleşim yerlerinden esinlenildiği için bu şekilde isimlendirilmiştir.

Rüzgârlı Postacı Problemi (Windy Postman Problem-WPP) nedir?

Aslında yönsüz bir serim üzerinde tanımlanan bu problemde her bir (i-j) ayrıtı için 2 farklı maliyet değeri verilir. Fakat bu ayrıttan bir kere geçilmesi yeterli olur. 2 faklı maliyet değerinin olması şöyle açıklanır. Araç i’den j’ye giderken rüzgâra karşı, j’den i’ye doğru giderken de rüzgârı arkasına alarak hareket ediyorsa, ilkinde daha yüksek maliyetle diğerinde ise daha düşük maliyetle gitmesi söz konusudur. O zaman rotalama problemi şu hâle dönüşür. Toplamda en az seyahat maliyetinin verecek şekilde ve her ayrıttan en az bir kere geçilmesini sağlayacak şekilde araç rotaları nasıl olmalıdır? Problemin ismine bakılarak konunun sadece rüzgârlı havaları ilgilendirdiği düşünülmemelidir. Örneğin A kenti ovada, B kenti tepede konumlanmışsa, aracın A’dan B’ye gitmesiyle, B’den A’ya gitmesi maliyetleri yine farklı olacaktır. Hatta ikisi de aynı yükseklikte olan 2 kent için birinden diğerine gitme maliyeti kentin popülerliği veya trafik yoğunluğunun olması gibi nedenlerle daha pahalı olabilir. Sonuçta 2 kent arasında sadece bir geçiş yapılması yeterliyken 2 farklı maliyet söz konusu olursa rüzgârlı postacı problemi ortaya çıkar. 

Yönlü Postacı Problemi (Directed Postman Problem-DPP) nedir?

Serimdeki bütün ayrıtların yönlü olması hâlidir. Başlangıçta bu problem rüzgârlı postacı probleminin benzeri gibi düşünülebilir. Çünkü iki düğüm arasında farklı ağırlık değerlerine sahip 2 farklı ayrıt vardır. Ama aralarındaki önemli fark, yönlü postacı probleminde bütün ayrıtlardan en az bir kere geçme zorunluluğunun olmasıdır. Örneğin bakkallara malzeme dağıtan bir araç için bir caddeden bir kere geçmek bütün müşterilere uğramak anlamına gelemeyebilir. Çünkü yol gidiş geliş şeklinde ortadan ayrılmış biçimde olabilir. Bu durumda caddenin her iki tarafındaki müşterilere de uğrayabilmek için aynı caddeden hem A’dan B’ye hem de B’den A’ya doğru geçmek gerekir. İşte bu durumda yönlü postacı problemi var demektir.

Hiyerarşik Postacı Problemi (Hierarchial Postman Problem-HPP) nedir?

Ayrıtlar arasında öncelik olması hâlinde ortaya çıkan problemdir. Özellikle kar temizleme sırasında trafik akışı gereği bazı yolların öncelikli olması buna bir örnektir. Benzer şekilde de çöp toplama işinde bazı caddelerin önceliği ve hatta zaman aralığı olabilir. Buna benzer durumdaki ayrıt tabanlı rotalama problemine hiyerarşik postacı problemi denmektedir. Ayrıt rotalama problemlerinde Çinli postacı problemi şaşırtıcı şekilde P sınıfı bir problemdir. Yani problem boyutu büyüdükçe çözmek için gerekli süre, polinom değerli artmaktadır. Bu da günümüz bilgisayar teknolojisi ile Çinli postacı probleminin çok büyük boyutlarda olsa bile rahatlıkla çözülebileceği anlamına gelir. Ama ne yazık ki diğer postacı problemi türlerinin hepsi NP-zor sınıfındadır. Özellikle de kapasiteli ayrıt rotalama problemi günümüzde çözülmesi en zor rotalama problemi olarak kabul edilmektedir. Bilindiği gibi NP-zor yapıdaki problemleri için sezgisel algoritmalar kullanmak çok işe yaramaktadır.

Çinli Postacı Problemi(Cpp)'nin amaç fonksiyonu nedir?

Modelin amaç fonksiyonu (1), toplamdaki maliyetin veya kat edilecek yolun en küçükleneceğini ifade eder. Modelin ilk kısıtı olan (2) nolu ifade, her bir düğüme giriş ve çıkış sayısının eşit olması gerektiğini gösterir. Bir diğer ifade ile bu kısıt tur devamlılığını sağlar. (3) nolu ifade her bir ayrıttan en az bir kere geçilmesini garantiler. (4) nolu ifade ise değişkenlere dair işaret kısıtlarıdır. Bu modelde xij değişkenlerinin tamsayı değer alması gereken değişken olarak tanımlanmış olmasına dikkat ediniz. Bu model yönlü veya yönsüz bütün serimlerde uygulanabilir. Ama elbette bir çözümün bulunabilmesi için yönlü serimde her bir düğüme en az bir giriş ve bir çıkışın olması gerekir. Aksi hâlde zaten bir çözüm bulunamaz. Model seyrek ve tam bağlı serimde de kullanılabilir.

Hangi durumda postacı problemi çözmeye gerek kalmaz?

Verilen bir serimde Euler turu bulunabiliyorsa postacı problemini çözmeye gerek yoktur, tur zaten bellidir.

Kapasiteli Ayrıt Rotalama Problemi (CARP) modeli nasıldır?

Kapasiteli ayrıt rotalama probleminin modeli oldukça karmaşıktır. Özellikle alt turların engellenmesi konusu ayrı bir bahistir. Burada model genel olarak verilecek ve alt tur engelleme kısıtları açık olarak verilmeyecektir. Model çözüldükten sonra alt tur oluştuğu görülüyorsa onu engelleyecek ek kısıtların modele eklenerek yeniden çözülmesi önerilebilir. Bu problemde k tane araç ve araçlar için de kapasite sınırı vardır. 1 numaralı düğüm araçların çıkış yapıp dönecekleri merkezdir. Bu problemin diğer postacı problemlerinden önemli farkı her bir ayrıtın bir talep değerinin olmasıdır. Yani i. düğümden j. düğüme geçen bir araç için yol boyunca toplayacağı veya dağıtacağı miktar o ayrıtın talep değeri olarak isimlendirilir ve wij ile gösterilir.

Kapasiteli Ayrıt Rotalama Problemi (CARP) modelinin amaç fonksiyonu nasıldır?

Modelin amaç fonksiyonu (1), toplamdaki maliyetin veya kat edilecek yolun en küçükleneceğini ifade eder. (2) nolu ifade, her bir araç için her bir düğüme giriş ve çıkış sayısının eşit olması gerektiğini gösterir. Yani her bir araç için tur devamlılığı sağlanmış olur. (3) nolu ifade eğer hizmet verilmesi gerekli bir ayrıt varsa oradan en az 1 kere geçilmesini garanti eder ama tur devamlılığını sağlamak için boş geçiş yapılması gereken bir ayrıttan da en fazla 1 kere geçilmesine izin verir. (4) nolu ifade x ve y değişkenleri arasındaki ilişkiyi sağlar. Öyle ki eğer bir araç bir ayrıta hizmet veriyorsa oradan geçiş yaptığını garantiler, ama hizmet vermiyorsa oradan geçiş yapmayabilir. (5) nolu ifade her bir araç için araç kapasitesinin aşılmamasını garantiler. (6) nolu araç turlarının alt tur içermemesi gerektiğini söyler. Kısıt burada açık şekilde ifade edilmemiştir. Model çözülürken bu kısıt görmezden gelinerek çözüm aranır. Elde edilen çözümde alt tur yoksa sorun olmaz. Varsa o alt turu engelleyecek yeni bir kısıt yazılarak modelin yeniden çözülmesi gerekir. Ne yazık ki kapasiteli ayrıt rotalama problemi için, kapasiteli araç rotalama probleminde olduğu gibi etkin alt tur engelleme kısıtları henüz geliştirilememiştir. Son olarak (7) nolu ifade ise değişkenlere dair işaret kısıtlarıdır. x ve y karar değişkenlerinin sadece 0 veya 1 tamsayı değer alabileceğini gösterir. Bu model yönlü, yönsüz, seyrek veya tam bağlı serimde uygulanabilir. Ama elbette bir çözümün bulunabilmesi için yönlü serimde her bir düğüme en az bir giriş ve bir çıkışın olması gerekir.

Yönsüz Çinli Postacı Problem İçin Enküçük Kusursuz Eşleşme Algoritmasının birinci adımı nedir?

1. Adım: Serimdeki tek ve çift dereceli düğümleri belirle. Bütün düğüm dereceleri çift ise Euler turu vardır, devam etmeye gerek olmaz, dur. Tek dereceli düğümler varsa 2. adıma geç. 

Yönsüz Çinli Postacı Problem İçin Enküçük Kusursuz Eşleşme Algoritmasının ikinci adımı nedir?

2. Adım: Tek dereceli düğümleri listeleyerek bunların arasından hangilerinde git gel yapılabileceğini incele. Toplamda en az maliyet artışını verecek ayrıtları serime ekle.

Yönsüz Çinli Postacı Problem İçin Enküçük Kusursuz Eşleşme Algoritmasının üçüncü adımı nedir?

3. Adım: Serimin genişletilmiş hâli için Euler turunu belirle. Toplam maliyet, bütün ayrıtların maliyetleri ve 2. adımda serime yeni eklenen ayrıtların maliyetleri toplamıdır.

Ödünleşme nedir?

Ödünleşme, birbiriyle çelişen iki veya daha çok amaç varken, birini iyileştirmeye kalktığınızda diğerinden verdiğiniz ödünü ifade eder. Örneğin süre ve maliyet arasında daima bir ödünleşme vardır. Bir işi daha kısa sürede yapmak isterseniz daha çok kaynak kullanmanız gerekir, bu da maliyeti artırır. Maliyet artmasın isterseniz işin süresi uzar. Birini tercih ederken diğerinden ödün vermeniz gerekir.