Desarrollo de un esquema de Branch & Price en la resolución de un problema de ruteo e inventario para una red de cajeros automáticos

Abstract

En esta tesis se propone el desarrollo de un esquema de Branch & Price en la resolución de un problema de ruteo e inventario multiperiodo para una red de cajeros automáticos. Las particularidades de este problema que lo hacen interesante son diversas y poco exploradas en la literatura especializada. Por una parte, en este problema se permite que el inventario de cajeros automáticos muestre quiebres de stock, generando dinámicas complejas de inventario. Adicionalmente, se permite la salida de vehículos desde el centro de distribución, para realizar sus recorridos, en un instante distinto al inicio de cada periodo, lo cual se traduce en un problema adicional de modelamiento complejo, ya que se deben generar filas y columnas al modelo de forma simultánea, lo cual es una particularidad que requiere de un tratamiento analítico especial en el esquema de generación de columnas propuesto como base del modelo Branch & Price. Adicionalmente, y como parte del esquema Branch & Price, se establece una estrategia de Reliability Branching así como una estrategia de selección de nodos ad-hoc al problema resultante. También se usa el concepto de Farkas Pricining para o bien hacer factible el problema o probar infactibilidad de los nodos y podarlos. Finalmente, se establece un esquema para seleccionar rutas iniciales que permitan comenzar el algoritmo a partir de un problema factible. A lo largo de la tesis se cubre en detalle la literatura necesaria para el modelamiento adecuado del problema y el desarrollo correcto e implementación del esquema de Branch & Price. Con esto se procede a resolver instancias del problema, en donde se identifican e implementan mejoras al modelo inicial y se identifican líneas de investigación futuras.