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

Serim kuramıyla ilgili kavramlar nelerdir?

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

Düğüm tabanlı rotalama problemleri nelerdir?

Düğüm tabanlı rotalama problemi müşterilerin düğümlerde tanımlandığı ve bu nedenle araçların düğümlere uğramak zorunda olduğu rotalama problemleridir. Bu problemlere, ilk tanımlayan kişi olması nedeniyle, Hamilton türü problemler de denir. Gezgin sayısı, gezginlerin kapasite sınırının olup olmaması ve özel bazı koşulların olup olmamasına göre farklı problemler tanımlanmıştır. Ama temeldeki ayrım, problemdeki gezgin sayısı ve taşıma kapasitesinin olup olmamasıdır. Bu alandaki en temel problem, gezgin satıcı problemidir (Travelling Salesman Problem-TSP), sonra çoklu gezgin satıcı problemi (m-Travelling Salesman Problem-mTSP) ve kapasiteli araç rotalama problemi gelir. (Capacitated Vehicle Routing Problem-CVRP veya kısaca VRP).

Gezgin satıcı problemi nedir?

Bu problemde 1 tane gezgin (araç veya kişi) vardır ve gezginin kapasite sınırı yoktur. Serimde bir tane çıkış noktası vardır. Gezgin, merkezden çıkarak bütün düğümlere gitmek ve geri dönmek zorundadır. Örnek olarak şunlar verilebilir: Bir kontrolörün kontrol amacıyla uğraması gereken noktalar olsun. Bu kontrolör su ve elektrik sayaçlarını okuyan kişi, binaları kontrol etmek amacıyla dolaşan bir güvenlik memuru, şehir şehir gezerek ürünleri için satış anlaşması yapmaya çalışan bir pazarlamacı olabilir. Bu problemlerin ortak noktası gezginlerin belli bir merkezden çıkıp geri dönmeleri ve planlanan bütün noktalara uğrama zorunluluğudur. Toplamda enkısa yolu veya en az maliyetli yolu verecek turun bulunması istendiğinde bir gezgin satıcı problemi oluşur. Bu problemde genellikle tek çıkış noktası vardır ve kapalı bir tur elde edilir.

Çoklu gezgin satıcı problemi nedir?

m tane gezginin olduğu ve gezginler için kapasite sınırının olmadığı durumdur. Esasen gezgin satıcı probleminin gelişkin hâlidir. Aradaki fark müşterilere uğramak için 1 değil m tane gezgin satıcı olmasıdır. Ama burada önemli olan bir gezginin uğradığı yere bir diğerinin uğramamasıdır. Çünkü bir müşteriyi bir kere ziyaret etmek işin tamamlanması anlamına gelir ve yeterlidir. Bu nedenle gezginlerin turları birbirlerinden ayrık olmak zorundadır. Yani turlar kesişmez, herkes farklı bir tur yapar. Ama sonuçta bütün düğümlere mutlaka bir gezgin tarafından uğranmış olması gerekir. Burada da genellikle kapalı turlar elde edilir. 

Kapasiteli araç rotalama problemi nedir?

m tane gezginin ve gezginler için taşıma kapasitesi sınırının olduğu durumdur. Araçlarla yapılan ürün dağıtma veya toplama problemi bu gruba girer. Kısaca LTL-tipi taşımanın söz konusu olan bütün işletmelerde ve kargo şirketlerinde karşılaşılır. Genellikle filodaki araçların türdeş (homojen) olduğu varsayılarak kapasiteleri de aynı kabul edilir ama kapasiteler farklı da (heterojen) olabilir. Bu problemde hem bütün müşterilere sadece bir araç tarafından uğranır, hem araç turları birbiri ile kesişmez ve hem de araçların taşıma kapasitelerinin aşılmaması gerekir. Bu nedenle gezgin satıcı ve çoklu gezgin satıcı problemine göre çok daha zor bir problemdir. Üstelik serimde birden fazla çıkış noktası varsa açık turlar da söz konusu olabilir.

