A Genetic Algorithm for the Traveling Salesman Problem with Pickup and Delivery Using Depot Removal and Insertion Moves

Cinar V., ÖNCAN T., SÜRAL H.

Evo Applications 2010 Conference, İstanbul, Türkiye, 7 - 09 Nisan 2010, cilt.6025, ss.431-433 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 6025
  • Basıldığı Şehir: İstanbul
  • Basıldığı Ülke: Türkiye
  • Sayfa Sayıları: ss.431-433
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

In this work, we consider the Traveling Salesman Problem with Pickup and Delivery (TSPPD), which is an extension of the well-known NP-hard Traveling Salesman Problem. We propose a Genetic Algorithm (GA) based on a specially tailored tour improvement procedure for the TSPPD. Computational experiments are reported on the test instances taken from the literature. The experimental results suggest that the proposed GA yields a promising performance in terms of both accuracy and efficiency compared to existing algorithms in the literature.