# A distributed approach for shortest path algorithm in dynamic multimodal transportation networks

Abdelfattah Idri, Mariyem Oukarfi, Azedine Boulmakoul, Karine Zeitouni, Ali Masri

► To cite this version:

Abdelfattah Idri, Mariyem Oukarfi, Azedine Boulmakoul, Karine Zeitouni, Ali Masri. A distributed approach for shortest path algorithm in dynamic multimodal transportation networks. 20th EURO Working Group on Transportation Meeting, EWGT 2017, Sep 2017, Budapest, Hungary. pp.294-300, 10.1016/j.trpro.2017.12.094 . hal-04371619

HAL Id: hal-04371619

https://hal.univ-lille.fr/hal-04371619

Submitted on 3 Jan 2024

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>
# A distributed approach for shortest path algorithm in dynamic multimodal transportation networks

Abdelfattah Idri, Mariyem Oukarfi, Azedine Boulmakoul, Karine Zeitouni, Ali Masri

► To cite this version:

Abdelfattah Idri, Mariyem Oukarfi, Azedine Boulmakoul, Karine Zeitouni, Ali Masri. A distributed approach for shortest path algorithm in dynamic multimodal transportation networks. 20th EURO Working Group on Transportation Meeting, EWGT 2017, Sep 2017, Budapest, Hungary. pp.294-300, 10.1016/j.trpro.2017.12.094. hal-04371619

HAL Id: hal-04371619

https://lilloa.hal.science/hal-04371619v1

Submitted on 3 Jan 2024

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>
20th EURO Working Group on Transportation Meeting, EWGT 2017, 4-6 September 2017,
Budapest, Hungary

A distributed approach for shortest path algorithm in dynamic
multimodal transportation networks

Abdelfattah IDRIb*, Mariyem OUKARFIa, Azedine BOULMAKOULa, Karine ZEITOUNIc and Ali MASRIc

aLIM Lab. IOS, Computer Sciences Department, Faculty of Sciences and Technology Mohammed, Mohammed, Morocco

bNational School of business and Management, Casablanca, Morocco

cDavid Lab. University of Versailles Saint-Quentin-en-Yvelines, Versailles, France

Abstract

In this paper we introduce a search approach for shortest path algorithm in a parallel distributed architecture which is designed to handle the time-dependency for multimodal transportation network. Our proposed algorithm relies on its effective target-oriented approach of reducing the search space while the distributed parallel processing focuses on reducing the computational time. The optimality of the algorithm is principally based on computing a virtual path which is basically an Euclidean distance from the source to the destination aiming at a restriction of the search space. After the presentation of the distributed algorithm, a profiling of the algorithm is given to evaluate its computing performance.

© 2017 The Authors. Published by Elsevier B.V.

Peer-review under responsibility of the scientific committee of the 20th EURO Working Group on Transportation Meeting.

Keywords: distributed shortest path algorithm; time-dependent multimodal transportation network; distributed architecture CORBA

**1. Introduction**

Route planning in highly developed transportation networks is gaining more and more importance considering
the evolution of transport means and the emergence of advanced intelligent transportation systems. Nowadays, the
mobility of goods and persons turns into a major challenge especially in critical fields such as transportation of
hazardous materials.

<footnote>* Corresponding author. Tel.: +212662038857 ; Fax: 212 (05) 23315353
E-mail address: abdelfattah.id@gmail.com</footnote>
20th EURO Working Group on Transportation Meeting, EWGT 2017, 4-6 September 2017,
Budapest, Hungary

A distributed approach for shortest path algorithm in dynamic
multimodal transportation networks

Abdelfattah IDRIb*, Mariyem OUKARFIa, Azedine BOULMAKOULa, Karine ZEITOUNIc and Ali MASRIc

aLIM Lab. IOS, Computer Sciences Department, Faculty of Sciences and Technology Mohammed, Mohammed, Morocco

bNational School of business and Management, Casablanca, Morocco

cDavid Lab. University of Versailles Saint-Quentin-en-Yvelines, Versailles, France

Abstract

In this paper we introduce a search approach for shortest path algorithm in a parallel distributed architecture which is designed to handle the time-dependency for multimodal transportation network. Our proposed algorithm relies on its effective target-oriented approach of reducing the search space while the distributed parallel processing focuses on reducing the computational time. The optimality of the algorithm is principally based on computing a virtual path which is basically an Euclidean distance from the source to the destination aiming at a restriction of the search space. After the presentation of the distributed algorithm, a profiling of the algorithm is given to evaluate its computing performance.

