INTRODUCTION
The transportation networks system includes several travel modalities. The users have distinct alternatives for traveling from one place to another. In reality, the private network is increasingly affected by traffic jam, rail network is scattered and it does not covered all places and surface network is thick and arrive everywhere. The multimodal travelling alternatives proposed to users aim at taking advantage of the several mode networks by linking two or more different transportation modes to move from a start point to a destination point. Trip chain for user travel may include several modes. A work trip commute might involve driving an auto to a rail or to bus stop, with possibility of additional transfers within or among modes to complete the trip. A significant travel constraint in multimodal context concerns the number of modal transfers that the user is able to execute in one originDestination trip.
In order to increasing the attractiveness of the public transportation networks,
many research (Agawal et al., 1990; Dar
and Ramkirishnan, 1994; CALTRANS, 2002; FHWA
and FTA, 2007; Dowling et al., 2008) was developed
to assist travelers with planning, perception and decision making. The path
planning module is an essential component of GISTransit Planning Application,
aiding travellers in choosing the best path among several travel alternatives.
The role of the path planning is to locate a connected sequence of segment of
the mode networks from a current location to a destination. The path planning
module includes three elements: path evaluation, path computation and path display.
The path computation is based on criteria such as the shortest travel distance
or travel time. The path evaluation determines the attributes (e.g., traffic
congestion) of a given segment between two points. The path display communicates
the optimal path to the travelers. The path evaluation and computation depend
systematically on the transit networks modeling. There have been many research
reported in the literature that focus on the transit network modeling (Jing
et al., 1998; Jung and Pramanik, 2002; Langou
and Mainguenaud, 1994; Mainguenaud, 1995). Mainguenaud
(1995) presents a data model to manage networks with a Geographical Information
System. The data model is based on the merge of graph theory concepts and the
objectoriented paradigm. This strategy allows a definition of a node and arc
as an abstraction of subnetworks. Jing et al. (1998)
proposed a special data model to structure the transit network. Their idea consists
of partitioning large graph into smaller sub graphs and organizing them in a
hierarchical fashion by pushing up border nodes. This approach precomputes the
shortest paths between all the member nodes (including the boundary nodes) of
each sub graph only within that sub graph. Jung develops a new graph model,
called Hierarchical multilevel graphs, for very large topographical road maps.
This graph model (HiTi) provides a tool to structuring and abstracting a topographic
road map in a hierarchical fashion.
Most of those models are useful to structure the transit networks in hierarchical fashion, but it still need to take into account the multimodal aspect of the transit networks. In general, data models have to provide facilities to represent relationships among objects. In many cases, it is helpful to view such relationships as graph structures. Then many queries can directly be mapped to wellknown graph problems for which efficient algorithms exist; e.g., route finding is solved by shortest path problem. Three levels are defined to manage network orienteddata: physical level (i.e., spatial coordinates), logical level (i.e., graph modeling the transportation network) and applicative level (i.e., the structuring of a graph taking into account application dependent modelling).
In the multimodal routing context, many works have been studied the multimodal
shortest viable path problem (Battista et al., 1995;
Fernandez et al., 1994; Boulmakoul
et al., 2002; Mouncif and Boulmakoul, 2003;
Ziliaskopoulos and Wardell, 2000). Two principal constraints
are considered in this type of problem; the first account for the set of transit
modes used to accomplish the OD trip and the second concerns the modal transfers
number performed in the OD trip. In this regard, we discussed the viable path
notion (i.e., feasible path). This one is treated in few studies (Battista
et al., 1995; Lozano and Storchi, 2001).
Fernandez et al. (1994) studied the shortest
path on bimodal networks. Pallottino and Scutella (1997)
considered the number of modal transfers in a path as an attribute in the multicriteria
shortest path. Modesti and Sciomachen (1998) proposed
a utility measure that takes into account the propensity of the decision maker
with respect to the given transportation modalities. Miller
and Storm (1996) modeled the transport mode change with a modal transfer
arc. Ziliaskopoulos and Wardell (2000) studied the problem
of shortest path for multimodal networks with dynamic arc travel times and switching
delays.
The multimodal path is executed by using several mode of transportation; hence the viable path is a multimodal path that respects a set of constraints on its sequences of used modes. The multimodal shortest viable path is one of the most important current routing problems and its solution is very interest to travel in Transportation Networks System. Each traveler assigns its personal attribute to OD paths in the multimodal networks, he/she can give the maximum of the generalized cost, the modes of transport utilized (for example, a user can choose which modes he prefers to use to reach his destination and a number of modal transfers that he/she can executed).
In the case under study, we consider a Transportation Networks System that comprises several mode networks. Each mode network is associated with one transport mode. The networks are connected amongst themselves by modal transfers. The first step for modeling the transportation networks system is to derive a model witch capture all the possible transit modalities and the interconnections among them. A graph is an efficient concept to model networkoriented data. In particular, the graph considered in this work is a multimodal graph, where the nodes represent the places where one has to choose between continuing by the current mode or switching to another one and arcs represents transportation links connecting two nodes from different routes. In addition, links that made a change mode or modal transfer are added to the multimodal graph, to represent for example the following activities: waiting for a bus or a train, boarding/alighting a bus or a train, walking between two transit stations for transfer.
The multimodal graph is partitioned into monomodal sub graphs, where each monomodal sub graph represents a mode network. This fashion of structuring the transportation networks system is efficient to perform an enhance design for the multimodal viable computation, but it exists one main drawbacks. The drawbacks concerns the considerable computational effort required to expand some mode networks due to its large volume of data, consequently it affected the computational time required to compute optimum paths within the transportation networks system. Thus, we need an efficient database organization method for structuring the transportation networks system to speed up the computation of a minimum cost path and also conserved the characteristics of viability of the multimodal path. In this regard, we deal with a multimodal path operator strategy. This strategy allowed an efficient data organization technique, it precomputes and stores some partial monomodal path information. This operator uses the precomputed partial monomodal path information to prune the search space when computing a minimum cost path. Hence, it represents an important component of our network solver.
TRANSPORTATION NETWORKS SYSTEM MODELING
Transportation networks system is comprised of networks. Each mode network is associated with one transport mode. The networks are connected amongst themselves by modal transfers. This system can be viewed as a multimodal graph. In multimodal graph a node represent a place where one has to select between continuing with the current mode or changing it, a arc is a connection between two nodes. We have two types of arcs: transport arc and transfer arc. Transport arc models a linking between two nodes by only one transport mode. A transfer arc represents a commutation from one mode to another.
Definition 1: A multimodal graph is a triplet G = (N, E, M), where, N is the nodes set, E is the edges set and M is the transport modes associated with the arcs.
We assume that each network is modelled by one monomodal sub graph SG = (N_{r},
E_{r}), where N_{r} is the set of nodes and E_{r} is
the set of arcs, r∈ M. The multimodal graph G is partitioned to a set of
monomodal sub graphs: SG_{r1} (N_{r1}, E_{r1}), SG_{r2
}(N_{r2}, E_{r2}),…, SG_{rq }(N_{rq},
E_{rq}), such that:
N = N_{r1} ∪ N_{r2} ∪ … ∪ N_{rq},
N_{ri} ∩ N_{rj }= ø
E_{r1} ∪ E_{r2} ∪ … ∪ E_{rq}
⊂ E, E_{r} ∩ E_{r’ }= ø

