非可加交通分配问题建模及高效求解算法研究

doi:10.3778/j.issn.1002-8331.2505-0338

摘要/Abstract

摘要： 现有非可加交通分配问题（NaTAP）求解方法中，仅有GP（gradient projection）算法可计算大规模网络，因此亟需探索适用于实际交通网络的高效算法。相较于NaTAP，传统的可加性交通分配问题（TAP）已发展出多种可高效处理大规模网络的成熟算法。由于NaTAP需在路径流空间中建模和求解，TAP算法中，只有Greedy、ISP（improved social pressure）、PE（path equilibration）、PG（projected gradient）和RG（reduced gradient）等基于路径的算法具备潜在适用性。为实现ISP、PE、PG和RG算法在NaTAP中的应用，构建了以路径流量为变量的非线性规划模型；此外，利用NaTAP与变分不等式问题（VIP）的等价性，引入了Greedy算法，并结合VIP可行集的单纯形结构，介绍了一种单纯形投影（simplex projection，SP）算法。在统一的计算框架下，系统评估了上述算法在大规模NaTAP中的适用性。数值实验结果显示，GP和SP具有较高的收敛速度和稳定性，而Greedy与PE的稳定性相对不足，ISP、PG和RG效率较低。

关键词: 非可加交通分配问题, 基于路径的算法, 非线性规划问题, 变分不等式问题, 数值研究

Abstract: Among existing solution methods for the non-additive traffic assignment problem (NaTAP), only the gradient projection (GP) algorithm solves large-scale networks, indicating an urgent need to explore efficient algorithms that are suitable for real-world traffic networks. In contrast, numerous mature algorithms have been developed for the traditional additive traffic assignment problem (TAP) that efficiently solve large-scale networks. Since NaTAP needs to be modeled and solved in the path flow space, only path-based TAP algorithms such as Greedy, improved social pressure (ISP), path equilibration (PE), projected gradient (PG), and reduced gradient (RG) have potential applicability. To apply ISP, PE, PG, and RG algorithms to NaTAP, a nonlinear programming model is formulated with path flows as variables. In addition, it introduces the Greedy algorithm by exploiting the equivalence between NaTAP and the variational inequality problem (VIP) and proposes a simplex projection (SP) algorithm based on the simplex structure of the VIP feasible set. Within a unified computational framework, the applicability of these algorithms to large-scale NaTAP is systematically evaluated. Numerical experiments demonstrate that GP and SP achieve higher convergence speed and stability, while Greedy and PE exhibit relatively weak stability, and ISP, PG, and RG are inefficient.

Key words: non-additive traffic assignment problem, path-based algorithms, nonlinear programming problem, variational inequality problem, numerical study

胡望欣, 黄中祥, 李亨, 蔡建荣. 非可加交通分配问题建模及高效求解算法研究[J]. 计算机工程与应用, 2025, 61(24): 103-115.

HU Wangxin, HUANG Zhongxiang, LI Heng, CAI Jianrong. Modeling and Efficient Solution Algorithms for Non-Additive Traffic Assignment Problem[J]. Computer Engineering and Applications, 2025, 61(24): 103-115.

参考文献

