INTRODUCTION
With the increase of cars on the streets, more and more congestion occurs.
The traffic congestion causes not only a monetary problem but also a pollution
problem at the same time (Peytchev and Coggan, 1999).
Among a number of problems faced by residents in large cities in the world especially
mega cities, traffic congestion are of prime importance. The high cost of transportation
infrastructure, rapid urban population growth and some traffic demand management
programs have led traffic authorities to limit doortodoor transportation and
encourage shared riding especially in traffic pick periods in central business
districts (Teimouri et al., 2008b).
Shared ride systems match the travel demand of passengers with the supply by
vehicles such that the passengers find rides to their destinations (Wu
et al., 2008). The shared riding helps to save money on travel expenses,
improve environmental conditions and reduce traffic load and parking demand.
The shared riding may be considered from vehicles centered viewpoint and travelercentered
viewpoint (Teimouri et al., 2008a). The shared
riding from vehicles centered viewpoint includes assigning the available vehicles
and decides routes and schedules (for pickup and delivery events) for each vehicle,
on the basis of customer requests; the overall costs and the level of service
have to be optimized (Castelli et al., 2002).
The shared riding from travelercentered viewpoint includes trip planning regarding
available vehicle with free capacity and finding optimal or sub optimal trip
in terms of minimizing travel cost or travel time, etc. In this condition, a
traveler is not only dependent on the street network, but also on the available
means of transportation. The information about available vehicle routes and
their time schedules has to be evaluated, so that travelers know which vehicle’s
route and time table is relevant to their optimal trips.
The aim of this study is developing a shared ride system for trip planning
in a dynamic traffic network from travelercentered viewpoint using a Geospatial
Information System (GIS). GIS as a matured concept, has a great potential to
accommodate a variety of transportation applications. It is due to the fact
that GIS has superior data management, visualization and analysis capabilities
which are vital in planning processes.
Recent technology developments in miniaturization of computing devices, locationsensing
technology and ubiquitous wireless networks in a single device enable new types
of social behavior such as adhoc meetings of people in colocated geographical
space (Nittel et al., 2007). Advances in technology
allow envisioning a novel sharedride system. In such a system, pedestrians
are the agents with transport demand, called clients and vehicles, or hosts,
providing the transport supply. Finding rides in an adhoc manner, without the
help of an external infrastructure, is accomplished by local negotiation between
these agents via radiobased communication (Wu et al.,
2008).
The shared ride system is explored in detail below (Tessmann,
2006; Winter et al., 2005):
• 
A client formulates a request for a sharedride trip containing
the complete route with timestamp information from current location to the
desired destination. It is the client’s responsibility to compute an
optimal trip, for instance using a shortestpath algorithm, before communication
starts. The request is then transmitted to nearby network nodes and rebroadcasted
further in a peertopeer manner 
• 
Hosts have their own independent travel plan and are assumed to be willing
to pick up passengers on their way without detours. Hosts who receive a
request decide if they are able to offer a ride to the client based on their
future travel plan and current passenger capacity. They apply a pattern
matching between the requested street segments and their own travel plans
for determining their potential contribution in the received request 
• 
Having received all offers, the client selects the best offer and books
the trip. This decision can be based, for instance, on preferring earliest
departure or arrival times 
The selected segments can cover only a part of the client’s trip and they
can have temporal gaps (waiting times at transfer points) and spatial gaps (segments
for which currently no supply is known). Using the pattern matching strategy,
the client is only allowed to follow a predefined route i.e., the shortest path
from the current location of the client to the desired destination. But the
actual trips conducted by clients are inflexible and prone to producing longer
travel times on average. This can happen if street segments of the predefined
path are experiencing a low frequency of passing hosts. Although, this approach
enables the client to reach the destination, a free route choice from the routes
received from hosts via peertopeer communication have the potential to enable
shorter trip durations (Gaisbauer, 2007), because the
clients can use all offers in their neighboring effectively, even though the
received routes do not coincide with the predefined route of the origin to the
destination location.
In shared riding, travel time is highly influenced by available means of transportation (e.g., transportation providers such as taxis and private cars), in addition to traffic congestion. Average trip duration is improved in free route choice strategy in comparison with the pattern matching strategy.
This study is based on a passenger with a ride request and the cars with single
occupancy commuter willing to take passengers on their way without making detour
for these passengers. The travel plans of cars form the links of a transportation
network. These links are spatially bound to the street network, but temporally
highly irregular and the routes are by no way predictable since many of the
considered vehicles are autonomous i.e., not scheduled: at any time a new vehicle
can enter the traffic and offer rides, current vehicles can get occupied and
are temporarily not available (Winter and Nittel, 2006).
Trip planning in this environment is planning on a complex, nondeterministic
transportation network. The global optimal trip can be determined in a nondeterministic
system only in hindsight (Raubal et al., 2007).
Based on knowledge of the entire transportation network monitored by the observer,
reconstructing the transportation and communication network in hindsight is
feasible after the clients complete their trips (Guan and
Winter, 2006).
This study attempts to develop a shared ride constrained path finding system to find all reasonable paths based on the received offers at a request time instant. The passenger collects information about available transportation opportunities; plan best trip according to his preference and take ride. In each reasonable path, the invehicle time, walking time, waiting time and length of each path as the fare are provided to the passenger and he can select the best trip regarding his preferences. The question comes up what does reasonable paths mean? How to find the reasonable paths from the transportation network made of all potential means with free capacity around the customer environment? This study intends to answer the abovementioned questions.
The crucial concept utilized in this study is a spacetime network in order to abstract the received offers not only over space, but also over time, where time is considered to be a finite and discrete time frame.
MATERIALS AND METHODS
Here, basic components of the research are introduced. Hence, the spacetime network and ChronoSPT and the proposed modifications to adhere to the goal of this study are described. A sample data of San Francisco urban network has been used in the case study.
The algorithmic problem: In shared ride constrained path finding, the
optimal path can be calculated regarding time as a cost function. The optimal
path is the one that minimizes the total travel time, which is sum of several
time components such as riding, walking and waiting. However, the fastest shared
ride constrained path is not sometimes satisfying passengers. In trip planning,
passengers do not always want to know which is the best path between an OriginDestination
(OD) pair, because the weights of waiting, walking time or fare may be different
from each other and different for the same person on different purposes of the
trip (Tan et al., 2004).
In this developed shared ride constrained path finding system, what passenger wants to know is number of reasonable (or feasible) paths between the OD pairs, the trip time or fare and transfer stops in each path.
Assumptions: As mentioned above, accomplishing a free route choice strategy without limiting customers to predefined paths achieves shorter trip durations on average, compared to the route choice technique employed so far in shared ride trip planning as the pattern matching strategy and thus improves service, performance and attractiveness of shared riding.
In the study, passengers are supported to use shared ride for trip planning rather than their private cars. They do not want to limit themselves to travel along shortest path from the origin to the destination and rather using shared ride with free route choice strategy.
The model is based on a customer’s ride request and cars to offer their ride to the customer. Trip planning starts with requests from passenger for a shared ride. The requests are broadcasted to the cars in its neighborhood. Relevant cars to the requests send the passenger an offer including nodes ID ahead on their ways and arrival time on those nodes in a textual manner. After receiving the offers, passenger’s mobile computing device finds all reasonable paths from the origin to the destination in the transportation network and selects the suitable offers and books those cars. It is assumed the composed graph of all car routes with related time schedules plus the pedestrian paths around OD pairs having at least a connected path from the origin to the destination.
To reduce the network redundancy and ensure the efficiency of path finding,
some assumptions need to be defined as follow:
• 
In the proposed approach, trip planning has to be done before
the start of the trip and works well if people have some knowledge about
the environment and there are no major deviations from the travel plan.
In other words, there is no uncertainty in the elements of the underlying
transportation network 
• 
If there is no ride passing through the origin, the passenger can walk
from the origin until for example 10 min to reach the main road of the network.
In main arterial streets, the user gets ride and only he may cross the street
when gets on or off the vehicle. Sometimes it is important for customer
not to be compelled to cross the street. Near to the destination, the user
can walk a couple of minutes, too 
• 
The cars pass any nodes on time in accordance to their predicted arrival
times available in the offers 
• 
The passenger is able to get on and off cars at any intersecting nodes
of the received offers 
The assumption of ontime passing of cars at any nodes ahead on their ways
is relaxed next when the time uncertainty is taken into consideration. In other
words, the cars reach the nodes with time uncertainty. The assumption of getting
on and off at only intersecting nodes of the received offers can be relaxed
in the future when all possible pedestrian paths are taken into account.
Methodology: In order to evaluate the received offers and model the waiting in transfer stops, space time network and ChronoSPT in a discrete model are introduced.
Shortest path problem: The classic shortest path problem consists of
finding, in an oriented graph, a feasible path that links a given origin node
to a given destination node and minimizes the sum of its arc costs. Most of
the literatures have focused on the problem in which the link travel cost (or
weight) is assumed to be static and deterministic. Many efficient algorithms
have been developed by Bellman (1958), Dijkstra
(1959) and Dreyfus (1969). These are referred to
as the standard shortest path algorithms.
Nowadays, the development of new tele communication and computer technologies
has made the dynamic routing problem a reality since the required data can be
obtained and processed in realtime. Dynamic networks typically fall into one
of the two main categories. In the first category, the future characteristics
of the network are not known in advance. Algorithms which optimize the performance
of this type of network are sometimes called reoptimization algorithms, since
they must react to changes in network conditions as they occur by making small
changes to an existing optimal solution so that it remains optimal under new
conditions. The Dynamic Shortest Path (DSP) algorithms belong to this category.
In the second category, timevarying network characteristics are known at all
times. The TimeDependent Shortest Path (TDSP) algorithms are related to second
network category (Dean, 1999).
In the viewpoint of shared riding, all the cars offering their ride to the passengers form timevarying network. There is a possibility of frequent occurrence of passenger’s transfer stops i.e., changing from one car to another in shared riding makes waiting between parts of the trip inevitable. Consequently, a data structure is needed which can model the waiting times common within sharedride trip planning.
This kind of the shortest paths problem can be efficiently studied and solved
by introducing the space time network (Dean, 2004a;
Pallottino and Scutella, 1998).
The space time network: Given a directed graph G = (N, A), N is the
set of nodes and A is the set of arcs, in dynamic problems, a positive travel
time or delay d_{ij} (t) is associated with each arc (I, j) with the
following meaning: if t is the (nonnegative) leaving time from node I, then
t+ d_{ij}(t) is the arrival time at node j. In addition to the delay,
a timedependent cost c_{ij}(t) is generally associated with (I, j),
which is the cost of traveling from I to j through (I, j) starting at time t.
Furthermore, there is the possibility of waiting at the nodes; in particular,
a waiting cost w_{i}(t) can be associated with each node I, which gives
the cost of waiting at I at time t (Gaisbauer, 2007).
Several models have been defined and analyzed in the literature depending on
the properties of the delay and cost function (e.g., continuous or discrete),
on the possibility of waiting at the nodes (e.g., no waiting, waiting at each
node, waiting only at certain nodes), on the choice of leaving time from the
origin node (Pallottino and Scutella 1998).
Here, the model description is limited to the discrete case. The time variable t may vary within the discrete set T = {t_{1}, t_{2},… , t_{q}}, so that t+d_{ij} (t) ∈ T. The variable q limits the finite time frame considered and has to be adopted to the specific problem. A discrete model is no loss of generality, as discretization is generally performed in the field of transportation engineering.
The spacetime network R = (V, E) consists of timeexpanded nodes (I, t) ∈
NxT. R is then formally defined as:
where, R is a common graph with V = nq and E<=(m+n)q. In order to model
the situation where waiting at nodes is allowed, waiting arcs is introduced
in R in the following way: (i_{h}, i_{h+1}) represents waiting
at I from t_{h} to t_{h+1} and is given the unit time cost w_{i}(t_{h}),
h = 1,… , q–1 (Gaisbauer, 2007).
From an algorithmic point of view, the suggestion is selecting the nodes by
means of a chronological order i.e., by considering first the nodes corresponding
to time t_{1}, then the ones for t_{2} and so on. The resulting
algorithmic paradigm is called ChronoSPT. The paradigm uses a bucket list B
= {B_{1}, B_{2},…,B_{q}} (Dial,
1969) in order to efficiently perform the selection operation, i.e., for
implementing the chronological visit of R, where, B_{h} denotes the
bucket containing the nodes to be visited at the time instant t_{h},
h = 1, …, q. In this notation, P_{i}(t) indicates the current predecessor
of node I at time t, i.e. i_{t}, while C_{i} (t) denoted the
label associated with i_{t}.
The typical algorithm iteration is described (Fig. 1) for
the case in which looks for a minimum cost path from a given root r to other
node I ≠ r, given a leaving time t, need to be found. B_{h} denotes
the current bucket used for the node selection (Pallottino
and Scutella, 1998).
The minimum of the labels associated with each node I ≠ r gives the optimum
path cost from r to I.
Model description: The customer specifies the origin and destination
locations with arbitrary latest arrival time to destination (a request), because
nobody is willing to travel for infinite time in an urban environment. There
is an upper time limit beyond which a travel offer is not accepted (Winter
and Raubal, 2006). The domain of neighborhood of each request is created
with attention to the origin and the destination and latest arrival time to
the destination. Winter and Raubal (2006) showed convincingly
that the spacetime prism of customers imposes a clear criterion for cars to
determine whether their travel plans are potentially relevant for a customer
and his request. They also demonstrated that this criterion is efficient by
filtering out about 97% of all cars that are irrelevant for the planning process.
All cars which their routes intersect the domain and have free capacity offer
their ride to the customer without detouring their paths. In the model arcs
arrival time rather than edges’ travel time are used, as they are available
in received offers. This way leads to simpler and more natural formulations
(Dean, 2004b).
The passenger’s mobile computing device receives these offers and forms their space time network, finds the reasonable paths in the transportation network from the origin to the destination. The reasonable paths may not coincide with shortest path of origin to destination location based on network street, but are according to transportation network made of the received offers and walking paths. After enumerating all reasonable paths, the customer evaluates each path according to his constraints and selects the best trip with transfer stops, pick up and drop off times.
The entire relevant offers to each request during a finite and discrete time horizon are considered. Without a loss of generality in the context under consideration, beginning time is the same as request time instant and starts at time origin of the process.
To form space time network from the received offers, only arrival time of
all host’s routes in the intersecting nodes is needed. It means that the
other nodes on host’s route are not important in this model, because the
passenger may leave the cars at some points and continue the ride with another
host after a waiting period. All intersecting nodes can be waiting stops (with
waiting times specified with the algorithm) in getting on or off the vehicles.
The finite and discrete time horizon is made of all the time instants in intersecting
nodes sorted in ascending order.


