基于改进背压算法的车辆路线动态规划方法

doi:10.12068/j.issn.1005-3026.2025.20239037

摘要/Abstract

摘要：

为了缓解交通网络中的拥堵，提出了一种基于网联车密度和速度背压的车辆调度方法.考虑道路上车辆的复杂性和异质性，通过计算上、下游道路的车辆密度来确定背压值，并使用道路的最大通行速度作为权重.根据背压的比率调整上游车队分配至下游道路的车辆数量，从而实现车流的均衡分布.此外，以最小化车队行驶距离为优化目标确定单个车辆路线计划，以减少车辆的平均行驶距离.仿真结果表明，该方法比其他基于背压算法的路线动态规划方法，能有效减少交通网络中排队车辆的数量，从而降低交通拥堵，同时也缩短了车辆的平均行驶距离和时间.

关键词: 网联车, 车辆调度, 背压算法, 车辆路线动态规划, 交通拥堵

Abstract:

A vehicle scheduling method based on vehicle density and speed back‑pressure （BP） is proposed to alleviate traffic congestion in traffic network. Addressing the complexity and heterogeneity of vehicles， the calculation of the BP value is based on vehicle density on upstream and downstream roads， with maximum allowable speeds serving as weights. Then， the BP ratio is used to govern the number of vehicles allocated from the upstream fleet to the downstream road to balance the traffic flow. In addition， the shortest driving distance for the fleet is used as the optimization goal for individual vehicle routing to reduce the average travel distance. Simulation results show that the proposed method is more effective than other BP algorithm‑based dynamic vehicle routing methods in reducing queuing length and alleviating congestion， while decreasing the average travel distance and time for vehicles significantly.

Key words: connected vehicle, vehicle scheduling, back?pressure（BP） algorithm, dynamic vehicle routing, traffic congestion

中图分类号:

U 491.2

王硕, 吴维敏, 张涛. 基于改进背压算法的车辆路线动态规划方法[J]. 东北大学学报（自然科学版）, 2025, 46(1): 18-25.

Shuo WANG, Wei-min WU, Tao ZHANG. Dynamic Vehicle Routing Method Based on Improved Back-Pressure Algorithm[J]. Journal of Northeastern University(Natural Science), 2025, 46(1): 18-25.

图/表 9

图1 交通网络示意图

Fig.1 Diagram of traffic network

图2 交叉口相位示意图

Fig.2 Schematic diagram of intersection phases

图3 仿真交通网络

Fig.3 Simulated traffic network

图4 不同需求场景下同质车辆交通网络排队长度（a）—低需求；（b）—中需求；（c）—高需求.

Fig.4 Queuing length in homogeneous vehicle traffic network for different demand scenarios

图5 不同需求场景下同质车辆交通网络车辆平均行驶距离

Fig.5 Average travel distance in homogeneous vehicle traffic network for different demand scenarios

图6 不同需求场景下同质车辆交通网络车辆平均行驶时间

Fig.6 Average travel time of homogeneous vehicletraffic network for different demand scenarios

图7 不同需求场景下异质车辆交通网络排队长度（a）—低需求；（b）—中需求；（c）—高需求.

Fig.7 Queuing length in heterogeneous vehicle traffic network for different demand scenarios

图8 异质车辆交通网络不同需求场景下车辆平均行驶距离

Fig.8 Average travel distance in heterogeneous vehicle traffic network for different demand scenarios

图9 异质车辆交通网络不同需求场景下车辆平均行驶时间

Fig.9 Average travel time in heterogeneous vehicle traffic network for different demand scenarios

参考文献 20

1	Wang S， Djahel S， Zhang Z H，et al.Next road rerouting：a multiagent system for mitigating unexpected urban traffic congestion［J］.IEEE Transactions on Intelligent Transportation Systems，2016，17（10）：2888-2899.
2	Nagy G， Salhi S.Location‑routing：issues，models and methods［J］.European Journal of Operational Research，2007，177（2）：649-672.
3	Ben‑Akiva M E， Gao S， Wei Z，et al.A dynamic traffic assignment model for highly congested urban networks［J］.Transportation Research Part C：Emerging Technologies，2012，24：62-82.
4	Yuan C J， Yu X X， Li D W，et al.Overall traffic mode prediction by VOMM approach and AR mining algorithm with large‑scale data［J］.IEEE Transactions on Intelligent Transportation Systems，2018，20（4）：1508-1516.
5	Anas A.The cost of congestion and the benefits of congestion pricing：a general equilibrium analysis［J］.Transportation Research Part B：Methodological，2020，136：110-137.
6	Zheng L， Liu P J， Huang H M，et al.Time‑of‑day pricing for toll roads under traffic demand uncertainties：a distributionally robust simulation‑based optimization method［J］.Transportation Research Part C：Emerging Technologies，2022，144：103894.
7	万辛，高圣翔.基于群智感知技术的车联网路径优化问题研究［J］.计算机与数字工程，2017，45（9）：1765-1769.
	Wan Xin， Gao Sheng‑xiang.Research on path optimization of internet of vehicle based on crowd sensing technology［J］.Computer & Digital Engineering，2017，45（9）：1765-1769.
