随机交通网络约束最可靠路径乘子交替方向法

doi:10.13229/j.cnki.jdxbgxb.20240792

摘要/Abstract

摘要：

为分析行程时间相关性和资源约束对交通网络最可靠路径选择的影响，建立考虑行程时间相关性的随机交通网络约束最可靠路径模型，提出了改进乘子交替方向法的求解方法。通过Cholesky分解和二次项放缩，将目标函数转化为可分离结构的矩阵形式，采用块坐标下降法将增广拉格朗日松弛问题分解为一系列子问题，上下界迭代获得近似最优解。针对Sioux Falls网络和Chicago sketch网络进行数值模拟试验并对比分析改进交替方向法和拉格朗日松弛算法的性能。结果表明：有无路段行程时间相关性的约束最可靠路径问题是有区别的；行程时间相关性和资源约束对最可靠路径的选择有显著影响；改进乘子交替方向法的计算效率和收敛性优于拉格朗日松弛算法。

关键词: 交通运输系统工程, 随机网络, 约束最可靠路径, 行程时间相关性, 乘子交替方向法

Abstract:

In order to analyze the influence of travel time correlation and resource constraints on the selection of the most reliable path in traffic network， the model of the constrained most reliable path with stochastic traffic network considering travel time correlation is established， and the solution method of improved alternating direction method of multipliers is proposed. By Cholesky decomposition and quadratic term deflation， the objective function is transformed into a matrix form of separable structure， and the augmented Lagrangian relaxation problem is decomposed into a series of subproblems by the block coordinate descent method， the upper and lower bounds are iterated to obtain the approximate optimal solution. Numerical simulation experiments are carried out for Sioux Falls network and Chicago sketch network， and the performance of improved alternating direction method of multipliers and Lagrangian relaxation algorithm is compared and analyzed. The results show that the most reliable path problem with or without link travel time correlation is different， the travel time correlation and resource constraints have a significant impact on the selection of the most reliable path， the computational efficiency and convergence of the improved alternating direction method of multipliers are superior to the Lagrangian relaxation algorithm.

Key words: engineering of communication and transportation system, stochastic network, constrained most reliable path, travel time correlation, alternating direction method of multipliers

中图分类号:

U491

潘义勇,曹天宇,刘宇. 随机交通网络约束最可靠路径乘子交替方向法[J]. 吉林大学学报(工学版), 2026, 56(2): 455-463.

Yi-yong PAN,Tian-yu CAO,Yu LIU. Constrained most reliable path in stochastic traffic network alternating direction method of multipliers[J]. Journal of Jilin University(Engineering and Technology Edition), 2026, 56(2): 455-463.

图/表 11

算法1

基于改进乘子交替方向法分解的可靠路径求解算法伪代码"

1	输入：网络节点 $x_c o o r d i n a t e, y_c o o r d i n a t e$
2	路段权值 $c i j, σ i j 2, w i j, C o v i j, k l$
3	初始参数 $μ, v, ρ, U B, L B$
4	最短路径求解：
5	while epsilon_hat <= epsilon or k<30：是否满足相对间隙
6	for head， tail in g_link_list：遍历所有的边
7	if node_label_cost［tail］ > node_label_cost［head］ + Distance［head， tail］：检查是否有路径更短，进行更新
8	end if
9	break
10	最短路径生成：
11	if g_origin！= destination_node：起点和目标节点不同
12	if node_label_cost［destination_node］ == Max_lab-el_cost：目标节点的最短路径成本
13	else：
14	agent_id += 1
15	end if
16	迭代：
17	计算LB， UB， new_mu， new_v
18	epsilon更新为（UB-LB）/UB
19 20	k=k+1 输出：路径解、LB和UB等

算法1

表1

期望值、方差和资源消耗的取值"

