The paper considers 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. It describes a new heuristic algorithm for ACVRP that, starting with an initial, possibly infeasible, solution, determines the final set of vehicle routes through an insertion procedure and intra-route and inter-route arc exchanges. The initial infeasible solution is obtained by using the additive bounding procedures for ACVRP described in Fischetti, Toth, and Vigo. Computational results on randomly generated test problems classes are presented, showing that the proposed approach favourably compares with previous algorithms from the literature.
