On the primal and dual formulations of traffic assignment problems with perception stochasticity and demand elasticity

ABSTRACT

This article reinvestigates the mathematical formulations of traffic assignment problems with perception stochasticity and demand elasticity in both the system optimum and user equilibrium principles. Our focus is given to a pair of new general formulations that pose a duality relationship to each other. In this primal-dual modeling framework, we found that the equilibrium or optimality conditions of a traffic assignment problem with perception stochasticity and demand elasticity can be redefined as a combination of three sets of equations and an arbitrary feasible solution of either the primal or dual formulation satisfies only two of them. We further rigorously proved the solution equivalency and uniqueness of both the primal and dual formulations, by using derivative-based techniques. While the two formulations pose their respective modeling advantages and drawbacks, our preliminary algorithmic analysis and numerical test results indicate that the dual formulation-based algorithm, i.e., the Cauchy algorithm, can be more readily implemented for large-scale problems and converge evidently faster than the primal formulation-based one, i.e. the Frank-Wolfe algorithm.

KEYWORDS:

• Traffic assignment
• demand elasticity
• stochastic user equilibrium
• supply-demand equilibrium
• unconstrained optimization
• Frank-Wolfe algorithm
• Cauchy algorithm

Acknowledgments

This study was jointly supported by research grants from the National Natural Science Foundation of China (Grant No. 71771150, 72171175, and 72021102) and the Fundamental Research Funds for the Central Universities. The two anonymous reviewers are highly appreciated for their constructive comments.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1. Demand elasticity also reflects the stochasticity or heterogeneity of travel-related attributes and other stochastic factors of individual travelers (Parkin, Powell, and Matthews 2002; Mankiw 2014).

2. By general, we do not mean that the proposed mathematical programming formulations can include non-separable travel cost functions, link flow capacity constraints, and other extra constraints or settings; instead, we mean the inclusion of different route and trip choice principles/objectives and models.

3. Unlike the EDSUE problem (see Maher 2001; Connors, Sumalee, and Watling 2007; Meng and Liu 2012; Yu, Fang, and Du 2014, for example), previous research has not yet defined the optimality conditions of the EDSSO problem. From the perspective of individual travel behaviors, its optimality conditions can be described as such a network flow pattern: Anyone traveling between any O-D pair aims to achieve a goal of minimizing his or her perceived total travel cost over the augmented network by choosing whether or not to make a trip and choosing which route to take if he or she makes a trip, where the trip choice could be regarded as a choice between the whole path set connecting the O-D pair and a dummy nontrip path connecting this O-D pair. The augmented network is formed by adding a dummy nontrip path to each O-D pair with positive demand, and the perceived total travel cost is defined as the sum of the perceived travel cost associated with the arcs in the original network and the perceived not-make-a-trip cost associated with dummy arcs.

4. This condition implicitly implies ${\bar{q}}_{rs}>q_{rs}^{\ast }$, where ${\bar{q}}_{rs}$ is an upper bound of $q_{rs}$.

5. It must be noted that the elastic demand functions of the EDSSO and EDSUE models for the same network must be different. The difference is rooted from the difference between the system optimum and user equilibrium trip choice behaviors and can be evaluated by aggregating the difference between individual marginal social costs and marginal private costs.

6. For example, when the distribution of perception errors follows the normal distribution, the resulting problem is a probit-based elastic-demand traffic assignment problem. In this case, the primal formulation still contains nonlinear constraints (see the equation in (2.2)); to evaluate the objective function and its derivative with respect to any path flow variable in the Frank-Wolfe framework, we need to calculate the value of $d_k^{rs}$, $\mathrm{\forall }k$, $r$, and $s$. The latter task, even if to be conducted by numerical methods, involves enumerating paths and solving a nonlinear system of equations (in the form of (2.2)) for each O-D pair. The size of this system is equivalent to the number of paths connecting the O-D pair, $\left|K_{rs}\right|$. Evidently, such computational requirements pose a very challenging technical difficulty.

7. The Markovian traffic assignment problem we discuss here is the type of spatial Markovian traffic assignment problems that imply an individual Markovian routing behavior with its state space consisting of nodes along paths, but not the temporal type of Markovian problems that imply a Markovian behavior with its state space consisting of periods along the time dimension.

8. In the logit-based case, the set of nonlinear constraints collapse to linear constraints (see the formulation in (15)).

Additional information

Funding

This work was supported by the National Natural Science Foundation of China [71771150], National Natural Science Foundation of China [72171175], and National Natural Science Foundation of China [72021102].