# Distributed Reinforcement Learning Algorithms for the Multicommodity Flow problem in a Urban Road Network

Nassim Haddam, Dominique Barth

► To cite this version:

Nassim Haddam, Dominique Barth. Distributed Reinforcement Learning Algorithms for the Multi-commodity Flow problem in a Urban Road Network. 2025. hal-05330315

HAL Id: hal-05330315

https://hal.science/hal-05330315v1

Preprint submitted on 24 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Distributed Reinforcement Learning Algorithms for the Multicommodity Flow problem in a Urban Road Network*

Nassim Haddam†¹ and Dominique Barth‡¹

¹DAVID-Lab, Université de Versailles Sq./Université Paris Saclay, Versailles, France

## Abstract

In this work, we propose to study algorithms for the problem of retrieving trajectory mobility patterns from aggregated data of vehicle flows. For this purpose, urban road networks are represented by a digraph for which the vehicle flow values are known on each link. These flow values result from vehicle movements between the origin/destination pairs of the urban road network, where each O/D pair corresponds to the set of routes taken by vehicles traveling from the origin to the destination. Reinforcement learning-based algorithms are presented, studied, and compared with basic heuristic methods for the problem of retrieving vehicle trajectories from aggregated flow data. The results demonstrate that reinforcement learning-based algorithms outperform basic heuristic methods, highlighting their potential to enhance mobility analysis and support policymaking for effective urban governance.

## 1 Introduction

To understand traffic dynamics in a large-scale urban network [9], managing vehicle mobility (automobiles, public transport, logistics vehicles) through the governance of an urban territory requires understanding mobility flows and trajectories or patterns. Such a mobility pattern is seen here as a flow in a graph representing the urban network, from a starting point to an arrival point of the territory. Such a flow models the union of the routes taken by vehicles for each such couple of points. This provides a modeling of vehicles traffic as a multicommodity flow network [1, 8] considering here different points of interest in the territory which are the origin or destination of the majority of vehicle flows [21].

In this work, we consider a constrained hypothesis in which we only know the value of the multi-goods flow on certain links of the digraph modeling the urban network, i.e. the number of vehicles crossing the corresponding street during a measured period. We can also have, for certain nodes, the traffic transition matrix, i.e., for each link entering the node, the distribution of its flow on the outgoing links. It should be noted that these two types of available data are those frequently available, often partially, for many territories in France for example. Finally, we assume that an estimate of the origin/destination traffic volume between the different points of interest considered (connection with a motorway or expressway, train station, shopping center, etc.) is also available [6, 11]. A survey of different approach to characterise mobility flow aggregation on time evoluting graphs modelling urban mobility can be found in [10].

The question we deal with here is to know whether the knowledge of all data and measures described above it is possible to reconstitute the underlying multiflow, that is to say for each origin/destination pair to determine the set of routes and the part of the flow induced by the mobility of vehicles moving from this origin to this destination (i.e., the corresponding mobility pattern). Thus, the aim of this article is to consider the complexity and resolution of a multiflow graph discovery problem, which is at the heart of this

<footnote>*This work was supported by the French LabCom HYPHES (ANRS-21-KCV1-0002) and by the TIGA project CFHF d'Ile de France.</footnote>

<footnote>†nassim.haddam@uvsq.fr</footnote>

<footnote>‡dominique.barth@uvsq.fr</footnote>
objective of mobility patterns analysis. This is in fact a specific problem of flow discovery in a network of aggregated multiflows.

In [3] we investigated the performances of some classical graph algorithm approaches to answer this question when only multicommodity flow congestions are known. Similar problems of flow decomposition have been yet considered but in simple flow network [2, 19]. In particular, the very studied multi-commodity flow problem consists in routing a set of commodities from their source to their target (ie the value of the flow for each couple of nodes) in a capacitated network, each commodity being routed along a single path. Many exact and heuristic algorithms have been proposed to solve this problem [16]. Two approaches are generally considered to solve this problem: the arc-path approach, well suited to the use of combinatorial optimization methods, which considers a set of routes from which those that decompose the multiflow will be chosen [7], and the node-arc approach which consists of constructing the chosen routes from the choice for an arc of its next arc [12]. This second approach covers more possible solutions but faces the combinatorial explosion that they induce. Finally, a deep reinforcement learning approach (based on DQN) has been proposed in [17] to solve this problem under uncertainty, showing the pertinence of using such an approach.

Here, we propose and analyze a node-arc approach based on distributed reinforcement learning on nodes [4], considering the three types of data defined above (flow values on links, transition matrix on nodes and multicommodity flows). The goal is not only to minimize the amount of flow that cannot be assigned to a pair of vertices (the residue), but also to minimize the difference between the calculated multiflow and the actual hidden multiflow (the deviation), where this hidden multiflow respects some urban mobility properties. The remainder of this paper is organized as follows. Section 2 introduces the problem and discusses its computational complexity. Section 3 defines the evaluation metrics used to evaluate the proposed approaches. Section 4 presents a general heuristic pseudo-algorithm that captures the core ideas underlying all the algorithms introduced in this work. Section 5 describes the baseline heuristics used as reference points for performance comparison. Section 6 details the distributed reinforcement learning approach proposed in this work. Section 7 outlines the instance generation algorithm for real and simulated cases. Finally, Section 8 compares the performance of all the methods presented in this work.

## 2 Problem formulation and complexity

In this work, an urban road network is represented by a flow network $G = (V, A, cap)$ in which cap: $A \mapsto \mathbb{N}^+$ is a capacity function defined on the arcs (the roadways) that bounds the quantity of vehicles flowing through them. In this road network, the time taken to traverse an arc depends on its level of congestion. The **origin-destination (O/D) pairs** of the network represent the departure and arrival points of vehicle movements in the network. The set denoted as $C = \{\langle s_1, t_1 \rangle, \langle s_2, t_2 \rangle, \dots, \langle s_k, t_k \rangle\}$ contains the O/D pairs of the network. The set $M_C = \{f_1, f_2, \dots, f_k\}$ forms a multiflow for $C$ in $G$ where $f_i$ is an $s_i-t_i$ flow on $G$ with $1 \le i \le k$. As conventionally considered, each flow in the multiflow verifies the conservation law in $G$:

$$ \sum_{u \in \Gamma^{-}(v)} f_{i}(u, v) = \sum_{w \in \Gamma^{+}(v)} f_{i}(v, w) \quad \forall v \in V - \{s_{i}, t_{i}\}. $$

Each flow $f_i$ has a value noted $|f_i|$ which corresponds to the total number of vehicles traveling from $s_i$ to $t_i$. The set of the flow values is noted $\mathcal{V} = \{|f_1|, |f_2|, \dots, |f_k|\}$. We consider a function $F_{M_C}: A \mapsto \mathbb{N}^+$ which maps each arc $(u, v) \in A$ to its **total flow** noted $F_{M_C}(u, v)$ which is expressed as :

$$ F_{M_C}(u, v) = \sum_{1 \le i \le k} f_i(u, v) \qquad (1) $$

Noting the set of all sources as $S = \{s: \exists t(s, t) \in C\}$ and the set of all destinations as $T = \{t: \exists s(s, t) \in C\}$, we consider the **points of interest** to be the set $PI = S \cup T$. The total flow $F_{M_C}$ verifies the property that for each node $v \in V - PI$:

$$ \sum_{u \in \Gamma^{-}(v)} F_{M_C}(u, v) = \sum_{w \in \Gamma^{+}(v)} F_{M_C}(v, w) \qquad (2) $$
which is a consequence of the fact that the flows $f_i$ verify the conservation law in $G^1$. Additionally, we consider a flow dependant cost function defined as $time: A \times N^+ \mapsto N^+$ where $time(a, fl\_val\_arc)$ is the traversal duration of the vehicles moving through arc $a \in A$ when the total flow on it is $fl\_val\_arc < cap(a)$.

Furthermore, we consider a function $tr\_f$ associated to $M_C$ defined as $tr\_f: A \times A \mapsto N^+$, which maps each pair $(a, a') \in A \times A$ to the amount of flow going from arc $a$ to arc $a'$ if $a'$ is a successor arc of $a$ (and zero otherwise). The function $tr\_f$ is referred to as the **transition function**. Similarly, for the sources, we consider another function $tr\_fs$ associated to $M_C$, defined as $tr\_fs: S \times A \mapsto N^+$, which maps each pair $(s, a') \in S \times A$ to the amount of flow going from source $s$ to arc $a'$ if $a'$ is a successor arc of $s$ (and zero otherwise). The function $tr\_fs$ is named the **transition function from the sources**$^2$. Note that the transition function $tr\_f$ and the transition function from the sources $tr\_fs$ associated to $M_C$ must obey the following conditions:

$$ -0 \leq tr\_f(a, a') \leq F_{M_C}(a') \text{ for all } a, a' \in A. $$

