Optimización combinatoria poliédrica: problemas de rutas-localización

Abstract

Análisis del politipo asociado al problema del ciclo en grafos no dirigidos, con el problema del viajante de comercio generalizado, y con una variante de este para los que se propone un algoritmo de ramificación y corte. Se afronta la resolución del problema de la orientación mediante una técnica de ramificación y corte y también el problema de rutas de vehículos con capacidades, usando el clásico modelo matemático con tres índices, oportunamente reforzado con la incorporación de nuevas familias de restricciones. Se presenta una nueva aplicación de la combinatoria poliédrica en la difusión de tablas estadísticas públicas y se introduce un nuevo problema que generaliza el problema de localización sin capacidades, de gran utilidad en la selección óptima de índices en el diseño de bases de datos. En cada caso la efectividad de las técnicas que se proponen viene avalada por resultados de computaciones que las comparan favorablemente frente a las técnicas propuestas por otros autores para estos mismos problemas