Mostrar el registro sencillo del ítem
Ruteo de vehículos VRPTWPD para información de valor mediante el uso de algoritmos genéticos
| dc.contributor.advisor | Parra Herrera, Jairo Enrique | |
| dc.contributor.author | Gómez Veloza, David Yoan | |
| dc.date.accessioned | 2022-08-11T20:00:25Z | |
| dc.date.available | 2022-08-11T20:00:25Z | |
| dc.date.issued | 2022-08-08 | |
| dc.identifier.uri | http://hdl.handle.net/10823/6599 | |
| dc.description.abstract | Este trabajo de investigación se centra en Proponer una solución para el ruteo de vehículos VRPTWDP para el transporte de información de valor mediante el uso de algoritmos genéticos. Para el desarrollo se aborda usando un enfoque cuantitativo y alcance descriptivo, integrando un diseño experimental en donde se desarrolla iniciando desde el planteamiento del problema, revisión de la literatura, alcance de la investigación, desarrollo, recolección y análisis de datos. Bajo estas consideraciones se toma como soluciones padres la solución propuesta con la herramienta de Excel “vrp_spreadsheet_solver_v3.72” del profesor Günes Erdogan, las cuales se integran al algoritmo genético propuesto para la solución de un problema VRPTWDP. Como resultado se genera el análisis de soluciones factibles que cumplen con condiciones del problema de estudio. | spa |
| dc.description.tableofcontents | INTRODUCCIÓN . 7 1. CAPÍTULO 1: CARACTERÍSTICAS Y PLANTEAMIENTO DEL PROBLEMA . 10 1.1 Formulación del Problema . 15 1.2 Delimitación del Problema . 15 1.3 Objetivos . 16 1.3.1 Objetivo General. 16 1.3.2 Objetivos Específicos . 16 2. CAPÍTULO 2: MARCO DE REFERENCIA . 17 2.1 Problema de Ruteo de Vehículos . 19 2.2 Variantes del VRP . 21 2.2.1 Problemas con Restricciones de Capacidad (CVRP) . 21 2.2.2 Problema con Múltiples Depósitos (MDVRP) . 22 2.2.3 Problemas con Entregas y Devoluciones (VRPPD) . 23 2.2.4 Problemas con Ventanas de Tiempo (VRPTW) . 24 2.3 Métodos para Abordar el Problema . 31 2.4 Métodos Exactos . 31 2.4.1 Programación Lineal Entera . 32 2.4.2 Algoritmo de Ramificación y Acotamiento (Branch & Bound) . 32 2.4.3 Algoritmo de Ramificación y Corte (Branch & Cut) . 32 2.4.4 Técnicas de Relajación . 33 2.5 Métodos Heurísticos . 33 2.5.1 Heurísticas Constructivas . 34 2.5.2 Heurística del Vecino más Cercano . 35 2.5.3 Heurística de Dos Fases . 35 2.5.4 Método de Rutear Primero y Asignar Después . 35 2.5.5 Método de Asignar Primero y Rutear Después . 36 2.5.6 Algoritmo de Barrido . 36 2.5.7 Heurística de Pétalos . 37 2.5.8 Heurística de Mejora . 37 2.6 Métodos Metaheurísticos . 38 2.6.1 Algoritmos Genéticos . 38 2.6.2 Recocido Simulado . 40 2.6.3 Redes Neuronales . 40 2.6.4 Búsqueda Tabú . 41 2.6.5 Algoritmo Colonia de Hormigas . 41 2.6.6 Algoritmo colonia de hormigas en el VRPTW . 43 3. CAPÍTULO 3: METODOLOGÍA . 48 3.1 Diseño de la investigación . 48 3.2 Población de Estudio . 49 3.3 Muestra y Muestreo . 50 3.4 Técnicas e instrumentos de recolección de datos . 51 3.5 Técnicas de análisis de datos . 51 3.6 Procedimiento para el Desarrollo . 52 CAPÍTULO 4: SOLUCIÓN CASO VRPTW . 53 4.1 Descripción de la Operación . 53 4.2 Definición del modelo VRPTW . 55 4.3 Selección de Método de Solución Algoritmo Genético . 58 4.4 Análisis Estadístico de Datos Históricos . 64 4.5 Generación de Rutas Iniciales Herramienta “VRP en Excel” . 68 4.6 Resultados Iniciales Utilizando Archivo “vrp_spreadsheet_solver_v3.72” . 71 4.7 Procedimiento para Generación de Población Inicial en AG . 73 4.8 Selección de individuos en AG . 76 4.9 Función de adaptación para AG . 79 4.10 Técnica de cruza para AG Order Crossover (OX) . 81 4.11 Técnica de Mutación por Intercambio Reciproco en AG . 84 4.12 Reparación de individuos . 86 5. RESULTADOS ..89 6. CONCLUSIONES . 7. RECOMENDACIONES Y TRABAJOS FUTUROS . 98 8. REFERENCIAS BIBLIOGRÁFICAS . 99 9. ANEXOS . 103 | |
| dc.format.mimetype | application/pdf | spa |
| dc.language.iso | spa | spa |
| dc.title | Ruteo de vehículos VRPTWPD para información de valor mediante el uso de algoritmos genéticos | spa |
| dc.type.local | Tesis/Trabajo de grado - Monografía - Especialización | spa |
| dc.type.driver | info:eu-repo/semantics/bachelorThesis | spa |
| dc.title.translated | Routing of VRPTWPD vehicles for valuable information through the use of genetic algorithms | spa |
| dc.subject.proposal | VRP with time windows | spa |
| dc.subject.proposal | Algoritmos genéticos | spa |
| dc.subject.proposal | Problemas combinatorios | spa |
| dc.subject.proposal | Problema de ruteo de vehículos | spa |
| dc.subject.proposal | Ultima milla | spa |
| dc.subject.proposal | VRP con ventanas de tiempo | spa |
| dc.subject.lemb | Información-Sistemas | |
| dc.subject.lemb | Industria | |
| dc.subject.lemb | Transportes | |
| dc.description.abstractenglish | This research work is focused on proposing a solution for VRPTWDP vehicle routing for the transport of valuable information through the use of genetic algorithms. The development is approached using a quantitative approach and descriptive scope, integrating an experimental design where it is developed starting from the problem statement, literature review, research scope, development, data collection and analysis. Under these considerations, the solution proposed with the Excel tool "vrp_spreadsheet_solver_v3.72" of Professor Günes Erdogan is taken as parent solutions, which are integrated to the genetic algorithm proposed for the solution of a VRPTWDP problem. As a result, the analysis of feasible solutions that satisfy the conditions of the study problem is generated. | spa |
| dc.subject.keywords | Genetic algorithms | spa |
| dc.subject.keywords | Combinatorial problems | spa |
| dc.subject.keywords | Vehicle routing problem | spa |
| dc.subject.keywords | Last Mille | spa |
| dc.relation.references | Alvez, D., Chalupa, J. P., & Correa, D. (2019). Problema de Ruteo con Multiples Ventanas de Tiempo para la Recolección de Leche (Tesis de Pregrado). Montevideo. | spa |
| dc.relation.references | Arévalo Alarcón, C., & Rojas Romero, R. A. (2019). Modelo de Ruteo de Vehículos para Diminuir Emisión de Material Particulado Generado por Transporte de Carga: Empresa del Sector Retail en Bogotá (Tesis de Pregrado). Universidad de la Salle, Bogotá D,C. | spa |
| dc.relation.references | Augerat, P., Belenguer b, J., Benavent, E., Corberin, A., & Naddef, D. (1998). Separating Capacity Constraints in the CVRP Using Tabu Search. European Journal of Operational Research, 106, 547-557. | spa |
| dc.relation.references | Bakker, S., Wang, A., & Gounaris, C. (2021). Vehicle Routing With Endogenous Learning: Application to Offshore. European Journal of Operational Research, 289, 93-106. | spa |
| dc.relation.references | Cañada, A. (2014). Diseño de Itinerarios para el Reparto de Gases Embotellados Mediante una Flota Heterogenea de Camiones. | spa |
| dc.relation.references | Castañeda Jimenez, J., & Cardona Arias, J. A. (2014). Implementación del Modelo de Ahorro para Resolver el VRP Aplicado al Diseño de una Red de Logistica Inversa para la Recolección de Aceite Vehícular Usado Generado en los Puntos de Acopio Ubicado en Pereia (Tesis de Pregrado). Universidad Tecnológica de Pereira, Pereira. | spa |
| dc.relation.references | Chiang, W.-C., & Russell , R. (1996). Simulated Annealing Metaheuristics for the Vehicle Routing Problem With Time Windows. Annals of Operations Research, 63, 3-27. | spa |
| dc.relation.references | Coello Coello, C. A. (2020). Introduccion a la Computación Evolutiva. México: Investav AV. | spa |
| dc.relation.references | Cordone, R. (2001). A Heuristic for the Vehícle Routing Problem With Time Windows. Kluwer Academic Publishers, 7, 107-129. | spa |
| dc.relation.references | Denisova, A., Alekseytsev, D., Meshcheryakov, V., & Denisov, O. (2021). Optimization of the Control System Parameters Using the Genetic Algorithm. Journal of Physics: Conference Series, 01095, 1742-1791. | spa |
| dc.relation.references | Donati, A., Montemanni, N. C., Rizzoli, A., & Gambardella, L. (2008). Time Dependent Vehicle Routing Problem. European Journal of Operational Research, 185, 1174-1191. | spa |
| dc.relation.references | Dr. P. V. Ingole, & Mr. Mangesh K Nichat . (2013). Landmark Based Shortest Path Detection by Using Dijkestra. International Journal of Engineering Research and Applications (IJERA), 3, 162-165. | spa |
| dc.relation.references | Eksioglu, B., Bural, A., & Reisman, A. (2009). The Vehicle Routing Problem: A Taxonomic Review. Computers & Industrial EngineerinG, 57, 1472-1483. | spa |
| dc.relation.references | El-Sherbeny, N. (2010). Vehicle Routing With Time Windows: An Overview. Journal of King Saud University, 22, 123-131. | spa |
| dc.relation.references | Gómez Veloza, D. Y., & Gonzalez Restrepo, D. A. (2019). Solución al Problema de Ruteo de Vehículos con Entregas y Recogidas Aplicando el Algoritmo de Petalos y el Algoritmo del Vecino más Cercano (Tesis de Pregrado). Universidad Distrital Francisco Jose de Caldas, Bogotá D,C. | spa |
| dc.relation.references | Guasmayan Guasmayan, F. A. (2014). Solución del Problema de Rueteo de Vehículos Dependientes del Tiempo Utilizandoun Algoritmo Genetico Modificado (Tesis de Maestria). Universidad Tecnológica de Pereria, Pereira. | spa |
| dc.relation.references | Hashimotoa, H., Mutsunori, Y., & Toshihide, I. (2008). An Iterated Local Search Algorithm For The Time-Dependent Vehicle. Discrete Optimization, 5, 434-456. | spa |
| dc.relation.references | Henández Sampieri, R. (2014). Metodología de la investigación. (6, Ed.) México D.F: McGrawhill. | spa |
| dc.relation.references | Hernan Restrepo, J., Medina, P. D., & Arturo Cruz, E. (2008). A Logistic Case of Programming Vehicle Routing Problem With The Time Windows. Scientia et Technica, 39, 0122-1701. | spa |
| dc.relation.references | Hiniestroza Marquinez, C. A. (2019). Modelo de Ruteo para la Recolección de Tapas Plasticas Apoyo a la Labrol Sosicla de la Fundación Carlos Portela (Tesis de Pregrado). Escuela de Ingenieria Informatica, Santiago de Cali. | spa |
| dc.relation.references | Homberger, J., & Gehring, H. (2005). A Two-Phase Hybrid Metaheuristic For The Vehicle Routing Problem With Time Windows. European Journal of Operational Research, 162, 220-238. | spa |
| dc.relation.references | Joerss, M., Jürgen, S., Neuhaus, F., Klink, C., & Mann, F. (2016). Parcel Delivery The Future of Last Mile: Travel, Transport and Logistics. 25. | spa |
| dc.relation.references | Jourdan, L., Basseur, M., & Talb, E.-G. (2005). Hybridizing Exact Methods and Metaheuristics: A Taxonomy. European Journal of Operational Research, 199, 620-629. | spa |
| dc.relation.references | Kurnia, H., Wahyuni, E. G., Pembrani, E. C., Gardini, S. T., & Aditya, S. K. (2017). Vehicle Routing Problem Using Genetic Algorithm with Multi Compartment on Vegetable Distribution. IOP Conf. Series: Materials Science and Engineering, 325. | spa |
| dc.relation.references | Londoño, C. S., & Arias Hernandez, C. P. (2018). Análisis y Prototipado de una Algoritmo Genético Modificado para Solucionar el Problema de Ruteo de Vehículos con Ventanas de Tiempo(VRPTW), Prioridad de Metas Económicas y Componente Medio Ambiental (Tesis de Maestria). Universidad Tecnológica de Pereira, Pereira. | spa |
| dc.relation.references | López, E., Salas, Ó., & Murillo, Á. (2014). The Travelin Salesman Problem A Deterministic Algorithm Using Tabu Search. Reviste de Matemática: Teoria y Aplicaciones, 21, 127-144. | spa |
| dc.relation.references | Lozada Diaz, A., & Cadena Gonzalez, R. A. (2012). Solución del Problema de Ruteo de Vehículos con Ventanas de Tiempo (VRPTW) Mediante Métodos Heuristicos (Tesis de Pregrado). Universidad Industrial de Santader, Bucaramanga. | spa |
| dc.relation.references | Lüer, A., Benavente, M., Bustos, J., & Venegas, B. (2009). El Problema de Rutas de Vehículos: Extensiones y Métodos de Resolución, Estado del Arte. Workshop Internacional. | spa |
| dc.relation.references | Márquez Gómez, M. (2014). Las metaheurísticas: Tendencias Actuales y su Aplicabilidad en la Ergonomía. Ingeniería Industrial. Actualidad y Nuevas Tendencias, 4, 108-120. | spa |
| dc.relation.references | Marshall, L. F., Madsen, O. B., & Jornsten, k. O. (1997). Vehicle Routing With Time Windows Two Optimization Algorithms. Institute for Operations Research and the Management Sciences, 45, 488-492. | spa |
| dc.relation.references | Mediorreal Carrillo, A. F. (2014). Modelo de Ruteo de Vehículos para la Distribución de las Empresas Laboratorios Veterland, Laboratorios Callbest y Cosméticos Marlioü París (Tesis de Pregrado). Pontifica Universidad Javeriana, Bogotá D,C. | spa |
| dc.relation.references | Orozco, E. M. (2017). Metaheurísticas para el Problema de Ruteo de Vehículos con Ventanas de Tiempo (VRP-TW) (Tesis de Maestria). Universidad Autónoma Metropolitana Azapotzal Co, Ciudad de México. | spa |
| dc.relation.references | Pacheco Bonostro, J. A. (2000). Problemas de Rutas con Ventanas de Tiempo. uniyersidad Complutense de Madrid, Madrid. | spa |
| dc.relation.references | Pureza, V., Morabito, R., & Reimann, M. (2012). Vehicle Routing With Multiple Deliverymen: Modeling and Heuristic Approaches. European Journal of Operational Research, 218, 636-647. | spa |
| dc.relation.references | Quagliaroli Zapata, D. R. (2007). Desarrollo de un Algoritmo Genetico-Cultiral para el Problema de Enrutamiento de Vehículos con Ventanas de Tiempo (Tesis de Pregrado). Pontificia Universidad Católica de Valparaíso, Valparaiso. | spa |
| dc.relation.references | Segura Peñuela, Á. D., & Padua Dueñas, A. K. (2018). Modelo para la Solución de un Problema de Ruteo de Vehículos con Capacidad y Ventanas de Tiempo, en el Servicio de Transporte de Canje y Correo Bancario (Tesis de Pregrado). Universitaria Agustiniana, Bogotá D,C. | spa |
| dc.relation.references | Segura, V., Fuster , A., Antolín, F., Casellas, C., Payno, M., Grandío, A., . . . Muelas, M. (2020). Logística de Última Milla: Retos y soluciones en España . 65. | spa |
| dc.relation.references | Solomon, M. (1987). Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, 35, 254-265. | spa |
| dc.relation.references | Subramanian, A., Uchoa, E., & Ochi, L. S. (2013). A Hybrid Algorithm For a Class of Vehicle Routing Problems. Computers & Operations Research, 40, 2519-2531. | spa |
| dc.relation.references | Szeto, W., Yongzhong, W., & Sin C, H. (2011). An Artificial Bee Colony Algorithm For The Capacitated Vehicle Routing Problem. European Journal of Operational Research, 215, 126-135. | spa |
| dc.relation.references | Velasco Linares, B. S. (2019). Diseño de un Modelo de Ruteo de Vehículos Dependientes del Tiempo en una Zona Urbana de Bogotá D,C (Tesis de Pregrado). Universidad Distrital Francisco Jose de Caldas, Bogotá D,C. | spa |
| dc.publisher.program | Especialización en Logística y Gestión de la Cadena de Abastecimiento | spa |
| dc.type.coar | http://purl.org/coar/resource_type/c_7a1f | |
| dc.publisher.faculty | Facultad Ingeniería y Diseño e Innovación | spa |
| dc.identifier.instname | instname:Politécnico Grancolombiano | spa |
| dc.identifier.reponame | reponame:Alejandría Repositorio Comunidad | spa |
| dc.type.hasversion | info:eu-repo/semantics/acceptedVersion | |
| dc.rights.accessrights | info:eu-repo/semantics/openAccess | |
| dc.identifier.repourl | repourl:http://alejandria.poligran.edu.co | spa |
| dc.type.redcol | https://purl.org/redcol/resource_type/TP | |
| dc.rights.creativecommons | Atribución-NoComercial-SinDerivadas 2.5 Colombia | spa |
| dc.type.version | info:eu-repo/semantics/draft | spa |
