Subscribe Now Subscribe Today
Research Article
 

Development of a Shared Ride Constrained Path Finding System



M. Teimouri, M.R. Delavar and M.R. Malek
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

This study introduces a novel idea of shared riding constrained path finding developed using a geospatial information system. The idea is to use more efficiently the available (volunteering to pick up passenger) vehicles with free capacity on the street network. The travel path of available means on the street network formed a time-dependent network called transportation network. The space-time network concept utilized in this study in order to abstract the transportation network. The chronological-shortest path tree algorithm with the proposed modifications presents all reasonable shared ride constrained paths on the kind of transportation network. The paths may not coincide with the shortest path of origin to destination locations based on the street network. The traveler’s origin and destination locations with arbitrary latest arrival time provide the input of the algorithm. The algorithm results provide the paths with the in-vehicle time, walking time, waiting time and length of each path as the fare with passenger. Then, passenger can select the best trip regarding his preferences. Finally, improving the proposed solution with incorporating travel time reliability through the model description as a possible extension is discussed.

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

 
  How to cite this article:

M. Teimouri, M.R. Delavar and M.R. Malek, 2009. Development of a Shared Ride Constrained Path Finding System. Journal of Applied Sciences, 9: 2228-2237.

DOI: 10.3923/jas.2009.2228.2237

URL: https://scialert.net/abstract/?doi=jas.2009.2228.2237
 

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 door-to-door 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 traveler-centered 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 traveler-centered 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 traveler-centered 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, location-sensing technology and ubiquitous wireless networks in a single device enable new types of social behavior such as ad-hoc meetings of people in co-located geographical space (Nittel et al., 2007). Advances in technology allow envisioning a novel shared-ride 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 ad-hoc manner, without the help of an external infrastructure, is accomplished by local negotiation between these agents via radio-based 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 shared-ride 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 shortest-path algorithm, before communication starts. The request is then transmitted to nearby network nodes and rebroadcasted further in a peer-to-peer 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 peer-to-peer 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, non-deterministic transportation network. The global optimal trip can be determined in a non-deterministic 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 in-vehicle 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 above-mentioned questions.