Topla-Dağıt Problemi (Pickup and Delivery Problem) nedir?

Kapasiteli araç rotalama probleminde sadece taşıma veya sadece toplama yapılması, çözüm açısından bir fark yaratmaz. Problem VRP olarak modellenip çözülebilir. Eğer müşteriler sadece ürün dağıtılacaklar ve sadece ürün toplanacaklar şeklinde 2 alt kümeye net olarak ayrılabiliyorsa, buna özel olarak geri taşımalı araç rotalama problemi (VRP with Backhauls) denir. Bu durumda problemin çözümü her iki küme için ayrı ayrı yapılır. Ama bir müşteri noktasında hem dağıtma hem toplama yapılıyorsa, problem topla- dağıt problemi olarak isimlendirilir ve çözümü oldukça zor bir problemdir. Hem taşıma hem toplamanın yapılmasına örnek olarak dolu kasanın bırakılıp boş kasanın alınması verilebilir. Bırakılan ve alınan kasaların boyutları aynı ise bir sorun çıkmaz ama genellikle bırakılan kasalarla alınan kasaların büyüklükleri birbirini tutmaz. O zaman araç kapasitesinin (ağırlık ve boyutlar olarak) aşılmaması için her indirme bindirme noktasında kontrol yapılması gerekir. Bu da özel bir çabayı gerektirir.

Topla-dağıt probleminde genel olarak karşılaşılabilir durumlar nelerdir?

• İlgili düğümde kasaları aynı olan ürünler için aynı anda hem dağıtma hem toplama işlemi yapılabilir. Bu durumda kasa boyutları aynı olduğundan boyut açısından sorun çıkmaz, dolu kasa bırakılıp yerine geriye boş kasa alındığı için araç taşıma kapasitesi de aşılmaz. Problem VRP gibi çözülebilir.

• İlgili düğümde farklı kasalı ürünler için aynı anda hem dağıtma hem toplama işlemi yapılabilir. Bu durumda kasa boyutları farklı olunca araca yeni konacak kasanın araçtaki boş kısma boyut açısından uyup uymadığının kontrol edilmesi gerekir. Geri alınan şey boş kasa değil de bir malzeme ise, malzemenin ağırlığının da kalan araç taşıma kapasitesini aşmaması gerekir. Dolayısıyla her indirme bindirme noktası için hem boyut, hem de ağırlık yönüyle araç kapasite değerlerinin aşılıp aşılmadığı kontrol edilmesi gerekir. Üstelik geri götürülecek kasaların üst üste konulabilirlik açısından da uygun olması gerekir. Taşıma güvenliği gereği bir kasa istenen başka bir kasanın üstüne konamayabilir. Ya da kasaların boyutları tutmadığı için üst üst konamayabilirler. Üst üste konulabilirliğin de kontrolü gerektiğinde problemin çözümü daha da zorlaşır. 

• Araç ürünleri dağıtarak gidip toplayarak dönebilir. Bu durum geri taşımalı araç rotalama olarak da modellenebilir. Her bir noktada boyut ve ağırlık kontrolü yapılmasına gerek olmaz ama gidiş ve dönüş rotalarının ayrı ayrı belirlenmesi gerekir. Bir aracın gidiş ve dönüş rotası aynı olabileceği gibi farklı da olabilir. 