where, i ≠ j and r_{i} ∈ M, for 1≤i≤q.
Let, T be the set of modal transfers between the different modalities, then
the elements of T are the transfer arcs and we have the following:
E = E_{r1} ∪ E_{r2} ∪ …
∪ E_{rq} ∪ T 
Definition 2: Let, SG_{ri}(N_{ri}, E_{ri}),
SG_{rj}(N_{rj}, E_{rj}) be two monomodal sub graphs,
where i≠j and ri, rj ∈ M, By TA(SG_{ri}, SG_{rj}) we
denote the set of transfer arcs between N_{ri} and N_{rj}.
Definition 3: Let, { SG_{r1}, SG_{r2}, …, SG_{rq}
}be a collection of monomodal sub graphs. We have the following notation:
TA(SG_{ri}) = ∪_{i≠ j}TA(SG_{ri},
Sg_{rj}) 
that denoted the set all transfer arcs for SG_{ri}, with respect to
{ SG_{r1}, SG_{r2}, …, SG_{rq} }.
Definition 4: Let, {SG_{r1}, SG_{r2}, …, SG_{rq}} be a collection of monomodal sub graphs.
By ETA(SG_{ri}) we design the set of all the emanating transfer arcs from SG_{ri} in TA(SG_{ri}). ETA(SG_{ri}) is called the set of emanating transfers and is noted by ETA_{ri}.
Definition 5: Let, {SG_{r1}, SG_{r2}, …, SG_{rq}} be a collection of monomodal sub graphs. Then, TN(SG_{ri}) is the set of nodes of E_{ri} that have at least one entering or emanating transfer arcs in TA(SG_{ri}). TN(SG_{ri}) is called the transfer nodes set of SG_{ri} and is denoted by TN_{ri}.
Each monomodal sub graph is identified by its transfer nodes since they exclusively belong to one sub graph. Based on transfer nodes of one monomodal sub graph SG_{ri}, we introduce a special arc set named monomodal optimal arc set of SG_{ri}. Definition 6 gives its formal interpretation.
Definition 6: Let, {SG_{r1}, SG_{r2}, …, SG_{rq}} be a collection of monomodal sub graphs.
MOA(SG_{ri}) is the set of the precomputed monomodal optimal path between two distinct transfer nodes only within SG_{ri}. Then, MOA(SG_{ri}) is named the monomodal optimal arc set, is noted by MOA_{ri}. Each monomodal optimal arc is associated with the mode _{ri}.∈ M.
In Fig. 1, we report an example that explains the definitions 4, 5 and 6. Table 1 shows the corresponding monomodal sub graph information.

Fig. 1: 
A multiomdal graph G and its monomodal sub graphs 
Table 1: 
The Corresponding Information of monmodal sub graphs in Fig.
1 

