Connected vehicles are revolutionizing the way in which transport and mobility are conceived. The main technology behind is the so-called Vehicular Ad-Hoc Networks (VANETs), which are communication networks that connect vehicles and facilitate various services. Usually these services require a centralized architecture where the main server collects and disseminates information from/to vehicles. In this paper, we focus on improving the downlink information dissemination in VANETs with this centralized architecture. With this aim, we model the problem as a Vertex Covering optimization problem and we propose four new nature-inspired methods to solve it: Bat Algorithm (BA), Firefly Algorithm (FA), Particle Swarm Optimization (PSO), and Cuckoo Search (CS). The new methods are tested over data from a real scenario. Results show that these metaheuristics, especially BA, FA and PSO, can be considered as powerful solvers for this optimization problem.