Escudo de la República de Colombia
Sistema Nacional de Biliotecas - Repositorio Institucional Universidad Nacional de Colombia Biblioteca Digital - Repositorio Institucional UN Sistema Nacional de Bibliotecas UN

Metodología de algoritmos meméticos para el problema de ruteo de vehículos con entregas parciales y tiempos de viaje dependientes con ventanas de tiempo

Cadavid Jaramillo, Jhoan Sebastián (2019) Metodología de algoritmos meméticos para el problema de ruteo de vehículos con entregas parciales y tiempos de viaje dependientes con ventanas de tiempo. Maestría thesis, Universidad Nacional de Colombia - Sede Medellín.

Texto completo

[img] PDF - Versión Aceptada
Available under License Creative Commons Attribution Non-commercial No Derivatives.

3MB

Resumen

El problema de ruteo de vehículos VRP es uno de los problemas más estudiados en investigación de operaciones, dada su relevancia en los campos del transporte y la logística. En los últimos años ha aumentado el interés en minimizar la contaminación por la emisión de gases efecto invernadero a causa del consumo de combustibles fósiles. El sector transporte representa una parte importante en esas emisiones. En el transporte, situaciones como los embotellamientos en las horas pico, por ejemplo, conducen a una red vial dinámica en la que varían los tiempos de viaje y consecuentemente el consumo de combustible. Por lo anterior el problema de enrutamiento de vehículos con tiempos dependientes TDVRP es una representación más cercana la vida real que los modelos tradicionales de enrutamientos de vehículos, VRP. Por otro lado, el problema de enrutamiento de vehículos con partición de entregas, SDVRP permite asignar múltiples rutas a un mismo cliente, propiciando ahorros en las mismas. El objetivo de esta tesis es desarrollar un método para el uso de los recursos de transporte, con el fin de atender a los clientes de manera eficiente respecto al costo total de la distancia recorrida y al tiempo total de viaje requerido. El problema consiste en programar un recorrido durante un día dividido en intervalos o zonas horarias, con ventanas de tiempo para atender a cada cliente, vehículos homogéneos con capacidad fija Q y un depósito único. Para ello se propone en este trabajo un Algoritmo Memético (MA) capaz de encontrar soluciones que respetan las restricciones del problema, teniendo en cuenta la posibilidad de hacer particiones en las entregas. Mediante el Diseño de Experimentos se evaluó la calidad de las soluciones generadas respecto a un Algoritmo Genético (GA) desarrollado también para el propósito, teniendo como criterio de evaluación el porcentaje de mejores soluciones alcanzado por cada algoritmo. Los experimentos permiten afirmar que el Algoritmo Memético propuesto supera el Algoritmo Genético, resultando más robusto ante cambios en los parámetros de ambos métodos. La solución propuesta representa un modelo más cercano a la realidad de las redes viales y genera rutas tendientes a disminuir la cantidad, recorrido y tiempo de permanencia de los vehículos en la red vial, conllevando a la disminución de las emisiones de gases efecto invernadero., Abstract: The vehicle routing problem VRP is one of the most studied problems in operations research, given its relevance in the fields of transport and logistics. In recent years, interest in minimizing pollution due to the emission of greenhouse gases, as a result of the consumption of fossil fuels, has increased. The transport sector represents an important part of those emissions. In transport, situations such as traffic jams during peak hours, for example, lead to a dynamic road network in which travel times and consequently fuel consumption vary. Therefore, the time dependent vehicle routing problem, TDVRP, is a closer representation of real life than the traditional vehicle routing models, VRP. On the other hand, the split delivery vehicle routing problem, SDVRP, allows assigning multiple routes to the same client, promoting savings in them. The objective of this thesis is to develop a method for the use of transportation resources, in order to serve customers efficiently with regard to the total cost of the distance traveled and the total traveled time required. The problem consists of scheduling a trip for a day which is divided into intervals or time zones, with time windows to serve each customer, homogeneous vehicles with fixed capacity Q and a single deposit. In order to do so, a Memetic Algorithm (MA) is proposed in this work, capable of finding solutions that respect the constraints of the problem, taking into account the possibility of splitting the deliveries. By using Design of Experiments, the quality of the solutions generated by the Memetic Algorithm was evaluated with respect to a Genetic Algorithm (GA) also developed for the purpose, having as the evaluation criterion the percentage of best solutions reached by each algorithm. The experiments show that the proposed memetic algorithm surpasses the genetic algorithm, being more robust to changes in the parameters of both methods The proposed solution represents a model that is closer to the reality of road networks and generates routes that tend to reduce quantity, travel length and time spent by vehicles on the road network, leading to a reduction in greenhouse gas emissions.

Tipo de documento:Tesis/trabajos de grado - Thesis (Maestría)
Colaborador / Asesor:Rodríguez Velásquez, Elkin
Información adicional:Línea de Investigación: Investigación de Operaciones
Palabras clave:Problema de ruteo de vehículos, Estudio de tiempos y movimientos, Metaheurístico, Algoritmo Memético, Split Delivery, Memetic Algorithm
Temática:6 Tecnología (ciencias aplicadas) / Technology > 62 Ingeniería y operaciones afines / Engineering
Unidad administrativa:Sede Medellín > Facultad de Minas > Escuela de Ingeniería de la Organización
Código ID:73941
Enviado por : Jhoan Sebastián Cadavid Jaramillo
Enviado el día :13 Septiembre 2019 15:45
Ultima modificación:16 Septiembre 2019 21:16
Ultima modificación:16 Septiembre 2019 21:16
Exportar:Clic aquí
Estadísticas:Clic aquí
Compartir:

Solamente administradores del repositorio: página de control del ítem

Vicerrectoría de Investigación: Número uno en investigación
Indexado por:
Indexado por Scholar Google WorldCat DRIVER Metabiblioteca OAIster BASE BDCOL Registry of Open Access Repositories SNAAC Red de repositorios latinoamericanos eprints Open archives La referencia Tesis latinoamericanas OpenDOAR CLACSO
Este sitio web se ve mejor en Firefox