• Taşımalar merkez ile düğümler arasında veya karşılıklı düğümler arasında olabilir. Bu durum problemi çok karmaşıklaştırır. Örneğin 10 farklı noktada konumlanmış olan toplam 100 ton malzemenin olduğunu varsayalım. Malzemeler bir araçla toplanacak olsunlar. Eğer hepsi merkeze taşınacaksa bu nispeten kolay bir araç rotalama (VRP) problemidir. Ama merkezdeki 100 ton yeni malzeme düğümlerdeki 100 ton eskimiş malzeme ile değiştirilecekse bu bir topla-dağıt problemi olur. Taşımalar sadece merkezle düğümler arasında yapılır. Öte yandan düğümlerdeki 100 ton malzeme karşılıklı yer değiştirecekse daha da karmaşık bir durum ortaya çıkar. Örneğin A noktasındaki 10 ton malzemeden 4 tonunun B’ye 6 tonunun C’ye gitmesi gerekiyor; B’de ki 20 ton malzemeden 10 tonunun A’ya, 10 tonunun da C’ye gitmesi gerekiyor olsun. Taşıma kapasitesi sınırlı araçlarla bütün bu karşılıklı taşımaların yapılmasını sağlamak oldukça karmaşık bir düğümler arası topla-dağıt problemini çözmeyi gerektirir.

Zaman Pencereli Araç Rotalama Problemi (VRP with Time Windows) nedir?

Araçların belli düğümlerde, önceden belirlenmiş zaman aralıkları içinde olması koşulu varsa ortaya çıkan problemdir. Zaman aralığı katı veya esnek tanımlanabilir. Katı zaman aralığı aracın mutlaka o zaman dilimi içinde ilgili yerde bulunmasını gerektirir. Bu aralık dar bir süreyi kapsar. Esnek zaman aralığı ise daha geniş bir zaman aralığı anlamına gelir. Servis araçlarının yaşadığı problem buna örnek olarak verilebilir. Okul servisi veya fabrika servisleri kullanıcıları belli duraklardan toplayarak merkeze (Okula veya fabrikaya vb.) taşır. Dönerken de kullanıcıları aynı duraklara dağıtır. Kullanıcıların önceden tanımlanmış zaman aralıkları içinde ilgili durakta olması gerekir. Aksi hâlde araçtan yararlanamaz. Bir başka örnek de İstanbul’daki Boğaziçi köprüleri için verilebilir. Köprülerden büyük tır şeklindeki araçların geçişleri belli zaman aralıklarıyla sınırlandırılmıştır ve bu genellikle gece 24’den sonrasıdır. Tehlikeli madde taşıyan araçlar için daha da sıkı koşullar getirilmiştir. Bu nedenle köprüleri kullanmak gerektiğinde aracın seyahat zamanının, köprü için verilmiş zaman aralıklarına uygun olması gerekir. Zaman pencereli araç rotalama problemi de çözümü oldukça zor bir problemdir. 

Kısmi Taşımalı Araç Rotalama Problemi (Split Delivery VRP) nedir?

Araç rotalama problemlerinde genellikle bir aracın müşteriye uğradığında, müşterinin tüm talebini bir defada karşıladığı kabul edilir. Ama aslında bu böyle olmak zorunda değildir. Bir müşterinin talebi birkaç farklı araçla da karşılanabilir. Bu durumda da müşteri talebinin en fazla kaç parçaya ve nasıl bölünebileceğinin önceden tasarlanmış olması gerekir. Müşteri taleplerinin tamamının bir defada karşılanmayıp bir kısmının karşılanması nedeniyle bu problem türüne kısmi taşımalı araç rotalama denir. Problemdeki amaç, toplamda kat edilen yolu enküçük yapacak şekilde hangi müşterilere hangi araçlarla hizmet verileceğinin belirlenmesidir.

Rassal Araç Rotalama Problemi (Stochastic VRP) nedir?

