Many location-based routing protocols have been developed recently, and have been demonstrated to be scalable and efficient for packet routing in mobile ad hoc networks. Using location-based routing requires that a node obtains the node position with which it wants to communicate. This task is generally achieved by a location service. This work presents a novel routing protocol, called hierarchical cell relay (HCR), with a location service. The network area is divided into a number of regular triangular regions, called cells. Nodes forward the packets by some chosen cells, and are classified to be three level hierarchical structures. The hierarchical approach of HCR makes it especially suited for high network density. Moreover, the traffic loads in HCR are shared by all nodes rather than just by some specific nodes, thus reducing overheads at high traffic loads. Simulation results indicate that HCR has better performance than location-aid routing (LAR), in terms of packet delivery ratio, end-to-end delay and overhead in high traffic load.