Magíster en Ciencias de la Ingeniería, Mención Transporte. Ingeniero Civil / Esta tesis tiene como objetivo desarrollar una metodología híbrida para resolver un problema de ruteo de vehículos repartidores de mercadería motivado por un caso práctico de una cadena de supermercados que ofrece un servicio de e-commerce. La formulación considera una primera etapa heurística en la que se genera un conjunto diversificado de rutas y una segunda etapa en donde, con un modelo exacto, se selecciona el subconjunto de rutas que minimiza el costo total de ejecución de las rutas. La modelación considera ventanas de tiempo duras para las visitas a los clientes, duración de los viajes dependientes del tiempo, cola en las zonas de carga de la bodega y múltiples viajes por vehículo. La primera etapa consiste en una heurística greedy basada en la propuesta de Ioannou et al. (2001), según la ponderación de tres parámetros, se selecciona el cliente a insertar junto a su posición dentro de la ruta en construcción. Estos parámetros buscan representar el impacto de una inserción tanto en los clientes aún no ruteados, así como sobre los clientes de la ruta en donde se realiza la inserción y el propio impacto para el cliente a insertar. Se emplean diversas estrategias de diversificación para obtener un conjunto variado de rutas. La segunda etapa, consiste en un modelo exacto con una formulación que emplea como variables las rutas previamente construidas. Dicho modelo considera el proceso de cola que se origina en la bodega cuando más de un vehículo debe ser cargado simultáneamente para realizar un nuevo viaje; este planteamiento supone un máximo de dos viajes por vehículo y una única bodega. Se realiza también una generalización del modelo anterior en el que se permite que los vehículos realicen n viajes y que existan múltiples bodegas. Para definir una cota inferior al problema resuelto se propone una formulación basada en generación de columnas para resolver el problema con máximo dos viajes y bodega única. Se plantea un esquema de simulación para definir la calidad de servicio ofrecida a los clientes en caso de emplear la metodología formulada. Los resultados obtenidos con el modelo mixto presentan ahorros, en comparación a emplear la heurística por sí sola, en gran parte debido a la minimización de la flota. Calculando un promedio de todos los escenarios estudiados, un 75,5% del costo total de la solución se debe a los costos correspondientes al uso de la flota. De aquí la importancia de emplear un modelo que considere todos los procesos involucrados al momento de definir la flota requerida para servir un conjunto de clientes.

En esta memoria se desarrolla una estrategia de control predictivo híbrido para un sistema de transporte público, que comprende acciones de control en tiempo real sobre buses y semáforos del sistema. El objetivo de esta estrategia es optimizar el funcionamiento de una flota de buses, esto es reducir tiempos de espera en paraderos y demoras en semáforos. Se expone los trabajos y formulaciones existentes sobre control de tráfico en tiempo real, con énfasis en el tema de prioridad para transporte público. Basándose en el tratamiento dado al transporte privado en la literatura especializada, en la que se da gran importancia a los largos de cola, se propone una formulación para la demanda de transporte privado. Asimismo, se formula un problema de control de semáforos y buses que contempla impactos en el transporte privado. Para lograr el objetivo propuesto se diseña un simulador de tráfico que se integra a una plataforma de simulación de transporte público. Sobre este sistema integrado se propone y prueba diferentes metodologías de control que incluyen estrategias de holding (retención en paraderos) y station skipping (salto de paraderos) y extensión y adelantamiento de verde con prioridad para buses en semáforos. Cada una de estas estrategias se verifica en forma separada y también de manera integrada, lo cual permite constatar que la estrategia integrada ofrece mejoras importantes. Se evalúa la sensibilidad de la estrategia integrada, con respecto a las condiciones de demanda, lo que revela la importancia de la distribución de demanda privada por sobre la magnitud de la misma. La estrategia se sensibiliza también con respecto a los parámetros de control, lo que muestra alta sensibilidad con respecto al horizonte predicción. Se concluye que la estrategia genera buenos resultados, disminuyendo los tiempos de espera en aproximadamente un 45% y demoras en semáforos en aproximadamente un 56% con respecto a un sistema sin control. Por su parte, la regularidad de intervalos, se mantiene en niveles similares. Sin embargo, para lograr tales resultados, se requiere de la implementación de tecnología que permita estimar tiempos de llegada a semáforos, cargas de pasajeros en buses y destino de los viajes de cada pasajero. Por otro lado, los desarrollos logrados durante este trabajo permiten continuar con la investigación en esta línea, así como la extensión a casos más complejos.

