Una heuristíca de construcción para el problema del vendedor viajero probabilístico
Cargando...
Archivos
Fecha
2010
Autores
Profesor/a Guía
Facultad/escuela
Idioma
es
Título de la revista
ISSN de la revista
Título del volumen
Editor
Universidad Andrés Bello
Nombre de Curso
Licencia CC
Licencia CC
Resumen
Esta 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.
Notas
Tesis (Magíster en Logística y Gestión de Operaciones)
Palabras clave
Programación Heurística., Flujo de Redes, Costos del Tratamiento, Chile