MULTIMODAL PATH OPERATOR
Path operator can be classified into categories of networkoriented operators
based on graph manipulation. Many current researches consider that the path
evaluation operator is one of the most important operators in a Geographical
Information System. Mainguenaud (1996) precise that
the user’s queries contain many implicit constraints that are not specified
while defining a query (e.g., i would like to go from one place to another one).
The work introduces the characterization of database alphanumeric attributes
in the following classes: Neutral, Time, Space and Aplicative_unit. The required
database modeling must to take into account these constraints.
The evaluation of path is performed with a path operator. The specification of the path operator proposed in this work is this evaluation that corresponds to the detection of a multimodal viable shortest path between an origin node and a destination node, based on our algorithmic approach proposed in the following paragraph. This path can be a direct link (i.e., a successor in a graph) or a more complex path (i.e., a transitive closure of a graph).
In this work, we implement a new operator called multimodal path operator in our LBS application. This operator is used to elaborate the multimodal viable shortest path in abstraction levels and can be used in routing to dramatically improve performance taking advantage of the theorem 1.
Definition 7:. Let, {SG_{r1}, SG_{r2}, …, SG_{rq}}
be a collection of monomodal sub graphs. Let X be a set of sub graphs SG_{ri},
we define the following sets:
Ω(X) = ∪_{i}(MOP_{ri} ∪
ETA_{ri}) 
is the emanating transfer and monomodal optimal arc sets of all the sub graphs
in X and Δ(X) = ∪_{i} TN_{ri} is the transfer node
sets of all the sub graphs in X.
Definition 8: Let, {SG_{r1}, SG_{r2}, …, SG_{rq}}
be a collection of monomodal sub graphs. We consider the nodes x ∈ SG_{ri}
and y ∈ SG_{rj}. By MVSP_{G }(x, y) we denote the multimodal
viable shortest path between the x and y within the graph. By MVSP_{G’}(x,
y) we denote the multimodal viable shortest path on the new graph G’ =(N’,
E’) issued from the original graph G as follows:
N’ = N_{ri} ∪ N_{rj} ∪ Δ, where Δ
= Δ(SG_{rk})_{1≤ k ≤ q, k≠ i,j}.
E’ = E_{ri} ∪ E_{rj} ∪ Ω, where Ω
= Ω(SG_{rk})_{1≤ k ≤ q, k≠ i,j}.

Theorem 1: Let, {SG_{r1}, SG_{r2}, …, SG_{rq}}
be a collection of monomodal sub graphs.
For any node pair x, y ∈ G, we have the following result:
MVSP_{G}(x, y) = MVSP_{G’}(x,
y) 
Proof. Appendix A.
Multimodal path operator strategy: Let, O be the origin node and D the destination node. Given a collection of monomodal sub graphs SG_{r1}, SG_{r2}, …, SG_{rq} that composed the graph G.
• 
Step 1: Find SG_{ri} = (N_{ri}, E_{ri})
and SG_{rj} = (N_{rj}, E_{rj}) such that: O ∈
SG_{ri} et D ∈ SG_{rj}. Set: 
N’ = N_{ri} ∪ N_{rj} ∪ Δ, où
Δ = Δ(SG_{rk})_{1≤ k ≤ q, k≠ i,j}.
E’ = E_{ri} ∪ E_{rj} ∪ Ω, où
Ω = Ω (SG_{rk})_{1≤ k ≤ q, k≠ i,j}.

• 
Step 2: Find the multimodal shortest path from the
node O to the node D on the new graph G’ = (N’, E’) by using
the MSP procedure 
The second step used the procedure proposed in the next paragraph to determined the multimodal shortest viable path between the nodes O and D on the new graph G’ = (N’, E’).
MULTIMODAL SHORTEST VIABLE PATH PROCEDURE
Now, we are interesting to find the multimodal shortest path from the origin node to the destination node, that respects the set of constraints on its sequences of used modes and includes an acceptable number of modal transfers, on the new graph G’= (N’, E’). Each arc of the set E’ is associated with one mode r ∈ M.
Multimodal viable path description: A path Π_{xy} between the node x and y is an alternating sequence of nodes and arcs of the form (z_{1}, z_{2}, …, z_{m}), in which : z_{1} = x and z_{m} = y. In a multimodal context we find two types of paths: the monomodal path and the multimodal path.
Definition 9: A monmodal path is a path accomplished by only one mode r ∈ M. Hence, the path Π_{xy} = (z_{1}, z_{2}, …, z_{m}) is monomodal, if z_{i} ∈ N_{r}, ∀ I ∈ {1, …, m}.
Definition 10: A multimodal path is a path accomplished by using several modes. Hence, the path Π_{xy} = (z_{1}, z_{2}, …, z_{m}) is multimodal, if the nodes z_{i}, ∀ I ∈ {1, …, m}, belongs to distinct nodes set.
In transportation networks system, it is not easy to use the private vehicle down town because the private network suffers of traffic jam and also the parking space is not enough, rail network is scattered and it does not arrive everywhere, but surface network is thick and arrives almost everywhere. Since rail network is connected and its transboards are made easier to user, then a user takes it long as possible in her/his path.
Therefore, the user has a set of several modes for traveling, but he/she not disposed to undertake too many modal transfers. In the following, the private mode and the rail mode are considered as a constraint modes.
A characteristic of multimodal path is the use of distinct modes of transportation,
then consistent with the works (Lozano and Storchi, 2001;
Modesti and Sciomachen, 1998), we assume that no modal
transfer allows to transfer from public modes to private mode since it is implicitly
assumed that once path is not started with private modality, it is not possible
anymore to take it for reaching the destination. For this reason a OD feasible
path that use the private mode, it take it at the origin node O. Then, the viable
path is a path that respects the following constraints:
• 
The number of modal transfer of the path must respect the
maximum that the user is able to establish 
• 
If the path uses the rail mode, it must include only one consecutive
sequence of rail mode 
• 
If the path uses the private mode, it must include only one
consecutive sequence of private mode with initial node O 
Hence, a path accomplished only by one travel mode is a trivial viable path. Therefore, the path viability is directly related to the number of modal transfer established during it.
In order to deal with the formulation of the multimodal viable path, we introduce
the definitions of some notations which will be used in the rest of the study.
Let (v, u, w) denote a nodetriplet on the graph G’. By the notation
we mean, the transit from node v to node w, when entering node u from arc (v,
u) on mode m and switching to arc (u, w) and mode n.
The following assumptions are used in below:
• 
is Monomodal, if the mode m coincide with the mode n 
• 
is Begin_ModalTransfer, if the mode m is a transit mode (i.e., m ε
M) and n is a modal transfer (i.e., n ε T) 
• 
is End_ModalTransfer, if the mode m (i.e., m ε T) is a modal transfer
and n is a transit mode (i.e., n ε M) 