Fig. 2: 
Two typical offers to a (a) passenger and (b) their space
time network representation 
Figure 2 shows the routes
of two cars offering free capacity to a customer and their space time network
representation. Each node has been labeled in the formed space time network by its node ID
and arrival time instant as a subscript. The arcs between two nodes with identical
ID and different time instants are waiting arcs. In this context, nodes are
transfer stops and arcs represent the time taken either to travel between each
pair of nodes with different nodes ID or to wait between each pair of nodes
with identical ID at the transfer stop.
By this way, a graph R composed of all car routes with related time schedules and pedestrian paths needs to have at least a connected path from the origin to the destination.
It is possible to solve the shortest path problem on R, by means of the entire
topological visits of R from the origin to the destination node. Each chronological
type visit of the nodes of R, i.e., a visit for nondecreasing values of time
index associated with the nodes of R, provides a topological visit of R (Pallottino
and Scutella, 1998).
As mentioned earlier, ChronoSPT gives the minimum cost (here time as cost)
path from the origin to other nodes. On the other hand, there is no need to
know which path is exactly the fastest between an OD pair only, however, knowing
all feasible paths between an OD pair is considered. Based on the results of
an ongoing research on this topic, the goal of this paper was achieved with
slight modification in ChronoSPT. These modifications accommodate our definition
of the proposed reasonable paths.
• 
It is reasonable to continue riding as far as possible on
the current ride, so that a modification is proposed as follow: 
In each chronology, when the algorithm deals with the first visited node of
a route, all relevant buckets according to other nodes of the route are filled.
Therefore, other nodes of the offer have the predecessor of the same route’s
nodes.
• 
It is reasonable to omit redundant distance and transfer from
the alternate paths, so that a modification is proposed as follow: 
As mentioned earlier, in iterations of the ChronoSPT algorithm, if the node
ID in a bucket with its existing label is greater than the new label created
in later chronology for that node, it is replaced with a new label and predecessor.
If the node ID in a bucket with its existing label is equal to the new label,
the algorithm does not handle this situation. Replacing only its predecessor
with new predecessor in some situations is proposed. In the proposed algorithm,
if one of the predecessors of the new predecessor is the same as the existing
predecessor, then the existing predecessor is not replaced. It leads to omit
the redundant distance and transfer from the alternate paths.
RESULTS
The proposed algorithm for the shared ride constrained path finding system
in transportation network was coded by VBA in ArcGIS environment. As a database,
a street network of the city downtown San Francisco is used. This section contains
the implementation results for 10 random offers for a shared ride trip request.
Table 1: 
The information of all the found reasonable paths 

