A Game Theory Approach to Trip Distribution Model: Game Distribution Model

2.1. The Place of Trip Distribution in Transportation Models

By the 1950s, car ownership increased rapidly, and travel modelling became necessary to design future transportation systems considering community needs and expectations. Trip distribution, which is the second step of the travel demand model, is intended to produce the best possible predictions of participant destination choices based on trip generation and attraction information. Two broad approaches are used in travel distribution: aggregate and disaggregate [1]. Aggregate models use data aggregated over a series of geographic sub-regions called TAZs. Together, these zones represent an activity system served by a transportation network, and aggregate models analyze each TAZ’s total number of trips. On the other hand, disaggregate models such as discrete choice models, family, and activity-based models deal with individuals' behaviors and destination choices. These models are generally derived from the notions of utility theory [2].

The first-generation aggregate trip distribution models use growth factors from extensive surveys of origin-destination flows. Growth factor methods may be subdivided into four groups: constant factor method, average factor method, Fratar method, and Furness method. Fratar and Furness are the most popular algorithms [3]. Fratar [4] developed a model that made the factoring of an observed flow matrix. It makes the assumption that the existing trips will increase in proportion to the production and attraction growth factors of TAZs. After the Fratar model, Furness [5] proposes a model which is one of the best known iterative methods that uses two growth factors and two balancing factors. All growth factor methods work regardless of increased supply or changed spatial accessibility that occur due to changes in travel patterns and congestion [6].

In addition to growth factor models, there are synthetic distribution models in the literature. These models attempt to identify the causes of current travel patterns and then assume that these underlying causes will remain the same in the future [3]. The most well-known synthetic distribution model is called the gravity model. The important feature that distinguishes the gravity model from growth factor models is that it models not only according to the demand in the future but also takes into account the concept of the hardship of travelling. The hardship is represented by travel impedances, a feature introduced by the gravity model. The first use of the gravity model occurred in the 1950s, and later, many other aggregate or disaggregate models followed the initial trip distribution techniques.

Disaggregate trip distribution models were developed after significant improvements in the discrete choice modelling technique. These models aim to better predict travel behavior by including variables other than travel time [6]. They calculate the choice probabilities of the individuals or groups of individuals with models such as Multinomial Logit or Nested Logit [7]. Later, more sophisticated models were developed, such as the Mixed Logit [8] and the Activity-Based Approach [9]. There are also some studies examining the use of Artificial Neural Networks in disaggregate trip distribution models [10]. The advantage of these models is that it is possible to introduce different attributes into the decision-making process.

2.2. Main Approaches Used in Aggregate Trip Distribution Models

The primary purpose of this study is to propose a new approach and calculation procedure for aggregate trip distribution models. Therefore, first of all, well-known main aggregate approaches have been explained in this section.

2.2.1. The Gravity Model

The doubly constrained classical gravity model [11] is the best-known and most basic aggregate distribution model. It is named for its similarity to Newton's law of universal gravitation.This model assumes that the number of trips between two locations is related to their populations and decays with an impedance function. The gravity model's inputs include the trip generation outputs (productions and attractions) for each zone and measures of travel impedance between each pair of zones obtained from the transportation network. In addition, socio-economic and area characteristics are sometimes used as inputs as well [12].

Probably the first rigorous use of a gravity model was by Casey in 1955, and the most straightforward formulation of the model has the following functional form [13]:

(1)

In this model, T_ijT_{ij}T_ij represents the trips between an origin zone i and a destination zone j, while Oi and Dj denote the trip ends produced at i and attracted at j, respectively. The proportionality factor α\alphaα can be replaced by the multiplication of two sets of balancing factors, Ai and Bj, as used in the Furness algorithm [13].

In Eq. (1) f(c_ij) function represents a generalized function of the travel expense (cost or time) between every pair of zones and has one or more calibration parameters. This function often receives the name ‘deterrence function’ because it represents the disincentive to travel as distance (time) or cost increases. Well-known functional forms are presented in Eqs. (2-4) [14]:

(2)

(3)

(4)

Where β and n are parameters to be calibrated, and c_ij is the deterrence value.

In order for the trip distribution step to be completed, the sum of the trips produced between any origin zone i and all destination zones j ∈ Z (Zones) should be equal to the total trip ends produced at the origin zone. Similarly, the sum of the trips attracted between any origin zone i and all destination zones j ∈ Z should be equal to the total trip ends attracted at the origin zone. These are known as the flow conservation constraints given in Eqs. (5 and 6):

(5)

(6)

With its well-known theoretical base, gravity-type spatial interaction models have been the most commonly used aggregate trip distribution models [15]. The gravity model is primarily far easier to estimate, with only one or two parameters in the deterrence function formulas to calibrate and easy application and calibration procedures using various travel modelling software [12].

Despite its widespread use, there are many criticisms of the gravity model. Mainly, it uses an aggregate procedure and does not refer to any explicit individual behavioral theory. Moreover, the model assumes that all information lies in the constraints; it does not consider any perception attributes [1].

2.2.2. Other Approaches

First-generation trip distribution models were used as Growth-factor models. Generally, originating and attracted trip totals are known collectively as an output of the trip generation step. In 1954, A method was introduced by T. J. Fratar to overcome some of the disadvantages of the doubly costraint methods [4]. The multiplication of the existing flow by two growth factors (row and column growth factors from production and attraction values) will result in the future trips originating in zone i being greater than the future forecasts, and so a normalizing expression is introduced [3]. The Fratar formulation is presented in Eq. (7).

(7)

T_ij and T_ij⁰ are the future and observed number of trips between zones i and j. F_i is the row factor from production, F_j is the column factor from attaction. k is the number of total zones.

After the Fratar algorithm, Furness proposed an iterative method in 1965 [5]. In this method, the productions of flows from a zone are first balanced, and then the attractions to a zone are balanced [3]. The equation of this model, in which two growth factors (row factor F_i, column factor F_j) and two balancing factors (A_i and B_j) are used, is given in Eq. (8).

(8)

The Doubly Constrained Growth Factor Model converges very quickly in most cases and is usually used to model the external to external movements or estimate goods vehicles and freight [16]. This model has two major disadvantages: a zero cell in the matrix remains zero regardless of how many times it is factored. The second is that it is not sensitive to possible changes or enhancements in the transport system.

Another popular approach is the Intervening Opportunities Model developed by Stouffer [17] and refined by Schneider [18] in the Chicago Area Transportation Study. In this model, the distance does not affect the destination choice, playing only the role of a surrogate for the number of intervening opportunities between them [19]. The number of persons going to a given distance is directly proportional to the number of opportunities at that distance and inversely proportional to the number of intervening opportunities.

The most widely used form of the intervening opportunities model can be written as shown in Eq. (9) [20]:

(9)

T_ij is the predicted number of trips, k_i is a constant or balancing factor, O_i is the total production from origin i, and V is the number of opportunities. Finally, L is a constant probability that a random destination will satisfy the needs of a traveler. According to Ortuzar and Willumsen [13], intervening opportunities model has three main disadvantages. The theoretical basis is less well-known and more complicated than the gravity model. It does not include any practically measured trip deterrence attribute (i.e., cost, etc.) and does not have a suitable software.

2.3. Game Theory

In this section, the background of game theory, which is the main method that the proposed model is built upon, is presented. The basis of game theory is the assumption that an individual who makes choices interacts strategically with other individuals. Players are aware that their decisions affect each other's conditions and make decisions accordingly [21].