© 2017 The Authors. Published by Elsevier B.V.

Peer-review under responsibility of the scientific committee of the 20th EURO Working Group on Transportation Meeting.

Keywords: distributed shortest path algorithm; time-dependent multimodal transportation network; distributed architecture CORBA

**1. Introduction**

Route planning in highly developed transportation networks is gaining more and more importance considering
the evolution of transport means and the emergence of advanced intelligent transportation systems. Nowadays, the
mobility of goods and persons turns into a major challenge especially in critical fields such as transportation of
hazardous materials.

<footnote>* Corresponding author. Tel.: +212662038857 ; Fax: 212 (05) 23315353</footnote>

<footnote>E-mail address: abdelfattah.id@gmail.com</footnote>
Travelers ask for efficient routing methods allowing them to reach their destinations through large-scale networks involving different scheduled and non-scheduled transportation modes. For this reason, many applications of algorithmic that compute an optimal route from a source to a destination in a multimodal network have been proposed to deal with this combinatorial optimization problem under additional constraints such as dynamic changing traveling data.

Accordingly, single-source single-destination shortest path algorithms in dynamic multimodal transportation network have known increasingly improvements adopting different optimization approaches. On one hand, concerning the problematic of time-dependency, multiple researches have been done. Besides the classical solutions for routing in static networks such as speed up techniques (Bastet al. 2014), Cooke and Halsey (1966) introduced the dynamic aspect to cope with the time dependency aspect of public transportation modes. Pyrga et al. (2008) detailed the realistic version of the time-dependent and time-expanded model for public transportation network. Bakalov et al. (2015) described the time-dependent network model tailored towards the need of transportation network modeling. On the other hand, we can find relevant works done in time-dependency problem. Schultes et al. (2008) and Pajor et al. (2009) did extensive research to extend networks from single mode to multimodal. Liu et al. (2009) proposed a switch point approach to model multimodal transport networks. Peng et al. (2008) proposed a distributed solution for planning of trips in a larger transport system. Ayed et al. (2008) proposed a transfer graph approach for multimodal transport problems. Lozano et al. (2002) adopted the concept of hypergraphs as Bielli et al. (2006) worked on hierarchical graph. Zhang et al. (2014) investigates the multimodal network design problem that optimizes the auto network expansion scheme and bus network design scheme. Ziliaskopoulos and Wardell (2000) presented a time-dependent intermodal optimum path algorithm for multimodal transportation networks that accounts for delays at mode and arc switching points.

## 2. Time-dependent multimodal network

**Definition.** Let $G = (V, E, M, T)$ denotes the time-dependent multimodal directed graph or network, where $M = \{m_1, ..., m_k\}$ is a set of transport mode (e.g., train, bus, metro). An edge $e_i \in E$ can be identified by $(v_i, v_{i'}, m_i)$ where $v_i, v_{i'} \in V \land m_i \in M$. $e_i$ means the possibility of going from node $v_i$ to $v_{i'}$ by using transport mode $m_i$. A path $p = \{e_1, e_2, ..., e_k\}$ is said to be multimodal if $\exists e_i, e_j \in A, e_i = (v_i, v_{i'}, m_i) = \{v_i, v_{i'}, m_i\}, e_j = (v_j, v_{j'}, m_j) = \{v_j, v_{j'}\}, m_i \neq m_j, \text{ and } i, j \leq k$. The edge $e = \{v, v'\}_m$ has a time-dependent distance cost $c_e(t)$. Let $t, t'$ denote time in a discrete set $\{t_1, ..., t_l\}$, the travel for the edge $e$ is defined as tuple $(t, t') \in T$ where $t$ is the departure time from node $v$, and $t'$ is the arrival time at node $v'$.

<table><caption>Table 1. Time table</caption><thead><tr><th colspan="3">Mode 1</th></tr><tr><th>Edges</th><th>Time</th><th>Travel time</th></tr></thead><tbody><tr><td rowspan="2">a → b</td><td>2 → 3</td><td>1</td></tr><tr><td>2 → 4</td><td>2</td></tr></tbody><thead><tr><th colspan="3">Mode 2</th></tr><tr><th>Edges</th><th>Time</th><th>Travel time</th></tr></thead><tbody><tr><td rowspan="2">d → b</td><td>1 → 4</td><td>3</td></tr><tr><td>8 → 10</td><td>2</td></tr><tr><td rowspan="2">b → c</td><td>5 → 6</td><td>1</td></tr><tr><td>10 → 11</td><td>1</td></tr></tbody></table>

