The classic Capacitated Vehicle Routing Problem (CVRP) has been studied in the Operations Research field for over 5 decades. This thesis formulates the vehicle routing problem with a variation that has not been studied in detail. It is called the Vehicle Routing Problem with Demand Ranges (VRPDR). With increasing competition, corporations are looking to minimize costs. This problem aims to reduce the cost of distributing goods by allowing flexibility in the delivered or dropped off quantity. This benefits the customer as well, by reducing storage and other inventory costs. We solve the VRPDR problem where the customer gives the distributor a demand range. The distributor is rewarded for delivering more. A metaheuristic, record-to-record travel with demand range (RTRDR), is developed which is capable of solving large problem instances. The metaheuristic is a modification of a successful CVRP metaheuristic used in the past. In this thesis, we report results on problems ranging in size from 560 to 1200 customers. The developed metaheuristic uses the Clarke-Wright procedure to get initial solutions and then applies record-to-record travel in conjunction with two-opt moves, one point moves, and two point moves. Since the problem has not been studied yet from a computational point of view, we have developed a comparison algorithm, which takes advantage of the demand range flexibility of this problem only after the algorithm has optimized for distance alone. We use the results from this algorithm as a benchmark to compare with our proposed metaheuristic RTRDR.