Fuzzy Dynamic Traffic Assignment Model
Abstract
Traffic assignment is a popular topic in Transportation Engineering and has received much attention since 1950s’. Stochasticity and dynamic are two characteristics of traffic assignment. Since drivers always have no perfect information about traffic conditions, they choose their route based on perceived travel time. Traditional traffic assignment model can only capture the stochasticity and dynamic features of traffic assignment and cannot represent the fuzziness of driver’s perception over travel time. Thus, we presented a fuzzy dynamic traffic assignment model in this paper. By the definition of fuzzy link travel time and fuzzy path travel time, we use fuzzy shortest path algorithm to find the group of fuzzy shortest paths and assignment traffic to each of them proportionally to their memberships. We also compare the results of our proposed model with those from traditional Stochastic Dynamic Traffic Assignment (SDTA) model and it turns out that our model can generate more reasonable solution than SDTA.
1. Introduction and Motivation
2-1 Traffic Assignment
According to Meyer and Miller, there are four major stages in Urban Transportation Modeling System (UTMS)[1]. After the first three steps (Trip Generation, Trip Distribution, Modal Split), the urban area will be divided into different zones and traffic flow (OD demand) will be generated between any two zones, as shown in Fig.1.
Traffic Assignment (also referred as Route Choice by many researchers) is the last and crucial step of UTP and it will try to assign traffic flows between each origin-destination pair to actual links through the given road networks, as shown in Fig.2 (only one O-D pair was shown in this figure). Since the most important thing drivers care about is the travel time from origin to destination, the goal of traffic assignment is to achieve minimum travel time for every driver by assigning appropriate traffic flows to each link of the networks.
2-2 Traffic Assignment Methods
Starting from mid-1950s, many methods have been developed trying to solve the traffic assignment problem. In 1952, Wardrop proposed his first principle [2] that is the foundation for later traffic assignment solutions. This principle requires for used routes between a given origin-destination pair that the route cost equals the minimum route cost, and that no unused route has a lower cost. This principle was also referred as User Equilibrium (UE) by many researchers: in a user-equilibrated network no user can improve his travel time (cost) by unilaterally changing routes[2].
Although efficient algorithms can be formulated by using Wardrop’s first principle, his principle assumes a very unrealistic situation: all drivers are supposed to have perfect information and knowledge of the traffic conditions, which is not the case in real life circumstances. In real world, it is almost impossible for drivers to have perfect information on current traffic conditions. Therefore, drivers choose their route from origin to destination based on their perceived travel time rather than actual travel time. Another disadvantage of this principle is that it only considers the static case in which all traffic conditions, like traffic flow, speed, link travel time, etc., are presumed to be constant over all the time periods. However, in practice, all traffic conditions may change over time frequently.
In order to capture the stochastic and dynamic characteristics of traffic assignment problem, various traffic assignment models have been developed over the past several decades. In 1971, Dial described a flow-independent logit model for network loading [3]. Daganzo and Sheffi formulated a stochastic user-equilibrium route choice model in 1977[4]. Detailed reviews of these models were prepared by Boyce et al in 1988 [5]. At the same time, other practitioners focused on the dynamic feature of traffic assignment. Yagar, Hurdle, Merchant and Nemhauser were among the first to consider dynamic models for congested traffic networks[6]. Using optimal control theory, Ran and Shimazaki established traffic assignment models over a multiple origin-destination (O-D) networks[7] in 1989. Later on, Ran and Boyce integrated both the stochastic and dynamic traffic assignment models into one Stochastic Dynamic Route Choice Model (SDRCM) using Variational Inequality (VI) method in 1996[6].
Although these stochastic dynamic models can reflect the stochasticity and dynamic of traffic condition quite well, drivers’ perception of travel time cannot be simulated reasonably using these models. Hence, in 1987, Mirchandani and Soroush proposed a static probabilistic model in which driver’s perception over travel time was represented by actual travel time plus perceived error that follows a Gamma distribution [8]. In 2001, Liu and Ban extended Mirchandani’s model from static case into dynamic case [9].
However, using probabilistic distribution to simulate driver’s perception is questionable by intuition. Because driver’s perception of travel time, for example, “Beltline is fast,” “University Ave. is congested now,” is actually a linguistic term that has no equivalent exactly defined expression, a few researchers applied fuzzy logic into driver’s perception. Vincent Henn developed a fuzzy route choice model using fuzzy number ranking in 2000 and his model is somewhat similar to logit model mentioned above [10]. However, Henn only considered static case in his paper.
For the purpose of reflecting stochastic and dynamic features of traffic conditions and driver’s perception over travel time more realistically, we propose a Fuzzy Dynamic Traffic Assignment (FDTA) model in this paper. We first formulate the fuzzy perceived link travel time and fuzzy perceived path travel time in Section 2 and 3. Fuzzy shortest path algorithm will be discussed in Section 4. In Section 5, fuzzy traffic assignment method will be proposed. Some numerical examples will be given in Section 6. Conclusions and some important future work will be achieved in the last section.
2. Fuzzy Sets of Perceived Link Travel Time
Since the main concern of drivers traversing in the road networks is travel time, travel time of each link is the basic component for assigning traffic. The fuzzy sets of perceived link travel time we proposed here will be based on deterministic link travel time and actual link travel time.
2-1 Deterministic Link Travel Time
Deterministic link travel time is determined by deterministic features of the link, like link length, capacity, etc., and also the current deterministic traffic conditions, like traffic flow on this link. The following equation (1) is usually chosen for computing the deterministic link travel time [11]:
(1)
where and are coefficients; is the free flow travel time on link a; is its inflow rate; Ca is its capacity; xa,max is its maximum holding capacity.
2-2 Actual Link Travel Time
In practice, it is difficult to formulate the equation for actual link travel time due to the tremendous factors that may impact the actual link travel time greatly, such as different time period we focused on, road condition, traffic signal, congestion, incident, construction, weather, special events, and so on. As mentioned in Section 1, this property is called the stochastic characteristic of traffic condition (link travel time). However, in order to provide a reasonable approximation of actual link travel time, some researchers using certain distribution to represent the stochastic part of link travel time. Normal Distribution was applied in Liu and Ban’s paper [9] as shown in Equation (2) and (3):
(2)
(3)
where is actual link travel time and is its stochastic term.
In this paper, equation (1), (2), (3) is used to estimate actual link travel time.
2-3 Fuzzy Sets of Perceived Link Travel Time
Fig.3 Membership function for fuzzy sets of perceived link travel time
2-3-1 Fuzzy Sets for Perceived Link Travel Time
Based on the actual link travel time, we can construct fuzzy sets for perceived link travel time. In this paper, we use linguistic descriptions to represent the fuzzy sets. Due to driver’s experience of similar links, several linguistic descriptions of perceived link travel time can be formulated as below:
· “travel time is normal” --- NORMAL
· “link is congested” --- CONGESTED
· “link has incident” --- INCIDENT
· “link has construction” --- CONSTRUCTION
· “link has special event” --- SPECIALEVENTS
These fuzzy sets represent different level of traffic conditions and more sets may be added if necessary.
2-3-2 Membership Function for Fuzzy Sets of Perceived Link Travel Time
Generation of membership functions arouses a lot of interests in the literature. However, no standard method exists yet. The membership functions can be constructed based on a survey. To model driver’s perceptions, in most applications of fuzzy set theory, TFN (Triangular Fuzzy Numbers) or TrFN (Trapezoidal fuzzy Numbers) are usually used. In this paper, we simply use triangular function to form the membership functions of the fuzzy sets in 2-3-1. Fig.3 shows the membership functions for NORMAL and CONGESTED fuzzy sets (We only construct the fuzzy sets for NORMAL and CONGESTED in this paper, while fuzzy sets for other cases will be constructed in future work).
2-3-3 Fuzzy Rules for Perceived Link Travel Time
Only one simple rule will be used for these fuzzy sets of link travel time.
“If the travel time of link A is less than that of link B, link A will be chosen.”
This rule implies that if link A is faster than link B, then link A, instead of link B, will be used by the driver.
3. Fuzzy Sets of Perceived Path Travel Time
In crisp case, path travel time equals to the summation of the travel time of those links that construct this path [6]. However, for fuzzy case, we need to define how to formulate fuzzy sets of perceived path travel time based on fuzzy sets of perceived link travel time. Therefore, here we need to define fuzzy addition formulation.
In this paper, we use Dubois and Prade’s method [12]. Four steps are needed to perform fuzzy addition operation: Flattening, Decomposition, Operation * and Union. Here operation * is operation +. Generally, Dubois’s method is a little complex to compute. But for fuzzy sets with triangular membership function, it is quite simple.
As shown in Fig.4, if we represent fuzzy set S that has triangular membership as S(L, M, R), its membership function can be expressed as:
(4)
And from Dubois’s theory[12], the addition of fuzzy set S1(L1,M1,R1) and S2(L2,M2,R2) will be:
(5)
From equation (4) and (5), we can easily get fuzzy path travel time and its membership function given the fuzzy travel time of those links that form this path.
4. Fuzzy Shortest Path (FSP) Algorithm
Under crisp case circumstances, after we find the travel time for paths connecting origin and destination, we can find the shortest path and assign all traffic to this path. However, under fuzzy case, it is difficult to find only path that is the “shortest” in term of fuzzy travel time. Therefore, we need some method to find a group of fuzzy “shortest” paths and assign traffic to all of them based on their membership functions.
Several fuzzy shortest path algorithms have been proposed for solving the traffic assignment problem. In this paper, we use Blue’s method [13].
According to Blue’s classification, the road networks we are working on are actually a pure Type V fuzzy graph with crisp nodes and links as well as fuzzy weights (travel time). Denote G is a Type V fuzzy graph, We can find the fuzzy shortest paths using the following three steps.
Step 1: Converting Fuzzy Graph to Crisp Graph
We first construct two crisp graphs and that are identical to G, except that the link travel time is crisp. Link travel time for graph is:
(6)
where sup means least upper bound, and supp means support of fuzzy set.
Equation (7) is the link travel time for graph :
(7)
where inf means greatest lower bound.
Step 2: Find Shortest Path in Graph
Find the shortest path in graph . It is a traditional problem to find the shortest path in a crisp graph and various algorithms are available to solve it [14]. Denote K is the length of this shortest path.
Step 3: Calculate Membership
Denote is the set of paths in, connecting origin to destination and with the length less than K.
Denote S is a set of fuzzy paths in G. All paths in S are identical to those paths in respectively, except that the travel time is fuzzy. S is the set of fuzzy shortest paths found and will be assigned traffic. Calculate the membership of K for each of the fuzzy path in S.
5. Fuzzy Traffic Assignment
From 4, we can get the set of fuzzy shortest paths S. We assume that S has M elements as displayed below:
(8)
where pm is the fuzzy shortest path.
And the memberships of K in those fuzzy shortest paths are:
(9)
Further, we assume the traffic flow from origin O to destination D is . In this paper, we assign the traffic flow to these paths in S proportionally to their membership using equation (10):
(10)
For dynamic traffic assignment (DTA), we have to consider the flow propagation. In this case, equation (11) is used for this purpose [6]:
(11)
where p is the path a belongs to, is the subpath from a to destination D.
6. Numerical Examples
In this section, we present some numerical results from our experiments for a small test network using the proposed fuzzy DTA model. We will compare our solution quality with that obtained from dynamic stochastic traffic by Liu and Ban [9] to illustrate if fuzzy DTA can generate reasonable results.