Location-based routing is a widely adopted message transmission mechanism in Vehicular Ad Hoc Networks (VANETs). While the existing location-based routing schemes of VANETs ignore the location privacy protection of vehicles, leading that the drivers to be tracked, and further threaten the safety of their life and property. To address the above issue, we propose an All-Round and Highly Privacy-Preserving Location-Based Routing for VANETs (called ARPLR). Specifically, ARPLR first proposes a road side unit assisted location management with location privacy protection that prevents the destination vehicle’s location from being leaked by the arbitrary query. Then, a message routing based on location ciphertext with highly privacy protection is designed by order revealing encryption, in which a multi-hop routing between the source and destination vehicle is established only by comparing the encrypted locations between intermediate vehicles. Security analysis shows that, ARPLR can not only effectively provide location privacy protection for the intermediate and the destination vehicles in the whole routing process, but also ensure end-to-end secure communication between the source and destination vehicles. Extensive experiments based on real-road map indicate that, compared with two state-of-the-art solutions, the average transmission delay of ARPLR is respectively reduced by about 18% and 60%, meanwhile the average packet delivery rate also increases about 30% and 2%, respectively.