LOJİSTİK PLANLAMA VE MODELLEME Dersi Düğüm Tabanlı Araç Rotalama Problemleri soru detayı:

CEVAP:

İngilizcedeki network kelimesi Türkçe’de 3 farklı şekilde karşılanmaktadır: Şebeke, ağ ve serim. Örneğin bir şehre ait su boruları ve onların bağlantılarını gösteren bir haritaya su şebekesi denirken, internet bağlantılarını gösteren haritaya internet ağı denmektedir. Aslında İngilizcede ikisi için de network denmektedir. Özel olarak yöneylem araştırmasında geçen eniyileme problemlerini ifade etmek için kullanılan yapılara da serim denmektedir. Bunun dışında bir de graph kelimesi kullanılır ve Türkçede karşılık olarak çizge denmektedir. Temel olarak network ve graph aynı yapıyı temsil eder. Çoğu zaman da birbirlerinin yerine kullanılırlar. Bir serim, düğüm (node) ve ayrıtlardan (arc) oluşur. Bunlara köşe (vertex) ve kenar da (edge) denmektedir. Bir serimin büyüklüğü düğüm ve ayrıt sayısı ile ifade edilir. Düğümler ise yolları birbirine bağlayan kavşakları gösterebileceği gibi müşterilerin bulunduğu konumları da gösterebilir. Düğüm tabanlı rotalama probleminde düğümler genellikle müşterilerin olduğu kentleri, ayrıtlar ise bu kentleri birbirine bağlayan yolları ifade eder. Serimdeki bütün düğümler arasında doğrudan geçiş varsa buna tam bağlı (complete) serim denir. Ama bazı düğümler arasında doğrudan bağlantı var, diğerlerinde yoksa buna seyrek (sparse) serim denir. Bir serim ayrıtların yönlü olup olmamasına bağlı olarak farklı isimler alır. Yön, bir düğümden diğerine geçiş olduğunu ama tersinin olmadığı durumda kullanılır. Örneğin bazı yollar tek yönlüyse (Sadece gidiş var ama dönüş yoksa) bu durumda yönlü ayrıt kullanılması gerekir. Ama her iki yönde de geçiş varsa yönsüz ayrıt kullanılabilir. Yönsüz ayrıt her iki yönde de geçiş olduğunu ve mesafenin aynı olduğunu gösterir. Ama önemli olan mesafe değil de maliyet ise durum değişebilir. Bu durumda A’dan B’ye gitmenin maliyeti ile B’den A’ya gitmenin maliyeti aynı olmayabilir. Bunu ifade etmek için A ve B düğümleri arasında iki farklı ve yönlü ayrıt çizilir. Ayrıtların üzerine de maliyet değerleri yazılır. Aslında ayrıtların üzerine yazılan değerler ayrıt ağırlığı veya ayrıtın değeri olarak isimlendirilir ve genellikle de mesafeyi ya da maliyeti simgeler. Kısacası bir serimdeki ayrıtların yönü veya yönsüzlüğü önemlidir. Bunu ifade etmek için de serim farklı isimlerle anlatılır. Örneğin serimdeki bütün ayrıtlar yönlü ise yönlü serim (directed network), ayrıtların hepsi yönsüz ise yönsüz serim (undirected network) denir. Bazıları yönlü bazıları değilse karma serim (mixed network) denir. Şekil 5.1’de verilen serim yönsüz bir serimdir. Ama en az bir tane ayrıta yön konursa karma serim olur. Bütün ayrıtlarında yön olursa, yönlü serim adını alır. Bir serimin yönsüz olmasıyla yönlü ya da karma olması önemli bir fark doğurur. Yönsüz bir serimde iki düğüm arasındaki gidiş geliş mesafesi aynı olduğu için düğümler arasındaki uzaklıkları gösteren matris (Buna uzaklıklar matrisi denir) asal köşegen üzerinde simetrik olur. Dolayısıyla yönsüz bir serim, simetrik olarak ifade edilir. I ve J düğümleri göstermek üzere dij, (i,j) düğümleri arasındaki mesafeyi simgelesin. Simetrik matriste bütün i?j ikilileri için dij=dji olur. Öte yandan serim karma veya yönlüyse en az bir (i,j) ikilisi için dij?dji hâli oluşur. Yani uzaklıklar matrisi asimetrik olur. Asimetrik bir problemi çözmek daha zordur. Bir serim üzerinde yol (path) ve tur (tour) tanımlanabilir. İki düğüm arasındaki geçişi ifade eden ayrıtlar dizisine yol denir. Enkısa yol bulma algoritmalarında geçen yol kelimesi buradaki yol kelimesi aynı anlamdadır. Örneğin Şekil 5.4’de 1. düğümden 5. düğüme farklı yollarla gidilebilir. Bunlar: 1-2-4-5; 1-2-4-3-5; 1-2-3-5 ve 1-2-4-6-5 yollarıdır. Enkısa yol ise 7 birim ile 1-2-3-5 yoludur. Elbette ki birden fazla enkısa yol da olabilir. Öte yandan tanımlanmış iki düğüm arasındaki yola tur (tour) denir. Tur ise, kapalı (closed tour) ve açık (open tour) olmak üzere ikiye ayrılmaktadır. Eğer serimde bir düğümden başlanıp diğer bazı düğümlere uğradıktan sonra yine aynı noktaya dönülüyorsa buna kapalı tur denir. Bu durum genellikle tek bir çıkış (single depot) noktası tanımlandığında olan hâldir. Ama serimde aracın çıkış ve dönüş yapabileceği birden fazla düğüm varsa (multi depot) ve bir çıkış noktasından başlayıp diğer bazı düğümlere uğradıktan sonra farklı bir çıkış noktasına dönülebiliyorsa buna açık tur denmektedir. Örneğin Şekil 5.4’de 1 numaralı düğüm tek çıkış noktası olarak tanımlanmış olsun. Bu durumda örneğin 1-2-4-6-5-3-1 turu, bir kapalı turdur. Ama 1 ve 3; 2 farklı çıkış noktası olarak tanımlanmışsa 1-2-4-6-5-3 turu bir açık tur olacaktır. Açık turlu bir rotalama problemi biraz daha zor bir problemdir.