This paper studies a variant of the traveling salesman problem called the pickup-and-delivery traveling salesman problem with neighborhoods that combines traditional pickup and delivery requirements with the flexibility of visiting the customers at locations within compact neighborhoods of arbitrary shape. We derive two optimality conditions for the problem, a local condition that verifies whether a given tour is locally optimal at the visiting points and a global condition that can be used to cut off sub-optimal regions of the neighborhoods. We model the problem as a mixed-integer nonlinear program and propose a generalized Benders decomposition to solve instances of the problem with convex neighborhoods. Finally, we conduct an extensive set of computational experiments to demonstrate the efficacy of the proposed solution framework.