# Route Choice Model Considering Generalized Travel Cost Based on Game Theory

Authors: Feng Yu-qin; Leng Jun-qiang; Xie Zhong-Yu; Zhang Gui-e; He Yi
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

This paper aims at testing the influence of emission factors on travelers’ behavior of route choice. The generalized travel cost is defined as the linear weighted sum of emission factors, travel time, and travel time reliability. The relational model of exhaust volume and traffic volume is established using the BPR (Bureau of Public Road) function to calculate the cost of travel regarding emission. The BPR function is used to measure the road segment travel time, while the reliability is used to quantify the cost of travel time fluctuation. At last, the route choice model considering the generalized travel cost is established based on the game theory. The calculating and analyzing of results under a miniature road network show that the weight coefficient of travel cost influences the travelers’ behavior of route choice remarkably and the route choice model which takes emission into account can reduce the exhaust of road network effectively, approximately 11.4% in this case.


---

## Body

## 1. Introduction

How to reduce exhaust emission has become a very urgent subject as the number of automobile grows rapidly in China. At the moment, research on energy saving and emission reduction about the vehicle itself has been relatively mature, while few studies were conducted concerning this problem from the perspective of traffic management. The influence of emission factors on travelers’ behavior of route choice will be studied in this paper from the aspect of traffic management, which can provide information about vehicle emission for traffic managers in order to decrease energy consumption and emission to some extent.Travel time cost and fuel consumption are usually considered in travel cost estimation [1–3]. However, in general, former route choice models only took travel time cost into consideration. The researches on the relationship between route choice model and exhaust emission are few [4, 5]. And there is only information about route length and travel time in the traffic guidance system and no other valuable information concerning emission. Travel cost was usually described using travel time which was presented by the BPR function.There are some route choice models of travelers such as stochastic user equilibrium model and elastic demand equilibrium model [6]. As the prisoner’s dilemma games and its extensions have been studied frequently [7–10], the paly game is also used in the traffic distribution [11]. However, their BPR functions do not well reflect different demands of travelers in choosing routes, because emission has gradually become a factor affecting route choice. And trip demand objectives are not single and are often mutually contradictory, for example, shorter travel time, higher reliability, and security [12, 13]. Hence, generalized travel cost, which took emission into consideration, was studied in the paper based on the emission model for road segment. Then, the effect of route choice behavior and cost factors on route choice of travelers was discussed.


## 2. Generalized Travel Cost Considering Emission

Travelers are paying more attention to the emission problem in route choice besides the consideration of travel time and its fluctuation, because of the aggravation of the energy crisis and the pressing need of environmental protection. It is the ideal goal of travelers to reduce emission, decrease travel time, increase reliability, and so forth [14]. However, these goals often lead to contradiction and conflicts. Travelers are always seeking compromise in pursuing them. Therefore, this paper is based on the generalized travel cost of the above factors. The generalized travel cost is defined as the linear weighted sum of travelers’ exhaust emission factor, travel time, and travel time reliability. So the generalized travel cost function may be represented as
(1)ca=w1lafa(·)+w2Ta+w3γ(Ta),
where ca is the generalized travel cost in road segment a;fa(·) represents the emission factor on road segment a, (g/km); la is the length of road segment a (km); Ta is the travel time of road segment a (s); γ(Ta) is the travel time fluctuation of road segment a; w1, w2, and w3 are the weight of exhaust emission, travel time, and travel time reliability in the generalized travel cost, respectively. These three weight coefficients may reflect travelers’ attitude towards hazards. The larger w1 is, the smaller w2 and w3 will be, which means travelers pay more attention to emission, tending to consider emission as a route choice criterion. Each weight can be determined on the basis of SP (stated preference) survey.The generalized travel cost of travelers can be represented as(2)ckw=∑a∈Acaδakw,
where ckw is the generalized travel cost of route k in OD pair w; δakw is a 0-1 variable; if road segment a lies in the route k of the OD pair w, then δakw=1; otherwise δakw=0.


### 2.1. Quantification of Travel Cost Index

#### 2.1.1. Travel Time

The BPR (Bureau of Public Roads) travel time function proposed by the United States Federal Highway Administration is the most representative achievement in the research of travel time model. The most significant influence of the model is on the field of traffic planning and it is most widely used in this field. It was initially used in the highway network planning, later in urban road network planning [15]. The mathematical expression is
(3)Ta=ta[1+β(xaCa)n],
where Ta is the travel time of road segment a, (s); ta is the free flow travel time of road segment a, (s); xa is the traffic flow of road segment a, (pcu/h); Ca is the traffic capacity of road segment a, (pcu/h); β, n are the model parameters; the recommended values are β=0.15,n=4 in highway network application.


