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

John Wilmer Escobar, Wilson Adarme-Jaimes, Nicolás Clavijo-Buriticá

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


Granular neighborhoods; Heterogeneous fleet; Tabu search; Vehicle routing problems

Full Text:

PDF

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.




DOI: https://doi.org/10.19053/01211129.v26.n46.2017.7321

Article Metrics

Abstract Views
97




Metrics Loading ...
_

Refbacks

  • There are currently no refbacks.




Copyright (c) 2017 Revista Facultad de Ingeniería

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

__________________________________________________________________________________________________________________

Revista Facultad de Ingeniería (Rev. Fac. Ing.) - ISSN: 0121-1129 - ISSN: 2357-5328 (Online)

Indexed and registered by: Emerging Sources Citation IndexSciELORedalycPublindex(Categoría A2)REDIBDOAJDialnetSHERPA/RoMEOLatindex.

__________________________________________________________________________________________________________________

__________________________________________________________________________________________________________________

Licencia de Creative Commons

This work is licensed under a Creative Commons Attribution 4.0 International

UNIVERSIDAD PEDAGÓGICA Y TECNOLÓGICA DE COLOMBIA
Sede Central Tunja–Boyacá–Colombia
Avenida Central del Norte 39-115
PBX: (57+8) 7405626
portalweb@uptc.edu.co Comentarios de este sitio
Horario de atención y servicio telefónico
8:00 a.m. a 12:00 m y 2:00 p.m a 6:00 p.m.

Atención al Ciudadano
Línea Gratuita: 01 8000 942024
Tel: (57+8) 7428263
quejas.reclamos@uptc.edu.co
Notificaciones Judiciales
Notificaciones de aviso

Institución de Educación Superior sujeta a inspección y vigilancia por el Ministerio de Educación Nacional
Sistema OJS - Metabiblioteca |