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

Abstract

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.

The Traveling Salesman Problem with Pickup and Delivery (TSPPD) is an extension ofthe famous Traveling Salesman Problem (TSP). In the literature there are many problemsrelated to pickup and delivery but they have different features (i.e. single commodity ormulti commodities, single vehicle or multi vehicles, one-to-one or one-to-many etc.).TSPPD is a static simultaneous pickup delivery problem with a ?one-to-many-to-one?structure where there is only one vehicle and that each customer is visited exactly once.The problem involves two sets of customers. ?Delivery Customers? are served bydelivery of the goods from a central warehouse. ?Pickup Customers? need to delivergoods from their locations to the central warehouse. We call the central warehouse as?Depot? and all delivery and pickup services are done by a single vehicle with a givencapacity which is equal to Q. Given two types of goods (delivery and pickup goods), avehicle which departs from the depot with fully loaded satisfies all the customer?s needsand returns back to the depot. The objective of the TSPPD is to minimize the totaltravelling distance. The additional constraint of the TSPPD is that the vehicle load mustbe feasible throughout the tour; it must remain nonnegative and the total load should notexceed the vehicle capacity. TSPPD is an NP-hard combinatorial optimization problemsince it as an extension of the well known TSP. To the best of our knowledge there is notmany publications on the TSPPD. The motivation of this thesis is to propose an efficientGenetic Algorithm (GA) to solve TSPPD instances.GAs are search algorithms based on the mechanics of natural selection and naturalgenetics. The basic principle of the GAs comes from ?survival of the fittest? which isstated by Charles Darwin in ?The Origins of Species?. They are adaptive methods whichmay be used to solve search and optimization problems. The power of GA comes fromthe fact that the method is robust and which can be used successfully for a wide range ofproblem areas including those which are difficult for other methods to solve.The motivation behind of the proposed GA, lies in the Mosheiov Theorem. Mosheiov hasproved that when we construct a Hamiltonian tour covering all pickup and deliverycustomers without the depot, there exists at least one point ik on this tour such that whenwe insert the depot between ik and ik+1 the resulting tour is feasible. Considering thistheorem we have devised an efficient algorithm which consists of three steps. The firststep is to solve Hamiltonian tour through all customers by using the GA. The second stepis to find the best starting point to insert the depot. The final step is to apply a localneighborhood search which we term as ?Tuning Phase?. Computational experiments arereported on standard test instances from the literature. The experimental results show thatour algorithm yields promising performance in terms of both accuracy and efficiencycompared to existing algorithms in the literature. We should also report that the tuningphase step considerably improves the solution obtained after the second step. This showsus the power of our tour improvement procedure, which is specially designed for theTSPPD.