## 4 Proposed Methods
### Augmented Graph
#### 4.1.2 Additional Adjacency Matrix  
We introduced some supporting matrices to support the proposed algorithm. First of all, we introduced _edge matrix_, denoted as \({}^{\mathrm{e}}B=\left\{{}^{\mathrm{e}}b_{i,j}|\dot{t},j\in\{1,2,\ldots,N_{ \mathrm{v}}\}\right\}\), whose dimension is the same with the adjacency matrix \(B\). Let \({}^{\mathrm{\prime}}e\), where \(q\) is the identifier of an edge whose value can be determined by Algorithm 1, be defined as the edge identifier of each element of \(B\), i.e., \(b_{i,j}\) that has the value of \(1\). Therefore, we get the following:  
\[{}^{\mathrm{e}}b_{i,j}=\left\{ \begin{array}{c}{}^{\mathrm{\prime}}e,\ \ \text{if}\ b_{i,j}>1,\\ 0,\ \text{otherwise}.\end{array} \right. \tag{4}\]  
where \(i,j\in\{1,2,\ldots,N_{\mathrm{v}}\}\). Figure 1: Augmented nodes and edges. Figure 2: The proposed augmented graph. For instance, suppose that we have the following adjacency matrix of a graph \(G\) whose number of nodes is \(5\), as follows. \[B=\left[ \begin{array}{ccccc}0&1&0&1&0\\ 0&0&1&0&0\\ 1&0&0&1&0\\ 0&1&1&0&0\\ 0&1&1&1&0\end{array} \right] \tag{5}\]  
Therefore, by using (4), we have the following:  
\[{}^{\rm e}B=\left[ \begin{array}{ccccc}0&{}^{1}e&0&{}^{2}e&0\\ 0&0&{}^{3}e&0&0\\ {}^{4}e&0&0&{}^{5}e&0\\ 0&{}^{6}e&{}^{7}e&0&0\\ 0&{}^{8}e&{}^{9}e&{}^{10}e&0\end{array} \right] \tag{6}\]  
Furthermore, we use the index of \({}^{\rm q}e\), i.e., \(q\) as the index of row of another adjacency matrix named _trajectory adjacency matrix_, denoted as \({}^{\rm\psi}B\). Each row and each column of this matrix represent edge \({}^{\rm q}e\) and speed \(s_{l}\), respectively. Let \({}^{\rm p}\psi\) be the element of \({}^{\rm\psi}B\), where we have the following:  
\[p(q,l)=(q-1)N_{s}+l\,, \tag{7}\]  
\(l\in\{1,2,\ldots,N_{\rm s}\}\) and \(q\) are defined in (4). Suppose that we apply three-speed options; therefore, \(N_{\rm s}=3\). From the adjacency matrix example in Equation (5) and its respective edge matrix in (6), we have the elements of \(T\) as follows: For edge \({}^{1}e\), we have three trajectories, i.e., \({}^{1}\psi\), \({}^{2}\psi\), and \({}^{3}\psi\). Since from Equations (5) to (7), \({}^{1}e\) represents \(e_{1}\),\({}^{2}\psi\), and \({}^{3}\psi\) represent \(\psi_{1,2,1}\), \(\psi_{1,2,2}\), and \(\psi_{1,2,3}\), respectively. Similarly, \({}^{5}e\) represents \(e_{3,4}\). By using (10), we have trajectories \({}^{13}\psi\), \({}^{14}\psi\), and \({}^{15}\psi\). Therefore, according to Equations (5)-(7), \({}^{13}\psi\), \({}^{14}\psi\), and \({}^{15}\psi\) represent \(\psi_{3,4,1}\), \(\psi_{3,4,2}\), and \(\psi_{3,4,3}\), respectively. The last adjacency matrix is the _augmented-edge adjacency matrix_, denoted by \({}^{\rm\xi}B\), where the row and column are indexed by the index of \({}^{\rm p}\psi\), i.e., \(p\). Let \({}^{h}\xi\) be the element of \({}^{\rm\xi}B\), whose value is not zero and be associated to \(\xi_{i_{1},i_{1},i_{1}}^{{}^{2}\psi_{2}\psi_{3}}\) by applying Algorithm 2. The functions \(\textit{row}_{\psi}(x)\), \(\textit{start}_{\rm e}(x)\), and \(\textit{end}_{\rm e}(x)\) return the row index belonged to the row in \({}^{\rm\psi}B\) containing \(x\), the indexes of start and end node in \({}^{\rm\alpha}B\), respectively. In the previous example, there are ten edges and three speed options. The number of trajectories is \(30\) and the dimension of \({}^{\rm\xi}B=\mathbb{Z}^{30\times 30}\). Until this step, we have the following adjacency matrices:\({}^{\rm e}B\), \({}^{\rm\psi}B\), and \({}^{\rm\xi}B\). Suppose that we are given \({}^{h}\xi\); then, by using the map described in \({}^{\rm\xi}B\), we obtain \({}^{p_{1}}\psi\) and \({}^{p_{2}}\psi\), where \(p_{1}\) and \(p_{2}\) are the indexes of the row and column of \({}^{\rm\xi}B\) associated to \({}^{h}\xi\). After that, we check the map in \({}^{\rm\psi}B\), and we obtain the edge \({}^{q}e\) and speed option \(s_{l}\) for each \({}^{p_{1}}\psi\) and \({}^{p_{2}}\psi\).