Tesis (Maestro en Ciencias, Especialidad en Sistemas Inteligentes) -- Tecnológico de Monterrey, Campus Monterrey. / Título tomado de la pantalla de presentación [como fue visto el 29 de agosto de 2006] Incluye referencias bibliográficas. También disponible en formato impreso.

Tesis para optar al grado de Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas / Memoria para optar al título de Ingeniero Civil Matemático / Estudiamos el problema de bases de peso mínimo en matroides en un contexto donde los pesos en los elementos son inciertos. Inicialmente, para cada elemento $e$ de una matroide $(E,\I)$ se conocerá un conjunto no vacío $A_e \subseteq \mathbb R$, llamado área de incertidumbre, que contiene los posibles pesos del elemento $e$. El algoritmo puede escoger un conjunto de elementos $X\subseteq E$ a consultar, de manera que si un elemento $e$ es consultado se obtiene un peso $w_e \in A_e$ con un costo de consulta $c_e \in \mathbb R$ asociado. El objetivo es encontrar un conjunto $X \subseteq E$ que, al consultarlo, permita calcular una base de peso mínimo independiente del valor de las aristas no reveladas. A estos conjuntos se les llamará consultas factible; tenemos particular interés en encontrar una de costo mínimo. Esto es de especial interés en aplicaciones donde obtener datos exactos es díficil o costoso, pero datos vagos son de fácil acceso. El problema adaptativo bajo análisis competitivo fue estudiado anteriormente. En este trabajo consideramos el caso no adaptativo; es decir, cuando los elementos a consultar se eligen todos al mismo tiempo. Formalizamos el problema, definimos las bases de peso mínimo en el contexto incierto, caracterizamos su existencia y demostramos que son las bases de una matroide. Proveemos una caracterización de las consultas factibles de tamaño mínimo, probamos que los complementos de consultas factibles forman una matroide sencilla y esto nos permite idear un algoritmo que encuentra una consulta factible de costo mínimo con una cantidad polinomial tanto de recursos computacionales como de llamadas al oráculo de independencia de la matroide / FONDECYT Regular N° 1181180 y CMM - Conicyt PIA AFB170001

Magíster en Gestión de Operaciones. Ingeniero Civil Industrial / El desarrollo de nuevas tecnologías en los últimos años, ha permitido reducir de manera significativa los costos de los sistemas GPS y de envío de información; a la vez han existido mejoras en el rendimiento de los algoritmos de optimización y un aumento de la capacidad computacional. Estos tres factores han impulsado la investigación de problemas dinámicos, en los que una parte de la información se va revelando ha medida que transcurre el tiempo, y en particular en problemas complejos como el ruteo de vehículos. En esta tesis se diseñó, implementó y evaluó una solución para el Problema de Ruteo de Vehículos Dinámico con Ventas de Tiempo, la que está basada en el método de descomposición de generación de columnas, que emplea un algoritmo de programación dinámica adaptado especialmente para el subproblema enfrentado. El modelo ocupado en esta tesis está basado en el presentado por Weintraub et al. [1999],que considera en su función objetivo métricas tanto de calidad de servicio como costos operacionales, además una componente de cobertura, la que busca mantener una distribución espacial de los técnicos que permita una reacción temprana a la llegada de los nuevos clientes. Se incluyen también puntos de espera para los vehículos ociosos, al igual que en Briceño [2014], en zonas donde la aparición de nuevos clientes es más probable. Para evaluar la solución, se ocuparon dos casos de estudio que enfrentan problemas dinámicos desarrollados en la ciudad de Santiago. El primero corresponde al servicio técnico de reparaciones de la empresa multinacional Xerox, y el segundo al servicio de emergencias de reparaciones eléctricas de CAM; en ambos casos, el principal objetivo es brindar una alta calidad de servicio, lo que se traduce en bajos tiempos de retraso y espera a sus clientes, que generan en promedio 300 y 200 llamados diarios respectivamente. La implementación de la solución fue realizada en el lenguaje de programación Python ocupando Gurobi como motor de optimización. Cada instancia se compone de una semana real de operación, y fueron generadas a partir de las base de datos históricas de ambos casos. Los resultados muestran que los tiempos de resolución del algoritmo de programación dinámica propuesto, son significativamente menores que los requeridos para resolver el subproblema de generación de columnas directamente como problema de programación entera mixta. Se observa además que el rendimiento de la solución depende fuertemente de la relación entre el número de clientes y vehículos. En el Capítulo 5 de resultados, se analiza en detalle cómo las distintas características de cada instancia, además de las distintas configuraciones de parámetros afectan el rendimiento del algoritmo propuesto.

