Planificar el reabastecimiento de estaciones de servicio es una actividad logística importante para todas las principales compañías petroleras. El problema estudiado de Reabastecimiento Periódico de Estaciones de Servicio de Múltiples Depósitos se deriva de un caso real en el que la empresa debe reabastecer un conjunto de estaciones de servicio desde un conjunto de depósitos, durante un horizonte de planificación semanal. La empresa debe garantizar el repostaje de acuerdo con los patrones de visitas disponibles, que pueden ser diferentes de un cliente a otro. Un patrón de visita predefine cuántas veces (días) ocurre el reabastecimiento durante una semana y en qué días de visita se debe entregar una cierta cantidad de combustible. Para satisfacer la demanda semanal de cada estación de servicio, se debe seleccionar uno de los planes de reabastecimiento disponibles entre un conjunto dado de patrones de visitas. El objetivo es minimizar la distancia total recorrida por la flota de camiones cisterna durante todo el horizonte de planificación. Se propone un enfoque matheurístico, basado en el paradigma de primero agrupar y luego enrutamiento, para resolverlo. El enfoque propuesto se prueba exhaustivamente en un conjunto de instancias aleatorias realistas. Finalmente, se considera una instancia real grande semanal con 194 estaciones de servicio y dos depósitos.