Computational Tools for Measuring Space-Time Accessibility Within Dynamic Flow Transportation Networks

Computational Tools for Measuring Space-Time Accessibility Within Dynamic Flow Transportation Networks

Yi-Hwa Wu*
Harvey J. Miller
University of Utah

Abstract

The space-time prism (STP) and STP-based accessibility measures are powerful techniques for assessing the ability of individuals to travel and participate in activities at different locations and times in a given environment. However, traditional STPs and STP-based accessibility measures ignore spatial and temporal variations in travel times in an urban environment. Factors such as traffic congestion impose increasingly complex and severe constraints on individual travel and participation in activities. This paper reports on the development of dynamic STP-based accessibility measures and computational procedures for assessing individual accessibility in networks with time-varying flow. We extend static network-based STPs to the case where network flow and travel velocities vary across time due to congestion. These tools can evaluate the accessibility of travelers under different traffic congestion scenarios, alternative network flow control strategies, and activity scheduling policies (e.g., flextime and telecommuting).

Introduction

Much travel behavior research focuses on understanding an individual's decision processes and analyzing the elementary factors determining travel activity. Consequently, most transportation planning tools emphasize travel demand patterns and predicting travelers' responses to transportation policy and management options. These methods concern how or when travel activities will take place throughout the transportation system. Accessibility measures are alternative approaches that emphasize the potential for travel behavior conditioned by the performance of the transportation system. Accessibility measures assess an individual's freedom to participate in activities in a given travel environment rather than explaining or predicting actual travel choices. Because they highlight constraints on travel rather than revealed travel choices that intertwine preferences and constraints, accessibility measures can be a more sensitive assessment technique than analyses of actual travel behavior (Hägerstrand 1970).

Conventional accessibility measures focus on tradeoffs between the attractiveness of opportunities and the travel cost required to obtain these opportunities (see, e.g., Geertman and Van Eck 1995). These indicators usually measure attractiveness through surrogates such as the size or variety of the opportunity (e.g., store size for retail opportunities) and travel cost through physical distance, travel time, or monetary cost. Accessibility is usually measured with respect to key activity locations for individuals (e.g., home, workplace) and evaluates the transportation services provided to these key locations to assess their relative advantages (Burns 1979).

Conventional accessibility measures often neglect the fact that the temporal dimension also affects individual accessibility. Limited time "budgets" or available time for travel and activity participation can constrain the participation time for each activity and therefore reduce individual accessibility. Periodic activity schedules, conditioned by required spatio-temporal events such as a fixed work schedule or child maintenance activities, vary widely but systematically by life stage, sex, socioeconomic status, and culture. An analysis by Kwan (1998) suggests that space-time measures are more sensitive in capturing interpersonal differences in individual accessibility than conventional measures. Measures that do not capture temporal constraints created by individual activity schedules are a one-size-fits-all depiction of accessibility that is insensitive to individual differences (Kwan 1998; Miller 1999; Miller and Wu 2000).

Hägerstrand's (1970) space-time prism (STP) is a powerful conceptual tool that captures both spatial separation and temporal constraints that limit individuals' freedom to travel and participate in required and desired activities. Accessibility measures based on the STP consider the spatial extent of travel and available activity participation time dictated by individual activity schedules. Most of these measures capture these schedules by measuring spatial separation with respect to anchor locations (e.g., home, work) and restricting travel extent based on the individual's time budget or free time for travel and activity participation (Miller 1999; Kwan 1998).

A weakness of STP-based accessibility measures, and accessibility measures in general, is their treatment of travel times as static. Consequently, these measures cannot capture the potential impacts of transportation network congestion on accessibility. Traffic congestion is a major problem and policy issue in many cities (Cervero 1986; Plane 1995). The traditional suburb to central city journey-to-work pattern has been replaced by more complex commuting patterns involving substantial suburb-to-suburb flows. Service sector working hours tend to be staggered and occupy more of the daily clock than traditional employment. This results in congestion being spread beyond the traditional morning and evening peak periods (Hanson 1995). The increasing saturation of urban transportation networks means that localized incidents (e.g., construction or accidents) can propagate widely through the network. This suggests the need for new tools to capture dynamic congestion patterns in urban transportation networks and the potential for these tools to affect accessibility.

This paper reports on the development of dynamic space-time accessibility measures and computational procedures for assessing individual accessibility in networks with time-varying congestion. We extend static network-based space-time accessibility measures to the case where network flow and travel velocities vary across time due to congestion. We also develop a computational toolkit that uses simulated dynamic traffic conditions to calculate travel times based on the shortest path routes through a network with dynamic flows. Our computational toolkit is coupled with a geographic information system (GIS), facilitating spatial data management and visualization of the resulting accessibility regimes.