#### 2.1.2. Travel Time Fluctuation

In 1991, Asakura and Kashiwadani [16] presented the travel time reliability concept to reflect travel time fluctuation. Travel time reliability is defined as the probability that a trip may be completed within a specified time under a certain LOS (level of service) demand, which is a measure of travel time stability index and describes the flexibility of road network in stochastic traffic conditions. In this paper, the travel time reliability is defined as
(4)R(Ta)=P(Ta≤ta+Δ′),
where Δ′ is the acceptable threshold of buffer time; it usually takes 5%, 10%, 15%, or 20% of the free travel time. For the simple reason that people have different tolerance degrees in various traffic congestions in different areas, Δ′ may be determined through the SP investigation; other parameters have the same meanings as previously mentioned. Substitute (3) into (4)
(5)Ra(Ta)=P[Ca≥xa(taβΔ′)1/n].
Due to the capacity Ca is a random variable, the distribution function FCa(x) can be obtained by field observation; it may be written as
(6)Ra(Ta)=1-FCa(xa(taβΔ′)1/n),r(Ta)=1-Ra(Ta)=FCa((taβΔ′)1/nxa).
In the formula, r(Ta) is the probability of road segment a not meeting the requirement of travel time reliability; it is deemed that r(Ta) is the negative utility of travel time fluctuation.


#### 2.1.3. Exhaust Emission Model

Average speed of vehicles is one of the most important factors that affect the exhaust emission. Margiotta [17] believed that emission factors were sensitive to speed and put forward the relational model between them. Wang et al. [18] calculated emission factors of vehicles under different average speeds using the modified MOBILE model based on the field data in Nanjing and then carried out a curve fitting taking emission factors as the dependent variable and the average speed of motor vehicle as the independent variable. The polynomial computational model for traffic exhaust emission can be written as follows:
(7)fa=b0+b1va+b2va2+b3va3,
where fa represents emission factor of passenger car on road segment a, (g/km); va is the average speed of vehicles on road segment a, (km/h),  0≤va≤90; b0, b1, b2, and b3 are regression coefficients.Average speed of vehicles on a road segment can be calculated by travel time as follows, for the average speed of the vehicle equals road length divided by average travel time:(8)va=laTa=lata[1+β(xa/Ca)n],
where la is the length of road segment, (km); other parameters are of the same meaning as mentioned previously. The volume of exhaust emission can be expressed as the function of the length of road segment, traffic volume, and its capacity.Pluging (8) into (7), we can get the following model of the traffic volume and exhaust emission:
(9)fa=b0+b1(lata[1+β(xa/Ca)n])+b2(lata[1+β(xa/Ca)n])2+b3(lata[1+β(xa/Ca)n])3.


### 2.2. Weight of Cost Index

Weight of different cost index may be determined on the basis of SP data, using the relative comparison method. First, make all indexes a square matrix. Second, compare every two indexes and score them, using[0,1] scoring method. Third, sum up each index score and do the normalization. The weight of index i may be expressed as
(10)wi=∑j=1naij∑i=1n∑j=1naij,
where aij is the importance of index i relative to index j. Other parameters have the same meanings as mentioned previously.


### 2.3. Nondimensionalization of Indexes

To make different dimensional evaluation index comparable and additive, the method of mathematical transformation was used to eliminate the influence of index dimension in generalized travel cost. This paper uses linear proportion method to process nondimensionalization. The formula is(11)yi=xixi′,
where xi is the sample value; yi is the dimensionless results of xi; and xi′ is the minimum, maximum, or average value of the sample value.


## 2.1. Quantification of Travel Cost Index

### 2.1.1. Travel Time

The BPR (Bureau of Public Roads) travel time function proposed by the United States Federal Highway Administration is the most representative achievement in the research of travel time model. The most significant influence of the model is on the field of traffic planning and it is most widely used in this field. It was initially used in the highway network planning, later in urban road network planning [15]. The mathematical expression is
(3)Ta=ta[1+β(xaCa)n],
where Ta is the travel time of road segment a, (s); ta is the free flow travel time of road segment a, (s); xa is the traffic flow of road segment a, (pcu/h); Ca is the traffic capacity of road segment a, (pcu/h); β, n are the model parameters; the recommended values are β=0.15,n=4 in highway network application.


