Tedarik Zinciri Eğitimleri 20 – Rota Optimizasyonu 3 – Gezmeyi Seven Satıcı Yola Devam Ediyor

Rota optimizasyonu konusunu anlatabilmek için bir sene beklemek zorunda kaldım. Bu konu için uygun alt yapıyı hazırladığımı düşündüğüm an seriyi sizlerle birlikte incelemeye de sonunda başlamıştık. Ben rota optimizasyonu konusuna güzel bir giriş yaptığımızı düşünüyorum. Daha sonra şahsi görüşüm olarak söyleyebilirim ki rota optimizasyonuna temel oluşturan gezgin satıcı konusuna giriş yapıp konuyu en tatlı yerinde kesmiştik. Çok sevdiğim bu gezgin satıcı konusunu öyle tek bir yazıya sığdırmak hoşuma gitmedi. Anlatmak, üstünde durmak istediğim çok noktanın olduğunu düşünüyorum. Molayı bitiren ve dinlenen gezmeyi çok seven bu satıcı ve bizler için macera devam ediyor. Konunun ilk yazısına aşağıda ki linkten ulaşabilirsiniz. Hazırsak şimdiden herkese keyifli geziler.

Tedarik Zinciri Eğitimleri 19 – Rota Optimizasyonu 2 – Gezmeyi Seven Satıcı Yola Çıkıyor

Gezgin satıcı problemlerinin çözüm yaklaşımlarına geçmeden önce kullanım alanlarından bahsetmek istiyorum. İsim ve altında yatan mentaliteye göre bir dağıtım problemi gibi dursa da çok fazla sektörde çok farklı konularda çok farklı sorunlara ilaç olmaktadır. Lojistik firmalarından depolara, elektronikten robot sanayine kadar birbirinden bağımsız ve alakasız sektörlerin içerisinde gezgin satıcı problemi mantığı ile kurgulanmış çok fazla problem çözümü bulabiliriz. Lojistik firmalarından bahsetmeye gerek yok sanırım. Filolarını planlarken algoritmalarının temelini gezmeyi seven garip amcamızdan alıyorlar. Bildiğimiz Turkcell, Vodafone, Türk Telekom baz istasyonu yerleşimi problemine çözüm olarak gezgin satıcı mantığını kullanıyor. Bunların dışında uzmanlık alanım olan depo yönetiminde toplama algoritmalarının içerisine epeyce yerleşmiş durumdadır. Üretim hatları da nasibini almış durumda. Malzeme akış şemalarını oluştururken optimumu yakalamak için çok rahatça gezgin satıcıyı kullanabiliriz. Ekibinizi planlarken, elektronik devre tasarlarken, bilgisayar ağınızın kablolarını tasarlarken, stok alanından malzeme toplama planını yaparken ve projenizi bile planlarken gezgin satıcı mantığı ile hareket edebiliriz. Hatta robotların yapacakları hareketleri bile planlarken algoritmaların temeli gezgin satıcı mantığına dayanıyor. Çok geniş bir hareket alanından bahsediyoruz burada ve nerelere dokunduğunu ne kadar önemli olduğunu görebiliriz.

Gezgin satıcı probleminin çözümüne giden yolu keşfedebilmek için öncelikle Hamilton Turunu bilmemiz gerekiyor. Kısaca bu turdan bahsetmek istiyorum.

Hamilton turu aslında gezgin satıcı probleminin özelleştirilmiş halidir. Bu problem mantığında başlangıç noktasından hareket eden bir satıcının her düğüme en fazla bir kez gitmesi kaydıyla tüm düğümlerden geçmesini barındırır. Dediğimiz gibi gezgin satıcı problemlerinin özelleştirilmiş bir halidir Hamilton Amca’nın turu.

Hamilton Amca’yı yanımıza aldığımıza göre çözümlerden bahsetmeye başlayabiliriz. Tek bir metot ile bu konuyu çözeriz diyemiyorum. Birbirinden farklı çözümler söz konusu burada. Bu çözümlerin bazılarını ayrı bir yazı başlığında inceleyeceğiz. Kendimi burada tekrar etme ihtiyacı hissettim. Dediğim gibi ders anlatır gibi konuyu geçmek istemiyorum. Amacım altında yatan mantığa ulaşabilmektir tamamen. Bu yüzden çözümlerde problem çözmeyeceğim. Mantığına yakınlaşmaya çalışacağım.

Gezgin satıcı çözüm yöntemlerini iki başlık altında inceleyebiliriz. Kesin ve sezgisel çözüm olarak ikiye ayıracağımız başlıklardan sezgisel kısmının alt kırılımlarını da inceleyeceğiz. Biraz önce dediğim gibi sezgisel yöntemlerin bazılarını tek bir yazı da inceleyip yoluma devam edeceğim.

Kesin çözüm bildiğimiz tam sayılı lineer problem çözümleridir. Düğüm yöntemi gibi düşünebilirsiniz. Bir düğümden diğer düğüme hareket eden olguyu inceliyor. Bu problemlerin çözümü için bilinen yöneylem algoritmaları kurulur ve bilgisayar sizin yerinize kurgulanan algoritmanın çözümü ile uğraşırken siz de arkanıza yaslanıp çayınızı kahvenizi yudumlarsınız. Ancak hareket edilecek nokta sayısı fazla ise biraz fazla beklemek zorunda kalırsınız. Gerçi bilgisayar teknolojisi de hızlı büyüyor. Artık küçücük makinelerin içerisinde devasa işletim sistemleri, güçlü yapılar var. Bu çözüm süresini doğrudan etkileyecek bir durumdur. Lineer programlama, dinamik programlama yöntemleri bu başlık altına girmektedir. Meşhur bir yöntem ise “Branch & Bound” algoritmasıdır.

