Hybrid local search for the heterogenous fixed fleet vehicle routing problem

We consider the heterogeneous fixed fleet vehicle routing problem and assume that customers are presented by points in Euclidean plane and a limited fleet of heterogenous vehicles is available. The proposed hybrid local search algorithm uses permutations of customers for coding feasible solutions. For given permutation, the Lagrangian relaxation approach is applied as decoding method for this NP-hard problem. New intensification and diversification procedures are proposed and a new exponential neighborhood is introduced. Computational results for test instances with number of customers up to 255 are reported. New best found solutions are discovered for 15 test instances. Tab. 7, ill. 5, bibliogr. 26.