Un problema de barrido de calles

Abstract

El problema de barrido de calles, en inglés Street Sweeping Problem (SSP) es una variante del problema del cartero con viento, en inglés el Windy Postman Problem (WPP), en el cual se deben construir dos recorridos que pasen por cada calle por lo menos una vez en cada dirección, barriendo una dirección en el primer recorrido y la otra dirección en el segundo recorrido. Se estudió el SSP junto con algunas variantes. Se presentó un modelo de programación entera del problema y se consideraron los poliedros definidos por la relajación de programación lineal del problema original. Se descrubrió algunas características de los poliedros asociados en el caso general. También se estudiaron los poliedros asociados a casos particulares de gráficas y sus características. Posteriormente se diseñó e implementó un algoritmo de aproximación para el SSP con garantía 3/2 α + 1 para cualquier gráfica, utilizando como subrutina algún algoritmo de aproximación para el WPP con garantía α. Después se presentó otro algoritmo de aproximación que mejora los algoritmos previos y da una garantía 2 para cualquier clase de gráfica con un tiempo polinomial de ejecución. Además se presentaron algoritmos exactos para algunas clases de gráficas. La complejidad computacional de este problema permanece abierta.