USING PARTITIONED CONTRACTION HIERARCHIES TO DETERMINE A ROUTE FROM AN ORIGINATION POINT TO A DESTINATION POINT

A route planning platform can identify a plurality of nodes interconnected by a plurality of paths in a road network, can divide the road network into a plurality of partitions, and can generate a respective contraction hierarchy for each partition of the plurality of partitions. The route planning platform can generate, based on the contraction hierarchies of the plurality of partitions, an overlay network and can generate a contraction hierarchy for the overlay network. The route planning platform can obtain information relating to an origination point and a destination point associated with the road network and can identify a first partition associated with the origination point and a second partition associated with the destination point. The route planning platform can determine a route from the origination point to the destination point based on the respective contraction hierarchies of the first partition, the second partition, and the overlay network.