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 di by an amount adi where 0 = a < 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 a on total distance and provide empirical results to illustrate ‘typical’ behavior.