Geodesic
Hybrid local search for the heterogenous fixed fleet vehicle routing problem
Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 5, pp. 5-29.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2015_22_5_a0,
     author = {Yu. A. Kochetov and A. V. Khmelev},
     title = {Hybrid local search for the heterogenous fixed fleet vehicle routing problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--29},
     publisher = {mathdoc},
     volume = {22},
     number = {5},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2015_22_5_a0/}
}
TY  - JOUR
AU  - Yu. A. Kochetov
AU  - A. V. Khmelev
TI  - Hybrid local search for the heterogenous fixed fleet vehicle routing problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2015
SP  - 5
EP  - 29
VL  - 22
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2015_22_5_a0/
LA  - ru
ID  - DA_2015_22_5_a0
ER  - 
%0 Journal Article
%A Yu. A. Kochetov
%A A. V. Khmelev
%T Hybrid local search for the heterogenous fixed fleet vehicle routing problem
%J Diskretnyj analiz i issledovanie operacij
%D 2015
%P 5-29
%V 22
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2015_22_5_a0/
%G ru
%F DA_2015_22_5_a0
Yu. A. Kochetov; A. V. Khmelev. Hybrid local search for the heterogenous fixed fleet vehicle routing problem. Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 5, pp. 5-29. http://geodesic.mathdoc.fr/item/DA_2015_22_5_a0/

[1] I. A. Davydov, Yu. A. Kochetov, “VNS-based heuristic with an exponential neighborhood for the server load balancing problem”, Electron. Notes Discrete Math., 47 (2015), 53–60 | DOI | Zbl

[2] I. A. Davydov, Yu. A. Kochetov, N. Mladenović, D. Urošević, “Fast metaheuristics for the discrete $(r|p)$-centroid problem”, Autom. Remote Control, 75:4 (2014), 677–687 | DOI | MR | Zbl

[3] P. A. Kononova, Yu. A. Kochetov, “The variable neighborhood search for the two machine flow shop problem with a passive prefetch”, J. Appl. Ind. Math., 7:1 (2013), 54–67 | DOI | MR | Zbl

[4] P. I. Stetsyuk, Ellipsoid methods and $r$-algorithms, Evrika, Chisinau, 2014

[5] Baldacci R., Battarra M., Vigo D., “Routing a heterogeneous fleet of vehicles”, The vehicle routing problem: latest advances and new challenges, Oper. Res./Comput. Sci. Interfaces, 43, eds. B. Golden, S. Raghavan, E. Wasil, Springer-Verl., Nerw York, 2008, 3–27 | DOI | MR | Zbl

[6] Baldacci R., Mingozzi A., “A unified exact method for solving different classes of vehicle routing problems”, Math. Program. Ser. A, 120:2 (2009), 347–380 | DOI | MR | Zbl

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

[8] Brandão J., “A deterministic tabu search algorithm for the fleet size and mix vehicle routing problem”, Eur. J. Oper. Res., 195:3 (2009), 716–728 | DOI | Zbl

[9] Brandão J., “A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem”, Comput. Oper. Res., 38:1 (2011), 140–151 | DOI | MR | Zbl

[10] Desrosiers J., Soumis F., Desrochers M., Sauvé M., “Methods for routing with time windows”, Eur. J. Oper. Res., 23:2 (1986), 236–245 | DOI | MR | Zbl

[11] Duhamel C., Gouinaud C., Lacomme P., Prodhon C., “A multi-thread GRASPxELS for the heterogeneous capacitated vehicle routing problem”, Hybrid Metaheuristics, Stud. Comput. Intell., 434, ed. El-G. Talbi, Springer-Verl., Heidelberg, 2013, 237–269 | DOI

[12] Duhamel C., Lacomme P., Prodhon C., 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, Accessed Aug. 24, 2015 Available at http://www.isima.fr/~lacomme/doc/RR_HVRP1-4_V1.pdf

[13] Duhamel C., Lacomme P., Prodhon C., “Efficient frameworks for greedy split and new depth first search split procedures for routing problems”, Comput. Oper. Res., 38:4 (2011), 723–739 | DOI | MR | Zbl

[14] Li F., Golden B., Wasil E., “A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem”, Comput. Oper. Res., 34:9 (2007), 2734–2742 | DOI | Zbl

[15] Penna P. H. V., Subramanian A., Ochi L. S., “An iterated local search heuristic for the heterogeneous fleet vehicle routing problem”, J. Heuristics, 19:2 (2013), 201–232 | DOI | MR

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

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

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

[19] Prins C., “Efficient heuristics for the heterogeneous fleet multitrip VRP with application to a large-scale real case”, J. Math. Model. Algorithms, 1:2 (2002), 135–150 | DOI | MR | Zbl

[20] Prins C., “Two memetic algorithms for heterogeneous fleet vehicle routing problems”, Eng. Appl. Artif. Intell., 22:6 (2009), 916–928 | DOI

[21] Subramanian A., Penna P. H. V., Uchoa E., Ochi L. S., “A hybrid algorithm for the heterogenous fleet vehicle routing problem”, Eur. J. Oper. Res., 221:2 (2012), 285–295 | DOI | MR | Zbl

[22] Taillard E. D., “A heuristic column generation method for heterogeneous fleet VRP”, RAIRO, Oper. Res., 33:1 (1999), 1–14 | DOI | MR | Zbl

[23] Tarantilis C. D., Kiranoudis C. T., Vassiliadis V. S., “A list based threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem”, J. Oper. Res. Soc., 54:1 (2003), 65–71 | DOI | MR | Zbl

[24] Tarantilis C. D., Kiranoudis C. T., Vassiliadis V. S., “A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem”, Eur. J. Oper. Res., 152:1 (2004), 148–158 | DOI | MR | Zbl

[25] Tarantilis C. D., Zachariadis E. E., Kiranoudis C. T., “A guided tabu search for the heterogeneous vehicle routing problem”, J. Oper. Res. Soc., 59:2 (2008), 1659–1673 | DOI | Zbl

[26] Vidal T., Crainic T. G., Gendreau M., Prins C., “A unified solution framework for multi-attribute vehicle routing problems”, Eur. J. Oper. Res., 234:3 (2014), 658–673 | DOI | MR | Zbl