<figure><img src="image_2.png" /><figcaption>Figure 1. Multimodal graph</figcaption></figure>
Travelers ask for efficient routing methods allowing them to reach their destinations through large-scale networks involving different scheduled and non-scheduled transportation modes. For this reason, many applications of algorithmic that compute an optimal route from a source to a destination in a multimodal network have been proposed to deal with this combinatorial optimization problem under additional constraints such as dynamic changing traveling data.

Accordingly, single-source single-destination shortest path algorithms in dynamic multimodal transportation network have known increasingly improvements adopting different optimization approaches. On one hand, concerning the problematic of time-dependency, multiple researches have been done. Besides the classical solutions for routing in static networks such as speed up techniques (Bastet al. 2014), Cooke and Halsey (1966) introduced the dynamic aspect to cope with the time dependency aspect of public transportation modes. Pyrga et al. (2008) detailed the realistic version of the time-dependent and time-expanded model for public transportation network. Bakalov et al. (2015) described the time-dependent network model tailored towards the need of transportation network modeling. On the other hand, we can find relevant works done in time-dependency problem. Schultes et al. (2008) and Pajor et al. (2009) did extensive research to extend networks from single mode to multimodal. Liu et al. (2009) proposed a switch point approach to model multimodal transport networks. Peng et al. (2008) proposed a distributed solution for planning of trips in a larger transport system. Ayed et al. (2008) proposed a transfer graph approach for multimodal transport problems. Lozano et al. (2002) adopted the concept of hypergraphs as Bielli et al. (2006) worked on hierarchical graph. Zhang et al. (2014) investigates the multimodal network design problem that optimizes the auto network expansion scheme and bus network design scheme. Ziliaskopoulos and Wardell (2000) presented a time-dependent intermodal optimum path algorithm for multimodal transportation networks that accounts for delays at mode and arc switching points.

## 2. Time-dependent multimodal network

**Definition.** Let $G = (V, E, M, T)$ denotes the time-dependent multimodal directed graph or network, where $M = \{m_1, ..., m_k\}$ is a set of transport mode (e.g., train, bus, metro). An edge $e_i \in E$ can be identified by $(v_i, v_{i'}, m_i)$ where $v_i, v_{i'} \in V \land m_i \in M$. $e_i$ means the possibility of going from node $v_i$ to $v_{i'}$ by using transport mode $m_i$. A path $p = \{e_1, e_2, ..., e_k\}$ is said to be multimodal if $\exists e_i, e_j \in A, e_i = (v_i, v_{i'}, m_i) = \{v_i, v_{i'}\}_{mi}, e_j = (v_j, v_{j'}, m_j) = \{v_j, v_{j'}\}_{mj}, m_i \neq m_j, \text{ and } i, j \leq k$. The edge $e = \{v, v'\}_m$ has a time-dependent distance cost $c_e(t)$. Let $t, t'$ denote time in a discrete set $\{t_1, ..., t_l\}$, the travel for the edge $e$ is defined as tuple $(t, t') \in T$ where $t$ is the departure time from node $v$, and $t'$ is the arrival time at node $v'$.

<table><caption>Table 1. Time table</caption><thead><tr><th colspan="3">Mode 1</th></tr><tr><th>Edges</th><th>Time</th><th>Travel time</th></tr></thead><tbody><tr><td rowspan="2">a → b</td><td>2 → 3</td><td>1</td></tr><tr><td>2 → 4</td><td>2</td></tr></tbody><thead><tr><th colspan="3">Mode 2</th></tr><tr><th>Edges</th><th>Time</th><th>Travel time</th></tr></thead><tbody><tr><td rowspan="2">d → b</td><td>1 → 4</td><td>3</td></tr><tr><td>8 → 10</td><td>2</td></tr><tr><td rowspan="2">b → c</td><td>5 → 6</td><td>1</td></tr><tr><td>10 → 11</td><td>1</td></tr></tbody></table>

<figure><img src="image_2.png" /><figcaption>Figure 1. Multimodal graph</figcaption></figure>
A simplified graph in figure 1 presents a multimodal time-dependent graph with two modes *mode1* and *mode2*. We construct the graph based on the adjacency matrix which affects the distance cost to each edge. Suppose that it is possible to switch from *mode1* on arc(*a*, *b*) to *mode2* on arc (*b*, *c*) and that transfer node for this switching is *b*. The delay associated with this mode switch is then calculated for each time interval by first determining at what time *mode1* arrives at node *b* and leaves it. According to the time table in table 1, if *mode1* departs from node *a* at time interval 2 and arrives at node *b* at 3, then switches to *mode2* through the arc (*b*, *c*) at the time interval 5 → 6, the delay associated with this mode switch is two time interval which is added to the total travel cost of the path.

