A hybrid evolutionary algorithm for vehicle routing problem with stochastic demands
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 evo...
- Autores:
-
Jaque Pirabán, Robinson Andrés
- Tipo de recurso:
- Fecha de publicación:
- 2015
- Institución:
- Universidad Nacional de Colombia
- Repositorio:
- Universidad Nacional de Colombia
- Idioma:
- spa
- OAI Identifier:
- oai:repositorio.unal.edu.co:unal/52953
- Acceso en línea:
- https://repositorio.unal.edu.co/handle/unal/52953
http://bdigital.unal.edu.co/47414/
- Palabra clave:
- 62 Ingeniería y operaciones afines / Engineering
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
- Rights
- openAccess
- License
- Atribución-NoComercial 4.0 Internacional
| id |
UNACIONAL2_5bd90d890b28460e873ec616f0383f11 |
|---|---|
| oai_identifier_str |
oai:repositorio.unal.edu.co:unal/52953 |
| network_acronym_str |
UNACIONAL2 |
| network_name_str |
Universidad Nacional de Colombia |
| repository_id_str |
|
| spelling |
Atribución-NoComercial 4.0 InternacionalDerechos reservados - Universidad Nacional de Colombiahttp://creativecommons.org/licenses/by-nc/4.0/info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2Hernández Pérez, Germán JairoJaque Pirabán, Robinson Andrés270c8284-bbea-440c-befe-20b9a40d9d333002019-06-29T15:50:08Z2019-06-29T15:50:08Z2015-03-09https://repositorio.unal.edu.co/handle/unal/52953http://bdigital.unal.edu.co/47414/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.Maestríaapplication/pdfspaUniversidad Nacional de Colombia Sede Bogotá Facultad de Ingeniería Departamento de Ingeniería de Sistemas e IndustrialDepartamento de Ingeniería de Sistemas e IndustrialJaque Pirabán, Robinson Andrés (2015) A hybrid evolutionary algorithm for vehicle routing problem with stochastic demands. Maestría thesis, Universidad Nacional de Colombia.62 Ingeniería y operaciones afines / EngineeringStochastic programmingVehicle routing problem with stochastic demandsDynamic programmingLogisticsOptimización estocásticaProblema de enrutamiento de vehículos con demandas estocásticasAlgoritmosProgramación dinámica,LogísticaA hybrid evolutionary algorithm for vehicle routing problem with stochastic demandsTrabajo de grado - Maestríainfo:eu-repo/semantics/masterThesisinfo:eu-repo/semantics/acceptedVersionTexthttp://purl.org/redcol/resource_type/TMORIGINAL80190790.2015.pdfapplication/pdf1135959https://repositorio.unal.edu.co/bitstream/unal/52953/1/80190790.2015.pdf6e363f05ec3e205c2f690b3d2be82cfbMD51THUMBNAIL80190790.2015.pdf.jpg80190790.2015.pdf.jpgGenerated Thumbnailimage/jpeg4466https://repositorio.unal.edu.co/bitstream/unal/52953/2/80190790.2015.pdf.jpgb46ac0e06f1dfce2f2caaef185c172a5MD52unal/52953oai:repositorio.unal.edu.co:unal/529532024-03-04 23:09:24.738Repositorio Institucional Universidad Nacional de Colombiarepositorio_nal@unal.edu.co |
| dc.title.spa.fl_str_mv |
A hybrid evolutionary algorithm for vehicle routing problem with stochastic demands |
| title |
A hybrid evolutionary algorithm for vehicle routing problem with stochastic demands |
| spellingShingle |
A hybrid evolutionary algorithm for vehicle routing problem with stochastic demands 62 Ingeniería y operaciones afines / Engineering 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 |
| title_short |
A hybrid evolutionary algorithm for vehicle routing problem with stochastic demands |
| title_full |
A hybrid evolutionary algorithm for vehicle routing problem with stochastic demands |
| title_fullStr |
A hybrid evolutionary algorithm for vehicle routing problem with stochastic demands |
| title_full_unstemmed |
A hybrid evolutionary algorithm for vehicle routing problem with stochastic demands |
| title_sort |
A hybrid evolutionary algorithm for vehicle routing problem with stochastic demands |
| dc.creator.fl_str_mv |
Jaque Pirabán, Robinson Andrés |
| dc.contributor.author.spa.fl_str_mv |
Jaque Pirabán, Robinson Andrés |
| dc.contributor.spa.fl_str_mv |
Hernández Pérez, Germán Jairo |
| dc.subject.ddc.spa.fl_str_mv |
62 Ingeniería y operaciones afines / Engineering |
| topic |
62 Ingeniería y operaciones afines / Engineering 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 |
| dc.subject.proposal.spa.fl_str_mv |
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 |
| description |
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. |
| publishDate |
2015 |
| dc.date.issued.spa.fl_str_mv |
2015-03-09 |
| dc.date.accessioned.spa.fl_str_mv |
2019-06-29T15:50:08Z |
| dc.date.available.spa.fl_str_mv |
2019-06-29T15:50:08Z |
| dc.type.spa.fl_str_mv |
Trabajo de grado - Maestría |
| dc.type.driver.spa.fl_str_mv |
info:eu-repo/semantics/masterThesis |
| dc.type.version.spa.fl_str_mv |
info:eu-repo/semantics/acceptedVersion |
| dc.type.content.spa.fl_str_mv |
Text |
| dc.type.redcol.spa.fl_str_mv |
http://purl.org/redcol/resource_type/TM |
| status_str |
acceptedVersion |
| dc.identifier.uri.none.fl_str_mv |
https://repositorio.unal.edu.co/handle/unal/52953 |
| dc.identifier.eprints.spa.fl_str_mv |
http://bdigital.unal.edu.co/47414/ |
| url |
https://repositorio.unal.edu.co/handle/unal/52953 http://bdigital.unal.edu.co/47414/ |
| dc.language.iso.spa.fl_str_mv |
spa |
| language |
spa |
| dc.relation.ispartof.spa.fl_str_mv |
Universidad Nacional de Colombia Sede Bogotá Facultad de Ingeniería Departamento de Ingeniería de Sistemas e Industrial Departamento de Ingeniería de Sistemas e Industrial |
| dc.relation.references.spa.fl_str_mv |
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. |
| dc.rights.spa.fl_str_mv |
Derechos reservados - Universidad Nacional de Colombia |
| dc.rights.coar.fl_str_mv |
http://purl.org/coar/access_right/c_abf2 |
| dc.rights.license.spa.fl_str_mv |
Atribución-NoComercial 4.0 Internacional |
| dc.rights.uri.spa.fl_str_mv |
http://creativecommons.org/licenses/by-nc/4.0/ |
| dc.rights.accessrights.spa.fl_str_mv |
info:eu-repo/semantics/openAccess |
| rights_invalid_str_mv |
Atribución-NoComercial 4.0 Internacional Derechos reservados - Universidad Nacional de Colombia http://creativecommons.org/licenses/by-nc/4.0/ http://purl.org/coar/access_right/c_abf2 |
| eu_rights_str_mv |
openAccess |
| dc.format.mimetype.spa.fl_str_mv |
application/pdf |
| institution |
Universidad Nacional de Colombia |
| bitstream.url.fl_str_mv |
https://repositorio.unal.edu.co/bitstream/unal/52953/1/80190790.2015.pdf https://repositorio.unal.edu.co/bitstream/unal/52953/2/80190790.2015.pdf.jpg |
| bitstream.checksum.fl_str_mv |
6e363f05ec3e205c2f690b3d2be82cfb b46ac0e06f1dfce2f2caaef185c172a5 |
| bitstream.checksumAlgorithm.fl_str_mv |
MD5 MD5 |
| repository.name.fl_str_mv |
Repositorio Institucional Universidad Nacional de Colombia |
| repository.mail.fl_str_mv |
repositorio_nal@unal.edu.co |
| _version_ |
1814090194745294848 |