Yeşil Kısıtlı Araç Rotalama Problemi Optimizasyonu | Genetik Algoritma-Tabu Arama

Bu slayt gösterisi için JavaScript gerekir.

Tüm projeyi indir: https://github.com/bulentsiyah/Yesil-Kisitli-Arac-Rotalama-Problemi-Optimizasyonu–Genetik-Algoritma-Tabu-Arama/

Problemin detayı: Günlük olarak yaklaşık 350 – 450 adet sipariş yaklaşık olarak 130-170 boşaltma noktasına teslimatlar yapılmaktadır. Teslimatlar 9 adet araçla ve teslimat siparişlerinin dağıtım saatleri ve iade siparişlerinin teslim alım saati 08:30 ile 17:30 arası olarak alınmıştır. Araçlar için ise bu dağıtım sürelerine uyum sağlayabilecek şekilde yaklaşık olarak 7:30 – 19:00 aralığına denk gelecek şekilde serbest bırakılmıştır. İade siparişlerinin sayısına göre aracın depoya dönüş saati 21:00’e kadar uzayabilir.
Araçların hızı harita servisinden gelen veriler kapsamında yaklaşık olarak ortalama 60km/s olarak alınmıştır.
Rota Optimizasyonu Kapsam Özeti
• Kapasite Kısıtları: Desi
• Zaman Pencereleri: Araçlar için çalışma saatleri; teslimat noktaları için teslimat saatleri
• Teslimat ve yükleme Sürelerine uyum.
• Depodan mal yükleme süreleri: Eğer aracın ara ara depoya dönmesi daha verimli olduğu durumlarda kullanılır.
• Aynı noktaya olan siparişlerin gruplanması ve aynı araçla yollanması.
• Siparişlerin sadece bazı araçlarla taşınabilmesi ya da taşınamaması durumları.
• Depodan çıkarak bütün malları teslim edilmesi ile depoya ara ara dönüşün mümkün olduğu modeller.

  1. GENETİK ALGORİTMA OPTİMİZASYONU:

Bu çalışmanın uygulama kısmında, çözülmek istenen problem için C#(sharp) (6.0) programlama dili kullanılmıştır. Geliştirme ortamı Visual Studio (2015) seçilmiştir ve uygulama bir form uygulamasıdır. Uygulamanın bir form olması sebebiyle ara yüz ve kod kısmı bulunmaktadır. Yazı içerisinde geçecek olan ara yüz ile kullanıcının uygulama ile ilgili parametre seçimi yaptığı, çözüm işlemlerine başlatabildiği ve sonuçları gözlemlendiği ekran kastedilmiş olacaktır. Yine yazı içerisinde geçecek olan GA ile Genetik Algoritma kastedilmiş olacaktır.
Adım 1. Genetik kodlamanın yapılması:
Çözümün ilk adımı kromozomların nasıl kodlanacağına karar vermektir. Kodlama yaklaşımı çözümün başarısına doğrudan etki eder ve problemin türüne ve özelliklerine göre farklılık gösterir. Permütasyon kodlama gezgin satıcı problemi ve iş sıralama problemleri gibi sıralama problemlerinde kullanılır. Bu yüzden problemimiz için bu çalışmada permütasyon kodlama seçilmiştir ve her varış noktası(firmalar) bir sayısal ifade ile belirtilmiştir.
Uygulama çalışmaya başladığı gibi probleme ait verileri okuyarak başlar. Verileri okuma işlemi için kaynak gerçek dünyada bu probleme ait bilgilerin bulunduğu bir excel belgesidir. Bu excel belgesi içerisindeki veriler kodlamayı kolaylaştırmak için txt belgelerine dönüştürülür. Bu belgede Lojistik firmasına ait her müşterinin n tane siparişleri ve bu siparişlere ait detay bilgilerdir. Bu belge form uygulamasının alt klasöründe bulunduğu için form uygulamasını çalıştırmak için herhangi bir gereklilik bulunmamaktadır. Uygulama excelde bu verileri sütunlarına göre ayıklayarak yazılım içerisinde kullanıla bilenecek Sınıflara(class) dönüştürülür.

