A heuristic algorithm for the Asymmetric Capacitated Vehicle Routing Problem

We consider the Asymmetric Capacitated Vehicle Routing Problem (ACVRP), a particular case of the standard asymmetric Vehicle Routing Problem arising when only the vehicle capacity constraints are imposed. ACVRP is known to be NP-hard and finds practical applications, e.g. in distribution and scheduling. In this paper we describe the extension to ACVRP of the two well-known Clarke–Wright and Fisher–Jaikumar heuristic algorithms. We also propose a new heuristic algorithm for ACVRP that, starting with an initial infeasible solution, determines the final set of vehicle routes through an insertion procedure as well as intra-route and inter-route arc exchanges. The initial infeasible solution is obtained by using the additive bounding procedures for ACVRP described by Fischetti, Toth and Vigo in 1992. Extensive computational results on several classes of randomly generated test problems involving up to 300 customers and on some real instances of distribution problems in urban areas, are presented. The results obtained show that the proposed approach favourably compares with previous algorithms from the literature.