### 3. Constrained shortest path algorithm

To respond to the issue of finding the shortest path in a time-dependent multimodal network, the Constrained Shortest Path Algorithm (CSPA), as introduced by Idri et al. (2017); is proposed to optimize the search space using the concept of “closeness” to the distance as the crow flies which we call it the “virtual path”. Thus, the main idea of the proposed searching approach is to drive the search toward the connected nodes close to the virtual path by a parameter *d* as mentioned in figure 2.

<figure><img src="image_3.png" /><figcaption>Figure 2. Illustrative example of the algorithm</figcaption></figure>

The main idea behind the algorithm approach is to explore the nodes in a restricted search space defined by four parameters:

* Virtual path (*st*): is the Euclidean distance from *s* to *t*, represents the reference path

* Distance *d*: is the threshold distance of the search space, represents the mean distance value from all the vertices to the virtual path: calculate_threshold() { vᵢ ∈ V, d = Σn₁ dist(vᵢ, (st))/n } (3.1)

* Distance *d*<sub>max</sub>: is the maximum value of *d*, represents the distance value from the farthest vertex to (st).

* Distance Δ*d*: is the elementary step distance of the search space, represents the mean distance value from all the vertices to their neighbors' vertices: calculate_step() { vᵢ ∈ V, Δ*d*ᵢ = Σk₁ xᵢ/k

Δ*d* = Σn₁ Δ*d*ᵢ/n } (Where total_neighbours(vᵢ) = *k* and xᵢ the distance from vᵢ to its neighbor) (4.2)

In each searching iteration and after selecting a candidate vertex v that satisfies the condition dist(v, (st)) ≤ *d*, we apply the elementary step function OneStepMMTDSP(v, t) on v. This function applies a multimodal time-dependent shortest path algorithm to find the next candidate vertex for the next iteration. It can be substituted with any algorithm designed to find the SP in a time-dependent multimodal network.

We should mention that the virtual path presented as an Euclidean distance from *s* to *t* equal to *D* is a model to demonstrate our approach and we can adopt the same reasoning to other cost function like travel time. The logic of our algorithm remains applicable when we substitute *dist(w, (st))* with *f(s, w) + f(w, t)* which has to be less than *f(s, v) + f(v, t) = τ* (see figure 4), where *f* is the cost function and *τ* is the threshold value equivalent to *d*.

The algorithm logic is based on the constraint represented by the parameter *d* aiming at a restriction of the search space. It is resumed as presented in figure 3.
A simplified graph in figure 1 presents a multimodal time-dependent graph with two modes *mode1* and *mode2*. We construct the graph based on the adjacency matrix which affects the distance cost to each edge. Suppose that it is possible to switch from *mode1* on arc(*a*, *b*) to *mode2* on arc (*b*, *c*) and that transfer node for this switching is *b*. The delay associated with this mode switch is then calculated for each time interval by first determining at what time *mode1* arrives at node *b* and leaves it. According to the time table in table 1, if *mode1* departs from node *a* at time interval 2 and arrives at node *b* at 3, then switches to *mode2* through the arc (*b*, *c*) at the time interval 5 → 6, the delay associated with this mode switch is two time interval which is added to the total travel cost of the path.

### 3. Constrained shortest path algorithm

To respond to the issue of finding the shortest path in a time-dependent multimodal network, the Constrained Shortest Path Algorithm (CSPA), as introduced by Idri et al. (2017); is proposed to optimize the search space using the concept of “closeness” to the distance as the crow flies which we call it the “virtual path”. Thus, the main idea of the proposed searching approach is to drive the search toward the connected nodes close to the virtual path by a parameter *d* as mentioned in figure 2.

<figure><img src="image_3.png" /><figcaption>Figure 2. Illustrative example of the algorithm</figcaption></figure>

The main idea behind the algorithm approach is to explore the nodes in a restricted search space defined by four parameters:

* Virtual path (*st*): is the Euclidean distance from *s* to *t*, represents the reference path

* Distance *d*: is the threshold distance of the search space, represents the mean distance value from all the vertices to the virtual path: calculate_threshold() { vᵢ ∈ V, d = Σn₁ dist(vᵢ, (st))/n } (3.1)