边	$c$	$σ 2$	$w$	边	$c$	$σ 2$	$w$	边	$c$	$σ 2$	$w$
（1，2）	3.90	7.80	3.06	（10，11）	7.34	14.68	3.54	（17，19）	2.75	5.50	4.77
（1，3）	8.16	16.32	6.16	（10，15）	5.71	11.42	9.71	（18，7）	2.48	4.96	5.29
（2，1）	3.17	6.34	6.39	（10，16）	1.76	3.52	3.46	（18，16）	4.51	9.02	3.66
（2，6）	8.14	16.28	3.54	（10，17）	9.57	19.14	8.86	（18，20）	2.27	4.54	6.34
（3，1）	7.89	15.78	4.10	（11，4）	2.65	5.30	4.54	（19，15）	8.04	16.08	1.07
（3，4）	8.52	17.04	4.84	（11，10）	9.24	18.48	4.13	（19，17）	9.86	19.72	1.82
（3，12）	5.05	10.10	4.45	（11，12）	2.23	4.46	2.17	（19，20）	0.29	0.58	2.99
（4，3）	6.35	12.70	3.76	（11，14）	3.73	7.46	1.25	（20，18）	5.35	10.70	4.89
（4，5）	9.50	19.00	3.88	（12，3）	0.87	1.74	3.08	（20，19）	0.87	1.74	1.93
（4，11）	4.43	8.86	7.66	（12，11）	6.40	12.80	7.26	（20，21）	8.02	16.04	8.95
（5，4）	0.60	1.20	3.36	（12，13）	1.80	3.60	7.82	（20，22）	9.89	19.78	5.57
（5，6）	8.66	17.32	6.62	（13，12）	0.45	0.90	6.93	（21，20）	0.66	1.32	0.44
（5，9）	6.31	12.62	2.44	（13，24）	7.23	14.46	5.09	（21，22）	9.39	18.78	5.57
（6，2）	3.55	7.10	2.95	（14，11）	3.47	6.94	8.43	（21，24）	0.18	0.36	4.72
（6，5）	9.97	19.94	6.80	（14，15）	6.60	13.20	9.22	（22，15）	6.83	13.66	3.11
（6，8）	2.24	4.48	5.27	（14，23）	3.83	7.66	7.70	（22，20）	7.83	15.66	1.78
（7，8）	6.52	13.04	4.11	（15，10）	6.27	12.54	2.42	（22，21）	5.34	10.68	3.38
（7，18）	6.04	12.08	6.02	（15，14）	0.21	0.42	3.78	（22，23）	8.85	17.70	2.10
（8，6）	3.87	7.74	7.50	（15，19）	9.10	18.20	4.04	（23，14）	8.99	17.98	5.10
（8，7）	1.42	2.84	5.83	（15，22）	8.00	16.00	5.29	（23，22）	6.25	12.50	3.06
（8，9）	0.25	0.50	5.51	（16，8）	7.45	14.90	2.24	（23，24）	1.37	2.74	6.28
（8，16）	4.21	8.42	5.83	（16，10）	8.13	16.26	2.69	（24，13）	2.17	4.34	7.01
（9，5）	1.84	3.68	5.11	（16，17）	3.83	7.66	6.73	（24，21）	1.82	3.64	3.90
（9，8）	7.25	14.50	0.82	（16，18）	6.17	12.34	4.77	（24，23）	0.41	0.82	5.54
（9，10）	3.70	7.40	7.19	（17，10）	5.75	11.50	6.23
（10，9）	8.41	16.82	9.96	（17，16）	5.30	10.60	2.36

表1

表2

不同可靠度和惩罚参数分析"

序号	起终点	$λ$	$ρ$	下界LB	上界UB	迭代次数	相对间隙
1	1→24	2	0.1	36.09	37.42	38	3.56%
2	1→24	0.5	0.1	25.29	26.03	11	2.85%
3	1→24	2	1	37.19	37.42	5	0.61%
4	2→23	2	0.1	61.94	64.34	26	3.71%
5	2→23	0.5	0.1	45.84	47.41	13	3.29%
6	2→23	2	1	65.44	64.34	4	-1.72%

表2

图1

图2

表3

路段行程时间相关条件下不同资源约束的最可靠路径"

序号	起终点	资源上限	下界LB	上界UB	$ε$	最可靠路径
1	1→23	$W = + ∞$	39.92	41.31	3.35	1→3→12→13→24→23
2	1→23	$W = 29$	44.21	45.39	2.59	1→3→12→11→14→23
3	3→17	$W = + ∞$	48.49	50.02	3.06	3→4→5→9→10→16→17
4	3→17	$W = 28$	53.20	54.94	3.16	3→4→5→9→10→17
5	4→20	$W = + ∞$	42.91	43.74	3.05	4→5→9→10→16→18→20
6	4→20	$W = 26$	43.75	45.12	1.91	4→11→14→15→19→20

