Behavioral Modeling of Network Traffic: Integrating Route Choice and Traffic Assignment Julie Chou Samer Takriti Steve Underwood Department of Industrial and Operations Engineering University of Michigan Ann Arbor, Michigan 48109-2117 November 1993 Technical Report 93-29

Behavioral Modeling of Network Traffic: Integrating Route Choice and Traffic Assignment Julie Chou Samer Takriti Steve Underwood November 15, 1993 Abstract Most of the current traffic modeling packages assume that drivers follow a shortest path to go from an origin to a destination. This approach has been adopted because of its simplicity and convenience. Unfortunately, in real life, drivers tend to use some other routes according to individual decision-making processes. These decisions depend on many factors such as travel time, number of intersections, quality of roads, traffic lights, and other attributes. Therefore, the shortest path assumption cannot reflect drivers' behavior in real life and nmax lead to biased results. The lack of a realistic model that can be used efficiently on computers is the real motivation for this project. In this paper, our objective is to develop a practical traffic model that reflects the route-choice process with greater accuracy. This new model would improve the existing driver's behavior model in dynamic network simulators. 1 Introduction Network-level traffic models and simulations generally assume drivers follow a shortest path to go from an origin to a destination. Shortest-path routing has been adopted over the years 1

because of its simplicity, computational efficiency, and linkage with algorithms for generating equilibrium in static traffic-assignment models. However, in real life, driver's routes are likely to deviate from optimal shortest paths in significant ways. Empirical research on route behavior shows that drivers use numerous criteria in formulating a route: travel time, number of intersections, quality of roads, traffic lights, and other factors. Drivers' experiences, habits, cognitive limits, and other behavioral considerations may also produce variations in route selection. Viewed in this light, one can see that the shortest path criterion is indeed an unrealistic abstraction of individual driver behavior, and when aggregated at the network level may result in an inaccurate representation of traffic. The purpose of this paper is to present a behavior-based dynamic traffic-assignment approach that combines an individual driver-routing module with a dynamic-traffic simulation module. Vehicles are routed in a manner that more accurately reflects the stochastic nature of individual route selection. Routing decisions are then aggregated in a dynamic simulation of network traffic flow. The result of our effort is a behavior-based traffic assignment that provides a more realistic traffic-loading baseline. Section two of this paper gives a review of microsimulation assignment. Section three classifies the drivers on the road into two categories: familiar and unfamiliar. In section four, the unfamiliar driver's behavior is studied in more detail. Discrete choice models are presented in section five. In section six, a simple method for estimating the utility cf a path is presented. The probit model is introduced in section seven. Sections eight anc nine link the ideas discussed in previous sections to develop an applicable model that is superior to the driver's behavior models used currently in simulators. Finally, some numerical results are presented in section ten. 2

2 Review of Microsimulation Assignment As a first step toward dynamic traffic assignment, researchers have developed network traffic simulators, which assign vehicles, or packets of vehicles, to links in accordance with some vehicle-routing logic. Early simulations of this type include CONTRAM [10], SATURN [8], and INTEGRATION [16]. Dynamic network traffic models generally employ some form of shortest-route algorithm to determine the paths of vehicles entering the network. For example, in CONTRAM, packets of vehicles enter the network in accordance with specified departure times. Upon entry, the packets are assigned to a shortest path from their entry point to their destination. The packet then follows this path for a designated period of time. The assignment process is then repeated and the packet is reassigned to a new shortest path based on current link times. A similar approach was used in the original version of INTEGRATION to simulate vehicles with route-guidance systems. Guided vehicles have the ability to periodically reassign themselves in response to up-to-date traffic conditions. One of the benefits of this approach is that vehicles are routed according to prevailing traffic conditions, including signal effects, queues and spillback. SATURN departs from the responsive assignment approach of CONTRAM and INTEGRATION and uses an iterative equilibrium approach where link flows are determined through a modified capacity-restrained assignment procedure. The drawback of this approach is that the assignment does not take into account signal effects, queues and spillback. Also, the vehicles cannot respond to incidents or other unexpected traffic occurrences while enroute. The problem with all three approaches cited here is that the vehicle routes do not accurately capture the route-selection dynamics described in the empirical research. To be fair, our descriptions of SATURN, CONTRAM, and INTEGRATION captures their state of development at the time they were introduced, or shortly thereafter. Many improvements have been made to these models and their offspring in subsequent years. In 3

