CartoType's standard routing system is sometimes not usable for large areas (any area with a population of more than 30 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-star 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 CH (contraction hierarchy) 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 trade-offs are that it is slower than the other systems (a-star and turn-expanded a-star) and that it doesn't support setting arbitrary routing profiles at run-time. However, you can supply as many pre-chosen routing profiles you like when building the data.

CH routing over multiple maps: mobile apps often need to provide coverage for a large area, for instance North America or Europe, where the map data is too large to be practicably downloaded on to a phone: it might be tens of gigabytes in size, depending on the level of detail. The problem can be solved by allowing the user to download parts of the area as separate map files, but that makes routing difficult; while CartoType can route over multiple maps, it needs to create route data at run-time, and that data will be in A-star format, which has a large RAM footprint, as mentioned earlier. The fix for that problem is to use stand-alone CH map data.

The original paper describing the contraction hierarchy algorithm is Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks, by Geisberger and others. There is a fine series of videos of lectures by Professor Dr. Hanna Bast in which she explains the algorithm carefully with worked examples.

Creating maps with CH (contraction hierarchy) routing data

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

/route=ch

with makemap.

You can specify one or more routing profiles for which to create data using, for example

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

or by loading an XML file containing a route profile exported from the Maps App:

/routeprofile=<file>

or by specifying multiple profile names, and / or files:

/routeprofile={ car | bike | walk | hike | <file>  }{, car | bike | walk | hike | <file>  } ... {, car | bike | walk | hike | <file>  }

By default the car profile is used.

Using the CH (contraction hierarchy) system

If you load a map created with this option into CartoType, routing automatically uses the CH (contraction hierarchy) system. You can choose one of the profiles you specified at data preparation time using the SetBuiltInProfile function, which takes the 0-based index of the profile, in the order in which you gave them on the command line. Note that CH routing is slower than standard routing, because it doesn't have the entire route network in memory.

Creating stand-alone CH routing data for routing over multiple maps

Stand-alone CH routing data can be used independently of the map, and can be loaded at the same time as one or more maps. It saves download space and run-time memory. A CartoType map (CTM1 file) of Canada using CH routing data is about 4Gb in size, of which about 400Mb, or a tenth, is routing data. If the routing data is created as a stand-alone file of 400Mb, it can be loaded at the same time as any number of smaller maps of part of Canada, and will provide routing over these maps, including routes over multiple maps.

You create stand-alone CH routing data using the makemap command-line option

/route=cs

Here's what you do:

1. Create a large map (e.g., the whole of Canada) using the /route=cs option with makemap. That creates two files: the normal map, which can be used as normal with the new SDK if needed, and the stand-alone route map. For example, you might get these files:

canada.ctm1
canada.ctm1.cs

The second one is the stand-alone route file.

2. Create any number of smaller maps using exactly the same projection parameters as the large map. Use /route=no with these maps to prevent the unnecessary creation of a route table, unless of course you want to be able to use them on their own.

3. Using the new SDK in your app, load one or more small maps, plus the stand-alone route map. You will now be able to create routes over whole area of the large map. However, any routes going outside the boundaries of the small maps will lack road names and turn details because those are obtained from the 'real' maps.