CartoType's standard routing system is sometimes not usable for large areas (any area with a population of more than 20 million, in practice) on the Android and iOS platforms, because the whole route network is loaded into memory.

To solve this problem you can use an alternative routing system based on contraction hierarchies:

makemap /route=ch

The contraction hierarchy system creates large numbers of shortcuts, enabling the correct route to be found after visiting a very small number of nodes. For example, our standard A* system visits over three million nodes out of four million when routing from one end of the United Kingdom to the other, which forces the route network to be held in memory. However the contraction hierarchy system visits fewer than a thousand nodes. That allows us to load nodes and arcs (junctions and road segments) from file as they are needed.

The new system is not an approximation or a heuristic, or in any way an imperfect solution. It creates exactly the same routes as the standard system. Its main disadvantage is that it doesn't support multiple routing profiles at run-time, because the shortcuts have to be worked out in advance during data preparation.

The original paper describing the contraction hierarchy algorithm is Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks, by Geisberger and others. I had some difficulty understanding the paper, but luckily there is a wonderful series of videos of lectures by Professor Dr. Hanna Bast, in which she explains the algorithm carefully with worked examples.

Creating maps with low-memory routing data

You can create maps with routing tables for the new low-memory system using the makemap command-line option

/route=ch

with makemap.

You can specify the routing profile (you can't change it at run time so it has to be chosen when creating the map) using

/routeprofile=car
/routeprofile=walk
/routeprofile=bike

or by loading an XML file containing the route profile:

/routeprofile=<file>

By default the car profile is used.

Using the new system

If you load a map created with this option into CartoType, routing automatically uses the low-memory system. You can't change the routing profile at run-time (because contraction-hierarchy routing uses a system of pre-calculated shortcuts, which necessarily depend on the weightings in the profile). The other trade-off is that low-memory routing is slower than standard routing, because it doesn't have the entire route network in memory.