# Distributed Approach for Solving Time-Dependent Problems in Multimodal Transport Networks

Authors: Carlos Galvez-Fernandez; Djamel Khadraoui; Hedi Ayed; Zineb Habbas; Enrique Alba
Journal: Advances in Operations Research
 (2009)

---

## Abstract

This paper presents an alternative approach for time-dependent multimodal transport problem. We describe a new graph structure to abstract multimodal networks, calledtransfer graph, which adapts to the distributed nature of real information sources of transportation networks. A decomposition of the Shortest Path Problem in transfer graph is proposed to optimize the computation time. This approach was computationally tested in several experimental multimodal networks having different size and complexity. The approach was integrated in the multimodal transport service of the European Carlink platform, where it has been validated in real scenarios. Comparision with other related works is provided.


---

## Body

## 1. Introduction

Multimodal transport is the combination of two or more means of transport to move passengers or goods from one source to a destination [1]. The traveller can use either public (e.g., bus, taxi, metro, railway, and ship) or private vehicles (e.g., car, motorbike, bicycle, and walking). Multimodal journeys are becoming a real necessity in our society in order to guarantee a high level of mobility both inside cities and at the regional level [2].From the last decades, many research projects were devoted to develop multimodal transport systems that recommend travellers a combination of transport means for door-to-door journeys [1, 3–5]. These systems must cope with different transport information sources, which are normally distributed in real scenarios, that is, transport data are usually provided by different public and private companies and can be stored in different locations. Another challenge for these systems is to integrate real-time traffic information (e.g., traffic jams, delays, roadworks) in order to adapt proposed routes to real conditions.Different abstractions have been proposed to represent the time-dependent multimodal transport problem. Three main categories of approaches can be identified: the multigraph-based approach [2, 6, 7], the constraint satisfaction problem approach [8], and the grid-based approach [9]. In order to adapt multimodal transport abstraction to the distributed nature of real-world information, the following constrains should be fulfilled: (i) the underlying multimodal network is assumed to be flat and to contain no hierarchical structure, like regional hierarchy; (ii) the involved unimodal networks may be distributed, that is, unimodal networks are stored and accessed separately; (iii) if there are multiple network information sources within a single mode, they may be distributed. The above-mentioned approaches relax any of these constraints when modeling and solving the problem.An alternative representation of the time-dependent multimodal transport problem was partially described in [10]. Here we present a formal description of this abstraction as well as the transfer graph approach, which calculates the best paths in this structure. This approach was tested and also validated in the real context of Carlink Platform (Carlink, Wireless Platform for Linking Cars, is a project of the Celtic Cluster Programme Call, which aims to develop an intelligent wireless traffic service platform between cars) [11]. Transfer graph approach provides a solution for the time-dependent multimodal transport problem which fulfills the three defined constraints and adapts to the distributed nature of real transport information providers.The outline of this article is the following. Section2 describes the transfer graph approach for the time-dependent multimodal transport problem. In Section 3 this approach is computationally tested. Section 4 describes Carlink, the real scenario where the approach is validated, mainly the service platform as well as the obtained results. In Section 5 the results are compared with other related works. Finally, this paper ends with some conclusions in Section 6.


## 2. Transfer Graph Approach for Multimodal Transport Problems

In real scenarios, transport information sources are normally distributed, that is, transport schedules are usually provided by different public and private companies. Besides, this information is frequently modified due to daily unexpected perturbations such as traffic jams, delays, and roadworks. These restrictions complicate the management of transport information and the updates of transport networks.This section presents the transfer graph approach for solving the Shortest Path Problem (SPP) in discrete time-dependent multimodal network. It is able to compute multimodal routes even if all involved networks are kept structurally separated and distributed. Instead of building a solution limited to the unified view of multimodal transport system, our strategy consists in finding a fundamental network representation which covers multimodal networks and then solves the SPP on this abstraction.The transfer graph approach adapts to the distributed nature of real world transport information sources and allows updates on each transport network independently without requiring any further modification. Our approach is mainly divided into two steps. In the first step, relevant paths are computed within each unimodal network. In the second step, the graph is reduced to a simple time-dependent unimodal network, where the classical SPP can be solved.The next subsections first introduce the basic concepts of graphs and a definition of SPP in time-dependent multimodal networks. Then, thetransfer graph abstraction is formally described, followed by the presentation of the relevant graph, a simplified structure calculated from transfer graph. Finally, the transfer graph approach to calculate SPP in transfer graph is discussed.


### 2.1. SPP in Discrete Time-Dependent Multimodal Networks

