Tavlama Benzetimi (Simulated Annealing) ile C-VRP (Capacitated Vehicle Routing Problem)

Müşteri taleplerini en kısa zaman, en kısa yol veya en az maliyet gibi amaçlardan birini veya birkaçını en iyileyecek şekilde karşılayan araç rotalarının belirlenmesi günümüz işletmelerinin üzerinde durduğu problemlerden birisidir. Kamyon gönderme problemi olarak VRP ilk 1959 yılında Dantzig ve Ramser tarafından tanıtıldı (Toth ve Vigo, 2002). Yazarlar, sorunun çözümü için ilk matematiksel programlama denklemini ve algoritmik yaklaşımını önerdi. Çeşitli kısıtlamaları verilen araçlar için güzergah optimizasyonu araç rotalama sorununun (VRP) kökenidir. VRP standart versiyonu olan kapasite kısıtlı VRP (CVRP) kolay ifade edilen ama çözümü zor olandır. CVRP, bütün müşterilere hizmet vermek üzere tek bir depodan filodaki homojen araçların bir dizi teslimat problemidir ve amaç tüm müşterilere hizmet edilmeli ve filo tarafından kat edilen toplam mesafe en aza indirilmelidir. Her araç kapasite ve maliyet olarak benzerdir ve araçlar bir depodan ayrılmalı ve o depoya dönmelidir. Her müşterinin bilinen bir talep miktarı vardır ve tek bir aracın tek bir ziyaretiyle bu talep karşılanır.

Resim 1: Bir VRP problemi çözümü gösterimi

VRP’de araç filosu homojendir. VRP varsayımına göre; bir müşteri talebi, bir aracın bir ziyareti ile tatmin edilmelidir. Diğer bir deyişle, araçlar arasında bir müşteriye teslimatı bölmeye izin verilmez. Ancak ayrılabilir teslimat dağıtım strateji dağıtım maliyetlerini düşürebilir. Bu nedenle, bölümlenmemiş teslimat stratejisi genişletilerek VRP içine bölünmüş teslimat dahil edilerek etkisi incelenmelidir. VRP’de bölünmüş teslimatlara izin verilirse problem bölünmüş teslimatlı VRP (SDVRP) olarak adlandırılır.

“Her müşteri sadece bir araç tarafından ziyaret edilmelidir” yaklaşımının genişletilmesi olarak SDVRP, CVRP’nin genişletilmiş halidir. Müşteri isteklerinin bölümlenmesine izin verilmektedir Bununla birlikte, bu kısıtlama serbest bırakıldığında, arama alanı daha büyük bir hale gelir. Bu durumda optimum çözümü bulmak veya etkin çözüme ulaşmak çok zor hale gelir.

Tavlama benzetimi stratejisi, doğal ısıl işlemde uygulanan, malzemenin belirli bir sıcaklığa kadar ısıtılması, bu ısıda bir süre tutulması ve son olarak da belirli tekniklerle soğutulması sayesinde, temelde 3 aşamada malzemeye daha kararlı bir yapı kazandırma prosesinden esinlenerek geliştirilmiştir. Bu aşamada soğutma işlemi, elde edilmek istenen malzeme özelliklerine bağlı olarak farklı hızlarla, farklı oranlarla ve değişik şekillerde uygulanabilmektedir. Bu prosesin sezgisel bir teknik olarak optimizasyon problemlerinin çözümü üzerindeki ilk uygulamaları 1983 yılında Kirkpatrick ve arkadaşları tarafından yapılmıştır (Kirkpatrick, 1983).

Bu çalışmada temel olarak CVRP’nin tavlama benzetimi yardımıyla çözümü anlatılacaktır. Bunun için Java dilinde geliştirilmiş bir program kullanılmıştır. Uygulama ileriki bölümlerde detaylı bir şekilde tanıtılacaktır. Uygulama ile literatürde ifade edilen klasik CVRP çözülmektedir. Eğer araç kapasitesini aşan müşteri istekleri olduğunda sadece bu teslimatlar bölünerek gerekli müşteri ihtiyacı karşılanmaya çalışılmaktadır. Bir başka deyişle ihtiyaç çeşitli servis araçları arasında bölümlenmektedir. Bu çalışmada bu probleme SDVRP’den farklı olarak servis bölümlemeli (split service) CVRP (CVRPSS) demeyi uygun buldum. Resim 2’de problemin çözüm şeması sunulmuştur. 