Rassal araç rotalama problemi 2 farklı şekilde ortaya çıkabilir. İlki müşteri taleplerinin rassal olmasıdır. Diğeri ise müşterilerin bulundukları yerlerin rassal olmasıdır. Örneğin haftanın son günü banka şubelerinde biriken paranın, zırhlı araçlarla toplanıp merkeze taşındığını düşünelim. Hafta sonu itibariyle hangi şubede ne kadar para birikmiş olacağı önceden kesin olarak bilinemeyebilir. Ama taşıma aracının kapasitesi sınırlıdır. Toplanacak para miktarının tam bilinemiyor olması müşteri talebinin rassal olduğu duruma bir örnektir. Diğer örnek ise tamircilerin veya evlere su dağıtan araçların yaşadığı problemdir. Su dağıtmak üzere kendisine bir rota belirleyerek yola çıkan araca, turu sırasında mesaj gelerek yakındaki bir noktaya uğraması ve oraya da su dağıtımı yapması istenebilir. Bu durumda araç için rotanın hemen güncellenmesi gerekir. Bu örnek müşteri yerlerinin (düğümlerin) önceden kesin olarak bilinmediği, rassal olduğu duruma bir örnek olarak verilebilir. Aslında problemde başka rassallıklar da olabilir. Örneğin bir tamirci için tamire gittiği müşteride işlem zamanı bir rassal değişkendir. Yani ne kadar süreceği önceden kesin bir değer olarak bilinemez. Önceki tamir sürelerine bakılarak bir ortalama değer türetilebilir. Benzer şekilde aracın seyahat zamanı da aslında bir rassal değişkendir. Seyahat süresi genellikle ortalama hız ve yolun uzunluğuna bağlı olarak hesaplanır. Fakat trafik yoğunluğu, hava şartlarının etkisi ve diğer beklenmedik durumlar nedeniyle seyahat sürelerinin de kesin olarak söylenmesi mümkün değildir. Rassal araç rotalama problemindeki rassal kelimesi olayların rastgele gerçekleştiği anlamında değil de bir olasılık dağılımına uygun olarak gerçekleştiği anlamına gelir. Olayların hangi olasılık dağılımına uygun dağıldığı belirlenebilirse güvenilir bir tahmin de yapılabilir. Örneğin banka şubelerinden para toplama işinde toplanacak para miktarı geçmiş verilerden yararlanılarak tahmin edilebilir. Benzer şekilde su dağıtıcısı için yeni görevler çıkması örneğinde de en az ve en fazla kaç yeni görev çıkabileceği önceden tahmin edilebilir. Planlama yaparken de bunlar dikkate alınır.  

Stok Rotalama Problemi (Inventory Routing Problem) nedir?

Stok rotalama problemi müşterilerin stok durumlarını inceleyerek daha onlar sipariş vermeden talep edecekleri ürünleri belirleyip, ürünleri gönderme olarak tanımlanır. Buna lojistikte satıcı kontrolünde stok izleme (Vendor managed inventory control) denmektedir. Özellikle tedarik zinciri yapılarında karşılaşılır. Örnek olarak petrol istasyonları verilebilir. Petrol istasyonlarında yakıt türlerine göre stok durumu ve ürünün tüketim hızı, ana şirket tarafından izlenerek, petrol istasyonunun ürünü bitmeden oraya ürün gönderiliyorsa, stok rotalama problemi söz konusu demektir.

Milk-run ve dial-a-ride problemleri nelerdir?