LetG=(N,M,A) denote a directed graph or network, in which N={n1,…,nj} is a set of nodes, M={m1,m2,…,mk} is a set of transport modes (e.g., train, bus, and car), and A={a1,…,al}⊆N×N×M is a set of arcs. An arc ai∈A can be identified by (ni,ni′,mi) or (ni,ni′)i, where ni,ni′∈N⋀mi∈M. The ai means the possibility of going from node ni to ni′ by using transport mode mi. A value cai is associated to each arc ai, indicating the cost of including the arc in the solution (e.g., distance, time).Definition 2.1.
A graphG=(N,M,A) is said to be multimodal if there is at least two transport modes mi,mj∈M where (ni,ni′,mi),(nj,nj′,mj)∈A, mi≠mj, and ni,ni′,nj,nj′∈N. If there is only one transport mode in the graph, the graph is said to be unimodal.In a graphG=(N,M,A) a path or route p is a sequence of arcs between a pair of nodes n1 and nk+1, ((n1,n2,m1),(n2,n3,m2),…,(nk,nk+1,mk)), nj∈N for all j=1,…,k+1, and (ni,ni+1,mi)∈A, mi∈M for all i=1,…,k.Definition 2.2.
Given a graphG=(N,M,A), a path p=(a1,a2,…,al) is said to be multimodal if ∃ai,aj∈A, ai=(ni,ni′,mi),aj=(nj,nj′,mj),mi≠mj,i≠j, and i,j≤l. If there is only one mode involved in the path, then the path is said to be unimodal.LetP be the set of paths in a graph G and f:P→R a function which represents the cost of a path. An SPP is considered to be multiobjective if f maps to a vector of dimension k≥2, f:P→Rk. Each component fi∈f, for all (1≤i≤k), follows the definition of single objective path cost function.Lett denote time in a discrete set {t1,t2,…,tl}. Unlike nontime-dependent networks where arc costs are fixed, in time-dependent networks the cost of an arc ai=(ni,ni′,mi) varies according to cost function cai(tk) for all tk∈{t1,…,tl}.Definition 2.3.
Given a graphG=(N,M,A) and a discrete time set {t1,…,tl}, a travel for the arc ai=(ni,ni′,mi)∈A is defined as tuple (t,t′)∈Tr,  t,t′∈{t1,…,tl}, where t is the departure time from node ni, and t′ is the arrival time at node ni′. Tr denotes the set of travels in G.Definition 2.4.
Given a graphG=(N,M,A,Tr) and a discrete time set {t1,…,tl}, G is said to be a time-dependent network if for all ai∈A, Tai={(t1,t1′),…,(tk,tk′)}⊆Tr where |Tai|≥1 and for all j=1,…,k, tj,tj′∈{t1,…,tl} and tj≤tj′.We conclude this subsection by formulating the SPP in time-dependent multimodal graphs. The reader can find a wider description of the SPP in [12].Definition 2.5.
Given a time-dependent multimodal graphG=(N,M,A,Tr), two nodes s,d∈N, and time t∈{t1,t2,…,tl}, the SPP is defined as follows: calculate a path p from node s to d that departures from s at time t and f(p) is minimal.


### 2.2. Transfer Graph

In this subsection, we present thetransfer graph, a graphical structure that abstracts the time-dependent multimodal transport network.Atransfer graph is described by a set of unimodal networks and a set of arcs connecting them, and it is defined by T=(N,A,C,Tr). Let s,d∈N be an origin-destination pair and C={C1,C2,…,Cm} a set of unimodal networks called components, where each Cg=(Ng,Ag), Ng⊆N and Ag⊆A. C itself is such that N=⋃∀gNg and A=⋃∀gAg, for all g=1,…,m,  Cg=(Ng,Ag)⋀Cg∈C. Unlike partitioned graph, given two distinct components Cg and Cg′, having Ng⋂Ng′=∅ is not mandatory; however Ag⋂Ag′=∅ must always hold. Again, let us define two distinct components Cg,Cg′∈C; a node n is said to be a transfer point when n∈Ng⋂Ng′, that is, any node which belongs to more than one component. Finally, a transfer is any arc which connects two components of the transfer graph: (ni,nj), ni∈Ng⋀nj∈Ng′⋀ni=nj⋀g≠g′.Figure1 illustrates an example of this abstraction, where C1, C2, and C3 are components connected by three transfers, and nodes a, b, and c are transfer points. One can observe that source node s and target node d may belong to more than one component; this is because they can be transfer points. Actually, time-dependence and multiobjectivity are not considered in this example, although the approach is able to work with these restrictions.Figure 1
Transfer graph illustrative case.Transfer graph abstraction separates all transport modes in unimodal networks. So, when a perturbation (e.g., traffic jam, roadworks) is detected for a transport mode, it does not affect globally to the representation, but locally. In those cases, it is only necessary to update those components related to the incident. According to this characteristic we can state Lemma 2.6.Lemma 2.6.
Transfer graph abstraction is more robust against modification of transport network data than classical multimodal network representation.


### 2.3. Relevant Graph

In the previous subsection we have formally defined thetransfer graph. We present now a simplified structure derived from this abstraction, called relevant graph, from which the Shortest Path Problem can be easier computed.At a high level, paths in atransfer graph can be divided into two groups: intracomponents paths and intercomponent paths. An intercomponent path within a transfer graphT is considered as any sequence of arcs which connects two nodes ni,nj∈N where at least there are two arcs belonging to two distinct components. On the other hand, an intracomponent path within Cg is any sequence of arcs which connects two nodes ni,nj∈Ng whose arcs belong only to one component. Intra component paths can be divided into the following categories:(i)
full paths (Ps·d*g): the smallest route which starts at source node s and ends at target node d within the component Cg;(ii)
relevant head paths (Ps·-*g): the smallest routes which start at source s and end at a transfer point within the component Cg;(iii)
relevant intermediate paths (P+·-*g): the smallest routes which start and end at any transfer point within the component Cg;(iv)
relevant tail paths (P+·d*g): the smallest routes which start at any transfer point and end at target d within the component Cg.Given atransfer graphT=(N,A,C,Tr) and an origin-destination pair s,d∈N, assume that for all components Cg∈C we have computed the best relevant path sets: Ps·d*g, Ps·-*g, P+·-*g, and P+·d*g (see Table 1). Having these relevant path sets in hand, it is possible to derive a reduced graph from which all possible best inter component paths from s to d can be computed. We call this graph the relevant graph and use R to denote it. The nodes of R are s, d and a subset of all transfer points in the transfer graph. The arc set of R is the best relevant intra component paths viewed as edges, that is, paths that are represented only by the initial and final nodes. In fact, R is a multigraph, but in general, its scale should be much smaller than the equivalent multigraph of the underlying transfer graph. This is because any node appearing in R is a transfer point, except the origin and destination nodes. So, the number of nodes in R depends directly on the number of transfer points in the whole transfer graph. Figure 2 shows the relevant graph computed out of Figure 1.Table 1
Best intracomponent paths calculated for thetransfer graph in Figure 1.
Comp.C1CostComp.C2CostComp.C3CostPs·d*g{(s,a)1,(a,b)1,(b,d)1}4——{(s,c)3,(c,e)3,(e,d)3}9Ps·-*g{(s,a)1,(a,b)1}2——{(s,a)3}5{(s,a)1}1——{(s,c)3}1P+·-*g{(a,b)1}1{(b,c)2}2——P+·d*g{(a,b)1,(b,d)1}3{(b,c)2,(c,d)2}3{(a,e)3,(e,d)3}9{(b,d)1}2{(c,d)2}1{(c,e)3,(e,d)3}8Figure 2
Relevant graph calculated for the transfer graph in Figure1.In order to formally describeR, let Vg denote the set of relevant nodes for component Cg, and let Eg be the set of relevant paths computed for Cg. From all Vg and Eg we can, respectively, build V=(⋃∀gVg)⋃{s,d} for all Cg∈C the set of relevant nodes for all component, and E=⋃∀gEg for all Cg∈C the set of relevant paths for all component Cg∈C. The relevant graph is formally described by the pair R=(V,E). If we consider time-dependent networks with different discrete time ti={t1,t2,…,tl}, then in order to build the relevant graph, it is necessary to calculate the best relevant paths at any departure time ti, that is, Ps·d*g(ti), Ps·+*g(ti), P-·d*g(ti), P-·+*g(ti), for all Cg∈C and for all ti={t1,t2,…,tl}.When arelevant graph is built from a transfer graph for nodes s and d and time t, we have a time-dependent unimodal multigraph with a reduced number of nodes where all the shortest paths between transfer points, s and d, are calculated. The computation of the shortest path from s to d in R is basically the classical origin-destination SPP on a reduced time-dependent unimodal network. This allows us to establish the following lemma.Lemma 2.7.
LetT=(N,A,C,Tr) be a transfer graph and R=(V,E) its associated relevant graph, then R is a less complex structure than T in terms of the shortest path computational time.