Resim 2: Resim 2: Servis bölümleme şeması

Servisi bölümlemek için uygulama 2 yaklaşımı desteklemektedir. Birinci yaklaşımda aracın tam kapasitesiyle müşterinin ihtiyaçları karşılanmakta yani depodan ilgili düğüme tam dolu araçla rota oluşmakta, en sonunda araç kapasitesini aşmayan kalan miktar ihtiyacı karşılanmaktadır. İkinci yaklaşımda ise ihtiyaç, müşteri ihtiyaçlarını karşılayabilecek servis araçlarına göre eşit olarak dağıtılıp karşılanmaktadır. Bu durumda depoya dönmeden önce araç kapasitesini aşmamak kaydıyla başka müşterilere de uğranma durumu söz konusu olabilmektedir. Her iki yaklaşımda da problem klasik CVRP’ye dönüştürülüp o şekilde çözüm bulunmaya çalışılmaktadır.

Resim 3: Birinci yaklaşım ile servis bölümleme örneği

Resim 4: İkinci yaklaşım ile servis bölümleme örneği

C-VRP (Capacitated Vehicle Routing Problem)

VRP’nin temel bir versiyonu olan CVRP’de müşteri taleplerinin karşılanmasının bölümlenmeden (not split) yapılmasını ve her aracın benzer kapasitede ve maliyette olmasını öngörür. Amaç araç rotalama sayısını bulmak ve maliyetleri aşağıdaki durumlarla minimize etmektir:

• Her rota depo düğümüne ziyaret eder 
• Her bir müşteri düğüm tek rotadan ziyaret edilir 
• Bir rota üzerinde talep toplamı aracın kapasitesini aşamaz

CVRP ile farklı varsayımları birleştirmeyle, VRP'nin varyasyonları oluşturulur. Bu varyasyonlardan biri de SDVRP dir. 

Trudeau ve Dror, 1990 yılında yayınladıkları çalışmada ilk defa bölünmüş teslimatlı VRP (SDVRP) kavramını incelemişlerdir. CVRP’de bir müşteri sadece bir araç (Talep aracın kapasitesini aşmadığı sürece) tarafından karşılanırken, SDVRP’de bir müşterinin teslimatları iki veya daha fazla araç arasında bölünebilir. Başka bir deyişle, bir müşteri düğüm birden fazla araç tarafından ziyaret edilebilir. Bu uygulamada sadece müşterinin talebi araç kapasitesini geçtiği durumda talep birden fazla araçla giderilmiştir. Uygulamada kapasite aşma durumunda yukarıdaki bölümde bahsedilen iki yaklaşımla kapasite sorunu giderilmiştir. 

Uygulamada kapasite aşma durumunda iki yaklaşımla kapasite sorunu giderilmiştir. Birinci ve ikinci yaklaşıma ait kod parçaları aşağıda sunulmuştur. Uygulama arayüzünde bu seçimi aşağıdaki gibi yapabilirsiniz.

//check City capacity

if(cty.demand>tcapasity)

{

//if capasity over then split equal

       if(splitType.getSelectedIndex()==0)

       {

       //reset truck

       yuk=0;

       int extraVehicle=(int) Math.ceil(cty.demand/tcapasity);

       int sameLoad=(int) (cty.demand/extraVehicle);

                                 

                           while((cty.demand-tcapasity*yuk)>tcapasity)

                           {

//do something

                           yuk++;

                           }//end while

        }

//if capasity overload fully then load the rest

else

{

//reset truck

yuk=0;                                 

                           while((arademand=cty.demand-tcapasity*yuk)>tcapasity)

                           {

                           //do something

                           yuk++;

                           }//end while

       }//end else

}//end if

Tavlama Benzetimi (Simulated Annealing)