The crucial concept utilized in this study is a space-time 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 space-time network and Chrono-SPT 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 Origin-Destination (O-D) 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 O-D 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 O-D 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 on-time 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 Chrono-SPT 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 real-time. 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 re-optimization 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, time-varying network characteristics are known at all times. The Time-Dependent 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 time-varying 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 shared-ride 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 dij (t) is associated with each arc (I, j) with the following meaning: if t is the (non-negative) leaving time from node I, then t+ dij(t) is the arrival time at node j. In addition to the delay, a time-dependent cost cij(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 wi(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 = {t1, t2,… , tq}, so that t+dij (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 space-time network R = (V, E) consists of time-expanded nodes (I, t) ∈ NxT. R is then formally defined as:

(1)

(2)

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: (ih, ih+1) represents waiting at I from th to th+1 and is given the unit time cost wi(th), 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 t1, then the ones for t2 and so on. The resulting algorithmic paradigm is called Chrono-SPT. The paradigm uses a bucket list B = {B1, B2,…,Bq} (Dial, 1969) in order to efficiently perform the selection operation, i.e., for implementing the chronological visit of R, where, Bh denotes the bucket containing the nodes to be visited at the time instant th, h = 1, …, q. In this notation, Pi(t) indicates the current predecessor of node I at time t, i.e. it, while Ci (t) denoted the label associated with it.

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. Bh denotes the current bucket used for the node selection (Pallottino and Scutella, 1998).

Fig. 1: The typical iteration for Chrono-SPT (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 space-time 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 non-decreasing values of time index associated with the nodes of R, provides a topological visit of R (Pallottino and Scutella, 1998).

As mentioned earlier, Chrono-SPT 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 O-D pair only, however, knowing all feasible paths between an O-D 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 Chrono-SPT. 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 Chrono-SPT 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 space-time 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 Multi-Criteria 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 low-budget 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 space-time graph.

Suppose the first car passing node 3 (Fig. 2) arrives at time t3 with reliability value in interval (t3 -a, t3 +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 time-expanded nodes of a location (Fig. 5), then virtual arc as waiting duration is constructed in space-time graph. Therefore, the space time network in Fig. 2 is satisfied.

When there is overlapping section between reliability value of the two consecutive time-expanded 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 time-expanded 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 supply-side infrastructure investments and demand-side strategies.

The original concepts of TDM took root in providing alternatives to single occupancy commuter travel, to save energy, improve air quality and reduce peak-period 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 private-vehicle 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 real-time, accurate information on travel options and traffic conditions.

REFERENCES
1:  ACT, 2004. The role of demand-side strategies: Mitigating traffic congestion. Association for Commuter Transportation, for the Federal Highway Administration. http://tmi.cob.fsu.edu/act/FHWA_Cong_Mitigation_11%202%2004.pdf.

2:  Bellman, R., 1958. On a routing problem. Q. Applied Math., 16: 87-90.

3:  Castelli, L., L. Coslovich, W. Ukovich and R. Pesenti, 2002. Improving techniques for an on-line dial-a-ride problem with time windows and capacity constraints. Proceedings of the 9th Meeting of the Euro Working Group Transportation, June 10-13, 2002, Bari, Italy, pp: 498-502.

4:  Chabini, I. and S. Gao, 2006. Optimal routing policy problems in stochastic time-dependent networks. Transport. Res. Part B, 40: 93-122.
CrossRef  |  Direct Link  |  

5:  Colorni, A. and G. Righini, 2001. Modeling and optimizing dynamic dial-a-ride problems. Int. Trans. Operat. Res., 8: 155-166.
CrossRef  |  Direct Link  |  

6:  Dial, R.B., 1969. Algorithm 360: Shortest path forest with topological ordering. Commun. ACM, 12: 632-633.
CrossRef  |  Direct Link  |  

7:  Dean, B., 1999. Continuous-time dynamic shortest path algorithms. Master Thesis. Massachusetts Institute of Technology, Cambridge.

8:  Dean, B., 2004. Algorithms for minimum-cost paths in time-dependent networks with waiting policies. Networks, 44: 41-46.
CrossRef  |  Direct Link  |  

9:  Dean, B., 2004. Shortest paths in FIFO Time-Dependent Networks: Theory and Algorithms, Technical Report. MIT, Cambridge, MA.

10:  Dijkstra, E.W., 1959. A note on two problems in connexion with graphs. Numerische Mathematik, 1: 269-271.
CrossRef  |  Direct Link  |  

11:  Dreyfus, S.E., 1969. An appraisal of some shortest path algorithm. Operat. Res., 17: 395-412.
CrossRef  |  Direct Link  |  

12:  Gaisbauer, C., 2007. Route-Choice Strategies for Shared-Ride Trip Planning in Geosensor-Networks. In: Buchreihe Geoinfo Series, Buchreihen, H. and A. Frank (Eds.). Institute for Geoinformation and Cartography, Vienna, ISBN: 978-3-901716-37-9.

13:  Guan, L.J. and S. Winter, 2006. Trip Quality in an Ad-Hoc Shared-Ride System. In: Geographic Information Science, Raubal, M. et al. (Eds.). IfGI Prints, Institute for Geoinformatics, University of Münster, Münster, Germany, ISBN: 3-936616-25-6, pp: 273-276.

14:  Nittel, S., S. Winter, A. Nural and C. Trang, 2007. Shared Ride Trip Planning with Geosensor Networks. In: Societies and Cities in the Age of Instant Access, Miller, H.J. (Ed.). Springer, Berlin, ISBN: 978-1-4020-5426-6, pp: 179-194.

15:  Pallottino, S. and M.G. Scutellà, 1998. Shortest Path Algorithms in Transportation Models: Classical and Innovative Aspects. In: Equilibrium and Advanced Transportation Modelling, Marcotte, P. and S. Nguyen (Eds.). Kluwer Academic Publishers, Boston, MA., ISBN: 978-0-7923-8162-4, pp: 245-281.

16:  Peytchev, E. and J. Coggan, 1999. See before you go. Traffic Technology International, December 1999/Jan 2000 Issue, pp: 69-72.

17:  Raubal, M., S. Winter, S. Tessmann and C. Gaisbauer, 2007. Time geography for ad-hoc shared-ride trip planning in mobile geosensor networks. Int. Soc. Photogrammetry Remote Sensin (ISPRS), 62: 366-381.
CrossRef  |  Direct Link  |  

18:  Tan, M.C., C.O. Tong and J.M. Xu, 2004. Study and implementation of a decision support system for urban mass transit service planning. J. Inform. Technol. Manage., 15: 14-32.
Direct Link  |  

19:  Teimouri, M., M.R. Delavar and M.R. Malek, 2008. The shared ride strategy for mitigating traffic congestion. Proceedings of 7th Annual International Conference and Exhibition on Geographic Information Technology and Application, Kuala Lampur, Malaysia.

20:  Teimouri, M., M.R. Delavar and M.R. Malek, 2008. Time dependent shortest path for shared ride trip planning. Proceedings of the International Symposium on Geoinformation, October 13-15, 2008, Kuala Lampur, Malaysia, pp: 8-.

21:  Tessmann, S., 2006. Time geography for efficient shared-ride trip planning in transportation networks. Diploma Thesis. Institute for Geoinformatics, University of Münster, Germany.

22:  Winter, S. and S. Nittel, 2006. Ad-hoc shared-ride trip planning by mobile geosensor networks. Int. J. Geographical Inform. Sci., 20: 899-916.
CrossRef  |  Direct Link  |  

23:  Winter, S., S. Nittel, A. Nural and T. Cao, 2005. Shared ride trips in large transportation networks. Miller, H.J. (Ed.). Proceedings of the International Symposium on Societies and Cities in the Age of Instant Access, November 10-12, 2005, Salt Lake City, pp: 1-12.

24:  Winter, S. and M. Raubal, 2006. Time geography for ad-hoc shared-ride trip planning. Aberer, K., T. Hara and A. Joshi (Eds.). Proceedings of the 7th International Conference on Mobile Data Management, May 10-12, 2006, IEEE Computer Society, Nara, Japan, pp: 6-.

25:  Wu, Q. and J. Hartley, 2004. Accommodating user preferences in the optimization of public transport travel. Int. J. Simulat., 5: 12-25.

26:  Wu, Y.H., L.J. Guan and S. Winter, 2006. Types of agents in peer-to-peer shared ride systems. Nittel, S., A. Stefanidis and A. Labrinidis (Eds.). Proceedings of the 2nd International Conference on Geosensor Networks, October 1-3, 2006, Boston, MA., pp: 27-38.

27:  Wu, Y.H., L.J. Guan and S. Winter, 2008. Peer-to-Peer Shared Ride Systems. In: Advances in Geosensor Networks, Lecture Notes in Computer Science, Nittel, S., A. Labrinidis and A. Stefanidis (Eds.). Springer, Berlin, ISBN: 978-3-540-79995-5.

©  2021 Science Alert. All Rights Reserved