Optimal routing in hierarchical wireless sensor networks is an NP-complete problem of immense practical importance for which exact solutions exist for very small problem sizes. This paper presents a new memetic algorithm, based on differential evolution, that solves routing problems of more than a thousand relay nodes; in comparison, the best-known approach in the literature handles up to 312 nodes. Simulation results show that the proposed method consistently produces better-quality solutions than three competing approaches.