表3

表4

相同资源约束条件下有无路段行程时间相关性的最可靠路径"

序号	起终点	资源上限	有无相关性	最可靠路径
1	3→17	$W = + ∞$	无	3→12→11→10→16→17
2	3→17	$W = + ∞$	有	3→4→5→9→10→16→17
3	3→17	$W = 28$	无	3→4→5→9→10→17
4	3→17	$W = 28$	有	3→4→5→9→10→17
5	3→18	$W = + ∞$	无	3→4→5→9→10→16→18
6	3→18	$W = + ∞$	有	3→12→11→10→16→18
7	4→18	$W = 25$	无	4→5→9→10→16→18
8	4→18	$W = 25$	有	4→11→10→16→18

表4

图3

图4

图5

表5

参考文献 15

[1]	Chen P, Tong R, Yu B, et al. Reliable shortest path finding in stochastic time-dependent road network with spatial-temporal link correlations: a case study from Beijing[J]. Expert Systems with Applications, 2020, 147: 113192.
[2]	Rajabi B M, Shariat M A, Babaei M, et al. Reliable vehicle routing problem in stochastic networks with correlated travel times[J]. Operational Research, 2021, 21: 299-330.
[3]	Shen L, Shao H, Wu T, et al. Finding the reliable shortest path with correlated link travel times in signalized traffic networks under uncertainty[J]. Transportation Research Part E: Logistics and Transportation Review, 2020, 144: 02159.
[4]	Zockaie A, Mahmassani H S, Nie Y. Path finding in stochastic time varying networks with spatial and temporal correlations for heterogeneous travelers[J]. Transportation Research Record, 2016(1): 105-113.
[5]	Zhang D, Wallace S W, Guo Z, et al. On scenario construction for stochastic shortest path problems in real road networks[J]. Transportation Research Part E: Logistics and Transportation Review, 2021, 152: 102410.
[6]	Pugliese L D P, Guerriero F, Poss M. The resource constrained shortest path problem with uncertain data: a robust formulation and optimal solution approach[J]. Computers & Operations Research, 2019, 107: 140-155.
[7]	Nie Y M, Li Q. An eco-routing model considering microscopic vehicle operating conditions[J]. Transportation Research Part B: Methodological, 2013, 55: 154-170.
[8]	潘义勇, 马健霄. 基于可靠性的随机交通网络约束最优路径问题[J]. 东南大学学报:自然科学版, 2017, 47(6): 1263-1268.
	Pan Yi-yong, Ma Jian-xiao. Constrained shortest path problem in stochastic traffic network based on reliability[J]. Journal of Southeast University (Natural Science Edition), 2017, 47(6): 1263-1268.
[9]	Zeng W, Miwa T, Morikawa T. Eco-routing problem considering fuel consumption and probabilistic travel time budget[J]. Transportation Research Part D: Transport and Environment, 2020, 78: 102219.
[10]	Thomas B W, Calogiuri T, Hewitt M. An exact bidirectional A* approach for solving resource-constrained shortest path problems[J]. Networks, 2019, 73(2): 187-205.
[11]	Prakash A A. Algorithms for most reliable routes on stochastic and time-dependent networks[J]. Transportation Research Part B: Methodological, 2020, 138: 202-220.
[12]	Yang L, Zhou X. Optimizing on-time arrival probability and percentile travel time for elementary path finding in time-dependent transportation networks: linear mixed integer programming reformulations[J]. Transportation Research Part B: Methodological, 2017, 96: 68-91.
[13]	Song M, Cheng L. An augmented lagrangian relaxation method for the mean-standard deviation based vehicle routing problem[J]. Knowledge-Based Systems, 2022, 247: 108736.
[14]	Yao Y, Zhu X, Dong H, et al. ADMM-based problem decomposition scheme for vehicle routing problem with time windows[J]. Transportation Research Part B: Methodological, 2019, 129: 156-174.
[15]	Song M, Cheng L. Solving the reliability-oriented generalized assignment problem by lagrangian relaxation and alternating direction method of multipliers[J]. Expert Systems with Applications, 2022, 205: 117644.