Magíster en Gestión de Operaciones / Ingeniero Civil Industrial / En la presente Tesis, se propone una metodología para enfrentar el Problema Dinámico de Ruteo de Técnicos con Ventanas de Tiempo. La naturaleza dinámica del problema está comprendida en los clientes que aparecen dinámicamente y deben ser asignados a la mejor ruta posible mediante algún criterio. La metodología propuesta puede ser resumida en tres pasos: - Usar información histórica para crear nodos ficticios, los que sirven como puntos de espera (y de covering) para los vehículos que han terminado sus tareas en agenda. - Resolver el problema de ruteo estático, que comprende los nodos reales y los puntos de espera, mediante Generación de Columnas. - Añadir las llamadas entrantes usando la heurística Generación de Columnas Dinámica. La Generación de Columnas Dinámica es una heurística que se basa en la propuesta de Chen, la cual genera nuevas columnas usando la información de los nuevos nodos junto con un subconjunto de las columnas generadas anteriormente en la resolución del problema estático. Mientras se generan nuevas columnas, estas pueden ser añadidas al conjunto total de columnas y resolver el nuevo problema de optimización. Esta heurística permite encontrar nuevas soluciones muy rápido, por lo cual corresponde a una buena opción para resolver problemas dinámicos donde las decisiones son tomadas en tiempo real. En cuanto a los resultados numéricos, el método propuesto (SCTTP-DCG), obtiene mejores resultados que la implementación dinámica más intuitiva realizable: el ruteo estático de nodos más la agregación Greedy de llamados dinámicos (TTP-Greedy). Por otra parte, el ruteo estático de nodos con la agregación de nodos dinámicos por medio de Generación de Columnas Dinámico (TTP-DCG) obtiene mejores resultados en comparación SCTTP-DCG. La explicación a este fenómeno tiene que ver con dos efectos: TTP-DCG gana las bondades de la inserción por medio de DCG y, además, ahorra en tiempos de desplazamiento pues no tiene que viajar a los nodos ficticios. Si bien era lógico que este fenómeno existiera, se esperaba que el SCTTP-DCG lograra recuperar los costos extra de transporte por medio de menor desplazamiento gracias a la buena ubicación frente a los llamados venideros.

