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

doi:10.13229/j.cnki.jdxbgxb.20240792

Abstract

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

CLC Number:

U491

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.

Figures/Tables 11

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等

Table 1

Values of expected value， variance and resource consumption"

边	$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

Table 1

Table 2

Analysis of different reliability and penalty parameters"

序号	起终点	$λ$	$ρ$	下界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%

Table 2

Fig.1

Fig.2

Table 3

Most reliable path with different resource constraints under link travel time correlation"

序号	起终点	资源上限	下界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

Table 3

Table 4

Most reliable path with or without link travel time correlation under the same resource constraints"

序号	起终点	资源上限	有无相关性	最可靠路径
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

Table 4

Fig.3

Fig.4

Fig.5

Table 5

References 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.

Related Articles 15

[1]	Wen-hui ZHANG,Mei-ru YE,Cong XI,Zi-wen SONG. Vehicle formation and carbon emission characteristics in mixed traffic flow environment [J]. Journal of Jilin University(Engineering and Technology Edition), 2026, 56(2): 416-430.
[2]	Yu-sheng CI,Yi-kang HUANG. Overview of intersection vehicle-infrastructure integration based on bibliometrics [J]. Journal of Jilin University(Engineering and Technology Edition), 2026, 56(2): 313-332.
[3]	De-xin YU,Lu-chen WANG,Xin-cheng WU,Jian-yu MAO,Shi-long SHI. Multi-layer time dependent network path planning algorithm considering waiting time [J]. Journal of Jilin University(Engineering and Technology Edition), 2026, 56(2): 443-454.
[4]	Zhao-wei QU,Ming-yang WANG,Zhe WANG,Xian-min SONG,Yun-xiang ZHANG,Jing-cheng HUANG. Adaptive scheduling method for bus based on autonomous modular vehicles main⁃auxiliary function allocation [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(9): 2946-2957.
[5]	Chang-ru MU,Liang XU,Guo-zhu CHENG. Collision prevention performance of outsourced U-shaped steel concrete composite guardrail based on reasonable energy allocation [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(8): 2669-2680.
[6]	Yan-bo LI,Jing-yuan WANG,Yuan-yuan Chen,Shao-feng CHENG,Hao-nan LYU,Jun-shuo CHEN. RAMS assessment approach of self-consistent energy system in highway service areas [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(7): 2243-2250.
[7]	Xiao-feng JI,Ruo-fan DENG,Xin QIAO,Hao-tian GUAN. Nonlinear influence of built environment on temporal aggregation modes of shared bicycles [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(7): 2233-2242.
[8]	Sheng-yu YAN,Ming-jie CHENG,Hong-ce TIAN,Hong-yu WANG,Yong-heng ZHOU,Bo-hao MA. Scheduling algorithm for battery electric vehicle in closed scenic area [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(6): 1984-1993.
[9]	Yan-yan QIN,Teng-fei XIAO,Qin-zhong LUO,Bao-jie WANG. Car-following safety analysis and control strategy for foggy freeway [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(4): 1241-1249.
[10]	Xian-min SONG,Tian-shu ZHAN,Hai-tao LI,Bo LIU,Yun-xiang ZHANG. Reservation and allocation model considering user cost and utilization of parking space [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(4): 1287-1297.
[11]	Yi-yong PAN,Xiang-yu XU. Model for predicting severity of accidents based on MobileViT network considering imbalanced data [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(3): 947-953.
[12]	Yong-zheng YANG,Zhi-gang DU,Jia-lin MEI. Setting method and effect evaluation of linear guiding system in highway tunnels [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(12): 3885-3897.
[13]	Guang-yong CHEN,Shi-rui ZHOU,Chu-qing TAO,Li WAN,Wei WEI. Collaborative control of tunnel speed and lighting based on driver’s visual characteristics [J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(12): 3898-3906.
[14]	Xi-zhen ZHOU,He GONG,Dun-dun LI,Yan-jie JI,Jie YAN. Nonlinear model for impact of built environment on curb parking spaces occupancy [J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(9): 2520-2530.
[15]	Ya-qin QIN,Zheng-fu QIAN,Ji-ming XIE. Vehicle cooperative obstacle avoidance strategy driven by CLAM model and trajectory data [J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(5): 1311-1322.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

路径	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

Constrained most reliable path in stochastic traffic network alternating direction method of multipliers

RICH HTML

PDF (PC)