Milk-run belirlenmiş bir rotada aracın sürekli olarak taşıma veya toplama yapması olarak tanımlanabilir. Ancak burada uğranılan düğümler için tanımlanmış zaman aralıkları da vardır. Yani araç belli zaman aralıklarına uyarak, standartlaştırılmış bir rotada genellikle toplama yapar. Örneğin tam zamanında üretim (Just in time) felsefesine göre çalışan bir firma stok tutmamak için üretimde gerekli ham madde ve malzemelerin tedarikçilerden tam zamanında toplanarak fabrikaya getirilmesini ister. Araçlar için belli rotalar, belli zaman aralıkları belirlendiğinde tedarikçilerden sürekli olarak malzeme alıp getirmeleri bir milk-run problemidir. Yalnız burada tedarikçiden alınacak ürünün miktarı, kasa şekli vb. bilgiler de önceden standartlaştırılmıştır. Araç tanımlı miktardaki ürünü, tanımlı yerden, tanımlı bir rotayı izleyerek ve belli zaman aralıklarına uyarak toplayıp getirir. Fabrika içindeki iş istasyonlarına malzeme götüren otomatik yönlendirilmiş araçlar da (OYA) aslında bir milk-run turu yapar. Bu problemde amaç, sürekli olarak kullanılacak standart rotaları belirlemektir. Dial-a ride problemi ise “çağrıları yönet” şeklinde çevrilebilir. Bu problem fiziksel özürlü veya yaşlı kişiler için kapıdan kapıya taşıma problemi olarak tanımlanabilir. Ayrıca düşük nüfus yoğunluğu olan yerleşim yerlerinde toplu taşıma sistemi olarak da tasarlanabilmektedir. Temeldeki düşünce talep eden kişinin çağrı göndermesi ve taşıma hizmetini almasıdır. Ama bu hizmeti veren şirket açısından çağrıların hemen karşılanmasının yanı sıra araçlar için de uygun turların belirlenmesi gerekir. Bir yönüyle düğümler arasında karşılıklı taşımanın olduğu topla-dağıt problemi olarak da düşünülebilir.

Düğüm tabanlı rotalama problemlerinin çözümünü zorlaştıran diğer etkenler nelerdir?

Düğüm tabanlı rotalama problemlerinin çözümünü zorlaştıran başka etkenler de vardır. Örneğin araç filosunun türdeş (homojen) olmaması, serimin yönlü (asimetrik) ve tam bağlı olması, problemdeki parametrelerin kesin (deterministic) olmayıp rassal (stochastic) olması, araçların birden fazla çıkış ve dönüş noktasının olması, turların açık veya kapalı olması çözüm sürecini çok etkiler, eniyi çözümün elde edilmesini zorlaştırır.

En yakın komşu sezgiseli nedir?

Gezgin satıcı problemi için geliştirilmiş en basit sezgisel algoritmalardan biridir. Çok kısa sürede çözüm bulur. Öte yandan seçilecek başlangıç noktasına göre farklı sonuçlar üretebilir. Bu nedenle serimdeki her bir düğüm algoritmadaki başlangıç nokta alınarak algoritmanın peş peşe n defa çalıştırılması ve elde edilen en küçük amaç fonksiyonlu çözümün seçilmesi önerilir. Çözüm süresi çok kısa olduğu için algoritmanın n defa çalıştırılması sorun yaratmaz. 

Gezgin Satıcı Problemi İçin En Yakın Komşuluk Algoritması adımları nelerdir?

• 1. Adım: Rassal olarak bir başlangıç noktası seç. 

• 2. Adım: Seçilen düğümden gidilebilir ve henüz uğranmamış diğer düğümler arasından enkısa mesafeli olanı belirle. İlgili düğüme git ve o düğümü seçilen düğüm olarak işaretle. 

• 3. Adım: Bütün düğümlere uğrandı mı? Cevap evet ise dur hayır ise 2. adıma dön.

Bu algoritmanın seyrek bir serim üzerinde uygulanması hâlinde bir aşamadan sonra gidilecek yol bulunamayıp algoritmanın tıkanması söz konusu olabilir. Oysa tam bağlı serimde böyle bir sorun olmaz. Bu nedenle eğer seyrek serim üzerinde gezgin satıcı turu araştırılacaksa, öncelikle serimin tam bağlı serim tipine çevrilmesi gerekir. Seyrek serim, bütün düğümler arasındaki enkısa yollar belirlenerek tam bağlı serim hâline çevrilebilir. Bunun için bir enkısa yol bulma algoritmasının kullanılması gerekir. Serimin yönlü veya yönsüz olması en yakın komşuluk sezgiselini etkilemez ama enkısa yolları bulmada önemlidir. Küçük boyutlu bir problemde enkısa yollar elle de hesaplanabilir.

En yakın komşuluk sezgiseli araç rotalama problemine nasıl uygulanabilir?

