Subscribe Now Subscribe Today
Research Article
 

An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)



Hicham Mouncif, Mohamed Rida and Azedine Boulmakoul
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

This study focuses on the problem of multimodal shortest path in the transportation networks system, where users have several modes to travel from an origin to a destination. To extend the traditional shortest path problem an innovative framework is presented, which integrates a set of constraints on the sequence of the used modes on the multimodal path. The aim is to deal with an efficient design for the multimodal shortest path computation taking into accounts 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 computational complexity and the correctness of the algorithm are proved. Attention is also devoted to the multimodal path operator developed on the base of the proposed algorithm. A Location Based Service (LBS) integrating our transit path planning computation is developed.

Services
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Hicham Mouncif, Mohamed Rida and Azedine Boulmakoul, 2011. An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS). Journal of Applied Sciences, 11: 1-15.

DOI: 10.3923/jas.2011.1.15

URL: https://scialert.net/abstract/?doi=jas.2011.1.15
 
Received: August 30, 2010; Accepted: October 19, 2010; Published: November 10, 2010



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 origin-Destination 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 GIS-Transit 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 object-oriented paradigm. This strategy allows a definition of a node and arc as an abstraction of sub-networks. 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 well-known graph problems for which efficient algorithms exist; e.g., route finding is solved by shortest path problem. Three levels are defined to manage network oriented-data: 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 O-D trip and the second concerns the modal transfers number performed in the O-D 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 O-D 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 network-oriented 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 = (Nr, Er), where Nr is the set of nodes and Er is the set of arcs, r∈ M. The multimodal graph G is partitioned to a set of monomodal sub graphs: SGr1 (Nr1, Er1), SGr2 (Nr2, Er2),…, SGrq (Nrq, Erq), such that:

N = Nr1 ∪ Nr2 ∪ … ∪ Nrq, Nri ∩ Nrj = ø

Er1 ∪ Er2 ∪ … ∪ Erq ⊂ E, Er ∩ Er’ = ø

where, i ≠ j and ri ∈ 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 = Er1 ∪ Er2 ∪ … ∪ Erq ∪ T

Definition 2: Let, SGri(Nri, Eri), SGrj(Nrj, Erj) be two monomodal sub graphs, where i≠j and ri, rj ∈ M, By TA(SGri, SGrj) we denote the set of transfer arcs between Nri and Nrj.

Definition 3: Let, { SGr1, SGr2, …, SGrq }be a collection of monomodal sub graphs. We have the following notation:

TA(SGri) = ∪i≠ jTA(SGri, Sgrj)

that denoted the set all transfer arcs for SGri, with respect to { SGr1, SGr2, …, SGrq }.

Definition 4: Let, {SGr1, SGr2, …, SGrq} be a collection of monomodal sub graphs.

By ETA(SGri) we design the set of all the emanating transfer arcs from SGri in TA(SGri). ETA(SGri) is called the set of emanating transfers and is noted by ETAri.

Definition 5: Let, {SGr1, SGr2, …, SGrq} be a collection of monomodal sub graphs. Then, TN(SGri) is the set of nodes of Eri that have at least one entering or emanating transfer arcs in TA(SGri). TN(SGri) is called the transfer nodes set of SGri and is denoted by TNri.

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 SGri, we introduce a special arc set named monomodal optimal arc set of SGri. Definition 6 gives its formal interpretation.

Definition 6: Let, {SGr1, SGr2, …, SGrq} be a collection of monomodal sub graphs.

MOA(SGri) is the set of the precomputed monomodal optimal path between two distinct transfer nodes only within SGri. Then, MOA(SGri) is named the monomodal optimal arc set, is noted by MOAri. 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.


Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)
Fig. 1: A multiomdal graph G and its monomodal sub graphs


Table 1: The Corresponding Information of monmodal sub graphs in Fig. 1
Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)

MULTIMODAL PATH OPERATOR

Path operator can be classified into categories of network-oriented 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, {SGr1, SGr2, …, SGrq} be a collection of monomodal sub graphs. Let X be a set of sub graphs SGri, we define the following sets:

Ω(X) = ∪i(MOPri ∪ ETAri)

is the emanating transfer and monomodal optimal arc sets of all the sub graphs in X and Δ(X) = ∪i TNri is the transfer node sets of all the sub graphs in X.