### 2.4. Transfer Graph Approach

Once thetransfer graph and the relevant graph are formally defined, we present the decomposition of the SPP in these abstractions as well as the transfer graph approach.Every time a request is fulfilled for obtaining the shortest path from a sources and a destination d at departure time t, we need to calculate the best relevant paths for Ps·d*g(t), Ps·-*g(t), and P+·d*g(ti) for all Cg∈C, for all ti={t1,…,tl}. However, P+·-*g(ti) for all ti={t1,…,tl} is calculated once, since it does not depend on s and d. Taking advantage of this feature we can decompose the SPP in transfer graphs as follows.(1)
The best paths forP+·-*g(ti), for all Cg∈C, for all ti={t1,…,tl} are calculated and stored. This is called precalculations.(2)
When a request is fulfilled for two specific nodess and d, and time t, then Ps·d*g(t), Ps·-*g(t), and P+·d*g(ti) for all ti={t1,…,tl} can be calculated.(3)
Finally, therelevant graphR is constructed and the shortest path is computed.This decomposition reduces time complexity of the problem considerably becauseprecalculations compute the most difficult set of paths in terms of computation time. Precalculations provide an important advantage if multiple and frequent requests are fulfilled (e.g., in a real web service). On the contrary, precalculation must be partly recomputed when a perturbation is detected. Table 2 shows an example of recalculating the relevant graph for Figure 1 if the cost of the arc between nodes b and c for component C2 increases from two to four. As it can be seen, only few paths are necessary to be recalculated, instead of considering all transport network. This is specially efficient for transfer graphs with multiple components.Table 2
Best intra component paths recalculated for graph in Figure1 if the cost of arc (b,c)2 of C2 increases from two to four. Recalculated paths are shown in bold.
Comp.C1CostComp.C2CostComp.C3CostPs·d*g{(s,a)1,(a,b)1,(b,d)1}4——{(s,c)3,(c,e)3,(e,d)3}9Ps·-*g{(s,a)1,(a,b)1}2——{(s,a)3}5{(s,a)1}1——{(s,c)3}1P+·-*g{(a,b)1}1{(b,c)2}4——P+·d*g{(a,b)1,(b,d)1}3{(b,d)2}4{(a,e)3,(e,d)3}9{(b,d)1}2{(c,d)2}1{(c,e)3,(e,d)3}8Finally, we present the transfer graph approach in Algorithm1. The procedure Compute calculates the shortest path for a specific component and departure time. This step can be calculated independently for each component, due to the characteristics of transfer graph and the decomposition of the SPP in this abstraction. The procedure StoreDataBase saves in the data base DB the previous calculated set of the shortest paths. The procedure Compute is called three times to calculate all the specific sets of shortest paths when the user request is submitted. RelevantGraph is the procedure reducing the initial graph to a more compact structure corresponding to a given user request. Finally, the procedure ShortestPath gives the smallest route requested by the user. Obviously all these procedures can be implemented in different ways and giving rise to different complexities. Here, we show the feasibility of our approach by using a variant of Dijsktra's algorithm. Therefore, the transfer graph approach can be applied to scenarios with distributed transport information sources.Algorithm 1:Transfer graph approach.
Input: Transfer graph T with m modes and n possible departure timesforg=1 to m  dofor  i=1 to n  doP+-←Compute(P+·-*g(ti),T)StoreDataBase(P+-,DB)end  forend  forwhile  Request(s,d,t)  dofor  g=1 to m  doPsd[g]←Compute(Ps·d*g(t),T)Ps-[g]←Compute(Ps·-*g(t),T)for  i=1 to n  doP+d[g]←Compute(P+·d*g(ti),T)end  forend  forR←RelevantGraph(Psd,Ps-,P+d,DB)ShortestPath(R,s,d,t)end  while


## 2.1. SPP in Discrete Time-Dependent Multimodal Networks

