General Variable Neighborhood Search for Asymmetric Vehicle Routing Problem

Abstract

The minimization of total distance in an asymmetric vehicle routing problem with a hard time window for serving all the customers is considered. This problem is used to model a real-life problem of delivering perishable and non-perishable goods to multiple customers. All the customers should be visited exactly ones with one among a limited number of homogeneous vehicles (with the same capacity and speed). Having in mind that the problem is NP-hard, we developed a General Variable Neighborhood Search (GVNS) approach and tested it on a set of available real-life instances. Our computational results show that the proposed GVNS is able to generate high quality solutions within reasonably short CPU time.