| GISdevelopment.net ---> GITA 1998 ---> SCADA and Real-Time Systems |
A GIS Approach to Dynamic Network Routing
Chan C. Chen
Department of Civil and Environmentrd Engineering
University of Wisconsin-Madison
1415 Engineer Drive, Room 1205
Madison, WI 53706
Chan C. Chen
Department of Civil and Environmentrd Engineering
University of Wisconsin-Madison
1415 Engineer Drive, Room 1205
Madison, WI 53706
Introductions
Recently, in transportation and GIS researches, the applications of Intelligent Transportation System (ITS) technologies have been seen as one of high potential directions to solve the problems of continuously degraded performance of transportation systems. By utilizing computers, communication and data processing technologies, the main goal of ITS is to improve the overall performance of transportation systems without building new highways.
ITS key programs cover a wide range of market areas that includes smart trrdlic control systems, emergency response systems, transit management systems, incident management systems, and traveler information systems. For these programs to succeed, the design models in ITS/GIS must simulate the real-world circumstances and must reflect reality. For the same reason, the embedded algorithm in each model of a real-time routing system has to function properly to MtIll user’s requests in terms of response time and information accuracy.
The trends of having reaJ-time in-vehicle navigation system on each car become much clear recently. For example, Mercedes Benz invests one billion dollars to design a Daimiler-Benz’s concept car in which the driver not only can send /receive e-mail and surf the world wide web, but can also receive real-time trrdlic information delivered from Traffic Operation Centers (TOC) (ITS World 1997). To offer more work productivity tools, convenience, safety and entertainment to millions of commuters who spend hours each day cruising the roads or stuck in traflic, at Comdex Fall 1997, IBM, Delco Electronics, NetsCape Communications and Sun Microsystems announced a technology that will utilize existing hardware and software technology -- including voice recognition, wireless communications, global positioning via satellite, head-up displays, Java technology, microprocessors, Web access and collaboration. and other Internet/intranet features -- to create a “Network Vehicle. ”
However, there are MTiculties that exist in applying GIS to this booming market. This paper will investigate the bottlenecks of applying current GIS technology in real-time vehicles routing, and thereafter, propose a conceptual model in GIS to represent and integrate data from various sources with dynamic traflic assignment theory from which accurate real-time or near real-time best route prediction result can be provided to driver for decision making.
System Characteristics
Unlike conventionalGIS applications,only points and linear objectsare consideredin real-time routing problem. Additionally,someof the attributes associatedwith point and linear objectsarea fiction of time; hence,the data model in GIS must be able to handle both spatial and temporal information. For example, as depicted in Figure 1, linear objects (e.g., street networks) and point objects (e.g., fixed objects such as detectors, and moving objects such as probe vehicles) must be relatable for spatial and temporal analysis. Dynamic attributes of dynamic point objects (e.g., vehicle speed) and linear objects (e.g., traffic volume) can be collected in real-time and telemetered to TOC. These dynamic attributes must be integrated with static attributes of linear objects such as number of lanes, directional constraints, and link capacity. That data then serves as input to models derived tlom traffic flow theory and dynamic network models to produce new information such as travel time or travel cost, which are subsequently assigned to the linear objects as attributes. The methodology for integration of this data and models needs to be carefully developed so that predicted travel times reflect the reality of tic conditions.
Figure 1: Trafiic Data Required for Real-Time Routing
Detectors are installed along the highway, major arterial, and intersections to collect real-time data, or so-called “dynamic” data, such as flow rate, travel speed, and trailic volume. The ADVANCE (Advanced Driver and Vehicle Advisory Navigation Concept) project had used probe vehicles mounted with expensive sensing and telemetering systems to report traft3c data, especially congestion situations, back to TOCS so that overall tratlic conditions in study areas can be analyzed simultaneously (Bowcott et al. 1993). Besides real-time tratlic data Kaysi et al. (1993) suggest that historical data or statistical data can also be used to improve the prediction accuracy of future traffic conditions which, thereafter, will assist drivers in providing more realistic route choices.
Procedures for integrating data from various sources are critical to the solution of congestion prediction and dynamic network problems. Such procedures result in “data fusion” -- one of the most important data sources as input to the dynamic traffic assignment model. Because of sparse distribution of probe vehicles, loop detectors and closed-circuit television, real-time data collected by these means are not sticient to give accurate predictions of traffic flow over five- to ten-minute time horizons. Historical origin-destination data and infrastructure data such as signal timing at intersections, number of lanes, and speed limits, are also important for real-time transportation applications. Currently, approaches proposed for data fhsion are by means of fuzzy logic and neural networks (Ivan et al. 1995).
However, even if the required data are available, models for capturing, representing and processing these data must be carefully designed to fidfill the response-time constraint of a real-time system. In his doctoral dissertation, Ziliaskopoulos (1995) proposed time-dependent optimal path algorithms in a multidimensional network model that responds to queries submitted by ditTerent user groups at various times of a day. He demonstrated that huge amounts of computing power are needed to satisfy general requests submitted by users.
Difficulties
Bottlenecks exit in several aspects for current GIS to be filly utilized for dynamic routing purpose. To process temporal related information collected by detectors from highway, the data model in GIS must be redesigned. Although several temporal GIS data models have been proposed (Armstrong 1988, Langran et al. 1988, Worboys 1994), none of them is specially designed to capture and process real-time traffic information. Means for data representation, data integration, and information delivery are also important modules that must to be modeled carefully so that the whole system integrates seamlessly to provide accurate near real-time information to travelers (Chen et al, 1997).
To predict travel time/travel cost while traveling across the street network, algorithms for traffic flow modeling have been developed by transportation engineers and researchers. Static traflic assignment theory provides an easy and systematic way for transportation engineers to analyze the problems if time constraint is not critical. Unfortunately, the temporal variation of traffic flow on each link of street network is crucial to real-time routing problem, which is beyond the scope that static traffic assignment can handle. Because of its ability of easily integrating time information to a data model, dynamic traffic assignment (DTA) theory has been recommended for solving this problem. Problems emerge to integrate GIS with DTA because it usually needs enormous computing power for traffic flow to reach the stable state for whole street network. The needs for GIS to enhance its computing power by various means have been discussed in literatures (Openshaw 1994, Lin 1993, Mower 1992). The architecture of establishing such high performance GIS/DTA framework still needs to be designed for rerd-time application.
Travel time prediction from origin to destination in a certain trrdlic condition that can easily be done by combining GIS with DTA. However, in the navigation aspect, although a vehicle may have GPS to locate its location preciously, due to the accuracy limitation (± 167 feet) of current digital maps in vehicle that are mostly deduced horn TIGER travelers still face a problem that the navigation system cannot make a decision of whereto make a right turn or left turn if more than one intersection exist in close proximity (Figure 2). Problems like this happen to various transportation applications; hence, a common linear referencing system – ITS Datum has been designed trying to solve problems (Siegel et al., 1996).
Figure 2: Navigation dii3icuhy due to inaccurate digital map.
Dynamic Transportation Network Modelling
Factors such as land use, time of day, street geometry, drivers’ experience, drivers’ behavior and people’s daily activities can affect vehicle distribution on a street network. Congestion occurs when people rush into the street at the same time and share the same routes. The decision made by drivers as to which route to travel is hard to predict systematically via traditional roadside survey due to the complexity of factors as well as unpredictable events such as the occurrence of certain incidents. Dynamic network modeling using real-time data collected by detectors deployed on major streets and traflic assignment theory provides an efficient means for transportation engineers to have an overall picture of traffic distribution patterns.
The dynamic network modeling is crucial to the adoption of real-time traveler information systems, which is one of the main programs of ITS. Such a model is needed to accurately assess network performance, and to forecast Mlc conditions that may exist in the near Mure, to develop real-time diversion strategies for alleviating both recurring and non-recurnng congestion. The core of dynamic network modeling is dynamic tratlic assignment theory, which is the extension of static traftic assignment. Hence, both static and dynamic traffic assignment algorithms will be briefly introduced and, thereafter, serve as the foundation of GINDTA design for real-time routing application.
Taffic Flow Assignment Model
Summarized by Sheffi (1985), the traffic assignment problem can be expressed as follows: Given:
By changing route, drivers are allowed to minimize his or her own travel time when traveling from origin to destination. This route change behavior results in traffic flow changes on each link, and therefore, the travel time from the origin to destination is altered accordingly. We call it the user-equilibrium (UE) condition if a stable state is reached when no traveler can improve his travel time by unilaterally changing routes. Mathematically, the UE objective fimction can be represented as follow:
where
C(X): the total travel time from origin to destination,
X : origin-destination matrix,
xn. : the travel time on link a which is on the route from origin to destination. It is a function of number vehicle w on that link,
ta(w) : travel time on link a while number of vehicle on the link is equal to w,
frsk :flow on the path k where connects origin r and destinations,
qrs : the total traffic flow from r tos.
Static Trailic Assimunent
To find the minimum travel time for a given origin and destination, all-or-nothing assignment method is used to compute the trtilc flow on each link. That is, given initial travel cost on each link (based on free flow condition), the shortest path will be found from origin to destination to minimize the total cost. All traffic flow that originated horn that origin will then be assigned to each link on the shortest path and zero flow will be assigned on those links that are not on the shortest path. With updated traffic flow on each link, the link performance function (shown as follows) developed by the Bureau of Public Roads will be used tore-compute the travel cost, and then the shortest path will be found again, based upon the new travel cost. The iteration stops if it reaches the predefine maximum iteration number or the ditTerence of overall flow on the network between two consecutive iterations is within a certain range.
Where
t0a:free flow travel time,
ta= : flow travel time,
b :0.15 or 0.25,
b :4,
Ca : capacity of link a,
A programmable procedure for traflic flow assignment wass ummarized by Sheffi. The flow chart representing this procedure is shown in Figure 3. In this figure, the convergence criteria can be defined as 1) the difference of overall trailic flow on street network between two consecutive iterations is within a pre-defined range, or 2) it reaches a pre-defined maximal iteration number.
Dynamic Traffic Assimunent
Being different from the snapshot of the transportation network in static traffic assignment model, the dynamic tratlic assignment model explicitly includes time as one of its attributes. For example, besides those variables mentioned in static model, the traffic flow and number of vehicle on the links also vary with time. The travel cost on a link can be expressed as (Boyce et al. 1995):
Ca[xa(t), Ua(t), Va(t)] = g1a[xa(t), ua(t)] + g2a[xa(t), Va(t)]
Where
g1a[xa(t), ua(t) and g2a[xa(t), va(t)]: time-dependentlink travel time function,
Ca(t): travel cost on link a at time t,
ua(t): inflow into link a at time t,
va(t): exit flow from link a at time t,
Figure 3: Procedure of Traffic Assignment
The goal of the dynamic user-optimal choice problem is to find a solution for the following equation,
such that the conservation constraints, flow propagation constraints, nonnegativity conditions and boundary conditions can be satisfied (Ran, 1996).
The primary difference between static traffic assignment and dynamic traflic assignment is that the static model is more like a snapshot of transportation network where its trafilc flow is captured in an instant of time. On the other hand, trailic flow in dynamic traffic assignment is time-dependent where flow in a certain link is a nonlinear function of in-flow and exit flow fkom all O-D pairs. Figure 4 shows the discrepancy of traflic flow between both algorithms.
Figure 4: Comparison of Static and Dynamic Traffic Assignment
System Components of Temproal GIS For Dynamic Routing
Although it is easy to notice that traffic assignment algorithm does not need any input data to initiate its recursive computation and eventually reaches the stable state of trafilc flow distribution on each link, the real-time data are important for four reasons: 1) to estimate or forecast timedependent O-D matrices; 2) to calibrate parameters of travel time functions, tiaveler choice behavior models (perception error, traveler classification, etc.); 3) to calibrate real-time traffic states and make modification to the output generated by the DTA models, and 4) to serve as input to the neural network and tizzy logic model for congestion and incident prediction.
Two categories of input data, data from sensors and detectors deployed at highway aud historical roadside O-D sumey data, are required for travel time prediction and real-time routing. Since data integration and analysis is one of the strengths of GIS, it is desirable to incorporate the data fusion model in a transportation-oriented GIS package to reduce the effort of designing a data input/output interface to link GIS to data fusion engines.
A standard ITS Datum for linear referencing is a fundamental framework to the integration of spatial information that comes from various sources. Although GPS (global positioning systems) provides accurate position information of the vehicle on which it is mounted, with the fact that digital maps derived from TIGER have been used in long range truck tracking, the ITS Datum will serve as a framework to link spatial information that come from various sources for future transportation applications. Vehicle navigation in urban areas cannot succeed without converting or translating all spatial information to a common referencing system.
A well designed spatial/temporal data model in GIS is critical to capture and manipulate trailic information in both present state and past state to predict future travel time and traftlc conditions. This data model has to integrate spatiat/temporal information with dynamic traftic assignment algorithm and neural network and fkzzy logic theory to seine as a data fusion engine for dynamic routing purposes. Data input to this data engine include real-time traillc data, historical O-D survey data, and the feedback from users as well (Figure 5).
Figure 5: System Components of GIS/DTA for Dynamic Routing
Conclusions
GIS has been adopted in many disciplines to solve real-world problems successfidly. However, most current GIS applications operate on data that are not sensitive to temporal change. To extend current GIS technologies to support solutions of dynamic routing problems, the data model must be redesigned to provide a scheme for data representation, data integration, and data analysis based upon DTA and neurid networldfhzzy logic algorithm. Moreover, this spatiaUtemporal data model needs to appropriately represent dynamic linear and point objects such that spatial/temporal operations based upon dynamic network models can be derived to generate predicted information for supporting travelers’ decision making en-route.
To handle hundreds or even thousands of requests submitted by travelers during rash hour, DTA is expected to consume a huge amount of computing power. Hence, to meet the time constraint of a real-time system, data structure in a GIS data model has to be decomposable so that a parallel processing algorithm can be applied. In addition to a centralized computing framework, which is common in the current GIS workplace, distributed computing architecture can also be considered as an alternative to speed up processing time and for the ease of system maintenance. How to design a high performance computing environment is one of major challenges for the success of applying GIS to an in-vehicle navigation system.
Finally, a location referencing system that serves as a base for spatial data integration is critical to accurate data representation and, therefore, to reflecting the reaJity of tratllc conditions at correct locations along the street network such that future tratlic conditions can be reliably predicted.
References
Recently, in transportation and GIS researches, the applications of Intelligent Transportation System (ITS) technologies have been seen as one of high potential directions to solve the problems of continuously degraded performance of transportation systems. By utilizing computers, communication and data processing technologies, the main goal of ITS is to improve the overall performance of transportation systems without building new highways.
ITS key programs cover a wide range of market areas that includes smart trrdlic control systems, emergency response systems, transit management systems, incident management systems, and traveler information systems. For these programs to succeed, the design models in ITS/GIS must simulate the real-world circumstances and must reflect reality. For the same reason, the embedded algorithm in each model of a real-time routing system has to function properly to MtIll user’s requests in terms of response time and information accuracy.
The trends of having reaJ-time in-vehicle navigation system on each car become much clear recently. For example, Mercedes Benz invests one billion dollars to design a Daimiler-Benz’s concept car in which the driver not only can send /receive e-mail and surf the world wide web, but can also receive real-time trrdlic information delivered from Traffic Operation Centers (TOC) (ITS World 1997). To offer more work productivity tools, convenience, safety and entertainment to millions of commuters who spend hours each day cruising the roads or stuck in traflic, at Comdex Fall 1997, IBM, Delco Electronics, NetsCape Communications and Sun Microsystems announced a technology that will utilize existing hardware and software technology -- including voice recognition, wireless communications, global positioning via satellite, head-up displays, Java technology, microprocessors, Web access and collaboration. and other Internet/intranet features -- to create a “Network Vehicle. ”
However, there are MTiculties that exist in applying GIS to this booming market. This paper will investigate the bottlenecks of applying current GIS technology in real-time vehicles routing, and thereafter, propose a conceptual model in GIS to represent and integrate data from various sources with dynamic traflic assignment theory from which accurate real-time or near real-time best route prediction result can be provided to driver for decision making.
System Characteristics
Unlike conventionalGIS applications,only points and linear objectsare consideredin real-time routing problem. Additionally,someof the attributes associatedwith point and linear objectsarea fiction of time; hence,the data model in GIS must be able to handle both spatial and temporal information. For example, as depicted in Figure 1, linear objects (e.g., street networks) and point objects (e.g., fixed objects such as detectors, and moving objects such as probe vehicles) must be relatable for spatial and temporal analysis. Dynamic attributes of dynamic point objects (e.g., vehicle speed) and linear objects (e.g., traffic volume) can be collected in real-time and telemetered to TOC. These dynamic attributes must be integrated with static attributes of linear objects such as number of lanes, directional constraints, and link capacity. That data then serves as input to models derived tlom traffic flow theory and dynamic network models to produce new information such as travel time or travel cost, which are subsequently assigned to the linear objects as attributes. The methodology for integration of this data and models needs to be carefully developed so that predicted travel times reflect the reality of tic conditions.
Figure 1: Trafiic Data Required for Real-Time Routing
Detectors are installed along the highway, major arterial, and intersections to collect real-time data, or so-called “dynamic” data, such as flow rate, travel speed, and trailic volume. The ADVANCE (Advanced Driver and Vehicle Advisory Navigation Concept) project had used probe vehicles mounted with expensive sensing and telemetering systems to report traft3c data, especially congestion situations, back to TOCS so that overall tratlic conditions in study areas can be analyzed simultaneously (Bowcott et al. 1993). Besides real-time tratlic data Kaysi et al. (1993) suggest that historical data or statistical data can also be used to improve the prediction accuracy of future traffic conditions which, thereafter, will assist drivers in providing more realistic route choices.
Procedures for integrating data from various sources are critical to the solution of congestion prediction and dynamic network problems. Such procedures result in “data fusion” -- one of the most important data sources as input to the dynamic traffic assignment model. Because of sparse distribution of probe vehicles, loop detectors and closed-circuit television, real-time data collected by these means are not sticient to give accurate predictions of traffic flow over five- to ten-minute time horizons. Historical origin-destination data and infrastructure data such as signal timing at intersections, number of lanes, and speed limits, are also important for real-time transportation applications. Currently, approaches proposed for data fhsion are by means of fuzzy logic and neural networks (Ivan et al. 1995).
However, even if the required data are available, models for capturing, representing and processing these data must be carefully designed to fidfill the response-time constraint of a real-time system. In his doctoral dissertation, Ziliaskopoulos (1995) proposed time-dependent optimal path algorithms in a multidimensional network model that responds to queries submitted by ditTerent user groups at various times of a day. He demonstrated that huge amounts of computing power are needed to satisfy general requests submitted by users.
Difficulties
Bottlenecks exit in several aspects for current GIS to be filly utilized for dynamic routing purpose. To process temporal related information collected by detectors from highway, the data model in GIS must be redesigned. Although several temporal GIS data models have been proposed (Armstrong 1988, Langran et al. 1988, Worboys 1994), none of them is specially designed to capture and process real-time traffic information. Means for data representation, data integration, and information delivery are also important modules that must to be modeled carefully so that the whole system integrates seamlessly to provide accurate near real-time information to travelers (Chen et al, 1997).
To predict travel time/travel cost while traveling across the street network, algorithms for traffic flow modeling have been developed by transportation engineers and researchers. Static traflic assignment theory provides an easy and systematic way for transportation engineers to analyze the problems if time constraint is not critical. Unfortunately, the temporal variation of traffic flow on each link of street network is crucial to real-time routing problem, which is beyond the scope that static traffic assignment can handle. Because of its ability of easily integrating time information to a data model, dynamic traffic assignment (DTA) theory has been recommended for solving this problem. Problems emerge to integrate GIS with DTA because it usually needs enormous computing power for traffic flow to reach the stable state for whole street network. The needs for GIS to enhance its computing power by various means have been discussed in literatures (Openshaw 1994, Lin 1993, Mower 1992). The architecture of establishing such high performance GIS/DTA framework still needs to be designed for rerd-time application.
Travel time prediction from origin to destination in a certain trrdlic condition that can easily be done by combining GIS with DTA. However, in the navigation aspect, although a vehicle may have GPS to locate its location preciously, due to the accuracy limitation (± 167 feet) of current digital maps in vehicle that are mostly deduced horn TIGER travelers still face a problem that the navigation system cannot make a decision of whereto make a right turn or left turn if more than one intersection exist in close proximity (Figure 2). Problems like this happen to various transportation applications; hence, a common linear referencing system – ITS Datum has been designed trying to solve problems (Siegel et al., 1996).
Figure 2: Navigation dii3icuhy due to inaccurate digital map.
Dynamic Transportation Network Modelling
Factors such as land use, time of day, street geometry, drivers’ experience, drivers’ behavior and people’s daily activities can affect vehicle distribution on a street network. Congestion occurs when people rush into the street at the same time and share the same routes. The decision made by drivers as to which route to travel is hard to predict systematically via traditional roadside survey due to the complexity of factors as well as unpredictable events such as the occurrence of certain incidents. Dynamic network modeling using real-time data collected by detectors deployed on major streets and traflic assignment theory provides an efficient means for transportation engineers to have an overall picture of traffic distribution patterns.
The dynamic network modeling is crucial to the adoption of real-time traveler information systems, which is one of the main programs of ITS. Such a model is needed to accurately assess network performance, and to forecast Mlc conditions that may exist in the near Mure, to develop real-time diversion strategies for alleviating both recurring and non-recurnng congestion. The core of dynamic network modeling is dynamic tratlic assignment theory, which is the extension of static traftic assignment. Hence, both static and dynamic traffic assignment algorithms will be briefly introduced and, thereafter, serve as the foundation of GINDTA design for real-time routing application.
Taffic Flow Assignment Model
Summarized by Sheffi (1985), the traffic assignment problem can be expressed as follows: Given:
- A graph representation of the urban transportation network
- The associated link performance fimctions
- An origin-destination matrix
By changing route, drivers are allowed to minimize his or her own travel time when traveling from origin to destination. This route change behavior results in traffic flow changes on each link, and therefore, the travel time from the origin to destination is altered accordingly. We call it the user-equilibrium (UE) condition if a stable state is reached when no traveler can improve his travel time by unilaterally changing routes. Mathematically, the UE objective fimction can be represented as follow:
where
C(X): the total travel time from origin to destination,
X : origin-destination matrix,
xn. : the travel time on link a which is on the route from origin to destination. It is a function of number vehicle w on that link,
ta(w) : travel time on link a while number of vehicle on the link is equal to w,
frsk :flow on the path k where connects origin r and destinations,
qrs : the total traffic flow from r tos.
Static Trailic Assimunent
To find the minimum travel time for a given origin and destination, all-or-nothing assignment method is used to compute the trtilc flow on each link. That is, given initial travel cost on each link (based on free flow condition), the shortest path will be found from origin to destination to minimize the total cost. All traffic flow that originated horn that origin will then be assigned to each link on the shortest path and zero flow will be assigned on those links that are not on the shortest path. With updated traffic flow on each link, the link performance function (shown as follows) developed by the Bureau of Public Roads will be used tore-compute the travel cost, and then the shortest path will be found again, based upon the new travel cost. The iteration stops if it reaches the predefine maximum iteration number or the ditTerence of overall flow on the network between two consecutive iterations is within a certain range.
Where
t0a:free flow travel time,
ta= : flow travel time,
b :0.15 or 0.25,
b :4,
Ca : capacity of link a,
A programmable procedure for traflic flow assignment wass ummarized by Sheffi. The flow chart representing this procedure is shown in Figure 3. In this figure, the convergence criteria can be defined as 1) the difference of overall trailic flow on street network between two consecutive iterations is within a pre-defined range, or 2) it reaches a pre-defined maximal iteration number.
Dynamic Traffic Assimunent
Being different from the snapshot of the transportation network in static traffic assignment model, the dynamic tratlic assignment model explicitly includes time as one of its attributes. For example, besides those variables mentioned in static model, the traffic flow and number of vehicle on the links also vary with time. The travel cost on a link can be expressed as (Boyce et al. 1995):
Ca[xa(t), Ua(t), Va(t)] = g1a[xa(t), ua(t)] + g2a[xa(t), Va(t)]
Where
g1a[xa(t), ua(t) and g2a[xa(t), va(t)]: time-dependentlink travel time function,
Ca(t): travel cost on link a at time t,
ua(t): inflow into link a at time t,
va(t): exit flow from link a at time t,
Figure 3: Procedure of Traffic Assignment
The goal of the dynamic user-optimal choice problem is to find a solution for the following equation,
such that the conservation constraints, flow propagation constraints, nonnegativity conditions and boundary conditions can be satisfied (Ran, 1996).
The primary difference between static traffic assignment and dynamic traflic assignment is that the static model is more like a snapshot of transportation network where its trafilc flow is captured in an instant of time. On the other hand, trailic flow in dynamic traffic assignment is time-dependent where flow in a certain link is a nonlinear function of in-flow and exit flow fkom all O-D pairs. Figure 4 shows the discrepancy of traflic flow between both algorithms.
Figure 4: Comparison of Static and Dynamic Traffic Assignment
System Components of Temproal GIS For Dynamic Routing
Although it is easy to notice that traffic assignment algorithm does not need any input data to initiate its recursive computation and eventually reaches the stable state of trafilc flow distribution on each link, the real-time data are important for four reasons: 1) to estimate or forecast timedependent O-D matrices; 2) to calibrate parameters of travel time functions, tiaveler choice behavior models (perception error, traveler classification, etc.); 3) to calibrate real-time traffic states and make modification to the output generated by the DTA models, and 4) to serve as input to the neural network and tizzy logic model for congestion and incident prediction.
Two categories of input data, data from sensors and detectors deployed at highway aud historical roadside O-D sumey data, are required for travel time prediction and real-time routing. Since data integration and analysis is one of the strengths of GIS, it is desirable to incorporate the data fusion model in a transportation-oriented GIS package to reduce the effort of designing a data input/output interface to link GIS to data fusion engines.
A standard ITS Datum for linear referencing is a fundamental framework to the integration of spatial information that comes from various sources. Although GPS (global positioning systems) provides accurate position information of the vehicle on which it is mounted, with the fact that digital maps derived from TIGER have been used in long range truck tracking, the ITS Datum will serve as a framework to link spatial information that come from various sources for future transportation applications. Vehicle navigation in urban areas cannot succeed without converting or translating all spatial information to a common referencing system.
A well designed spatial/temporal data model in GIS is critical to capture and manipulate trailic information in both present state and past state to predict future travel time and traftlc conditions. This data model has to integrate spatiat/temporal information with dynamic traftic assignment algorithm and neural network and fkzzy logic theory to seine as a data fusion engine for dynamic routing purposes. Data input to this data engine include real-time traillc data, historical O-D survey data, and the feedback from users as well (Figure 5).
Figure 5: System Components of GIS/DTA for Dynamic Routing
Conclusions
GIS has been adopted in many disciplines to solve real-world problems successfidly. However, most current GIS applications operate on data that are not sensitive to temporal change. To extend current GIS technologies to support solutions of dynamic routing problems, the data model must be redesigned to provide a scheme for data representation, data integration, and data analysis based upon DTA and neurid networldfhzzy logic algorithm. Moreover, this spatiaUtemporal data model needs to appropriately represent dynamic linear and point objects such that spatial/temporal operations based upon dynamic network models can be derived to generate predicted information for supporting travelers’ decision making en-route.
To handle hundreds or even thousands of requests submitted by travelers during rash hour, DTA is expected to consume a huge amount of computing power. Hence, to meet the time constraint of a real-time system, data structure in a GIS data model has to be decomposable so that a parallel processing algorithm can be applied. In addition to a centralized computing framework, which is common in the current GIS workplace, distributed computing architecture can also be considered as an alternative to speed up processing time and for the ease of system maintenance. How to design a high performance computing environment is one of major challenges for the success of applying GIS to an in-vehicle navigation system.
Finally, a location referencing system that serves as a base for spatial data integration is critical to accurate data representation and, therefore, to reflecting the reaJity of tratllc conditions at correct locations along the street network such that future tratlic conditions can be reliably predicted.
References
- Armstrong, M. P. (1988). Temporality in spatial database. In Proceedings: GIS/LIS’88, 2:pp.880-889.
- Boyce, D., B. Ran, and L. Leblanc (1995). Solving an Instantaneous Dynamic User-Optimal Route Choice Model. Transportation Science. Vol. 29, No. 2: pp. 128-142.
- Bowcott, S. and P. De Leuw, Inc. (1993). The ADVANCE Project. ATMS Conference on Management of Large Urban Tratlic Systems. ADVANCE Information Source. http://ais. its-program. anl.gov/reports/REPORTS.HTML/atms/atms93.html.
- Chen, C. C, A. P. Vonderohe, and B. Ran (1997). SpatiaVTemporaJ Data Modelling and Integration Problems in Dynamic Network Routing. In Proceedings: GIS/LIS’97,pp.863-871.
- ITS World (1997). Daimler-Benz unveils infomobile, July/August 1997, pp. 10-11.
- Ivan, J. N., J. L. Schofer, F. S. Koppelman, and L. L. E. Massone (1995). Real-time data fusion for arterial street incident detection using neural networks. Transportation Research Record, 1497:pp.27-35.
- Kaysi, I., M. Ben-Akiva, and H. Koutsopoulos (1993). Integrated approach to vehicle routing and congestion prediction for real-time driver guidance. Transportation Research Record, 1408:pp.66-74.
- Langran, G. and N. R. Chrisman (1988). A tiamework for temporal geographic information. Cartographic, 25(3) :pp.1-14.
- Lin, B. (1993). Developing network-oriented GIS software for parallel computing. In Proceedings: GIS/LIS’93, pp.403-413.
- Mower, J. E. (1992). Building a GIS for parallel computing environments. Proceedings of the 5ti International Symposium on Spatial Data Handling, Vol. 1, pp.219-229.
- Openshaw, S (1994). A concepts-rich approach to spatial analysis, theory generation, and scientific discovery in GIS using massively parallel computing. Innovations in GIS. Taylor & Francis, Inc. pp. 123-138.
- Ran, B. and D. Boyce (1996), Moeling Dynamic Transportation Networks: An Intelligent Transportation System Oriented Approach. 2nd Edition. Springer-Verlag, Berlin, Germany.
- Sheffi, Y (1985). Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice-Hall: Englewood Cliffs.
- Siegel, D., C. Goodwin, and S. Gordon. (1996). ITS datum prototype final design report. Task C: spatial data interoperability protocol for ITS project. Federal Highway Administration. IVHS Research Division. McLean, VA.
- Worboys, M. (1994). Unifying the Spatial and TemporaJ Components of Geographical Information. In Advanced in GIS Researches: Proceedings of 6ti International Symposium on Spatial Data Handling. Taylor and Francis, London, pp.505-517.
- Ziliaskopoulos, A. (1995). Optimum path algorithm on multidimensional networks: anatysis, design, implementation, and computational experience. Ph.D. Dissertation, University of Texas at Austin.