Volume 22, No 4, 2015, P. 5-29
UDC 519.85
Kochetov Yu. A., Khmelev A. V.
Hybrid local search for the heterogenous fixed fleet vehicle routing problem
Abstract:
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.
Keywords: local search, exponential neighborhood, Lagrangian relaxation, subgradient optimization.
DOI: 10.17377/daio.2015.22.479
Yury A. Kochetov 1,2
Aleksey V. Khmelev 2
1. Sobolev Institute of Mathematics
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: jkochet@math.nsc.ru, avhmel@gmail.com
Received 13 March 2015
Revised 15 June 2015
References
[1] I. A. Davydov and Yu. A. Kochetov, VNS-based heuristic with an exponential neighborhood for the server load balancing problem, Electron. Notes Discrete Math., 47, 53–60, 2015.