Sezgisel yöntemlere giriş yapmadan önce neden bu kadar çok sezgisel metot var ona değinmek istiyorum. Bilgisayar bilimleri ve matematik birazcık ilgi alanıma giriyor. Bilgisayarcı arkadaşlar problemleri kolay ve zor diye sınıflandırma ihtiyacı duymuşlar. Gezgin satıcı problemleri de algoritma mantığında zor problemler sınıfının ağır toplarındandır. Bu zor probleme kesin ancak yavaş ve yıpratıcı bir çözümle gitmek yerine sezgisel çözümlerle optimuma yakın veya belki de optimum çözümler bulmak daha sağlıklı olacaktır. Bu düşünce hareketi ile fazlasıyla sezgisel metotlar gelişmiş. Hadi bakalım şimdi neymiş genel hatları ile bu sezgisel metotlar.

Sezgisel metotları üç farklı başlık altında incelemek çok yanlış olmayacaktır. Tur oluşturanlar, tur geliştirenler ve bu iki yöntemi kullanan melezler olarak bir ayrım yapmak mümkündür. Tur oluşturan metotlarda bir sezgisel algoritmanız bir sonucu yakalarsa tüm işlemlerini durdurur ve daha iyi bir sonuç var mı diye arama yapmaz. Konuya giriş yaparken ne demiştik sezgisel yöntemler optimuma yakın bir sonuç bulur. Yani tur oluşturan yöntemin bulduğu sonucun daha iyisi olabilir ancak sistem kesinlikle bununla ilgilenmeyecektir. En bilindik yöntemi en yakın komşu yöntemidir. Greedy ve ekleme sezgiselini de bu başlık altında inceleyebiliriz.

Tur geliştiren sezgiseller ise bir sonuca varsa bile her zaman daha iyi olmak için çalışan arkadaşlardır. Sistemsel anlamda daha yıpratıcılardır ancak optimum sonuca her zaman daha çok yaklaşırlar. İlerleyen yazılarda bu başlık altına girecek arkadaşlarla bol bol ilgileneceğiz. En meşhur yöntemi karınca kolonisi yöntemidir. Lin-Kernighan, tabu araması, benzetim gibi yöntemleri de mevcuttur.

Ve geldik optimum sonuca yakın olmayı kafasına en çok takan arkadaşların grubuna. Burası biraz ölüm grubu gibi. Çok ağır teknik detaya sahip olduğu için fazlaca üstüne düşmeyeceğim. Mantık aramaya çıkmışken teknik detay bataklığında boğulmak istemiyorum. Ne ben bunu yazı vasıtasıyla anlatmak isterim ne sizi sıkmak isterim. Evet bu şahsına münhasır arkadaş melez yöntemlerin ta kendisidir. Yinelemeli Lin-Kernighan metodu en meşhur çözüm yollarından biridir bu arkadaşın. Genetik algoritmalarla fazlası ile uğraşmak zorunda kalırız eğer bu yöntem ile çözüme yürümeye kalkarsak. Size direkt olarak genetik algoritmanın vikipedi tanımını getiriyorum:

Genetik algoritmalar, doğada gözlemlenen evrimsel sürece benzer bir şekilde çalışan arama ve optimum yöntemidir. Karmaşık çok boyutlu arama uzayında en iyinin hayatta kalması ilkesine göre bütünsel en iyi çözümü arar.”

Tanımın içerisinde bile karmaşık, çok boyutlu, uzay gibi kavramlar var. Bu bile konunun ne kadar ağır bir konu olduğuna kanıttır. Ancak şunu söylemeden geçemeyeceğim. Son yılların en popüler konularındandır kendisi. Özellikle akademisyen bazında bakacaksak olaya baya baya araştırma alıyor kendileri son yıllarda.

Yukarıda bahsedilen metotların bazılara yazı bazında gireceğiz ve incelemeye devam edeceğiz. İlk yazı biraz mantığı çözmeye yönelik oldu. Bu asıl amacımızdı. Ancak ikinci yazıda amacımın dışına çıktım diyebilirim. Gezgin satıcının öneminden bahsederken ne kadar köklü bir konu olduğuna vurgu yapmaya çalıştım. Üzeriden binlerce araştırma yapılan onlarca çözüm yöntemi geliştirilen bir konu önemsiz olamaz. Gezgin satıcı turunu tamamladığına göre artık evine gidebilir. Bizlerde ilerleyen günlerde bu gezgin satıcıyı takip etmeye devam edeceğiz. Bakalım nerelere götürecek bizleri. Bilgiyle kalın!

Facebook Sayfamizdan Bizleri Takip Edebilirsiniz
Nevzad Ali Kılıç
2013 Kırıkkale Üniversitesi Endüstri Mühendisliği mezunuyum. Tedarik zinciri danışmanlığı, proje ve tedarik zinciri mühendisliği görevlerimin ardından şu an Flo Mağazacılık bünyesinde Lojistik ve Depo Yönetimi Süreç Geliştirme Uzmanı olarak görev almaktayım.