Generation of inefficient MLD partitions

[mjjbell]

Issue

As discovered by @zhudelong, the mapping from node-based edges to edge-based nodes (osrm.cnbg_to_ebg) does not include the duplicate nodes used to represent turn restrictions.

The MLD partitioner uses this mapping to assign nodes to a partition. Duplicate restriction nodes are not assigned, and end up in a special "invalid" partition.

osrm-backend/src/partitioner/partitioner.cpp

Lines 102 to 119 in f7478ba

	// Partition ids, keyed by edge based graph nodes
	std::vector<NodeID> edge_based_partition_ids(edge_based_graph.GetNumberOfNodes(),
	SPECIAL_NODEID);
	// Only resolve all easy cases in the first pass
	for (const auto &entry : mapping)
	{
	const auto u = entry.u;
	const auto v = entry.v;
	const auto forward_node = entry.forward_ebg_node;
	const auto backward_node = entry.backward_ebg_node;
	// This heuristic strategy seems to work best, even beating chosing the minimum
	// border edge bisection ID
	edge_based_partition_ids[forward_node] = node_based_partition_ids[u];
	if (backward_node != SPECIAL_NODEID)
	edge_based_partition_ids[backward_node] = node_based_partition_ids[v];
	}

This special partition will break the spatial properties of the multi-level hierarchy - the partition and its super levels will have a large number of border nodes and very few internal paths between them. This will bloat the hierarchy and make queries slower due to reduced data locality.

This issue will have existed since via way restriction support was added in #4255, but will have become more prominent with the support of multi-via way restrictions in #5907.

Fix

As osrm.cnbg_to_ebg is only used by the MLD partitioner, this can be fixed by simply including the duplicate restriction nodes in the mapping.

[zhudelong]

Nice work, cheers！