### 2.1.2. Travel Time Fluctuation

In 1991, Asakura and Kashiwadani [16] presented the travel time reliability concept to reflect travel time fluctuation. Travel time reliability is defined as the probability that a trip may be completed within a specified time under a certain LOS (level of service) demand, which is a measure of travel time stability index and describes the flexibility of road network in stochastic traffic conditions. In this paper, the travel time reliability is defined as
(4)R(Ta)=P(Ta≤ta+Δ′),
where Δ′ is the acceptable threshold of buffer time; it usually takes 5%, 10%, 15%, or 20% of the free travel time. For the simple reason that people have different tolerance degrees in various traffic congestions in different areas, Δ′ may be determined through the SP investigation; other parameters have the same meanings as previously mentioned. Substitute (3) into (4)
(5)Ra(Ta)=P[Ca≥xa(taβΔ′)1/n].
Due to the capacity Ca is a random variable, the distribution function FCa(x) can be obtained by field observation; it may be written as
(6)Ra(Ta)=1-FCa(xa(taβΔ′)1/n),r(Ta)=1-Ra(Ta)=FCa((taβΔ′)1/nxa).
In the formula, r(Ta) is the probability of road segment a not meeting the requirement of travel time reliability; it is deemed that r(Ta) is the negative utility of travel time fluctuation.


### 2.1.3. Exhaust Emission Model

Average speed of vehicles is one of the most important factors that affect the exhaust emission. Margiotta [17] believed that emission factors were sensitive to speed and put forward the relational model between them. Wang et al. [18] calculated emission factors of vehicles under different average speeds using the modified MOBILE model based on the field data in Nanjing and then carried out a curve fitting taking emission factors as the dependent variable and the average speed of motor vehicle as the independent variable. The polynomial computational model for traffic exhaust emission can be written as follows:
(7)fa=b0+b1va+b2va2+b3va3,
where fa represents emission factor of passenger car on road segment a, (g/km); va is the average speed of vehicles on road segment a, (km/h),  0≤va≤90; b0, b1, b2, and b3 are regression coefficients.Average speed of vehicles on a road segment can be calculated by travel time as follows, for the average speed of the vehicle equals road length divided by average travel time:(8)va=laTa=lata[1+β(xa/Ca)n],
where la is the length of road segment, (km); other parameters are of the same meaning as mentioned previously. The volume of exhaust emission can be expressed as the function of the length of road segment, traffic volume, and its capacity.Pluging (8) into (7), we can get the following model of the traffic volume and exhaust emission:
(9)fa=b0+b1(lata[1+β(xa/Ca)n])+b2(lata[1+β(xa/Ca)n])2+b3(lata[1+β(xa/Ca)n])3.


## 2.1.1. Travel Time

The BPR (Bureau of Public Roads) travel time function proposed by the United States Federal Highway Administration is the most representative achievement in the research of travel time model. The most significant influence of the model is on the field of traffic planning and it is most widely used in this field. It was initially used in the highway network planning, later in urban road network planning [15]. The mathematical expression is
(3)Ta=ta[1+β(xaCa)n],
where Ta is the travel time of road segment a, (s); ta is the free flow travel time of road segment a, (s); xa is the traffic flow of road segment a, (pcu/h); Ca is the traffic capacity of road segment a, (pcu/h); β, n are the model parameters; the recommended values are β=0.15,n=4 in highway network application.


## 2.1.2. Travel Time Fluctuation

In 1991, Asakura and Kashiwadani [16] presented the travel time reliability concept to reflect travel time fluctuation. Travel time reliability is defined as the probability that a trip may be completed within a specified time under a certain LOS (level of service) demand, which is a measure of travel time stability index and describes the flexibility of road network in stochastic traffic conditions. In this paper, the travel time reliability is defined as
(4)R(Ta)=P(Ta≤ta+Δ′),
where Δ′ is the acceptable threshold of buffer time; it usually takes 5%, 10%, 15%, or 20% of the free travel time. For the simple reason that people have different tolerance degrees in various traffic congestions in different areas, Δ′ may be determined through the SP investigation; other parameters have the same meanings as previously mentioned. Substitute (3) into (4)
(5)Ra(Ta)=P[Ca≥xa(taβΔ′)1/n].
Due to the capacity Ca is a random variable, the distribution function FCa(x) can be obtained by field observation; it may be written as
(6)Ra(Ta)=1-FCa(xa(taβΔ′)1/n),r(Ta)=1-Ra(Ta)=FCa((taβΔ′)1/nxa).
In the formula, r(Ta) is the probability of road segment a not meeting the requirement of travel time reliability; it is deemed that r(Ta) is the negative utility of travel time fluctuation.


