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, Turkey, 7 - 09 April 2010, vol.6025, pp.431-433 identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 6025
  • City: İstanbul
  • Country: Turkey
  • Page Numbers: pp.431-433
  • Middle East Technical University Affiliated: Yes


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.