Definition 8: Let, {SGr1, SGr2, …, SGrq} be a collection of monomodal sub graphs. We consider the nodes x ∈ SGri and y ∈ SGrj. By MVSPG (x, y) we denote the multimodal viable shortest path between the x and y within the graph. By MVSPG’(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’ = Nri ∪ Nrj ∪ Δ, where Δ = Δ(SGrk)1≤ k ≤ q, k≠ i,j.

E’ = Eri ∪ Erj ∪ Ω, where Ω = Ω(SGrk)1≤ k ≤ q, k≠ i,j.

Theorem 1: Let, {SGr1, SGr2, …, SGrq} be a collection of monomodal sub graphs.

For any node pair x, y ∈ G, we have the following result:

MVSPG(x, y) = MVSPG’(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 SGr1, SGr2, …, SGrq that composed the graph G.

Step 1: Find SGri = (Nri, Eri) and SGrj = (Nrj, Erj) such that: O ∈ SGri et D ∈ SGrj. Set:

N’ = Nri ∪ Nrj ∪ Δ, où Δ = Δ(SGrk)1≤ k ≤ q, k≠ i,j.

E’ = Eri ∪ Erj ∪ Ω, où Ω = Ω (SGrk)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 (z1, z2, …, zm), in which : z1 = x and zm = 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 = (z1, z2, …, zm) is monomodal, if zi ∈ Nr, ∀ I ∈ {1, …, m}.

Definition 10: A multimodal path is a path accomplished by using several modes. Hence, the path Πxy = (z1, z2, …, zm) is multimodal, if the nodes zi, ∀ 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 O-D 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 node-triplet on the graph G’. By the notation Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS) 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:

Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS) is Monomodal, if the mode m coincide with the mode n
Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS) 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)
Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS) 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)

Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)
Fig. 2: Representation of Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)

Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)
Fig. 3: Begin_ModalTransfer representation.

Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)
Fig. 4: End_ModalTransfer representation.

Figure 2 illustrates examples for the definitions 11, 12 and 13.

Figure 3 illustrates an example of Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS) 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 Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS) 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 Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS) is Monomodal, then the Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS) is viable
if Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS) is End_ModalTransfer, then the viability of the transit from node v through node u to node w, must be controlled
Finally, if Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS) is Begin_ModalTransfer, then the number of modal transfers is incremented and tested if not superior of the maximum transfer given by the user

Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)
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 Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS). We assume that the path ΠOD from the nodes O to D is comprised of sequence of Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS).

Each arc (v, u) is associated with one mode. In this case, we consider the modal transfer as a mode. The notations Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)and Nv,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 Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS) 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 Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)= 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 Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS) 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.

Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)
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 λmv,u the time required to travel from node v to node u on mode m ∈ M ∪ T. By the notation Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)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 Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS) is Monomodal, Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS) represents the time penalties associated with the turning movement. If Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS) is End_ModalTransfer, then Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS) is the waiting time until the coming scheduled departure. Finally, if Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS) 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 Cmv,u represents the expected path time for going from arc (v, u) on mode m to destination D.

Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)

Theorem 2: Upon termination of the algorithm, every label Cmu,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 least-cost 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.


Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)
Fig. 7: The multimodal graph G


Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)
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
Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)


Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)
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.

Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)

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.

Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)

LOCATION BASED SERVICE (LBS) FOR MULTIMODAL PATH PLANNING APPLICATION

GIS-Technology 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 GeoMobility-Server concept and other elements of LBS architecture. This architecture requires the integration of many disparate technologies that is designed to support coupling archived and real-time 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 server-side dependencies. OpenLayers implements a JavaScript API for building rich web-based geographic applications, similar to the Google Maps and MSN Virtual Earth APIs, with one important difference-openlayers 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 real-time information about mobile objects. The administrator can use web-browser or Google Earth to view GPS current location. Portal server provides displaying GPS location at real-time and interactive map operations through web browser. The prototype system allows user to use Google Earth to display real-time 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 location-based 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 stand-alone 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 object-relational 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 object-relational database. PostGIS spatially enables the PostgreSQL server, allowing it to be used as a back-end spatial database for geographic information systems (GIS) and web-mapping applications in the same manner as Microsoft's SQL Server Spatial and Oracle's Spatial database extension
pgRouting is an optional routing add-in 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.

Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)
Fig. 10: System architecture

Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)
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.

Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)
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 route-based 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 GIS-analysis. 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 {SGr1, SGr2, …, SGrq} be a collection of monomodal sub graphs.

For any node pair x, y ∈ G, we have the following result:

MVSPG(x, y) = MVSPG’(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 ∈ SGri, y ∈ SGrj, where i ≠ j and ri, rj ∈ M.

Case 1: We assume that x and y belongs to the same monomodal sub graph SG. Let PG(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 PCSG(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,

SPCG(x, y) = SPCSG(x, y)

Any path of (2) consists of arcs which can be represented by sequence of nodes x, z1, z2, …, zm, 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 :

PCG(x, y) = PCG(x, a) + PCG(a, b) + PCG(b, y)

By the principle of optimality, we have the following:

SPCG(x, y) = SPCG(x, a) + SPCG(a, b) + SPCG(b, y) (*)

As the shortest path SPG(x, a) consists only of edges of SG, it falls into (1). Therefore, we have SPCG(x, a) = SPCSG(x, a). Similarly, we have SPCG(b, y) = SPCSG(b, y).

For SPCG(a, b) we use the following proposition.

Proposition 2: Let, {SGr1, SGr2, …, SGrq} be a collection of monomodal sub graphs of the graph G. For any transfer nodes a, b ∈ Δ, where Δ(SGrk)1≤ k ≤ q, we have:

SPCG(a, b) = SPCΩ(a, b), where Ω =Ω(SGrk)1≤ k ≤ q.

Proof: Let, PCG(a, b) represent a path from the transfer nodes a to b. Then, for any path PG(a, b) all the transfer nodes on it as well as the two end nodes can be represented sequentially by the node sequence, a, z1, z2, …, zm, b. Hence, its path cost can be represented by:

PCG(a, b) = PCG(a, z1) + PCG(z1, z2) + … + PCG(zm, y)

By the principle of optimality, the shortest path cost:

SPCG(a, b) = SPCG(a, z1) + SPCG(z1, z2) + … + SPCG(zm, 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, z1, z2, …, zm, b belong to the same set of emanating transfer and multimodal optimal arc sets, say (x, z1) ∈ Ω(SGr1), (z1, z2) ∈ Ω(SGr2), …, (zm, b) ∈ Ω (SGrm), with 1 ≤ r1, r2, …, rm ≤ q. As the shortest path cost SPG(x, z1) can be obtained in from Ω(SGr1), we would have SPCG(x, z1) = SPCΩ(SGr1)(x, z1). For a similar reason, we have SPCG(z1, z2) = SPCΩ(SGr2)(z1, z2) and so on, until SPCG(zm, b) = SPCΩ(SGrm)(x, z1). Thus, the shortest path cost SPCG(a, b) can be represented by:

SPCG(a, b) = SPCΩ(SGr1)(b, z1) + SPCΩ(SGr2)(z1, z2) + …. + SPCΩ(SGrm)(zm, b)

From this, we know that the shortest path cost SPCG(a, b) can be computed by using only the edges in Ω(SGrk)1≤ k ≤ q. Thus, we have proven the proposition that

SPCG(a, b) = SPCΩ(a, b), where Ω =Ω(SGrk)1≤ k ≤ q.

Now, by using the result of the proposition in equation (*), we have

SPCG(x, y) = SPCSG(x, a) + SPCΩ(a, b) + SPCSG(b, y)

From this equation, we know that the shortest path cost SPCG(x, y) can be denoted by:

SPCG(x, y) = min ({SPCSG(x, a) + SPCΩ(a, b) + SPCSG(b, y)/ a, b ∈Δ(SGrk)1≤ k ≤ q })

By combing the preceding result of the multimodal viable path we have:

MVSPG(x, y) = MVSPG’(x, y)

Case 2: We assume that the nodes x and y belongs to two distinct sub graphs SGri and SGrj, 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 SGri and SGrj respectively. Thus, we have

MVSPG(x, y) = MVSPG’(x, y)

Theorem 2: Upon termination of the algorithm, every label Cmu,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 least-cost 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 Cmu,w at every stage of computation means that there is no Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS) 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 Cmu,w that has updated the label Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS) at an earlier stage of computation, according to the following equation:

Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)

where, Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS) 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 Cmu,w, it corresponds to least-cost viable path ΠOw from the node origin to the node w through arc (u, w), such that:

Πow =(z1 = O, z2, …zm-1 = u, zm =w),

If not, then there exists another path Π’Ow from the origin node to the node w through arc (u, w) that is least-cost path such that:

Π’Ow =(z1 = O, z2, …zm-2 = v, zm-1 = u, zm =w)

This would mean that we have:

Image for - An Efficient Multimodal Path Computation Integrated Within Location based Service for Transportation Networks System (Multimodal Path Computation within LBS)

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 decrease-values 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’|).

REFERENCES
1:  Anderson, L.D., 1991. Applying geographic information systems to transportation planning. Trans. Res. Record, 1305: 113-117.
Direct Link  |  

2:  Agawal, R., S. Dar and H.V. Jagadish, 1990. Direct transitive closure algorithms: Design and performed evaluation. ACM Trans. Database Syst., 15: 427-458.
Direct Link  |  

3:  Battista, M.G., M. Lucertini and B. Simeone, 1995. Path composition and multiple choice in bimodal transportation networks. Proceedings of the 7th World Conference on Transportation Research Modelling Transport Systems, July 16-21, 1995, Sydney, Australia, pp: 750-759.

4:  Boulmakoul, A., R. Laurini, H. Mouncif and G. Taqafi, 2002. Path-finding operators for fuzzy multimodal spatial networks and their integration in mobile-GIS. Proceedings of the 2nd IEEE International Symposium on Signal Processing and Information Technology, December 18-21, 2002, Marrakech, Morocco, pp: 51-56.

