Dynamic Vehicle Routing Method Based on Improved Back-Pressure Algorithm

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

CLC Number:

U 491.2

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.

Figures/Tables 9

Fig.1 Diagram of traffic network

Fig.2 Schematic diagram of intersection phases

Fig.3 Simulated traffic network

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

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

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

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

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

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

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