Lamas Vilches, AlejandroCorrea Simonet, LuciaFacultad de Ingeniería2020-08-272020-08-272010http://repositorio.unab.cl/xmlui/handle/ria/15076Tesis (Magíster en Logística y Gestión de Operaciones)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.esProgramación Heurística.Flujo de RedesCostos del TratamientoChileTesis