|
Route Guidance: State of the Art vs. State of the Practice |
|
William Herbert, Fatma Mili |
Abstract— Route guidance is an essential component of intelligent
transportation systems and a necessary ingredient to any automatic piloting
system. Looking at the literature on Route Guidance, one can quickly see a
chasm in how the problem is seen in the academic community and how it is seen
in the automotive, industrial world. There seems to be different levels of
interest in this problem and divergent assessment of its level of difficulty
and the nature of challenges that are inhibiting its becoming a reality. In
this paper, we examine the literature in the field, identify the prerequisites
for a viable implementation of Route Guidance, and examine the state of development
of each of these pre-requisites.
I.
Introduction
|
R |
oute guidance systems refer to all driver decision aids used before a trip to select a route, a travel starting time, and possibly decide whether or not to undertake the trip, as well as those used during the trip to adjust the route as needed in light of unforeseen events. Route guidance is a sub-component of Driver Assistance Systems, which is in turn a component of Intelligent Transportation Systems (ITS) as defined by the U.S. Department of Transportation [1] [2]. ITS is a technology aimed at improving traffic safety and mobility and enhancing productivity through a broad range of advanced information and communications technologies. DOT identifies Route guidance systems as a major component of ITS. In addition to Route Guidance, which is concerned with decisions at intersection points (as well as entry and exit points on a highway), Driver assistance Systems encompass a variety of other smaller grain decision aids such as lane keeping, Object Detection, and Intelligent Speed Control. Other capabilities within ITS, at the same level as Driver Assistance Systems include Arterial, Freeway, and Transit Management Systems, Incident Management Systems, and Electronic Payment Systems, to mention just a few.The technologies developed under ITS have the dual goal of enhancing existing modes of transportation as well as paving the road for future modes, such as fully automated driving. Route guidance is a key ingredient to automatic driving. In addition, it has been shown through some studies to have a potentially dramatic impact on safety [4], mobility [5], capacity throughput [4], and customer satisfaction [6]. Yet, many questions remain about the mechanics and the effectiveness of this guidance. For example, a 2001 simulation-based study for drivers in Toronto, Canada, showed that Route Guidance improved travel time and capacity throughput starting from a market penetration of 15%, but also an increase in accident rates when market penetration exceeded 60% [7].
Because of its potential, and in response to advances in technology, there has been a flurry of interest in research and development in ITS. The developments in wireless communications and their increasing presence onboard vehicles, as well as raised expectations from drivers in terms of the variety and the quality of services that they expect onboard their vehicles pave the way for further developments. Whereas the level of penetration of the technology seems to be largely economically driven (more predominant in wealthier countries) the level of expectation and the openness towards these services seem to be in part culturally driven, with significant differences between Asia, Europe, and North America (e.g., see [29] for a comparative study of US, France, Germany, and Japan).
At a first glance, Route Guidance may seem to be one of the easiest of ITS technologies, and thus, one would expect it to have become a standard feature available on all vehicles and demanded by all drivers. Yet, this is far from being the case. This paper is an attempt to understand the challenges to a full materialization of this technology. The impetus behind this investigation is the observed divergence between the way the Route Guidance Problem seems to be portrayed in “academic” circles, basically as a solved problem, and the way in which it is seen in industry, as a problem for which existing published solutions either do not scale up, make unrealistic assumptions or lack the cost/benefit structure necessary for success as a commercial product.
This paper is organized as follows: In section II, we discuss the motivation and need for route guidance and provide a classification of route guidance approaches. In sections III, IV and V we discuss respectively the computational, human factor and economic challenges to a widespread deployment of Route Guidance. Section VI presents conclusions and future directions.
II.
Classification of
Route Guidance Approaches
Route guidance systems are a type of Traveler Information System (TIS) that provide traffic information and travel recommendations to drivers to help them make better travel decisions. By influencing driver decisions, these systems affect transportation demand. A closely related advanced technology is Traffic Management Systems (TMS) which control and impose constraints on traffic. These systems control transportation supply. The technologies differ in the sense that drivers are obligated to comply with TMS processes and rules but are not required to accept or follow TIS/route guidance recommendations. However, the two systems are similar in that they use some of the same mechanisms and processes to perform overlapping functions such as determining network traffic flow and congestion and identifying optimum routes.
A. Descriptive and Prescriptive Guidance
Route guidance can be divided into two major categories of guidance: Descriptive Guidance which provides information on traffic and road conditions with no routing advice, and Prescriptive Guidance which provides routing advice but no information on traffic network conditions. In some implementations, descriptive and prescriptive system elements are combined. A variable message sign that provides drivers with current estimates of driving time to an upcoming highway intersection is an example descriptive guidance while an online mapping and driving direction system is an example of prescriptive guidance. Guidance can also be categorized by when the guidance is provided: either pre-trip as with online driving directions or en route as with variable traffic signs.
B. Static and Dynamic Guidance
A key distinction among route guidance systems involves the type of data used. Static guidance systems are based on historical data that may reflect traffic patterns over some time period of interest, but does not reflect current conditions in the network. Dynamic guidance systems use real-time data to develop guidance based on current conditions in the network that drivers are likely to experience when following guidance. Dynamic guidance can be further subdivided into two major types: discrete and continuous. In discrete dynamic networks time is modeled as a set of integers (such that each travel time interval is associated with a fixed travel cost). In continuous networks time is treated as real numbers. A key challenge in dynamic route guidance is the difficulty and cost of obtaining accurate estimates of traffic in the network; this is especially the case when the timeframe we are interested in route guidance is in the future (such guidance is referred to as anticipatory route guidance). As a result, any traffic estimate is bound to be an approximation. The tradeoff then is in obtaining an approximation in a cost-effective manner.
There are two complementary
approaches to addressing this inherent uncertainty related to traffic:
v Reactive Systems: The uncertainty related to the future is overcome by shortening the time horizon of the route guidance. Data is monitored and collected in real-time about upcoming segments on a route and used to modify previous predictions. Reactive behavior tends to lead towards a greedy approach whereby decisions make local optimizations based on short-range time frames.
v Predictive Models: Models of various levels of complexity are created using historical data collected over long periods of time and further complemented with real time data. The complexity and level of accuracy of these models varies with the nature and grain size of the data they use, among other things.
The data used in the reactive approach is collected either from road-side traffic monitoring equipment or from mobile vehicular networks (VANETS) in which vehicles exchange recent traffic experience with other vehicles in their transmission range. These decentralized approaches are able to react to unplanned events. Farver [13] observes that reactive systems can be useful when predictive systems are unavailable or provide poor results. The predictive approach usually involves large centralized databases of historical traffic data about the entire traffic network. Bottom [15,16] has found that predictive, centralized systems provide high quality guidance when accurate data is used. However, when these systems make their predictions on historical data alone, they are unable to react to unplanned events such as congestion caused by traffic accidents or emergency road repairs.
The reactive and the predictive approaches are not exclusive of each other. Reactive systems can be made to react to events relevant to future decision points (rather than to the immediate decisions alone), and predictive systems can use dynamic, real-time data in addition to historical data. Such approaches are qualified as hybrid; they have been shown to achieve the advantages of both types of systems [13]; they provide globally optimal routes using predictive traffic models and maintain the optimality of these routes by reacting quickly to unforeseen events. When hybrid systems use real-time data concerning future decision points and adjust their recommendations based on what they anticipate the traffic to be, they are called anticipatory.
C. Consistent Route Guidance and the CARG Problem
Any method for generating anticipatory route guidance must address the following important problem: anticipatory guidance involves predictions of future conditions, but those conditions will themselves be affected by driver’s reactions to the guidance received. There is a risk that the number of drivers changing their behavior in response to predicted guidance information is so high that the predicted traffic conditions become invalid. Critten [19] calls this phenomenon overreaction. Route recommendations that account for this phenomenon and incorporate it in their predictions are said to be consistent. Guidance is said to be consistent when any forecast on which the guidance is based is the same as the outcome that results when drivers follow the guidance.
D. System Optimal and User Optimal Guidance
Route guidance can be provided to selected drivers that are equipped to receive it, or it can be made available to all drivers in the traffic network. This distinction leads to a further classification of route guidance in terms of interest served.
v System Optimal guidance aims at improving travel conditions for the entire network. In this scenario, some drivers might be routed to suboptimal routes in order to balance and improve overall network flow. System optimal approaches are usually categorized as traffic management systems rather than guidance systems. While users might not be inclined to accept suboptimal route guidance, they are obliged to follow such routing if provided by traffic management system because compliance is compulsory.
v User Optimal guidance aims at optimizing the route of individual drivers (i.e. those equipped and enabled to receive it) without concern for the network as a whole.
III. computational challenges
In this section we review the spectrum of solutions published to the route guidance problem in order to better understand the claim that these solutions are based on unrealistic assumptions, and that they do not scale up. We examine these solutions by starting from the most simplified view (Route Guidance as a shortest path problem), to the most comprehensive and complex (anticipatory route guidance). For each of these solutions, we assess
v Their assumptions,
v Their scalability,
v Their usefulness.
There are many characteristics of a trip that can be considered in defining an optimum route. Among these are: shortest distance, shortest travel time, minimum number of traffic signals and the route with the least amount of freeway driving. Finding the optimal path when the parameter being optimized does not change (e.g. distance, nature of the road) is relatively easy. We thus focus on the more common, and more challenging case of optimizing travel time.
A. Optimal Route Problem
Traditionally, the problem of finding the optimal path is modeled as a shortest path on a directed graph as follows:
Given a labeled directed graph G defined as follows:
V: {v1, v2 …vn} the set of vertices represents the set of decision points on the map of interest. These decision points can be intersections or highway entry and exit points.
E: the set of edges is a set of pairs (vi, vj) representing a segment of the road between two adjacent decision points. The graph is directed to account for one-way streets and divided roads/freeways.
C: the cost function is a function EàR+ associating a cost with each edge.
Given two distinguished vertices a source s and a destination d, we define the optimal route p(s,d) as the path in G from s to d with the minimal cost.
When G is connected and the cost of interest, C, is the distance or some other static parameter such as the number of traffic signals or highway distance, then the Optimal Route Problem can be formulated and solved efficiently to find the optimal route using one of the well-established shortest path algorithms.
Applications of this type, such as Mapquest, are typically accessed by online users to generate maps and driving directions on the fly. These applications are widely used, with Mapquest [9] alone providing more than 10 million sets of driving instructions and maps each day. Despite these large transaction volumes, system response time is very low.
An important factor in assessing the effectiveness of a route guidance algorithm is its scalability or growth rate. This is particularly important in route guidance where traffic networks can involve very large numbers of nodes and links, and guidance algorithms are often run repeatedly in real time for guidance updates during a trip. Mapquest employs the Dijkstra [8] algorithm which computes a one-to-all (i.e. from a single vertex to all other vertices) shortest path at a single instant in time. Mapquest uses Dijkstra in a bi-directional search, working backward from both the starting and ending points at the same time. Dijkstra is in O(|V|2) where |V| is the number of vertices in the network. However, for sparse graphs (i.e. with many fewer than |V|2 edges), Dijkstra can be implemented to run in O(|E| log(|V|)), where |E| is the number of edges. A typical urban transportation network, such as the city of Boston [11] with 25,000 links and 7,000 nodes, constitutes a sparse graph. For such a network, |V|2 would be 4.9 107 whereas |E| log(|V|) is “only” 4.2 105. To further reduce the computational cost, hierarchical maps are often employed. These maps are constructed with coarse granularity, grouping large numbers of vertices into a few regions. Since street level resolution is only addressed near the origin and destination, the task of creating guidance greatly simplified, and scaling is improved.
Because mapping and driving direction systems employ static cartography and map databases, they are unable to provide real time information on the status of the traffic network. These systems are able to provide estimates of driving time, however this information is usually based on posted speed limits and does not take into account the status of the traffic network as time varies. Because they are unable to reflect time-dependent changes in the network, these systems are used primarily for pre-trip planning and not within-trip guidance.
B. Traffic-Dependent Optimal Route Problem
For many parameters of interest, such as travel time, a travel cost function cannot be formulated simply as a function C: EàR+. Instead, travel time on a given edge is a function, not of the edge alone, but also on the amount of traffic as measured by the number of vehicles on that edge, in other words, the cost function is C: ExT à R+. The traffic-dependent optimal route problem is no more complex than the original optimal route problem, provided T is available and accurate, and congestion in the network does not prevent the required additional routing. Thus, the traffic-dependent problem is defined as:
Given a labeled directed graph G defined as follows:
V: {v1, v2 …vn} the set of vertices, and
E: the set of edges (vi, vj) are defined as in problem 1
T: the amount of traffic on each of the segments is a function EàR+
C: the cost function is function ExTàR+ associating a cost with each edge in a continuous dynamic network (or ExTàN+ in a discrete dynamic network).
Given two distinguished vertices: a source s and a destination d, we define the optimal route p(s,d) as the path in G from s to d with the minimal cost. p(s,d) constitutes guidance instructions for traveling from s to d.
While a fastest path solution based on dynamic data is a significant improvement to a static solution, it has little practical value if the resulting route guidance is restricted to the present time only. Rather than implement such narrow solutions, researchers moved to the following more general problem of using current knowledge of the traffic network to project guidance for future time periods.
C. Predictive Route Guidance
The traffic dependent optimal route problem and its solution assume that the traffic conditions are known ahead of time. In practice, what is available is:
v An estimate of traffic at the time of interest based on historical data, and
v The current state of the traffic.
To the extent that the current state of the traffic is consistent with historical patterns, the solution presented above is bound to also be accurate. But, in those cases where non-routine traffic events occur, the current event of the traffic, when projected on the future would give a more accurate solution than the traffic-dependent presented above. Predictive route guidance differs from traffic-dependent guidance in the definition and computation of the traffic component. The function T that associates traffic to route segments over time needs to be estimated based on historical data and on real time reports on traffic.
Given a labeled directed graph G defined as follows:
V: {v1, v2 …vn} the set of vertices, and
E: the set of edges (vi, vj) are defined as in problem 1
Th: the amount of traffic on each of the segments is a function EàR+ based on historical data.
Tp: the amount of traffic on each of the segments measured in the present.
T: the amount of traffic on each of the segments at the time it will be traversed. T is the predicted time computed from the combination of Th and Tp .
C: the cost function is function ExTàR+ associating a cost with each edge in a continuous dynamic network (or ExTàN+ in a discrete dynamic network).
Given two distinguished vertices: a source s and a destination d, we define the optimal route p(s,d) as the path in G from s to d with the minimal cost. P(s,d) constitutes guidance instructions for traveling from s to d.
The predictive problem differs from the dynamic problem only by the way in which traffic is computed. Thus we only need a solution to the computation of T from Th and Tp. Chabini [11] has proposed an all-to-one (i.e. shortest paths from all nodes to one destination node for all departure times) discrete dynamic shortest path algorithm, named the Decreasing Order of Time (DOT) algorithm. Chabini [11] has tested DOT and claims it to be the most efficient algorithm solution possible.
In order to discuss the DOT formulation, we further define G as follows:
C: the set of link-dependent travel times where
C = {cij(t)|(i,j) 
E}, and
cij(t) is a discrete and time-dependent function that has integer-value domain and range and takes a static value after a finite number of time intervals M.
If we define πi(t) as the fastest travel time to destination d from departing node i at time t, the minimum travel times are defined as:
min
v(j)
E(v(i))cij(t) + πi(t + cij(t)) ; i
j
πi(t) =
0 ; i = j
The DOT algorithm as presented by Chabini[11] runs in Θ (SSP + |V|*I + |E|*I) where I the number of time intervals. SSP is the optimal running time of a valid static shortest paths procedure. If we assume the procedure is Dijkstra, DOT is in Θ (|E| log(|V|) + |V|*I + |E|*I). As with the Dijkstra algorithm, the DOT algorithm is also quasi-linear. This, combined with the use of hierarchical maps, makes the algorithm’s performance not an issue for scalability. Furthermore, Chabini [11] compares DOT performance to three other established label-correcting, all-to-one fastest path algorithms. Those tests suggest that DOT significantly outperforms all other algorithms for a range of |V|, |E| and I values. Although DOT is one of the more recently developed (1997) dynamic shortest path algorithms, it is more than 10 years old. Neither DOT nor any of the other well known dynamic shortest path algorithms, such as A*[24] are known to have been deployed for use in automotive transportation networks and have been tested primarily in simulation.
D. Consistent Anticipatory Route Guidance (CARG) Problem
Based on the above discussion, given a source s, a destination d, and a time t, we can find an optimum path p1 in graph G. Yet, if G were to represent a real-world traffic network involving thousands of drivers per day with the same source and destination, all of whom were routed to p1 instead of other options, congestion will occur on p1, making it far from being the optimal path, and leaving alternate routes underutilized. This problem highlights one of the major challenges of route guidance: ensuring that guidance, when followed, actually produces travel improvements for vehicles that receive it. Traffic congestion can be defined as the condition of a traffic network when the traffic demand exceeds the capacity of the network. The Transportation Research Board’s Highway Capacity Manual [10] identifies traffic congestion in terms of six Levels Of Service (LOS) ranging from level A, the best travel conditions (i.e. free flow) in which individual vehicles are virtually unaffected by other vehicles in the traffic flow, to level F, the worst conditions, characterized by stop and go traffic and poor travel time. The volume of traffic on a road segment at LOS A or B could be doubled or tripled with minimal affect on speed and travel time. However, at LOS E or F, the addition of just a few vehicles could cause a traffic jam. Overall, traffic congestion is nonlinear and the application of route guidance can have varying effects based upon the state (i.e. LOS) of the road segment to which the guidance is applied. A road segment identified as an optimal route can absorb additional traffic routed to it if it has a low LOS but will experience congestion if its LOS is high.
Any method for generating anticipatory route guidance must address the following important issue: anticipatory guidance involves predictions of future conditions, but those conditions will themselves be affected by driver’s reactions to the guidance received. Clearly, the potential for overreaction becomes greater at high LOS. In most cases, a road segment with high LOS is not likely to be part of the optimal path. However, at high penetration levels, a segment selected as part of the optimal path, because of its low LOS, may turn into a high LOS, and thus become sub-optimal. At high penetration and LOS levels, it is difficult for guidance to produce positive results. In such cases, the network is described as being in a state of “user equilibrium” where no driver is able to change to a better path.
Bottom notes that randomness is a significant component of congestion. He quotes Lindley’s [17] estimate that roughly 60% of the congestion delays on urban freeways in the U.S. are non-recurrent; instead, they are caused by instances of “random” events such as accidents and vehicle breakdowns.
For the above reasons, the concept of “consistent” route guidance has emerged as a relevant issue in route guidance. The concept of consistency addresses the concern that route guidance can be rendered invalid by the very act of drivers following the guidance In order to address the issue of consistency, we can no longer focus on a single driver and single pair (source, destination). Instead, we need to address the problem globally, for a set of drivers and a set of routes. Thus, given a set of (s,d) pairs, we generate, not a single optimal path, but a set of optimal paths. The following will be part of the Consistent Anticipatory Route Guidance (CARG) Problem.
Given a labeled directed graph G, the CARG problem is defined as follows:
V: {v1, v2 …vn} the set of vertices, and
E: the set of edges (vi, vj) are defined as in problem 1 & 2
T: the time
varying amount of traffic on each of the segments is a function EàR+
C: the cost function is function ExTàR+ associating a cost with each edge in a continuous dynamic network (or ExTàN+ in a discrete dynamic network)
Because of the possibility of overreaction, the generation of an optimal path, p, is only a first step in generating the guidance. Once path p is generated, multiple variations on p will be generated to spread the drivers. Thus, we distinguish between P, the set of optimal paths, and M the set of instructions generated.
P: the set of optimum path flows between <specific/all> <s,d> pairs
M: guidance instructions for travel between all <s,d> pairs.
Bottom [15] and a team of MIT researchers have developed a guidance system called DynaMIT [21] (Dynamic traffic assignment for the Management of Information to Travelers) based on the above described framework. DynaMIT incorporates origin-destination demand estimation and prediction models, a traffic simulation model, and behavioral models that anticipate drivers’ behavior. Data from these discrete dynamic models are fed into an algorithm that integrates the information to predict network conditions and provide guidance to drivers in an iterative fashion. Starting with a computer generated estimate of P, DynaMIT iteratively employs the following functions:
S: a network loading function that maps the altered path flows into a new set of network conditions PàT
GD: A guidance function that maps current network conditions into a set of instructions for travel between all <s,d> pairs TàM
D: A path splitting function that maps Guidance messages into corresponding path flows MàP
Optimum guidance as the set of paths P in G with minimal total cost C such that such that the composite mapping: S o G o D: PàP
After each iteration, the input guidance traversal times are compared with the output traversal times to determine consistency. DynaMIT repeats the process until consistency is satisfactory or the allotted number of iterations has been performed. Bottom [15] concludes that the guidance is consistent if the forecast path flows are the same as the flows initially assumed. An iterative algorithm called the Time Smoothing Algorithm was developed for the solution of the above problem. This algorithm is somewhat based on the Method of Successive Averages (MSA), which is frequently used in stochastic user-equilibrium assignment algorithms.
The problem described in this section applies to both user optimal and system optimal guidance. If the definition of P involves specific <s,d> pairs we are addressing user optimal guidance. However, if P refers to all <s,p> pairs then the problem addresses system optimal guidance. In either case, the behavior of all traffic must be modeled, including unguided traffic in user optimal systems.
As mentioned above, at present, there are no known major implementations of consistent anticipatory route guidance in user-optimal settings. However, several CARG traffic management (i.e. system optimal) systems have been deployed for field testing. MIT has implemented DynaMIT [25] as a traffic management system in the South Park area of Los Angeles in September 2005. This approximately one-square-mile region just south of downtown is plagued with heavy traffic year round. Data from its origin-destination, demand estimation and prediction models, its traffic simulation model and its driver behavior model are fed into an algorithm that integrates the information to predict conditions 30 minutes out and provide alternate routes to drivers. The MIT team claims that DynaMIT does all this in less than five minutes operating on a desktop computer.
No detailed information is yet available regarding DynaMIT performance and run time complexity in the Los Angeles implementation. Such data is needed to determine its effectiveness and scalability in providing anticipatory, consistent guidance under congested traffic conditions. However, the installation of DynaMIT in a very busy traffic network indicates that consistent, anticipatory route guidance is coming of age (at least in a traffic management environment) and is moving from simulation to the real world where a body of data can be accumulated and evaluated.
E. Summary
Great strides have been made in the implementation of static, mapping and driving direction systems. Despite their limitations, these applications have enjoyed great commercial success by efficiently performing a narrowly defined but very important function. However, despite the considerable amount of route guidance research that has been performed, implementations of such systems for public use are still sparse. MIT professor Moshe Ben-Akiva [22] blames this on a lack of focus on coordinated and well-funded intelligent traffic systems. Some in the automobile and transportation industry are unaware level of research that has been performed. Although there is great interest in the topic there is concern that the current state of the art in route guidance does not yet justify its inclusion in the design of commercial vehicles.
In discussing the competing philosophies underlying “individual” (user-optimal) and “collective” (system optimal) route guidance, Muffat [23] charges that different research projects are “developing separately and competing, thus creating confusion and preventing car companies from really choosing one system they could recommend to their customers or postponing investment or support from authorities in order to implement a system.” In his study on vehicle navigation and route guidance technologies, Ygnace [28] observes that it is not unusual for some technical inventions (e.g. the washing machine, the elevator and the camera) to take half a century or longer before emerging into the market with a large scale diffusion. He opines that the field of vehicle navigation may be falling into the “long-term process” considering that early research in the subject dates back to the late 1950’s.
IV.
Human Factor
Challenges
The level of acceptance and perceived value of route guidance by the driving public are a major determinant in the degree to which route guidance technologies are developed and deployed for use in traffic networks. This is particularly true in user optimal systems, where drivers have the option of equipping their vehicles to use guidance and/or subscribing to some type of guidance service. Drivers that do not perceive value in guidance and do not plan to use it will be unlikely to pay additional costs for guidance functionality when they purchase a vehicle or pay for on-going guidance service access.
Watling [14] suggests that unless in-vehicle systems become compulsory, no more than 20 – 30 % of the driver population is likely use such systems. He further suggests, that in order for route guidance to achieve wide acceptance, it should be provided as a public service or as a private operation funded by user’s license fees. Finally, he observes that drivers are unlikely to invest in route guidance equipment unless they believe that it will improve the efficiency of their own journeys, and that governmental units will invest in route guidance only if it benefits the entire driving public. In a 2007 study of driver response to variable message signs (VMS), Erke [26] found that drivers welcomed information about incidents and suggestions for alternative routes and determined that 20% of vehicles changed their route according to the VMS recommendation. In an earlier study (known as the Chicago Study) of driver reaction to the Advanced Driver and Vehicle Advisory Navigation Concept (ADVANCE) in-vehicle dynamic route guidance system, Schofer [27] found that drivers perceived routes provided by ADVANCE to be not particularly good and inferior to their own routes. However, these drivers exhibited a high level of interest in real-time traffic information, particularly information about non-recurring congestion. They appeared to be very interested in blending such real-time information with their own knowledge to plan their own routes.
V.
Economic
Challenges
A key factor in the degree to which route guidance technology continues to grow in importance as an ITS component is the affordability of the technology and the willingness of users to pay to acquire and use it. In the case of system optional implementations, decisions to implement will usually be made by a governmental unit. Such decisions will often be prompted by the need to extend the usability of a traffic network that is nearing capacity. If it is believed that the technology will result in more efficient traffic routing and extended traffic network life, route guidance technology becomes an attractive option since it is likely to be cheaper than building new/additional roadways.
In the case of user optimal systems, where guidance acceptance is optional, decisions to invest in technology development will be made by auto manufacturers and OEMs who believe that customers will purchase and use the products thus developed. In this regard, field trials such as the Chicago project or MIT’s Los Angeles project are very important in providing real-world data as to actual costs for system implementation. The very comprehensive Chicago report indicated that potential user/customers were willing to pay significant prices for guidance features (such as real time traffic information) they deemed important. While there will be infrastructure costs associated with the implementation of both system and user optimal guidance, overall there will be likely be higher costs associated with the latter due to equipment and software required in vehicles. This fact, together with the need for governmental units to find additional roadway capacity may explain why traffic management systems are being developed and implemented more quickly than route guidance systems.
VI.
conclusions
and future directions/needs
It is apparent that ITS researchers have developed a strong analytical understanding of route guidance and its associated problems. However it is also clear that much work remains to be done in the development and testing of algorithms to implement the concepts that have been learned, particularly in the areas of anticipatory guidance involving time-dependent data. Most of the testing to date has been done in simulation, and then often with very small traffic networks. And many of the navigational aids that are currently available to the public involve static databases. Because of this situation, it is often the case that important, emerging technologies, such as autonomous driving vehicles, intended to work in conjunction with anticipatory route guidance, are implemented with the most rudimentary route guidance functionality. For example, in November 2007, the Defense Advanced Research Projects Agency (DARPA) conducted its annual driverless car competition in a mock urban environment for the first time. Although all competing vehicles demonstrated strong capabilities in most automotive robotic systems, and showed the ability to move in traffic and negotiate busy intersections, there was no requirement for the identification and use of efficient routes. When autonomous vehicles are deployed for public use, they must be able to produce guidance that drivers perceive to be as good or better than the routes they would choose on their own. This situation points out the need for more aggressive pursuit of practical solutions to basic anticipatory route guidance problems that can be implemented within reasonably short time frames and tested through use in the public domain. It also suggests a need to more efficiently utilize research resources. For example, there is great interest and considerable published research devoted to finding consistent solutions to the CARG problem. However, considering the time that may be required for a significant number of drivers to become equipped to receive guidance, and the low upper limit of such drivers as predicted by researchers such as Watling [14], there could be many years before any serious consequences of the CARG problem are felt in most traffic networks. And considering the high computational overhead associated with some forms of consistent guidance (e.g. fixed point formulations), it may be beneficial, at this time, to channel more research energy into basic anticipatory guidance solutions. This will make needed guidance technology more quickly available to the public and create a knowledge base that will expedite solutions to future problems.
REFERENCES
1. U.S. Department of Transportation, National Intelligent Transportation System Architecture, ver. 6.0, 2007 http://www.iteris.com/itsarch.
2.
U.S.
Department of Transportation, Intelligent Transportation Systems,
http://www.its.dot.gov/its_overview.htm.
3. U.S. Department of Transportation, National Intelligent Transportation System Benefits, Costs and Lessons Learned: 2005 Update.
5. Transport Sector of the Telematics Applications Programme, 4th Framework Programme for RTD&D 1994-1998, Website http://www.cordis.lu/telematics/tap_transport/research/10.html. Last accessed 29 Oct. 2004.
9. Robinson, S., Mapping Magic, Society for Industrial and Applied Mathematics, http://www.siam.org/news/news.php?id=255, 2004.
10. Transportation Research Board, Highway Capacity Manual, 2000.
20. Wunderlich, K., Kaufman. D., Smith, R., Link Travel Time Prediction for Decentralized Route Guidance Architectures, University of Michigan ITS Research Center, 2000
22. http://web.mit.edu/its/pressclips.html.
24. Husdal, J., Fastest Path Problems in dynamic transport networks, http://www.husdal.com/blog/2000/06/fastest-path-pr.html.
25. Dynamic traffic model traverses L.A. freeways, http://cee.mit.edu/index.pl?id=22180&isa=Category&op=show .