Los altos costos de transporte y la baja calidad del servicio son vulnerabilidades comunes en diversas redes logísticas, especialmente en la distribución de alimentos. Aquí proponemos un Problema de Distribución de Alimentos Perecederos centrado en el cliente y con múltiples objetivos que se enfoca en el costo, la calidad del producto y la mejora del nivel de servicio al considerar no solo las ventanas de tiempo, sino también el tiempo objetivo de los clientes y su prioridad. Reconociendo la dificultad de resolver dicho modelo, proponemos un enfoque basado en metaheurística de Búsqueda de Vecindario Variable General (GVNS) que nos permite resolver eficientemente un subproblema al permitirnos obtener una. Estas soluciones se evalúan sobre algunos criterios no optimizados y luego se clasifican utilizando un enfoque a posteriori que requiere información mínima sobre las preferencias del tomador de decisiones. Los resultados computacionales muestran (a) que GVNS logró soluciones de igual calidad que un solucionador exacto (CPLEX) en el subproblema; (b) que GVNS puede generar un gran número de soluciones candidatas, y (c) que el uso del enfoque a posteriori facilita generar diferentes perfiles de tomadores de decisiones que a su vez permiten obtener diferentes clasificaciones de las soluciones.