Following this introduction, there are six sections to this paper:

  • Space-Time Accessibility reviews the conceptual and theoretical basis for the space-time accessibility measures.
  • Dynamic Space-Time Accessibility Constructs discusses the algorithm for calculating space-time accessibility within dynamic transportation networks.
  • Dynamic Congestion Modeling provides the methodology used for developing the dynamic congestion module.
  • System Design describes the system configuration for the toolkit.
  • Example Calculations shows some preliminary results.
  • The Conclusion provides some summary comments and directions for continued system development.

Space-Time Accessibility

Temporal Constraints and Activity Participation

Since all human activities occur in space and time, these dimensions are inseparable from the intricacies of human behavior (Hägerstrand 1970). Empirical research has shown that temporal constraints can impact significantly the ability of individuals to participate in activities. Time-policy research suggests that space-time accessibility affects individual travel behavior both in space and time (Tacken 1997). Adding temporal constraints that affect the size of individuals' choice sets can improve prediction accuracy of behavioral choice models (Landau et al. 1981; 1982). The space-time constraint framework provides the fundamental physical constraints to define individuals' potential action space (Dijst and Vidakovic 1997). Many activity-based travel models (e.g., Recker et al. 1986) require time constraints to restrict the number of possible activity schedules when predicting individual activity programs.

Classical Space-Time Prisms

Hägerstrand's (1970) time geography is an elegant and powerful framework for measuring constraints to individual accessibility. Time geography incorporates the spatial, temporal, and transportation elements that affect accessibility within a geographic environment. In its classical form, the activity pattern of an individual is a space-time path in three-dimensional space where a two-dimensional horizontal plane represents geographic locations and a vertical axis represents time. The path traces the spatio-temporal position of the individual's travel and activity behavior. The limits on this path create an accessibility regime that is a connected and continuous set of positions in space-time known as the space-time prism (Lenntorp 1976).

An individual's activity schedule is usually constrained by fixed (mandatory) activities. The mandatory activities typically include work, home, or other household maintenance activities (e.g., driving children to school). The STP is an extension of the space-time path during temporal intervals when the individual is free to participate, in discretionary activities. These are activities over which the individual has relative control with respect to location and timing; examples include shopping and recreation. The STP is the set of locations in space-time that are accessible to an individual given the locations and duration of fixed activities, a time budget for flexible activity participation, and the travel velocities allowed by the transportation system. Instead of tracing the observed movement throughout space of an individual over an interval of time, the STP indicates what portions of space are possible for an individual at each moment in time (Miller 1991). The STP also delimits the feasible set of locations for travel and activity participation in a bounded territory of space and a limited interval of time (Burns 1979; Miller 1991; Kwan 1998).

Figure 1 illustrates an STP. The three-dimensional volume bounded by the STP is called the Potential Path Space (PPS). An individual's time budget (available time for travel and activity participation), spatial constraints (fixed activity locations that determine travel origin/destination within the discretionary time period), and the available travel velocity in the environment determines the PPS. The prism boundaries demarcating the STP result from the available travel velocity within the geographic environment. In the classical STP, travel velocity is assumed to be constant across space for analytical simplicity.

The Potential Path Area (PPA) is the projection of the PPS to planar (two-dimensional) space. The PPA represents the purely spatial extent or area that an individual can travel within a specified time budget. It can be calculated directly without reference to the PPS, with any stationary activity participation time excluded from the overall time budget to reflect the reduced amount of time available for travel (Miller 1991).

Several researchers have developed accessibility measures based on the STP. STP-based measures view accessibility as an individual's ability to reach activity locations given the person's daily activity program and spatio-temporal constraints (Kwan 1998). STP-based measures usually include the following elements. First is a reference fixed-activity event in space and time from where and when the accessibility of an individual to other locations is measured. Second is a set of destinations (activity locations) and their attributes representing the discretionary opportunities available to an individual. Third is a transportation system that enables an individual to overcome the spatial temporal separation of activity sites. Therefore, any STP-based measure of accessibility may be defined as basically a quantification of the opportunities for activity participation open to an individual from a given location at a given time of day.

Lenntorp (1976) uses the PPS and the PPA to simulate all possible activity schedules within an urban environment. Lenntorp's simulation model (Program Evaluating the Set of Alternative Sample Paths) does not calculate the STP directly. Input variables are the general characteristics of the transportation system, the spatial distribution and operational hours of activity, and a hypothetical activity schedule as variables. The hypothetical activity schedule provides constraints imposed by the fixed activities. The fundamental assumption is that greater freedom for flexible activity participation implies greater accessibility. Therefore, the number of possible flexible activity schedules allowed by the PPS and PPA are a surrogate for accessibility.