LetG=(N,M,A) denote a directed graph or network, in which N={n1,…,nj} is a set of nodes, M={m1,m2,…,mk} is a set of transport modes (e.g., train, bus, and car), and A={a1,…,al}⊆N×N×M is a set of arcs. An arc ai∈A can be identified by (ni,ni′,mi) or (ni,ni′)i, where ni,ni′∈N⋀mi∈M. The ai means the possibility of going from node ni to ni′ by using transport mode mi. A value cai is associated to each arc ai, indicating the cost of including the arc in the solution (e.g., distance, time).Definition 2.1.
A graphG=(N,M,A) is said to be multimodal if there is at least two transport modes mi,mj∈M where (ni,ni′,mi),(nj,nj′,mj)∈A, mi≠mj, and ni,ni′,nj,nj′∈N. If there is only one transport mode in the graph, the graph is said to be unimodal.In a graphG=(N,M,A) a path or route p is a sequence of arcs between a pair of nodes n1 and nk+1, ((n1,n2,m1),(n2,n3,m2),…,(nk,nk+1,mk)), nj∈N for all j=1,…,k+1, and (ni,ni+1,mi)∈A, mi∈M for all i=1,…,k.Definition 2.2.
Given a graphG=(N,M,A), a path p=(a1,a2,…,al) is said to be multimodal if ∃ai,aj∈A, ai=(ni,ni′,mi),aj=(nj,nj′,mj),mi≠mj,i≠j, and i,j≤l. If there is only one mode involved in the path, then the path is said to be unimodal.LetP be the set of paths in a graph G and f:P→R a function which represents the cost of a path. An SPP is considered to be multiobjective if f maps to a vector of dimension k≥2, f:P→Rk. Each component fi∈f, for all (1≤i≤k), follows the definition of single objective path cost function.Lett denote time in a discrete set {t1,t2,…,tl}. Unlike nontime-dependent networks where arc costs are fixed, in time-dependent networks the cost of an arc ai=(ni,ni′,mi) varies according to cost function cai(tk) for all tk∈{t1,…,tl}.Definition 2.3.
Given a graphG=(N,M,A) and a discrete time set {t1,…,tl}, a travel for the arc ai=(ni,ni′,mi)∈A is defined as tuple (t,t′)∈Tr,  t,t′∈{t1,…,tl}, where t is the departure time from node ni, and t′ is the arrival time at node ni′. Tr denotes the set of travels in G.Definition 2.4.
Given a graphG=(N,M,A,Tr) and a discrete time set {t1,…,tl}, G is said to be a time-dependent network if for all ai∈A, Tai={(t1,t1′),…,(tk,tk′)}⊆Tr where |Tai|≥1 and for all j=1,…,k, tj,tj′∈{t1,…,tl} and tj≤tj′.We conclude this subsection by formulating the SPP in time-dependent multimodal graphs. The reader can find a wider description of the SPP in [12].Definition 2.5.
Given a time-dependent multimodal graphG=(N,M,A,Tr), two nodes s,d∈N, and time t∈{t1,t2,…,tl}, the SPP is defined as follows: calculate a path p from node s to d that departures from s at time t and f(p) is minimal.


## 2.2. Transfer Graph

In this subsection, we present thetransfer graph, a graphical structure that abstracts the time-dependent multimodal transport network.Atransfer graph is described by a set of unimodal networks and a set of arcs connecting them, and it is defined by T=(N,A,C,Tr). Let s,d∈N be an origin-destination pair and C={C1,C2,…,Cm} a set of unimodal networks called components, where each Cg=(Ng,Ag), Ng⊆N and Ag⊆A. C itself is such that N=⋃∀gNg and A=⋃∀gAg, for all g=1,…,m,  Cg=(Ng,Ag)⋀Cg∈C. Unlike partitioned graph, given two distinct components Cg and Cg′, having Ng⋂Ng′=∅ is not mandatory; however Ag⋂Ag′=∅ must always hold. Again, let us define two distinct components Cg,Cg′∈C; a node n is said to be a transfer point when n∈Ng⋂Ng′, that is, any node which belongs to more than one component. Finally, a transfer is any arc which connects two components of the transfer graph: (ni,nj), ni∈Ng⋀nj∈Ng′⋀ni=nj⋀g≠g′.Figure1 illustrates an example of this abstraction, where C1, C2, and C3 are components connected by three transfers, and nodes a, b, and c are transfer points. One can observe that source node s and target node d may belong to more than one component; this is because they can be transfer points. Actually, time-dependence and multiobjectivity are not considered in this example, although the approach is able to work with these restrictions.Figure 1
Transfer graph illustrative case.Transfer graph abstraction separates all transport modes in unimodal networks. So, when a perturbation (e.g., traffic jam, roadworks) is detected for a transport mode, it does not affect globally to the representation, but locally. In those cases, it is only necessary to update those components related to the incident. According to this characteristic we can state Lemma 2.6.Lemma 2.6.
Transfer graph abstraction is more robust against modification of transport network data than classical multimodal network representation.


## 2.3. Relevant Graph

