En los últimos años, los volúmenes de paquetería han alcanzado niveles récord, lo que ha llevado a la industria logística a explorar soluciones innovadoras para satisfacer la creciente demanda. En áreas densamente pobladas, los robots de reparto ofrecen una alternativa prometedora a los sistemas de reparto tradicionales basados en camiones. Estos robots eléctricos autónomos operan en aceras y entregan productos sensibles al tiempo, como paquetes express, medicamentos y comidas. Sin embargo, su capacidad de carga limitada y la duración de la batería requieren un regreso a un depósito después de cada entrega. Este desafío se puede modelar como un problema de enrutamiento de vehículos eléctricos con ventanas de tiempo flexibles y restricciones de capacidad de una sola unidad. El objetivo es atender a todos los clientes minimizando la suma cuadrática de retrasos en las entregas y asegurando que cada vehículo opere dentro de sus limitaciones de batería. Para abordar este problema, proponemos un modelo de programación cuadrática mixta entera e introducimos una formulación mejorada utilizando una estructura de grafo en capas. Para este grafo en capas, presentamos dos enfoques de solución basados en relajaciones que reducen el número de nodos y arcos en comparación con la formulación expandida. El primer enfoque, Refinamiento Iterativo, resuelve la relajación actual hasta optimizarla y perfecciona el grafo cuando la solución es inviable para la formulación expandida. Este proceso continúa hasta obtener una solución óptima comprobada. El segundo enfoque, Ramificar y Refinar, integra el perfeccionamiento del grafo en un marco de ramificación y acotamiento, eliminando la necesidad de reinicios. Experimentos computacionales en instancias modificadas de Solomon demuestran la efectividad de nuestros enfoques de solución, con Ramificar y Refinar superando consistentemente a Refinamiento Iterativo en todas las configuraciones de parámetros probadas.