Magíster en Gestión de Operaciones. Ingeniero Civil Industrial / El trabajo de tesis se realizó en Correos de Chile, empresa con más de 280 años de antigüedad y líder en el mercado postal a nivel nacional, con una participación de mercado cercana al 60% en cartas y de un 30% en paquetería. La empresa tiene ingresos aproximados de más de 90.000 millones de pesos chilenos al año, movilizando más de 250 millones de productos anualmente a nivel nacional. Para poder responder de buena manera frente a este gran volumen de envíos la empresa cuenta con más de 2300 carteros, quienes reparten a lo largo de todo el territorio nacional. El trabajo consistió en la creación de una herramienta de simulación para la evaluación de sus zonas de reparto, la que permite estimar de forma teórica cuál sería el rendimiento de cada una de ellas, utilizando como base para la simulación los datos de la demanda correspondientes al año 2016. Actualmente la empresa no cuenta con alguna herramienta que le permita evaluar rápidamente el rendimiento esperado de sus cuarteles, por lo que les resulta imposible planificar de manera objetiva y eficiente, dejando que muchos de los problemas aparezcan sobre la marcha, lo cual trae muchos problemas asociados como la baja en la calidad de servicio, aumento en postergación de envíos y jornadas laborales muy demandantes para los carteros. La metodología de la tesis consistió en estudiar distintos modelos de estimación de tiempos y de ruteo, analizar la demanda agregada y por sus distintos productos, formular un modelo teórico de simulación, programar el modelo, evaluar el rendimiento teórico de los cuarteles actuales y plantear una nueva zona de reparto para la comuna de Renca. En primera instancia se realizó un diagnóstico de la situación actual para la comuna escogida, analizando las zonas de reparto definidas y evaluando el rendimiento teórico que tendrían, identificando qué zonas tienen carga más elevada y qué zonas están en condiciones de recibir una mayor cantidad de puntos de entrega. La propuesta final considera rediseñar todas las zonas de reparto, redistribuyendo los puntos de entrega entre cada una de ellas, ya que se identificó que existe una oportunidad de mejora importante en la calidad de servicio ofrecida, medida como envíos entregados a tiempo. Según la nueva propuesta, la calidad promedio, medida como porcentaje de productos entregados a tiempo, mejoraría en un 8 %. Finalmente cabe mencionar que la solución propuesta no garantiza ser óptima, pues la definición de zonas de reparto debe alimentarse tanto de criterios cuantitativos como de la experiencia del personal de la empresa, por lo que se podrían identificar mejores zonas de reparto trabajando en conjunto con una mayor cantidad de personas de Correos de Chile

Ingeniero Civil Industrial / Todas las ciudades, a medida que se comienzan a extender y densificar, se ven enfrentadas al complejo fenómeno del sistema de transporte público, donde constantemente está en juego el desafío de lograr transportar una gran cantidad de gente de forma eficiente y efectiva. Actualmente, el sistema de transporte público de Santiago se ve afectado por un problema importante: los usuarios evaden el pago del pasaje. Según cifras recientes del año 2017, el índice de evasión supera el 30%, manteniendo una tasa creciente en el tiempo, y es bajo esta preocupación que se propone el proyecto FONDEF Desarrollo de tecnologías para el control de la evasión en el transporte público . Este proyecto busca desarrollar algoritmos eficientes para la resolución de un modelo de fiscalización a gran escala con el fin de mejorar los índices de efectividad del sistema de fiscalización actual y es en este contexto que se desarrolla esta memoria de título. Los modelos, considerados en el marco del proyecto, consisten en una estrategia mixta de fiscalización sobre el grafo de paraderos de Santiago, es decir, una densidad de probabilidad de fiscalización dentro del área de cobertura. Sin embargo, la implementación de estos resultados al sistema no es directa. Es por este motivo que este trabajo busca implementar un modelo de calendarización, que condense un estado probabilístico a una respuesta humanamente realizable, pero que a la vez sea eficiente en su ejecución. En virtud de este objetivo, se implementan dos modelos de calendarización diferentes; uno estático, que mantiene el sistema actual de fiscalización por paraderos, y uno dinámico, que se ajusta a sistemas de fiscalización implementados en otros países y permite la fiscalización con los buses en movimiento. Esta segunda estrategia permite ampliar el abanico de oportunidades que tiene el área de fiscalización del DPTM para cumplir su tarea. Dentro del arista estática, se generan dos propuestas: un sistema más directo, donde se genera una submuestra con su matching respectivo, y un segundo sistema más desarrollado, donde se genera una combinación de turnos a realizar. Generando una diferencia de hasta 92% en los costos de transporte entre estos modelos. Con respecto al modelo dinámico, se mejora en un 42% la capacidad de ejecutar correctamente los resultados de fiscalización. Esta mejora corresponde a la comparación de un modelo aleatorio con respecto a un modelo de decisión dinámica glotón por tramos. A modo de conclusión se propone la implementación del sistema estático en el corto plazo, mientras se trabaja en la formulación de modelos de decisión dinámicos más robustos a los utilizados actualmente junto con la generación de las herramientas necesarias para su correcta implementación. Como trabajo futuro se propone estudiar la posible implementación de un modelo híbrido que mantenga características tanto estáticas como dinámicas.