[1] BECKMANN M J, MCGUIRE C B, WINSTEN C B. Studies in the economics of transportation[M]. New Haven: Yale University Press, 1956.
[2] PEREDERIEIEVA O, EHRGOTT M, RAITH A, et al. A framework for and empirical study of algorithms for traffic assignment[J]. Computers & Operations Research, 2015, 54: 90-107.
[3] XIE J, XIE C. Origin-based algorithms for traffic assignment: algorithmic structure, complexity analysis, and convergence performance[J]. Transportation Research Record: Journal of the Transportation Research Board, 2015, 2498(1): 46-55.
[4] NIE Y M. A class of bush-based algorithms for the traffic assig-nment problem[J]. Transportation Research Part B: Methodological, 2010, 44(1): 73-89.
[5] LO H K, CHEN A. Reformulating the traffic equilibrium problem via a smooth gap function[J]. Mathematical and Computer Modelling, 2000, 31(2/3): 179-195.
[6] LO H K, CHEN A. Traffic equilibrium problem with route-specific costs: formulation and algorithms[J]. Transportation Research Part B: Methodological, 2000, 34(6): 493-513.
[7] SZETO W Y, JIANG Y, WONG K I, et al. Reliability-based stochastic transit assignment with capacity constraints: formul-ation and solution method[J]. Transportation Research Part C: Emerging Technologies, 2013, 35: 286-304.
[8] CHEN A, ZHOU Z. The α-reliable mean-excess traffic equilibrium model with stochastic travel times[J]. Transportation Research Part B: Methodological, 2010, 44(4): 493-513.
[9] 刘志伟, 宋正沄, 邓卫, 等. 无人驾驶汽车对中短距离市际出行方式选择行为的影响[J]. 交通信息与安全, 2022, 40(2): 91-97.
LIU Z W, SONG Z Y, DENG W, et al. Impacts of autonomous vehicles on mode choice behavior in the context of short-and medium-distance intercity travel[J]. Journal of Transport Information and Safety, 2022, 40(2): 91-97.
[10] 张凌煊, MONICA M, 张士行, 等. 考虑街区尺寸的不同交通方式广义出行成本分析[J]. 交通运输系统工程与信息, 2019, 19(2): 166-174.
ZHANG L X, MONICA M, ZHANG S H, et al. An analysis of traffic cost of different transport modes considering city block size[J]. Journal of Transportation Systems Engineering and Information Technology, 2019, 19(2): 166-174.
[11] 程国柱, 刘轩龄, 冯天军. 行为经济学视角下城市居民出行方式选择演化博弈模型[J]. 哈尔滨工业大学学报, 2024, 56(7): 102-111.
CHENG G Z, LIU X L, FENG T J. Evolutionary model of transportation mode choice for urban residents from the perspective of behavioral economics[J]. Journal of Harbin Institute of Technology, 2024, 56(7): 102-111.
[12] 黄合来, 蒋梦曦, 韩春阳, 等. 基于安全可靠性的多类用户交通分配模型[J]. 中国公路学报, 2018, 31(4): 312-321.
HUANG H L, JIANG M X, HAN C Y, et al. Traffic assignment method for multiclass users considering safety reliability[J]. China Journal of Highway and Transport, 2018, 31(4): 312-321.
[13] 黄中祥, 胡望欣, 李志学. 考虑快捷性和舒适性出行偏好的网络混合均衡[J]. 交通科学与工程, 2022, 38(3): 121-127.
HUANG Z X, HU W X, LI Z X. Mixed network equilibrium considering travel preferences of rapidity and comfort[J]. Journal of Transport Science and Engineering, 2022, 38(3): 121-127.
[14] 张卫华, 刘冉冉, 颜鹏, 等. 考虑舒适度因素的出行价值模型[J]. 公路交通科技, 2020, 37(5): 116-122.
ZHANG W H, LIU R R, YAN P, et al. A travel value model considering comfort factors[J]. Journal of Highway and Transportation Research and Development, 2020, 37(5): 116-122.
[15] 孙超, 尹浩为, 张玮, 等. 基于有限理性的交通网络可靠性均衡模型[J]. 西南交通大学学报, 2023, 58(1): 83-90.
SUN C, YIN H W, ZHANG W, et al. Traffic equilibrium model of reliable network based on bounded rationality[J]. Journal of Southwest Jiaotong University, 2023, 58(1): 83-90.
[16] 徐光明, 王英姿, 史峰, 等. 基于出行时间可靠性的支路网络均衡分析[J]. 吉林大学学报(工学版), 2015, 45(3): 755-760.
XU G M, WANG Y Z, SHI F, et al. Traffic flow equilibrium analysis of branch network based on travel time reliability[J]. Journal of Jilin University (Engineering and Technology Edition), 2015, 45(3): 755-760.
[17] SUN C, CHENG L, ZHU S L, et al. Multi-criteria user equilibrium model considering travel time, travel time reliability and distance[J]. Transportation Research Part D: Transport and Environment, 2019, 66: 3-12.
[18] CHEN P, NIE Y. Bicriterion shortest path problem with a general nonadditive cost[J]. Transportation Research Part B: Meth-odological, 2013, 57: 419-435.
[19] DI X, LIU H X, BAN X J, et al. Ridesharing user equilibrium and its implications for high-occupancy toll lane pricing[J]. Transportation Research Record: Journal of the Transportation Research Board, 2017, 2667(1): 39-50.
[20] LI Y Y, LIU Y, XIE J. A path-based equilibrium model for ridesharing matching[J]. Transportation Research Part B: Methodological, 2020, 138: 373-405.
[21] MA J, XU M, MENG Q, et al. Ridesharing user equilibrium problem under OD-based surge pricing strategy[J]. Transportation Research Part B: Methodological, 2020, 134: 1-24.
[22] LI M, DI X, LIU H X, et al. A restricted path-based ridesharing user equilibrium[J]. Journal of Intelligent Transportation Systems, 2020, 24(4): 383-403.
[23] AGRAWAL S K, BOYLES S D, JIANG N, et al. Network route choice model for battery electric vehicle drivers with different risk attitudes[J]. Transportation Research Record: Journal of the Transportation Research Board, 2015, 2498(1): 75-83.
[24] JEFF BAN X, DESSOUKY M, PANG J S, et al. A general equilibrium model for transportation systems with e-hailing services and flow congestion[J]. Transportation Research Part B: Methodological, 2019, 129: 273-304.
[25] LIU Y H, CHEN Z B, XIE C, et al. Temporal equilibrium for electrified ride-sourcing markets considering charging capacity and driving fatigue[J]. Transportation Research Part C: Emerging Technologies, 2023, 147: 104008.
[26] HUANG W T, JIAN S S, REY D. Non-additive network pricing with non-cooperative mobility service providers[J]. European Journal of Operational Research, 2024, 318(3): 802-824.
[27] GABRIEL S A, BERNSTEIN D. The traffic equilibrium problem with nonadditive path costs[J]. Transportation Science, 1997, 31(4): 337-348.
[28] XU M, CHEN A, QU Y C, et al. A semismooth Newton method for traffic equilibrium problem with a general nonadditive route cost[J]. Applied Mathematical Modelling, 2011, 35(6): 3048-3062.
[29] CHEN A, LO H K, YANG H. A self-adaptive projection and contraction algorithm for the traffic assignment problem with path-specific costs[J]. European Journal of Operational Research, 2001, 135(1): 27-41.
[30] HAN D R, LO H K. Solving non-additive traffic assignment problems: a descent method for co-coercive variational ine-qualities[J]. European Journal of Operational Research, 2004, 159(3): 529-544.
[31] AGDEPPA R P, YAMASHITA N, FUKUSHIMA M. The traffic equilibrium problem with nonadditive costs and its monotone mixed complementarity problem formulation[J]. Transportation Research Part B: Methodological, 2007, 41(8): 862-874.
[32] CHEN A, ZHOU Z, XU X D. A self-adaptive gradient projection algorithm for the nonadditive traffic equilibrium problem[J]. Computers & Operations Research, 2012, 39(2): 127-138.
[33] TAN H Q, DU M Q, CHEN A. Accelerating the gradient projection algorithm for solving the non-additive traffic equilibrium problem with the Barzilai-Borwein step size[J]. Computers & Operations Research, 2022, 141: 105723.
[34] BARZILAI J, BORWEIN J M. Two-point step size gradient methods[J]. IMA Journal of Numerical Analysis, 1988, 8(1): 141-148.
[35] JAYAKRISHNAN R, TSAI W T, PRASHKER J N, et al. A faster path-based algorithm for traffic assignment[C]//Proceedings of the 73rd annual Meeting of the Transportation Research Board, 1994: 75-83.
[36] XIE J, NIE Y M, LIU X B. A greedy path-based algorithm for traffic assignment[J]. Transportation Research Record: Journal of the Transportation Research Board, 2018, 2672(48): 36-44.
[37] KUMAR A, PEETA S. An improved social pressure algorithm for the static deterministic user equilibrium traffic assi-gnment problem[C]//Proceedings of the 90th Annual Meeting of the Transportation Research Board, 2011.
[38] FLORIAN M, HEARN D. Network equilibrium models and algorithms[M]//Network routing. Amsterdam: Elsevier, 1995: 485-550.
[39] FLORIAN M, CONSTANTIN I, FLORIAN D. A new look at projected gradient method for equilibrium assignment[J]. Transportation Research Record: Journal of the Transportation Research Board, 2009, 2090(1): 10-16.
[40] BABAZADEH A, JAVANI B, GENTILE G, et al. Reduced gradient algorithm for user equilibrium traffic assignment problem[J]. Transportmetrica A: Transport Science, 2020, 16(3): 1111-1135.
[41] PANICUCCI B, PAPPALARDO M, PASSACANTANDO M. A path-based double projection method for solving the asymmetric traffic network equilibrium problem[J]. Optimization Letters, 2007, 1(2): 171-185.
[42] PEREDERIEIEVA O, RAITH A, SCHMIDT M. Non-additive shortest path in the context of traffic assignment[J]. European Journal of Operational Research, 2018, 268(1): 325-338.
[43] FENG L Y, XIE J, NIE Y M, et al. Efficient algorithm for the traffic assignment problem with side constraints[J]. Transportation Research Record: Journal of the Transportation Research Board, 2020, 2674(4): 129-139.
[44] XU Z D, XIE J, LIU X B, et al. Hyperpath-based algorithms for the transit equilibrium assignment problem[J]. Transportation Research Part E: Logistics and Transportation Review, 2020, 143: 102102.
[45] ZHANG H G, LIU Z Y, WANG J, et al. A novel flow update policy in solving traffic assignment problems: successive over relaxation iteration method[J]. Transportation Research Part E: Logistics and Transportation Review, 2023, 174: 103111.
[46] DU M Q, TAN H Q, CHEN A. A faster path-based algorithm with Barzilai-Borwein step size for solving stochastic traffic equilibrium models[J]. European Journal of Operational Research, 2021, 290(3): 982-999.
[47] CHEN A, XU X D, RYU S, et al. A self-adaptive Armijo stepsize strategy with application to traffic assignment models and algorithms[J]. Transportmetrica A: Transport Science, 2013, 9(8): 695-712.
[48] ZHOU B, GAO L, DAI Y H. Gradient methods with adaptive step-sizes[J]. Computational Optimization and Applic-ations, 2006, 35(1): 69-86.
[49] DIAL R B. A path-based user-equilibrium traffic assignment algorithm that obviates path storage and enumeration[J]. Transportation Research Part B: Methodological, 2006, 40(10): 917-936.