## 2.1.3. Exhaust Emission Model

Average speed of vehicles is one of the most important factors that affect the exhaust emission. Margiotta [17] believed that emission factors were sensitive to speed and put forward the relational model between them. Wang et al. [18] calculated emission factors of vehicles under different average speeds using the modified MOBILE model based on the field data in Nanjing and then carried out a curve fitting taking emission factors as the dependent variable and the average speed of motor vehicle as the independent variable. The polynomial computational model for traffic exhaust emission can be written as follows:
(7)fa=b0+b1va+b2va2+b3va3,
where fa represents emission factor of passenger car on road segment a, (g/km); va is the average speed of vehicles on road segment a, (km/h),  0≤va≤90; b0, b1, b2, and b3 are regression coefficients.Average speed of vehicles on a road segment can be calculated by travel time as follows, for the average speed of the vehicle equals road length divided by average travel time:(8)va=laTa=lata[1+β(xa/Ca)n],
where la is the length of road segment, (km); other parameters are of the same meaning as mentioned previously. The volume of exhaust emission can be expressed as the function of the length of road segment, traffic volume, and its capacity.Pluging (8) into (7), we can get the following model of the traffic volume and exhaust emission:
(9)fa=b0+b1(lata[1+β(xa/Ca)n])+b2(lata[1+β(xa/Ca)n])2+b3(lata[1+β(xa/Ca)n])3.


## 2.2. Weight of Cost Index

Weight of different cost index may be determined on the basis of SP data, using the relative comparison method. First, make all indexes a square matrix. Second, compare every two indexes and score them, using[0,1] scoring method. Third, sum up each index score and do the normalization. The weight of index i may be expressed as
(10)wi=∑j=1naij∑i=1n∑j=1naij,
where aij is the importance of index i relative to index j. Other parameters have the same meanings as mentioned previously.


## 2.3. Nondimensionalization of Indexes

To make different dimensional evaluation index comparable and additive, the method of mathematical transformation was used to eliminate the influence of index dimension in generalized travel cost. This paper uses linear proportion method to process nondimensionalization. The formula is(11)yi=xixi′,
where xi is the sample value; yi is the dimensionless results of xi; and xi′ is the minimum, maximum, or average value of the sample value.


## 3. Game Theory Model

The theory of games is a study about the interaction between rational decision makers. Each player has a number of strategies (feasible actions), which determines the outcome of the game and the payment to each player. In this game, a network user looks for a route to minimize the expected travel cost while an “evil entity” imposes road segment costs on the user so as to maximize the expected trip cost. This is assumed to be a two-player, noncooperative, and zero-sum game. The user guesses what road segment costs will be imposed and the evil entity guesses which route will be chosen. The mixed strategy that the Nash equilibrium proposed offers a useful measure for network reliability, since it yields the expected trip cost when the user is extremely pessimistic about the state of the network [19, 20].We assume that situationj implies performance degradation, failure, or attack on road segment i. The problem is to solve the following maximization and minimization model:
(12)minpimaxqjC=∑ijpicijqj=∑ij∑kδikhkcijqj=∑khk∑jgkjqj,St.∑jqj=1qj≥0,∑kδikhk=pi,∑khk=1,hk≥0,
where pi is the probability that road segment i is chosen; qj is the probability of situation j; cij is the travel cost of road segment i under situation j; gij is the travel cost of path k under situation j; hk is the probability path k is chosen; δik equals 1 if road segment i is on path k, 0 otherwise.To facilitate the application of the route choice model, the method of successive average (MSA) scheme is used and it can be described as follows.Step 1.
Initializeqj for all situations j and n←1.Step 2.
Set expected road segment costs to∑jcijpj for all road segments i.Step 3.
Build the least expected cost path;xi←1 if road segment i is on this path, and 0 otherwise.Step 4.
p
i
←
(
1
/
n
)
x
i
+
(
1
-
1
/
n
)
p
i for all road segments i.Step 5.
Find thej which maximizes ∑icijpi; yj←1; for all situations k≠jyk←0.Step 6.
q
j
←
(
1
/
n
)
y
i
+
(
1
-
1
/
n
)
q
j for all situations j.Step 7.
n
←
n
+
1 and return to Step 2 until a satisfactory convergence is achieved.