The trip descriptions as a result of the
algorithm are presented: Path 1: You must walk from the origin location
to node ID = 4946, You get on the vehicle with route 5 on node ID = 4946
at 6.3 min later, You get off on node ID = 12488 at 19.4 min later, You
must walk to the destination location. Path 2: You get on the vehicle
with route 6 at the origin location at 3.6 min later, You get off on node
ID = 16419 at 11.5 min later, You get on the vehicle with route 7 on node
ID = 16419 at 16 min later, You get off on node ID=12488 at 21.1 min later,
You must walk to the destination location. Path 3: You get on the vehicle
with route 2 at the origin location at 5.7 min later, You get off on node
ID = 4355 at 10.2 min later, You get on the vehicle with route 10 on node
ID = 4355 at 11.2 min later, You get off on node ID = 12804 at 19.9 min
later, You must walk to the destination location 
The customer specifies the origin and destination locations and an arbitrary
latest arrival time to the destination. All the hosts acceptable in the spacetime
prism of the customer offer their ride to him.
The service area around the origin and the destination is created. The service area is a region that encompasses all accessible streets lie within specified impedance for example 10 min walking. The algorithm searches all possible pedestrian routes to reach a waiting stop to get ride from there. Finding such a service area is one of the GIS network analysis capabilities. Figure 3 shows all the received offers and the service areas around the origin and the destination locations. The results of the simulated offers for this trip request are shown in Fig. 4 and Table 1.
Now the passenger can decide which path is more suitable to his preference (e.g., less transfer, fare, travel time or walking time) and select it. He may confront to multi criteria in decision making, so that he can use some of the MultiCriteria Decision Analysis (MCDA) methods.
For some passengers, shorter travel times are more important than trip fares.
A rushed pedestrian would prefer a quick trip, while lowbudget passengers favor
cheaper rides. Fewer transfers are more attractive to passengers who appreciate
comfortable trips (Wu et al., 2006).
If the passenger travel by his car along the shortest path from the origin
to the destination, it takes about 13 min. Note, the link’s travel time
attribute is stored in built network dataset as an attribute. The shortest path
is computed based on this attribute using a network analysis capability in GIS.