Fig. 2: 
Representation of 

Fig. 3: 
Begin_ModalTransfer representation. 

Fig. 4: 
End_ModalTransfer representation. 
Figure 2 illustrates examples for the definitions 11, 12 and 13.
Figure 3 illustrates an example of
that can be modeled by Begin_ModalTransfer. The situation represents one user
driving its car from a given place to the parking area and walking to another
place. Figure 4 elucidates an example of
that may be represented by End_ModalTransfer. It corresponds to the situation
when one user walks from a given place to the metro station and riding a metro
to another metro station close to its destination.
Let, (v, u, w) be a node triplet on the graph G. As a consequence from above discussions, we have the following results:
• 
if
is Monomodal, then the
is viable 
• 
if
is End_ModalTransfer, then the viability of the transit from node v through
node u to node w, must be controlled 
• 
Finally, if
is Begin_ModalTransfer, then the number of modal transfers is incremented
and tested if not superior of the maximum transfer given by the user 

Fig. 5: 
Viable transit Procedure for End_ModalTransfer 
Dealing with the previous assumptions of the viable path, we define the procedure
used for determining the viability of the .
We assume that the path Π_{OD} from the nodes O to D is comprised
of sequence of .
Each arc (v, u) is associated with one mode. In this case, we consider the
modal transfer as a mode. The notations and
N_{v,u} represents the set of modes and the number of modal transfers
in the current path Π_{Ou} from the origin node O to the node u
through the arc (v, u).
If
is a End_ModalTransfer, we use the procedure given in Fig. 5.
To allow entering a node origin, we introduce a virtual arc (0, O) in the beginning
of the trip. It is associated with =
O.
Furthermore, Leaving one transit mode m ∈ M, in the current path Π is denoted by Um, it means that the transit mode m was used in the current path Π.
In the case where the
is a Begin_Modal Transfer, we need to confirm if the number of modal transfers
associated with the arc (v, u) is not superior than the maximum of transfers
given by the user (Max_transfer), then the number of modal transfer performed
on the current path to arrive at the node w is incremented and marked that the
transit mode of the arc (v, u) it was used to arrive at the node w. Those steps
are defined in Fig. 6.
Time constraint description: Transportation networks system is comprised
of set of lines of a public transit mode. A model of the user’s behavior
consists in assuming that each user has a priori to choose his attractive subset
of lines to go from node u to destination d, such that, at node u, the user
is willing to board the first carrier of lines with a stop at node u, which
arrives.

Fig. 6: 
Procedure of viable path for Begin_ModalTransfer transit 
We assume that each station u is associated with a set of scheduled departure list. Public rail modes are the modes such that at each stop, the user could take only one line with fixed schedule. Public surface modes are characterized by imprecise schedules and at each stop the user is willing to board the first carrier of the attractive set of lines.
Let, (v, u, w) be a node triplet on the graph G. We denote by λ^{m}_{v,u}
the time required to travel from node v to node u on mode m ∈ M ∪ T.
By the notation we
denote the delay at node u, the delay at node u, when entering node u from arc
(v, u) on mode m and switching to arc (u, w) and mode n.
In the case when
is Monomodal,
represents the time penalties associated with the turning movement. If
is End_ModalTransfer, then
is the waiting time until the coming scheduled departure. Finally, if
is Begin_ModalTransfer, we assume that leaving the transit mode associated with
the arc (v, u) is accomplished without delays.
Design of the multimodal shortest viable path procedure: The label C^{m}_{v,u}
represents the expected path time for going from arc (v, u) on mode m to destination
D.
Theorem 2: Upon termination of the algorithm, every label C^{m}_{u,w} is either an infinite number, meaning that no viable path exists from the origin node O to the node u through arc (u, w) on mode m, or a finite number that represents the leastcost viable path from the origin node O to the node u through arc (u, w) on mode m.
Proof: Appendix A.
Proposition 1: The algorithm with a Fibonacci heap as a storage data structure has computational complexity O(E’*N’).
Proof: Appendix A.
From this proposition, it is easy to see how the new graph G’ = (N’, E’) can significantly reduce the search space necessary for the multimodal viable path computation. That is without using the new graph G’, the search space would be G = (V, E). Furthermore, the multimodal graph structuring facilitate the searching of multimodal viable path, since this one if it use the metro or the private modalities, it must enter and leave the corresponding monomodal sub graph in one time, also the number of modal transfers is controlled in easy way.
CASE STUDY
Figure 7 illustrates a practical example of the modeling
approach. For simplicity we suppose that the Transportation Networks System
include three distinct mode networks. The mode networks considered in this example
are: the private network, the metro network and the bus network. The Transportation
Networks System is modeled by a multimodal graph G = (N, E, M), where N is the
set of nodes, E is the set of arcs and M is the set of transport modes associated
with arcs. The graph G is partitioned into three monomodal sub graphs, where
each one represents a corresponding mode network. A node on the graph G may
model metro station, stop of bus, parking, etc. An arc on the graph G may model
a transportation mode connecting two nodes in the same monomodal sub graph or
a modal transfer between two nodes locating in distinct monomodal sub graphs.
The transfer arcs design the allowed modal transfer between the different mode
networks.

