In this paper we present a new memetic algorithm for the CVRP (Capacitated Vehicle Routing Problem). The new algorithm was developed from our earlier multi-objective algorithm for the vehicle routing problem - selecting and further developing one part of the earlier algorithm. The new algorithm is a steady-state evolutionary algorithm. It uses tournament selection; the descendents are derived from the parents by mutation based on the EVL (Extended Virtual Loser) where the EVL is an explicit collective memory technique. The algorithm is a memetic algorithm and uses five different stochastic 2-opt local searches to improve the descendents. We used some test problems of the Vehicle Routing Data Sets and of Christofides. Comparing the results with other method’s results we concluded: in the case of n < 200 costumers we got similar results that was published earlier. ; A cikkben az egy telephelyes, kapacitással adott járatszervezései problémára (CVRP: Capacitated Vehicle Routing Problem) mutatunk be egy memetikus algoritmust. A megoldáshoz egy korábbi több-célfüggvényes járatszervezési algoritmusunkat használjuk fel, kiemelve és továbbfejlesztve az algoritmusból az egy célfüggvényes járatszervezési problémánál alkalmazható algoritmus részt. Az új algoritmus egy steady-state rendszer, amely tournament szelekciót alkalmaz, az utódokat mutációval generálja a szülőkből, ahol a mutáció egy memória alapú technikán, az EVL (Extended Virtual Loser) technikán alapul. Az algoritmus, mint memetikus algoritmus, az utódok minőségét ötféle sztochasztikus helyi kereső eljárással javítja. Az algoritmust a „Vehicle Routing Data Sets”, valamint Christofides néhány tesztfeladatán ellenőriztük. Az eredményeket más módszerekkel is összehasonlítottuk: n < 200 fogyasztó esetén a korábban publikált eredményekhez hasonlót kaptunk.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    A memetic Algorithm for the Capacitated Vehicle Routing Problem ; Egy memetikus algoritmus a járatszervezési problémára


    Beteiligte:

    Erscheinungsdatum :

    2008-02-15


    Anmerkungen:

    Acta Agraria Kaposváriensis; Vol. 12 No. 2 (2008): Acta Agraria Kaposváriensis; 59-69 ; Acta Agraria Kaposváriensis; Évf. 12 Szám 2 (2008): Acta Agraria Kaposváriensis; 59-69 ; 1418-1789


    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    629



    A memetic algorithm for the open capacitated arc routing problem

    Fung, Richard Y.K. / Liu, Ran / Jiang, Zhibin | Elsevier | 2012


    A memetic algorithm for the open capacitated arc routing problem

    Fung, Richard Y.K. | Online Contents | 2013


    A REVIEW OF MEMETIC ALGORITHM FOR CAPACITATED VEHICLE ROUTING PROBLEM WITH TIME WINDOWS

    Pandey, Digesh / Srivastava, Namita | BASE | 2018

    Freier Zugriff

    Memetic algorithm with adaptive local search for Capacitated Arc Routing Problem

    Yao, Tingting / Yao, Xin / Han, Shuangshuang et al. | IEEE | 2017