Tesis para optar al grado de Magíster en Ciencias de la Ingeniería, Mención Eléctrica / Memoria para optar al título de Ingeniero Civil Eléctrico / 01/04/2021

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.

Ingeniero Civil Eléctrico / Una Ciudad Inteligente es un modelo de planificación y gestión, enfocado en mejorar la sustentabilidad, seguridad y eficiencia de una ciudad, con el objetivo de mejorar la calidad de vida de sus habitantes. Para ello, integra diferentes sistemas, tales como: energía, transporte, infraestructura, servicios, etc. en un gran ecosistema, gracias a los desarrollos tecnológicos actuales. Particularmente, en áreas de transporte, los esfuerzos se enfocan en la descongestión de la ciudad, el aumento del acceso, la optimización de costos y consumo de combustible y los impactos ambientales y sociales. Las telecomunicaciones son parte de las tecnologías claves para el desarrollo de Ciudades Inteligentes, ya que proporcionan una capa de interconexión fundamental para el proceso de integración. Sus aportes tendrán un impacto sustancial en el diseño de nueva infraestructura, sistemas de control de congestión y protocolos de enrutamiento inteligente, sistemas de seguridad activos y pasivos, además de la conducción autónoma. Estos nuevos mecanismos requieren de un modelo detallado subyacente, para estudiar y mejorar las técnicas de gestión del flujo vehicular implementadas en la actualidad, en el cual la dinámica del vehículo tiene un impacto significativo en el proceso de toma de decisiones de los mismos. Este trabajo aborda tres estudios, con el fin de brindar soluciones al mejoramiento del flujo vehicular en una ciudad. En primer lugar, se desarrolla un modelo de flujo vehicular microscópico, compuesto por dos mecanismos básicos: el encargado de la dinámica individual de un vehículo y el seguimiento entre los mismos, bajo criterios de seguridad. Luego, en una segunda parte, se realiza un estudio sobre las propiedades geométricas de diferentes rutas, con el objetivo de diseñar una métrica de sinuosidad de las calles y determinar cómo esta puede afectar al flujo. Finalmente, se programa una plataforma de ruteo vehicular simulando sectores de una ciudad con plano urbanístico ortogonal, cuyo sistema de ruteo se compone de un grafo y el algoritmo Dijkstra. Dicha plataforma, escalable y modular, integra el modelo microscópico junto a un nuevo sistema de aceleración, haciendo el comportamiento vehicular mucho más real, y adicionando el uso de semáforos como mecanismos de control. Los resultados confirman que el modelo microscópico satisface las condiciones de conducción humana en un ambiente urbano, contribuyendo al diseño de futuros sistemas de gestión de tráfico, lo que permite obtener modelos más precisos de simulación. Por otro lado, la velocidad depende de varios aspectos de la vía, como la distancia entre las curvas, los radios de las mismas y la circunferencia del arco agregado, derivando en una métrica de sinuosidad proporcional al inverso de la velocidad promedio de los vehículos simulados. Finalmente, utilizando un grafo, cuyos segmentos estén caracterizados por pesos, en conjunto con Dijkstra, es posible determinar la mejor ruta, bajo cierto criterio de optimización, dado el punto de origen y destino de un vehículo. Esta plataforma de ruteo vehicular es, por tanto, una herramienta útil para diseñar, simular y estudiar nuevos modelos sobre la dinámica, control y ruteo de los vehículos, en ciudades inteligentes.

Ingeniero Civil Industrial / La empresa Xerox en Chile ofrece el servicio de reparación de equipos de oficina tales como impresoras y fotocopiadoras. Para ello cuenta con una dotación de técnicos que se trasladan hacia los clientes para realizar el trabajo. La estrategia de la empresa es atender las solicitudes de trabajo tan pronto como sean recibidas, es decir, organizar y atender durante el día las llamadas que van recibiendo por parte de sus clientes. Cuando esto no es posible, ciertos clientes son postergados para otro día. Como consecuencia de dicha estrategia, las llamadas que no alcanzaron a ser atendidas a tiempo por los técnicos llegó al 54% para el periodo 2002-2003 en la ciudad de Santiago, considerándose esto un deterioro en la calidad de atención. En este trabajo se propuso disminuir la cantidad de clientes postergados junto con la distancia recorrida mediante la planificación eficiente de las rutas. La metodología consistió en abordar la situación como un problema de ruteo de vehículos, donde además los tiempos de viaje no son fijos, sino que dependen de la hora del día. Este problema es conocido como el Problema de Ruteo de Vehículos con Dependencia del Tiempo (TDVRP por sus siglas en inglés). Debido a la necesidad de encontrar soluciones rápidas, el problema fue resuelto mediante Algoritmo Genético, el cual consiste en generar un conjunto de rutas aleatorias de clientes y luego intercambiar entre sí pequeños segmentos para crear nuevas y mejores rutas, imitando de tal forma el proceso de recombinación genética presente en la naturaleza. Se consideró también un cambio en la política de atención, donde ahora todos los llamados serían atendidos al día siguiente para una mejor planificación. Los resultados se obtuvieron para una semana de operación. Las soluciones alcanzaron tasas de retraso entre 6-20% en comparación con el 59% de la situación real de aquella semana. Respecto de la dependencia del tiempo, los resultados mostraron que no hubo diferencias significativas al incluir variación en los tiempos de viaje en comparación con tiempos de viaje fijos. Se concluye que el cambio en la estrategia de atención y una buena planificación inicial mejoran ostensiblemente la cantidad de clientes que deben ser postergados, esto implica una oportunidad de mejora en la calidad de servicio que ofrece Xerox. Por otro lado, incluir dependencia de la hora del día en los tiempos de viaje no significó un aporte al modelo en cuanto calidad de las soluciones. Aquello podría explicarse por tiempos de servicio mayores que los tiempos de viaje, haciendo que el impacto de estos últimos sean irrelevantes para la solución del modelo en una ciudad.