Comparative analysis of granular neighborhoods in a Tabu Search for the vehicle routing problem with heterogeneous fleet and variable costs (HFVRP)

Main Article Content

Autores

John Wilmer Escobar http://orcid.org/0000-0001-6175-9553
Wilson Adarme-Jaimes http://orcid.org/0000-0001-7401-223X
Nicolás Clavijo-Buriticá http://orcid.org/0000-0001-5871-9390

Abstract

In the vehicle routing problem with heterogeneous fleet and variable costs (HFVRP), the group of routes to be developed to satisfy the demand of the customer must be determined, considering the minimization of the total costs of the travelled distance. Heuristic algorithms based on local searches use simple movements (neighborhoods) to generate feasible solutions to problems related to route design. In this article, we conduct a comparative analysis of granular neighborhoods in a Tabu Search for the HFVRP, in terms of the quality of the obtained solution. The computational experiments, performed on instances of benchmarking for the HFVRP, showed the efficiency and effectiveness of implementing some neighborhoods in metaheuristic algorithms of path, such as the Tabu Search.

Keywords:

Article Details

Licence

The journal authorizes the total or partial reproduction of the published article, as long as the source, including the name of the Journal, author(s), year, volume, issue, and pages are cited.

The ideas and assertions expressed by the authors are their solely responsibility and do not represent the views and opinions of the Journal or its editors.

All articles included in the Revista Facultad de Ingeniería are published under the Creative Commons (BY) license.

Authors must complete, sign, and submit the Review and Publication Authorization Form of the manuscript provided by the Journal; this form should contain all the originality and copyright information of the manuscript.

The authors  keep copyright, however, once the work in the Journal has been published, the authors must always allude to it.

The Journal allows and invites authors to publish their work in repositories or on their website after the presentation of the number in which the work is published with the aim of generating greater dissemination of the work.

References

J. Engblom, T. Solakivi, J. Töyli, and L. Ojala. Multiple-method analysis of logistics costs, 2012.

J. K. Lenstra, and A. H. G. Kan, “Complexity of vehicle routing and scheduling problems,” Networks, vol. 11 (2), pp. 221-227, 1981. DOI: http://doi.org/10.1002/net.3230110211.

D. E. Puenayán, J.C. Londoño, J. W. Escobar, and R. Linfati. “Un algoritmo basado en búsqueda tabú granular para la solución de un problema de ruteo de vehículos considerando flota heterogénea,” Revista Ingenierías Universidad de Medellín, vol. 13 (25), pp. 81-98, 2014.

P. Toth, and D. Vigo, “The granular tabu search and its application to the vehicle-routing problem,” Informs Journal on Computing, vol. 15 (4), pp. 333-346, 2003. DOI: http://doi.org/10.1287/ijoc.15.4.333.24890.

M. Schneider, and A. Stenger, Designing granular solution methods for routing problems with time windows. Technical Report Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL), 2015.

É. D. Taillard, “A heuristic column generation method for the heterogeneous fleet VRP. Revue française d'automatique, d'informatique et de recherche opérationnelle,” Recherche opérationnelle, vol. 33 (1), pp. 1-14, 1999.

B. Golden, A. Assad, L. Levy, and F. Gheysens, “The fleet size and mix vehicle routing problem,” Computers & Operations Research, vol. 11 (1), pp. 49-66, 1984. DOI: http://doi.org/10.1016/0305-0548(84)90007-8.

A. Subramanian, E. Uchoa, and L. S. Ochi, “A hybrid algorithm for a class of vehicle routing problems,” Computers & Operations Research, vol. 40 (10), pp. 2519-2531, 2013. DOI: http://doi.org/10.1016/j.cor.2013.01.013.

R. Baldacci, and A. Mingozzi, “A unified exact method for solving different classes of vehicle routing problems,” Mathematical Programming, vol. 120 (2), pp. 347-380, 2009. DOI: http://doi.org/10.1007/s10107-008-0218-9.

A. Subramanian, P. H. V. Penna, E. Uchoa, and L. S. Ochi, “A hybrid algorithm for the heterogeneous fleet vehicle routing problem,” European Journal of Operational Research, vol. 221 (2), pp. 285-295, 2012. DOI: http://doi.org/10.1016/j.ejor.2012.03.016.

A. Subramanian, E. Uchoa, and L. S. Ochi, “A hybrid algorithm for a class of vehicle routing problems,” Computers & Operations Research, vol. 40 (10), pp. 2519-2531, 2013. DOI: http://doi.org/10.1016/j.cor.2013.01.013.

J. Brandão, “A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem,” Computers & Operations Research, vol. 38 (1), pp.140-151, 2011. DOI: http://doi.org/10.1016/j.cor.2010.04.008.

J. Brandão, “A deterministic tabu search algorithm for the fleet size and mix vehicle routing problem,” European Journal of Operational Research, vol. 195 (3), pp. 716-728, 2009. DOI: http://doi.org/10.1016/j.ejor.2007.05.059.

H. Jia, Y. Li, B. Dong, and H. Ya, “An improved tabu search approach to vehicle routing problem,” Procedia-Social and Behavioral Sciences, vol. 96, pp.1208-1217, 2013. DOI: http://doi.org/10.1016/j.sbspro.2013.08.138.

L. S. Ochi, D. S. Vianna, L. M. Drummond, and A. O. Victor, “An evolutionary hybrid metaheuristic for solving the vehicle routing problem with heterogeneous fleet,” Genetic programming, Springer Berlin Heidelberg, pp. 187-195, 1998. DOI: http://doi.org/10.1007/BFb0055938.

