Título: Problema de ordenamiento de vehículos con múltiples depósitos

Marco de Trabajo: Maestría

Área de desarrollo: Investigación Operativa, Transporte

Autor: Sebastián Alaggia

Contacto: salaggia@fing.edu.uy

Día: MARTES

Hora: 10:15

Palabras Claves: Programación lineal entera, Optimización Combinatoria, Ordenamiento

Resumen:
El problema de ordenamiento de vehículos se presenta en el contexto de la planificación a mediano plazo de un sistema de transporte colectivo público; toma como insumo la definición de un conjunto de viajes a realizar y busca minimizar costos de operación de la compañía de ómnibus. No se considera el ordenamiento del personal, ni detalles de la operativa diaria como la asignación individual de chóferes a ómnibus, embotellamientos, roturas de móviles, entre otros. En esta tesis de maestría que está en curso, se estudia el problema de ordenamiento de vehículos con múltiples depósitos (MDVSP, siglas de Multi Depot Vehicle Scheduling Problem) y se aplica a un caso real. El MDVSP consiste encontrar un conjunto de secuencias de viajes, también llamado conjunto de servicios, que cubran todo los viajes a realizar por una flota de vehículos que está distribuida entre varios depósitos. Un viaje está dado por un origen, un destino, una hora de partida y una hora de llegada. Se dice que dos viajes son compatibles si el tiempo requerido para ir del destino del primer viaje al origen del segundo, no supera al tiempo entre la salida del segundo y la llegada del primero. Cada servicio está compuesto por viajes compatibles y debe ser realizado por un vehículo, por tanto la cantidad servicios debe ser menor o igual al tamaño de la flota y su costo debe ser mínimo. El costo utilizado en este trabajo es la distancia recorrida por un vehículo sin transportar pasajeros durante un servicio (viaje expreso). El MDVSP es un problema NP completo (Bertossi et al, 1987) si la cantidad de depósitos es mayor o igual a 2. En la literatura se encuentran dos formas de modelar este problema: (1) se trabaja sobre una red de flujos donde un camino de la fuente al pozo es un servicio y se calcula un conjunto de servicios óptimo partiendo de los viajes compatibles; (2) se elige un subconjunto de servicios óptimo a partir de servicios factibles buscando cubrir todos los viajes. En el primer modelo se trabaja con los servicios de forma indirecta, en el segundo se trabaja directamente con ellos lo que facilita el manejo e inclusión de restricciones a los servicios. Para utilizar el segundo modelo es necesario desarrollar un método de creación de un conjunto inicial de servicios, una solución inicial. En este trabajo se crea ese conjunto inicial mediante una heurística de inserción; en cada paso se trata de insertar un viaje en alguno de los servicios que han sido creados de forma que dicha inserción tenga el menor costo (en kilómetros expresos) posible. Los viajes compatibles se modelan mediante un grafo dirigido cuyo conjunto de nodos representan el conjunto de viajes y los arcos la relación de compatibilidad. Para casos de mediano a gran tamaño visualizar esta relación se vuelve impracticable; por eso se propone representarla por medio de imágenes utilizando la representación matricial del grafo como base y diferentes colores según la compatibilidad existente entre los pares de viajes. También es posible representar de esa manera las soluciones encontradas al solucionar un problema en particular. En este trabajo harán consideraciones sobre la aplicación de esta representación visual para un caso real y uno de laboratorio de menor dimensión. Se mostrará que el caso de laboratorio planteado representa fidedignamente las relaciones de compatibilidad del real, por tanto es viable utilizarlo para probar los algoritmos a utilizar. Referencias: Bertossi, A. A., P. Carraresi, G. Gallo. 1987. On some matching problems arising in vehicle scheduling models. Networks 17 271–281.