Fig. 7: 
The multimodal graph G 

Fig. 8: 
Roles assigned to nodes and arcs. 
Figure 8 illustrates a specific role assigned to nodes and
arcs. In this case the transfer modal is considered as a mode. M includes metro
mode, bus mode and the private mode. The value along each arc is the arc’s
travel time. In this case, we assume that the transit travel times include the
delays.
We choose that the origin node O belongs to the private sub graph and the destination
node D is located in the metro sub graph. The modeling approach is done in two
steps. The first one taking advantage of the theorem 1, selects the necessary
search space by marking the subset of nodes and arcs to constructed the set
of nodes N’ and the set of arcs E’ respectively, of the new graph
G’ (Fig. 9). In this example, the private sub graph,
the metro sub graph and the transfer arc set are conserved in the new graph
G’.
Table 2: 
Transfer nodes, emanating transfer and monomodal optimal
arcs of all mode r sub graphs 


Fig. 9: 
The new mutimodal graph G’ 
The bus sub graph is reduced into the transfer node set and the bus optimal
arc set (Table 2). The following step used the MSVP procedure
to search the multimodal viable shortest path from the nodes O to D on the new
graph G’.
When one travel modal has admitted by the user, the algorithm find the multimodal
viable shortest path accomplished by the private mode and the metro mode from
the origin node O to the destination node D and has an cost equal to 3.61 units.
For two modal transfers, the algorithm finds the multimodal viable shortest
path from the origin node O to the destination node D accomplished by using
the three modes: private mode, bus mode and the metro mode, its cost is 3.24
units.
LOCATION BASED SERVICE (LBS) FOR MULTIMODAL PATH PLANNING APPLICATION
GISTechnology integrated with spatial networks modeling promises to bring
solutions to the transit planning problems. Many researchers have identified
several advantages of using GIS for transportation modeling such as: analytical
capabilities, visual power, efficiency of data storage, integration of spatial
databases and capabilities for spatial analysis (Theriault,
1999; Boulmakoul et al., 2002).
The Open GIS Consortium (OGC) has introduced the OpenLS standard, which addresses
the technical specifications for LBS, to enhance a range of personal, governmental,
industrial and emergency mobile applications (OGC, 2005).
At the heart of the OpenGIS Location Services (OpenLS) standard lies the GeoMobility
server, which comprises Abstract Data Types (ADTs) and the core services that
are: location utilities services, directory services, presentation service,
gateway service and route determination service (Meng et
al., 2008).
In this study, we developed a multimodal path planning software according to
OpenLS specifications. In Fig. 10, we report the system architecture
that is based on the GeoMobilityServer concept and other elements of LBS architecture.
This architecture requires the integration of many disparate technologies that
is designed to support coupling archived and realtime geospatial data with
scientific applications such as simulation, visualization or data mining software
Anderson, 1991; Rehrl et al.,
2005). The architecture can be demarcated into the following components:
Client (mobile or desktop): all objects equipped with a location detection mechanism (such as GPS) can be considered in this category. In our prototype system, we have used OpenLayers and Google Maps for displaying maps. OpenLayers is a pure JavaScript library for displaying map data in most modern web browsers, with no serverside dependencies. OpenLayers implements a JavaScript API for building rich webbased geographic applications, similar to the Google Maps and MSN Virtual Earth APIs, with one important differenceopenlayers is free software, developed for and by the open source software community.
Portal and service platforms: Its principal responsibility is the administration of the system, but it can be asked to visualize maps with realtime information about mobile objects. The administrator can use webbrowser or Google Earth to view GPS current location. Portal server provides displaying GPS location at realtime and interactive map operations through web browser. The prototype system allows user to use Google Earth to display realtime GPS location at 3D angle, fly through view and also with 3D buildings using KML file.
Location server: Is used to determinate mobile objects positions. Generally, the database that deals with mobile objects locations will be distributed among cellular architecture networks. Location server is mostly embedded in a Gateway Mobile Location Center (GMLC).
Geomobility server: Is an OpenLS platform through which content and
service providers can deliver and service locationbased applications. The core
services are Location Utilities Service, searching facilities Service, Presentation
Service and Route Determination Service (OGC, 2005).
In the follow subsection, we specify the multimodal path planning service that
extends OGC OpenLS Route Determination Service. His principal task is to determine
travel routes and navigation information between two or more points among a
multimodal transportation network. In our prototype system, this server component
was implemented by using Mapserver and Mapscript. Mapserver is an Open Source
geographic data rendering engine written in C. Beyond browsing GIS data, it
allows to create geographic image maps that can direct users to content. MapServer
provides support for many OGC specifications. It provides support for WMS (Web
Mapping Service), SLD (Styled Layer Descriptor), WFS (Web Feature Service) and
experimental support for WCS (Web Coverage Service) (Sayar,
2008). Mapscript provides a scripting interface for MapServer for the construction
of Web and standalone applications. It can be used independently of CGI MapServer
and it is a loadable module that adds MapServer capability. MapScript currently
exists in PHP, Perl, Python, Ruby, Tcl, Java and .NET flavors.
GIS database: Is implemented under PostgreSQL/PostGIS using pgRouting package.
• 
PostgreSQL is an objectrelational database management
system (ORDBMS) based on POSTGRES, Version 4.2, developed at the University
of California at Berkeley Computer Science Department. POSTGRES pioneered
many concepts that only became available in some commercial database systems
much later. PostgreSQL supports a large part of the SQL standard and offers
many modern features. And because of the liberal license, it can be used,
modified and distributed by anyone free of charge for any purpose, be it
private, commercial, or academic (PostgreSQL/PostGIS,
2009) 
• 
PostGIS is a spatial database extension for the popular
PostgreSQL objectrelational database. PostGIS spatially enables the PostgreSQL
server, allowing it to be used as a backend spatial database for geographic
information systems (GIS) and webmapping applications in the same manner
as Microsoft's SQL Server Spatial and Oracle's Spatial database extension 
• 
pgRouting is an optional routing addin for PostgreSQL
(when the PostGIS package is also installed) and implements Shortest path
Dijkstra Algorithm, Shortest Path A* algorithm, Shortest Path Shooting Star
and Traveling Sales Person (TSP) algorithms. pgRouting is part of PostLBS,
which provides core tools for Location Based Services (LBS) as Open Source
Software (OSS). Its tools are similar to those found on proprietary software
(pgRouting. 2010) 
The principal task of the software is the capability to support the mulimodal modeling throughout several phases. It has been performed under Mapserver with PhpMapscript library coupled with postgresSQL/postGIS DBMS and OpenLayers. Some of major features of these tools include: displaying and querying of hundreds of raster, vector and database formats, ability to run on various operating systems (Windows, Linux, Mac OS X, etc.), support for popular scripting languages and development environments (PHP, Python, Perl, Ruby, Java, .NET) etc.
Multimodal path planning service: The OpenLS Route Service determines
a route for a traveler that must indicate the start point and the endpoint and
use the Presentation Service to display a route map with directions and the
calculated path (Bruntsch and Rehrl, 2005; Dowling
et al., 2008). The OpenLS Route Service also supports extended navigation
functionality. If the user wants to know which route to take, he can specify
endpoints and waypoints based on a certain set of criteria and determine a route.
The user can also specify the route preference (such as fastest and shortest)
and the preferred mode of transport. In this section, we specify the Multimodal
Path Planning Service as an extension of the OpenLS Route Service that comprises
the same functionality plus the option to provide the client with all information
necessary to generate multimodal route directions that considers various modes
(walking, cycling, automobile, public transit, etc.) and connections among modes
so each can fill its optimal role in the overall transport system.
A class diagram (Fig. 11) is integrated into the model for
a broad range of objects dealing with the topological network.

