In this paper we propose a population based memetic algorithm, the Discrete Bacterial Memetic Evolutionary Algorithm for solving the one-commodity Pickup-and-Delivery Traveling Salesman Problem. The algorithm was tested on benchmark instances up to 100 nodes, and the results were compared with the state-of-the art methods in the literature. For all instances the DBMEA found optimal or close-optimal solutions.