Comparative analysis of granular neighborhoods in a Tabu Search for the vehicle routing problem with heterogeneous fleet and variable costs (HFVRP)
Article Sidebar
PDF
FLIP
XML
Section: PAPERS
How to Cite
Escobar, J., Adarme-Jaimes, W., & Clavijo-Buriticá, N. (2017). Comparative analysis of granular neighborhoods in a Tabu Search for the vehicle routing problem with heterogeneous fleet and variable costs (HFVRP). Revista Facultad De Ingeniería, 26(46), 93-104. https://doi.org/10.19053/01211129.v26.n46.2017.7321
More Citation Formats
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.
Article Details
Licence
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 who publish in this Journal accept the following conditions:
a. The authors retain the copyright and transfer the right of the first publication to the journal, with the work registered under the Creative Commons attribution license, which allows third parties to use what is published as long as they mention the authorship of the work and the first publication in this Journal.
b. Authors can make other independent and additional contractual agreements for the non-exclusive distribution of the version of the article published in this journal (eg, include it in an institutional repository or publish it in a book) provided they clearly indicate that the work It was first published in this Journal.
c. Authors are allowed and recommended to publish their work on the Internet (for example on institutional or personal pages) before and during the process.
review and publication, as it can lead to productive exchanges and a greater and faster dissemination of published work.
d. The Journal authorizes the total or partial reproduction of the content of the publication, as long as the source is cited, that is, the name of the Journal, name of the author (s), year, volume, publication number and pages of the article.
e. The ideas and statements issued by the authors are their responsibility and in no case bind the Journal.
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.
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.