In the previous subsection we have formally defined thetransfer graph. We present now a simplified structure derived from this abstraction, called relevant graph, from which the Shortest Path Problem can be easier computed.At a high level, paths in atransfer graph can be divided into two groups: intracomponents paths and intercomponent paths. An intercomponent path within a transfer graphT is considered as any sequence of arcs which connects two nodes ni,nj∈N where at least there are two arcs belonging to two distinct components. On the other hand, an intracomponent path within Cg is any sequence of arcs which connects two nodes ni,nj∈Ng whose arcs belong only to one component. Intra component paths can be divided into the following categories:(i)
full paths (Ps·d*g): the smallest route which starts at source node s and ends at target node d within the component Cg;(ii)
relevant head paths (Ps·-*g): the smallest routes which start at source s and end at a transfer point within the component Cg;(iii)
relevant intermediate paths (P+·-*g): the smallest routes which start and end at any transfer point within the component Cg;(iv)
relevant tail paths (P+·d*g): the smallest routes which start at any transfer point and end at target d within the component Cg.Given atransfer graphT=(N,A,C,Tr) and an origin-destination pair s,d∈N, assume that for all components Cg∈C we have computed the best relevant path sets: Ps·d*g, Ps·-*g, P+·-*g, and P+·d*g (see Table 1). Having these relevant path sets in hand, it is possible to derive a reduced graph from which all possible best inter component paths from s to d can be computed. We call this graph the relevant graph and use R to denote it. The nodes of R are s, d and a subset of all transfer points in the transfer graph. The arc set of R is the best relevant intra component paths viewed as edges, that is, paths that are represented only by the initial and final nodes. In fact, R is a multigraph, but in general, its scale should be much smaller than the equivalent multigraph of the underlying transfer graph. This is because any node appearing in R is a transfer point, except the origin and destination nodes. So, the number of nodes in R depends directly on the number of transfer points in the whole transfer graph. Figure 2 shows the relevant graph computed out of Figure 1.Table 1
Best intracomponent paths calculated for thetransfer graph in Figure 1.
Comp.C1CostComp.C2CostComp.C3CostPs·d*g{(s,a)1,(a,b)1,(b,d)1}4——{(s,c)3,(c,e)3,(e,d)3}9Ps·-*g{(s,a)1,(a,b)1}2——{(s,a)3}5{(s,a)1}1——{(s,c)3}1P+·-*g{(a,b)1}1{(b,c)2}2——P+·d*g{(a,b)1,(b,d)1}3{(b,c)2,(c,d)2}3{(a,e)3,(e,d)3}9{(b,d)1}2{(c,d)2}1{(c,e)3,(e,d)3}8Figure 2
Relevant graph calculated for the transfer graph in Figure1.In order to formally describeR, let Vg denote the set of relevant nodes for component Cg, and let Eg be the set of relevant paths computed for Cg. From all Vg and Eg we can, respectively, build V=(⋃∀gVg)⋃{s,d} for all Cg∈C the set of relevant nodes for all component, and E=⋃∀gEg for all Cg∈C the set of relevant paths for all component Cg∈C. The relevant graph is formally described by the pair R=(V,E). If we consider time-dependent networks with different discrete time ti={t1,t2,…,tl}, then in order to build the relevant graph, it is necessary to calculate the best relevant paths at any departure time ti, that is, Ps·d*g(ti), Ps·+*g(ti), P-·d*g(ti), P-·+*g(ti), for all Cg∈C and for all ti={t1,t2,…,tl}.When arelevant graph is built from a transfer graph for nodes s and d and time t, we have a time-dependent unimodal multigraph with a reduced number of nodes where all the shortest paths between transfer points, s and d, are calculated. The computation of the shortest path from s to d in R is basically the classical origin-destination SPP on a reduced time-dependent unimodal network. This allows us to establish the following lemma.Lemma 2.7.
LetT=(N,A,C,Tr) be a transfer graph and R=(V,E) its associated relevant graph, then R is a less complex structure than T in terms of the shortest path computational time.


## 2.4. Transfer Graph Approach

Once thetransfer graph and the relevant graph are formally defined, we present the decomposition of the SPP in these abstractions as well as the transfer graph approach.Every time a request is fulfilled for obtaining the shortest path from a sources and a destination d at departure time t, we need to calculate the best relevant paths for Ps·d*g(t), Ps·-*g(t), and P+·d*g(ti) for all Cg∈C, for all ti={t1,…,tl}. However, P+·-*g(ti) for all ti={t1,…,tl} is calculated once, since it does not depend on s and d. Taking advantage of this feature we can decompose the SPP in transfer graphs as follows.(1)
The best paths forP+·-*g(ti), for all Cg∈C, for all ti={t1,…,tl} are calculated and stored. This is called precalculations.(2)
When a request is fulfilled for two specific nodess and d, and time t, then Ps·d*g(t), Ps·-*g(t), and P+·d*g(ti) for all ti={t1,…,tl} can be calculated.(3)
Finally, therelevant graphR is constructed and the shortest path is computed.This decomposition reduces time complexity of the problem considerably becauseprecalculations compute the most difficult set of paths in terms of computation time. Precalculations provide an important advantage if multiple and frequent requests are fulfilled (e.g., in a real web service). On the contrary, precalculation must be partly recomputed when a perturbation is detected. Table 2 shows an example of recalculating the relevant graph for Figure 1 if the cost of the arc between nodes b and c for component C2 increases from two to four. As it can be seen, only few paths are necessary to be recalculated, instead of considering all transport network. This is specially efficient for transfer graphs with multiple components.Table 2
Best intra component paths recalculated for graph in Figure1 if the cost of arc (b,c)2 of C2 increases from two to four. Recalculated paths are shown in bold.
Comp.C1CostComp.C2CostComp.C3CostPs·d*g{(s,a)1,(a,b)1,(b,d)1}4——{(s,c)3,(c,e)3,(e,d)3}9Ps·-*g{(s,a)1,(a,b)1}2——{(s,a)3}5{(s,a)1}1——{(s,c)3}1P+·-*g{(a,b)1}1{(b,c)2}4——P+·d*g{(a,b)1,(b,d)1}3{(b,d)2}4{(a,e)3,(e,d)3}9{(b,d)1}2{(c,d)2}1{(c,e)3,(e,d)3}8Finally, we present the transfer graph approach in Algorithm1. The procedure Compute calculates the shortest path for a specific component and departure time. This step can be calculated independently for each component, due to the characteristics of transfer graph and the decomposition of the SPP in this abstraction. The procedure StoreDataBase saves in the data base DB the previous calculated set of the shortest paths. The procedure Compute is called three times to calculate all the specific sets of shortest paths when the user request is submitted. RelevantGraph is the procedure reducing the initial graph to a more compact structure corresponding to a given user request. Finally, the procedure ShortestPath gives the smallest route requested by the user. Obviously all these procedures can be implemented in different ways and giving rise to different complexities. Here, we show the feasibility of our approach by using a variant of Dijsktra's algorithm. Therefore, the transfer graph approach can be applied to scenarios with distributed transport information sources.Algorithm 1:Transfer graph approach.
Input: Transfer graph T with m modes and n possible departure timesforg=1 to m  dofor  i=1 to n  doP+-←Compute(P+·-*g(ti),T)StoreDataBase(P+-,DB)end  forend  forwhile  Request(s,d,t)  dofor  g=1 to m  doPsd[g]←Compute(Ps·d*g(t),T)Ps-[g]←Compute(Ps·-*g(t),T)for  i=1 to n  doP+d[g]←Compute(P+·d*g(ti),T)end  forend  forR←RelevantGraph(Psd,Ps-,P+d,DB)ShortestPath(R,s,d,t)end  while


