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.
| Identifer | oai:union.ndltd.org:UCHILE/oai:repositorio.uchile.cl:2250/112259 |
| Date | January 2012 |
| Creators | Rojas Mejias, José Antonio |
| Contributors | Cortés Carrillo, Cristián, Facultad de Ciencias Físicas y Matemáticas, Departamento de Ingeniería Industrial, Weintraub Pohorille, Andrés, Ordóñez Pizarro, Fernando, Gendreau, Michel |
| Publisher | Universidad de Chile |
| Source Sets | Universidad de Chile |
| Language | Spanish |
| Detected Language | Spanish |
| Type | Tesis |
Page generated in 0.0022 seconds