DII CGO
inicioir al DIIbuscar
fcfm
top
topleft
analisis de complejidad y algoritmos para algunos problemas

Los problemas de recolección y entrega constituyen una clase importante de problemas de ruteo de vehículos en donde objetos o individuos deben ser recolectados y distribuidos. Estos problemas poseen numerosas aplicaciones en diversas areas como la logística, los servicios de ambulancias y la robótica. En esta charla hablaré sobre algunos aspectos de este tipo de problemas que estudié en mi tesis. Comenzaré con el estudio de la complejidad del problema recolección y entrega con rutas parciales fijas y algunas de sus relajaciones. Luego presentaré un algoritmo exacto para determinar la factibilidad de instancias del denominado problema de transporte a la orden basado en la programación por restricciones. Finalmente describiré un algoritmo híbrido para el problema de transporte a la orden dinámico en donde las órdenes de servicio pueden ser recibidas en tiempo real. El algoritmo combina, en paralelo, una versión modificada del algoritmo exacto de programación por restricciones y una heurística de búsqueda tabú.