A PSO-Based Memetic Algorithm for the Team Orienteering Problem

Dang D., Guibadj R. N., Moukrim A.

Conference on EvoApplications 2011: EvoCOMPLEX, EvoGAMES, EvoIASP, EvoINTELLIGENCE, EvoNUM, AND EvoSTOC, Torino, İtalya, 27 - 29 Nisan 2011, cilt.6625, ss.471-480 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 6625
  • Basıldığı Şehir: Torino
  • Basıldığı Ülke: İtalya
  • Sayfa Sayıları: ss.471-480
  • İstanbul Teknik Üniversitesi Adresli: Hayır

Özet

This paper proposes an effective Particle Swarm Optimization (PSO)-based Memetic Algorithm (PSOMA) for the Team Orienteering Problem (TOP). TOP is a particular vehicle routing problem whose aim is to maximize the profit gained from visiting clients while not exceeding a travel cost/time limit. Our PSOMA features optimal splitting techniques and genetic crossover operators. Furthermore, the memetic characteristic of our PSOMA is strengthened by an intensive use of local search techniques and also by a low value of 0.07 for inertia. In our experiments with the standard benchmark for TOP, PSOMA attained a gap of only 0.016%, as compared to 0.041%, the best known gap in the literature.