Magíster en Gestión de Operaciones / Ingeniero Civil Industrial / Skretting es una empresa dedicada a la producción de alimentos para peces y camarones. Una de sus principales fi liales se encuentra en Chile, con una fuerte producción de alimentos para Salmonideos. La empresa se encarga de la producción y distribución del alimento a muchas de las salmoneras del sur de Chile. El problema al cual se enfrenta la empresa es como distribuir el alimento entre sus clientes de manera e ciente. Tales planifi caciones son realizadas manualmente por el encargado de la empresa y luego distribuidas por la empresa TransMarko, la cual cobra por tonelada a distribuir. El objetivo de esta tesis es diseñar y desarrollar un prototipo que le permita a la empresa generar plani ficaciones e cientes. Para generar rutas y asignaciones de demandas efi cientemente, se modeló el problema como un problema de ruteo de vehículos heterogéneos con ventanas de tiempo. La formulación resulto difícil, por lo cual se optó por el desarrollo de heurísticas de tipo metaheurística GRASP. Como Skretting no paga los costos operacionales de los barcos, se generaron dos heurísticas, donde una de ellas optimiza con respecto a los costos de contrato que tiene Skretting con TransMarko y la otra plani ca optimizando los costos operacionales de los barcos (i.e. costos directos en los que incurre la empresa TransMarko). El prototipo fue desarrollado en Java y fue diseñado para una fácil comprensión y evaluaci ón de las soluciones. Además se trabajó en la construcción de los datos necesarios para poder ejecutar las heurísticas, obtener resultados y comparar las soluciones. Entre estos datos destacan las coordenadas, áreas y clientes de cada uno de los más de 100 centros de cultivo que demandan a Skretting y la generación de una matriz con las distancias (alrededor de 5000) entre cada uno de esos centros de cultivo. Se utilizó el prototipo para ejecutar 5 días de planifi cación. Los resultados que arrojó la heurística que optimizaba en torno los costos reales muestran una reducción de un 20% de las millas navegadas y un 21% menos de días-barco utilizados comparados a la planifi cación manual. Por otro lado, la heurística de costos de contrato no arrojó una reducción de las millas y días-barco tan relevantes, pero si mostró una gran mejora en el aprovechamiento de los barcos acorde a los costos de contrato.

En este trabajo se presenta una heurística que mejora los resultados operacionales en el despacho de pedidos de cerveza. Este trabajo está, especializado en las características de CERVECERÍAS CHILE S.A., empresa dedicada a la elaboración y transporte de cervezas a lo largo de todo Chile. La problemática diaria que se aborda en este proyecto consiste en la asignación de 400 clientes, en promedio, a rutas específicas de entrega, tomando en cuenta una flota homogénea de vehículos y restricciones horarias en la entrega de los pedidos. Se considera que la demanda de los productos es conocida y que los productos están disponibles para la entrega. Es importante notar que en este problema no existe una limitante en el número de vehículos disponibles para la entrega del producto, debido a que la empresa tiene una gran variedad de proveedores de transporte que facilitan el arrendamiento de vehículos. La formulación de la heurística desarrollada asegura el cumplimiento de las restricciones temporales en la entrega de productos y además minimiza los costos asociados al transporte diario de los productos para satisfacer la demanda de los clientes. La solución del problema se enfrentó con la técnica de Generación de Columnas. La base de esta metodología es dividir el problema en dos etapas: La primera etapa considera la generación de rutas factibles conocida como Sub Problema, y una segunda etapa la formulación de un problema de programación lineal que escoge mediante un modelo de optimización las soluciones que serán consideradas como rutas factibles para el despacho de los pedidos. Estas rutas corresponden a aquellas que tienen un costo reducido negativo para mejorar la función objetivo. El modelo decide qué cliente es asignado a cada viaje y horarios en que se realiza dicho viaje. El modelo se aplicó a datos que representan situaciones reales analizando principalmente el comportamiento de los resultados entregados por la heurística respecto a la configuración de rutas generadas y a la naturaleza de las rutas factibles generadas. El resultado final de la heurística utilizada contempla un aumento en el nivel de servicio, dado que logra entregar los pedidos cumpliendo las restricciones horarias de los clientes. Lo anterior refleja también una mejora de un 50% aproximadamente en las utilidades de los pedidos diarios.