Other researchers use mathematical and geometric methods to directly measure STP properties. For example, Burns (1979) uses geometric methods to calculate the volume of the STP under different transportation environments (e.g., continuous space versus different types of uniform network meshes, travel timing policies). The STP volume is a surrogate for individual accessibility. Similar methods can be found in Kitamura et al. (1981) and Kondo and Kitamura (1987).

Forer (1998) develops a 3-D raster model using taxels as the basic building block for constructing an STP. Its GIS-based method overlays relevant layers of geographic information (e.g., the transportation network, activity locations) during each discrete time interval comprising a temporal study horizon. This allows the analyst to visualize accessibility as a space-time "aquarium." It also creates an accessibility mask for spatio-temporal querying using customized 3-D data structures. While effective, a shortcoming is the same as for any raster model; that is, large data storage requirements as the spatial and temporal domains of the problem grow.

Network-Based Space-Time Prisms

The space-time framework provides a powerful and elegant perspective for analyzing individuals' accessibility within the environment. Instead of directly modeling travel interaction throughout the system, the STP provides a measure to describe individual possible travel behavior under physical constraints. However, it is difficult to operate and apply in its classic form as a real-world accessibility tool. The ideal geometries of the STP, PPS, and PPA result from the unrealistic assumption of a constant and uniform travel velocity.

In order to improve the realism and applicability of the space-time prism approach, Miller (1991) developed an operational method for implementing a network-based space-time prism using GIS procedures. This approach uses link-based travel speed, instead of uniform travel conditions, throughout the transportation system. The Network Time Prism (NTP) is comprised of arcs and nodes in the transportation network rather than an unrealistic simple geometric set that assumes constant travel velocities across space. A Potential Path Tree (PPT) is a subtree of the network consisting of nodes and arcs reachable given fixed activity locations and a time budget. Its root is usually the travel origin, although it can also be anchored at the travel destination. Kwan and Hong (1998) extend this approach by incorporating cognitive (information, preference) constraints into the PPT. The study defines the feasible opportunity set (FOS) as the subset of opportunity locations available to an individual, based on both temporal and cognitive constraints.

Miller (1999) develops space-time accessibility measures (STAMs) of users' benefits based on the PPT. These measures are consistent with behavioral choice theory and with the rigorous Weibull (1976) framework for spatial interaction-based accessibility measures. Miller (1999) also develops computational methods for calculating these measures within the network itself for query and visualization purposes. Miller and Wu (2000) describes the architecture of a GIS toolkit for these measures and provide examples for a detailed, urban-scale transportation network.

Using the urban transportation network to calculate space-time measures can provide a more realistic method for evaluating accessibility relative to classical time geographic measures. However, the previous approaches reviewed above do not consider the temporal dynamics of real-world transportation networks. As mentioned in the introduction, the increasing saturation of most real-world transportation networks means that assuming static network conditions is as unrealistic as assuming constant travel velocity across space. Our objective in this paper is to implement the dynamic space-time accessibility measures within a realistic time-varying transportation network.

Dynamic Space-Time Accessibility Constructs

The space-time accessibility measures in the research focus on how the constraints within urban environments affect an individual's choice of activity. The space-time prism provides a direct framework for this type of accessibility measure. We use simulated time-varying flows within a transportation network to compute dynamic versions of the basic NTP constructs.

In a Dynamic Network Time Prism (DNTP), travel times between locations vary with both space and time. Travel between any two locations in a network with time-varying flows must be constrained by the start/stop time intervals for the travel episode and traced along a finite set of connected arcs in space-time. Given a travel origin and start time, a DNTP is a subset of a space-time network that indicates the maximum travel extent under time constraints dictated by the individual's activity schedule, including the timing of the travel and activity episode.

A Dynamic Potential Path Tree (DPPT) is a time-dependent maximum coverage tree from an origin to any network nodes given dynamic network flow conditions and a specified departure time. The DPPT can be combined with geographic visualization techniques, such as animation tools, to provide powerful visualizations of changing accessibility conditions over time within a congested transportation network. It could also be used to support spatio-temporal network queries based on space-time accessibility and as input to models such as activity scheduling simulations.

The DPPT can be used to construct the dynamic opportunity set (DOS) of activity locations for an individual. The DOS extends the FOS concept from Kwan and Hong (1998) to the case of dynamic temporal constraints imposed by time-varying traffic flow and therefore travel velocities. This opportunity set is based on the timing of travel from the origin to the activity location, net any activity participation time:

