Magíster en Gestión de Operaciones / Ingeniera Civil Industrial / En el mundo actual la mayoría de los problemas logísticos son dinámicos; sin embargo, la investigación desarrollada hasta hoy se concentra principalmente en enfoques basados en adaptaciones de algoritmos estáticos. El vertiginoso avance de la tecnología ha incrementado significativamente las posibilidades de diseñar modelos de ruteo dinámico, lo que debe ser explotado para mejorar la eficiencia en problemas reales. En esta tesis se aborda el problema que enfrenta el Servicio Técnico de Xerox en Santiago, el cual es una aplicación real del Problema Dinámico de Ruteo de Vehículos con Ventanas de Tiempo. El objetivo es atender a los clientes con el menor retraso posible dentro de los límites factibles, minimizando a la vez los costos de trasporte. La complejidad de este problema radica principalmente en su naturaleza dinámica, ya que la información de las llamadas se conoce una vez que son recibidas durante el día, por lo que las rutas diseñadas deben ser modificadas para incorporar la nueva información cuando entran al sistema nuevos clientes. Para resolver este problema se desarrolló un algoritmo que utiliza la información histórica de las llamadas para definir Idle Points o puntos de espera, a los cuales acuden los vehículos desocupados para anticipar la demanda futura y minimizar los tiempos de respuesta. Además, se considera un sistema de puntuación según la intensidad de la demanda con el cual se premia la cobertura de las zonas con mayor intensidad de demanda y un esquema de Generación Dinámica de Columnas, en el se utilizan las rutas generadas anteriormente para diseñar nuevas columnas cada vez que surge una nueva solicitud de un cliente. El modelo fue implementado computacionalmente en C++ utilizando Ilog Cplex como motor de optimización, con el fin de realizar simulaciones con datos disponibles de la operación real y evaluar su desempeño en comparación a una versión dinámica de un algoritmo Greedy. Respecto a este benchmark se obtienen mejoras de 26% en los costos totales evaluando instancias que corresponden a 120 días de operación real de todos los meses del año. Además, se compara el modelo con dos versiones simplificadas para medir el impacto de incluir la información histórica y el covering en el modelamiento. Se observa que ambas componentes del modelo permiten disminuir los tiempos de espera de los clientes. Finalmente se comparan los resultados obtenidos con la operación manual de Xerox, obteniendo mejoras significativas en el nivel de servicio y una reducción de un 23% en el tamaño de flota requerido para la atención. Se concluye que el enfoque propuesto se adapta de manera satisfactoria a problemas dinámicos cuya prioridad es el nivel de servicio ofrecido a los clientes.

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 / 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.

