Egy memetikus algoritmus a járatszervezési problémára

Szerzők

  • István Burgulya

Kulcsszavak:

Evolúciós algoritmus, explicit kollektív memória, kombinatorikus optimalizálás

Absztrakt

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.

Letöltések

Megjelent

2008-02-15

Hogyan kell idézni

Egy memetikus algoritmus a járatszervezési problémára. (2008). ACTA AGRARIA KAPOSVARIENSIS, 12(2), 59-69. https://journal.uni-mate.hu/index.php/aak/article/view/1912