uppercase m equals { (lowercase k is an element of uppercase omega given uppercase t subscript {lowercase k}) equals uppercase t minus (lowercase t superscript {lowercase d} subscript {lowercase i} times (lowercase x subscript {lowercase i}, lowercase x subscript {lowercase k})) is greater than or equal to lowercase t superscript {lowercase m} subscript {lowercase k} }

where

M = the set of accessible discretionary activity locations, given the travel origin, time budget, and dynamic network flow.

uppercase omega = the set of total discretionary activity locations.

Tk = participation time at activity discretionary activity location k.

T = the overall time budget for travel and activity participation.

lowercase t superscript {lowercase m} subscript {lowercase k} = minimum required time for activity participation time at location k.

lowercase t superscript {lowercase d} subscript {lowercase i} times (lowercase x subscript {lowercase i}, lowercase x subscript {lowercase k}) = the minimum travel time from xi to xk given a departure at time d.

Equation (1) shows that the subset of feasible activity locations must have greater activity participation time (Tk) than the minimum required time for discretionary activity k. The minimum required time for each discretionary activity could be standardized for each activity or derived for individuals from activity diary data. The activity participation time is the time budget minus the minimum travel time lowercase t superscript {lowercase d} subscript {lowercase i} times (lowercase x subscript {lowercase i}, lowercase x subscript {lowercase k}). The minimum travel time is constrained by the start time from travel origin and dynamic network flows. Time budgets vary by individual; these can be extracted from activity diary data or by self-reporting (see Miller 1999). The procedure calculates the dynamic shortest path from the specified travel origin to all possible discretionary activity points. The shortest path is very easily extracted once the DPPT is created.

Equation (1) creates a set of feasible discretionary activity locations rather than a subset of the network arcs. This type of DNTP calculation only delimits feasible activity locations; it does not consider activity attractiveness as part of the accessibility measure (as in Miller 1999). However, it can be used to delimit the activity choice set for further dynamic accessibility for input into dynamic versions of the STAMs.

Dynamic Congestion Modeling

Since we need to construct DNTP measures based on time-varying flow conditions, we require some method for computing these flows. The particular dynamic flow model that provides these estimates is modular in the sense that any model is acceptable if it can generate realistic dynamic flow and travel time estimates. However, the method must be computationally efficient due to the number of calculations required for the DNTP measures.

Initial work on developing dynamic flow models began in the late 1970s with Merchant and Nemhauser (1978a; 1978b). Several approaches to the dynamic network flow problem have emerged, including: 1) simulation-based approaches; 2) optimal control theory; 3) variational inequality; 4) dynamic systems approaches; and 5) mathematical optimization. Although several dynamic network flow models are available (see Friesz et al. 1996; Ran and Boyce 1996; Chen 1999), most of these methods (particularly continuous-time formulations) are not computationally efficient to the degree required for the DNTP calculations of interest in this paper.

Equilibrium analysis is a relatively efficient approach to modeling transportation network flows. The equilibrium approach captures the relationship between users' travel decisions and network performance assuming shortest path travel. However, as Ben-Akiva (1985) argues, traditional static network equilibrium models fail to capture fundamental properties of traffic congestion. Janson greatly improved the applicability of dynamic network flow modeling to real-world network problems by developing a tractable discrete-time dynamic user optimal (DUO) approach (Janson 1991a; 1991b). Furthermore, the Janson DUO model can be solved for realistic, urban-scale networks with reasonable computational times (Robles and Janson 1995; Boyce et al. 1997) making it suitable for constructing DNTP. Because of its tractability, we use the Janson DUO model in our DNTP procedures, although we can swap this for other dynamic flow models in future system development if breakthroughs allow more sophisticated models to be solved efficiently.

The DUO is a direct extension of Wardrop's user optimal equilibrium conditions. The DUO condition requires that, at network equilibrium, no traveler who departed or arrived during the same time interval can reduce his or her travel costs by unilaterally changing routes. An alternative but equivalent statement is that all routes used between an origin-destination (O-D) pair have the same minimal cost, and no unused route has a lower cost for travelers that departed or arrived during the same time interval. The DUO is based on either departure or arrival times, not both. Since travel times are variable, we cannot constrain both departure and arrival times within the equilibrium conditions. Therefore, the DUO conditions assume either a known (fixed) departure or arrival time interval for flows and require equivalent minimal travel costs for all flows that depart or arrive during each interval. The DUO principle means that positive flow on a route for users who departed (arrived) during a given time interval implies that it must have a travel cost equal to the minimum cost for the users between the particular origin-destination pair. Second, any route with a cost greater than the minimum for users who departed during a given time interval implies that the flow level for those users is zero.