Magíster en Ciencias de la Ingeniería, Mención Transporte / Ingeniero Civil Matemático / El objetivo de esta tesis es formular un modelo que integre el Pickup and Delivery Problem (PDP) y la localización óptima de los depots de distribución, el cual llamaremos Problema de Localización y Ruteo con Pickup and Delivery (PLRPDP). Este problema se plantea y tiene una gran variedad de aplicaciones en la industria, como por ejemplo en el courier, en el transporte de pasajeros, o en el transporte de alimentos perecibles, y por lo tanto es de suma importancia cuando existe un sistema de alta demanda con diferentes opciones en relación a la ubicación de los depots. Para modelar este problema se propone un esquema de generación de columnas, donde el problema maestro resultante es similar al del modelo propuesto por Berger et al. (2007), pero en este caso, el subproblema es un PDP. Para resolver este subproblema y poder generar columnas factibles para el problema maestro, se propone un algoritmo de label-setting, que resuelve el problema de camino más corto, con restricciones de Pickup and Delivery y ventanas de tiempo. Además se propone un conjunto de heurísticas para acelerar este proceso. Para validar el modelo, se hace una implementación del esquema de generación de columnas, el cual se prueba en diferentes instancias, algunas ya existentes en la literatura actual, como también desarrolladas en este trabajo. Destacando dentro de estas últimas, las instancias clusterizadas y las de tipo corredor, las cuales por su geometría especial hacen que la localización de los depots sea de suma importancia. También se hace un análisis detallado de como los costos de apertura de los depots inciden en la solución óptima. Finalmente se presentan resultados del rendimiento de nuestra implementación para cada una de las instancias.

Para tomar decisiones sobre alternativas para reducir los efectos negativos de la congestión, se debe planificar el transporte. La planificación requiere, según el enfoque clásico, el conjunto secuencial de cuatro (04) modelos de transporte para tomar decisiones pertinentes. El cuarto y último modelo corresponde a la asignación de tráfico, el cual requiere de la función BPR. La función BPR (Bureau of Public Roads) estima el tiempo de viaje (Tf) respecto al flujo de transporte (V), a la capacidad (C), al tiempo de viaje en flujo libre (to) y a los parámetros (α y β), los cuales deben reflejan el desempeño de la infraestructura vial. En Lima Metropolitana, como en otras ciudades de Latinoamérica, suele emplearse valores estandarizados de α y β en la función BPR, esto significa que dichos valores no están ajustado a las condiciones actuales de la ciudad. A partir de ello, se genera incertidumbre en la estimación de los datos de salida de la función (tiempo de viaje) y en efecto, incertidumbre en la eficiencia de las decisiones para disminuir la congestión. El objetivo de la presente investigación es calibrar la función BPR, es decir, estimar los valores de α y β. Y, en consecuencia, asegurar que esta represente, de manera confiable, el comportamiento vial en Lima Metropolitana, específicamente en la vía colectora: Avenida San Luis. La metodología se desarrolla en tres (03) etapas: Levantamiento de información, determinación de los parámetros y análisis de los resultados. Como resultado de la calibración se obtiene valores de α=2.22 y β=1.19, y se demuestra que la función calibrada representa de forma adecuada los tiempos de viaje observados en la vía en estudio. En cambio, la utilización de valores estandarizados no resulta ser la mejor para dicha representación, y por el contrario, presenta errores significativos. / In order to take decisions about alternatives to reduce the congestion’s negative effects, transport must be planified. Planification requires, according to the classic approach, the four-model transport sequential set to take the pertinent decisions. The fourth and last model corresponds to the traffic allocation, that requires the BPR function. The BPR function (Bureau of Public Roads) estimates the travel time (Tf) regarding the transport’s flow (V), the capacity (C), the travel time in free flow (to) and the parameters (α y β), that reflect the performance of the road infraestructure. In the city of Lima, as in others Latinamerican cities, it is common to use standarised values of α and β in BPR function. That means that those values are not adjusted to the city’s current conditions. On that basis, uncertainty arises on the function of the data output (travel time) and also on the efficiency of the decisions taken to diminish the traffic congestion. The main approach of this investigation is to calibrate the BPR function, that means, to estimate the functions of α y β, and, because of it, ensure that this function represents the traffic behavoir in the city of Lima in a reliable way, specifically in the collector road: San Luis Avenue. The methodology is developed in three stages: gathering of information, determination of the parameters and analysis of the results. As a result of the calibration, the values obtained are α=2.22 and β=1.19, and it is demonstraded that the calibrated functions represent in a reliable way the travel times observed in the studied avenue. However, the use of standarised values is not the best one for such representation, and, on the contrary, it shows significative errors. / Tesis