## 4. Numerical Example

A numerical example was chosen to verify the applicability of the model proposed in this paper. As shown in Figure1, it includes 4 nodes, 5 road segments, and 1 OD pair (1→4). The value of OD pair is 2600 pcu/h. In BPR function, parameters β=0.15,n=4, road segments length, free travel time, capacity and emission parameters, and so forth are shown in Table 1. In the numerical example, Δ′ takes 15% of the free travel time ta. Matlab 7.0 was used in the calculations.Table 1
Attribute data of road network unit.
Road segment
Road segment 1
Road segment 2
Road segment 3
Road segment 4
Road segment 5
Free travel timeta/s
76
70
49
76
49
CapacityCa/(pcu/h)
N (1400, 70)
N (1100, 90)
N (1000, 120)
N (1400, 70)
N (1000, 120)
Lengthl/m
1600
1900
1200
1600
1200
Parameters of emission model
b0
168.351
157.483
168.351
168.351
168.351
b1
−5.3423
−5.6240
−5.3423
−5.3423
−5.3423
b2
0.0674
0.0609
0.0674
0.0674
0.0674
b3
−0.0003
−0.0003
−0.0003
−0.0003
−0.0003Figure 1
Test road network.The results show that the different attitudes of travelers towards travel cost have obvious effects on road network traffic assignment. From the results of Table2, it can be found that when w1 is gradually increasing until it approaches 1, which means gradually increase the weight of emission factor in travel cost, the travelers tend to select emission as a criterion of route choice. Meanwhile, the travelers will select the low emission route as their priority selection. Because route 1–4 is the longest, it is 1.68 times as long as route 2 and 1.33 times as long as route 3–5, and it has the largest emission in terms of unit distance, so the emission cost of route 1–4 is the highest. When w1 is 1, the distributed traffic capacity on route 1–4 is the lowest; it is only 653 pcu/h, but the traffic assignments on other routes are 1043 pcu/h and 904 pcu/h. As a result, the emission of the whole local road network can be reduced by 11.4%. When w2 increases and approaches 1, it indicates that travelers tend to select travel time as a criterion of route choice, and travelers tend to select the lower time-consuming route. Due to the fact that route 2 takes the shortest travel time, route 3–5 the next, and then route 1–4, when w2 is 1, the distribution of traffic on route 2 is the highest, which is 1062 pcu/h, route 3–5 is 906 pcu/h, and route 1–4 is the lowest, which is only 662 pcu/h. When w3 gradually approaches 1, it indicates that the travelers tend to treat reliability as a criterion. They will select the high-capacity and low-fluctuation route, and route 3–5 has the lowest capacity and highest fluctuation. Therefore, the assignment on route 3–5 is the smallest, which is only 795 pcu/h.Table 2
Volume under different weight coefficient (pcu/h).
w
1
w
2
w
3
Road segment 1
Road segment 2
Road segment 3
Road segment 4
Road segment 5
0
1.0
0
662
1062
906
662
906
0
0
1.0
843
962
795
843
795
0.2
0.2
0.6
739
971
890
739
890
0.2
0.4
0.4
641
1071
888
641
888
0.2
0.6
0.2
767
1054
779
767
779
0.2
0.8
0
705
994
901
705
901
0.4
0.2
0.4
737
1083
781
737
781
0.4
0.4
0.2
831
1031
738
831
738
0.4
0.6
0
735
1004
861
735
861
0.6
0.2
0.2
702
1044
854
702
854
0.6
0.4
0
712
1030
857
712
857
0.8
0.2
0
685
1076
840
685
840
1.0
0
0
653
1043
904
653
904


## 5. Conclusions

On the basis of the research carried out on emission model, road segment travel time, travel reliability, and generalized travel cost are defined and quantified. Meanwhile, the traffic distribution model that considers emission is proposed based on game theory. By means of the calculation examples, it is proved that travelers’ different attitudes towards emission have obvious effects on route choice. The route choice model considering emission can distinctly reduce road network emission; in the example, it reduced by 11.4%. With the popularized application of ITS, further researches about the effects of information and other factors on route choice behavior should be carried out.



---

*Source: 464038-2013-02-06.xml*