Una heuristíca de construcción para el problema del vendedor viajero probabilístico

Vista sencilla de ítem
dc.contributor.advisorLamas Vilches, Alejandro
dc.contributor.authorCorrea Simonet, Lucia
dc.contributor.editorFacultad de Ingeniería
dc.date.accessioned2020-08-27T19:41:26Z
dc.date.available2020-08-27T19:41:26Z
dc.date.issued2010
dc.descriptionTesis (Magíster en Logística y Gestión de Operaciones)es
dc.description.abstractEsta tesis tiene como motivación principal presentar una heurística que entregue buenas soluciones al Problema del Vendedor Viajero Probabilístico (PTSP), para que éste pueda ser utilizado en problemas de tipo estratégico, como puede ser el problema de diseño de Redes de Distribución (DRD). Esta tesis propone una heurística de construcción basada en el Vecino Más Cercano (VMC), de baja complejidad para el PTSP. Se analizará en forma asintótica los costos asociados a esta heurística aplicada al PTSP que llamaremos VMC-PTSP extendida, además de realizar este mismo análisis a la heurística existente propuesta por Tang y Miller-Hooks (2005) que nombraremos por heurística VMC-PTSP tradicional. Se realizará un análisis a las heurísticas VMC-PTSP tradicional y extendida, utilizando un enfoque aproximado similar al presentado por Lamas (2007), en la mejora local 2-p-opt. El enfoque aproximado, acota términos considerados en las heurísticas VMC-PTSP tradicional y extendida, evaluando sólo un subconjunto de ellos que deberían ser incluidos en el cálculo de los costos de ingresar nodos a las heurísticas. Para la heurística VMC-PTSP tradicional y extendida con probabilidad homogénea de demanda, se tendrá de antemano factores de acotamiento para evaluar sólo una parte del total de términos. El factor de acotamiento entrega un porcentaje de error, de comparar éstas heurísticas acotadas con las heurísticas considerando todos los términos. Se disminuye la complejidad de la heurística VMC-PTSP tradicional de 0(n3) a 0(n2) al acotarla Lo anterior se sustenta en el comportamiento asintótico de los términos de la heurística, que permite no computar a todos y que el problema no se vea afectado por la cantidad de nodos.es
dc.identifier.urihttp://repositorio.unab.cl/xmlui/handle/ria/15076
dc.language.isoeses
dc.publisherUniversidad Andrés Belloes
dc.subjectProgramación Heurística.es
dc.subjectFlujo de Redeses
dc.subjectCostos del Tratamientoes
dc.subjectChilees
dc.titleUna heuristíca de construcción para el problema del vendedor viajero probabilísticoes
dc.typeTesises
Archivos
Bloque original
Mostrando 1 - 1 de 1
No hay miniatura disponible
Nombre:
a73245_Correa_L_Una_heuristica_de_construccion_para_2010.pdf
Tamaño:
5.84 MB
Formato:
Adobe Portable Document Format
Descripción:
TEXTO COMPLETO ESPAÑOL
Descargar
Bloque de licencias
Mostrando 1 - 1 de 1
No hay miniatura disponible
Nombre:
license.txt
Tamaño:
1.71 KB
Formato:
Item-specific license agreed upon to submission
Descripción:
Descargar
Colecciones
FIng - Trabajos de Titulación Post-Grado