We present a Variable Neighborhood Search approach to solving the one-commodity pickup-and-delivery travelling salesman problem. It is characterized by a set of customers, each of them supplying (as pickup customers) or demanding (as delivery customers) a given amount of a single product. A vehicle with a given capacity starts at the depot and must visit each customer once only and, the vehicle's capacity must not be exceeded. The objective is to minimize the total length of the tour. Thus, the problem considered contains the checking of existence of feasible travelling salesman's tour and the design of the optimal travelling salesman's tour, both being NP-hard. We adapt a collection of neighborhood structures which are mainly used for solving the classical travelling salesman problem: k-opt, double-bridge and insertion operators. Using a binary indexed tree, we efficiently update the data structures for feasibility checking in these neighborhoods. Our extensive computational analysis shows that the proposed variable neighborhood search based heuristics outperforms the best-known algorithms in terms of both the solution quality and computational efforts. Moreover, we improve the best-known solution of all benchmark instances from the literature (with 100 to 500 customers). We are also able to solve instances with up to 1000 customers.