* Distance *d*<sub>max</sub>: is the maximum value of *d*, represents the distance value from the farthest vertex to (st).

* Distance Δ*d*: is the elementary step distance of the search space, represents the mean distance value from all the vertices to their neighbors' vertices: calculate_step() { vᵢ ∈ V, Δ*d*ᵢ = Σk₁ xᵢ/k

Δ*d* = Σn₁ Δ*d*ᵢ/n } (Where total_neighbours(vᵢ) = *k* and xᵢ the distance from vᵢ to its neighbor) (4.2)

In each searching iteration and after selecting a candidate vertex v that satisfies the condition dist(v, (st)) ≤ *d*, we apply the elementary step function OneStepMMTDSP(v, t) on v. This function applies a multimodal time-dependent shortest path algorithm to find the next candidate vertex for the next iteration. It can be substituted with any algorithm designed to find the SP in a time-dependent multimodal network.

We should mention that the virtual path presented as an Euclidean distance from *s* to *t* equal to *D* is a model to demonstrate our approach and we can adopt the same reasoning to other cost function like travel time. The logic of our algorithm remains applicable when we substitute *dist(w, (st))* with *f(s, w) + f(w, t)* which has to be less than *f(s, v) + f(v, t) = τ* (see figure 4), where *f* is the cost function and *τ* is the threshold value equivalent to *d*.

The algorithm logic is based on the constraint represented by the parameter *d* aiming at a restriction of the search space. It is resumed as presented in figure 3.
If *d* reaches the maximum value which is the distance from the farthest vertex to the virtual path, the algorithm behaves just like any other MMTDSP (multimodal time-dependent shortest path) algorithm depending on MMTDSP function and all the graph vertices will be captured in the search space. On the other hand, when *d* is less then *d*<sub>max</sub>, then the algorithm will navigate back and forth relying on the density of the network. It starts from a restricted search space and enlarges it by Δ*d* until a shortest path is found, while each vertex not leading to a complete path is removed from the possible partial paths.

<figure><img src="image_4.png" /><figcaption>Figure 3. The algorithm process</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Figure 4. Calculation of threshold</figcaption></figure>

## 4. Distributed architecture

We study the possibility of improving the performance of the CSPA by examining the distribution and parallelism of the algorithm, more precisely the algorithm searching process. It generates multiple instances that run through the network to find the candidate paths.

The choice was made on the Manager / Agent model since it guarantees scalability and distribution services and this coincides well with our objective. The task of finding the final right path passes through constructing the right set of nodes by the operation of selecting and excluding nodes. To cover the communication between the Manager and the Agents, the Common Object Request Broker Architecture (CORBA) which is gaining increasing importance in the field of network and systems management, was chosen for the reasons mentioned below. CORBA has no notion of hierarchy but assumes symmetric peer-to-peer relationships between objects; in terms of management, this result in an extension of the role model Manager/Agent relationship.

Accordingly, the distributive model consists of using multiple Agents running in a completely independent way, each with the next candidate node, with the goal of searching the shortest path below the said node. Once an Agent finishes searching, it sends resulting path, until all the paths from all the agents are collected and the entire problem is solved by choosing the optimal possible path. The multiplication of the number of agents directly implies the reduction of the execution time and makes it possible to avoid memories during the selection of possible paths. The Manager uses a dispatcher to distribute the tasks to the Agents and a collector to collect the results sent by them.

CORBA was chosen for communication between all the actors of this architecture (figure 5). The use of CORBA offers advanced programming mechanisms such as distributed event management, support for asynchronous communication AMI (Asynchronous Method Invocation) and object-oriented programming. The services offered by the Manager and the Agents are listed below:
If *d* reaches the maximum value which is the distance from the farthest vertex to the virtual path, the algorithm behaves just like any other MMTDSP (multimodal time-dependent shortest path) algorithm depending on MMTDSP function and all the graph vertices will be captured in the search space. On the other hand, when *d* is less then *d*<sub>max</sub>, then the algorithm will navigate back and forth relying on the density of the network. It starts from a restricted search space and enlarges it by Δ*d* until a shortest path is found, while each vertex not leading to a complete path is removed from the possible partial paths.

<figure><img src="image_4.png" /><figcaption>Figure 4. Calculation of threshold</figcaption></figure>

<caption>Figure 3. The algorithm process</caption>

4. Distributed architecture

We study the possibility of improving the performance of the CSPA by examining the distribution and parallelism of the algorithm, more precisely the algorithm searching process. It generates multiple instances that run through the network to find the candidate paths.