Bunu cevaplamak için taleplerin bölünmesine izin verilip verilmediğinin ve eğer bölünebiliryorsa talebin en çok kaç defada karşılanmasına izin verilebileceğinin belirlenmesi gerekir. Eğer taleplerin bölünmesine izin verilmiyorsa, algoritmanın 2. adımında seçilecek ayrıt belirlenirken gidilecek düğümü talebinin aracın kalan kapasitesine sığıp sığmadığı kontrol edilir. Sığıyorsa ilgili düğüme geçiş yapılır ama sığmıyorsa ikinci enkısa yol seçilerek oradaki talep değerinin kalan araç kapasitesine sığıp sığmadığı kontrol edilir. Kalan hiçbir düğüm için talep değeri araca sığmıyorsa araç bulunduğu noktadan merkeze geri gönderilir. Karşılanan taleplere dair düğümler serimden çıkarılarak kalan matriste yeni bir araç için algoritma bir kez daha çalıştırılır. Taleplerin bölünmesine izin veriliyorsa ilgili düğümün talebi kalan araç kapasitesi kadar karşılanır ve araç merkeze yönlendirilir.

Araç Rotalama Problemi İçin En Yakın Komşuluk Algoritması (Talepler Bölünemez Kabulü Varken) adımları nelerdir?

• 0. Adım:Eldeki serim seyrek ise düğümler arası karşılıklı enkısa yolları bularak serimi tam bağlı hâle çevir. 

• 1. Adım: Merkez düğümü başlangıç noktası olarak seç. 

• 2. Adım: Seçilen düğümden gidilebilir ve henüz uğranmamış diğer düğümler arasından enkısa mesafeli olanı belirle. Gidilecek düğümün talebi aracın boş kalan kapasitesini aşmıyorsa ilgili düğüme git, o düğümü seçilen düğüm olarak işaretle ve 3. adıma geç. Gidilecek düğümün talebi kalan kapasiteyi aşıyorsa ikinci enkısa mesafeli yolu, o da olmuyorsa sırayla diğerlerini dene. Hiçbirinin talebi kalan kapasiteye sığmıyorsa bu araç daha fazla yüklenemez. Aracı o düğümden merkeze geri gönder ve 4. adıma geç. 

• 3. Adım: Bütün düğümlere uğrandı mı? Cevap evet ise dur, hayır ise 2. adıma dön. 

• 4. Adım: Talebi karşılanan düğümleri serimden çıkar, kalan düğümler için yeni bir araç hazırla, merkez düğümü başlangıç düğüm olarak seç ve 2. adıma git. 

Bu algoritma ile araç kapasiteleri aşılmadan ve araç rotaları da kesişmeyecek şekilde turlar belirlenir. Özel bir durum olarak taleplerin kısmi karşılanmasına izin verilirse algoritmada düzeltme yapılarak aynı mantığın kullanılması mümkündür.

Kazanım algoritması nedir?

Kazanım (Savings) algoritması Clarke ve Wright tarafından geliştirilmiş, kullanışlı ve etkin bir tur iyileştirme algoritmasıdır. Türkçede tasarruf algoritması adıyla da bilinmektedir. Tur iyileştirmeden kastedilen, algoritmanın her adımda eldeki turu iyileştirmesidir. Bu algoritma yönlü, yönsüz ve karma serimler üzerinde çalışabilir. Seyrek matrisin tam bağlı biçime çevrilmesine gerek yoktur. Kazanım algoritmasının gezgin satıcı probleminde eniyi çözümün en çok % 6 kadar uzağında çözüm bulabildiği de ispatlanmıştır. Algoritmadaki temel mantık, başlangıçta merkez düğümden her bir düğüme git gel şeklinde tanımlanmış, ama uygun olmayan turları, her adımda iyileştirerek istenen özelliklere sahip bir tura dönüştürmektir. Bunun için hangi düğümlerin tur oluşturacak şekilde bağlanabildiği ve bu bağlantıyla amaç fonksiyonu değerinde ne kadar kazanç elde edilebildiği incelenir. Enbüyük kazanç hangisindeyse o düğümlerin tura bağlanmasına karar verilir.

