Algoritmos de solución para el problema multidepósito y multiobjetivo de ruteo de vehículos considerando recogida de productos y restricción de precedencia

En esta tesis se presenta la aplicación de diferentes técnicas heurísticas y metaheurísticas para la solución del problema de ruteo de vehículos con restricción de precedencia, heurísticas como el vecino más cercano y la del ahorro con inserción secuencial, y metaheurísticas como búsqueda tabú y opt...

Full description

Autores:
Santa Chávez, Jhon Jairo
Tipo de recurso:
Fecha de publicación:
2017
Institución:
Universidad Tecnológica de Pereira
Repositorio:
Repositorio Institucional UTP
Idioma:
spa
OAI Identifier:
oai:repositorio.utp.edu.co:11059/8472
Acceso en línea:
https://hdl.handle.net/11059/8472
Palabra clave:
Programación heurística
Metaheurística
Algoritmos
Rights
License
Attribution-NonCommercial-NoDerivatives 4.0 International
id UTP2_b3472f62eca28073c5c0ea82f1bfed43
oai_identifier_str oai:repositorio.utp.edu.co:11059/8472
network_acronym_str UTP2
network_name_str Repositorio Institucional UTP
repository_id_str
dc.title.spa.fl_str_mv Algoritmos de solución para el problema multidepósito y multiobjetivo de ruteo de vehículos considerando recogida de productos y restricción de precedencia
title Algoritmos de solución para el problema multidepósito y multiobjetivo de ruteo de vehículos considerando recogida de productos y restricción de precedencia
spellingShingle Algoritmos de solución para el problema multidepósito y multiobjetivo de ruteo de vehículos considerando recogida de productos y restricción de precedencia
Programación heurística
Metaheurística
Algoritmos
title_short Algoritmos de solución para el problema multidepósito y multiobjetivo de ruteo de vehículos considerando recogida de productos y restricción de precedencia
title_full Algoritmos de solución para el problema multidepósito y multiobjetivo de ruteo de vehículos considerando recogida de productos y restricción de precedencia
title_fullStr Algoritmos de solución para el problema multidepósito y multiobjetivo de ruteo de vehículos considerando recogida de productos y restricción de precedencia
title_full_unstemmed Algoritmos de solución para el problema multidepósito y multiobjetivo de ruteo de vehículos considerando recogida de productos y restricción de precedencia
title_sort Algoritmos de solución para el problema multidepósito y multiobjetivo de ruteo de vehículos considerando recogida de productos y restricción de precedencia
dc.creator.fl_str_mv Santa Chávez, Jhon Jairo
dc.contributor.advisor.none.fl_str_mv Granada Echeverri, Mauricio
dc.contributor.author.none.fl_str_mv Santa Chávez, Jhon Jairo
dc.subject.spa.fl_str_mv Programación heurística
Metaheurística
Algoritmos
topic Programación heurística
Metaheurística
Algoritmos
description En esta tesis se presenta la aplicación de diferentes técnicas heurísticas y metaheurísticas para la solución del problema de ruteo de vehículos con restricción de precedencia, heurísticas como el vecino más cercano y la del ahorro con inserción secuencial, y metaheurísticas como búsqueda tabú y optimización por colonia de hormigas son utilizadas y ajustadas para resolver eficientemente diferentes variantes del problema de ruteo de vehículos con entrega y recogida de paquetes con restricción de precedencia, considerando el caso monodepósito y multidepósito, mono y multiobjetivo. Cada ruta realizada consta de una sub-ruta en la que se realiza sólo la tarea de entrega y otra sub-ruta en la que se realiza sólo el proceso de recolección, esta última se inicia solo cuando el vehículo está vacío. Los algoritmos y metaheurísticas propuestas tratan de encontrar el mejor orden para visitar a los clientes en cada ruta realizada. Además, el enfoque propuesto determina la mejor conexión entre los sub-rutas de entrega y recogida, con el fin de obtener una solución global minimizando el número de vehículos, la distancia recorrida, el tiempo empleado y la cantidad de energía consumida por los vehículos. El estudio multiobjetivo permitió encontrar un conjunto de soluciones ordenadas en los frentes de Pareto considerando el concepto de dominancia. Adicionalmente, para el modelo multiobjetivo, se plantea la metodología de ponderaciones de los valores de cada función objetivo se selecciona una alternativa de solución con dominancia en el número de vehículos usados. La eficacia del enfoque propuesto se examina teniendo en cuenta un conjunto de casos adaptados de la literatura. También, se propone un modelo exacto, el cual es resuelto mediante la técnica de rutas abiertas con enlace óptimo. Los resultados computacionales muestran resultados de alta calidad en tiempos de procesamiento competitivos. Los resultados computacionales se comparan con los existentes en la literatura especializada y entre los diferentes algoritmos propuestos. Por último, se presentan las conclusiones y sugerencias para trabajos futuros.
publishDate 2017
dc.date.issued.none.fl_str_mv 2017
dc.date.accessioned.none.fl_str_mv 2018-02-06T14:01:33Z
2021-11-02T19:43:39Z
dc.date.available.none.fl_str_mv 2018-02-06T14:01:33Z
2021-11-02T19:43:39Z
dc.type.spa.fl_str_mv doctoralThesis
dc.type.coar.fl_str_mv http://purl.org/coar/resource_type/c_db06
dc.type.hasVersion.spa.fl_str_mv acceptedVersion
dc.identifier.uri.none.fl_str_mv https://hdl.handle.net/11059/8472
dc.identifier.local.spa.fl_str_mv T519.6 S231;6310000121462 F5705
url https://hdl.handle.net/11059/8472
identifier_str_mv T519.6 S231;6310000121462 F5705
dc.language.iso.spa.fl_str_mv spa
language spa
dc.rights.*.fl_str_mv Attribution-NonCommercial-NoDerivatives 4.0 International
dc.rights.coar.fl_str_mv http://purl.org/coar/access_right/c_abf2
dc.rights.uri.*.fl_str_mv http://creativecommons.org/licenses/by-nc-nd/4.0/
rights_invalid_str_mv Attribution-NonCommercial-NoDerivatives 4.0 International
http://creativecommons.org/licenses/by-nc-nd/4.0/
http://purl.org/coar/access_right/c_abf2
dc.format.spa.fl_str_mv application/pdf
dc.publisher.spa.fl_str_mv Pereira : Universidad Tecnológica de Pereira
dc.publisher.department.spa.fl_str_mv Facultad de Ingeniería
dc.publisher.program.spa.fl_str_mv Doctorado en Ingeniería
institution Universidad Tecnológica de Pereira
bitstream.url.fl_str_mv https://dspace7-utp.metabuscador.org/bitstreams/e74307ff-2f45-4147-b700-a18e9b94e91f/download
https://dspace7-utp.metabuscador.org/bitstreams/56ac1d66-4fe4-4380-9bd7-528a6540dbaa/download
https://dspace7-utp.metabuscador.org/bitstreams/d3ffad71-d978-4340-89d9-c28eeddec867/download
https://dspace7-utp.metabuscador.org/bitstreams/76bebeee-68fb-49a8-8217-03504015496a/download
https://dspace7-utp.metabuscador.org/bitstreams/38b990cc-a188-454c-befb-0784591ace6e/download
bitstream.checksum.fl_str_mv e2e549e0a1eff8f2de922c8fd2184f09
b101b0d23bbe6747b1194699543d9d6c
7c9ab7f006165862d8ce9ac5eac01552
4425bf2127ed1ae74a82dfcdb14cdf39
a40e19bd70c027c0e44113858ae198cc
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
MD5
MD5
MD5
repository.name.fl_str_mv Repositorio de la Universidad Tecnológica de Pereira
repository.mail.fl_str_mv bdigital@metabiblioteca.com
_version_ 1815732400151330816
spelling Granada Echeverri, MauricioSanta Chávez, Jhon JairoDoctor en Ingeniería2018-02-06T14:01:33Z2021-11-02T19:43:39Z2018-02-06T14:01:33Z2021-11-02T19:43:39Z2017https://hdl.handle.net/11059/8472T519.6 S231;6310000121462 F5705En esta tesis se presenta la aplicación de diferentes técnicas heurísticas y metaheurísticas para la solución del problema de ruteo de vehículos con restricción de precedencia, heurísticas como el vecino más cercano y la del ahorro con inserción secuencial, y metaheurísticas como búsqueda tabú y optimización por colonia de hormigas son utilizadas y ajustadas para resolver eficientemente diferentes variantes del problema de ruteo de vehículos con entrega y recogida de paquetes con restricción de precedencia, considerando el caso monodepósito y multidepósito, mono y multiobjetivo. Cada ruta realizada consta de una sub-ruta en la que se realiza sólo la tarea de entrega y otra sub-ruta en la que se realiza sólo el proceso de recolección, esta última se inicia solo cuando el vehículo está vacío. Los algoritmos y metaheurísticas propuestas tratan de encontrar el mejor orden para visitar a los clientes en cada ruta realizada. Además, el enfoque propuesto determina la mejor conexión entre los sub-rutas de entrega y recogida, con el fin de obtener una solución global minimizando el número de vehículos, la distancia recorrida, el tiempo empleado y la cantidad de energía consumida por los vehículos. El estudio multiobjetivo permitió encontrar un conjunto de soluciones ordenadas en los frentes de Pareto considerando el concepto de dominancia. Adicionalmente, para el modelo multiobjetivo, se plantea la metodología de ponderaciones de los valores de cada función objetivo se selecciona una alternativa de solución con dominancia en el número de vehículos usados. La eficacia del enfoque propuesto se examina teniendo en cuenta un conjunto de casos adaptados de la literatura. También, se propone un modelo exacto, el cual es resuelto mediante la técnica de rutas abiertas con enlace óptimo. Los resultados computacionales muestran resultados de alta calidad en tiempos de procesamiento competitivos. Los resultados computacionales se comparan con los existentes en la literatura especializada y entre los diferentes algoritmos propuestos. Por último, se presentan las conclusiones y sugerencias para trabajos futuros.application/pdfspaPereira : Universidad Tecnológica de PereiraFacultad de IngenieríaDoctorado en IngenieríaAttribution-NonCommercial-NoDerivatives 4.0 Internationalhttp://creativecommons.org/licenses/by-nc-nd/4.0/http://purl.org/coar/access_right/c_abf2Programación heurísticaMetaheurísticaAlgoritmosAlgoritmos de solución para el problema multidepósito y multiobjetivo de ruteo de vehículos considerando recogida de productos y restricción de precedenciadoctoralThesisacceptedVersionhttp://purl.org/coar/resource_type/c_db06PublicationLICENSElicense.txttext/plain849https://dspace7-utp.metabuscador.org/bitstreams/e74307ff-2f45-4147-b700-a18e9b94e91f/downloade2e549e0a1eff8f2de922c8fd2184f09MD51ORIGINAL5196S231.pdfDocumento Principalapplication/pdf4414541https://dspace7-utp.metabuscador.org/bitstreams/56ac1d66-4fe4-4380-9bd7-528a6540dbaa/downloadb101b0d23bbe6747b1194699543d9d6cMD52CC-LICENSElicense_rdfapplication/octet-stream1223https://dspace7-utp.metabuscador.org/bitstreams/d3ffad71-d978-4340-89d9-c28eeddec867/download7c9ab7f006165862d8ce9ac5eac01552MD53TEXT5196S231.pdf.txt5196S231.pdf.txtExtracted texttext/plain284527https://dspace7-utp.metabuscador.org/bitstreams/76bebeee-68fb-49a8-8217-03504015496a/download4425bf2127ed1ae74a82dfcdb14cdf39MD56THUMBNAIL5196S231.pdf.jpg5196S231.pdf.jpgGenerated Thumbnailimage/jpeg8857https://dspace7-utp.metabuscador.org/bitstreams/38b990cc-a188-454c-befb-0784591ace6e/downloada40e19bd70c027c0e44113858ae198ccMD5711059/8472oai:dspace7-utp.metabuscador.org:11059/84722024-09-05 16:47:23.063http://creativecommons.org/licenses/by-nc-nd/4.0/Attribution-NonCommercial-NoDerivatives 4.0 Internationalopen.accesshttps://dspace7-utp.metabuscador.orgRepositorio de la Universidad Tecnológica de Pereirabdigital@metabiblioteca.comRUwgQVVUT1IsIG1hbmlmaWVzdGEgcXVlIGxhIG9icmEgb2JqZXRvIGRlIGxhIHByZXNlbnRlIGF1dG9yaXphY2nDs24gZXMgb3JpZ2luYWwgeSBsYSByZWFsaXrDsyBzaW4gdmlvbGFyIG8gdXN1cnBhciBkZXJlY2hvcyBkZSBhdXRvciBkZSB0ZXJjZXJvcywgcG9yIGxvIHRhbnRvIGxhIG9icmEgZXMgZGUgZXhjbHVzaXZhIGF1dG9yw61hIHkgdGllbmUgbGEgdGl0dWxhcmlkYWQgc29icmUgbGEgbWlzbWEuIFBBUsOBR1JBRk86IEVuIGNhc28gZGUgcHJlc2VudGFyc2UgY3VhbHF1aWVyIHJlY2xhbWFjacOzbiBvIGFjY2nDs24gcG9yIHBhcnRlIGRlIHVuIHRlcmNlcm8gZW4gY3VhbnRvIGEgbG9zIGRlcmVjaG9zIGRlIGF1dG9yIHNvYnJlIGxhIG9icmEgZW4gY3Vlc3Rpw7NuLCBFTCBBVVRPUiwgYXN1bWlyw6EgdG9kYSBsYSByZXNwb25zYWJpbGlkYWQsIHkgc2FsZHLDoSBlbiBkZWZlbnNhIGRlIGxvcyBkZXJlY2hvcyBhcXXDrSBhdXRvcml6YWRvczsgcGFyYSB0b2RvcyBsb3MgZWZlY3RvcyBsYSB1bml2ZXJzaWRhZCBhY3TDumEgY29tbyB1biB0ZXJjZXJvIGRlIGJ1ZW5hIGZlLiBFTCBBVVRPUiwgYXV0b3JpemEgYSBMQSBVTklWRVJTSURBRCBURUNOT0xPR0lDQSBERSBQRVJFSVJBLCBwYXJhIHF1ZSBlbiBsb3MgdMOpcm1pbm9zIGVzdGFibGVjaWRvcyBlbiBsYSBMZXkgMjMgZGUgMTk4MiwgTGV5IDQ0IGRlIDE5OTMsIERlY2lzacOzbiBhbmRpbmEgMzUxIGRlIDE5OTMsIERlY3JldG8gNDYwIGRlIDE5OTUgeSBkZW3DoXMgbm9ybWFzIGdlbmVyYWxlcyBzb2JyZSBsYSBtYXRlcmlhLCB1dGlsaWNlIHkgdXNlIGxhIG9icmEgb2JqZXRvIGRlIGxhIHByZXNlbnRlIGF1dG9yaXphY2nDs24u