An evolutionary approach to the traveling salesman problem with pickup and delivery based on depot insertion and removal moves

Gezgin Satıcı Problemi (GSP) bir sehirden baslayıp, listedeki tüm sehirleri sadece birkez ziyaret edip, tekrar basladığı sehre dönen bir satıcı için en kısa turun belirlenmesiproblemidir. Toplamalı Dağıtımlı Gezgin Satıcı Problemi (TDGSP) de GSP'nin farklıbir türüdür. Literatürde toplamalı dağıtımlı problemlerin bir çok farklı karakteristiktekiçesitleri mevcuttur. (Ör: Tek ürünlü-çok ürünlü, tek araçlı ? çok araçlı, tekten-teke,çoktan-çoka, vs.). Bu çalısmada incelenen problem, statik, eszamanlı, tek araç ileyapılan ve bütün sehirlerin tek bir seferde ziyaret edildiği dağıtım ve toplamaproblemidir. Problem iki çesit müsteriyi barındırır. Dağıtım yapılan müsteriler depodanmal talep müsterilerdir. Toplama yapılan müsteriler ise depoya mal gönderenmüsterilerdir. Bütün toplama ve dağıtım islemleri, sığası Q değerine esit olan bir araçvasıtasıyla gerçeklestirilir. Bu araç tam yüklü olarak depodan çıkar ve bütün müsteriihtiyaçlarına cevap vererek tekrar depoya geri döner. TDGSP'nin en önemli ilave kısıtıaraç yükünün tur boyunca olurlu olması gerektiğidir. Araç yükü tur boyunca negatifolmamalı ve yük araç sığasını geçmemelidir. TDGSP, GSP gibi NP-zor problemlersınıfında yer almaktadır. Yapmıs olduğumuz yazın taramalarına göre TDGSP hakkındaçok sayıda yayın bulunmamaktadır. Bu tezin amacı bu bosluğu doldurmak veTDGSP'nin çözümü için etkin bir Genetik Algoritma (GA) gelistirmektir.GA'lar temelinde doğal seçimi esas alan arama algoritmalarıdır ve doğadaki evrimsürecini taklit etmeye dayalı sezgisel teknikleri barındırırlar. GA'nın temel prensibiCharles Darwin'in ?Türlerin Kökeni? kitabında tanımladığı ?güçlü olanın hayattakalması? ilkesine dayanır. GA'lar diğer metotlar ile çözülemeyecek bir çok farklıalandaki problemin çözümünde fayda sağlamaktadır.Bu tezde gelistirilen GA'nın temel prensibi Mosheiov'un TDGSP için ispatlamısolduğu teoreme dayanmaktadır. Mosheiov su sonucu ispatlamıstır: ?Eğer depo hariçdiğer müsterilerin hepsini kapsayan bir Hamilton turu olusturulursa bu tur içerisinde enaz bir ik noktası vardır ki; depo, ik ve ik+1 arasına yerlestirilirse yeni olusan Hamilton turuTSPPD için olurlu olur. Bu teoreme dayanarak bu tezde üç asamalı bir algoritmagelistirilmistir. Algoritmanın birinci asamasında depo hariç diğer bütün müsterileriiçinde barındıran bir Hamilton turu GA kullanılarak olusturulur. ?kinci asamada depo,en optimum olurlu noktadan tura yerlestirilir. Son olarak ise ?iyilestirme asaması?olarak adlandırdığımız bir yerel arama metodu kullanılır. Gelistirilen algoritmaliteratürdeki mevcut TDGSP örnekleri ile test edilmistir. Yapılan denemelerde gerekhız gerek çözüm iyiliği açısından iyi sonuçlar elde edilmistir. Bununla birliktealgoritmanın 3. asamasında kullanılan ve TDGSP'ye özel olarak gelistirilmisiyilestirme asamasının 2. asamadan çıkan sonuçlar üzerinde hatırı sayılır iyilestirmeleresebep olduğu gözlemlenmistir.