A problem generator–solver heuristic for vehicle routing with soft time windows

In this paper we consider the vehicle routing problem with soft time window constraints (VRPTW), in which vehicles are allowed to service customers before and after the earliest and latest time window bounds, respectively. This relaxation comes at the expense of appropriate penalties that reflect that time window violations have on the customers' satisfaction. The problem is of particular importance for fleet planning as it allows decision-makers from both the logistics and marketing–sales side to determine minimal fleet sizes by appropriate contract negotiations for order delivery times. To solve the problem, we couple the nearest-neighbor method with a problem generator that provides, in a structured manner, numerous instances that result from the manipulation of the level of time window violations and the population of customers that allow such violations. The proposed heuristic results in solutions that reduce the number of vehicles required for the hard case and provide minimal violations of time windows. Computational results on a set of benchmark problems show that our method outperforms previous approaches to the vehicle routing problem with soft time windows, and that it can serve as the basis for efficient and effective fleet planning.