The choice was made on the Manager / Agent model since it guarantees scalability and distribution services and this coincides well with our objective. The task of finding the final right path passes through constructing the right set of nodes by the operation of selecting and excluding nodes. To cover the communication between the Manager and the Agents, the Common Object Request Broker Architecture (CORBA) which is gaining increasing importance in the field of network and systems management, was chosen for the reasons mentioned below. CORBA has no notion of hierarchy but assumes symmetric peer-to-peer relationships between objects; in terms of management, this result in an extension of the role model Manager/Agent relationship.

Accordingly, the distributive model consists of using multiple Agents running in a completely independent way, each with the next candidate node, with the goal of searching the shortest path below the said node. Once an Agent finishes searching, it sends resulting path, until all the paths from all the agents are collected and the entire problem is solved by choosing the optimal possible path. The multiplication of the number of agents directly implies the reduction of the execution time and makes it possible to avoid memories during the selection of possible paths. The Manager uses a dispatcher to distribute the tasks to the Agents and a collector to collect the results sent by them.

CORBA was chosen for communication between all the actors of this architecture (figure 5). The use of CORBA offers advanced programming mechanisms such as distributed event management, support for asynchronous communication AMI (Asynchronous Method Invocation) and object-oriented programming. The services offered by the Manager and the Agents are listed below:
* Manager: Network management, distribution of tasks, generation and synchronization of agents, collection of paths and treatment.

* Agent: Generation of set of nodes and returned elementary path processing.

<figure><img src="image_6.png" /><figcaption>Figure 5. Distributed Manager/Agent architecture</figcaption></figure>

**5. Experimental results**

In this section, an implementation of the CSPA, with cost function defined as the travel time, is evaluated below. Also, several tests are done in order to analyze the impact of the parameter values and the used architecture on computing time. The performance of the algorithm on different instances of the problem in monolithic architecture is compared with its performance in distributed architecture.

<figure><img src="image_7.png" /><figcaption>Figure 6. Comparison of A* and CSPA in monolithic and distributed architecture</figcaption></figure>

The CSPA algorithm in the implemented prototype is a variant of A* algorithm in a way that the algorithm uses A* for the elementary step function *OneStepMMTDSP*. Therefore, different instances of CSPA are compared in the first place with A* to point out the notable reduction of computational time (figure 6). The comparison shows how our approach applied to A* can reduce the CPU time efficiently in comparison with A*. We try to give three
* Manager: Network management, distribution of tasks, generation and synchronization of agents, collection of paths and treatment.

* Agent: Generation of set of nodes and returned elementary path processing.

<figure><img src="image_5.png" /><figcaption>Figure 5. Distributed Manager/Agent architecture</figcaption></figure>

## 5. Experimental results

In this section, an implementation of the CSPA, with cost function defined as the travel time, is evaluated below. Also, several tests are done in order to analyze the impact of the parameter values and the used architecture on computing time. The performance of the algorithm on different instances of the problem in monolithic architecture is compared with its performance in distributed architecture.

<figure><img src="image_6.png" /><figcaption>Figure 6. Comparison of A* and CSPA in monolithic and distributed architecture</figcaption></figure>

The CSPA algorithm in the implemented prototype is a variant of A* algorithm in a way that the algorithm uses A* for the elementary step function *OneStepMMTDSP*. Therefore, different instances of CSPA are compared in the first place with A* to point out the notable reduction of computational time (figure 6). The comparison shows how our approach applied to A* can reduce the CPU time efficiently in comparison with A*. We try to give three
different values to the parameter *d* for the two architectures (monolithic: case1/distributed: case2) and calculate the corresponding execution time. The performance of the algorithm is more significant in *d*3 in both cases which includes the importance of the choice of the calculation method for the upper bound that conducts the search process. The impact of the distribution is shown in the figure 6 if we compare CSPA for monolithic architecture and CSPA' for distributed architecture. The gap between the different values is noticeable.

Table 2 shows the performance of the proposed approach in monolithic and distributed architecture. The results in this table are given in terms of computation time and space. These values were calculated on multiple independent runs for four instances of the SPP, with different number of vertices, edges, and transport modes.

According to the CPU time, the proposed approach provides the best result for almost all instances in distributed architecture especially for big instances.

We can conclude here that the distributed CSPA' presents an optimal solution for reducing the search space and reducing the computation time.