Fig. 3: 
All the received offers and the service areas around the origin
and the destination with 10 min as maximum walking time 

Fig. 4: 
Illustration of reasonable paths (the bold lines) on a map
with the transfer stops (the stars) 
DISCUSSION
In this modeling framework, it is assumed that every node’s arrival time is known with certainty. Unfortunately, the realistic situations violate this assumption. It would be possible to establish a time interval around mean travel time to bring the possibilities of early and late arrivals. One way to overcome this flaw is to keep into account these intervals during constructing spacetime graph.
Suppose the first car passing node 3 (Fig. 2) arrives at time t_{3} with reliability value in interval (t_{3 }a, t_{3 }+b), the second car passing node 3 arrives at time t’_{3} with reliability value in interval (t’_{3}c, t’_{3}+d). These reliable intervals in the graph framework are considered in order to reduce risk probability of missing booked vehicles for the proposed options in transfer points and provision of reliable transportation options.
When there is no overlapping section between reliability value of the two consecutive timeexpanded nodes of a location (Fig. 5), then virtual arc as waiting duration is constructed in spacetime graph. Therefore, the space time network in Fig. 2 is satisfied.
When there is overlapping section between reliability value of the two consecutive timeexpanded nodes of a location (Fig. 6), then construction virtual arc is dependent on the ratio between the overlapping section and the time difference interval. If this ratio is larger than a threshold value, so the virtual edge between timeexpanded nodes of a location is ignored.
The problem of the paths determination, while minimizes the risk of missing
booked vehicle, is resolved significantly during building alternate solutions
with this policy.