this study, INTEGRATION is used to simulate the traffic in the networks of section ten. 3 Classes of Drivers on the Road Drivers can be divided into different classes according to individual behavior, objective of the trip, and knowledge of the area. For example, some drivers prefer a scenic route whilst others are under time pressure. The same driver may change his behavior depending on the goal of the trip: vacation, business, etc. In order to simplify the study, drivers are classified into two different categories: familiar and unfamiliar. The familiar driver is the commuter who uses a route to go to his work and back every day. This type is the most important because it is associated with the majority of traffic on the road during peak hours. By unfamiliar driver, we mean someone who does not know the area or has very little knowledge of the network and, in most cases, uses a map to get to his destination. The percentage of these drivers is relatively small compared with the familiar drivers. The unfamiliar drivers are of special importance since they form the base for the study of familiar drivers. The following section describes the unfamiliar driver's behavior and proposes a model to approximate it. 4 A Model for the Unfamiliar Driver's Behavior Unfamiliar drivers share many characteristics. For instance, they tend to plot the entire path of their trip before departing and stick to this predetermined route. Since this driver, in most cases, is using a map to design his trip, only a few paths are considered. The rest of the feasible paths are ignored because he assumes that they are inferior to the ones chosen. After finding the set of alternative paths, the driver evaluates each path and then chooses the best one. Obviously, different drivers have different evaluation techniques, hence, a different best path. The driver cannot evaluate exactly all the parameters of his trip. For example, 4

the travel time depends on speed restrictions, congestion, number of available lanes, number of traffic lights, and some other undetermined factors. The model has to reflect all of these factors to a reasonable degree. The process of approximating the unfamiliar driver's behavior has two stages. The first one is to generate the set of possible routes. A method is applied to narrow down the vast number of route possibilities, leaving only a few candidates to be considered. Once a set of options has been identified, it is necessary to measure the relevant attributes of these options and compare them. In the second stage, a discrete choice-model is applied to compute the probability of choosing an alternative based on its desirability. Section five outlines discrete choice models and how they can be used to compute these probabilities. 5 Discrete Choice-Models The hypothesis of discrete choice models is that an individual's preference towards each alternative can be represented by a utility. A utility is a function of the alternative's attributes and the decision maker's characteristics. Many of the attributes that influence an individulal's utility cannot be observed and thus are treated as random. For example, the real travel tilme froml origin to destination is usually not obtainable by drivers. The perceived travel timie can be assnumed to be a random variable with a given distribution. Therefore, choice niodels give only the probability with which the alternatives are chosen, not the choice itself. Let.4 represent a given sent a it of K alternatives and Uk = Vk+ k be the utility of alternative k.1 Here,'k is a constant and Ek is a random variable with a given distribution. The decision niaker tendls to choose the alternative that yields the highest utility. The probability that alternative k will be chosen is then the probability that Uk is higher than the utility of any'The svnymbol is used to indicate that a variable is random or undeterministic. 5

other alternative. Therefore, Pk = P{iik > iii, V A/{k}} PP{vk+ ek > max v + e}} VIEA/{k} where, Pk= 1 and Pk > 0, Vk E A keA The most commonly used driver-behavior model is the logit model which is developed using the previous equations. In logit formulation, the utilities of different alternatives are assumed to be independent Gumbel-distributed random variables. Hence, the choice probability of a given alternative can be obtained by some simple calculations. The independence assumption is a major disadvantage since, in general, the paths considered by a driver overlap. Another discrete choice model is probit where a more realistic distribution for the random utilities is used. Also, the dependence between the random terms is taken into account, which makes this model superior to the logit model. Later in this paper, the probit model is studied and then applied to some traffic networks. Throughout the previous discussions, the utility was assumed known. In the following section, a simple method for estimating a route's utility.is proposed. 6 Utility Estimation Many factors affect the driver's preference towards a particular path. For analytical simplicity, assume that travel time and number of turns dominate other factors. Also, it is assumed that the utility is linear in these attributes; i.e., ii = -t - yn. y > 0 is a scalar obtainable from experimental studies. n is the number of turns encountered on the path and considered to be a deterministic attribute since the driver can obtain its value from the map. Note that 6

