DOI 10.1007/s10479-006-0057-0 The vehicle routing problem with demand range

Abstract 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 αdi where 0 ≤ α < 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 α on total distance and provide empirical results to illustrate “typical” behavior