Improved Time Bounds for Exact Algorithms of the Shortest Path Tour Problem with Time Windows

Ortega Cadavid, Pablo

Publicación:
Improved Time Bounds for Exact Algorithms of the Shortest Path Tour Problem with Time Windows

authorProfile.id.code	202021700
dc.contributor.advisor	Medaglia González, Andrés
dc.contributor.advisor	Duitama Castellanos, Jorge Alexander
dc.contributor.author	Ortega Cadavid, Pablo
dc.date.accessioned	2026-02-11T13:15:18Z
dc.date.available	2026-02-11T13:15:18Z
dc.date.issued	2025-12-02
dc.description.abstract	The Shortest Path Tour Problem with Time Windows (SPTPTW) seeks the minimum-cost path between two nodes in a directed graph while visiting exactly one node from each ordered subset and respecting service times and time windows. The problem is NP-hard and existing exact methods, mainly labeling algorithms, often suffer from high memory usage and exponential growth of partial paths. This work introduces new backward temporal bounds that compute latest feasible arrival and reachability times to prune infeasible partial solutions early. In addition, a pulse-based exact algorithm is proposed that explores paths through depth-first search with dominance and bounding rules, requiring substantially less memory than labeling approaches. Computational experiments on multiple instance types show that the proposed bounds significantly reduce the search space and improve runtime, with pulse variants achieving competitive performance and lower memory consumption.
dc.description.degreelevel	Pregrado
dc.format.extent	5 páginas
dc.format.mimetype	application/pdf
dc.identifier.instname	instname:Universidad de los Andes
dc.identifier.reponame	reponame:Repositorio Institucional Séneca
dc.identifier.repourl	repourl:https://repositorio.uniandes.edu.co/
dc.identifier.uri	https://hdl.handle.net/1992/78276
dc.language.iso	eng
dc.publisher	Universidad de los Andes
dc.publisher.department	Departamento de Ingeniería de Sistemas y Computación
dc.publisher.department	Departamento de Ingeniería Industrial
dc.publisher.faculty	Facultad de Ingeniería
dc.publisher.program	Ingeniería de Sistemas y Computación
dc.publisher.program	Ingeniería Industrial
dc.rights	Attribution 4.0 International	en
dc.rights.accessrights	info:eu-repo/semantics/openAccess
dc.rights.coar	http://purl.org/coar/access_right/c_abf2
dc.rights.uri	http://creativecommons.org/licenses/by/4.0/
dc.subject.keyword	Shortest path
dc.subject.keyword	Algorithms
dc.subject.themes	Ingeniería	spa
dc.title	Improved Time Bounds for Exact Algorithms of the Shortest Path Tour Problem with Time Windows
dc.type	Trabajo de grado - Pregrado
dc.type.coar	http://purl.org/coar/resource_type/c_7a1f
dc.type.coarversion	http://purl.org/coar/version/c_ab4af688f83e57aa
dc.type.content	Text
dc.type.driver	info:eu-repo/semantics/bachelorThesis
dc.type.redcol	http://purl.org/redcol/resource_type/TP
dc.type.version	info:eu-repo/semantics/acceptedVersion
dspace.entity.type	Publication
person.identifier.cvlac	https://scienti.minciencias.gov.co/cvlac/visualizador/generarCurriculoCv.do?cod_rh=0000220981
person.identifier.gsid	https://scholar.google.es/citations?user=L29kExQAAAAJ
person.identifier.orcid	0000-0003-1529-0322
relation.isDirectorOfPublication	a6afe9d4-d385-4df6-9085-db7ad5b1cdb9
relation.isDirectorOfPublication	07e4ae59-26ee-4988-9701-129fa965d270
relation.isDirectorOfPublication.latestForDiscovery	a6afe9d4-d385-4df6-9085-db7ad5b1cdb9

Archivos

Bloque original

Mostrando 1 - 2 de 2

Nombre:: Improved Time Bounds for Exact Algorithms of the Shortest Path Tour Problem with Time Windows.pdf
Tamaño:: 194.77 KB
Formato:: Adobe Portable Document Format

Descargar