Tavlama benzetimi stokastik arama yöntemidir. Katıların fiziksel tavlanma süreci ile olan benzerlikten ileri gelmektedir. Katıların ısıtılması ve sonra yavaş yavaş soğutulması esasına dayanır. Kirk Patrick ve arkadaşları tarafından 1983 yılında önerilmiştir.

Tavlama, Malzemeyi belirli bir süre (tavlama sıcaklığına kadar) ısıttıktan sonra, yavaş yavaş soğutmaktır. Tavlama malzemeyi rahatlatmak, yumuşatmak ve iç yapıyı daha kullanılabilir hale getirmek için yapılan ısıl işlemlerin geneline verilen addır. Isıl işlem, bir katının sıcaklığının belirli bir maksimum dereceye kadar artırılarak tekrar azaltılması işlemidir. Maksimum sıcaklıkta kristalin tüm molekülleri, kendilerini rasgele olarak sıvı faza ayarlar. Sonra, erimiş kristalin sıcaklığı kristal yapı soğutuluncaya kadar düşürülür. Soğuma uygun şekilde yapılırsa kristal yapı çok düzenli olur. 

Tavlama Benzetimi, katıların ısıtılması ve sonra kristalleşmeye kadar yavaş yavaş soğutulması esasına dayalı bir yaklaşımla çözüm alanını tarar. Bu benzetime göre, sıcaklık değeri, elde edilen en iyi çözümden daha kötü çözümlerin kabul edilme olasılığını belirlemede kullanılır. Yüksek bir sıcaklık değeri ile başlatılır ve her bir adımda sıcaklık değeri düşürülmeden önce belli sayıda çözüm üretilir. Yeni çözümler belirlenen kriterlere göre kabul edilir veya reddedilir. Düşen her sıcaklık, eldeki çözümün bırakılıp yeni bir çözüme geçme ihtimalinin azalmasına etki eder. Sıcaklık minimum değere ulaştığında veya algoritma istenen iterasyon kadar çalıştığında yahut istenen çözüme ulaşıldığında algoritma sonlandırılır. 

Amaç fonksiyonunda Δ kadar bir yükselmeye yol açan hareketin kabul edilme olasılığını veren fonksiyon “kabul fonksiyonu” olarak adlandırılır. Kabul koşulu resim 5’te gösterilmiştir. [0,1] arasında seçilen rassal rakam bu kabul fonksiyonunda küçükse komşu çözüm kabul edilir.

Resim 5: Kabul koşulu matematiksel formül

Uygulamada bu kontrolü yapan kod parçası aşağıda verilmiştir.

......

// Decide if we should accept the neighbour

if (acceptanceProbability(currentEnergy, neighbourEnergy, temp) > Math.random()) {

currentSolution = new Tour(newSolution.getTour());

                    }

.....

       public static double acceptanceProbability(double energy, double newEnergy, double temperature) {

             // If the new solution is better, accept it

             if (newEnergy < energy) {

                    return 1.0;

             }

             // If the new solution is worse, calculate an acceptance probability

             return Math.exp((energy - newEnergy) / temperature);

       }

Tavlama benzetimine ait akış şeması aşağıda sunulmuştur.

Resim 6: Tavlama Benzetimi Akış Şeması

Tavlama Benzetimi Algoritması

Bir Tavlama benzetimi algoritması genel olarak bir başlangıç çözümü, komşu çözümler oluşturma yöntemi ve bir tavlama programından oluşmaktadır. Tavlama sürecinin işlevi, yeterince yüksek bir sıcaklıktaki bir çözümden başlayıp sıcaklığı aşamalı olarak azaltarak iyi ve kötü çözümler arasında dolaşmak ve en sonunda en iyi çözüme ulaşmaktır.

       Begin

Başlangıç çözümü seç

Başlangıç sıcaklığı seç (örn: t=100)

Sıcaklık azaltım fonksiyonu belirle [f(t)]

repeat

repeat

Yeni bir komşu çözüm üret

if (yeni - eski) < 0 then yeni çözümü seç

else begin

[0,1] aralığında rassal sayı üret (r)

