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, (Full Text)

  • Publication Type: Conference Paper / Full Text
  • Volume: 6025
  • Doi Number: 10.1007/978-3-642-12242-2-44
  • City: İstanbul
  • Country: Turkey
  • Page Numbers: pp.431-433
  • Galatasaray University Affiliated: Yes

Abstract

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.