John von Neumann (1944) [22] discussed Game Theory, which dates back to Babylon, as an economic study in his book “Game Theory and Economic Behavior”. After that, John Nash's articles on the definition of equilibrium laid the foundations of modern non-cooperative games in the early 1950s [23]. Before the 1970s, studies were carried out by assuming that individuals were fully knowledgeable about all options. By the 1970s, game theory studies were developed considering that information is incomplete and rationality is limited [24].

In economics, all participants aim to maximize their profit. Supply-demand equality, a state in which participants do not tend to change their behavior without any external influence is called the concept of market equilibrium. The most widely used equilibrium theory in strategic structures is the Nash equilibrium, developed by John Nash [23]. In the Nash equilibrium, after both players see the other player's strategy, they will not regret their choice and will continue this strategy if they have a chance to play again [25]. The profit function of each player is given in Eq. (10). In this equation, _i represents player i's profit, and s represents the strategies of players.

(10)

This theory defines decisions as responses to the game. The best response functions are found by taking the derivative of each player's profit function and equalizing it to zero (Eq. 11). With this process, it is aimed to determine the extremum point of response, and this point is named Nash equilibrium. At this point, all players make the decision that they are satisfied with. b_i represents the player i's best response, and α_i represents player i's action that affects the strategy,

(11)

The Nash equilibrium is searched for a point where all players determine their decisions, and they do not want to make any changes. On the other hand, Cournot is a model based on quantity competition for participant decisions and was developed long before the concept of Nash equilibrium. Following Nash, Cournot is reinterpreted and has become an integral part of economic analysis [26]. In the Cournot – Nash model, a homogeneous product is produced by n number of companies. The production value of each firm that makes its own profit maximum is determined by the Nash equilibrium.

Profit (π) is found by subtracting the total cost from its total income (Eq. 12). The cost of producing for the i. company is expressed as c_i(q_i). Where, c_i represents unit cost and q_i is the production value. Moreover, P(Q) (Q= q₁+q₂+…q_n) represents the market price, which is determined by the demand for goods and the total production amount of the companies. This price has an inverse demand function, if the company's output increases, the price decreases (p= a-Q).

(12)

Similar to Nash equilibrium, the best response function can be calculated by taking the derivative of the gain according to the strategy action (here, strategy is determined by production value -q). Company i’s best response given Eq. (13).

(13)

Nash equilibrium is at the intersection of these best response functions.

3.1. Proposed Model; Game Distribution Model

In this study, game theory was used to distribute the production and attraction values obtained from the first step of the classical four-step model. In the proposed methodology, production and attraction values for each TAZ are distributed with a game. Each TAZ is assumed to be a player. Games between TAZ pairs are shown in the form of an O/D matrix in Table 1. All cells in the center of the n x n matrix represent the number of trips (q_ij) from TAZ_i (starting point of the trip -origin) to TAZ_j (the final point - destination). This matrix has n production games and n attraction games.

In every game created for attractions, (shown in red in Table 1), it is assumed that all TAZs traveling to destination TAZ are players aiming to maximize their share of total attraction profit. Players (TAZs) determine the number of trips they can send to optimize their profit, with the number of trips from TAZ_i to TAZ_j (q_ij) being strategy actions for players. The sum of the q_ij gives the attraction value (∑q_ij=Q). The profit of the trip from i to j (π_ij) is calculated by subtracting the total cost (c_ij) from the total utility (u(Q)). It is shown in Eq. (14).

(14)

Table 1.

The concept of utility seen in Eq. (14) is created by an analogy with the concept of price in the Cournot – Nash model. Utility motivates passengers to make trips; it is inversely proportional to demand. As the number of trips increases, the utility decreases. Utility depends on the total number of trips, trip origin, and destination characteristics. It is shown in Eq. (15).

(15)

aj: A parameter that depends on destination TAZ

bi: A parameter that depends on the origin TAZ

u: The utility per trip

Q: Total number of trips (∑qij)

