La semana próxima empezamos con la técnica de ramificación y poda, una estrategia de búsqueda informada especialmente adecuada para problemas de optimización para los que las técnicas anteriores (dividir para vencer, voraz, programación dinámica, u otras) no dan una solución satisfactoria.

Un ejemplo reciente de aplicación es el planteado en este artículo, en el que se presenta un algoritmo de ramificación y poda para la solución del problema de balance de flota en un sistema de bicicletas de uso compartido:

“A branch-and-bound algorithm for solving the static rebalancing problem in bicycle-sharing systems”, por A.A. Kadri, I. Kacem y K. Labadi; en Computers & Industrial Engineering, Vol. 95, May 2016, Pág. 41–52 (el artículo puede verse completo o descargar el PDF de forma gratuita desde la red de Unizar).

Sistema de bicicletas de uso compartido (© artículo enlazado arriba)