Show simple item record

Desarrollo de un algoritmo de optimización basado en búsqueda local guiada para el problema de minimización en la huella de carbono en el ruteo de vehículos heterogéneos

dc.rights.licenseAtribución-NoComercial 4.0 Internacional
dc.contributor.advisorBula, Gustavo
dc.contributor.authorFerrer, Daniel
dc.date.accessioned2023-11-02T18:56:46Z
dc.date.available2023-11-02T18:56:46Z
dc.date.issued2023
dc.identifier.urihttps://repositorio.unal.edu.co/handle/unal/84862
dc.descriptionilustraciones, diagramas
dc.description.abstractEl objetivo de este trabajo es la construcción de un algoritmo basado en búsqueda local guiada para la minimización de las emisiones equivalentes de CO2 a través de la minimización del consumo de combustible para una flota de vehículos heterogénea. Para lograr este objetivo se construye un conjunto de métricas o características que permitan distinguir entre soluciones “óptimas” de aquellas no optimas. Considerando diferentes valores de parámetros, se crean diversas instancias para las soluciones “optimas” y aquellas que no lo son. Luego, por medio de un árbol de decisiones se obtiene la caracterización de las métricas que reflejan la diferencia entre las soluciones. Posteriormente se analiza el impacto de un grupo definido de operadores de búsqueda local en la mejora de las métricas de las soluciones, de acuerdo con la caracterización hecha por el árbol de decisiones y se propone una versión de algoritmo búsqueda local guiado por la ordenada secuencia de los operadores que mejores resultados obtuvieron en la caracterización de esas métricas. Por último, se evalúa las soluciones entregadas por estos algoritmos respecto a otras soluciones. (Texto tomado de la fuente)
dc.description.abstractThe objective of this work is the construction of an algorithm based on guided local search for the minimization of CO2 equivalent emissions through the minimization of fuel consumption for a heterogeneous fleet of vehicles. To achieve this goal, a set of metrics or features is constructed to distinguish between "optimal" solutions and non-optimal ones. Considering different parameter values, several instances are created for "optimal" and non-optimal solutions. Then, by means of a decision tree, the characterization of the metrics that reflect the difference between the solutions is obtained. Subsequently, the impact of a defined group of local search operators on the improvement of the metrics of the solutions is analyzed, according to the characterization made by the decision tree, and a version of the local search algorithm is proposed, guided by the ordered sequence of the operators that obtained the best results in the characterization of those metrics. Finally, the solutions provided by these algorithms are evaluated with respect to other solutions.
dc.format.extent98 páginas
dc.format.mimetypeapplication/pdf
dc.language.isospa
dc.publisherUniversidad Nacional de Colombia
dc.rights.urihttp://creativecommons.org/licenses/by-nc/4.0/
dc.subject.ddc000 - Ciencias de la computación, información y obras generales
dc.titleDesarrollo de un algoritmo de optimización basado en búsqueda local guiada para el problema de minimización en la huella de carbono en el ruteo de vehículos heterogéneos
dc.typeTrabajo de grado - Maestría
dc.type.driverinfo:eu-repo/semantics/masterThesis
dc.type.versioninfo:eu-repo/semantics/acceptedVersion
dc.publisher.programBogotá - Ingeniería - Maestría en Ingeniería - Ingeniería Industrial
dc.description.notesContiene tablas e ilustraciones de los datos
dc.description.degreelevelMaestría
dc.description.degreenameMagíster en Ingeniería - Ingeniería Industrial
dc.description.methodsMetodología de carácter cuantitativo. La metodología para dar cumplimiento a los objetivos se establece a través de fases mostradas a continuación: Fases A. Entendimiento y formulación del problema: [A 1.1., A 1.2. y A.1.3, A.1.4] Presenta los conceptos de huella ambiental y de ruteo de vehículos para flotas heterogéneas. Discute los diferentes enfoques para el uso de la huella ambiental, analiza y discute sobre una selección de literatura alrededor de las mejores maneras de estimar la huella ambiental, se diseña el modelo matemático que integra las restricciones, la demanda y las estimaciones de la huella ambiental para los vehículos heterogéneos, se discute y analiza la importancia de estos modelos para la sostenibilidad en la logística. B. Propuesta a la solución al problema: [A 1.5., A 2.1. y A.2.2] Se hace un recorrido sobre las metaheurísticas que se han trabajado hasta ahora abordando el problema de minimización de la huella ambiental y de la guía inteligente para los problemas de ruteo de vehículos, se analizan como se han solucionado estos problemas y se integran los conceptos para generar una nueva propuesta de solución a este problema. C. Diseño del método guía: [A 3.1., A 3.2. y A 3.3 A 3.4 A.3.5] Analiza y presenta los modelos de machine learning que se han empleado en la actualidad para entregar caracterizaciones de variables, la manera en que se han caracterizado y los métodos para definir qué modelo es el mejor, definir que variables se van a usar para predecir el modelo, evaluar los resultados y generar las características de este modelo. D. Diseño del algoritmo: [A 4.1., A 4.2. y A 4.3 A 4.4 A.5.1 A5.2 A.5.3] Se estudian la manera en que se han trabajado los algoritmos de búsqueda local guiada, se construyen los modelos de guía y penalización, se generan las métricas con las que se va a analizar la solución al problema, se proponen las meta- heurísticas y los operadores con los que se va a trabajar el algoritmo, se diseña el algoritmo de acuerdo con la validación previa, se evalúa el modelo y se analizan los indicadores para entender si cumple con la minimización de la huella ambiental, así como su eficiencia en tiempo y memoria, se analizan los resultados y se divulgan.
dc.description.researchareaGestión de Operaciones
dc.identifier.instnameUniversidad Nacional de Colombia
dc.identifier.reponameRepositorio Institucional Universidad Nacional de Colombia
dc.identifier.repourlhttps://repositorio.unal.edu.co/
dc.publisher.facultyFacultad de Ingeniería
dc.publisher.placeBogotá, Colombia
dc.publisher.branchUniversidad Nacional de Colombia - Sede Bogotá
dc.relation.referencesAlpaydin, E. (2014). Introduction to Machine Learning Second Edition. In Methods in molecular biology (Clifton, N.J.) (Vol. 1107). http://www.ncbi.nlm.nih.gov/pubmed/24272434
dc.relation.referencesArnold, F., & Gendreau, M. (2017). Efficiently Solving Very Large Scale Routing Problems Efficiently Solving Very Large Scale Routing Problems. CIRRELT-2017-75.
dc.relation.referencesArnold, F., Gendreau, M., & Sörensen, K. (2019). Efficiently solving very large-scale routing problems. Computers and Operations Research, 107, 32–42. https://doi.org/10.1016/j.cor.2019.03.006
dc.relation.referencesArnold, F., & Sörensen, K. (2019). What makes a VRP solution good? The generation of problem-specific knowledge for heuristics. Computers and Operations Research, 106, 280–288. https://doi.org/10.1016/j.cor.2018.02.007
dc.relation.referencesAstarita, C. (2013). El Gran Juego de las Tierras Raras. Journal of Chemical Information and Modeling, 53(9), 1689–1699. https://doi.org/10.1017/CBO9781107415324.004
dc.relation.referencesBaldacci, R., Battarra, M., & Vigo, D. (2008a). Routing a heterogeneous fleet of vehicles. In Operations Research/ Computer Science Interfaces Series (Vol. 43, pp. 3–27). https://doi.org/10.1007/978-0-387-77778-8_1
dc.relation.referencesBaldacci, R., Battarra, M., & Vigo, D. (2008b). The Vehicle Routing Problem: Latest Advances and New Challenges. In Operations Research/ Computer Science Interfaces Series (Vol. 43).
dc.relation.referencesBautista-Valhondo, J. (2003). Adaptación de la heurística LIN-KERNINGHAM para la resolución de problemas de diseño de itinerarios : Secuenciación de unidades con restricciones múltiples View project. October. https://doi.org/10.13140/RG.2.2.17660.33929
dc.relation.referencesBektaş, T., & Laporte, G. (2011). The Pollution-Routing Problem. Transportation Research Part B: Methodological, 45(8), 1232–1250. https://doi.org/10.1016/j.trb.2011.02.004
dc.relation.referencesBlum, C. (2003). Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison Metaheuristics in Combinatorial Optimization. In ACM Computing Surveys (Vol. 35, Issue 3).
dc.relation.referencesClimatico, G. I. de E. sobre el C. (2019). Maintaining Humanity’s Life Support Systems in the 21st Century Scientific Consensus on. http://consensusforaction.stanford.edu/see-scientific-consensus/consensus_english.pdf
dc.relation.referencesCorzo, J. A. (2019). Análisis Multivariado Aplicado con aplicaciones en R Notas de clase
dc.relation.referencesDaza, J. M., Montoya, J. R., & Narducci, F. (2010). RESOLUCIÓN DEL PROBLEMA DE ENRUTAMIENTO DE VEHÍCULOS CON LIMITACIONES DE CAPACIDAD UTILIZANDO UN PROCEDIMIENTO METAHEURÍSTICO DE DOS FASES.
dc.relation.referencesEshtehadi, R., Fathian, M., & Demir, E. (2017). Robust solutions to the pollution-routing problem with demand and travel time uncertainty. Transportation Research Part D: Transport and Environment, 51, 351–363. https://doi.org/10.1016/j.trd.2017.01.003
dc.relation.referencesFeng, Y., Zhang, R. Q., & Jia, G. (2017). Vehicle Routing Problems with Fuel Consumption and Stochastic Travel Speeds. Mathematical Problems in Engineering, 2017. https://doi.org/10.1155/2017/6329203
dc.relation.referencesFigliozzi, M. (2010). Vehicle routing problem for emissions minimization. Transportation Research Record, 2197, 1–7. https://doi.org/10.3141/2197-01
dc.relation.referencesFisher, M. (1995). Vehicle routing. Handbooks in Operations Research and Management Science, 8(C), 1–33. https://doi.org/10.1016/S0927-0507(05)80105-7
dc.relation.referencesGe, Z., Song, Z., Ding, S. X., & Huang, B. (2017). Data Mining and Analytics in the Process Industry: The Role of Machine Learning. IEEE Access, 5, 20590–20616. https://doi.org/10.1109/ACCESS.2017.2756872
dc.relation.referencesGendreau, M., & Potvin, J.-Y. (2010). Variable Nneighborhood search (chapter). Handbook of Metaheuristics, 146(September 2010), 648. https://doi.org/10.1007/978-1-4419-1665-5
dc.relation.referencesHa, S. H. (2010). Behavioral assessment of recoverable credit of retailer’s customers. Information Sciences, 180(19), 3703–3717. https://doi.org/10.1016/j.ins.2010.06.012
dc.relation.referencesHansen, P., Mladenovic, N., Andrés Moreno Pérez, J., Sánchez, F., & Cruz de Tenerife, S. (2003). Variable Neighbourhood Search. Revista Iberoamericana de Inteligencia Artificial. No, 19, 77–92. http://www.aepia.org/revista
dc.relation.referencesHillier, F. S., & Lieberman, G. J. (2010). Introducción a la Investigación de Operaciones (M. G. Hill (ed.); Novena Edi).
dc.relation.referencesHines, W. W., & Montgomery, D. C. (1993). Probabilidad y estadística para ingeniería y administración. In Applied Statistics (Vol. 22, Issue 1).
dc.relation.referencesHuang, B., Thorne, P. W., Banzon, V. F., Boyer, T., Chepurin, G., Lawrimore, J. H., Menne, M. J., Smith, T. M., Vose, R. S., & Zhang, H. M. (2017). Extended reconstructed Sea surface temperature, Version 5 (ERSSTv5): Upgrades, validations, and intercomparisons. Journal of Climate, 30(20), 8179–8205. https://doi.org/10.1175/JCLI-D-16-0836.1
dc.relation.referencesHuemer, M. (2011). Heuristics for the vehicle routing problem with multiple deliverymen. August.
dc.relation.referencesIrnich, S., Toth, P., & Vigo, D. (2014). Chapter 1: The Family of Vehicle Routing Problems. In Vehicle Routing (pp. 1–33). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611973594.ch1
dc.relation.referencesKoç, Ç., Bektaş, T., Jabali, O., & Laporte, G. (2016). Thirty years of heterogeneous vehicle routing. In European Journal of Operational Research (Vol. 249, Issue 1, pp. 1–21). Elsevier. https://doi.org/10.1016/j.ejor.2015.07.020
dc.relation.referencesKramer, R., Subramanian, A., Vidal, T., & Cabral, L. D. A. F. (2015). A matheuristic approach for the Pollution-Routing Problem. European Journal of Operational Research, 243(2), 523–539. https://doi.org/10.1016/j.ejor.2014.12.009
dc.relation.referencesLarose, D. T., & Larose, C. D. (2014). Discovering Knowledge in Data. In Discovering Knowledge in Data. https://doi.org/10.1002/9781118874059
dc.relation.referencesLeung, S. C. H., Zheng, J., Zhang, D., & Zhou, X. (2010). Simulated annealing for the vehicle routing problem with two-dimensional loading constraints. Flexible Services and Manufacturing Journal, 22(1–2), 61–82. https://doi.org/10.1007/s10696-010-9061-4
dc.relation.referencesLi, X. Y., Tian, P., & Leung, S. C. H. (2009). An ant colony optimization metaheuristic hybridized with tabu search for open vehicle routing problems. Journal of the Operational Research Society, 60(7), 1012–1025. https://doi.org/10.1057/palgrave.jors.2602644
dc.relation.referencesLucas, F., Billot, R., & Sevaux, M. (2019). A comment on “What makes a VRP solution good? The generation of problem-specific knowledge for heuristics.” Computers and Operations Research, 110, 130–134. https://doi.org/10.1016/j.cor.2019.05.025
dc.relation.referencesMedina, L. B. R., Rotta, E. C. G. La, & Castro, J. A. O. (2011). Una Revisión al Estado del Arte del Problema de Ruteo de Vehículos: Evolución Histórica Y Métodos De Solución. Ingeniería, 16(2), 35–55. http://revistas.udistrital.edu.co/ojs/index.php/reving/article/view/3832
dc.relation.referencesMolina, J. C. (2012). Problema VRP con flota heterogénea.
dc.relation.referencesMuñoz-Villamizar, Montoya-Torres, & Caceres Cruz, J. (2020). A SIMULATION-BASED ALGORITHM FOR THE INTEGRATED LOCATION AND ROUTING PROBLEM IN URBAN LOGISTICS. Suparyanto Dan Rosad (2015, 5(3), 248–253.
dc.relation.referencesNikfarjam, A., Moosavi, A., Rezaei, N., & Ebrahimnejad, S. (2019). A green vehicle routing problem with time windows considering the heterogeneous fleet of vehicles: two metaheuristic algorithms. European J. of Industrial Engineering, 13(4), 507. https://doi.org/10.1504/ejie.2019.10022249
dc.relation.referencesOlivera, A. (2004). Heurísticas para Problemas de Ruteo de Vehículos.
dc.relation.referencesOlson, R. S., & Moore, J. H. (2016). Olson Moore - TPOT A Tree-based Pipeline Optimization Tool for .pdf. 163–173.
dc.relation.referencesPessoa, A., Sadykov, R., & Uchoa, E. (2018). Enhanced Branch-Cut-and-Price algorithm for heterogeneous fleet vehicle routing problems. European Journal of Operational Research, 270(2), 530–543. https://doi.org/10.1016/j.ejor.2018.04.009
dc.relation.referencesPosada, J., & González, C. (2013). Fuel Consumption in Vehicles for Highway Transportation - Predictive Models. Revista Ingenierías Universidad de Medellín, 12(23), 35–46. http://www.scielo.org.co/scielo.php?script=sci_arttext&pid=S1692-33242013000200004&lng=en&nrm=iso&tlng=es
dc.relation.referencesRezgui, D., Chaouachi Siala, J., Aggoune-Mtalaa, W., & Bouziri, H. (2019). Application of a variable neighborhood search algorithm to a fleet size and mix vehicle routing problem with electric modular vehicles. Computers and Industrial Engineering, 130(January 2018), 537–550. https://doi.org/10.1016/j.cie.2019.03.001
dc.relation.referencesRopke, S., & Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40(4), 455–472. https://doi.org/10.1287/trsc.1050.0135
dc.relation.referencesSörensen, K., Sevaux, M., & Glover, F. (2018). A history of metaheuristics. Handbook of Heuristics, 2–2(January), 791–808. https://doi.org/10.1007/978-3-319-07124-4_4
dc.relation.referencesSuarez-Chilma, V. F., Sarache, W. A., & Costa, Y. J. (2018). Una Solución al Enrutamiento de Vehículos en Ciudades Montañosas Considerando Aspectos Ambientales y Económicos. Información Tecnológica, 29(3), 3–14. https://doi.org/10.4067/s0718-07642018000300003
dc.relation.referencesSuzuki, Y. (2011). A new truck-routing approach for reducing fuel consumption and pollutants emission. Transportation Research Part D: Transport and Environment, 16(1), 73–77. https://doi.org/10.1016/j.trd.2010.08.003
dc.relation.referencesTAHA, H. A. (2012). Investigación de Operaciones.
dc.relation.referencesToth, P., & Vigo, D. (2002). 1. An Overview of Vehicle Routing Problems. In The Vehicle Routing Problem (pp. 1–26). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9780898718515.ch1
dc.relation.referencesTrujillano, J., Sarria, A., Esquerda, A., Mariona, B., Matilde, P., & Jaume, M. (2008). Aproximación a la metodología basada en árboles de decisión (CART). Mortalidad hospitalaria del infarto agudo de miocardio. Gaceta Sanitaria, 22(SUPPL. 1), 65–70. https://doi.org/10.1157/13115113
dc.relation.referencesVoudouris, C., Tsang, E. P. K., & Alsheddy, A. (2003). Guided Local Search. https://doi.org/10.1007/978-1-4419-1665-5
dc.relation.referencesWang, S., Lu, Z., Wei, L., Ji, G., & Yang, J. (2016). Fitness-scaling adaptive genetic algorithm with local search for solving the Multiple Depot Vehicle Routing Problem. SIMULATION, 92(7), 601–616. https://doi.org/10.1177/0037549715603481
dc.relation.referencesWolsey, L. A. (2008). Mixed Integer Programming. Wiley Encyclopedia of Computer Science and Engineering, 1, 1–10. https://doi.org/10.1002/9780470050118.ecse244
dc.relation.referencesWu, X., Kumar, V., Ross, Q. J., Ghosh, J., Yang, Q., Motoda, H., McLachlan, G. J., Ng, A., Liu, B., Yu, P. S., Zhou, Z. H., Steinbach, M., Hand, D. J., & Steinberg, D. (2008). Top 10 algorithms in data mining. In Knowledge and Information Systems (Vol. 14, Issue 1). https://doi.org/10.1007/s10115-007-0114-2
dc.rights.accessrightsinfo:eu-repo/semantics/openAccess
dc.subject.lembContaminación del aire
dc.subject.lembAir - Pollution
dc.subject.proposalMetaheurísticas
dc.subject.proposalProblema de ruteo de vehículos con flota heterogénea
dc.subject.proposalBúsqueda local guiada
dc.subject.proposalBúsqueda local
dc.subject.proposalAprendizaje de máquina
dc.subject.proposalMetaheuristics
dc.subject.proposalFleet size and mix vehicle routing problem
dc.subject.proposalGuided local search
dc.subject.proposalLocal search
dc.subject.proposalMachine learning
dc.title.translatedDevelopment of an optimization algorithm based on guided local search for the carbon footprint minimization problem in heterogeneous vehicle routing
dc.type.coarhttp://purl.org/coar/resource_type/c_bdcc
dc.type.coarversionhttp://purl.org/coar/version/c_ab4af688f83e57aa
dc.type.contentText
dc.type.redcolhttp://purl.org/redcol/resource_type/TM
oaire.accessrightshttp://purl.org/coar/access_right/c_abf2


Files in this item

Thumbnail
Name:
1152434863.2023.pdf
Size:
1.788Mb
Format:
PDF
Description:
Tesis de Maestría en Ingeniería ...
Download

This item appears in the following Collection(s)

Show simple item record

Atribución-NoComercial 4.0 InternacionalThis work is licensed under a Creative Commons Reconocimiento-NoComercial 4.0.This document has been deposited by the author (s) under the following certificate of deposit