As an advantage, this profit approach allows the use of not only travel cost but also travel time or marginal cost to determine total cost. c_ij function can be replaced with t_ij (travel time) or a combination of factors. Even more, other variables, such as the employment or population of the destination TAZ can be added to this equation.

According to the game theory, the best response function is calculated after the profit function is determined. The best response function can be calculated by taking the profit's derivative according to the strategy action (action-the number of trips from TAZi to TAZ_j (q_ij)). In the case of n players, there are n best response functions for every attraction (Eq. 16).

(16)

With the steps and approach mentioned above, n game has been developed for n attraction values, and n best response (br_i) has been determined for each attraction (a total of n² best responses, Eq. (16)).

Production games are developed in the same way and shown in blue in Table 1. TAZs, that have at least one traveler from that TAZ, are players, and they aim to get a share of the total production. The total profit for each TAZ is, again, inversely proportional to demand; if the total number of trips increases, the utility decreases (Eq. 14). Accordingly, n game has been developed for n production values and n best responses (br_i) has been determined for each production (a total of n² best response, Eq. (17)).

(17)

As a result of the construction of attraction and production games, 2*n² best response functions are formulated. The equilibrium point can be determined by solving these equations together. Additionally, because of the complexity of equations, these best response functions can be designed as a minimization problem, and this problem can be solved using algorithms such as the Generalized Reduced Gradient (GRG) Nonlinear Solving method and others. Game Distribution Model, formulated as a minimization problem, is presented below.

Variables: q_ij, a_i ve b_j (n*n+ 2n variable)

Objective: Min ε

ε= (∑ ε_n)^1/2

b₁*2q_1i+b₂*q_2i+ …..+b_n *q_ni - a_i-c_1i = ε₁

b₁*q_1i+ b₂*2q_2i+ ….+ b_n*q_ni - a_i–c_2i = ε₂

…

…

b_j*q_j1+b_j*q_j2+ …..+b_j* 2q_jn - a_n–b_n*c_jn =ε_n

Subject to: q_ji >0, a_i>0, b_j>0

In the minimization problem mentioned above, due to the nonlinearity of the best response functions, the obtained results are local optimums. Therefore, if there is a preliminary estimate, the minimization problem can yield a better local optimum. In the proposed model, a preliminary estimation does not exist. Thus, an algorithm that accounts for no initial estimates was developed (Fig. 1).

The steps of the algorithm are as follows:

Step 1: Set all variables (q_ij, a_i, b_j) to 0 (there is no preliminary estimation.)

Step 2: Solve the minimization problem, then calculate the error (ε_ι) and set var_i+1.

Step 3: Compare the recent error (ε_ι) with the previous error (ε_i-1) to see if any improvement is achieved

Step 4: Any improvement? Update all variables (q_ij, a_i, b_j) and error (ε_ι), then go to Step 2.

Step 5: Stop. ε_i-1 is the final error, and var_i are final variables.

3.2. Performance Measures and Goodness of Fit Statistics

The performance and success of the proposed methodology can be assessed by using various measures. In this study, several different goodness-of-fit statistics were selected for performance measurement and model evaluation. Root Mean Squared Error (RMSE) and the Coefficient of Determination (r²) were determined as the micro-level goodness of fit parameters, Mean Travel Cost Error (MTCE) and Trip Length Distribution Root Mean Squared Error (TLD RMSE) were determined as macro-level goodness of fit parameters.

The RMSE is one of the most accurate comparative measures of model performance [65]. RMSE represents the differences between predicted values and observed values with the quadratic mean. It serves to aggregate the magnitudes of the errors in predictions for various data points into a single measure. When the RMSE values are lower correspondence is higher, and 0 would indicate a perfect fit to the data. As the RMSE value gets smaller, it

is determined that the model estimation gets closer to the observed values. The effect of each error on the RMSE is proportional to the squared size of the error; therefore, larger errors have a disproportionately large impact on the RMSE. Accordingly, the RMSE shown in Eq. (18) is sensitive to outliers.