<table><caption>Table 2. CPU time comparison between the performance of CSPA in monolithic and distributed architecture</caption><thead><tr><th colspan="3">Graph instance</th><th colspan="2">CPU Time (x10<sup>-2</sup>ms)</th></tr><tr><th>|V|</th><th>|E|</th><th>|M|</th><th>Monolithic arch.</th><th>Distributed arch.</th></tr></thead><tbody><tr><td>100</td><td>230</td><td>3</td><td>0.8</td><td>0.77</td></tr><tr><td>500</td><td>800</td><td>3</td><td>1.66</td><td>1.62</td></tr><tr><td>1000</td><td>2600</td><td>3</td><td>2.85</td><td>1.5</td></tr><tr><td>2000</td><td>5000</td><td>3</td><td>3.01</td><td>1.86</td></tr></tbody></table>

## 6. Conclusion

In this paper, we give an overview of the modeling of solving time-dependent route planning in multimodal transportation networks. Our added value to this routing problem is proposing an approach to find the shortest path with optimal searching process which is designed to handle the time-dependent shortest path algorithm problematic for multimodal transportation network. It is implemented in a parallel distributed architecture using CORBA for Manager/Agent model. Computational results indicated that the actual performance of the proposed distributed algorithm is substantially better than A* algorithm in time-dependent multimodal network. In the future, the evaluation of our proposed algorithm will be done by comparing the performance of CSPA with other algorithms such as ALT with more variation of modes.

## Acknowledgment

This work was partially funded by the CNRST project in the priority areas of scientific research and technological development “Spatio-temporal data warehouse and strategic transport of dangerous goods”.

## References

Ayed, H., & Khadraoui, D., 2008. “Transfer graph approach for multimodal transport problems”. Second International Conference MCO, Metz, France – Luxembourg.

Bakalov, P., Hoel, E., & Heng, W. L. 2015. Time dependent transportation network models. In Data Engineering (ICDE), 2015 IEEE 31st International Conference on (pp. 1364-1375). IEEE.

Bast, H. et al., 2009. “Route planning in transportation networks.” Technical Report MSR-TR-2014-4. Microsoft Research, Microsoft Co.

Bielli, M., Boulmakoul, A., and Mounrif, H., 2006. “Object modeling and path computation for multimodal travel systems”. European Journal of Operational Research pp. 175, 1705–1730.

Cooke, K. & Halsey, E., 1966. “The Shortest Route through a Network with Time-Dependent Intermodal Transit Times”. Journal of Mathematical Analysis and Applications, (14):493–498.

Idri, A., Oukarfi, M., Boulmakoul, A., Zeitouni, K. & Masri, A., 2017. “A new time-dependent shortest path algorithm for multimodal transportation network”. Procedia Computer Science. volume 109, 2017, Pages 692–697.

Liu, L. & Meng, L., 2009. “Algorithms of multi-modal route planning based on the concept of switch point”. 6th International Symposium on LBS & TeleCartography, Nottingham, UK.

Lozano, A. & Storchi, G., 2002. “Shortest viable hyperpath in multimodal networks”. Transportation Research Part B, 36, 853–874.

Pajor, T., 2009. “Multi-modal route planning”. Master thesis of Karlsruhe Institute of Technology.
different values to the parameter *d* for the two architectures (monolithic: case1/distributed: case2) and calculate the corresponding execution time. The performance of the algorithm is more significant in *d*3 in both cases which includes the importance of the choice of the calculation method for the upper bound that conducts the search process. The impact of the distribution is shown in the figure 6 if we compare CSPA for monolithic architecture and CSPA' for distributed architecture. The gap between the different values is noticeable.

Table 2 shows the performance of the proposed approach in monolithic and distributed architecture. The results in this table are given in terms of computation time and space. These values were calculated on multiple independent runs for four instances of the SPP, with different number of vertices, edges, and transport modes.

According to the CPU time, the proposed approach provides the best result for almost all instances in distributed architecture especially for big instances.

We can conclude here that the distributed CSPA' presents an optimal solution for reducing the search space and reducing the computation time.

<table><caption>Table 2. CPU time comparison between the performance of CSPA in monolithic and distributed architecture</caption><thead><tr><th colspan="3">Graph instance</th><th colspan="2">CPU Time (x10<sup>-2</sup>ms)</th></tr><tr><th>|V|</th><th>|E|</th><th>|M|</th><th>Monolithic arch.</th><th>Distributed arch.</th></tr></thead><tbody><tr><td>100</td><td>230</td><td>3</td><td>0.8</td><td>0.77</td></tr><tr><td>500</td><td>800</td><td>3</td><td>1.66</td><td>1.62</td></tr><tr><td>1000</td><td>2600</td><td>3</td><td>2.85</td><td>1.5</td></tr><tr><td>2000</td><td>5000</td><td>3</td><td>3.01</td><td>1.86</td></tr></tbody></table>