5:  Bruntsch, S. and K. Rehrl, 2005. Vienna-SPIRIT: Smart travelling by using integrated and intermodal traveller information. Proceedings of the 5th European Congress and Exhibition on Intelligent Transport Systems and Services, June 1-3, ITS Crossroads Eur. Transport, Hannover, Germany, pp: 1-8.

6:  CALTRANS, 2002. Guide for the preparation of traffic impact studies. California DOT. http://www.dot.ca.gov/hq/traffops/developserv/operationalsystems/reports/tisguide.pdf.

7:  Dar, S. and R. Ramkirishnan, 1994. A performance study of transitive closure algorithms. ACM SIGMOD Record, 23: 454-465.
Direct Link  |  

8:  Fernandez, E., J. Cea, M. Floria and E. Cabrera, 1994. Network equilibrium models with combined modes. Transport. Sci., 28: 182-193.

9:  FHWA and FTA, 2007. The transportation planning process key issues: A briefing book for transportation decisionmakers, officials and staff. FHWA-HEP-07-039. http://www.incog.org/transportation/about/TransportationPlanningProcess.pdf.

10:  Jing, N., Y.W. Huang and E.A. Rundensteiner, 1998. Hierarchical encoded path views for path query processing: An optimal model and its performance evaluation. IEEE Trans. Knowledge Data Eng., 10: 409-432.
CrossRef  |  

11:  Jung, S. and S. Pramanik, 2002. An efficient path computation model for hierarchically structured topographical road maps. IEEE Trans. Knowledge Data Eng., 14: 1029-1046.
Direct Link  |  

12:  Langou, B. and M. Mainguenaud, 1994. Manipulations of geographical information system network component. Proceedings of the 6th International Symposium on Spatial Data Handling, September 5-9, 1994, Edinburgh, pp: 888-898.

13:  Lozano, A. and G. Storchi, 2001. Shortest viable path algorithm in multimodal networks. Transport Res., 35: 225-241.
Direct Link  |  

14:  Mainguenaud, M., 1995. Modeling the network component of geographical information system. Int. J. Geographic Inform. Syst., 9: 575-593.
Direct Link  |  

15:  Mainguenaud, M., 1996. Constraint-based queries in a geographical database for network facilities. Comput. Environ. Urban Syst., 20: 139-151.
CrossRef  |  

16:  Miller, H.J. and J.D. Storm, 1996. Geographic information system design for networks equilibrium-based travel demand models. Transport. Res. Part C Emerg. Technol., 4: 373-389.
Direct Link  |  

17:  Meng, L., A. Zipf and S. Winter, 2008. Map-Based Mobile Services: Design, Interaction and Usability. Springer, Heidelberg.

18:  Modesti, P. and A. Sciomachen, 1998. A utility measure for finding multiobjective shortest paths in urban multimodal transportation networks. Eur. J. Operat. Res., 111: 495-508.
CrossRef  |  

19:  Mouncif, H. and A. Boulmakoul, 2003. Multimodal transportation networks: Object modeling and k-multimodal shortest path. Proceedings of the International Conference on Information Systems and Engineering, July 03, Canada, pp: 75-80.

20:  Pallottino, S. and M.G. Scutella, 1997. Shortest path algorithms in transportation models: Classical and innovative aspects. Technical Report TR-97-06, Department of Informatics, Univeristy of Piza, Italy.

21:  PgRouting, 2010. pgRouting project. http://pgrouting.postlbs.org.

22:  PostgreSQL/PostGIS, 2009. Guide de lutilisateur de PostgreSQL/PostGIS. http://www.postgis.fr/.

23:  Dowling, R.G., R. Dowling and D. Reinke, 2008. Multimodal level of service analysis for urban streets. NCHRP Report 616, TRB. http://www.trb.org.

24:  Rehrl, K., N. Goll, S. Leitinger and S. Bruntsch, 2005. Combined indoor/outdoor smartphone navigation for public transport travelers. Proceedings of the 3rd Symposium LBS and Tele Cartography, Nov. 28-30, Vienna, Austria, pp: 235-239.

25:  Sayar, A., 2008. GIS service oriented architecture. Community Grids Laboratory, IN, USA.

26:  Theriault, M., 1999. Modelling commuter trip length and duration within GIS: Application to an O-D survey. J. Geographic Inform. Decision Anal., 3: 40-56.

27:  Ziliaskopoulos, A.K. and W. Wardell, 2000. An intermodal optimum path algorithm for multimodal networks with dynamic arc travel times and switching delays. Eur. J. Operat. Res., 125: 486-502.
CrossRef  |  

28:  OGC., 2005. OpenGIS location service (OpenLS) implementation specification: Core services. http://www.opengeospatial.org/standards/olscore.

©  2021 Science Alert. All Rights Reserved