Seminario de Matemáticas
07 de febrero de 2014
De 13.00 a 14.00 h
De 13.00 a 14.00 h
ITAM, Río Hondo
El Problema de Ruteo de Vehículos y su resolución mediante el método de entropía cruzada
Viernes 7 de Febrero de 2014, 13:00 - 14:00, Salón B5
Dra. Marta Cabo
ITAM
Resumen: El problema de ruteo de vehículos (VRP) es un problema clásico en la investigación de operaciones. Consiste en encontrar el conjunto óptimo de rutas que ha de seguir una flota de vehículos para servir un conjunto de clientes que tienen una demanda determinada. Fue formulado por primera vez por Dantzig y Ramser en 1959 y en 1964 Clarke y Wright propusieron un primer heurístico efectivo. Desde entonces cientos de modelos y algoritmos han hecho de este problema uno de los más estudiados en el ámbito de la investigación de operaciones.
En este seminario explicaremos con más detalle el problema clásico de VRP y los enfoques que existen para su resolución. Para resolver este problema se deben de tomar dos decisiones: qué clientes debe visitar cada vehículo, y en qué orden se visitan. Así pues los enfoques de resolución se basan en qué decisión tomar primero.
El método de entropía cruzada viene motivado por un algoritmo adaptivo para estimar la probabilidad de eventos raros, en entornos estocásticos. Sin embargo resulta sencillo aplicarlo a problemas de optimización. Veremos como aplicarlo, sin necesidad de amplios conocimientos estadísticos. Explicaremos cómo implementar este método para los dos enfoques de resolución del VRP, y los resultados obtenidos.
Organiza: Departamento Académico de Matemáticas
Teléfono(s):
Edgar Possani Ext 3845
Edgar Possani Ext 3845