Cada vez más, las empresas de transporte de viajeros se encuentran enmarcadas por un reto financiero para su supervivencia en un mundo globalizado, y están en busca de una gestión eficiente para optimizar los costes de explotación de las flotas. El principal objetivo es obtener el mínimo coste por kilómetro recorrido de los autobuses durante toda su vida útil, pero sin olvidar la influencia de la edad y del kilometraje sobre los vehículos. Desde un punto de vista puramente económico, es evidente que se obtengan los costes de operación y mantenimiento más bajos en los primeros años de trabajo de los vehículos. Pero cuando se consideran otros tipos de costes, como la compra del vehículo, impuestos, subvenciones o incentivos fiscales, y la necesidad de sustitución por nuevos vehículos dotados de innovaciones tecnológicas en conformidad con las exigentes normas de sostenibilidad y sus altos costes, la optimización económica es un reto para los operadores. Así, la determinación del momento óptimo de reemplazo es una tarea cada vez más dependiente de la disponibilidad, fiabilidad y precisión de los datos que se manejen, debido a la incertidumbre en la predicción de algunos valores y costes, tales como los futuros precios del combustible, costes de mantenimiento y la tasa de utilización. Teniendo en cuenta que este proceso ocurre a nivel global en diferentes sectores, existen diferentes modelos y herramientas de gestión que permiten encontrar al menos una solución para el problema de reemplazo. En este trabajo se han planteado dos modelos clásicos aplicados en problemáticas similares, para adaptarlos a la resolución del caso de flotas de transporte urbano de dos países diferentes, España y Brasil, propiciando así un análisis bajo condiciones y entornos distintos. Con el acceso a los datos reales de las flotas, fue desarrollada e implementada la metodología combinada entre la herramienta gerencial Life Cycle Cost y el modelo matemático de Simulación Monte Carlo, mediante la realización de un análisis estocástico, considerando tanto la edad y el kilometraje promedio anual. El estudio ha demostrado que la inclusión de las variables aleatorias en el proceso de determinación de la edad óptima de cambio, junto con la mejor tasa de utilización de los vehículos en función del kilometraje medio, aporta ventajas al proceso de reemplazo convencional, al permitir una perspectiva más confiable de los futuros escenarios, mediante el análisis probabilístico dependiente de las variables económicas y técnicas. Los resultados obtenidos apuntan hacia la eficiencia del modelo, y que podrá ser utilizado de forma satisfactoria en otros estudios comparativos en flotas de transporte urbano. / The passenger transport companies have been increasingly challenged by financial restrictions for their survival in a globalised world and they are searching out an efficient management to optimise the exploitation costs of the fleets. The main objective is not only reaching the lowest average cost per mile of the buses during their lives, but also reaching such aim considering the influence of the age and mileage over the vehicles. From an economic point of view, it is evident that the operational and maintenance costs must be lower at the first working years of the vehicle. However, when other types of costs are taken into consideration, such as the purchasing price, taxes, subsidies or tax incentives, the need of the replacement for new vehicles endowed with technologic innovations in accordance with sustainable rules and their high costs, the economic optimisation becomes a challenge for the managers. Likewise, the determination of the optimum replacement moment is a more and more dependent task on the availability, reliability and precision of the data in use due to the uncertainty and unreliability when predicting some values and costs, such as future fuel prices, maintenance costs and bus use rate. In view of this process happens at a global level over different sectors of the economy, there are several models and tools of management that leads to a solution to the replacement problem. In this study, two classic modules were applied in similar conditions, however, some changes were required to adapt them for the resolution in two urban transport fleet in two different countries, Spain and Brazil, generating an analysis under different conditions and environments though. Using the access of real date from the two fleets, a methodology was developed combining the Life Cycle Cost tool and the mathematical model of Monte Carlo Simulation, by performing a stochastic analysis considering both age and average annual mileage for optimum vehicle replacement. This study has demonstrated that the inclusion of random variables into the determination process of optimum replacement age together with the best mileage of the vehicle in function of average mileage improve the conventional replacement process since it creates a more reliable perfective on future successes through probabilistic analysis dependent on economic and technical variables. The results suggest that the model is effective, and it could be used satisfactorily in other comparative studies about urban transport fleet. / Cada vegada més, les empreses de transport de viatgers es troben majors reptes financers per a la seva supervivència en un món globalitzat, i estan a la recerca d'una gestió eficient per optimitzar els costos d'explotació de les flotes. El principal objectiu és obtenir el mínim cost per quilòmetre recorregut dels autobusos durant tota la seva vida útil, però sense oblidar la influència de l'edat i del quilometratge sobre els vehicles. Des d'un punt de vista purament econòmic, és evident que s'obti els costos d'operació i manteniment més baixos en els primers anys de treball dels vehicles. Però quan es consideren altres tipus de costos, com la compra del vehicle, impostos, subvencions o incentius fiscals, i la necessitat de substitució per nous vehicles dotats d'innovacions tecnològiques en conformitat amb les exigents normes de sostenibilitat i els seus alts costos, l'optimització econòmica és un repte per als operadors. Així, la determinació del moment òptim de reemplaçament és una tasca cada vegada més dependent de la disponibilitat, fiabilitat i precisió de les dades que es manegen, a causa de la incertesa en la predicció d'alguns valors i costos, com ara els futurs preus del combustible, costos de manteniment i la taxa d'utilització. Tenint en compte que aquest procés ocorre a nivell global a diferents sectors, hi ha diferents models i eines de gestió que permeten trobar almenys una solució per al problema de reemplaçament. En aquest treball s'han plantejat dos models clàssics aplicats en problemàtiques similars, per adaptar-los a la resolució del cas de flotes de transport urbà de dos països diferents, Espanya i el Brasil, propiciant així una anàlisi sota condicions i entorns diferents. Amb l'accés a les dades reals de les flotes, va ser desenvolupada i implementada la metodologia combinada entre l'eina gerencial Life Cycle Cost i el model matemàtic de simulació Monte Carlo, mitjançant la realització d'una anàlisi estocàstica, considerant tant l'edat com la mitjana de quilometratge anual. L'estudi ha demostrat que la inclusió de les variables aleatòries en el procés de determinació de l'edat òptima de canvi, juntament amb la millor taxa d'utilització dels vehicles en funció del quilometratge mitjà, aporta avantatges al procés de reemplaçament convencional, en permetre una perspectiva més fiable dels futurs escenaris, mitjançant l'anàlisi probabilístic depenent de les variables econòmiques i tècniques. Els resultats obtinguts apunten cap a l'eficiència del model, i que podrà ser utilitzat de forma satisfactòria en altres estudis comparatius en flotes de transport urbà. / Sá Riechi, JLD. (2018). Desarrollo de un modelo para la optimización del reemplazo de vehículos para una flota de transporte urbano de pasajeros [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/99567 / TESIS

El plan de carga del buque debe adherirse a las instrucciones de estiba del operador del buque. Estas instrucciones especifican las características generales de cada contenedor que habrá de ccargarse. El plan de carga también debe agilizar las operaciones de transporte en la explanada de la terminal. Presentamos dos algoritmos para generar el plan de carga. El primero utiliza el método de descomposición Lagrangeana. El segundo utiliza la metaheurística tabú. Las companías navieras se enfrentan a un problema extremadamente complejo cuando intentan determinar la composición y ruteo óptimo de su flota. Presentamos un modelo y algoritmo para este problema. El modelo representa los costes operativos de una naviera. También permite la respresentación de buques con diferentes propiedades, puntos y costes de transbordo, retrasos en puerto, y la posibilidad de rechazar una solicitud de transporte. Un caso práctico explora la sensitividad de los resultados a cambios en el precio del combustible. / The vessel loading plan must comply with stowage instructions provided by the vessel operator, which specify characteristics of each container to be loaded. Additionally, the vessel loading plan should expedite transport operations in the yard. We present two vessel planning algorithms. In the first model, the vessel planning problem is formulated as a mixed integer programming (MIP) model and solved using Lagrangean relaxation and branch and bound. In the second model, a tabu metaheuristic is employed. Liner companies face a complex decision problem in determining the optimal fleet composition and routing. We present a model that captures the revenues and operating expenses of a liner company. The model allows for vessel types with different cost and operating properties; transhipment hubs; port delays; regional trade imbalances; and the possibility of rejecting transportation demand selectively. A case study explores the sensitivity of optimal fleet composition and routing to bunker costs.