Fig. 5: 
Lack of overlapping section between reliability values 

Fig. 6: 
Existence of overlapping section between reliability values 
CONCLUSIONS
Traffic congestion is perhaps the most conspicuous problem in the transportation
network and has become a crucial issue that needs immediate attention. It is
commonly recognized that establishment of more infrastructure, which is usually
financially and environmentally constrained, is not the only remedy to congestion
(Chabini and Gao, 2006). Travel Demand Management (TDM)
strategies more often are implemented as part of an integrated set of solutions
for regional traffic congestion problems that balance supplyside infrastructure
investments and demandside strategies.
The original concepts of TDM took root in providing alternatives to single
occupancy commuter travel, to save energy, improve air quality and reduce peakperiod
congestion (ACT, 2004). This research is related to one
of TDM strategies, called shared riding. The proposed approach for shared riding
can decreases the number of travel by private transport, whereas attracts passengers
by allowing them to get ride closer to the desired one. On the other hand, it
encourages privatevehicle drivers to share their rides for economic benefits
without making detour for passengers. The shared riding paradigm would contribute
to a more efficient usage of today’s transportation networks, because a
large amount of available transportation supply remains unused (Tessmann,
2006).
In this research, a shared ride constrained path finding is developed. Some
considerations are taken into account as follow:
• 
The problem of finding a reasonable path can be solved based
on the available means of transportation, rather than the street networks,
alone 
• 
The reasonable path can be acquired regarding the passenger’s preference,
rather than time as a cost function, alone 
• 
All the possible pedestrians can reach a ride in the main road from the
origin using a service area 
• 
Incorporating travel time reliability in the framework significantly improves
trip planning reliability 
For quantitative assessment of the shared ride constrained path finding system,
we are defining the quality of the service perceived by the passenger as the
ratio between the service time offered by the system and the time the passenger
would need to travel by his own car (Colorni and Righini,
2001), we are comparing the results for the same request in the different
time instances with different number of offers, which will be presented in the
future work.
The future research is to use all the possible pedestrian paths everywhere
in the network, rather than pedestrian paths around the origin and destination.
To make the generated path more practical in the real world, the developed algorithm
must be based on a bimodal (by car and on foot) travel network. This makes the
research more challenging because it causes a fundamental topological change
to the network and significantly increases the complexity of the network (Wu
and Hartley, 2004).
The effectiveness and competitiveness of such a system significantly depends on communication and information technology used. Recent developments in the two fields incorporate travelers into shared ride arrangements more effective by providing realtime, accurate information on travel options and traffic conditions.