Vortrag aus Archiv

A Variable Neighborhood Search Framework for solving different Vehicle Routing Problems

28.11.2011

Vehicle routing problems (VRPs) are meaningful problems in real-life distribution management. Most of the algorithms for VRPs reported in the literature are used to solve one specific VRP. Normally, different variants ask for different parameter settings or even different approaches. In real-world situations on the vendor side as well as on the customer side, today’s economic conditions induce merging companies to larger units therefore vehicle fleets have to be able to service customers and routes with different tasks. Accordingly, a key issue is to design methods that are generic, although genericity should not be achieved at the expense of solution quality. We develop a unified framework for solving different VRPs with fixed fleet size beginning with the capacitated VRP through the VRPs with time windows and the open VRPs up to the time-dependent VRPs. Further we consider two different types of time windows: soft and hard time windows. Consequently we have to deal with two different evaluation functions. All problem variants are solved with a generic method, a modified variable neighborhood search algorithm while using a default parameter configuration. For realization the problems have to be transformed to a standardized VRP. A computational study, in which the different variants of VRPs are considered, is performed on standard benchmark instances from the literature. The outcomes of the tests are promising and they show that generality does not come at the expense of solution quality. The realized prototype for a generic framework provides a good basis for a further extension in terms of integration of more sophisticated tuning algorithms and state of the art statistical methods to evaluate the performance of the designed solution procedure.