The DUO model assumes a known temporal O-D matrix, with each time slice corresponding to a discrete time interval over the study time horizon. Based on this exogenous data, the DUO minimization problem, when solved, determines the dynamic flow patterns that satisfies the DUO principle while meeting the O-D flow constraints imposed by the matrices. The DUO problem is

minimize [summation over lowercase k is an element of uppercase l, summation over lowercase t is an element of uppercase t (integral from zero to lowercase x superscript {lowercase t} subscript {lowercase k} (lowercase f superscript {lowercase t} subscript {lowercase k} times (lowercase w) times lowercase d w)]

Subject to

lowercase x superscript {lowercase t} subscript {lowercase k} equals summation over lowercase p is an element of uppercase p, summation over lowercase d is an element of uppercase t [(lowercase nu superscript {lowercase d} subscript {lowercase p}) times (lowercase alpha superscript {lowercase d t} subscript {lowercase p k})]; for all lowercase k is an element of uppercase l, lowercase t is an element of uppercase t

lowercase q superscript {lowercase d} subscript {lowercase r s} equals summation over lowercase p is an element of uppercase p subscript {lowercase r s} (lowercase nu superscript {lowercase d} subscript {lowercase p}; for all lowercase r is an element of uppercase z, lowercase s is an element of uppercase z, lowercase d is an element of uppercase t

lowercase nu superscript {lowercase d} subscript {lowercase p} is greater than or equal to zero; for all lowercase p is an element of uppercase p, lowercase d is an element of uppercase t

lowercase alpha superscript {lowercase d t} subscript {lowercase p k} is an element of {0,1}; for all lowercase p is an element uppercase p, lowercase k is an element of uppercase k subscript lowercase p, lowercase d is an element of uppercase t, lowercase t is an element of uppercase t

summation over lowercase t is an element of uppercase t (lowercase alpha superscript {lowercase d t} subscript {lowercase p k} equals 1; for all lowercase p is an element of uppercase p, lowercase k is an element of uppercase k subscript lowercase p, lowercase d is an element of uppercase t, lowercase t is an element of uppercase t

lowercase b superscript {lowercase d} subscript {lowercase p n} equals summation over lowercase t is an element of uppercase t, summation over lowercase k is an element of uppercase k subscript {lowercase p n} [(lowercase f superscript {lowercase t} subscript {lowercase k}) times (lowercase x superscript {lowercase t} subscript {lowercase k}) times lowercase alpha superscript {lowercase d t} subscript {lowercase p k}]; for all lowercase p is an element of uppercase p, lowercase n is an element of uppercase n, lowercase d is an element of uppercase t, lowercase t is an element of uppercase t

[(lowercase b superscript {lowercase d} subscript {lowercase p n}) minus (lowercase t times uppercase delta) times lowercase t] times (lowercase alpha superscript {lowercase d t} subscript {lowercase p k}) is less than or equal to 0; for all lowercase p is an element of uppercase p, lowercase n is an element of uppercase n, lowercase k is an element of uppercase l subscript {lowercase n}, lowercase d is an element of uppercase t, lowercase t is an element of uppercase t

[(lowercase b superscript {lowercase d} subscript {lowercase p n}) minus (lowercase t minus one) times (uppercase delta times lowercase t)] times (lowercase alpha superscript {lowercase d t} subscript {lowercase p k}) is greater than or equal to 0; for all lowercase p is an element of uppercase p, lowercase n is an element of uppercase n, lowercase k is an element of uppercase l subscript lowercase n, lowercase d is an element of uppercase t, lowercase t is an element of uppercase t

where

N = set of all nodes

Z = set of all origin-destination zones (trip begin/end nodes)

L = set of all links (directed arcs)

Ln = set of all links incident from node n

P = set of all routes between all zone pairs

Prs = set of all routes from zone r to zone s

Kp = set of all links on route p

Kpn = set of all links on route p prior to node n

uppercase delta times lowercase t = duration of each time interval (same for all t)

T = set of all time intervals in the full analysis period

lowercase x superscript {lowercase t} subscript {lowercase k} = amount of traffic flow between all zone pairs assigned to link k in time interval t

lowercase nu superscript {lowercase d} subscript {lowercase p} = amount of traffic flow departing in time interval d assigned to route p

(lowercase f superscript {lowercase t} subscript {lowercase k}) times (lowercase x superscript {lowercase t} subscript {lowercase k}) = travel impedance (travel time) on link k in time interval t

lowercase q superscript {lowercase d} subscript {lowercase r s} = amount of traffic flow from zone r to zone s departing in time interval d via any route

lowercase alpha superscript {lowercase d t} subscript {lowercase p k} = 0-1 variable indicating whether trips departing in time interval d and assigned to route p use link k in time interval t (0 = no, 1 = yes)

lowercase alpha superscript {lowercase d t} subscript {lowercase p k} = travel time of route p from its origin to node n for trips departing in time interval d

The dynamic constraints (equations 7-10) ensure temporal flow consistency. The temporal route-link incidence variable lowercase alpha superscript {lowercase d t} subscript {lowercase p k} maintains correspondence between links and routes across time intervals for trips departing within a particular time interval. This is a temporal extension of the static route-link incidence variable in the static version of this problem (equations 2-5 without the time dimension). However, a major difference is that the temporal route-link incidence is an endogenous decision variable solved within the dynamic equilibrium problem. In the DUO, the link composition of routes for trips that departed within a given time period cannot be predetermined since the time interval of link use is affected by travel time, which in turn is affected by traffic flow loadings (Janson 1991a).

The endogenous nature of route-link incidence in the DUO requires the problem to have nonlinear dynamic flow constraints to ensure flow consistency. First, we require trips to only use each link on a given route only once within each time interval (equations 6-7). Second, we require each route to be consistent with respect to the required travel times to reach each link on the route. To ensure this, we measure the total travel time on a route from the origin to a given node for trips departing within a given time interval (equation 8). Then, we force trips to use the links on a route in a temporally consistent manner. Trips can only use a link during the interval that it reaches the from-node of the link according to the cumulative travel time to that from-node. If cumulative travel time to the from-node is greater than or less than the cumulative clock time then the temporal route-link incidence variable is forced to zero and the route cannot use that link (equations 8-10).

We can solve the DUO problem efficiently using a heuristic procedure that assigns link flows based on current flow levels, future travel demands, and flows assigned in previous intervals. An alternative, exact algorithm decomposes the main DUO problem into two subproblems, namely, a static UO assignment subproblem and a linear program that updates the temporal incidence variables and enforces conditions for temporally continuous flows. For detailed discussion of these solution procedures, see Wu et al. (2001).

System Design

Our current software system integrates three major modules for performing dynamic accessibility measures. Commercial GIS software (Arc/Info version 7) provides the data management and visualization functions. We implement a dynamic traffic module based on Janson's (1991a) formulation for providing dynamic flow simulation. An accessibility measure module uses the dynamic network flow conditions as space-time constraints to calculate the DNTP. Both modules are stand-alone systems written in C11. Although both modules run as separate programs, the programs directly read and write Arc/Info INFO files, allowing the GIS software to manage the input data and visualize model results. Figure 2 shows the basic system architecture.

Both transportation network and activity locations data are processed into Arc/Info coverages. The dynamic traffic module reads the network structure from coverages and writes new INFO files with dynamic flow information, one file for each time interval modeled. These can be visualized and queried within the cartographic context of the network coverage using Arc/Info. The accessibility measure module retrieves dynamic flow information from these new INFO files and calculates the DNTP. The results transfer back into Arc/Info and create new coverages. Two discrete space versions of DNTP can be visualized and queried within Arc/Info. Point entities represent an opportunity set of locations that are choices for individual activity participation. Arc entities represent the subset of space (defined by transport routes) that is feasible to travel. These can be used directly to access accessibility regimes given a congested network.

The current prototype performs data transfers between the three modules. The user interface is still in progress. We expect to more fully integrate the three modules using Arc/Info version 8, which provides more powerful interface functionality than earlier versions.

Examples of Calculations

We now provide examples of calculations of the DPPT for a realistic problem. The network in this example represents northeast Salt Lake City, Utah. It contains 7,812 directed links, 2,328 nodes, and 331 O-D zones. The discrete time interval for the DUO model is three minutes. A 2-hour study time horizon results in 40 consecutive time slices of dynamic congestion patterns. A daily O-D matrix was derived from a travel survey conducted by the University of Utah during spring 1994. We constructed a local daily peak profile curve to mimic the aggregate peak hour commute patterns in the study area. Therefore, traffic patterns during the first and last few intervals are less congested than the middle intervals within the modeled time horizon. We use the standard Bureau of Public Roads performance functions to calculate traffic flow in each time interval.

Figure 3 shows an example of a dynamic congestion pattern for the university area of the Salt Lake City network (northeast corner of study area) in different time intervals estimated from the DUO model. For display purposes, we offset the two arcs corresponding to two-way travel within each street segment. We classify the congestion level in each arc into two categories, namely, "very congested" for flow of 80% of capacity or greater and "normal traffic" for flow levels less than 80% of capacity. The upper half of figure 3 shows the traffic conditions during time interval 1 or the first three minutes of the time horizon. The lower half of figure 3 shows the peak traffic conditions in interval 20, which is 57 to 60 minutes into the study horizon. A comparison of the two graphics shows the temporal flow complexity captured by the DUO model.

Figures 4-8 provide examples of DPPT calculations for the Salt Lake City transportation network from the GIS-DNTP software system. Figures 4 and 5 represent the DPPT for a single origin (the University of Utah) and single departure interval (time interval 15, or 42 to 45 minutes into the modeled time horizon). Figure 4 shows the accessible portion of the transportation network given a five-minute time budget for travel. Figure 5 shows the accessible portion of the network given a 15-minute time budget for travel. As is the case with the NTP, the accessible portion of the network is greater if the available time budget is larger. After calculating the DPPT, the system assigns the required travel time to each node. We can then use this information to query activity locations georeferenced at network nodes to calculate the DOS (equation 1).

Figures 6-8 show DPPTs given the same origin and time budget (10 minutes) but based on different departure time intervals. Figure 6 provides the DPPT based on departing at time interval 1 (three minutes into the modeled time horizon), figure 7 shows the DPPT based on departing in time interval 15 (42 to 45 minutes into the horizon), and figure 8 shows the DPPT based on departing during time interval 20 (60 to 63 minutes into the horizon). Since the traffic conditions are dynamic, the reachable portion of the network varies depending on the departure interval. In figure 6, the DPPT has a relatively large spatial extent due to the low traffic flows and higher travel velocities during the initial portion of the modeled time horizon. As traffic flow builds during the middle time periods, the spatial extent of the DPPT becomes more curtailed (figure 7), particularly towards the central portion of the city (downtown is the area in the middle north of the map, just west of the DPPT extent). By the later time intervals, traffic has started to ease and the DPPT spreads outward (figure 8). Note that the DPPT extends substantially toward the south in time interval 20 since traffic flows ease first in these more peripheral locations of the city.

Conclusion

This paper introduces realistic conditions of time-varying flow and congestion within the transportation network for dynamic space-time accessibility measures. This allows the accessibility measures to consider the locations and time-varying travel velocities dictated by the network. These computational procedures are tractable with respect to storage space and time requirements, meaning they can be applied to urban-scale accessibility analyses with detailed networks. The GIS environment supports visualization, querying, and additional analysis of accessibility within the transportation network structure.

The dynamic space-time accessibility measures in this research only consider the space-time constraints within the urban environment. The DPPT we construct is from a specified origin given available travel time and departure time interval. Moreover, DPPT in this research is a path tree that depicts travel from a given origin node that terminates at network nodes. In other words, the results are the subset of original network arcs. In our continuing research, we are developing a Dynamic Potential Network Area (DPNA) that extends the potential tree into a potential area. This means that the travel path can terminate at any location in the network, even at a location within an arc. This will be a dynamic version of the extended shortest path tree developed by Okabe and Kitamura (1996).

In this current stage, we did not include activity schedules in the calculation of DNPT. A more sensitive dynamic accessibility tool would calculate the potential path area based on archoring mandatory activity locations (e.g., home and work locations). Moreover, the attractiveness of discretionary activity locations and participation time for activities have also been ignored in this current research. The objective of further research is to capture the interactions between transportation system performance, the locations of mandatory and discretionary activities, and the individual's activity schedule using the STAMs developed by Miller (1999).

References

Ben-Akiva, M. 1985. Dynamic Network Equilibrium Research. Transportation Research A 19A:429-31.

Boyce, D.E., D.H. Lee, B.N. Janson, and S. Berka. 1997. Dynamic Route Choice Model of Large-Scale Traffic Network. Journal of Transportation Engineering. 123, no. 4:276-82.

Burns, L.D. 1979. Transportation, Temporal, and Spatial Components of Accessibility. Lexington, MA: Lexington Books.

Cervero, R. 1986. Suburban Gridlock. New Brunswick, NJ: Center for Urban Policy Research.

Chen, H.-K. 1999. Dynamic Travel Choice Models: A Variational Inequality Approach. Berlin, Germany: Springer-Verlag.

Dijst, M. and V. Vidakovic. 1997. Individual Action-Space in the City. Activity-Based Approach to Travel Analysis. Edited by D.F. Ettema and H.J.P. Timmermans. Oxford, England: Elsevier Science Ltd. 117-34.

Forer, P. 1998. Geometric Approaches to the Nexus of Time, Space, and Microprocess: Implementing a Practical Model for Mundane Socio-Spatial Systems. Spatial and Temporal Reasoning in Geographic Information Systems. Edited by M.J. Egenhofer and R.G. Golledge. New York, NY: Oxford University Press. 171-90.

Friesz, T.L., D. Bernstein, and R. Stough. 1996. Dynamical Systems, Variational Inequalities and Control Theoretic Models for Predicting Time-Varying Network Flows. Transportation Science 30:14-32.

Geertman, S.C.M. and J.R.R. Van Eck. 1995. GIS and Models of Accessibility Potential: An Application in Planning. International Journal of Geographical Information Systems 9:67-80.

Hägerstrand, T. 1970. What About People in Regional Science? Papers of the Regional Science Association 24:7-21.

Hanson, S. 1995. Getting There: Urban Transportation in Context. The Geography of Urban Transportation. Edited by S. Hanson. New York, NY: The Guilford Press. 305-41.

Janson, B.N. 1991a. Dynamic Traffic Assignment for Urban Road Networks. Transportation Research B 25B:143-61.

____. 1991b. Convergent Algorithm for Dynamic Traffic Assignment. Transportation Research Record 1328:69-80.

Kitamura, R., L.P. Kostyniuk, and M.J. Uyeno. 1981. Basic Properties of Urban Time-Space Paths: Empirical Tests. Transportation Research Record 794:8-19.

Kondo, K. and R. Kitamura. 1987. Time-Space Constraints and the Formation of Trip Chains. Regional Science and Urban Economics 17:49-65.

Kwan, M.-P. 1998. Space-Time and Integral Measures of Individual Accessibility: A Comparative Analysis Using a Point-Based Framework. Geographical Analysis 30, no. 3:191-216.

Kwan, M.-P. and X.-D. Hong. 1998. Network-Based Constraint-Oriented Choice Set Formation Using GIS. Geographical Information 5:139-62.

Landau, U., J.N. Prashker, and M. Hirsh. 1981. The Effect of Temporal Constraints on Household Travel Behavior. Environment and Planning A 13:435-48.

Landau, U., J.N. Prashker, and B. Alpern. 1982. Evaluation of Activity Constrained Choice Sets to Shopping Destination Choice Modeling. Transportation Research A 16A:199-207.

Lenntorp, B. 1976. Path in Space-Time Environments: A Time-Geographic Study of the Movement Possibilities of Individuals, Lund Studies in Geography, series B, no. 44.

Merchant, D.K. and G.L. Nemhauser. 1978a. A Model and an Algorithm for the Dynamic Traffic Assignment Problem. Transportation Science 12:183-99.

____. 1978b. Optimality Conditions for a Dynamic Traffic Assignment Model. Transportation Science 12:200-7.

Miller, H.J. 1991. Modeling Accessibility Using Space-Time Prism Concepts Within Geographical Information Systems. International Journal of Geographical Information Systems 5, no. 3:287-301.

____. 1999. Measuring Space-Time Accessibility Benefits Within Transportation Networks: Basic Theory and Computational Procedures. Geographical Analysis 31:187-212.

Miller, H.J. and Y.-H. Wu. 2000. GIS Software for Measuring Space-Time Accessibility in Transportation Planning and Analysis. GeoInformatica 4:141-59.

Okabe, A. and M. Kitamura. 1996. A Computational Method for Market Area Analysis on a Network. Geographical Analysis 28:330-49.

Plane, D.A. 1995. Urban Transportation: Policy Alternatives. The Geography of Urban Transportation. Edited by S. Hanson. New York, NY: The Guilford Press. 435-69.

Ran, B. and D.E. Boyce. 1996. Modeling Dynamic Transportation Networks: An Intelligent Transportation System Oriented Approach, 2nd revised edition. Berlin, Germany: Springer-Verlag.

Recker, W.W., M.G. McNally, and G.S. Root. 1986. A Model of Complex Travel Behavior Part 2: An Operational Model. Transportation Research A 19A:279-96.

Robles, J. and B.N. Janson. 1995. Dynamic Traffic Modeling of the I-25/HOC Corridor Southeast of Denver. Transportation Research Record 1516:48-60.

Tacken, M. 1997. Changing Travel Behaviour and Time Policy. Activity-Based Approach to Travel Analysis. Edited by D.F. Ettema and H.J.P. Timmermans. Oxford, England: Elsevier Science Ltd. 313-28.

Weibull, J.W. 1976. An Axiomatic Approach to the Measurement of Accessibility. Regional Science and Urban Economics 6:357-79.

Wu, Y.-H., H.J. Miller, and M.-C. Hung. 2001. A GIS-Based Decision Support System for Dynamic Network Congestion Analysis and Routing. Journal of Geographical Systems 3:3-24.

Address for Correspondence

Yi-Hwa Wu, University of Utah, DIGIT Laboratory, 260 S. Central Campus Dr. Room 270, Salt Lake City, UT 84112-9155. Email: wu.yi-hwa@geog.utah.edu.