Volume 22, No 5, 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 ²
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.

[2] I. A. Davydov, Yu. A. Kochetov, N. Mladenović, D. Urošević, Fast metaheuristics for the discrete (r|p)-centroid problem, Avtom. Telemekh., No. 4, 106–119, 2014. Translated in Autom. Remote Control, 75, No. 4, 677–687, 2014.

[3] P. A. Kononova and Yu. A. Kochetov, The variable neighborhood search for the two machine flow shop problem with a passive prefetch, Diskretn. Anal. Issled. Oper., 19, No. 5, 63–82, 2012. Translated in J. Appl. Ind. Math., 7, No. 1, 54–67, 2013.

[4] P. I. Stetsyuk, Metody ellipsoidov i r-algoritmy (Ellipsoid methods and r-algorithms), Evrika, Chisinau, 2014.

[5] R. Baldacci, M. Battarra, and D. Vigo, Routing a heterogeneous fleet of vehicles, in B. Golden, S. Raghavan, and E. Wasil, eds., The Vehicle Routing Problem: Latest Advances and New Challenges, pp. 3–27, Springer, New York, 2008 (Oper. Res./Comput. Sci. Interfaces, Vol. 43).

[6] R. Baldacci and A. Mingozzi, A unified exact method for solving different classes of vehicle routing problems, Math. Program., Ser. A, 120, No. 2, 347–380, 2009.

[7] M. Boudia, C. Prins, and M. Reghioui, An effective memetic algorithm with population management for the split delivery vehicle routing problem, in Hybrid Metaheuristics (Proc. 4th Int. Workshop Hybrid Metaheuristics, Dortmund, Germany, Oct. 8–9, 2007), pp. 16–30, Springer, Berlin, 2007 (Lect. Notes Comput. Sci., Vol. 4771).

[8] J. Brandão, A deterministic tabu search algorithm for the fleet size and mix vehicle routing problem, Eur. J. Oper. Res., 195, No. 3, 716–728, 2009.

[9] J. Brandão, A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem, Comput. Oper. Res., 38, No. 1, 140–151, 2011.

[10] J. Desrosiers, F. Soumis, M. Desrochers, and M. Sauvґe, Methods for routing with time windows, Eur. J. Oper. Res., 23, No. 2, 236–245, 1986.

[11] C. Duhamel, C. Gouinaud, P. Lacomme, and C. Prodhon, A multithread GRASPxELS for the heterogeneous capacitated vehicle routing problem, in El-G. Talbi, ed., Hybrid Metaheuristics, pp. 237–269, Springer, Heidelberg, 2013 (Stud. Comput. Intell., Vol. 434).

[12] C. Duhamel, P. Lacomme, and C. Prodhon, A GRASPxELS with depth first search split procedure for the HVRP, Res. Rep. LIMOS/RR-10-08, Inst. Supér. Inform., Modél. Appl., Aubière, France, 2010. Available at
http://www.isima.fr/˜lacomme/doc/RR_HVRP1-4_V1.pdf. Accessed Aug. 24, 2015.

[13] C. Duhamel, P. Lacomme, and C. Prodhon, Efficient frameworks for greedy split and new depth first search split procedures for routing problems, Comput. Oper. Res., 38, No. 4, 723–739, 2011.

[14] F. Li, B. Golden, and E. Wasil, A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem, Comput. Oper. Res., 34, No. 9, 2734–2742, 2007.

[15] P. H. V. Penna, A. Subramanian, and L. S. Ochi, An iterated local search heuristic for the heterogeneous fleet vehicle routing problem, J. Heuristics, 19, No. 2, 201–232, 2013.

[16] P. H. V. Penna, T. Vidal, L. S. Ochi, and C. Prins, New compound neighborhoods structures for the heterogeneous fixed fleet vehicle routing problem, Proc. XLV Simp. Bras. Pesqui. Operac., Natal, Brazil, Sept. 16–19, 2013, pp. 3623–3633, Soc. Bras. Pesqui. Oper., Rio de Janeiro, 2013. Available at http://ws2.din.uem.br/˜ademir/sbpo/sbpo2013/pdf/arq0110.pdf. Accessed Aug. 24, 2015.

[17] B. T. Poljak, Subgradient methods: A survey of Soviet research, in C. Lemarechal and R. Mifflin, eds., Nonsmooth Optimization, (Proc. IIASA Workshop, Laxenburg, Austria, Mar. 28 – Apr. 8, 1977), pp. 5–29, Pergamon Press, Oxford, GB, 1977 (IIASA Proc. Ser., Vol. 3).

[18] J.-Y. Potvin and M.-A. Naud, Tabu search with ejection chains for the vehicle routing problem with private fleet and common carrier, J. Oper. Res. Soc., 62, No. 2, 326–336, 2011.

[19] C. Prins, Eficient heuristics for the heterogeneous fleet multitrip VRP with application to a large-scale real case, J. Math. Model. Algorithms, 1, No. 2, 135–150, 2002.

[20] C. Prins, Two memetic algorithms for heterogeneous fleet vehicle routing problems, Eng. Appl. Artif. Intell., 22, No. 6, 916–928, 2009.

[21] A. Subramanian, P. H. V. Penna, E. Uchoa, and L. S. Ochi, A hybrid algorithm for the heterogenous fleet vehicle routing problem, Eur. J. Oper. Res., 221, No. 2, 285–295, 2012.

[22] E. D. Taillard, A heuristic column generation method for the heterogeneous fleet VRP, RAIRO, Oper. Res., 33, No. 1, 1–14, 1999.

[23] C. D. Tarantilis, C. T. Kiranoudis, and V. S. Vassiliadis, A list based threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem, J. Oper. Res. Soc., 54, No. 1, 65–71, 2003.

[24] C. D. Tarantilis, C. T. Kiranoudis, and V. S. Vassiliadis, A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem, Eur. J. Oper. Res., 152, No. 1, 148–158, 2004.

[25] C. D. Tarantilis, E. E. Zachariadis, and C. T. Kiranoudis, A guided tabu search for the heterogeneous vehicle routing problem, J. Oper. Res. Soc., 59, No. 12, 1659–1673, 2008.

[26] T. Vidal, T. G. Crainic, M. Gendreau, and C. Prins, A unified solution framework for multi-attribute vehicle routing problems, Eur. J. Oper. Res., 234, No. 3, 658–673, 2014.