Gezgin Satıcı Problemi İçin Kazanım Algoritmasının adımları nelerdir?

• 1. Adım: 1. düğümden bütün diğer düğümlere git-gel şeklinde tanımlanabilecek ve T={1,i,1}şeklinde gösterilebilecek olan uygun olmayan ilk turları türet. (Başlangıçta n-1 tane tur türetilmiş olacaktır). Toplam amaç fonksiyonunu hesapla. 

• 2. Adım: sij değerlerini hesapla. Sij = c1j + ci1 - cij i ? j ? 1 

• 3. Adım: Olabilir bağlantılar arasından enbüyük sij değerine karşı gelen (i,j) ayrıtını seçerek turu T={1-i-j-1} şekline dönüştür. Amaç fonksiyonu değerini güncelle. 

4. Adım: Var olan tur için 1 ile i arasına ve j ile 1 arasına girebilecek (Turun başına ve sonuna eklenebilecek) ama henüz turda olmayan alternatif düğümleri belirleyerek bunlara karşı gelen kazanım değerleri arasından enbüyük olanı seç. Uygun bağlantıyı yap. Turu ve amaç fonksiyonu değerini güncelle. 

• 5. Adım: Bütün düğümler tura eklendi mi? Cevap evet ise dur, hayır ise 4. adımı tekrar et.

Araç Rotalama Problemi İçin Kazanım Algoritması (Talepler Bölünemez Kabulü Varken) adımları nelerdir?

• 1. Adım: 1. düğümden bütün diğer düğümlere git-gel şeklinde tanımlanabilecek ve T={1,i,1}şeklinde gösterilebilecek olan uygun olmayan ilk turları türet. (Başlangıçta n-1 tane tur türetilmiş olacaktır). Amaç fonksiyonu değerini hesapla. 

• 2. Adım: sij değerlerini hesapla. 

• 3. Adım: Olabilir bağlantılar arasından enbüyük sij değerine karşı gelen (i,j) ayrıtını seçerek turu T={1-i-j-1} şekline dönüştür. Amaç fonksiyonu değerini güncelle. 

• 4. Adım: Var olan tur için 1 ile i arasına ve j ile 1 arasına girebilecek (Turun başına ve sonuna eklenebilecek) henüz tura eklenmemiş alternatif düğümleri belirleyerek, bunlara karşı gelen kazanım değerleri arasından enbüyük olanı seç. Yeni eklenecek düğümün talebi, elde kalan kapasiteyi aşmıyorsa uygun bağlantıyı yap. Turu ve amaç fonksiyonu değerini güncelle. 5. adıma geç. Eklenecek yeni düğümün talebi elde kalan kapasiteyi aşıyorsa, bir sonraki enbüyük kazanım değerli durumu incele. O da olmuyorsa sırayla hepsine bak. Hiçbiri uymuyorsa aracı daha fazla doldurmak mümkün değildir. Aracı merkeze gönder ve 6. adıma geç. 

• 5. Adım: Bütün düğümlerin talebi karşılandı mı? Cevap evet ise dur, hayır ise 4. adımı tekrar et. 

• 6. Adım: Talebi karşılanan düğümleri serimden çıkararak serimi güncelle, yeni bir araç için 1. adımdan başlayarak algoritmayı uygula. 

Kazanım algoritması ile araç kapasiteleri aşılmadan ve araç rotaları da kesişmeyecek şekilde turlar belirlenir. Özel bir durum olarak taleplerin kısmi karşılanmasına izin verilirse, algoritmada düzeltme yapılarak ve müşteri talebinin en fazla kaç parçada karşılanmasına izin verilebileceği belirlenip aynı mantığın kullanılması mümkündür.