Fig. 10: 
System architecture 

Fig. 11: 
Class diagram representing network infrastructure 
Furthermore, the software environment model supports both microscopic as well
as macroscopic traffic planning tools. The data interface brings the interaction
between the database level and the user interface levels that are the edition
tools.
In other level, the spatial representation of the transportation networks system
is funded on the following basic entities: Node, Link and Graph. For each entity
we assigned a role describing its class function. The entity Node may represent
several physical elements, for example: street intersections, railroad switches,
stations … etc. The entity Link represents a connection between two successive
Nodes. Each Link is assigned two Nodes representing its initial and final extremity.
The Links are considered as an oriented connection between its extremities.
The Link may model different physical elements such as: streets, railroad tracks
…etc. All objects can be updated.

Fig. 12: 
Multimodal path planning application 
The updates depend on the type of edit being performed. The entity Turns describe
possible movements of vehicles at junctions between specific Links. Turns are
used to model turn restrictions in street networks and for detailed street intersection
delays. One Turn relates to two Links and one Node. Interchange is a category
of objects, which are used to model modal transfer at stations or terminals.
The entity Stop is a physical element location for embarking and disembarking
routebased transportation, such as busses and metros. Passengers are able to
change between busses at bus stops and between trains at railroad stations.
We introduce the entity Line to represent public transport services. Each Line
is assigned a itinerary designed by a group of Stops. Some Stops represent the
Line terminator. The entity Terminator is added to the model to describe the
ending and the starting point for the public traffic service. Finally, the entities
HyperNode and HyperLink proposed by Langou and Mainguenaud
(1994) were implemented in this work to overcome the macroscopique and microsocpique
representation of the traffic planning within The Transportation Networks System.
The hyperNode represent an abstraction of several sub networks, but the HyperLink
is an abstraction of one sub network.
In the Fig. 12, the graphical user interfaces for desktop user (GUI) is presented. This Fig. 12 displays the transport network of Casablanca city in Morocco including several modes (train, tramway and subway). The user can choose the departure station and the destination station and also he can choose his preferred transport modes, the maximum number of transfers and the criteria to be considered (time or cost). According to the user preferences, the application can display the multimodal shortest path.
This prototype is developed in order to respond to the future requirements of the passengers in Casablanca city in Morocco during the displacement within the city. The application is not yet operational; this is because the infrastructure of the subway and the tramway is under construction. The implementation of this application will be the subject of a future project between the university and the city authorities of Casablanca.
CONCLUSION
This study has examined the multimodal routing problem in Transportation Networks System. This system is viewed as a multimodal graph and each mode network is modeled by a monomodal sub graph. The mode network structuring was used to speed up the computation of the multimodal shortest viable path and also to perform a new design for the multimodal path operator. The proposed algorithm takes into account not only the expected travel time, but also additional constraints such as: delays at mode and arc switching points, viability of the sequence of the used modes and the number of modal transfers. The correctness and the complexity of the approach were theoretically proved.
The proposed approach adds more aspects of the integration of the path evaluation operator into the GISanalysis. The users can define the number of modal transfers and the mode of transport he/she preferred to reach his/her destination.
APPENDIX
Appendix A:
Theorem 1: Let {SG_{r1}, SG_{r2}, …, SG_{rq}}
be a collection of monomodal sub graphs.
For any node pair x, y ∈ G, we have the following result:
MVSP_{G}(x, y) = MVSP_{G’}(x,
y) 
Proof: To prove the theorem, recall the definition of a multimodal viable path. A path from the origin node to the destination node is a viable path if the following are satisfied:
• 
The number of modal transfers of the path must be inferior
or equal the maximum of the transfers given by the user 
• 
If the path connect a rail mode sub graph, it must enter (from
transfer node) to this sub graph and leave it (by transfer node) at most
in one time 
• 
If the path connect a private mode sub graph, it must enter
(from transfer node) to this sub graph and leave it (by transfer node) at
most in one time 
Following the definition 8 all transfer arcs of the graph G are locating into
the set E’, so, the first condition of the path viability on the new graph
G’ is satisfied. Furthermore, the corresponding modes are assigned to the
monomodal optimal arcs and all transfer nodes of the graph G are in the new
set N’, then this will guaranteed the other conditions of the path viability.
So, now, we need to prove that the shortest path cost between any pair of nodes
of the graph G is the same as the one computed on the new graph G’ = (E’,
N’). In order to prove this result, we proceed in several steps as the
proof in (Jung and Pramanik, 2002). Let x, y be a node
pair of the graph G. We have two cases, the first one is that x and y belongs
to the same monomodal sub graph SG. The second consists that x and y belongs
to two distinct sub graphs, i.e., x ∈ SG_{ri}, y ∈ SG_{rj},
where i ≠ j and ri, rj ∈ M.
Case 1: We assume that x and y belongs to the same monomodal sub graph SG. Let P_{G}(x, y) represent a path from the nodes x to y. The paths from the node x to the node y can be classified into two categories : (1) the path composed only of arcs of the sub graph SG, or (2) the path consists of arcs not only from SG but from other sub graphs of the graph G.
For paths of (1), the cost path from x to y is noted by PC_{SG}(x,
y). If all paths from x to y are of this kind. It is evident that the shortest
path from x to y is also defined in SG. That is,
SPC_{G}(x, y) = SPC_{SG}(x, y)