## 6. Conclusion

In this paper, we give an overview of the modeling of solving time-dependent route planning in multimodal transportation networks. Our added value to this routing problem is proposing an approach to find the shortest path with optimal searching process which is designed to handle the time-dependent shortest path algorithm problematic for multimodal transportation network. It is implemented in a parallel distributed architecture using CORBA for Manager/Agent model. Computational results indicated that the actual performance of the proposed distributed algorithm is substantially better than A* algorithm in time-dependent multimodal network. In the future, the evaluation of our proposed algorithm will be done by comparing the performance of CSPA with other algorithms such as ALT with more variation of modes.

## Acknowledgment

This work was partially funded by the CNRST project in the priority areas of scientific research and technological development "Spatio-temporal data warehouse and strategic transport of dangerous goods".

## References

Ayed, H., & Khadraoui, D., 2008. "Transfer graph approach for multimodal transport problems". Second International Conference MCO, Metz, France - Luxembourg.

Bakalov, P., Hoel, E., & Heng, W. L. 2015. Time dependent transportation network models. In Data Engineering (ICDE), 2015 IEEE 31st International Conference on (pp. 1364-1375). IEEE.

Bast, H. et al., 2009. "Route planning in transportation networks." Technical Report MSR-TR-2014-4. Microsoft Research, Microsoft Co.

Bielli, M., Boulmakoul, A., and Mounrif, H., 2006. "Object modeling and path computation for multimodal travel systems". European Journal of Operational Research pp. 175, 1705-1730.

Cooke, K. & Halsey, E., 1966. "The Shortest Route through a Network with Time-Dependent Intermodal Transit Times". Journal of Mathematical Analysis and Applications, (14):493-498.

Idri, A., Oukarfi, M., Boulmakoul, A., Zeitouni, K. & Masri, A., 2017. "A new time-dependent shortest path algorithm for multimodal transportation network". Procedia Computer Science. volume 109, 2017, Pages 692-697.

Liu, L. & Meng, L., 2009. "Algorithms of multi-modal route planning based on the concept of switch point". 6th International Symposium on LBS & TeleCartography, Nottingham, UK.

Lozano, A. & Storchi, G., 2002. "Shortest viable hyperpath in multimodal networks". Transportation Research Part B, 36, 853-874.

Pajor, T., 2009. "Multi-modal route planning". Master thesis of Karlsruhe Institute of Technology.
Peng, Z. R. & Kim, E., 2008. "A standard-based integration framework of distributed transit trip planning systems". Journal of the Intelligent Transportation Systems, 12(1), pp. 13-19.

Pyrga, E., Schulz, F., Wagner, D., & Zaroliagis, C. 2008. "Efficient models for timetable information in public transportation systems". Journal of Experimental Algorithmics (JEA), 12, 2-4.

Schultes, D., 2008. "Route planning in road networks". Ph.D Thesis of Karlsruhe Institute of Technology.

Zhang, L., Yang, H., Wu, D., & Wang, D. 2014. "Solving a discrete multimodal transportation network design problem". Transportation Research Part C: Emerging Technologies, 49, 73-86.

Ziliaskopoulos, A., & Wardell, W. 2000. "An intermodal optimum path algorithm for multimodal networks with dynamic arc travel times and switching delays". European Journal of Operational Research, 125(3), 486-502.
Peng, Z. R. & Kim, E., 2008. "A standard-based integration framework of distributed transit trip planning systems". Journal of the Intelligent Transportation Systems, 12(1), pp. 13-19.

Pyrga, E., Schulz, F., Wagner, D., & Zaroliagis, C. 2008. "Efficient models for timetable information in public transportation systems". Journal of Experimental Algorithmics (JEA), 12, 2-4.

Schultes, D., 2008. "Route planning in road networks". Ph.D Thesis of Karlsruhe Institute of Technology.

Zhang, L., Yang, H., Wu, D., & Wang, D. 2014. "Solving a discrete multimodal transportation network design problem". Transportation Research Part C: Emerging Technologies, 49, 73-86.

Ziliaskopoulos, A., & Wardell, W. 2000. "An intermodal optimum path algorithm for multimodal networks with dynamic arc travel times and switching delays". European Journal of Operational Research, 125(3), 486-502.