if r < ( 1 / (exp(abs(yeni - eski)/t) ) then yeni çözümü seç

end

until [iterasyon sayısına kadar veya maksimum iterasyon sayısına kadar]

t = f(t);

until (t < minimum sıcaklık) veya (uygun çözüm bulununcaya kadar) veya (döngü> Maksimum Döngü sayısı oluncaya kadar)

  End

Algoritmaya Ait Kararlar

Algoritmaya ait kararlar 4 maddede toplanabilir. Bunlar aşağıda detaylanarak açıklanacaktır.

• Başlangıç Sıcaklığının Belirlenmesi 

Tavlama benzetiminde de başlangıç sıcaklığının belirlenmesi oldukça önemlidir. Başlangıç sıcaklığının gereğinden fazla bir değere çıkartılması gereksiz işlem sürelerine neden olurken; düşük sıcaklıklarda başlanması, algoritmanın yerel minimumlarda takılma riskini arttırmaktadır. Bu açıdan eğer başlangıç sıcaklığının değeri hakkında kesin bir sınır belirlenemiyorsa, mümkün olduğunca yüksek değerlerin atanması daha uygun olacaktır.

• Sıcaklık değiştirme kuralının tanımlanması 

o Aritmetik sıcaklık düşürme: Tk=Tk-1-c

o Geometrik sıcaklık düşürme: Tk=Tk-1*d (d<1 ve 1’e yakın d=1-[soguma orani])

o Ters Fonksiyon sıcaklık düşürme: Tk=c/(1+k)

o Logaritmik sıcaklık düşürme: Tk=c/Log(1+k)

• Her sıcaklıkta gerçekleştirilecek iterasyon sayısının tanımlanması 

o Sabit: Nk=C

o Aritmetik: Nk=Nk-1 + C

o Geometrik: Nk=Nk-1/a (a<1)

o Logaritmik: Nk=C/Log(Tk)

o Üstel: Nk=(Nk-1)(1/a) (a<1)

• Çözüm aramanın durdurulması için durdurma koşullarının belirlenmesi 

o Belirlenen maksimum döngü sayısına ulaşılması (M)

o Belirlenmiş minimum sıcaklığa ulaşılması (minT)

o İstenen kriterleri sağlayan uygun çözüme ulaşılması (FS)

o En iyinin belli bir döngüde bulunmama durumunda sonlanması (LoopMax)

Sıcaklık Değiştirme Kuralının Tanımlanması:

Sıcaklık 4 farklı şekilde değiştirilebilir. Sıcaklık değişimine ait arayüz ve kod parçası aşağıda verilmiştir.

       // Cool system

       /*

      temp-=c; //aritmetik          

      temp *= 1-[soguma orani]; //Geometrik (d<1 --> d=1-[soguma orani])

      temp = temp/(1+repeatNumber); //Ters Fonksiyon

      temp = temp/Math.log(1+repeatNumber); //logaritmik

*/

//diğer değerler

coolingRate ç Soğuma Oranı

c ç Soğuma Sabiti (c)

       // Cool system

             switch (combotemp.getSelectedIndex()) {

             case 0:

                    temp-=c; //aritmetik

                    break;

             case 1:

                    temp *= 1-coolingRate; //Geometrik

                    break;

             case 2:

                    temp = c/(1+repeatNumber); //Ters Fonksiyon

                    break;

             case 3:

                    temp = c/Math.log(1+repeatNumber); //logaritmik

                    break;

             default:

                    break;

             }

Her sıcaklıkta gerçekleştirilecek iterasyon sayısının tanımlanması:

Aynı sıcaklıkta yapılacak olan iterasyon sayısının belirlenmesi 5 şekilde yapılır. İterasyon tipine ait arayüz ve kod parçası aşağıda verilmiştir.

             /*

             N=C; //sabit (C; C=N)

             N=Nonceki+C; //aritmetik

             N=(int) (Nonceki/a); //geometrik  (a<1)

             N=(int) (C/Math.log(temp)); //logaritmik      

             N=(int) Math.pow(Nonceki, 1/a); //üstel (a<1)

       */

             //diger degiskenler

             int Nsabit=N;

             int Nartim=N;

             temp ç sıcaklık değeridir.

             N ç İterasyon Sabiti (N)

             a ç a;

                    switch (comboiteration.getSelectedIndex()) {

                    case 0:

N=N;

                           break;

                    case 1:

                           N+=Nartim; //aritmetik

                           break;

                    case 2:

                           N=(int) (N/a); //geometrik

                           break;

                    case 3:

                           N=(int) (Nsabit/Math.log(temp)); //logaritmik

                           break;

                    case 4:

                           N=(int) Math.pow(N, 1/a); //üstel

                           break;

                    default:

                           break;

                    }

Çözüm aramanın durdurulması için durdurma koşullarının belirlenmesi:

Tavlama benzetiminde programın çalışmasının sonlanması ve bir çözüm gösterilmesi için 4 farklı durdurma koşulu tanımlanmıştır. Durdurma koşulu parametrelerinin setlenmesi ve koşul durdurma kodu aşağıdadır.

// Loop until system has cooled or found acceptable feasible solution or maximum repeat number or maximum notfound best solution

//diğer değişkenler

minT ç Minimum Sıcaklık

M ç Maksimum Döngü #

FS ç İstenen Çözüm (FS)

Floopmax ç Bulunmama Durumu (LoopMax)

while (temp>minT && best.getDistance()>FS && repeatNumber<M && notfound<FLoopmax)

{

             repeatNumber++;

             notfound++;

                       //do something

}

2-Opt Optimizasyonu

2-opt optimizasyonu programın çalışması bulunduktan sonra işletilen bir optimizasyondur. 2-opt ile aynı rota içindeki birbirinden uzak uçların yer değiştirmesiyle daha iyi çözümün bulunması amaçlanır. Program belirlenen sayıda en iyileri tutarak bunlar içinde 2-opt uygular ve en iyi bulunan optimize edilmiş sonucu Final çözüm olarak ekrana yazdırır. 2-opt seçim arayüzü ve kodu aşağıda verilmiştir

//diğer değişkenler

Fifo ç En iyi adet sayısınca çözümlerin bulunduğu yığın değeridir.

//2-opt optimization settings

             Tour twooptSolution=new Tour(best.getTour());

             Tour twooptLastSolution=new Tour(best.getTour());;

            

//add 2-optimized solution to fifobest stack

LinkedList<ArrayList> fifobest=new LinkedList<ArrayList>();

             if(chk2opt.isSelected())

             {

                   

                    //apply 2-opt for the best solutions...

       for(int eni=0;eni<fifo.size();eni++)

       {

                    twooptSolution=new Tour(fifo.get(eni));

                    twooptLastSolution=new Tour(fifo.get(eni));

                          

       for(int i = 0; i < twooptSolution.tourSize(); i++)

       {

       for(int j = i+1; j < twooptSolution.tourSize(); j++)

       {

                                  City city1=twooptSolution.getCity(i+1);

                                  City city2=twooptSolution.getCity(j);

       //eğer seçilen 2 şehir depo şehir ise hiçbir işlem yapılmaz                      if(city1==TourManager.getStartCity()||city2==TourManager.getStartCity())

             {

                    break;

             }

       else

             {

                    twooptSolution.setCity(i+1, city2);

                    twooptSolution.setCity(j, city1);

//2-opt sonrasinda elde edilen sonuç iyiyse bu degisken en iyi olarak işlem gorur

             if(twooptSolution.getDistance() < twooptLastSolution.getDistance())

                           {                                      

                           twooptLastSolution.setCity(i+1, city2);

                           twooptLastSolution.setCity(j, city1);

                           }//end if

                    twooptSolution=new Tour(twooptLastSolution.getTour());

             }//end else

       }//end for

}///end for

                   

       fifobest.add(twooptLastSolution.getTour());

}//end for fifo

            

//Find Best Solution.. Assume first is best

Tour firstbest=new Tour(fifobest.getFirst());

while(!fifobest.isEmpty())

{

              Tour arabest= new Tour(fifobest.removeFirst());

              

if(arabest.getDistance()<firstbest.getDistance())

              {

             twooptLastSolution=new Tour(arabest.getTour());

             firstbest=arabest;

              }

}//end while

Tavlama benzetimi ile CVRP için geliştirilmiş uygulamaya ve kodlarına bu blog sayfalarından ulaşabilirsiniz. Uygulama için tıklayınız.