u < 0 and that a larger ii value means a shorter travel time, a fewer turns or both. The only random term in the utility function is the travel time, which cannot be estimated exactly. Denote the perceived travel time on link c by lc. Let lc be the mean of the random variable l, i.e., 1, = E(lC). I can be chosen as the free-flow travel time on c. Since, in general, variance increases with larger travel times, it is reasonable to assume that Var(lc) is cal, where, a > 0 is a scalar.2 The perceived travel time on any path k is given by the relationship tk = Ec lcc,k Here, I is the indicator function; i.e., I, 1 if link c is on path k Ic,k - 0 Otherwise One can compute the mean and variance of the random variable tk in terms of the indicator function: E(tk) = ElcIc,k C Var(ik) = EVar(lc)Ik C = QE(tk) The variance equality is justified since lc's are independent random variables. Therefore, E(iik) = E(-k - 7nk) = k + E(Ek) Var(ik) = aE(tk) = Var(k ) Given two paths k1 and k2, the covariance between the utility of kl and that of k2 is: Cov(Ufk,, ik2) -= EZIc,klIc,k2 C 2Note that Var(lc) should be proportional to I2. The linear relation is assumed to simplify the calculations. Although the variance has units of time x time implying a to have units of time, a is taken as a dimensionless quantity for numerical purposes. 7