L. S. Ochi, D. S. Vianna, L. M. Drummond, and A. O. Victor, “A parallel evolutionary algorithm for the vehicle routing problem with heterogeneous fleet,” Parallel and Distributed Processing, Springer Berlin Heidelberg, pp. 216-224, 1998. DOI: http://doi.org/10.1007/3-540-64359-1_691.

P. H. V. Penna, A. Subramanian, and L. S. Ochi, “An iterated local search heuristic for the heterogeneous fleet vehicle routing problem,” Journal of Heuristics, vol. 19 (2), pp.201-232, 2013. DOI: http://doi.org/10.1007/s10732-011-9186-y.

A. Imran, A. Salhi, and N. A. Wassan, “A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem,” European Journal of Operational Research, vol. 197(2), pp. 509-518, 2009. DOI: http://doi.org/10.1016/j.ejor.2008.07.022.

C. Prins, “Efficient heuristics for the heterogeneous fleet multitrip VRP with application to a large-scale real case,” Journal of Mathematical Modelling and Algorithms, vol. 1 (2), pp. 135-150, 2002. DOI: http://doi.org/10.1023/A:1016516326823.

X. Li, P. Tian, and Y. P. Aneja, “An adaptive memory programming metaheuristic for the heterogeneous fixed fleet vehicle routing problem,” Transportation Research Part E: Logistics and Transportation Review, vol. 46 (6), pp.1111-1127, 2010. DOI: http://doi.org/10.1016/j.tre.2010.02.004.

C. D. Tarantilis, C. T. Kiranoudis, and V. S. Vassiliadis, “A list based threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem” Journal of the Operational Research Society, vol. 54 (1), pp. 65-71, 2003. DOI: http://doi.org/10.1057/palgrave.jors.2601443.

F. Li, B. Golden, and E. Wasil, “A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem,” Computers & Operations Research, vol. 34 (9), pp.2734-2742, 2007. DOI: http://doi.org/10.1016/j.cor.2005.10.015.

J. W. Escobar, and R. Linfati, “Un algoritmo metaheurístico basado en recocido simulado con espacio de búsqueda granular para el problema de localización y ruteo con restricciones de capacidad,” Revista Ingenierías Universidad de Medellín, vol. 11 (21), pp. 139-150, 2012.

J. W. Escobar, R. Linfati, and P. Toth, “A two-phase hybrid heuristic algorithm for the capacitated location-routing problem,” Computers & Operations Research, vol. 40 (1), pp.70-79, 2013. DOI: http://doi.org/10.1016/j.cor.2012.05.008.

J. W. Escobar, R. Linfati, M. G. Baldoquin, and P. Toth, “A Granular Variable Tabu Neighborhood Search for the capacitated location-routing problem,” Transportation Research Part B, vol. 67 (C), pp. 344-356, 2014. DOI: http://doi.org/10.1016/j.trb.2014.05.014.

J. W. Escobar, R. Linfati, P. Toth, and M. G. Baldoquin, “A hybrid Granular Tabu Search algorithm for the Multi-Depot Vehicle Routing Problem,” Journal of Heuristics, vol. 20 (5), pp. 483-509, 2014. DOI: http://doi.org/10.1007/s10732-014-9247-0.

J. W. Escobar, “Heuristic Algorithms for the Capacitated Location-Routing Problem and the Multi-Depot Vehicle Routing Problem,” 4OR - A Quarterly Journal of Operations Research, vol. 12 (1), pp. 99-100, 2014.

R. Linfati, J. W. Escobar, and G. Gatica, “Un algoritmo metaheurístico para el problema de localización y ruteo con flota heterogénea,” Ingeniería y Ciencia, vol. 10 (19), pp.55-76, 2014. DOI: http://doi.org/10.17230/ingciencia.10.19.3.

R. Linfati, J. W. Escobar, and B. Cuevas, “An algorithm based on granular tabu search for the problem of balancing public bikes by using multiple vehicles,” Dyna, vol. 81 (186), pp.284-294, 2014. DOI: http://doi.org/10.15446/dyna.v81n186.45220.

J. W. Escobar, R. Linfati, and W. Adarme, “Un algoritmo metaheurístico híbrido para el problema de localización y ruteo con restricciones de capacidad,” Revista DYNA, vol. 82 (189), pp. 243-251, 2015.

S. Eilon, C. D. T. Watson-Gandy, and N. Christofides, Distribution management. London: Griffin, 1971.

N. Christofides, A. Mingozzi, and P. Toth, Loading problems. N. Christofides and al., editors, Combinatorial Optimization, pp. 339-369, 1979.

B. L. Golden, G. Laporte, and É. D. Taillard, “An adaptive memory heuristic for a class of vehicle routing problems with minmax objective,” Computers & Operations Research, vol. 24 (5), pp. 445-452, 1997. DOI: http://doi.org/10.1016/S0305-0548(96)00065-2.

J. Bernal J. W. Escobar, J. C. Paz, G. Gatica, and R. Linfati, “A probabilistic Granular Tabu Search for the Distance Constrained Capacitated Vehicle Routing Problem (DCVRP),” Journal of Industrial and Systems Engineering, pre-print.

J. Bernal, J. W. Escobar, C. Marin, R. Linfati, and G. Gatica, “A comparison of granular heuristic algorithms for the Location-Routing Problem with Heterogeneous Fleet (LRPH),” Dyna, vol. 84 (200), pp. 193-201, 2017. DOI: http://doi.org/10.15446/dyna.v84n200.55533.

Downloads

Download data is not yet available.