An exact bidirectional pulse algorithm for the constrained shortest path

"Una ruta más corta restringida es una secuencia de arcos de costo mínimo en una red dirigida que satisface las restricciones de tipo knapsack en el consumo de recursos sobre los arcos. Nosotros proponemos un método exacto basado en un procedimiento de búsqueda recursiva en profundidad, conocid...

Full description

Autores:
Cabrera Malik, Nicolás
Tipo de recurso:
Fecha de publicación:
2019
Institución:
Universidad de los Andes
Repositorio:
Séneca: repositorio Uniandes
Idioma:
eng
OAI Identifier:
oai:repositorio.uniandes.edu.co:1992/44083
Acceso en línea:
http://hdl.handle.net/1992/44083
Palabra clave:
Problema de rutas de vehículos - Investigaciones
Análisis de ruta crítica - Investigaciones
Sistemas inteligentes de transporte - Investigaciones
Programación heurística - Investigaciones
Carreteras - Análisis de redes - Investigaciones
Sistemas de grandes dimensiones - Investigaciones
Investigación operacional - Investigaciones
Optimización matemática - Investigaciones
Ingeniería
Rights
openAccess
License
https://repositorio.uniandes.edu.co/static/pdf/aceptacion_uso_es.pdf
id UNIANDES2_d38901e845aff51afcc1cfb7ea1c3e2f
oai_identifier_str oai:repositorio.uniandes.edu.co:1992/44083
network_acronym_str UNIANDES2
network_name_str Séneca: repositorio Uniandes
repository_id_str
spelling Al consultar y hacer uso de este recurso, está aceptando las condiciones de uso establecidas por los autores.https://repositorio.uniandes.edu.co/static/pdf/aceptacion_uso_es.pdfinfo:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2Medaglia González, Andrés L.3642fa58-ecf3-4f9e-a695-5934b0ff6c5f400Cabrera Malik, Nicolásb768e781-5408-4d64-963d-5054f5cb309f500Lozano Sánchez, LeonardoGómez Castro, Camilo Hernando2020-09-03T14:31:43Z2020-09-03T14:31:43Z2019http://hdl.handle.net/1992/44083u827478.pdfinstname:Universidad de los Andesreponame:Repositorio Institucional Sénecarepourl:https://repositorio.uniandes.edu.co/"Una ruta más corta restringida es una secuencia de arcos de costo mínimo en una red dirigida que satisface las restricciones de tipo knapsack en el consumo de recursos sobre los arcos. Nosotros proponemos un método exacto basado en un procedimiento de búsqueda recursiva en profundidad, conocido como el algoritmo del pulso. Una de las novedades clave de la propuesta radica en una estrategia de etiquetado bidireccional soportada en el paralelismo. Además, desarrollamos una heurística basada en el pulso que rápidamente encuentra soluciones casi óptimas y muestra un gran potencial para esquemas de generación de columnas. Nosotros presentamos experimentos computacionales en grandes redes de carreteras con hasta 6 millones de nodos y 15 millones de arcos." -- Tomado del Formato de Documento de Grado."A constrained shortest path is a minimum-cost sequence of arcs on a directed network that satisfies knapsack-type constraints on the resource consumption over the arcs. We propose an exact method based on a recursive depth-first search procedure known as the pulse algorithm. One of the key novelties of the proposal lies in a bidirectional labeling strategy leveraged on parallelism. In addition, we developed a pulse-based heuristic that quickly finds near-optimal solutions and shows great potential for column generation schemes. We present computational experiments over large real-road networks with up to 6 million nodes and 15 million arcs." -- Tomado del Formato de Documento de Grado.Magíster en Ingeniería IndustrialMaestría21 hojasapplication/pdfengUniandesMaestría en Ingeniería IndustrialFacultad de IngenieríaDepartamento de Ingeniería Industrialinstname:Universidad de los Andesreponame:Repositorio Institucional SénecaAn exact bidirectional pulse algorithm for the constrained shortest pathTrabajo de grado - Maestríainfo:eu-repo/semantics/masterThesishttp://purl.org/coar/version/c_970fb48d4fbd8a85Texthttp://purl.org/redcol/resource_type/TMProblema de rutas de vehículos - InvestigacionesAnálisis de ruta crítica - InvestigacionesSistemas inteligentes de transporte - InvestigacionesProgramación heurística - InvestigacionesCarreteras - Análisis de redes - InvestigacionesSistemas de grandes dimensiones - InvestigacionesInvestigación operacional - InvestigacionesOptimización matemática - InvestigacionesIngenieríaPublicationORIGINALu827478.pdfapplication/pdf875980https://repositorio.uniandes.edu.co/bitstreams/b7f39668-5972-47fc-9b3b-43692ecb2709/download698a22f167f3215841fdb8b8eb6581a8MD51TEXTu827478.pdf.txtu827478.pdf.txtExtracted texttext/plain52713https://repositorio.uniandes.edu.co/bitstreams/ead8ec06-9a48-4f97-b782-c5a04f00c483/downloadd56816af7cb64c55a5d639d9b3eeff02MD54THUMBNAILu827478.pdf.jpgu827478.pdf.jpgIM Thumbnailimage/jpeg25717https://repositorio.uniandes.edu.co/bitstreams/4d3577cc-a7d5-4433-bf57-d47dad6e31e1/downloadeaa8234ff2112e72460028dec17044adMD551992/44083oai:repositorio.uniandes.edu.co:1992/440832023-10-10 17:01:45.117https://repositorio.uniandes.edu.co/static/pdf/aceptacion_uso_es.pdfopen.accesshttps://repositorio.uniandes.edu.coRepositorio institucional Sénecaadminrepositorio@uniandes.edu.co
dc.title.es_CO.fl_str_mv An exact bidirectional pulse algorithm for the constrained shortest path
title An exact bidirectional pulse algorithm for the constrained shortest path
spellingShingle An exact bidirectional pulse algorithm for the constrained shortest path
Problema de rutas de vehículos - Investigaciones
Análisis de ruta crítica - Investigaciones
Sistemas inteligentes de transporte - Investigaciones
Programación heurística - Investigaciones
Carreteras - Análisis de redes - Investigaciones
Sistemas de grandes dimensiones - Investigaciones
Investigación operacional - Investigaciones
Optimización matemática - Investigaciones
Ingeniería
title_short An exact bidirectional pulse algorithm for the constrained shortest path
title_full An exact bidirectional pulse algorithm for the constrained shortest path
title_fullStr An exact bidirectional pulse algorithm for the constrained shortest path
title_full_unstemmed An exact bidirectional pulse algorithm for the constrained shortest path
title_sort An exact bidirectional pulse algorithm for the constrained shortest path
dc.creator.fl_str_mv Cabrera Malik, Nicolás
dc.contributor.advisor.none.fl_str_mv Medaglia González, Andrés L.
dc.contributor.author.none.fl_str_mv Cabrera Malik, Nicolás
dc.contributor.jury.none.fl_str_mv Lozano Sánchez, Leonardo
Gómez Castro, Camilo Hernando
dc.subject.armarc.es_CO.fl_str_mv Problema de rutas de vehículos - Investigaciones
Análisis de ruta crítica - Investigaciones
Sistemas inteligentes de transporte - Investigaciones
Programación heurística - Investigaciones
Carreteras - Análisis de redes - Investigaciones
Sistemas de grandes dimensiones - Investigaciones
Investigación operacional - Investigaciones
Optimización matemática - Investigaciones
topic Problema de rutas de vehículos - Investigaciones
Análisis de ruta crítica - Investigaciones
Sistemas inteligentes de transporte - Investigaciones
Programación heurística - Investigaciones
Carreteras - Análisis de redes - Investigaciones
Sistemas de grandes dimensiones - Investigaciones
Investigación operacional - Investigaciones
Optimización matemática - Investigaciones
Ingeniería
dc.subject.themes.none.fl_str_mv Ingeniería
description "Una ruta más corta restringida es una secuencia de arcos de costo mínimo en una red dirigida que satisface las restricciones de tipo knapsack en el consumo de recursos sobre los arcos. Nosotros proponemos un método exacto basado en un procedimiento de búsqueda recursiva en profundidad, conocido como el algoritmo del pulso. Una de las novedades clave de la propuesta radica en una estrategia de etiquetado bidireccional soportada en el paralelismo. Además, desarrollamos una heurística basada en el pulso que rápidamente encuentra soluciones casi óptimas y muestra un gran potencial para esquemas de generación de columnas. Nosotros presentamos experimentos computacionales en grandes redes de carreteras con hasta 6 millones de nodos y 15 millones de arcos." -- Tomado del Formato de Documento de Grado.
publishDate 2019
dc.date.issued.es_CO.fl_str_mv 2019
dc.date.accessioned.none.fl_str_mv 2020-09-03T14:31:43Z
dc.date.available.none.fl_str_mv 2020-09-03T14:31:43Z
dc.type.spa.fl_str_mv Trabajo de grado - Maestría
dc.type.coarversion.fl_str_mv http://purl.org/coar/version/c_970fb48d4fbd8a85
dc.type.driver.spa.fl_str_mv info:eu-repo/semantics/masterThesis
dc.type.content.spa.fl_str_mv Text
dc.type.redcol.spa.fl_str_mv http://purl.org/redcol/resource_type/TM
dc.identifier.uri.none.fl_str_mv http://hdl.handle.net/1992/44083
dc.identifier.pdf.none.fl_str_mv u827478.pdf
dc.identifier.instname.spa.fl_str_mv instname:Universidad de los Andes
dc.identifier.reponame.spa.fl_str_mv reponame:Repositorio Institucional Séneca
dc.identifier.repourl.spa.fl_str_mv repourl:https://repositorio.uniandes.edu.co/
url http://hdl.handle.net/1992/44083
identifier_str_mv u827478.pdf
instname:Universidad de los Andes
reponame:Repositorio Institucional Séneca
repourl:https://repositorio.uniandes.edu.co/
dc.language.iso.es_CO.fl_str_mv eng
language eng
dc.rights.uri.*.fl_str_mv https://repositorio.uniandes.edu.co/static/pdf/aceptacion_uso_es.pdf
dc.rights.accessrights.spa.fl_str_mv info:eu-repo/semantics/openAccess
dc.rights.coar.spa.fl_str_mv http://purl.org/coar/access_right/c_abf2
rights_invalid_str_mv https://repositorio.uniandes.edu.co/static/pdf/aceptacion_uso_es.pdf
http://purl.org/coar/access_right/c_abf2
eu_rights_str_mv openAccess
dc.format.extent.es_CO.fl_str_mv 21 hojas
dc.format.mimetype.es_CO.fl_str_mv application/pdf
dc.publisher.es_CO.fl_str_mv Uniandes
dc.publisher.program.es_CO.fl_str_mv Maestría en Ingeniería Industrial
dc.publisher.faculty.es_CO.fl_str_mv Facultad de Ingeniería
dc.publisher.department.es_CO.fl_str_mv Departamento de Ingeniería Industrial
dc.source.es_CO.fl_str_mv instname:Universidad de los Andes
reponame:Repositorio Institucional Séneca
instname_str Universidad de los Andes
institution Universidad de los Andes
reponame_str Repositorio Institucional Séneca
collection Repositorio Institucional Séneca
bitstream.url.fl_str_mv https://repositorio.uniandes.edu.co/bitstreams/b7f39668-5972-47fc-9b3b-43692ecb2709/download
https://repositorio.uniandes.edu.co/bitstreams/ead8ec06-9a48-4f97-b782-c5a04f00c483/download
https://repositorio.uniandes.edu.co/bitstreams/4d3577cc-a7d5-4433-bf57-d47dad6e31e1/download
bitstream.checksum.fl_str_mv 698a22f167f3215841fdb8b8eb6581a8
d56816af7cb64c55a5d639d9b3eeff02
eaa8234ff2112e72460028dec17044ad
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
MD5
repository.name.fl_str_mv Repositorio institucional Séneca
repository.mail.fl_str_mv adminrepositorio@uniandes.edu.co
_version_ 1808390292314783744

Publicaciones similares