The vehicle routing problem with demand range

We propose and formulate the vehicle routing problem with demand range (VRPDR), a new variation on the traditional vehicle routing problem. In the VRPDR, the delivery quantity for each customer i is allowed to vary from its original size d(i) by an amount alpha d(i) where 0 <= alpha < 1. In adding this limited flexibility to the problem, there is potential to generate significant savings in the total distance traveled. We address issues such as bounding the impact of a given alpha on total distance and provide empirical results to illustrate "typical" behavior.