Okumaya devam et “Yeşil Kısıtlı Araç Rotalama Problemi Optimizasyonu | Genetik Algoritma-Tabu Arama”

Genetik Algoritma ile Kitap Konteyneri Yerleştirme Problemi(Genetik Algoritma, C#)

Bu slayt gösterisi için JavaScript gerekir.

Proje de bir ilçenin mahalle/cadde bazında nufüs yoğunluğu olan nokta verileri mevcut. Bu ve diğer bilgilerle değişken sayıda kitap konteynerini, Genetik Algoritma ile en optimum şekilde yerleştirme işlemi yapılmaktadır. Örneğin bu proje de istanbul pendik ilçesi için 143 merkez nokta ve her noktaya ait yaklaşık nüfus miktarı belirlenmiş. Farklı kapasite ve özelliklere sahip yaklaşık 40 tane kütüphane konteynerı bu noktalaradan 40 tanesine en doğru nasıl yerleştirileceği Genetik Algoritma ile yapılmıştır.

Kaynak Kodları : https://github.com/bulentsiyah/Genetik-Algoritma-ile-Kitap-Konteyneri-Yerlestirme-Problemi–Genetik-Algoritma–C—

Tavlama Benzetimi ve Tabu Arama Algoritmaları ile Gezgin Satıcı Problemi (C#)

Bu slayt gösterisi için JavaScript gerekir.

Gezgin Satıcı Problemi

GSP, n adet şehir arasındaki mesafelerin bilindiği durumda, şehirlerin her birine yalnız bir kez uğramak şartıyla, başlangıç noktasına geri dönülmesi esasına dayalı, tur boyunca kat edilen toplam yolun en kısa olduğu şehir sıralamasının (optimal rota) bulunmasının amaçlandığı bir problemdir. Dağıtım, rotalama, kuruluş yeri belirleme, planlama, lojistik gibi problemlerde geniş bir uygulama alanına sahip olan gezgin satıcı problemi, aynı zamanda optimizasyon alanında, araştırmacılar tarafından üzerinde uzun yıllardır çalışmalar yapılan NP-hard (çözümü zor) sınıfında yer alan bir problemdir.

Tavlama Benzetimi Algoritması (TB)

TB algoritması, ilk olarak 1983 yılında Kirkpatrick, Gelatt ve Vecchi  tarafından sunulmuş olup, optimizasyon problemlerinin çözümü için geliştirilmiş bir yerel arama algoritmasıdır.

Okumaya devam et “Tavlama Benzetimi ve Tabu Arama Algoritmaları ile Gezgin Satıcı Problemi (C#)”

GENETİK ALGORİTMA İLE LOJİSTİK AĞ TASARIMI PROBLEMİ – GAMS İLE HİBRİT ÇÖZÜM (C#)

Model, tedarikçilerden satış toplama merkezine sıfır parça (komponent) ve sıfır ürün satışı yaparken, diğer taraftan satış toplama merkezleri aynı zamanda geri dönen ürünleri toplamakta ve bu ürünlerin belirlenen değer seviyelerine göre de tamir, komple demontaj ve atık seçeneklerine göndermektedir. Bu şekilde ileri ve tersine bir akış söz konusudur. Çalışmamdaki modelimi GAMS paket programında çözdürülebilmektedir(GAMS optimizasyon modellerini çözüme ulaştıran bir paket programdır) fakat problem GAMS te küçük boyutlu problemler için çözüme ulaşırken, tesis sayılarını arttırdığında çözümün  uzun süreler aldığını ve uzun sürelere rağmen optimal çözümler elde edilmemiştir. Bu problem NP hard problem sınıfında, Genetık algorıma ile yaklaşık kısa sürede yaklaşık çözümler elde etmek istenmiştir. Model yapısı çok basit olup, sadece tedarikçi, fabrika ve dağıtım merkezlerinin açma kapama kararlarını sezgisel algoritma karar verip, geri kalan cebirsel işlemleri GAMS paket programı ile çözmüştür. Yani tüm model komple genetik algoritma değilde Hibrit olarak çözülmüştür.

Kaynak kodları projeye özel olduğu için yayınlanmamıştır.

Genetik Algoritma ile Dağıtım Problemi-Araç Rotalama Problemi (Genetik Algoritma, C#)

Bu slayt gösterisi için JavaScript gerekir.

Projenin Kodları

Tüm projeyi İNDİR: Program Kodu

GİRİŞ

        21.yüzyılın dünyasında bilgisayarın daha etkin kullanılması ile birlikte özellikle büyük firmalar dağıtım ağ yapılarını yeniden düzenlemektedirler. Optimal dağıtım yöntemleri zaman, maliyet ve kalite açısından işletmelere rekabet avantajı kazandırmaktadır. Özellikle coğrafi açıdan ulaşımın zor olduğu bölgelere uygun dağıtım kanalının seçilmesi müşterileri ihtiyaçlarının zamanında temin edilmesini sağlar. Araç güzergahlarının belirlenmesi, taşıma yapacak araç tiplerinin seçimi, araç kapasitelerinin düzenlenmesi ve ürünlerin yerlerine ulaşımının takip edilmesi gerekmektedir. Böylelikle işletmeler rekabetçi ortamda rakipleri karşısında önemli pazar payı elde etmektedirler.

        Araç Rotalama Problemi (ARP),    “bir noktadan başlayarak farklı düğüm noktalarına (şehir, hedef, vs.),en kısa süre veya en düşük maliyetle en az sayıda araç ile uğranılmasını eniyileyen problem çeşitidir”(Pakkan vd. 2010:78). ARP ilk olarak Danzig ve Ramser tarafından 1959 yılında tanımlanmıştır.  Temelde depodan çıkan araç her bir müşteriye bir kez uğrar ve depoya tekrar döner.  Firma tarafından gönderilen araç sayısı ve gidilen müşteri sayısı az ise çözüme kesin çözüm algoritmaları ile kolaylıkla ulaşılabilir. Müşteri sayısı ve dağıtımı yapan araç sayısı arttıkça bilgisayar işlem süresi uzamaktadır. ARP çözümü zor olan problemler (NPL-Hard) için kesin çözüm algoritmaları yerine sezgisel ve metasezgisel yöntemler kullanılmaktadır(Çolak vd. 2009:171-173).

Okumaya devam et “Genetik Algoritma ile Dağıtım Problemi-Araç Rotalama Problemi (Genetik Algoritma, C#)”

Genetik Algoritma ile Maksimum Ağırlıklı Clique Problemi ( MWCP ) (Genetik Algoritma, C#)

Bu çalışmada ağırlıkları ve diğer Nodelerle ilişkileri verilmiş bir uzayda en yüksek ağırlığa sahip alt grafın bulunması amaçlanmıştır. Çalışma sonunda büyük bir arama uzayına rağmen doğru çaprazlama şekli ve oranı sayesinde çok kenarlı graflar bulunmuştur. Projede bu çalışma için en uygun olan Rulet tekeri çaprazlama modeli kullanılmıştır. Problemin Genetik Algortima ile çözümü için geliştirilen uygulama, c#(sharp) programlama dili ile yazılmıştır.

Projenin detayı: maksimum ağırlık projesi

Projenin Kodları

Tüm projeyi İNDİR: Program Kodu

Genetik Algoritma ile Çift Taraflı Montaj Hattı Dengeleme (Genetic Algorithms, C#)

Projenin Kodları

Tüm projeyi İNDİR: Program Rapor ve Kodu

1. GİRİŞ

Bu çalışmada, çift taraflı mondaj hattının her iki tarafı için belirlenmiş çevrim süresi içerisinde istasyon sayısını en aza indirgeme amaçlanmıştır. Operasyonlarda taraf ve istasyon sayısı kısıtları bulunmaktadır. Problemin Genetik Algortima ile çözümü için geliştirilen uygulama, c#(sharp) programlama dili ile yazılmıştır.

Genetik algoritma rastgele arama metodu olduğu için tek bir çözüm aramak yerine bir çözüm kümesi üzerinde çalışır. Optimum çözüme olası çözümlerin bir bölümü üzerinde gidilir. Böylece çalışmadaki sonuçlar her zaman en iyi olmaz. Çalışmada genetik algoritmanın kullanılmasının nedeni, genetik algoritmanın problemin doğasıyla ilgili herhangi bir bilgiye ihtiyaç duymamasıdır.

2. Materyal ve Yöntem

Genetik Algoritmalar, daha iyi çözümlere yavaş yavaş bir yaklaşım sağlayan geniş bir problem uzayı boyunca yönlendirilmiş rastgele bir araştırmaya imkan sağlar. Temel avantajı optimize edilmeye çalışılan problemin doğasıyla ilgili herhangi bir bilgiye ihtiyaç göstermemeleridir.

Okumaya devam et “Genetik Algoritma ile Çift Taraflı Montaj Hattı Dengeleme (Genetic Algorithms, C#)”

Genetik Algoritma ile Araç Rotalama Problemi (Genetik Algoritma, C#)

Bu çalışmada bir firmaya ait farklı taşıma hacmine sahip araçlarla en az araç ve en az yol gidilecek şekilde rotalama amaçlanmıştır. Çalışmada ikili turnuva methodu kullanılmıştır. Çalışma sonunda, araç sayısına göre yapılan nesil ve birey sayısı ayarının ardından  tasarruflu değerler üretilmiştir. Problemin Genetik Algortima ile çözümü için geliştirilen uygulama, c#(sharp) programlama dili ile yazılmıştır.

Örnek Genetik Algoritma İle Araç Rotalama Probleminde ;

Şirket Türkiye’de 5 bölgeye hizmet vermektedir. Bölgelerin kapsadığı şehirler şöyledir:
Ankara, Çankırı, Kırıkkale, Kastamonu Ankara Bölge Müdürlüğüne; Kayseri, Kırşehir, Nevşehir, Aksaray, Sivas, Niğde Kayseri Bölge Müdürlüğüne; Samsun, Sinop, Ordu, Tokat, Çorum, Amasya Samsun Bölge Müdürlüğüne; Trabzon, Gümüşhane, Giresun, Rize, Artvin Trabzon Bölge Müdürlüğüne; Zonguldak, Bolu Düzce, Karabük, Bartın Zonguldak Bölge Müdürlüğüne bağlıdır.
Rotanın bulunmasında kısıtlar araç sayısının minimum olması ve yolun en kısa olmasıdır.
Şirketteki Araç Sayıları ve Kapasiteleri:
1 tane 1490 kg’lık Transit
5 tane 7860 kg’lık Isuzu
3 tane 9130 kg’lık Mercedes
1 tane 14670 kg’lık Mercedes olmak üzere 10 tane araç vardır.

Projenin Kodları

Tüm projeyi İNDİR: Kaynak Kodu

Genetik Algoritma Kullanılarak Noktadan Noktaya Yol ve Rota Planlama (C#)

Projenin Kodları

Tüm projeyi İNDİR: Program Kodu ve Rapor

1.Giriş

Bu çalışmada bir kroki üzerinde bulunan noktalar arası rota ve yolun genetik algortima ile bulunması amaçlanmıştır. Genetik algoritma rastgele arama metodu olduğu için tek bir çözüm aramak yerine bir çözüm kümesi üzerinde çalışır. Optimum çözüme olası çözümlerin bir bölümü üzerinde gidilir. Böylece çalışmadaki sonuçlar her zaman en iyi olmaz. Çalışmada genetik algoritmanın kullanılmasının nedeni, genetik algoritmanın  problemin doğasıyla ilgili herhangi bir bilgiye ihtiyaç duymamasıdır. Temelinde gezgin satıcı problemine benzeyen çalışmanın , gezgin satıcı problemine benzer problemler içinde çözüm olması amaçlanmıştır.

2.Genetik Algoritma Yönteminin Probleme Uygulanışı

Problemin çözümü için populasyon büyüklüğü karar verilmelidir. Populasyon büyüklüğü seçilirken aşırı yüksek seçilirse gelişim yavaşlar, aşırı küçük seçilmesi durumunda da araştırma uzayı yetersiz olur. Problemimize en uygun populasyon büyüklüğü 30 birey olarak seçilmiştir. Programın arayüzünde birey sayısı değiştirilebilir. Her kromozom 20 genle temsil edilip, genler kodlanırken değer kodlama yöntemi kullanılmıştır. Her gen yönleri temsil eden 0;Batı, 1;Kuzey, 2;Doğu ve 3;Güney ile belirtilmiştir. Örnek olarak 5 nolu kromozomun genleri:01102033021011023221 gibi 20 gene sahiptir.

Populasyon büyüklüğü tamamlanıp, kromozomlar kodlandıktan sonra uygunluklarına göre seçilim yapıldı. Uygunluk değerleri hesaplanırken noktalar arası seyahat olduğu için kromozomun en son noktası ile ulaşmak istenen arasındaki farka bakılır. Bu yüzden uygunluk fonksiyonumuz 2 fonksiyonun toplamına eşittir. Birinci fonksiyonumuz en son nokta uzaklığı f(y) , ikinci fonksiyonumuz ise kromozomun aldığı yolların toplamı olan toplam mesafe f(z) fonksiyonudur. Uygunluk fonksiyonumuz f(x)=5*f(y)+ f(z) olarak belirlenmiştir. Burada son nokta uzaklığını fonksiyonu problem için daha önemli olduğundan katsayısı artılmıştır. Örneğin 6 nolu kromozom son noktası 21 , ulaşılmak istenen nokta 22 ise f(y)=20, ve aldığı yolların mesafesini ölçen f(z)=550 olduğunu düşünelim ,6 nolu kromozomun uygunluk değeri f(x)=5*20+550=650 olur. Kromozom ulaşılmak istenilen noktaya varmış olsaydı bu değer 550 olacaktı. Burada görüldüğü gibi son noktaya ulaşmak uygunluk değerini hesabının doğruluğunu kanıtlıyor. Okumaya devam et “Genetik Algoritma Kullanılarak Noktadan Noktaya Yol ve Rota Planlama (C#)”

Genetik Algoritma Parametreleri

Genetik algoritmanın performansını etkileyen önemli etmenlerden biri kontrol parametrelerinin belirlenmesidir. Kontrol parametrelerinin seçimi problem tiplerine göre farklılık göstermektedir. Farklı problem ve kodlama türlerine göre en uygun kontrol parametrelerin belirlenmesi için birçok çalışma yapılmıştır. Aşağıda GA kontrol parametreleri olan popülasyon büyüklüğü, çaprazlama olasılığı, mutasyon olasılığı, kuşak farkı, seçim yöntemi ve fonksiyon ölçeklemesi açıklanmaktadır.

1.Popülasyon Büyüklüğü

Genetik algoritmanın ilk adımı başlangıç popülasyonunun oluşturulmasıdır. Başlangıç popülasyonunu oluşturan bireylerin uygunluk değerleri GA performansını etkileyen unsurlardan biridir. Popülasyon oluşturan bireylerin sayısı küçük seçildiğinde iterasyonlar daha hızlı olacak ancak algoritmanın yerel optimuma takılma şansı artacaktır. Popülasyonun çok büyük seçilmesi çözüm kalitesini arttıracak ancak algoritmanın adımları daha uzun zaman alacaktır. Goldberg 1985’de, yalnızca kromozom uzunluğuna bağlı bir popülasyon büyüklüğü hesaplama yöntemi önermiştir. Golderg birçok araştırmacının popülasyon büyüklüğünü 30-200 aralığında seçtiğini belirtmiştir. Popülasyon büyüklüğünü kromozom uzunluklarını dikkate alarak belirlenmesinde seçilen yöntemlerden biri n kromozom uzunluğu olmak üzere popülasyon büyüklüğünün [n, 2n] arasında seçilmesidir. Popülasyon büyüklüğünün küçük bir değer olarak belirlenmeye çalışılmasının başlıca nedeni GA’nın diğer meta-sezgisel yöntemlerle çözüm süresi olarak rekabetçi olabilmesidir.

Okumaya devam et “Genetik Algoritma Parametreleri”