## 3. Simulation Results

So far, we have introduced thetransfer graph abstraction and the transfer graph approach. In this section we present a computational test of this approach with several instances of the SPP in time-dependent multimodal networks.We have selected eighteen instances of the SPP with three, four, and five transport modes and increasing number of nodes from 50 to 2000, namedSPP(nodes,modes). A transfer graph is built for each instance with variable number of arcs and transfers, but keeping high number of transfers and 10 possible random travel times per each arc, in order to simulate real scenarios. Table 3 presents for each problem instance a description of the transfer graph, the characteristic of the relevant graph built from the transfer graph, and the computation time. Instances are grouped by number of nodes.Table 3
Performance and graph reduction for different instances of the SPP with variable transport modes, number of nodes and arcs.
Transfer graphRelevant graphCPU timeSPPNodesArcsTransfersTravelsPrecalcula.NodesArcs% NodeAvg.Max.Instance(N,M)time (second)reductionSPP(50,3)502001920000.7215210700.0010.001SPP(100,3)1003003330001.4725570750.0120.108SPP(200,3)2006006260002.13522170740.0250.656SPP(500,3)5001500152150006.3312613214750.0540.342SPP(1000,3)100030003763000026.1130464376700.2481.295SPP(2000,3)2000600085060000102.23652243982671.0533.454SPP(50,4)502002620000.7116202680.0160.176SPP(100,4)1003005030001.4330711700.0130.250SPP(200,4)20060010360002.62603050700.0280.193SPP(500,4)5001500264150006.8715219449700.0710.624SPP(1000,4)100030004933000025.8730770617690.1780.975SPP(2000,4)2000600090460000100.54657247018671.1414.129SPP(50,5)502003520000.6917216660.0100.160SPP(100,5)1003005230001.2633824670.0140.387SPP(200,5)20060013360002.35663434670.0190.278SPP(500,5)5001500314150005.8016419418670.0490.677SPP(1000,5)100030006543000022.1232073765680.1490.774SPP(2000,5)200060009266000099.04662250643671.0053.705A variant of Dijkstra's algorithm [13] is used to implement the function ShortestPath(R,s,d,t) of the transfer graph approach (Algorithm 1), which calculates the shortest path in terms of travel time. In these simulation tests we consider that P+·-*g(ti) for all Cg∈C, for all ti={t1,…,tl} are available, that is, the precalculations are already computed. The computation time of precalculations is presented in Table 3.Thetransfer graph approach was tested in a computer equipped with an Intel Core2 Duo T7300, 2 GHz, and 2 GB RAM. 100 tests have been done for each instance with random nodes and departure time, calculating the average and maximum CPU time for them all (see Table 3).When building therelevant graph from the transfer graph, the number of nodes in all instances is reduced around 70%, although the number of arcs increases considerably (see Table 3). Since the complexity of Dijkstra's algorithm depends on the number of nodes O(N2), this is an appropriate algorithm to calculate the shortest path in a relevant graph.Transfer graph approach has been tested in eighteen instances of the problem, providing a solution in a second approximately in average, even for instances with 2000 nodes and 60.000 travels. Precalculation time increases according to the network size and number of travels. Nevertheless, this precalculations must be done once, and considerably reduced the computation time for requests.Finally, we present the computation cost ofprecalculations on medium-sized networks with different levels of complexity, according to number of travels. Five transfer graphs are built for the instance SPP(200,3) with variable number of travels. Figure 3 shows that the computation cost of precalculation is not considerably affected by the number of travels.Figure 3
Computation time forprecalculation in the instance SPP(200,3) with different numbers of travels.


## 4. Experimental Validation