相关文章 15

[1]	张文会,叶梅茹,席聪,宋子文. 混合交通流环境下车辆编队与碳排放特性[J]. 吉林大学学报(工学版), 2026, 56(2): 416-430.
[2]	慈玉生,黄轶康. 基于文献计量的交叉口车路协同研究综述[J]. 吉林大学学报(工学版), 2026, 56(2): 313-332.
[3]	马壮林,毕宇明,周备,邓亚娟,兆雪. 公交换乘优惠政策下居民换乘意向的异质性分析[J]. 吉林大学学报(工学版), 2026, 56(1): 158-169.
[4]	曲昭伟,王铭阳,王喆,宋现敏,张云翔,黄镜尘. 基于自动驾驶模块化车辆主辅功能分配的公交自适应调度方法[J]. 吉林大学学报(工学版), 2025, 55(9): 2946-2957.
[5]	王琳虹,刘宇阳,刘子昱,鹿应佳,张宇恒,黄桂树. 基于YOLOv5的轻量化桥梁缺陷识别[J]. 吉林大学学报(工学版), 2025, 55(9): 2958-2968.
[6]	张云翔,宋现敏,谢渝,湛天舒. 基于用户满意度的停车预约服务智能体行为仿真[J]. 吉林大学学报(工学版), 2025, 55(9): 2978-2984.
[7]	穆长儒,徐亮,程国柱. 基于能量合理分配的外包U型钢-混凝土组合护栏防撞性能[J]. 吉林大学学报(工学版), 2025, 55(8): 2669-2680.
[8]	李艳波,汪静远,陈圆媛,程绍峰,吕浩楠,陈俊硕. 面向高速公路服务区自洽能源系统的RAMS评价方法[J]. 吉林大学学报(工学版), 2025, 55(7): 2243-2250.
[9]	戢晓峰,邓若凡,乔新,关昊天. 建成环境对共享单车时间集聚模式的非线性影响[J]. 吉林大学学报(工学版), 2025, 55(7): 2233-2242.
[10]	于江波,翁剑成,林鹏飞,孙宇星,柴娇龙. 基于混合Transformer的对外客运枢纽抵站客流预测模型[J]. 吉林大学学报(工学版), 2025, 55(7): 2251-2259.
[11]	柴树山,周志强,李海涛,徐炅旸. 基于图时空模式学习网络的路网实时交通事件自动检测方法[J]. 吉林大学学报(工学版), 2025, 55(7): 2145-2161.
[12]	赵红专,吴泽健,张鑫,石胜文,李文勇,展新,许恩永,王佳明. 基于密度离散度和信息传输延迟的网联商用车弯道格子模型[J]. 吉林大学学报(工学版), 2025, 55(6): 2015-2029.
[13]	闫晟煜,程铭杰,田宏策,王洪瑀,周永恒,马博浩. 封闭式景区纯电动客车调度方法[J]. 吉林大学学报(工学版), 2025, 55(6): 1984-1993.
[14]	潘福全,牛远征,张丽霞,杨金顺,陈秀锋,陈德启. 智能网联环境下无信号交叉口车辆通行控制策略[J]. 吉林大学学报(工学版), 2025, 55(6): 1948-1962.
[15]	潘义勇,徐家聪,尤逸文,全勇俊. 网约车出行需求影响因素多尺度空间异质性分析[J]. 吉林大学学报(工学版), 2025, 55(5): 1567-1575.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

路径	LR					ADMM
路径	时间/s	迭代次数	下界LB	上界UB	相对间隙/%	时间/s	迭代次数	下界LB	上界UB	相对间隙/%
1	82	30	73.86	77.81	5.08	70	30	70.17	72.98	3.85
2	78	28	66.28	69.21	4.24	81	28	61.61	63.74	3.34
3	62	25	72.02	76.71	6.12	56	25	70.55	73.80	4.40
4	76	28	83.91	87.96	4.61	74	24	81.40	84.61	3.80
5	67	33	62.91	65.10	3.36	59	29	62.51	64.05	2.39