A classical problem in distribution logistics is the problem of designing least cost routes from one depot to a set of geographically scattered points. All routes start and end at the depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle. This problem is known as the Vehicle Routing Problem (VRP). If each customer to be served is associated with two quantities of goods to be collected and delivered, the problem is then called the Vehicle Routing Problem with Pick-up and Delivery (VRPPD). In this paper, the Vehicle Routing Problem with Pick-up and Delivery (VRPPD) is used to solve the distribution problem face by a beverage industry where vehicles of a certain loading capacity must routinely visit several retailers. Each retailer has a certain demand of full bottles to be delivered and empty bottles to be picked-up and be brought back to the depot. A heuristic algorithm is then used to construct the routes with the objective of minimizing not only the number of vehicles required, but also the total travel distance (or total cost) incurred by the fleet of vehicles. Keywords: Vehicle Routing Problem, Pick-up and Delivery, Heuristic