Performance of aggregated multicommodity flows discovery algorithms in a urban road network for the discovery of mobility patterns

Here we consider a digraph representing an urban road network for which we have a vehicle flow value for each link. These flow values correspond to vehicle movements between different origin/destination pairs. The objective is to determine the mobility patterns between each couple of O/D, that is to say the O/D flows formed by the union of routes followed by the vehicles from each origin to its corresponding destination. We show that this multicommodity flow discovery problem is equivalent to an NP-complete problem, and we compare the performances of different heuristic algorithms in their ability to find such a hidden multicommodity flow to predict mobility patterns.