(18)

In Eq. (18), T_ij^o represents the number of observed trips, and T_ij represents the number of trips obtained as a result of the model. n represents the total number of values compared.

The coefficient of determination (r²) is another widely used measure of model performance. It is a measure of the linear association between observed and predicted values. The r² value is lies in the range of 0-1. As the value gets closer to 1, the similarity of the model to the observation values increases. It has been determined that in some special cases, the r² statistic may show insensitivity to error. Therefore, the interpretation of r² measures should be done with caution [65]. It is presented in Eq. (19).

(19)

In this equation, T_ij^o represents the number of observed trips, T^o represents the average of these observed values, and T_ij represents the number of trips obtained as a result of the model.

Mean Travel Cost Error (MTCE) is a macro-level performance measure in trip distribution modelling. It is also employed as a standard calibration procedure for years [66]. In the MTCE, in addition to traffic values, travel costs are also used (Eq. 20). For model and real trips, the trip cost per trip is calculated, and the MTCE is determined by calculating the difference between these values. The calculated value is considered as the deviation value, and the closer the deviation value is to 0, the more realistic the model gives results, regardless of the sign of the deviation.

(20)

In Eq. (20), T_ij^o, T^o, and T_ij represent the same values used in Eq. (19). In addition, is the total number of observed trips, is the total number of estimated trips.

Finally, The Trip Length Distribution (TLD) is determined by calculating the frequency distributions of the travel time or costs for the observed values. It is a macro-level measure for trip distribution modelling, and is used both in the calibration and the model evaluation phases. The TLD obtained by calculating the number of trips within the specified ranges is expected to fit the right-skewed normal distribution in the ideal situation. It is assumed that the TLD graph drawn with the predicted values will remain the same. Trip Length Distribution Root Mean Squared Error (TLD RMSE) measures the root mean squared differences between observed and estimated trip length frequency distributions associated with usual time intervals.

3.3. Empirical Evaluation

In this paper, the model described in Section 3.1 was evaluated with real-world household survey data by using the actual trip information collected for the Eskisehir Master Plan [67]. Eskişehir is a medium-sized city located in the inner parts of Turkey. The network created with TAZs that have sufficient data in the household survey is shown in Fig. (2). As a part of the master plan studies [67] TAZs were determined, and data were collected from more than 30000 households in the 72 TAZs.

In the empirical evaluation, an actual O/D matrix is extracted from the survey and this actual matrix is re-estimated by using both the proposed method and the gravity model. Afterward, for both methods, convergence to the actual values is investigated and the results are compared by using the measures given in Section 3.2. For computational simplicity, this practice is performed by using only a subset of 72 TAZs. The subset contains 5 TAZs selected for different cases. In this empirical analysis, 5 cases are selected: (a) neighboring TAZs, (b) distinct TAZs, (c) TAZs with high travel demand, (d) TAZs with low travel demand, and (e) randomly selected TAZs. Randomly selected TAZs contain arbitrarily selected 5 TAZs while neighboring TAZs include 5 TAZs sharing administrative borders. On the other hand, separate TAZs are defined as TAZs that do not have any administrative borders with each other. The threshold between high and low demand is assumed to be 100 trips/day. Accordingly, for the TAZ group with low demand, the number of trips for every TAZ in the group is less than 100. Parallelly, for the high-demand TAZ group, the number of trips for every TAZ is more than 100.

For all TAZ subsets, a 5x5 O/D matrix was established by using the number of trips obtained from the household surveys. Here, the travel times and costs were determined from the network.

Furthermore, for intra-zonal trips, times and costs are assumed to be zero for computational simplicity. The plots of the cases and TAZs are given in Fig. (3).

Travel times and travel cost values for the example cases are provided in Table 2. Using these values, empirical examples were calculated employing both the game distribution model and the gravity model. The resulting pairs were then compared using the measures described in Section 3.2.