Any path of (2) consists of arcs which can be represented by sequence of nodes
x, z_{1}, z_{2}, …, z_{m}, y. As this path contains
arcs of other sub graphs. Then, the path would leave the sub graph SG and eventually
come back. Therefore, the path contains at least two transfer nodes a and b
∈ TN(SG). Choose a be the first such node and b be the last such node on
this path. The cost of this particular path can be denoted by :
PC_{G}(x, y) = PC_{G}(x, a) + PC_{G}(a, b)
+ PC_{G}(b, y)

By the principle of optimality, we have the following:
SPC_{G}(x, y) = SPC_{G}(x, a) + SPC_{G}(a,
b) + SPC_{G}(b, y) (*) 
As the shortest path SP_{G}(x, a) consists only of edges of SG, it falls into (1). Therefore, we have SPC_{G}(x, a) = SPC_{SG}(x, a). Similarly, we have SPC_{G}(b, y) = SPC_{SG}(b, y).
For SPC_{G}(a, b) we use the following proposition.
Proposition 2: Let, {SG_{r1}, SG_{r2}, …, SG_{rq}}
be a collection of monomodal sub graphs of the graph G. For any transfer nodes
a, b ∈ Δ, where Δ(SG_{rk})_{1≤ k ≤ q},
we have:
SPC_{G}(a, b) = SPC_{Ω}(a, b),
where Ω =Ω(SG_{rk})_{1≤ k ≤ q}. 
Proof: Let, PC_{G}(a, b) represent a path from the transfer
nodes a to b. Then, for any path P_{G}(a, b) all the transfer nodes
on it as well as the two end nodes can be represented sequentially by the node
sequence, a, z_{1}, z_{2}, …, z_{m}, b. Hence,
its path cost can be represented by:
PC_{G}(a, b) = PC_{G}(a, z_{1})
+ PC_{G}(z_{1}, z_{2}) + … + PC_{G}(z_{m},
y) 
By the principle of optimality, the shortest path cost:
SPC_{G}(a, b) = SPC_{G}(a, z_{1})
+ SPC_{G}(z_{1}, z_{2}) + … + SPC_{G}(z_{m},
y) 
In the transfer node sequence, every two successive transfer nodes correspond
to either the transfer node entering a sub graph and the transfer node leaving
that sub graph or vice versa. Therefore, every successive pair of nodes in the
transfer nodes sequence a, z_{1}, z_{2}, …, z_{m},
b belong to the same set of emanating transfer and multimodal optimal arc sets,
say (x, z_{1}) ∈ Ω(SG_{r1}), (z_{1}, z_{2})
∈ Ω(SG_{r2}), …, (z_{m}, b) ∈ Ω (SG_{rm}),
with 1 ≤ r1, r2, …, rm ≤ q. As the shortest path cost SP_{G}(x,
z_{1}) can be obtained in from Ω(SG_{r1}), we would have
SPC_{G}(x, z_{1}) = SPC_{Ω(SGr1)}(x, z_{1}).
For a similar reason, we have SPC_{G}(z_{1}, z_{2})
= SPC_{Ω(SGr2)}(z_{1}, z_{2}) and so on, until
SPC_{G}(z_{m}, b) = SPC_{Ω(SGrm)}(x, z_{1}).
Thus, the shortest path cost SPC_{G}(a, b) can be represented by:
SPC_{G}(a, b) = SPC_{Ω(SGr1)}(b,
z_{1}) + SPC_{Ω(SGr2)}(z_{1}, z_{2})
+ …. + SPC_{Ω(SGrm)}(z_{m}, b) 
From this, we know that the shortest path cost SPC_{G}(a, b) can be
computed by using only the edges in Ω(SG_{rk})_{1≤ k ≤
q}. Thus, we have proven the proposition that
SPC_{G}(a, b) = SPC_{Ω}(a, b),
where Ω =Ω(SG_{rk})_{1≤ k ≤ q}. 
Now, by using the result of the proposition in equation (*), we have
SPC_{G}(x, y) = SPC_{SG}(x, a) + SPC_{Ω}(a,
b) + SPC_{SG}(b, y) 
From this equation, we know that the shortest path cost SPC_{G}(x, y) can be denoted by:
SPC_{G}(x, y) = min ({SPC_{SG}(x,
a) + SPC_{Ω}(a, b) + SPC_{SG}(b, y)/ a, b ∈Δ(SG_{rk})_{1≤
k ≤ q} }) 
By combing the preceding result of the multimodal viable path we have:
MVSP_{G}(x, y) = MVSP_{G’}(x,
y) 
Case 2: We assume that the nodes x and y belongs to two distinct sub
graphs SG_{ri} and SG_{rj}, respectively. Then, the demonstration
is similar to the one makes for paths of categories (2) in the case1. The difference
in this case is that the transfer nodes a and b belongs to the sub graphs SG_{ri}
and SG_{rj} respectively. Thus, we have
MVSP_{G}(x, y) = MVSP_{G’}(x,
y) 
Theorem 2: Upon termination of the algorithm, every label C^{m}_{u,w} is either an infinite number, meaning that no viable path exists from the origin node O to the node u through arc (u, w), or a finite number that represents the leastcost viable path from the origin node O to the node u through arc (u,w).
Proof: First, we prove that the algorithm terminates in finite number of iterations. This can be determined by contradiction. Suppose that the set X is not empty in a finite number of iterations, this means that there is at least one label that is infinitely improved at each step. This will eventually lead to negative label, which contradicts the fact that all labels must be positive.
At every stage of the computation the label of a node is either an infinite
or finite number. An infinite label C^{m}_{u,w} at every stage
of computation means that there is no
that has updated the label up to this stage. Therefore, there exists no viable
path from any node u to node w and consequently from the origin node. If the
label is finite, then there exist a C^{m}_{u,w} that has updated
the label
at an earlier stage of computation, according to the following equation:
where,
is either viable or viable_Begin_Modal Transfer. Consequently, there exists
a viable path from the origin node O to the node u.
On the other hand, upon termination of the algorithm every node u with a finite
label C^{m}_{u,w}, it corresponds to leastcost viable path
Π_{Ow} from the node origin to the node w through arc (u, w), such
that:
Π_{ow} =(z_{1} = O, z_{2},
…z_{m1} = u, z_{m} =w), 
If not, then there exists another path Π’_{Ow} from the origin
node to the node w through arc (u, w) that is leastcost path such that:
Π’_{Ow} =(z_{1} = O, z_{2},
…z_{m2} = v, z_{m1} = u, z_{m} =w) 
This would mean that we have:
where (v,u) ∈E’.
This relation means that the algorithm does not terminate since node w has not been scanned. Thus, _{KK} still in the set X. This contradicts the statement that the algorithm has terminated.
Proposition 3: The algorithm with a Fibonacci heap as storage data structure has computational complexity O(E’*N’).
Proof: To obtain the time complexity of the algorithm, recall that it involves operations if initialization (step 1) is O(E’), take one node and remove it from the scanning set (step 2) is O(E’*log(E’)). Two operations: viability tests and decreasevalues determine the complexity of the step 3.
It is clear that the step 3 determines the major complexity of the algorithm. We need to examine N’ nodes each with at most E’ arcs, i.e. E’ values to update. Thus, the complexity of the algorithm is O(E’*N’).