8	Tang C H， Hu W B， Hu S M，et al.Urban traffic route guidance method with high adaptive learning ability under diverse traffic scenarios［J］.IEEE Transactions on Intelligent Transportation Systems，2020，22（5）：2956-2968.
9	Lazar D A， Bıyık E， Sadigh D，et al.Learning how to dynamically route autonomous vehicles on shared roads［J］.Transportation Research Part C：Emerging Technologies，2021，130：103258.
10	Lazar D A， Coogan S， Pedarsani R.Routing for traffic networks with mixed autonomy［J］.IEEE Transactions on Automatic Control，2020，66（6）：2664-2676.
11	李妍峰，高自友，李军.基于实时交通信息的城市动态网络车辆路径优化问题［J］.系统工程理论与实践，2013，33（7）：1813-1819.
	Li Yan‑feng， Gao Zi‑you， Li Jun.Vehicle routing problem in dynamic urban network with real‑time traffic information［J］.Systems Engineering—Theory & Practice，2013，33（7）：1813-1819.
12	Zhu W L， Zhu C S， Cao Y J，et al.An intelligent route guidance strategy based on congestion type for ITS［C］//IEEE International Conference on Communications.Seoul，2022：5047-5052.
13	Pan J， Popa I S， Borcea C.DIVERT：a distributed vehicular traffic re‑routing system for congestion avoidance［J］.IEEE Transactions on Mobile Computing，2016，16（1）：58-72.
14	Chow A H F， Sha R， Li Y.Adaptive control strategies for urban network traffic via a decentralized approach with user‑optimal routing［J］.IEEE Transactions on Intelligent Transportation Systems，2019，21（4）：1697-1704.
15	Zaidi A A， Kulcsar B， Wymeersch H.Back‑pressure traffic signal control with fixed and adaptive routing for urban vehicular networks［J］.IEEE Transactions on Intelligent Transportation Systems，2016，17（8）：2134-2143.
16	Chen H Y， Wu F， Hou K Z，et al.Back pressure‑based distributed dynamic route control for connected and automated vehicles［J］.IEEE Transactions on Intelligent Transportation Systems，2022，23（11）：20953-20964.
17	Varaiya P.Max pressure control of a network of signalized intersections［J］.Transportation Research Part C：Emerging Technologies，2013，36：177-195.
18	Li L， Jabari S E.Position weighted backpressure intersection control for urban networks［J］.Transportation Research Part B：Methodological，2019，128：435-461.
19	Wang X M， Yin Y F， Feng Y H，et al.Learning the max pressure control for urban traffic networks considering the phase switching loss［J］.Transportation Research Part C：Emerging Technologies，2022，140： 103670.
20	Liu H， Gayah V V.A novel max pressure algorithm based on traffic delay［J］.Transportation Research Part C：Emerging Technologies，2022，143：103803.

[1]	李想, 孙振超, 高振宇. 基于固定时间扰动观测器的智能网联车辆协同队列控制[J]. 东北大学学报（自然科学版）, 2024, 45(11): 1521-1528.
[2]	杜子超，卢福强，王素欣，王雷震. 众包物流配送车辆调度模型及优化[J]. 东北大学学报（自然科学版）, 2021, 42(8): 1210-1216.
[3]	孔媛;唐加福;潘震东;董纲;. 基于集划分求解接送旅客到机场问题的启发式算法[J]. 东北大学学报(自然科学版), 2009, 30(5): 625-627+660.
[4]	宋伟刚;张宏霞;佟玲;. 有时间窗约束非满载车辆调度问题的节约算法[J]. 东北大学学报(自然科学版), 2006, 27(1): 65-68.