= Ctkl,k2 where, tklik2 is the mean travel time on the common segment between k1 and k2. After computing the expected values and variances, one can assume that the utility follows a suitable probabilistic distribution. Then, the probability of selecting a path can be computed accurately. Using a normally distributed utility leads to the probit model, which is introduced in the following section. 7 Multinomial Probit Model Following many other statistical models, it may be natural to assume that the random error term of each utility is normally distributed with mean zero; i.e., e N(O, aE(t)), hence, u i N(-E(t) - 7yn, aE(t)). This implies that the joint density function of these error terms is a multivariate normal function. This is the underlying assumption of the probit model. As in section five, the likelihood that a particular alternative will be chosen is given by the probability that its utility is the highest in the choice set. With the probit model, however, this probability cannot be expressed analytically, since the cumulative normal distribution function does not have a closed form. The calculations of probit choice's probabill'v, in the presence of more than two alternatives, are not straightforward. The choice probability can be estimated by using either an analytical approximation or a Monte Carlo simulation. A widely used analytical method is successive approximation. It is based on approximating the distribution of the maximum of two normally distributed random variables by another normal random variable. For example, to find PK=IIAII one needs to approximate maxi{i,u 2} by a normally distributed random variable, call it a,. Then, approximate max{U3, &} by 2, and so on. In the final step, max{zil,..., uK-l is approximated by UK-2. PK can be obtained from AK-2 by some integration methods. The successive approximation is fully described in appendix A. 8

The main advantage of the probit model is its ability to account for dependence between the utilities of different routes. On the other hand, computational costs for problems of the size encountered in network analysis are very high. Furthermore, the accuracy of this method deteriorates as the number of alternatives increases. In the following section, the probit model is used in conjunction with the previously presented ideas to develop an algorithm that distributes unfamiliar drivers on the network according to the utility of each path. 8 A Route-Choice Algorithm for Unfamiliar Drivers In traffic modeling, it is convenient to introduce the notion of origin-destination pairs, or simply O-D pairs. The network is assumed to have source nodes, or origins, where the flow is generated, and sink nodes, or destinations, where the flow is absorbed. Each vehicle has a predetermined destination, which cannot be changed during the trip. Hence, the only paths in the network that need to be considered are these connecting the O-D pairs.3 This assumption simplifies the study and makes it more efficient on a computer. Here is a description of the route-choice algorithm for unfamiliar drivers: * Initialization. Set i = 1.4 Using the free-flow travel time, compute the mean travel time, tk = E(tk), for all paths k. * General Step. 1. Find the set of the K shortest paths connecting each O-D pair j.5 Let this set be Aj. 3From here on, the word path refers to a path connecting an O-D pair. 4i is a counter. It links the unfamiliar-driver algorithm to the familiar-driver algorithm presented in the following section. 5A practical range of K is 10 to 20. Shortest-path algorithms are described in [12]. 9

2. For each path k e A, compute the mean of its utility, ui = -t - yk, and the variance, ate. 3. From each set Aj, select the M paths with the highest average utilities.6 4. For each O-D pair j, compute the probability of selecting path k, Pk, as described in appendix A. The previous probabilities can be used in any dynamic traffic simulation-package to distribute cars on the network in a realistic manner. 9 A Model for Familiar Driver's Behavior Any driver starts as an unfamiliar driver then, using his daily experience, adjusts his route choice to maximize his utility. Here is the algorithm used: * Initialization. Set P2k = 0 for all paths k. Set i = 1. Using the free-flow travel time, compute the mean travel time, tk = E(tk), for all paths k. * General Step. 1. Perform the general step of the unfamiliar-driver algorithm described in section eight. 2. If I Pk - Pk-' 1< 6 for all paths k, stop. Pk represents the distribution of familiar drivers over the network. 3. Distribute drivers over different paths using Pk and then run a simulation to get the average travel time on each path tk. 4. Update tk1 = jwt\ + (1 - w)tk, 0 < w < 1. w is an exponential smoothing factor. 5. i i + 1. Go to 1. 6MA = 3 is used in this study as recommended by [9] and [13]. 10

6 represents the maximum error in the computed probabilities. A key question is whether this method converges to a steady state or not. More research should be done to find the necessary and sufficient conditions for convergence. In case of cycling, one may need to increase the number of paths considered or the value of 6. 10 Numerical Results In order to test the algorithm of section eight, two traffic networks were used. The traffic on each of them was simulated using INTEGRATION. All drivers were considered to be unfamiliar drivers. The parameters -y and a were set to 0.5 and 1.5 respectively. These two values were chosen according to personal experience. The networks were loaded with cars during the first 26 minutes. The number next to each arc on the graph represents the length of the link in kilometers in both directions. The simulation was run twice for each network. In the first run, drivers followed the shortest path to travel from their origin to destination. A few arcs were used by the vehicles. This cllaused immense congestion in these areas, leaving the rest of the network with zero flow throughout the simulation. In the second run, the model described in section eight was used to assign drivers to the alternative routes in the network. The number of arcs used here was larger than had been used previously. The cars were distributed more realistically over the network and this resulted in less congestion. Figure 1 shows the first network. The traffic flow from 4 to 8 is 840 cars/hour and from 9 to 1 is 851 cars/hour. The average travel time from 4 to 8, T4,8, using shortest path is 3.88 minutes. Using the algorithm of section eight, T4,8 is 2.78 minutes. T9,1 is 4.15 minutes wliel shortest path is used and it is 3.44 minutes using the algorithm. The average travel times in the network are 4.02 and 2.98 minutes. The second network is shown in figure 2. The traffic flow from 1 to 7 is 1020 cars/hour and frolm 10 to 8 is 1000 cars/hour. T1,7 is 6.26 minutes when using the shortest path and 11

14 10 1 14 10 10 10 Figure 1: First Network 4.43 minutes when the algorithm is applied. T10,8 is 13.12 minutes and 8.67 minutes. The average travel times in the network are 9.71 and 6.56 minutes. 11 Conclusion Two algorithms for modeling the behavior of unfamiliar and familiar drivers are introduced. Both of them generate a choice set and then use the probit model to distribute drivers over the network. A simple method for estimating the utility of each alternative is presented. Simulation results indicate that our model gives a more realistic distribution of the cars than the shortest path assumption, and therefore decreases the travel time in the network. In order to improve the performance of the algorithms, more research should be done on the utility function and its estimation. A survey of the paths chosen by drivers in a real network would lead to a better understanding of their behavior. Considering more classes of drivers would improve the model. 12

101 3 2 2 2 / 3 ^ 1 Figure 2: Second Network 12 Appendix A Successive Approximation Method In this section. the details of computing the probability of choosing a path are presented. It is convenient to use the notations introduced in section six: t = E(t) and v = -E(t) - yn. The probit model is used; i.e., e ~ N(O, cE(t)), and the utility is obtained as in section seven; i.e., 11 N(-E(t) - yn, aE(t)). No other assumptions are made, hence, the results presented here are general. Given two paths with utilities u1 and u2, one needs to approximate the probability distribution of max{ul, u2} by a normal distribution. Let = ca(t +t2 - t12) V1 - V2 r -- Y/= v1(r) + v2~(-r) + /3-/(T) 13

p= (v + l-at1)(r) + (v2 + cxt2)~(-r) + (vl + v2)/3(r) where, 4(x) = -x2/2 (x) = J (y)dy:-00 then, the distribution of max{ul,u2} is approximated by N(v, - v2). The covariance between max{ui, u2} and the utility U3 of a third path is given by the following relationship: I -- ^ Cov(max{ul, U2}, U3) = t (t134(r)+ t23s(-r)) t3(^ - V2 ) For example, given three paths, the probability of selecting path 3, P3, is computed as follows: P3 = P(u3 > max{u1,u2}) (3 -- at3 + (-2) - 2Cov(max{u, u2}, u3)/at 3(p- 2) The same procedure can be used to compute Pi and P2. References [1] Antonisse R. W., Daly A. J., and Ben-Akiva M., "Highway Assignment Method Based on Behavioral Models of Car Drivers' Route Choice", Transportation Rescac h Record 1220, 1989. 14

[2] Arnott R., DePalma A., and Lindsey R., "Departure Time and Route Choice for the Morning Commute", Transportation Research, Vol. 24B, No. 3, pp. 209-228, 1990. [3] Ben-Akiva M., Bergman M. J., Daly A. J., and Ramaswamy R., Modeling Inter Urban Route Choice Behavior, Ninth International Symposium on Transportation and Traffic Theory, VNU Science Press, pp. 299-330, 1984. [4] Case E. R., Van Aerde M., and Krage M., "Supporting Routines for Modeling the Traffic Responsive Features of the Travtek Systems Using Integration", Vehicle Navigation and Information Systems Conference Proceedings, Society of Automotive Engineers, Dearborn, Michigan, pp. 681-691, 1991. [5] Chang G. L. and Mahmassani H. M., "Travel Time Prediction and Departure Time Adjustment Behavior Dynamics in Congested Traffic Systems", Transportation Research, Vol. 22B, No. 3, pp. 217-332, 1988. [6] Dijkstra E. W., A Note on Two Problem in Connection to Graphs, Numerische, Mathematik, Vol. 1, pp. 269-271, 1959. [7] Dow R. D. C. and Van Vliet D., "Capacity-Restrained Road Assignment: Two Equilibrium Methods", Traffic Engineering and Control, Vol. 20, No. 6, pp. 299-303, 1979. [8] Hall NI. D., Van Vliet D., and Willumsen L. G., "SATURN: A Simulation-Assignment Model for the Evaluation of Traffic Management Schemes", Traffic Engineering and Control, Vol. 21, pp. 168-177, 1980. [9] Jansen C. F., "Ontwikkeling Van een Verkeersmodel Voor Zuidwest Friesland", Verkeerskunde, vol. 36, No. 5, pp. 225-226, 1984. [10] Leonard D. R., Gower P., and Taylor N. B., CONTRAM: Structure of the Model, Transport and Road Research Laboratory, Report 178, 1989. 15

[11] Mahmassani H. S. and Chang G. L., "Experiments With Departure Time Choice Dynamics of Urban Commuters", Transportation Research, Vol. 20B, No. 4, pp. 297-320, 1986. [12] Murty K. G., Network Programming, Prentice Hall, Englewood Cliffs, New Jersey 07632, 1992. [13] Stern E., and Leiser D., "Levels of Spatial Knowledge and Urban Travel Modeling", Geographical Analysis, Vol. 20, No. 2, pp. 140-155, 1988. [14] Van Aerde M., Modeling of Traffic Flows, Assignment and Queueing in Integrated Freeway/Traffic Signal Networks, Ph. D. Thesis, Department of Civil Engineering, University of Waterloo, Waterloo, Canada, 1985. [15] Van Aerde M. and Krage M., Overview of the General Motors/Queen Traffic Simulation Activities Related to the Travtek Experiment in Orlando, Florida, Presentation for the University of Michigan Intelligent Vehicle-Highway System Speaker Series, Program in Intelligent Vehicle-Highway Systems, University of Michigan, Ann Arbor, 1991. [16] Van Aerde M. and Yagar S., "Dynamic Integrated Freeway/Traffic Signal Networks: A Routing-Based Modeling Approach", Transportation Research, Vol. 22A, No. 6, pp. 445-453, 1988. [17] Whiting P. D. and Hillier J. A., "A Method of Finding the Shortest Route Through a Road Network", Operations Research Quarterly, Vol. 11(1/2), pp. 37-40, 1960. 16