The paper deals with a self-organizing system in a evolutionary framework applied to the Euclidean Vehicle Routing Problem (VRP). Theoretically, self-organization is intended to allow adaptation to noisy data as well as to confer robustness according to demand fluctuation. Evolution through selection is intended to guide a population based search toward near-optimal solutions. To implement such principles to address the VRP, the approach uses the standard self-organizing map algorithm as a main operator embedded in a evolutionary loop. We evaluate the approach on standard benchmark problems and show that it performs better, with respect to solution quality and/or computation time, than other self-organizing neural networks to the VRP presented in the literature. As well, it substantially reduces the gap to some classical Operations Research heuristics.