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

A hybrid evolutionary algorithm for vehicle routing problem with stochastic demands

Jaque Pirabán, Robinson Andrés (2015) A hybrid evolutionary algorithm for vehicle routing problem with stochastic demands. Maestría thesis, Universidad Nacional de Colombia.

Texto completo

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

1MB

Resumen

In this work we propose a hybrid dynamic programming evolutionary algorithm to solve the vehicle routing problem with stochastic demands, it is a well known NP-hard problem where uncertainty enhances the computational efforts required to obtain a feasible and near-optimal solution. We develop an evolutionary technique where a rollout dynamic programming algorithm is applied as local search method to improve the quality of solutions. Motivated by computational considerations, the rollout algorithm can be applied partially, so, this finds competitive solutions in large instances for which the global rollout dynamic programming strategy is time unfeasible., Resumen. En este trabajo se propone un algoritmo evolutivo hibrido que combina un m ́etodo de programación dinámica estocástica para resolver el problema de enrutamiento de vehículos con demandas estocásticas, este es un problema demostrado como NP-difícil donde la presencia de incertidumbre incrementa los requerimientos computacionales necesarios para obtener soluciones factibles y cercanas a la óptima. Así, para el algoritmo evolutivo desarrollado se aplico un algoritmo rollout de programación dinámica estocástica como operador de búsqueda local para mejorar la calidad de las soluciones. Motivado por requerimientos computacionales, el algoritmo de rollout puede ser aplicado parcialmente, con el objetivo de encontrar soluciones competitivas en instancias lo suficientemente grandes para las cuales la estrategía global no es aplicable por consumir una cantidad de tiempo no tolerable.

Tipo de documento:Tesis/trabajos de grado - Thesis (Maestría)
Colaborador / Asesor:Hernández Pérez, Germán Jairo
Información adicional:Master of System Engineer and Computer Science. Research Topic: Stochastic optimization
Palabras clave:Stochastic programming, Vehicle routing problem with stochastic demands, Dynamic programming, Logistics, Optimización estocástica, Problema de enrutamiento de vehículos con demandas estocásticas, Algoritmos, Programación dinámica,, Logística
Temática:6 Tecnología (ciencias aplicadas) / Technology > 62 Ingeniería y operaciones afines / Engineering
Unidad administrativa:Sede Bogotá > Facultad de Ingeniería > Departamento de Ingeniería de Sistemas e Industrial
Código ID:47414
Enviado por : Robinson Andres Jaque Piraban
Enviado el día :17 Mar 2015 07:17
Ultima modificación:17 Mar 2015 07:36
Ultima modificación:17 Mar 2015 07:36
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 Registry of Open Access Repositories OpenDOAR Metabiblioteca BDCOL OAIster Red de repositorios latinoamericanos DSpace BASE Open archives La referencia Colombiae Open Access Theses and Dissertations Tesis latinoamericanas CLACSO
Este sitio web se ve mejor en Firefox