In previous sections thetransfer graph approach has been described. In this section, we first present the Carlink Platform (http://carlink.lcc.uma.es/) as well as its services and constraints. Then, it is described how the transfer graph was validated in Carlink Platform for real scenarios.The Carlink Wireless Traffic Service Platform is designed to provide a basis for a wide range of commercial and governmental traffic, safety, and transport services (see Figure4). The platform is a wireless ad hoc type communication entity with connectivity to the backbone network via base stations. The communication platform itself is the key element of Carlink, but the various services created to the platform have an important role. The three most important services are the traffic local road weather service (RWS), the traffic management service (TMS), and multimodal transport service (MTS).Figure 4
Carlink platform structure.The local RWS is derived from the FMI (Finnish Meteorological Institute) road weather model [14] and provides automatic traffic safety enhancement operations by gathering safety related information from vehicles and delivering consolidated data back, automatically without requiring user initiation. The TMS provides the traffic status by using static traffic information offered by the authorities and the dynamic traffic information given by the Carlink floating car application. This application is composed of several cars collecting information about the vehicle density in different locations of the road network and providing information of the traffic status. Finally, the MTS calculates multimodal itineraries according to a travel requested and a set of constraints specified by the user. This service is based in the transfer graph approach which has been extensively described in Section 2.The platform exploits information of the RWS and TMS, as well as of other services, in order to generate accident or incident warning from traffic and weather conditions (see Figure4). The MTS uses this information to calculate best routes avoiding bad condition roads and accidental areas to reduce the traveling time, or even recommending to change the transport mode if a blocked road is detected (e.g., to park the car near a train station and taking the train instead).


### 4.1. Experimental Environment

The Wireless Traffic Service Platform is divided in three different parts: Traffic Service Central Unit (TSCU), Traffic Service Base Station (TSBS), and Mobile End User (MEU) with ad hoc connectivity and (noncontinuous) backbone network connectivity. The whole platform can be seen as data exchange architecture between TSCU and MEU, while TSBS acts as bidirectional data transceivers. MEUs communicate between them in an ad hoc manner when encountering and can also send critical data directly to the TSCU by using a lower-capacity communication method (GRPS). The service cores are external systems connected to TSCU.TSCU achieves and processes up-to-date traffic platform information from the service cores. The TSCU updates regularly TSBS with the more recent traffic platform information related to their area, through the fixed network. Each TSBS disseminates the traffic platform information to every MEU that passes close to it by using a wireless ad hoc connection. Finally, MEUs disseminate this information when encountering (see Figure5).Figure 5
Carlink platform architecture.MEU and TSBS are equipped with acquisition system that collect their own information (speed, GPS-data, airbag blast, road temperature, etc.) and transmit regularly to TSCU. This data is processed by the TSCU, and if a critical event is detected in an area (e.g., accident, bad road condition), a warning message is delivered in real-time directly to MEUs known to be in the warning area by using GPRS or similar communication method.The advantage of this architecture is that both users (MEU) and disseminating systems (TSBS) send regularly information of the road condition to the TSCU. This is specially important when an accident occurs, because the TSCU is informed in real-time and can warn drivers in the surrounding of the accident area. Besides, since cars communicate each other when encountering, the number of TSBS necessary in roads can be considerably reduced, and also the system cost.


### 4.2. Experimental Results in Real Scenario

The validation of the developed system was performed in a real scenario (see Figure6). The route origin is the Belgian city of Arlon, and the destination is Luxembourg city (Luxembourg). Several thousands of commuters do daily this trip by car, train, bus, or by a combination of these transport modes.Figure 6
Validation scenario.Atransfer graph abstracting this scenario was deployed in the Carlink Platform and made available for the MTS. The transfer graph has 73 nodes, 49 transfer points, and 226 arcs and contains three components, associated to train, car, and bus. We consider that changing between two transport modes is done by walking, and this cost is represented in transfers.The transfer graph approach is implemented in the MTS of the Carlink Platform. The user requests are sent to the MTS through a client application for mobile devices. In this application, the user can select the travel preferences (e.g., transport modes, departure time, origin, and destination), send the request to the MTS, and get the optimal path from the Carlink Platform (Figure7).Figure 7
Screenshots of the application for mobile devices. Selecting the preferences for the traveling, confirming and showing the itinerary steps.In our scenario, the selected preferences are optimizing travel time to go from Arlon to Luxembourg by using any kind of transport mode and departing at 5:50. The first route recommended by the MTS consists in going directly by car using the highway (Table4). While we are traveling by car, the TMS is reported at 6:00 with a perturbation in the current itinerary. Since this perturbation modifies the transport data for road transports, precalculations are recomputed for components bus and car, but not for rail. This perturbation increases the travel time for route 1 up to 80 minutes. Automatically, the MTS recalculates a second route taking into account this perturbation and the current GPS position of the traveller. This information is reflected to the user by the client application. The second route is expected to arrive 25 minutes before the first route and its itinerary steps are the following: park near the next train station in Kleinbettingen, take the next train to Luxembourg, and finally the bus to the final destination, as indicated in Table 4.Table 4
Routes calculated for the validation scenario.
Itinerary steps (departure and arrival time)RouteTransport  ModeTime  (min.)Arlon, 34 cova st.Highway E25/A4Kleinbettingen parking stationKleinbettingen train stationLuxembourg train stationLuxembourg bus stationLuxembourg 29 JFK ave.1Car40′5:506:301Car80′6:017:21(updated)2Car9′6:016:10Walk5′6:106:15Train18′6:156:33Walk5′6:336:38Bus18′6:386:56


## 4.1. Experimental Environment

The Wireless Traffic Service Platform is divided in three different parts: Traffic Service Central Unit (TSCU), Traffic Service Base Station (TSBS), and Mobile End User (MEU) with ad hoc connectivity and (noncontinuous) backbone network connectivity. The whole platform can be seen as data exchange architecture between TSCU and MEU, while TSBS acts as bidirectional data transceivers. MEUs communicate between them in an ad hoc manner when encountering and can also send critical data directly to the TSCU by using a lower-capacity communication method (GRPS). The service cores are external systems connected to TSCU.TSCU achieves and processes up-to-date traffic platform information from the service cores. The TSCU updates regularly TSBS with the more recent traffic platform information related to their area, through the fixed network. Each TSBS disseminates the traffic platform information to every MEU that passes close to it by using a wireless ad hoc connection. Finally, MEUs disseminate this information when encountering (see Figure5).Figure 5
Carlink platform architecture.MEU and TSBS are equipped with acquisition system that collect their own information (speed, GPS-data, airbag blast, road temperature, etc.) and transmit regularly to TSCU. This data is processed by the TSCU, and if a critical event is detected in an area (e.g., accident, bad road condition), a warning message is delivered in real-time directly to MEUs known to be in the warning area by using GPRS or similar communication method.The advantage of this architecture is that both users (MEU) and disseminating systems (TSBS) send regularly information of the road condition to the TSCU. This is specially important when an accident occurs, because the TSCU is informed in real-time and can warn drivers in the surrounding of the accident area. Besides, since cars communicate each other when encountering, the number of TSBS necessary in roads can be considerably reduced, and also the system cost.


## 4.2. Experimental Results in Real Scenario

The validation of the developed system was performed in a real scenario (see Figure6). The route origin is the Belgian city of Arlon, and the destination is Luxembourg city (Luxembourg). Several thousands of commuters do daily this trip by car, train, bus, or by a combination of these transport modes.Figure 6
Validation scenario.Atransfer graph abstracting this scenario was deployed in the Carlink Platform and made available for the MTS. The transfer graph has 73 nodes, 49 transfer points, and 226 arcs and contains three components, associated to train, car, and bus. We consider that changing between two transport modes is done by walking, and this cost is represented in transfers.The transfer graph approach is implemented in the MTS of the Carlink Platform. The user requests are sent to the MTS through a client application for mobile devices. In this application, the user can select the travel preferences (e.g., transport modes, departure time, origin, and destination), send the request to the MTS, and get the optimal path from the Carlink Platform (Figure7).Figure 7
Screenshots of the application for mobile devices. Selecting the preferences for the traveling, confirming and showing the itinerary steps.In our scenario, the selected preferences are optimizing travel time to go from Arlon to Luxembourg by using any kind of transport mode and departing at 5:50. The first route recommended by the MTS consists in going directly by car using the highway (Table4). While we are traveling by car, the TMS is reported at 6:00 with a perturbation in the current itinerary. Since this perturbation modifies the transport data for road transports, precalculations are recomputed for components bus and car, but not for rail. This perturbation increases the travel time for route 1 up to 80 minutes. Automatically, the MTS recalculates a second route taking into account this perturbation and the current GPS position of the traveller. This information is reflected to the user by the client application. The second route is expected to arrive 25 minutes before the first route and its itinerary steps are the following: park near the next train station in Kleinbettingen, take the next train to Luxembourg, and finally the bus to the final destination, as indicated in Table 4.Table 4
Routes calculated for the validation scenario.
Itinerary steps (departure and arrival time)RouteTransport  ModeTime  (min.)Arlon, 34 cova st.Highway E25/A4Kleinbettingen parking stationKleinbettingen train stationLuxembourg train stationLuxembourg bus stationLuxembourg 29 JFK ave.1Car40′5:506:301Car80′6:017:21(updated)2Car9′6:016:10Walk5′6:106:15Train18′6:156:33Walk5′6:336:38Bus18′6:386:56


## 5. Related Work

The multimodal transport problem under the time-dependence constraint is not often studied in literature. As far as we know there are two works related to time-dependent multimodal transport problem which present the performance of their approach on different instances of the problem [2, 5].Authors in [5] abstract the problem with nonhierarchical multimodal graph and propose several data structures and tables, previously precalculated, in order to optimize the computation. The problem is simplified as well as the space search by considering that the optimum paths between two nodes at any departure time are almost always topologically the same. Nevertheless, this constraint cannot be considered in realistic multimodal networks, because perturbations modify the conditions of the networks at different times of the day. Bielli et al. [2] consider the problem of multimodal transport between towns. The problem is geographically divided and abstracted with hierarchical graph: towns are represented by subgraphs, which are interconnected by direct links. The shortest paths inside subgraphs are previously precomputed, reducing the search space. The main goal of this work is the proposed abstraction of the problem, which can be partially parallelized. The proposed approach is tested in networks composed on many small-sized subgraphs.Table5 presents a comparison between these works and transfer graph approach on the same instances of the problem. Since different machines are used in the experiments (Pentium II, UltraSPARC III, and T7300), computation time has been normalized by two benchmarks [15, 16]. According to these benchmarks, T7300 and UltraSPARC III are 13.3 and 1.32 times faster than Pentium II, respectively. These ratios are applied to computation time and included in Table 5. After these corrections, our results are still faster and advantageous, even if they were performed in an old Pentium II. The overall results show that transfer graph approach performs better with respect to the normalized computation time. The possible reason of this performance is due to precalculations, and the decomposition of the SPP in transfer graph simplified the problem.Table 5
Comparative performances of approaches on different instances of the problem.
NumberNumberAverage CPU time (second)Normalized average CPU time (second)NodesArcsAppr. 1 [2]Appr. 2 [5]Transfer.GAppr. 1 [2]Appr. 2 [5]Transfer.G502000.330.540.0010.330.710.011003000.530.810.0120.531.070.162006001.27—0.0251.27—0.3350015004.316.190.0544.318.170.72100030006.5513.590.2486.5517.943.30


## 6. Conclusion and Future Work

The main contribution of this research is an approach for the multimodal transport problem which deals with distributed nature of real transport information providers.Thetransfer graph can abstract scenarios with distributed transport information sources, since it separates and keeps all transport modes in different unimodal networks. Besides, each unimodal network can be easily updated when unexpected perturbations are detected. This characteristic is very important because the RWS and TMS provide in real-time information about weather and traffic condition, and if an incident or delay is detected, only those unimodal networks related to the warning area must be recalculated, instead of the total network.The decomposition of the SPP intransfer graphs provides an adequate solution for systems which receive multiple and frequent requests. Nevertheless, precalculations limited the scalability of the transfer graph abstraction in terms of space memory.Thetransfer graph approach has been tested with several instances of the SPP, calculating the solution in less than one second in average. This approach provides better performance in terms of computation time than other related works.The transfer graph approach has been developed as a multimodal transport service for the Carlink Platform and validated in real conditions using several transport means. This service will be deployed and made active and will provide an important solution for thousand of daily travellers in Luxembourg.Our future work is to take advantage of the inherent parallel and distributed structure exhibited bytransfer graph. For this purpose, relevant paths will be computed by using multiobjective Evolutionary Algorithm within each component separately and concurrently and will be also experimented and tested in large real multimodal network spanning many countries and involving several transportation service providers.



---

*Source: 512613-2009-09-08.xml*