The general multimodal network equilibrium problem with elastic balanced demand is studied. This problem is a combination of trip distribution, modal split and trip assignment problems. The problem is approached from an asymmetric network equilibrium point of view with side constraints. The balances for travel demand are taken as side constraints. These balances do not guarantee that the problem's solution will satisfy the user equilibrium conditions. It is shown that the obtained solution is equilibrium traffic pattern in terms of the generalized travel costs which is constructed with the use of dual variables for demand balance constraints. The economical interpretation of dual variables from the city infrastructure extension point of view is proposed. By calculating of the dual values we know whether or not a city area is suitable for growing. It is established that if the travel costs are co-coercive then the set of shortest routes in terms of generalized travel costs is the same for every solution of the studied problem.
Natalia Shamray
Transportation processes have been studied, modelled and thoroughly analysed for almost a century by now. During this time a large amount of knowledge concerning various aspects of transportation systems was accumulated. An essential part of it is the equilibrium theory of network flows [1–3] initiated by the studies in the economics of transportation by M.J. Beckmann, C.B. McGuire, C.B. Winsten in 1955 [4]. This theory is one of the objective tools for efficiency estimation of transportation planning projects. It is usually used to forecast a traffic pattern in congestion urban networks.
Forecast modelling of traffic patterns consists of solving the following four problems [2]: Copyright c by the paper’s authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org 1) trip generation (it is to determine the number of trips originating and terminating in different zones of the area under study ); 2) trip distribution (it is to determine the travel demand between origin and destination zones); 3) modal split (it is to determine the portion of the total number of trips made between an origin and destination using different transport modes); 4) trip assignment (it is to allocate the origin-destination trips to routes in the network).
There are special mathematical models for each of these problems. The problems are considered sequentially in a top-down sequential process. The output from one problem is the input to the next one.
The traffic pattern is forecasted at the fourth step. The basic assumption concerning the way the network users choose their routes is usually formulated as socalled Wardrop’s first behavioral principle: drivers use only routes with minimal travel costs [5]. This principle is also called user equilibrium. Therefore the trip assignment problem is based on the so-called network equilibrium model.
In order to achieve an agreement between solutions of four considered problems and obtain an adequate modelling results it is necessary to introduce a ”feedback” mechanism into the computational procedures. So the process has to be repeated many times, however, the convergence is not guaranteed.
The current network equilibrium theory allows us to substitute all four steps mentioned above or only several of them with the solution of a single problem. In this case, the basis is the network equilibrium model, which combined with other models (trip generation, trip distribution, modal split) (for example, the most cited papers [6–9]) Such substitution improves the calibration of calculations and leads to more adequate results of traffic modelling.
All forecast traffic flow models can be divided into two classes. Based on the assumption that travel cost structures are either separable or symmetric, the models of the first class are formulated as convex optimization programs. In scientific literature this class of models gains a lot of attention. But, in order to capture such supplementary flow relationships as interactions among vehicles on different roads, turning priorities in junctions and etc., the traditional modelling strategy is to modify the travel cost functions. This strategy often leads to the nonseparable and asymmetric travel cost functions [10–12]. In this case we deal with the models of second class which were formulated as variational inequalities [9], [14, 13].
In this paper we consider a forecast traffic flow problem which is in fact a combination of trip distribution, modal split and trip assignment problems. We assume that the trip assignment problem is based on the network equilibrium model with nonseparable and asymmetric travel cost functions. Unlike most papers in this field we do not specify the structure (gravity, entropy, logit etc.) of the models for the trip distribution and modal split problems. We consider the general form of the travel disutility function which is the measure of the perceived loss to the network users. Also we assume that the number of trips originating and terminating in different zones is known. It means that the travel demand has to satisfy balance constraints. As the result we have obtained a general multimodal network equilibrium problem with elastic demand in the form of a variational inequality [15] with an additional set of balance constraints for demand. We have called this problem as the general multimodal network equilibrium problem with elastic balanced demand (GMNEP with EBD).
As is known the introduction of additional constraints into the network equilibrium problem does not guarantee that the obtained solution will satisfy the user equilibrium conditions. This topic has been considered in detail in [16] for a network equilibrium problem with fixed demand with an additional convex set of inequalities. The purpose of our research is to give equilibrium characterizations of a solution of the GMNEP with EBD and to explore an influence of the demand balance constraints on the equilibrium traffic pattern.
We note that the model presented in this paper is inspired from the project of creating of a cloud service for interactive modelling of transportation flows in the growing city infrastructure. This service is designed for rapid assessment of the network load level as a result of various modifications of network elements and changes in the arrangement and designation of urban objects. The main characteristics of urban objects from the service point of view are the number of trips originating and terminating in it. These data identify the right parts of demand balance constraints. Therefore in order to change the city infrastructure responsibly it is very important and useful to know how does the demand balance constraints affect the traffic pattern.
In this paper is shown that the solution of the GMNEP with EBD may be interpreted as a generalization of network equilibrium in terms of generalized travel costs which are constructed with the use of dual variables for demand balance constraints. The economical interpretation of dual variables from the city infrastructure extension point of view is proposed. By calculating the dual values we know whether or not a city area is suitable for growing. It is established that if the travel costs are co-coercive then the set of shortest routes in terms of generalized travel costs is the same for every solution of the GMNEP with EBD. 2
We describe the transportation network as a connected directed graph Γ (N , L), where N is the set of nodes and L is the set of directed links in the network. Each link corresponds to a real road segment with no intersections. Each node represents a point that divides road segments. Roads with a two-sided traffic have paired links going in both directions.
To study the flow-generating factors we distinguish two subsets of N : the first subset O ⊆ N contains nodes that generate flows, while the second subset D ⊆ N contains nodes that absorb flows. We call elements of the set O origins, and elements of D destinations. We assume that the network flows differ by modes of transportation. Denote by M the set of the considered modes.
Travel demand is the crucial information for the transportation planning. The so called OD-matix denoted by ρ = (ρmij : m ∈ M, (i, j) ∈ O × D) is the quantitative characteristic of the travel demand where the element ρmij gives the number of potential users of the mode m travelling between the OD-pair (i, j) ∈ O × D).
In practice travellers choose a destination node taking into account economical factors. The travel disutility is a measure of the perceived loss to the travellers in an OD-pair and the intention to undertake the trip decreases with an increasing disutility. Let umij be the travel disutility associated with traveling by the mode m ∈ M between the OD-pair (i, j) ∈ O × D. We arrange the travel disutilities into a vector u = (umij : m ∈ M, (i, j) ∈ O × D).
We adopt the assumption of ”elastic demands” according to which the travel demands are determined by travel disutilities. We consider the most general situation where the demand associated with any mode and any OD-pair may depend on the disutilities associated with all modes and all OD-pairs in the network: ρmij = ρmij(u). We also assume that, conversely, travel demands uniquely determine travel disutilities, i.e. the functions ρmij(u) are invertible: umij = umij(ρ).
Network users traveling between flow-generating pairs choose one or another route. Denote by Pij the set of alternative routes by which the flow outgoing from origin i reaches destination j. Let xmp be the flow of the mode m on the route p. We arrange the route flows into a vector x = (xmp : m ∈ M, p ∈ Pij , (i, j) ∈ O × D). Traditionally, flow variables in transportation problems must be non-negative and satisfy the flow conservation equations
X xmp = ρmij , m ∈ M, (i, j) ∈ O × D.
p∈Pij
Let Xρ = {(x, ρ) ≥ 0 : (
The user of the mode m on the route p undergoes a travel cost Fmp (time, fuel, money, car amortization, road wear, etc.). We assume that the route travel cost associated with any mode on any route may depend on flows by all modes on all routes: Fmp = Fmp(x). We arrange the route travel costs into a mapping F (x) = (Fmp(x) : m ∈ M, p ∈ Pij , (i, j) ∈ O × D).
Definition 1 ([15]). The vector (x∗, ρ∗) ∈ Xρ is called equilibrium traffic pattern if for every mode m ∈ M, every OD-pair (i, j) ∈ O × D, and every route p ∈ Pij Fmp(x∗) = umij(ρ∗), if x∗mp > 0, ≥ umij(ρ∗), if xmp = 0.
∗
(
In general case the equilibrium conditions (
Theorem 1 ([15]). The vector (x∗, ρ∗) ∈ Xρ is an equilibrium traffic pattern if and only if it is a solution of the following variational inequality
F (x∗)(x − x∗) − u(ρ∗)(ρ − ρ∗) ≥ 0, (x, ρ) ∈ Xρ.
The issues of existence and uniqueness of solutions of the variational inequality (
Further on we will assume that the mapping F (x) and u(ρ) are positive.
Note that any solution (x∗, ρ∗) of the problem (
(x∗, ρ∗) = argmin{F (x∗)x − u(ρ∗)ρ : (x, ρ) ∈ Xρ}.
It means that F (x∗)x∗ = u(ρ∗)ρ∗. Therefore any equilibrium traffic pattern provides a minimum of the total system travel cost under assumption that the network users choose the least cost routes for the trips. 3
We assume that the total number of trips by the mode m ∈ M generated by the origin i ∈ O, denoted omi, and absorbed by the destination j ∈ D, denoted as dmj, are known. Then the travel demand have to satisfy the following balance constraints
X ρmij = omi,
j∈D
X ρmij = dmj,
i∈O
are fulfilled for every mode m ∈ M. Let Θρ = {ρ ≥ 0 : (
We define the general multimodal network equilibrium problem with elastic balanced demand as the problem of finding a traffic pattern (x∗, ρ∗) ∈ Ω such that
F (x∗)(x − x∗) − u(ρ∗)(ρ − ρ∗) ≥ 0, (x, ρ) ∈ Ω.
The existence of at least one solution of (
The variational inequalities (
Consider the unimodal network shown on the Fig. 1. Let O = {1} and D = {2, 3}.
There are two routes for each of OD-pairs: P12 = {1 → 2, 1 → 3 → 2}, P13 =
{1 → 3, 1 → 2 → 3}. Let x = (x12, x132, x13, x123) is the route flow vector and
F (x) = (F12 = f12, F132 = f13+f32, F13 = f13, F123 = f12+f23) is the route travel cost
mapping for the respective routes. Let f12 = y12 + 3, f13 = y13 + 2, f23 = y23, f32 = y32,
where ykl is link flow on the link (k, l). Let u(ρ) = (uij = ln 1ρ0ij0 : (i, j) ∈ {(
The solution of problem (
Define the total number of trips generated by the origin A as o = 4 and absorbed
by the destination B and C as d1 = 2 and d2 = 2, respectively. Then the solution of
the problem (
x∗ = (
F (x∗) − u(ρ∗) = (0.421, 0.421, −0.245, 0.421).
Furthermore the difference between travel costs and travel disutility for routes actually used can be positive as well as negative.
The purpose of this paper is to explain what kind of solution we obtain by solving
the problem (
X X xmp = omi,
j∈D p∈Pij
X X xmp = dmj,
i∈O p∈Pij
(F (x∗) − ΔU (x∗))(x − x∗) ≥ 0, x ∈ X.
(
Denote by X∗ the solution set of the problem (
First of all we show that any solution of the problem (
Proposition 1. Let x∗ ∈ X∗. For every mode m ∈ M, every OD-pair (i, j) ∈ O × D
and every route q ∈ Pij if ∗mq > 0 then Fmq(x∗) = minp∈Pij Fmp(x∗).
Proof. Fix the OD-pair (k, l) ∈ O × D and the mode n ∈ M and choose two different
∗ ε ∗
routes q, r ∈ Pkl such that xnq > 0. Consider a vector xε such that xmp = xmp for all
m 6= n, p 6= q and p 6= r, but xεnq = x∗nq − ε and xεnr = x∗nr + ε, where ε > 0 such that
xnq ≥ 0. Obviously xε ∈ X and it is easy to see that variational inequality (
ε(Fnr(x∗) − Fnq(x∗)) ≥ 0.
Thus for every OD-pair (k, l) ∈ O × D and every mode n ∈ M if the routes q ∈ Pkl actually used then Fnq(x∗) = minp∈Pij Fnp(x∗).
Observe that any solution x∗ ∈ X∗ also solves a following linear optimization problem
(F (x∗) − ΔU (x∗))x → min, x ∈ X.
Let λmi and μmj are dual variables for the constraints (
Theorem 2. Every solution x∗ ∈ X∗ is equilibrium traffic pattern in terms of generalized route travel costs be given as
F¯mq(x∗) = Fmp(x∗) − (λ∗mi + μ∗mj),
where λ∗mi and μ∗mj are optimal values of dual variables for the linear optimization
problem (
Proof. Based on the standard theorems in the linear optimization duality we have for
every mode m ∈ M, every OD-pair (i, j) ∈ O × D and every route p ∈ Pij
x∗mp(Fmp(x∗) − (λ∗mi + μ∗mj) − Umij(x∗)) = 0,
x∗ ≥ 0, Fmp(x∗) − (λ∗mi + μ∗mj) − Umij(x∗) ≥ 0.
(
F¯mp(x∗)
= Umij (x∗), if x∗mp > 0,
≥ Umij (x∗), if xmp = 0
∗
(
The Theorem 2 allows us to call the vector x∗ ∈ X ∗ the generalized equilibrium traffic pattern. We arrange the generalized route travel costs into a mapping F¯(x) = (F¯mp(x) : m ∈ M, p ∈ Pij , (i, j) ∈ O × D).
The rows of the coefficient matrix of the balance constraints (
Note that if x∗ satisfies the conditions (
x∗ = argmin{(F¯(x∗) − ΔU (x∗))x : x ≥ 0}.
Therefor the demand balance constraints on the one hand (as it is shown in the Theorem 2) have no effect on the user’s behavior and on the other hand they lead to the deterioration of the transportation situation( the total system travel cost has increased on the value (λ∗ + μ∗)ΔT x∗). So for every mode m ∈ M and every OD-pair (i, j) ∈ O × D the value λmi + μ∗mj can be interpreted as:
∗ – if λ∗mi + μ∗mj < 0 then the travel demand between the OD-pair (i, j) by the mode m is too low, therefore the city infrastructure related to the node i or/and j can ∗ be considered as an area for growing: if λmi < 0 then new objects generation flows (residential districts) or/and if μ∗mj < 0 then new objects abserbtion flows (business centers) can be created; – if λmi + μ∗mj > 0 then the travel demand between the OD-pair (i, j) by the mode ∗ m is too high and, as a consequence, we have the saturation of route links in this direction therefore it is advisable to take actions to decrease the correspondence ∗ ρmij , due to changes in the infrastructure related to the node i or/and j; – if λmi +μ∗mj = 0 then in current state of the transportation network the equilibrium ∗ travel demand ρmij has formed between the origin i and destination j and any changes in the infrastructure related to i or j are inadvisable.
For the network example given in Fig. 1 the introduction of the demand balance
constraints leads to the increase of the total system travel cost by 0.352 points. The
causes of such increase are the shortage of travel demand in the pair (
We then need to introduce the following concept.
Definition 2. A mapping G : X → Rn on a set X is called: – co-coercitive (inversely strongly monotone) with constant τ > 0 if for all x, y ∈ X (G(x) − G(y))(x − y) ≥ τ kG(x) − G(y)k2; – strictly monotone if for all x, y ∈ X
(G(x) − G(y))(x − y) > 0.
For co-coercitive mappings the next result is proved.
Lemma 1 ([16]). Consider the variational inequality problem of finding an y∗ ∈ Y
such that
Φ(y∗)(y − y∗) ≥ 0, y ∈ Y,
(
By the standard theory of variational inequalities if Φ(y) is a strictly monotone
mapping then the problem (
Next we will establish some stability properties of the solutions of the general
multimodal network equilibrium problem with elastic balanced demand (
Proof. By the Lemma 1 the mappings F (x) and u(ρ) are constants on the set Ω therefor for every x∗ ∈ X∗ we have F (x∗) − ΔU (x∗) = c∗ where c∗ is some constant vector. Thus for every x∗ ∈ X∗ the set of optimal dual vectors λ∗ and μ∗ is defined as (λ∗, μ∗) = argmax{oλ + dμ : λ + μ ≤ c∗}, where o = (omi : m ∈ M, i ∈ O) and d = (dmj : m ∈ M, j ∈ D).
Moreover for every x∗ ∈ X∗ and vectors λ∗ and μ∗ satisfying (
Let for x∗ ∈ X∗ the conditions (
To show it by contradiction we assume that there exist x∗, x∗∗ ∈ X∗ such that
x∗ 6= x∗∗. Since F (x∗) − ΔU (x∗) = F (x∗∗) − ΔU (x∗∗) = c∗ then x∗ and x∗∗ are
different solutions of the same problem (
The co-coercivity assumption in the Theorem 3 may also be replaced by strict
monotonicity assumption on F (x) and −u(ρ) since it implies that the traffic pattern
solution of (
Mathematical equilibrium models are one of the efficient tools to support managerial decisions in the transportation planing. We believe the general multimodal network equilibrium problem with elastic balanced demand allows us to achieve more adequate results of traffic modelling because 1) the solution of this problem integrates three stages of the four-phases iterative process of traffic modelling, namely trip distribution, modal split, and route assignment; 2) the information about trip generation is explicitly included into the model in terms of the demand balance constraints; 3) the fact that the travel costs are considered in this problem as the functions of the load across the entire network, makes it possible to capture such supplementary flow relationships as interactions among vehicles on different road links and turning priorities in junctions and etc.
The use of the general multimodal network equilibrium problems with elastic balanced demand is also justified from a theoretical point of view. Its solution agrees with the Wardrop’s first behavioral principle and can be interpreted as generalized traffic equilibrium pattern.
Moreover the economic interpretation of dual variables for the demand balance constraints can be used for managerial decisions concerning of upgrade projects for the city infrastructure related to the network. According to the solution of the considered problem, we can detect which of the originating and terminating zones are poorly developed, and which overload the transportation network.