$$ -tr\_f(a, a') = 0 \text{ if } a' \text{ is not a successive arc of } a \text{ (as mentioned previously).} $$

$$ - \sum_{a' \in A} tr\_f(a, a') = F_{M_C}(a) \text{ for all } a \in A. $$

Similarly, the transition function from the sources $tr\_fs$ associated to $M_C$ must obey the following conditions:

$$ -0 \leq tr\_fs(s, a) \leq F_{M_C}(a) \text{ for all } s, a \in S \times A. $$

$$ -tr\_fs(s, a) = 0 \text{ if } a \text{ is not a successive arc of } s. $$

$$ - \sum_{a \in A} tr\_fs(s, a) = \sum_{j \in S_j^s} |f_j| \text{ where } S_j^s = \{j : <s_j, t_j> \in C \land s_j = s\}. $$

$$ - \sum_{a \in A} tr\_f(a, a') + \sum_{s \in S} tr\_fs(s, a') = F_{M_C}(a') \text{ for all } s, a' \in S \times A. $$

This work addresses the problem of reconstructing vehicle trajectories using only aggregated flow data, which we name the **flow Disaggregation-problem**. Thus, based on the elements defined in previously, we introduce the 5-uple $AD = (C, V, F_{M_C}, tr\_f, tr\_fs)$, which represents the **aggregated flow data**. Our goal is to recover a multiflow that closely approximates the real multiflow $M_C$, from partial or total knowledge of the elements in $AD$. A variant of this problem, named **Existing-Multiflow** has been shown to be NP-complete [3] in which the proof is a direct reduction from the directed edge-disjoint paths problem known to be NP-complete [20, 13]. In Existing-Multiflow, the aim is to find a multiflow that saturates all arcs while satisfying all demands, in which the capacity function represents a target value that we aim to achieve. However, in the Disaggregation-problem, the capacity function is the total flow, and the objective is to disaggregate the multiflow within the graph.

## 3 Evaluating Methods Quality

In the following, we present performance metrics used to evaluate the quality of the solutions returned by our approaches. The metrics presented are used in both Section 8 (for evaluation) and Section 6 (for the definition of the reward function).

Consider the aggregated flow data $AD = (C, V, F_{M_C}, tr\_f, tr\_fs)$, and let $M'_C = \{f'_1, \dots, f'_k\}$ be a multiflow of $C$ such that

$$ \bullet |f'_i| \leq |f_i| \text{ for each } 1 \leq i \leq k, $$

$$ \bullet \text{ and for any arc } (x, y) \in A, \text{ we have } F_{M'_C} = \sum_{1 \leq i \leq k} f'_i(x, y) \leq F_{M_C}(x, y) \text{ (}M'_C \text{ is feasible for } H). $$

<footnote n="1">¹Since the number of vehicles on the roads is a discrete, this work considers integer flows, capacities, and demands. Fractional flows will be studied in a subsequent work.</footnote>

<footnote n="2">²While it is possible to define a transition function for the destinations, we will omit it as it is not required for our algorithms.</footnote>
<table><caption>Table 1: List of the main notations concerning the algorithms and concepts in this work.</caption><tr><td>G</td><td>The flow network.</td></tr><tr><td>C</td><td>The set of origin-destination pairs.</td></tr><tr><td>f<sub>i</sub></td><td>The flow of index i in C.</td></tr><tr><td>M<sub>C</sub></td><td>The multi flow for C in G.</td></tr><tr><td>V</td><td>The set of the flow values associated to M<sub>C</sub>.</td></tr><tr><td>M<sub>C</sub></td><td>The total flow associated to M<sub>C</sub>.</td></tr><tr><td>S</td><td>The set of all sources.</td></tr><tr><td>T</td><td>The set of all destinations.</td></tr><tr><td>PI</td><td>The points of interest.</td></tr><tr><td>time</td><td>The function predicting the duration of a trip in an arc.</td></tr><tr><td>tr-f</td><td>The transition function.</td></tr><tr><td>tr-fs</td><td>The transition function from the sources.</td></tr><tr><td>AD</td><td>The tuple representing the aggregated flow data.</td></tr><tr><td>τ</td><td>The flow value deviation.</td></tr><tr><td>ρ</td><td>The flow residue.</td></tr><tr><td>δ</td><td>The transition function residue.</td></tr><tr><td>ε</td><td>The multiflow residue.</td></tr><tr><td>tr-f<sub>j</sub></td><td>The learned transition function associated to the pair (s<sub>j</sub>, t<sub>j</sub>).</td></tr><tr><td>tr-fs<sub>j</sub></td><td>The learned transition function from the sources associated to the pair (s<sub>j</sub>, t<sub>j</sub>).</td></tr><tr><td>ag<sub>j</sub><sup>e</sup></td><td>The agent associated to node (or arc) e for the pair (s<sub>j</sub>, t<sub>j</sub>).</td></tr><tr><td>RL<sup>j</sup><sub>AG</sub></td><td>The reinforcement learning algorithm used for all the agents associated to pair (s<sub>j</sub>, t<sub>j</sub>).</td></tr><tr><td>DSA</td><td>The distributed system of agents.</td></tr></table>

We define the following metrics :

* The flow value residue $\tau$ of $M'_C$ from $M_C$ represents the normalized difference between the flow values of the multi flow $M'_C$ and those of the real multi flow

$$ \tau(AG, M'_C) = \frac{\sum_{1 \le i \le k} |f_i| - |f'_i|}{\sum_{1 \le i \le k} |f_i|} $$

* The flow residue $\rho$ of $M'_C$ defined by

$$ \rho(AG, M'_C) = \frac{\sum_{a \in A} F_{M_C}(a) - F_{M'_C}(a)}{\sum_{a \in A} F_{M_C}(a)} $$

is the normalized sum of the differences in total flow across all arcs between the real multiflow and $M'_C$.

* The transition function residue $\delta$ is defined as the normalized absolute sum of the differences, over all arcs and their successors, between the values of the original transition function $tr_f$ and those of the transition function $tr'_f$ associated with $M'_C$. The transition function residue is expressed as

$$ \delta(AG, M'_C) = \frac{\sum_{a \in A} \sum_{a' \in A} |tr-f(a, a') - tr-f'(a, a')|}{\sum_{a \in A} F_{M_C}(a)} $$
* The **multiflow residue** $\epsilon$ is the normalized sum of the absolute differences in flow across all arcs and all pairs between the real multiflow and $M'_c$. It corresponds to the error that the heuristics are designed to minimize, despite it being hidden from the algorithms themselves. It is expressed as

$$ \epsilon(AG, M'_c) = \frac{\sum_{(x,y) \in A} \left( \sum_{1 \le i \le k} |f_i(a) - f'_i(a)| \right)}{2 \sum_{a \in A} F_{M'_c}(a)} $$

Note that $\epsilon \in [0, 1]$ and that $\epsilon = 1$ if every flow is poorly distributed and $\epsilon = 0.5$ if every flow has value zero.

The problem we thus solve consists in finding a feasible multi-flow $M'_c$ minimising as possible the flow residue and/or the flow value deviation and/or the transition function residue for $M'_c$, knowing only the aggregated flow data AD. In the following section, we present the general heuristic approach which serves as a template for the algorithms presented in this work.

# 4 Formulation of a General Pseudo-Heuristic approach

This work presents algorithms that rely on shared core principles, which are elaborated upon in the following paragraphs. The idea behind all the proposed methods is to gradually update a multiflow by adding flow on elementary paths in it as long as possible, while updating the flow on the arcs of the original flow network and the corresponding flow values of the selected pairs. All updates must maintain consistency regarding the flow properties and the transition functions properties presented previously. In all the algorithms, the pairs are always chosen randomly among the pairs in $C$ for which the remaining flow value is maximal and non-zero. This means that pairs with the highest flow are prioritized, assuming they generate most of the network's traffic. The proposed methods differ essentially in how the paths are chosen once a pair $(s, t)$ has been selected. This can be naturally explained by the fact that, for the algorithms to operate properly, the flow network needs to be restricted only to arcs that meet the minimal requirement of being **accessible** from the source $s$ and from which the destination $t$ is **accessible**. Consequently, each time a pair $(s, t)$ is chosen, a subgraph is constructed containing arcs that satisfy the **accessibility** criteria, along with additional criteria specific to the method employed for disaggregation. In the **greedy heuristics**, the path is selected based on an appropriately chosen cost function or utility function. Whereas in the **transition function based heuristic**, the path is determined by using the transition functions iteratively from the source to the destination. And in the **distributed reinforcement learning based heuristic**, a transition function is **learned** through an iterative process of attempting to disaggregate the flow, observing the outcomes, and making adjustments accordingly. We also consider variants of the algorithm where only **one path** is chosen at a time and variants where **multiple paths** are chosen.

In the following paragraph, we detail the pseudo-algorithm of the general heuristic depicted in Algorithm 1. The algorithm takes as inputs the flow network $G$, the aggregated flow data AD, an integer $max_nb_iters$ which is the maximum number of iterations of the algorithm (which serves to bound the number of unsuccessful path selection attempts) and the mapping between pairs and indices *index pairs*. First, the flow value on each arc for every pair on the constructed multiflow is initialized to zero, represented by the matrix $CM$ (of size $k \times |G.V| \times |G.V|$). The list *rem_flow vals*, which is initialized to the flow values of the pairs, contains for each pair its remaining flow value during the algorithm's execution. The iteration number *num_iter* is initialized to zero. Then, the disaggregation loop is executed until either the maximum number of iterations is reached or all pairs have been removed from $C$. At the beginning of the **while** loop (line 6), a pair $(s, t)$ of index $j$ in $C$ is selected randomly among the pairs for which the remaining flow is maximal. Then, in line 9, a subgraph $SG$ is constructed consisting of all the arcs that are reachable from the source $s$, from which the destination $t$ is also accessible, and that satisfy additional criteria determined by the chosen heuristic. If $SG$ is empty, no path connects $s$ to $t$, and the pair $(s, t)$ is then removed from $C$. Otherwise, a path from $s$ to $t$ is chosen in $SG$ based on the heuristic used for the algorithm (line 12). One unit of flow is added along this
path on the constructed multiflow CM, while simultaneously subtracting one unit of flow along the same path in AD.F<sub>Mc</sub>, and updating the transition functions tr-fs and tr-f to reflect this change. Any arc whose total flow reaches zero is deleted (lines 14-15). Next, the remaining flow value associated with the selected pair is decremented (line 16). If this value reaches zero, the selected pair (s, t) is then deleted from C (lines 17-19). Finally, the iteration number num_iter is incremented, and the process moves to the next iteration. In the two following sections, we introduce the proposed distributed reinforcement learning based heuristic, after presenting the baseline heuristics, which we use as reference points to assess the performances of our method.

<caption>**Algorithm 1:** General heuristic pseudo algorithm</caption>

**Inputs:** $G = (V, A, cap)$ - the flow network
$AD = (C, V, F_{M_c}, tr\_f, tr\_fs)$ - the tuple containing the aggregated flow data
$max\_nb\_iters$ - the limit on the number of iterations performed by the algorithm
$index\_pairs$ - a dictionary which maps each pair $(s, t)$ with the integer $j$ such that $(s, t)$ is the pair of flow $f_j$
1: Initialization of the constructed multiflow
2: Let CM bet a $k \times |G.V| \times |G.V|$ matrix whose entries are initialized to zero.
3: $rem\_flow\_vals \leftarrow list(V)$
4: $num\_iter \leftarrow 0$
5: Flow disaggregation loop
6: **while** $num\_iter < max\_nb\_iters \land C \neq \emptyset$ **do**
7: &nbsp;&nbsp;&nbsp;&nbsp; ▷ Depending on the specific method chosen
8: &nbsp;&nbsp;&nbsp;&nbsp; Chose randomly a pair $(s, t) \in C$ such that $rem\_flow\_vals[j] = max(rem\_flow\_vals)$ where $j = index\_pairs[(s, t)]$
9: &nbsp;&nbsp;&nbsp;&nbsp; Construct a subgraph SG which includes $s$ and $t$ depending on the heuristic chosen
10: &nbsp;&nbsp;&nbsp;&nbsp; ▷ Choose a path if possible and perform the relevant updates, else delete the pair
11: **if** $SG \neq \emptyset$ **then**
12: &nbsp;&nbsp;&nbsp;&nbsp; Chose a random $s-t$ path $path$ in SG depending on the heuristic chosen
13: &nbsp;&nbsp;&nbsp;&nbsp; Add one unit of flow along the path $path$ in CM
14: &nbsp;&nbsp;&nbsp;&nbsp; Subtract one unit of flow along the path $path$ in AD.F<sub>M_c</sub>
15: &nbsp;&nbsp;&nbsp;&nbsp; Update the transition functions tr-fs and tr-f along the path $path$
16: &nbsp;&nbsp;&nbsp;&nbsp; Delete from G.A all arcs $a \in path$ for which $AD.F_{M_c}(a) = 0$
17: &nbsp;&nbsp;&nbsp;&nbsp; $rem\_flow\_vals[j] \leftarrow rem\_flow\_vals[j] - 1$
18: **if** $rem\_flow\_vals[j] = 0$ **then**
19: &nbsp;&nbsp;&nbsp;&nbsp; $C \leftarrow C - \{(s, t)\}$
20: **end if**
21: **else**
22: &nbsp;&nbsp;&nbsp;&nbsp; $C \leftarrow C - \{(s, t)\}$
23: **end if**
24: $num\_iter \leftarrow num\_iter + 1$
25: **end while**
26: **return** CM
# 5 Baseline Heuristics

In this section are detailed the baseline heuristics. These heuristics form baseline methods against which the methods presented in the rest of this work are compared.

## 5.1 Greedy heursitics

We present in this subsection two simple and natural greedy heuristics designed to address the disaggregation-problem. The greedy heuristics are implementations of the pseudo-algorithm presented in Algorithm 1. The subgraph SG of relevant arcs (constructed after choosing a pair $(s_j, t_j)$), contains all the arcs reachable from $s_j$ and from which $t_j$ is reachable that lie in a least cost (or maximal utility) path from $s_j$ to $t_j$. The cost structure used to construct such a subgraph depends on the heuristic chosen. In heuristic **Min-Time**, the cost cost of a path path is the time taken to go from node $s_j$ to $t_j$ knowing the flow values on the arcs, which is expressed as

$$cost(path) = \sum_{a \in path} time(a, F_{MC}(a))$$

Thus, the subgraph SG is a DAG constructed using Dijkstra's algorithm, such that any path from $s_j$ to $t_j$ is a least cost path in G (restricted to the non-saturated arcs). In heuristic **Max-Capacity**, the utility util of a path path (which is also its capacity), is the minimum remaining capacity among the arcs of path expressed as

$$util(path) = \min_{a \in path} F_{MC}(a)$$

Here as well, the subgraph SG is constructed using a variant of Dijkstra's algorithm in heuristic Max-Capacity, such that every simple path from $s_j$ to $t_j$ is a maximum capacity path (i.e. a thickest path), considering only non-saturating arcs.

Once SG is constructed, a random walk is performed in it starting from $s_j$ until $t_j$ is reached. Consider path to be the path followed by this random walk. Each cycle in path, if any exists, is subsequently removed to obtain a simple path. Afterwards, the value of the flow is increased by the minimum remaining capacity of the arcs of this path (the smallest total flow remaining on its arcs). For the following steps, the baseline heuristics proceed exactly as in Algorithm 1.

## 5.2 Transition function based heuristic

In this subsection, we present the transition function heuristic, which uses the transition functions $tr\_f$ and $tr\_fs$ in order to choose the paths in Algorithm 1. Unlike the baseline heuristics, which lack any information about flow distribution, the transition function heuristic incorporates such information (albeit at a coarse level) through the use of the transition functions. In the following paragraphs, we explain how the transition function heuristic implements Algorithm 1, how the transition functions are used for path selection, starting with the construction of the subgraph used for path selection.

After choosing a pair $(s_j, t_j)$, the subgraph SG of relevant arcs is constructed and contains all the arcs reachable from $s_j$ and from which $t_j$ is reachable in the updated graph G using the transition functions. To construct such a subgraph, a graph search is performed on the arcs of the graph, starting from $s_j$. For this traversal, a queue-based breadth-first search (BFS) algorithm can be used. The algorithm starts by queueing each non-saturated and unvisited arc $a$ satisfying $tr\_fs(s_j, a) > 0$. The algorithm loops until the queue is non-empty. Each iteration of the loop, an arc $a$ is queued and marked as visited. Next, all unvisited successor arcs $a'$ of the current arc $a$ satisfying $tr\_f(a, a') > 0$ are enqueued. Following that, the algorithm proceeds to the next iteration until it terminates. The graph SG is induced by the arcs marked as visited during the graph search phase.

The path selection operates by a random walk starting from $s_j$ until $t_j$ is reached. At each step, the next arc is chosen stochastically, with each successor arc weighted according to its corresponding value in
associated to the k'th execution. The reward function noted $r.eval_k)$ is calculated based on those metrics, and is used to reinforce the agent's actions chosen during the k'th executions of Algorithm 1. At each iteration of this process, if $k$ equals nbs then the learning process terminates, else the new policies serve to disaggregate the flow during the $k+1$'th execution of Algorithm 1. In the following paragraphs, we formalize and elaborate on how the distributed system of agents selects paths during the learning process. Finally, we describe how the reinforcement step is carried out by the agents at the end of each episode.

<caption>**Algorithm 2:** Pseudo algorithm of the learning process of the distributed system of agents</caption>

1: **for** $k$ in $[1,..., nb\_episodes]$ **do**
2: &nbsp;&nbsp;&nbsp;&nbsp;Initialize flow network $G$ and the aggregated flow data $AD$.
3: &nbsp;&nbsp;&nbsp;&nbsp;Execute Algorithm 1 on $G$, $AD$ and $max\_nb\_iters$ as inputs.
4: &nbsp;&nbsp;&nbsp;&nbsp;Calculate $eval_k = (\tau_k, \rho_k, \delta_k)$ and the reward $r.eval_k$.
5: &nbsp;&nbsp;&nbsp;&nbsp;Update the agents in $DSA$ involved in step 3 with the reward $r.eval_k$.
6: **end for**

We distinguish two approaches to designing such a distributed system of agents that uses reinforcement learning for the flow disaggregation problem. The **node based** approach, in which each node is associated with an agent, and the **arc based** approach, in which each arc is associated with an agent. We note $ag_j^e$ the agent whose task is to select the next arc in the path selection process for pair $(s_j, t_j)$ when the current arc (or node) is $e$. The distributed system of agents is thus noted

$$DSA = (\bigcup_{1 \le j \le k} ag_j^{s_j}, \bigcup_{1 \le j \le k} \bigcup_{e \in E} ag_j^e)$$

where $E = V$ for the node based system and $E = A$ for the arc based system in which the agents $ag_j^{s_j}$ with $1 \le j \le k$ are tasked to choose the first arc starting from $s_j$. Each agent in the distributed system is defined by a tuple $ag_j^{s_j} = (rl\_tr\_fs_j, rl\_tr\_f_j, RL_{ALG}^j)$ containing the transition functions (presented in the beginning of section 6) and the reinforcement learning algorithm used by the agent. In the next paragraph, we detail how the path construction process is performed in the distributed reinforcement learning based heuristic.

Each time a pair $(s_j, t_j)$ is selected, the algorithm constructs the subgraph $SG$; using the transition functions $rl\_tr\_fs_j$ and $rl\_tr\_f_j$ as shown in subsection 5.2. Then, a path is constructed by executing a walk guided by $rl\_tr\_fs_j$ and $rl\_tr\_f_j$, starting from $s_j$ until the destination $t_j$ is reached. The algorithm selects agent $ag_j^{s_j}$ to choose the first arc using its associated transition function from the sources $rl\_tr\_fs_j$, depending on the type of reinforcement learning algorithm $RL_{ALG}^j$ used by the agent. If $RL_{ALG}^j$ is a policy based algorithm, $rl\_tr\_fs_j$ represents the weights given to each successor arc of $s_j$ used to select stochastically the next arc of the path (via the stochastic vector constructed with those weights), whereas if $RL_{ALG}^j$ is a value based algorithm, $rl\_tr\_fs_j$ holds the estimated reward associated to each successor arc based on which the next arc is chosen. The path construction process operates by a random walk starting from $s_j$ until $t_j$ is reached. At each step, the next arc is selected depending on the type of $RL_{ALG}^j$ using $rl\_tr\_fs_j$, with each successor arc weighted according to its corresponding value in the relevant transition functions ($rl\_tr\_fs_j$ when choosing the first arc and $rl\_tr\_f_j$ otherwise). All cycles are subsequently removed from the path, and the resulting path is returned. Each time a path is chosen, it is stored along with the pair associated with it for the subsequent reinforcement step, which will be the focus of the next paragraph.

Algorithm 3 represents how the reinforcement step is performed at the end of each episode. The algorithm has as inputs the distributed system of agents $DSA$, the mapping between pairs and indices `index pairs`, the list `selected paths` of selected paths during the episode, the list `selected pairs` of the associated selected pairs, a tuple `eval` = $(\tau, \rho, \delta)$ containing the quality evaluations of the solution generated during the episode, and a boolean `arc based` which is True if $DSA$ is an arc based system and False if it is a node based system. Algorithm 3 starts by calculating the reward using the evaluations `eval` associated with the current episode (line 1 of Algorithm 3). Then, for each path `path` in `selected paths`, represented as an ordered list of nodes, we identify the associated pair $(s, t)$ and determine its index $j$ in $C$ (lines 3-6). Afterwards, each node in `path` is visited, and the policy of the agent that selected the node's successor arc in the path is updated with
the reward *r* via a call to procedure *update_agent_policy*(). The said agent corresponds to *ag*<sub>j</sub><sup>s</sup> when the first node is visited, *ag*<sub>j</sub><sup>(path[k-1], path[k])</sup> when an arc based system is used, and *ag*<sub>j</sub><sup>path[k]</sup> when a node based system is used. The algorithm continues in this manner to update the policies of the agents responsible for constructing the paths until all paths have been processed. Note that Algorithm 3 is executed after each episode during the learning phase.

<caption>**Algorithm 3:** The algorithm which performs the reinforcement step at the end of each episode for a distributed system of agents</caption>

Inputs: $DSA$, `index pairs`, `selected paths`, `selected pairs`, `eval` = ($\tau$, $\rho$, $\delta$), `arc based`.
1: $r \leftarrow process\_reward eval$
2: **for** $i$ in $[0, ..., len selected\_paths) - 1$ **do**
3: &emsp; ▷ For each path, get the associated pair and the pair index
4: &emsp; $path \leftarrow selected\_paths[i]$
5: &emsp; $(s, t) \leftarrow selected\_pairs[i]$
6: &emsp; $j \leftarrow index\_pairs[(s, t)]$
7: &emsp; ▷ Update the policy of each agent along the path
8: &emsp; **for** $k$ in $[0, ..., len(path) - 2]$ **do**
9: &emsp; &emsp; **if** $k = 0$ **then**
10: &emsp; &emsp; update\_agent\_policy(ag\_j<sup>s</sup>, (s, path[1]), r)
11: &emsp; &emsp; **else**
12: &emsp; &emsp; ▷ Select the associated agent according to arc\_based
13: &emsp; &emsp; **if** arc\_based = True **then** $e \leftarrow (path[k-1], path[k])$ **else** $e \leftarrow path[k]$
14: &emsp; &emsp; update\_agent\_policy(ag\_j<sup>e</sup>, (path[k], path[k+1]), r)
15: &emsp; &emsp; **end if**
16: &emsp; **end for**
17: **end for**

## 6.3 Multipath selection in the distributed system of agents

In all the algorithms presented so far, the paths are consistently chosen and augmented one at a time. An alternative approach is to select multiple candidate pairs and jointly augment the paths chosen from among them. This approach allows pairs with lower remaining flow values to be selected and have their flow assigned to the arcs of the graph. Algorithm 4 shows how this path selection is performed, where the idea is to select additional paths as more arcs approach saturation. The algorithm has as inputs the graph *G*, the aggregated data *AG*, and the list of remaining flow values *rem_flow vals*. The algorithm starts by ordering the remaining pairs descendingly based on their remaining flow value; the sorted list is stored in *sorted rem pairs* (line 1). Then, a path is constructed for each remaining pair in *sorted rem pairs* using the learned transition functions; those generated paths are stored in list *candidate paths* (line 2). Before entering the main loop, *selected pairs* and *selected paths* are initialized with the first pair in *sorted rem pairs* and its corresponding path in *candidate paths*. Next, within the **for** loop starting at line 6, each remaining pair (*s*, *t*) in *sorted rem pairs* is considered. A pair (*s*, *t*) is selected if its candidate path, together with the selected paths of the previously chosen pairs (those in *selected paths*), can jointly route the total remaining flow of all the pairs considered.

The condition previously presented is checked in the following way. For each selected path *path'* in *selected_paths*, process the arc intersection between it and the candidate path *path* of (*s*, *t*) and store the result in the set *IA*. Next, for each arc *a* in *IA* construct the set *rest pairs* composed of the pair (*s*, *t*) in addition to the selected pairs for which the associated candidate path contains *a*. If the sum of the remaining
flow of the pairs in *rest-pairs* exceeds the remaining flow in *a*, do not add the path *path*' in *selected_paths*;
otherwise, add it along with its associated pair (*s*, *t*) (in *selected_paths* and *selected pairs* respectively).
Algorithm 4 terminates after treating all the pairs in *sorteditat pairs* and returns the selected pairs as well
as the selected paths (which contain at least one element each).
**Algorithm 4:** The multi path selection algorithm

**Inputs:** $G$, $AG$, $rem_flow vals$, $index pairs$
1: $sorted\_rem\_pairs \leftarrow sort\_pairs(AG.C, rem_flow vals)$
2: $candidate\_paths \leftarrow construct\_paths(G, AG.tr_f, AG.tr_fs, sorted\_rem\_pairs)$
3: $selected\_pairs \leftarrow [sorted\_rem\_pairs[0]]$
4: $selected\_paths \leftarrow [candidate\_paths[0]]$
5: ▷ For each pair in $sorted\_rem\_pairs$ decide if to select it
6: **for** i in $[1, ..., len(sorted\_rem\_pairs) - 1]$ **do**
7: &nbsp;&nbsp;&nbsp;&nbsp;▷ Extract the current path and the current pair
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(s, t) \leftarrow sorted\_rem\_pairs[i]$
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$path \leftarrow candidate\_paths[i]$
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$add\_path \leftarrow True$
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$j \leftarrow 0$
12: &nbsp;&nbsp;&nbsp;&nbsp;▷ Decide if $path$ can be added by checking if the remaining flow of the considered pairs can be routed through the selected paths
13: **while** $add\_path \land j < len(selected\_paths)$ **do**
14: &nbsp;&nbsp;&nbsp;&nbsp;▷ Extract a selected path $path'$ and process the arc intersection between $path$ and $path'$
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$path' \leftarrow selected\_paths[j]$
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$IA \leftarrow arc\_path\_intersection(path, path')$
17: &nbsp;&nbsp;&nbsp;&nbsp;▷ For each arc in $IA$, check if it can route the remaining flow of the relevant selected pairs
18: **for** $a \in IA$ **do**
19: &nbsp;&nbsp;&nbsp;&nbsp;▷ Restrict the selected pairs to those for which the candidate path traverses $a$
20: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$rest\_pairs \leftarrow restrict\_pairs\_arc(selected\_pairs, selected\_paths, a) \cup \{(s, t)\}$
21: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$rest\_id\_pairs \leftarrow get\_indices\_pairs rest\_pairs, index\_pairs)$
22: &nbsp;&nbsp;&nbsp;&nbsp;▷ Don't add $path$ if $a$ can't route the remaining flow of the pairs in $rest\_pairs$
23: **if** $\sum_{j' \in rest\_id\_pairs} rem\_flow\_vals[j'] > AG.F_M(a)$ **then**
24: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$add\_path \leftarrow False$
25: &nbsp;&nbsp;&nbsp;&nbsp;**break**
26: **end if**
27: **end for**
28: $j \leftarrow j + 1$
29: **end while**
30: ▷ Add the current path $path$ if $add\_path$ is True
31: **if** $add\_path$ **then**
32: &nbsp;&nbsp;&nbsp;&nbsp;selected\_pairs.append((s, t))
33: &nbsp;&nbsp;&nbsp;&nbsp;selected\_paths.append(path)
34: **end if**
35: **end for**
36: **return** $selected\_pairs, selected\_paths$
# 7 Instance Generation

In order to fully test and validate the algorithms proposed in this work, we need to generate simulated instances for executing those heuristics. In this section, we describe the instance generation algorithm. Each instance is generated as follows. First, a planar graph is randomly generated. Each arc in the planar graph is then assigned a capacity value and a traversal time. Next, origin-destination pairs are selected from among the graph's nodes, and corresponding flow values are generated. Finally, a multiflow is constructed in the generated planar graph with the selected origin-destination pairs, which induces a total flow in the graph. In the following subsections, we present the random planar graph generation algorithm (Subsection 7.1), followed by the generation of the capacities and the traversal times (Subsection 7.2), the pairs and flow values generation (Subsection 7.3), and the multiflow generation algorithm (Subsection 7.4).

## 7.1 Random Planar Graph Generation

The generation of the random planar graphs (representing the road network) follows the steps depicted in Algorithm 5. We note by $n$ the number of nodes of the graph, and by $m$ the desired number of arcs. In Algorithm 5, to guarantee that the graph is connected, multiple attempts are performed at generating the random planar graph. We note $max\_nb\_tries$ the maximum number of such attempts. $G$ is a matrix whose entries are initialized to zero, which represents the adjacency matrix of the planar graph to be generated. $Keys()$ is a function that takes a dictionary as input and returns a list containing all of its keys. $Index()$ is a function that takes a list of nodes and the coordinates of a point as inputs and outputs the label associated with this point in the list of nodes.

During each attempt of random planar graph generation, the algorithm constructs a grid of size $l$ and selects $n$ of its intersection points to form the vertices of the graph (by a call to the function *GenerateNodes()*) in line 5 of Algorithm 5). Then, the arcs are drawn randomly from the selected nodes in such a way that no two arcs cross each other (with at most $max\_nb\_draws$ draws per graph generation attempt). The number of arcs drawn during a try, denoted by $nb\_draws$, is initialized to zero (line 7). The list $arcs$, initially empty, stores the selected arcs, while points contains the grid coordinates of the selected nodes (lines 8 and 9). Afterwards, the arcs are selected (in the **while** loop starting at line 10) in the following way. Two nodes are chosen randomly among the selected nodes of the grid: a node with grid coordinates $P$ and another node with grid coordinates $Q$ in the disk of center $P$ and radius $r$ if such a node exists (lines 12-15). If the segment $[P,Q]$ doesn't cross any of the segments in $arcs$ (chosen to be the arcs of the graph), it is added to $arcs$ and the entries of $G$ corresponding to $[P,Q]$ and $[Q,P]$ are set to 1 (lines 17-21). If no selected node exists within distance $r$ of node $P$ or if $[P,Q]$ intersects with one of the already chosen arcs, $nb\_draws$ is incremented. After each attempt, the algorithm checks whether the graph generated is connected (lines 26-28). The algorithm terminates after generating a connected planar graph (with a maximum of $m$ arcs as indicated), or after exhausting the number of graph generation attempts allowed ($max\_nb\_tries$ as mentioned earlier). The algorithm returns True in the first case and False in the second. In the next subsection, we present the multiflow generation algorithm.
**Algorithm 5:** Algorithm for generating a random planar graph

**Inputs**: *G*, *l*, *r*, *m*, *max_nb Draws*, *max_nb tries*

**Outputs**: A boolean which is True iff the graph generated is planar and connected

**Variables**: *nodes* - A dictionary of coordinates of nodes to label of nodes

*arcs* - A list of segments

1: ▷ Attempt to generate a planar random graph for a maximum of *max_nb_tries* times

2: *nb_tries* ← 0

3: **while** *nb_tries* < *max_nb_tries* **do**

4: ▷ Generate the nodes of the graph

5: *nodes* ← *GenerateNodes*(*l*, *taille*(*G*))

6: ▷ Generate the arcs of the planar random graph

7: *nb*draws ← 0

8: *arcs* ← An empty list

9: *points* ← *Keys*(*nodes*)

10: **while** *taille*(*arcs*) < *m* ∧ *nb*draws < *max_nb*draws **do**

11: ▷ Select a new candidate arc to be added in *arcs*

12: *P* ← *RandomNode*(*points*)

13: *candidate_neibours* ← *GetNearNodes*(*P*, *points*, *r*)

14: **if** *taille*(*candidate_neibours*) ≠ 0 **then**

15: *Q* ← *RandomNode*(*candidate_neibours*)

16: ▷ Add arc (*P*, *Q*) to *arcs* if (*P*, *Q*) does not intersect with any of the arcs in *arcs*

17: **if** [*P*, *Q*] ∉ *arcs* ∧ [*Q*, *P*] ∉ *arcs* ∧ ! *Intersect*([*P*, *Q*], *arcs*) **then**

18: *append*(*arcs*, [*P*, *Q*])

19: *G*[*Index*(*nodes*, *P*), *Index*(*nodes*, *Q*)] ← 1

20: *G*[*Index*(*nodes*, *Q*), *Index*(*nodes*, *P*)] ← 1

21: **end if**

22: **end if**

23: *nb*draws ← *nb*draws + 1

24: **end while**

25: ▷ If the graph generated is connected return True else increment the numbers of tries

26: **if** *IsConnected*(*G*) **then**

27: **return** *True*

28: **end if**

29: *nb_tries* ← *nb_tries* + 1

30: **end while**

31: **return** *False*

## 7.2 Generation of capacities and traversal times

The capacities are generated in the following way. A node in the center of the planar graph is randomly selected as the root. Then, a spanning tree, denoted *span_tree* is constructed by applying a breadth-first
search algorithm executed from this node. All arcs in the graph are initially assigned a base capacity, *base_cap*, except for those belonging to the spanning tree, which are assigned capacities that are integer multiples of *base_cap*.

Arcs in *span_tree* are assigned a traversal time equal to the Euclidean distance of their corresponding segments in the grid constructed by Algorithm 5. Arcs not belonging to *span_tree* are assigned a traversal time equal to a predefined fraction of the distance associated with their respective segments. The resulting traversal times reflect how long it takes to traverse the graph's arcs when no flow is present.

## 7.3 Construction of the origin-destination pairs

The origin-destination pairs are constructed as follows. Each node in the graph is assigned a weight equal to the sum of the capacities of its outgoing arcs. Then, each pair is selected stochastically by selecting its two nodes one after the other, where the probability to select a node is equal to its weight divided by the total weight of all nodes. The results of this step are stored in the *origin-destination datastructure* *LF*, which is an object having three attributes :

* *pair* is a list of origin-destination pairs.

* *proba* is a list containing the probability of selecting each pair during the multiflow generation process. For a pair (s, t), this probability is computed as follows. A weight equal to the sum of the total capacity of the outgoing arcs of s and the total capacity of the ingoing arcs of t is associated with (s, t). The probability of selecting the pair (s, t) is then given by its weight divided by the total weight of all pairs.

* *value* is a list of the desired flow values associated to the pairs, which represent an upper bound on the flow value assigned to each pair during the multiflow generation process.

## 7.4 Multiflow Generation Algorithm

Algorithm 6 depicts the multiflow generation algorithm. The multiflow generation algorithm takes as input the matrix *M*, representing the flow network *G* to be generated, the list *LF* presented previously, and *min_fl*, which is the minimum amount of flow routed in a path. Each element of *M(i,j)* of the matrix *M* has two attributes, *M(i,j).cap* and *M(i,j).time* which represents the time taken to go from node *i* to node *j* when there is no flow in arc (i,j). The multiflow generation returns the matrices *M*<sub>*i*</sub> with 1 ≤ *i* ≤ *k* associated to the pairs in *LF* as well as the list *RF*, which contains the value of each flow in the generated multiflow. The multiflow is generated path by path until no more flow can be added to the network.

Algorithm 6 starts by copying the matrix *M* and initializing to zero the variable *cpt_saturated*, which is the number of saturated pairs at a given time (lines 1 and 2). The algorithm constructs the multiflow pair by pair, stopping once, for each pair, either no further flow can be routed from the source to the destination, or the pair has no remaining flow. Each iteration (in the **while** loop starting at line 3), an origin-destination pair (a, b) = (*s*<sub>*i*</sub>, *t*<sub>*i*</sub>) ∈ *C* iks drawn according to the probabilities in *LF.proba* (line 4). Then, a DAG of shortest paths with source *s*<sub>*i*</sub> and destination *t*<sub>*i*</sub> is generated by first executing the Dijkstra algorithm with source *s*<sub>*i*</sub> to return the minimum costs (travel times) associated with each node (line 5). The DAG of shortest paths from *s*<sub>*i*</sub> to *t*<sub>*i*</sub> is generated by executing a Breadth-First Search going backward from *t*<sub>*i*</sub>, which uses the costs returned by Dijkstra to select the arc to be added in the DAG. If such a DAG no longer exists for a pair (*s*<sub>*i*</sub>, *t*<sub>*i*</sub>), the probability *LF.proba(i)* to choose pair (*s*<sub>*i*</sub>, *t*<sub>*i*</sub>) is set to zero and *cpt_saturated* is incremented (line 25 and 26). If such a DAG exists, a random path *P* is chosen from this DAG (line 7), and the flow network as well as the generated multiflow are updated (lines 9-23). *f_am* units of flow are added along each arc (a, b) of the selected path *P* in matrix *M*<sub>*i*</sub> (line 10), where *f_am* is the minimum value among the remaining capacities of the arcs of *P*, the remaining flow value of the pair (*s*<sub>*i*</sub>, *t*<sub>*i*</sub>) and *min_fl*. Likewise, the capacity of *M(a,b).cap* is decreased for every arc (a, b) ∈ *P* by *f_am* units (line 11). If the capacity of arc (a, b) ∈ *P* reaches 0, the arc is deleted from *M* (line 13). In addition, the cost *M(a,b).time* associated with each of the arcs (a, b) ∈ *P* is updated according to its remaining capacity (by a call to the procedure *UpdateTime()* detailed in Algorithm 7). At lines 18 and 19, *LF.value(i)* is decreased by *f_am* units, and
$RF.value(i)$ is incremented by $f\_am$ units. Then, if $LF.value(i)$ reaches zero, the probability $LF.proba(i)$ to choose pair $(s_i, t_i)$ is set to zero and $cpt\_saturated$ is incremented (lines 21 and 22). If all entries of $LF.proba$ reach value zero, $cpt\_saturated$ equals $k$ and the algorithm terminates and returns the matrices $M_i$ with $1 \le i \le k$ as well as the list $RF$. The functions used to generate the multiflow are :

- $Dijkstra(M, s)$ whose input is the matrix $M$ and a node $s$ of the graph, and which outputs a list containing the costs of shortest paths from node $s$ to every other node.

- $CopyGraph(M)$ returns a matrix $M'$ which is a copy of matrix $M$ given in entry.

- $DAGSP(s, t, M, path\_costs)$ which takes two nodes as inputs $s$ and $t$ and a list named `path_costs` containing the costs of the shortest paths originating from $s$, and outputs a DAG containing all the arcs which are part of a shortest cost path between $s$ and $t$. As mentioned previously, this function uses a modified version of the BFS algorithm applied to $M$ starting at node $t$.

- $RandomPath(s, t, G')$ which returns a random path from node $s$ to node $t$ in a graph $G'$ if there is one and null otherwise.

- $RandomPair(LF.proba)$ which draws a pair $(s, t)$ using the probability law represented by $LF.proba$. Each pair $(s_i, t_i)$ is drawn with probability $LF.proba(i)$.

- `UpdateTime(M, OG, (u, v))` has as input the matrix representing the network flow $M$, the original flow network matrix $OG$ and an arc $(u, v)$ and updates the cost of arc $(u, v)$ noted $M.time(u, v)$. By noting that $OG(u, v).time = F_M(u, v)$ is the total capacity of the arc $(u, v)$; the update of the traversal time of $(u, v)$ shown in Algorithm 7 makes it possible to take into account the congestion of the urban network. Each time the procedure `UpdateTime(M, OG, (u, v))` is invoked, the traversal time of arc $(u, v)$, denoted $M(u, v).time$, is updated by multiplying its ideal traversal time $OG(u, v).time$ by the ratio $OG(u, v).cap/M(u, v).cap$, which represents its congestion level.

# 8 Performance evaluation

The subsections below present the methodology and results of our study. Subsection 8.1 describes the experimental setup. Subsection 8.2 examines the characteristics of the generated instances. Finally, Subsection 8.3 provides an evaluation and comparison of our approaches in real and simulated instances.

## 8.1 Experimental design

**Generated instances.** The simulated instances are generated as follows: the graph is generated according to Subsection 7.1, the capacities (which are upper limits on the flow on the roads) and the traversal times are generated according to Subsection 7.2, and the multiflow generation is performed according to Subsection 7.4. In real instances, the multiflow is generated following the procedure outlined in Subsection 7.4. Unless specified otherwise, the experiments are performed with `nb_instances` = 100 instances with $n = 75$ nodes each and with at most `max_nb Compares` = 250 arcs. The capacity of the arcs belonging to the spanning tree is set to 30, and the capacity of the remaining arcs is set to 10. The initial traversal times of the arcs belonging to the spanning trees are scaled to one-third of their original values, which is their euclidean distance. For each instance, `nb pairs` = 15 pairs are designated as origin-destination pairs. The multiflow is generated in the same way for both simulated instances and real instances. We set $f\_am = 1$, meaning that the multiflow is updated by at most one unit of flow at each step. After applying the multiflow generation algorithm presented in Subsection 7.4, the graph is reduced to the arcs where the flow passes, and all the origin-destination pairs for which there is zero flow are discarded.

**Graph from real data.** The graph considered models the road infrastructure of the municipality of Lieusaint in Île-de-France <fnref n="3" />. We use OpenStreetMap data to obtain the topological structure of the mobility

<footnote n="3">³see https://fr.wikipedia.org/wiki/Lieusaint_(Seine-et-Marne)</footnote>
network. We chose the OsmToRoadGraph project [5] to convert OSM files into a graph of the real map. Intersections are represented as vertices, while the roads connecting them are represented as edges. Eleven places were identified as points of interest for the Lieusaint site: Lieusaint - Moissy SNCF station, Lieusaint - Moissy parking, a college dormitory, Sénart-Fontainebleau IUT, Icam-Site of Grand Paris Sud, Carré Sénart shopping center, Saint-Léon Sénart high school, A5 highway, and three junction vertices with the neighboring cities of Lieusaint: Saint-Pierre-du-Perray, Moissy-Cramayel, and Savigny-le-Temple. For each one of these points of interest, a vertex was created and connected to its nearest node by an arc.

Based on cartographic data obtained by *Grand Paris Sud* and OpenStreetMap, we exported an area that covers the entire city of Lieusaint. This resulted in a graph with 14,114 vertices and 16,149 edges. Since all points of interest are concentrated in the southern part of Lieusaint, we restricted our study area to the region encompassing them. This resulted in a graph with 5,412 vertices and 6,499 edges. Using the Overpass Turbo data exploration tool [15], we extracted the driving roads within the selected area. The resulting graph contains thousands of vertices and edges, as each turn, no matter how minor, recorded in the OSM data generates a vertex with degree 2, which affects the graph's characteristics. We made some modifications that are implemented as additional modules to the OsmToRoadGraph script to remove dead ends and intermediary nodes from the graph. Additionally, residential areas located far from the selected points of interest were removed from the network. Finally, we obtained a graph with 223 vertices and 320 edges. Four capacity values {400, 300, 140, 100} weight the arcs, according to the road type (the real speed limitation) and the maximum number of road traffic lanes on each. And the traversal time of each arc is calculated as the ratio of its length and the real speed limitation. From vehicle flow data partially measured by cameras and counting systems analyzed and communicated by the territory, 11 points of interest were selected, yielding up to 109 potential O/D pairs. Finally, the multiflow generation algorithm presented in Subsection 7.4 is applied in the same way as in the simulated instances.

**Distributed reinforcement learning based system** All reinforcement learning agents in the distributed system of agents evaluated here are implemented using the LRI algorithm [14]. The agents are trained for *nb_episodes* = 30. Unless stated otherwise, for each instance, the learning rate is chosen from the set *learning_rate_set* = {0.01, 0.025, 0.05, 0.075, 0.1} that achieves the highest reward in the final episode.

## 8.2 Generated instance exploration

In this subsection, we evaluate whether the flow networks generated using the method described in Section 7 realistically capture the characteristics of urban road networks, making them suitable as simulation environments for testing our algorithms. To evaluate the soundness of our instances, we define metrics and distributions, each designed to capture specific characteristics

First, we aim for the structural properties of the flow network to reflect the infrastructure of real cities. This is partially achieved because the graphs associated with the instances are always planar, which aligns with the physical constraints of urban areas. Additionally, it is worth noting that certain areas within a city often exhibit a grid-like structure, where the average node degree typically lies between 3 and 4. This characteristic is observed in our instances: the average degrees (± standard deviation) range from 3.418 ± 1.865 to 4.645 ± 1.751.

We also aim for the ranges of the flow values to be relatively diverse. Figure 5 presents boxplots illustrating the distributions of the minimum and maximum flow values for each instance. As shown, the minimum flow values for an instance range from 3 to 26, while the corresponding maximum values range from 39 to 100. These results indicate that the flow values exhibit a sufficiently broad range.
<figure><img src="image_2.png" /><figcaption>Figure 1: The ranges associated to the minimal and maximal flow values across instances.</figcaption></figure>

We also aim to know how many vertices in the graph are points of interest (appearing as a source or a destination of an origin-destination pair). Figure 2 presents a histogram illustrating the proportion of nodes that appear in a given number of origin-destination pairs across all instances. For each value *k* on the x-axis, a corresponding boxplot shows the distribution of the number of nodes that appear exactly *k* times among the origin-destination pairs of an instance. The histogram in Figure 2 shows that 68% of all nodes do not appear in any origin-destination pair, 25% appear in exactly one pair, and 8% appear in two or more pairs (with 5% appearing in exactly two). These results are consistent with the boxplots in Figure 2, which show that, for each instance, the number of nodes which do not appear in any origin-destination pair is typically around 50, the number of nodes appearing in exactly one pair ranges from 10 to just under 30, and the number of nodes appearing in more than one pair does not exceed 10. We can conclude that enough nodes appear as points of interests of the instances and that those nodes are sufficiently distributed across the origin-destination pairs.
<figure><img src="image_3.png" /><figcaption>Figure 2: The number of occurrences of the nodes among the point of interests of the graph.</figcaption></figure>

Finally, another desirable property that we want to see in our networks is that the global flow passing through the arcs of the graph must come from multiple sources. Figure 2 presents a histogram showing the proportion of flow in the arcs originating from each origin-destination pair across all instances. For each value *k* on the x-axis of Figure 2, a corresponding boxplot shows the distribution of the number of arcs that are traversed by *k* flows of an instance. As shown in the histogram in Figure 2, 36.4% of all arcs are traversed by exactly one flow, 28% by two flows, 19.2% by three flows, and 16.4% by more than three distinct flows. These results seem consistent with the boxplots in Figure 2, although their spread heavily overlaps. Overall, much of the flow traversing the graph comes from multiple sources, which is expected from a real city.

<figure><img src="image_4.png" /><figcaption>Figure 3: The number of flows passing through the arcs of the instances.</figcaption></figure>

We conclude that the generated instances are sufficiently similar to real urban networks to serve as
simulation environments for evaluating our algorithms. In the next subsection, we present the evaluation and comparison of our approaches.

## 8.3 Evaluation and Comparison

In the following section, we evaluate and compare the performances of the heuristics presented in section 5 and 6. The figures in subsections 8.3.1, 8.3.2, and 8.3.3 are generated using the same approach. Each of this figures contains subfigures depicting a comparison of heuristics introduced in sections 5 and 6 in terms of the flow value residue (top left), the flow residue (top right), the multiflow residue (bottom left) and the transition function residue (bottom right). In all such subfigures, the abscissa axis represents the instances, and the ordinate axis represents the values of their corresponding performance metric, which are ranked in descending order. Next to the legends, the mean performance is shown along with its 95% BCa bootstrapped confidence interval generated using Python.

### 8.3.1 Comparison of baseline heuristics

Figure 4 presents a comparison of the performances of the baseline heuristics introduced in section 5 in terms of the flow value residue (Figure 4a), the flow residue (Figure 4b), the multiflow residue (Figure 4d) and the transition function residue (Figure 4c). In every subfigure of Figure 4, the abscissa axis represents the instances, and the ordinate axis represents the values of their corresponding performance metric, which are ranked in descending order. Legend *trans.func* corresponds to the transition function based heuristics, while *random* denotes a baseline heuristic implementing Algorithm 1 where paths are chosen by performing a random walk from the selected source to the selected destination. Next to the legends, the mean performance is shown along with its 95% BCa bootstrapped confidence interval generated using Python.

As expected, the performance of the random walk method is inferior to that of all other methods, as its corresponding curve is higher than that of any other method in figures 4a, 4b, 4d and 4c. This observation is further supported by the fact that the confidence intervals associated with the random walk method—namely, [0.256, 0.285] (Figure 4a), [0.168, 0.192] (Figure 4b), [0.361, 0.377] (Figure 4d), and [0.54, 0.562] (Figure 4c)—do not overlap with the corresponding confidence intervals of the other methods.
<figure><img src="image_5.png" /><figcaption>Figure 4: The values of the residues for all the baseline heuristics.</figcaption></figure>

Figure 4d shows that the multi-flow residue of the transition function based heuristic is lower than that of the baseline heuristics (Min-Time and Max-Capacity), indicating that the transition function based heuristic disaggregates the total flow more effectively than the baseline methods. This is further supported by its confidence interval, namely [0.156, 0.172], which is significantly lower than that of the baseline methods. And as shown in Figure 4c, the transition function residue achieved by the transition function based method is considerably lower than that of the baseline methods. Specifically, the residue does not exceed 0.2 for the transition function based heuristic, while it consistently exceeds 0.2 for all baseline approaches. This suggests that the transition function constructed using the transition function based heuristic more closely approximates the true transition function than the baseline methods, demonstrating that the transition function heuristic is better at matching the real transition function. And because the transition function based method fails to produce a multiflow with a lower value of τ and ρ than the baseline methods (as shown in figure 4a and 4b), we conclude that the transition function based heuristic produces a multi-flow close to the real one by approaching the real transition function. Finally, note that the Min-Time approach yields the lowest flow value residue and flow residue (as shown in Figures 4a and 4b), which can be attributed to the fact that the multi-flow generation is based on the arc trip durations which are also relied upon in the Min-Time approach.
### 8.3.2 Comparison of the transition function based heuristic with the RL heuristic (node based and arc based)

Figure 5 presents a comparison of the performances of the distributed reinforcement learning heuristic introduced in section 6 in terms of the flow value residue (Figure 5b), the flow residue (Figure 4b), the multiflow residue (Figure 5d) and the transition function residue (Figure 5c). In every subfigure of Figure 5, the abscissa axis represents the instances, and the ordinate axis represents the values of their corresponding performance metric, which are ranked in descending order. Legend *rl_node_based* corresponds to the node based distributed reinforcement learning approach, and legend *rl_arc_based* corresponds to the arc based distributed reinforcement learning approach. Next to the legends, the mean performance is shown along with its 95% BCa bootstrapped confidence interval generated using Python.

<figure><img src="image_6.png" /><figcaption>Figure 5: Comparison between the distributed reinforcement learning based heuristics and the transition function based heuristic.</figcaption></figure>

For both the node based and arc based approaches, Figure 5 shows that the reinforcement learning based heuristic achieves lower residue values than the transition function-based heuristic. This is clearly illustrated by the fact that the confidence interval of the residues associated with the transition function-based approach is significantly higher than those of the distributed reinforcement learning based approaches. These results
indicate that flow disaggregation can be achieved through an algorithm that learns to adapt the transition function to construct a multiflow maximizing a reward signal dependent on the metrics presented in Section 3.

Figures 5a, 5b, and 5c show that the mean performance of the flow value residue, the flow residue, and the transition function residue is higher for the arc based approach compared to the node based approach. Along with the fact that the confidence intervals of the flow value residue, the flow residue and the transition function associated to the arc based approach do not intersect with the residues of the node based approach, we conclude that the arc based approach achieves better values of $\tau$, $\rho$ and $\delta$ than the node based approach. Because the confidence intervals of the multi flow residue of the node based approach and the arc based share significant overlap (namely the intervals [0.11, 0.123] and [0.10, 0.116]), a test was perfomed to asses if the multi flow residue of the node based approach is lower or equal than that of the arc based approach. The test rejects the hypothesis with a p-value of 0.06. Although the p-value does not fall below the conventional threshold of 0.05, it is still sufficiently low to support the conclusion that the arc-based approach has better multiflow residue than the node based approach. In summary, the arc-based approach seems to outperform the node-based approach across all considered residues. These results suggest that it may be more effective at disaggregating the flow than the node-based approach.

### 8.3.3 Compare the multiple paths approach with the one path approach

Figure 6 presents a comparison of the performances of the multipath distributed reinforcement learning heuristic introduced in section 6.3 with the one path approach in terms of the flow value residue (Figure 6a), the flow residue (Figure 6b), the multiflow residue (Figure 6d) and the transition function residue (Figure 6c). In every subfigure of Figure 6, the abscissa axis represents the instances, and the ordinate axis represents the values of their corresponding performance metric, which are ranked in descending order. Legend *rl_arc_one_path_based* corresponds to the one path arc based distributed reinforcement learning approach, and legend *rl_arc_multi_path_based* corresponds to the multipath arc based distributed reinforcement learning approach. Next to the legends, the mean performance is shown along with its 95% BCa bootstrapped confidence interval generated using Python. Table 2 depicts the p-values associated to the test of the hypotheses $H_0: \tau_{one_path} \le \tau_{mul_path}$, $H_0: \rho_{one_path} \le \rho_{mul_path}$, $H_0: \delta_{one_path} \le \delta_{mul_path}$ and $H_0: \epsilon_{one_path} \le \epsilon_{mul_path}$ from left to right.
<figure><img src="image_7.png" /><figcaption>Figure 6: Comparison of the multipath and the mono path methods.</figcaption></figure>

<table><caption>Table 2: List of the main notations concerning the algorithms and concepts of.</caption><thead><tr><th>residues</th><th>τ</th><th>ρ</th><th>δ</th><th>ε</th></tr></thead><tbody><tr><td>p-values</td><td>0.006</td><td>0.026</td><td>0.078</td><td>0.1</td></tr></tbody></table>

Figures 6a, 6b, 6c, and 6d suggest that the residues associated with the multipath approach are lower than those of the one path approach. Noting in Table 2 the p-values of 0.006 and 0.026 associated to τ and ρ respectively, we can safely conclude that the multipath approach produces lower flow value residue and flow residue compared to the one path approach. This suggests that the multipath approach more effectively distributes the flow across the pairs and arcs of the network during the disaggregation process. However, as shown in Table 2, the p-values associated with the transition function residue and the multiflow residue are 0.078 and 0.1, respectively. While these values do not fall below the conventional significance threshold of 0.05, they are still sufficiently low to suggest a tendency for the multipath approach to produce lower residues than the one path approach. Overall, the multipath approach appears to outperform the one path approach across all residue measures considered. These findings indicate that it may be more effective at
disaggregating the flow.

### 8.3.4 Study the effect of increasing the number of nodes in the graph.

Figure 7 depicts in the form of heatmaps, the performances of the distributed system of agents across different values for the number of nodes (55, 75, 95) and the number of pairs (10, 15, 20). The flow value residue is shown in Figure 7a, the flow residue is shown in Figure 7b, the transition function residue is shown in Figure 7c, and the multiflow residue is shown in Figure 7d. The residues are averaged across all executions of the algorithm for the value of the learning rate achieving the highest reward at the final episode. Figure 8b presents the rate of change (scaled by 1000) of the multiflow residue along the x-axis and the y-axis of Figure 7d.

<figure><img src="image_8.png" /><figcaption>Figure 7: Heatmaps showing the performances of our method as a function of the number of nodes and the number of pairs.</figcaption></figure>
<figure><img src="image_9.png" /><figcaption>Figure 8: Heatmaps showing the rate of change of the multiflow residue (scaled by 1000) as a function of the number of nodes (a) and the number of pairs (b).</figcaption></figure>

Naturally, we observe in Figure 7 that the residue obtained from executing the distributed reinforcement learning based heuristic increases as the number of nodes or the number of pairs increases. As expected, these results suggest that increasing either the number of nodes or the number of pairs increases the difficulty of the instances for the algorithms. Figure 8 allows us to identify which one of the parameters has the greatest impact on the performances of the algorithm. Figure 8a illustrates the performance impact of increasing the number of nodes, whereas Figure 8b reflects the performance impact of increasing the number of pairs.

We observe from Figure 8a that the rate of change of the multiflow residue with respect to the number of nodes generally lies between $0.3814 \times 10^{-3}$ and $0.5484 \times 10^{-3}$. The only exceptions occur at 55 nodes, with 15 and 20 pairs yielding notably higher values of $1.2152 \times 10^{-3}$ and $1.1125 \times 10^{-3}$, respectively. Conversely, Figure 8b shows that the rate of change with respect to the number of pairs is mostly contained within the interval $5.7414 \times 10^{-3}$ to $6.9477 \times 10^{-3}$, except for a lower outlier of $3.8336 \times 10^{-3}$, corresponding to the case of 10 pairs with 55 nodes. And since all values of the rate of change of the multiflow residue with respect to the number of nodes exceed those with respect to the number of pairs, these results tend to indicate that increasing the number of pairs has a stronger impact on the difficulty of the instances of our problem compared to increasing the number of nodes.

### 8.3.5 Performance study in real instances and comparison with simulated instances

In the following, we present the results obtained from applying the heuristics proposed in this work (baseline and distributed RL) to the instances generated from the graph associated to Lieusaint.

#### Comparison of baseline heuristics

Figure 9 presents a comparison of the performances of the baseline heuristics applied to the real instances (analogous to the Figure 4).
<figure><img src="image_10.png" /><figcaption>Figure 9: The values of the residues for all the baseline heuristics in Lieusaint instances.</figcaption></figure>

Unlike in Figure 4, we note in Figure 9 that the multiflow residue achieved is better with approach *Min-Time* compared to other methods. We also note that the residues linked to the transition function-based approach are comparable to those obtained with the random heuristic and represent the highest values among all methods. These results indicate that the flow predominantly follows the shortest paths in the graph and is randomly distributed across the arcs within those paths.

## Distributed RL based heuristic

Figure 10 presents a comparison of the performances of the distributed RL based heuristic (arc based with multiple paths variant) with that of the *Min-Time* approach applied to the real instances. The learning rate associated with the RL based approach is set to 0.025.
<figure><img src="image_11.png" /><figcaption>Figure 10: Comparison between the distributed reinforcement learning based heuristics and the transition function-based heuristic in Lieusaint instances.</figcaption></figure>

We note from Figure 10 that the residues associated with the RL based heuristics are higher compared to the residues associated with heuristic *Min-Time*. This result is consistent with the observation from the previous analysis. Indeed, if the flow is mainly routed through the shortest paths and randomly distributed across the arcs within those paths, a transition function becomes somewhat less effective even when learned through interaction by the algorithm. Note that this behaviour would not, in principle, be expected to occur in larger graphs.

# 9 Conclusion and Perspectives

These experimental results demonstrate that distributed reinforcement learning on graphs is an effective base of heuristic approaches for the flow Disaggregation problem, in terms of minimizing residual values. The experiments conducted and analyzed in this article seem to show that this heuristic approach finds multi-flows that are closer to the optimal solutions in the simulated instances, compared to optimization approaches classically used in this context. However, for small real-world instances, the Min-Time heuristic appears to yield the best results. Our hypothesis is that few possible multi-flows exist in these instances, which is more
favorable to optimization approaches, as learning approaches are limited in their distributed exploration phases. Larger and more complex real-world instances will need to be tested for a more comprehensive comparison of these two approaches.

## References

[1] A. Bhaskar B. Bevrani, R. Burdett and P. K.D.V. Yarlagadda. A multi-criteria multi-commodity flow model for analysing transportation networks. *Operations Research Perspectives*, 7:3057-3098, 2020.

[2] G. Baier, E. Kohler, and M. Skutella. On the k-splittable flow problem. *Algorithmica*, 42:231–248, 2005.

[3] Dominique Barth, Wei Chen, Nassim Haddam, and Taissir Marce. Performance of aggregated multi-commodity flows discovery algorithms in a urban road network for the discovery of mobility patterns. In *26th Euro Working Group on Transportation Meeting (EWGT 2024). In Transportation Research Procedia 86*, volume 86, pages 786–792, 2025.

[4] Dominique Barth, Johanne Cohen, Olivier Bournez, and Octave Boussaton. Distributed learning of equilibria in a routing game. *Parallel Processing Letter*, 19(2):189–204, 2009.

[5] CrowleyVS. osmtoroadgraph 0.6.0.

[6] C. Comito E. Cesario and D. Talia. An approach for the discovery and validation of urban mobility patterns. *Pervasive and Mobile Computing*, 42:77–92, 2017.

[7] Zhang Fan, Wang Jiazheng, Mathieu Lacroix, Roberto Wolfler Calvo, and Youcef Magnouche. The multi-commodity flow problem: Double dantzig-wolfe decomposition. In *10th IEEE International Conference on Control, Decision and Information Technologies (CoDIT)*, 2024.

[8] R. K. Ahuja J. B. Orlin and T. L. Magnanti. *Network Flows: Theory, Algorithms and Applications*. Prentice Hall, 1993.

[9] J. Kim and H.S. Mahmassani. Spatial and temporal characterization of travel patterns in a traffic network using vehicle trajectories. *Transportation Research Part C Emerging Technologies*, 9, 2015.

[10] X. Kong and et al. Mobility trajectory generation: a survey. *Artif Intell Rev*, 56 (Suppl 3), 2023.

[11] I. X. Y. Leung, S. Yan Chan, P. Hui, and P. Lio. Intra-city urban network and traffic flow analysis from gps mobility trace. *ArXiv 2011*, abs/1105.5839, 2011.

[12] Abdel Lisser and Philippe Mahey. *Multicommodity Flow Problems and Decomposition in Telecommunications Networks*, pages 241–267. Springer US, 2006.

[13] D. Marx. Eulerian disjoint paths problem in grid graphs is np-complete. *Disc. Appl. Math.*, 2004.

[14] Kumpati S. Narendra and Mandayam A.L. Thathachar. *Learning Automata: An Introduction*. Prentice Hall, 1989.

[15] Martin Ramm. Overpass turbo.

[16] Khodakaram Salimifard and Sara Bigharaz. The multicommodity network flow problem: state of the art classification, applications, and solution methods. *Operational Research*, 22(1):1–47, 2022.

[17] Bulent Soykan and Ghaith Rabadi. Optimizing multi commodity flow problem under uncertainty: A deep reinforcement learning approach. In *International Conference on Machine Learning and Applications (ICMLA)*, 2023.
[18] Richard S. Sutton and Andrew G. Barto. *Introduction to Reinforcement Learning*. MIT Press, Cambridge, MA, USA, 1st edition, 1998.

[19] B. Vantilen and et al. Simple bounds and greedy algorithms for decomposing a flow into a minimal set of paths. In *EJOR*, 2006.

[20] J. Vygen. Np-completeness of some edge-disjoint paths problems. *Disc. Appl. Math.*, 1995.

[21] M. Hou X. Kong, Q. Chen and al. Mobility trajectory generation: a survey. *Artif Intell Rev 56 (Suppl 3)*, page 3057-3098, 2023.